Pith. sign in

REVIEW 2 major objections 1 minor 1 cited by

Entity Resolution via Batched Oracle Queries

T0 review · 2 major / 1 minor · reviewed 2026-06-25 · grok-4.3

Pith's one-line read Batched entity resolution casts oracle query selection as an NP-hard problem with an optimal solution when entity sizes satisfy a natural condition.

desk verdict Batched oracle model for ER adds NP-hardness proof and conditional optimal algorithm, but the load-bearing size condition stays underspecified. read the letter →

arxiv 2606.24407 v1 pith:L533QI6Q submitted 2026-06-23 cs.DB cs.AI

classification cs.DBcs.AI
keywords entityresolutionbatchedqueriesoracleNP-hardnessbatchselectiondataintegrationrecalloptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies how to resolve entities across a large dataset when an oracle can only examine limited batches of records and cluster matches within each batch. It defines the problem of selecting which batches to submit so that recall grows steadily while the total number of oracle calls stays under explicit control. The authors prove that finding the optimal sequence of batches is NP-hard in general, then give a polynomial-time optimal method that works whenever entity sizes obey a stated regularity condition. Experiments on six datasets show the method exceeds standard baselines in recall per oracle call.

What carries the argument

The batched entity resolution formulation together with the polynomial-time optimal batch selector that applies when entity sizes meet the regularity condition.

What would settle it

A dataset whose entity-size distribution violates the stated condition, on which the proposed selector fails to match or exceed the recall of a simple greedy baseline at the same number of oracle calls.

Watch

Extended reading notes

Core claim

We formally cast this problem as batched entity resolution, prove that selecting optimal batches is NP-hard, and provide an optimal solution under a natural condition on entity sizes. Finally, we evaluate our approach on six datasets and show its superiority over state-of-the-art baselines.

Load-bearing premise

The claimed optimal batch selector works only when the dataset obeys a stated natural condition on the sizes of its entities.

Editorial extensions

If this is right

  • Users obtain explicit, incremental control over the total number of oracle consultations while recall improves at each step.
  • The pay-as-you-go property lets practitioners stop querying once a target recall is reached rather than committing to a fixed budget in advance.
  • Under the size condition the method is guaranteed to be optimal, removing the need for heuristic search over batch choices.
  • The same modeling framework applies to any oracle that returns clusters within a supplied batch rather than pairwise decisions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the size condition holds for most real-world entity-resolution collections, the NP-hardness result mainly serves as a warning against brute-force search rather than a barrier to practice.
  • The pay-as-you-go framing could extend to other oracle-limited tasks such as deduplication in streams or active learning loops that request labels in batches.
  • Relaxing the size condition while retaining near-optimality would require approximation algorithms whose guarantees the paper leaves open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 1 minor

Summary. The paper formalizes the problem of batched entity resolution, where an oracle clusters records from limited-size batches that may not contain all mentions of any entity. It proves that selecting optimal batches is NP-hard and claims an optimal solution exists under a natural condition on entity sizes. It then evaluates the approach on six datasets, reporting superiority over state-of-the-art baselines in a pay-as-you-go setting that controls oracle consult costs while maximizing recall.

Significance. If the hardness result and conditional optimality hold with the condition explicitly stated and verified, the work would provide a useful theoretical framing for entity resolution under batch-oracle constraints, along with a practical algorithm and empirical evidence of improvement. The new formalization and complexity analysis are the primary contributions; the six-dataset evaluation strengthens the case for applicability if the modeling assumptions are met.

major comments (2)
  1. [Abstract] Abstract: The optimality claim rests entirely on an unspecified 'natural condition on entity sizes.' Without an explicit definition of this condition (e.g., bounded maximum entity size or a distributional requirement) and a verification that the six evaluation datasets satisfy it, the route from the NP-hardness result to a practical optimal algorithm cannot be assessed, undermining the central practical claim.
  2. [Abstract] Abstract (and implied § on algorithm): The paper states it provides 'an optimal solution under a natural condition,' yet the abstract gives no derivation outline or section reference for how the condition enables polynomial-time optimality. This is load-bearing because the NP-hardness result alone does not yield a usable algorithm without the condition.
minor comments (1)
  1. [Abstract] The abstract mentions 'six datasets' but provides no names, sizes, or entity-size statistics; adding these details would allow readers to check the condition themselves.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback. We address the major comments point by point below.

read point-by-point responses
  1. Referee: [Abstract] Abstract: The optimality claim rests entirely on an unspecified 'natural condition on entity sizes.' Without an explicit definition of this condition (e.g., bounded maximum entity size or a distributional requirement) and a verification that the six evaluation datasets satisfy it, the route from the NP-hardness result to a practical optimal algorithm cannot be assessed, undermining the central practical claim.

    Authors: We agree that the abstract would benefit from an explicit definition of the condition to make the optimality claim self-contained. The condition is defined in the body of the manuscript; we will revise the abstract to include a concise statement of the condition along with confirmation that the six datasets satisfy it based on their entity-size distributions. revision: yes

  2. Referee: [Abstract] Abstract (and implied § on algorithm): The paper states it provides 'an optimal solution under a natural condition,' yet the abstract gives no derivation outline or section reference for how the condition enables polynomial-time optimality. This is load-bearing because the NP-hardness result alone does not yield a usable algorithm without the condition.

    Authors: We will revise the abstract to add a reference to the section containing the derivation of the conditional polynomial-time optimality result. This will clarify the logical connection between the NP-hardness proof and the practical algorithm. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper introduces a formalization of batched entity resolution as a new problem, proves NP-hardness of optimal batch selection, states an optimal solution under an explicitly declared condition on entity sizes, and validates via evaluation on six external datasets. No equations, definitions, or claims reduce the central results to self-definitional inputs, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained with independent theoretical content and falsifiable external benchmarks.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The central claim rests on the oracle correctly clustering matches inside each batch and on the existence of a usable condition on entity sizes; no free parameters or invented entities are introduced in the abstract.

assumptions (1)
  • domain assumption The oracle returns correct clusters for records that refer to the same entity within any given batch.
    Stated as the definition of the oracle in the problem setup.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Entity Resolution via Batched Oracle Queries." pith.science (2026). https://pith.science/paper/L533QI6Q

@misc{pith2026260624407,
  author       = {Pith},
  title        = {Pith review of: Entity Resolution via Batched Oracle Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L533QI6Q}},
  note         = {Machine review of arXiv:2606.24407}
}
read the original abstract

We consider an oracle that processes a limited batch of records at a time and clusters those that refer to the same real-world entity. We study how to interrogate such an oracle to resolve entities in a dataset whose size is far larger than a single batch, and where no batch is guaranteed to contain all records of any given entity. We aim at a pay-as-you-go approach, to have full control over the costs (the number of oracle consults), while achieving the highest possible recall at every step. We formally cast this problem as batched entity resolution, prove that selecting optimal batches is NP-hard, and provide an optimal solution under a natural condition on entity sizes. Finally, we evaluate our approach on six datasets and show its superiority over state-of-the-art baselines.

Figures

Figures reproduced from arXiv: 2606.24407 by the authors.

Figure 1
Figure 1. (a) Entity Resolution workflow with an oracle: [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Schematic representation of the pERbacco algorithm, highlighting its core components. Independent of the specific similarity model, ER systems must address the quadratic complexity of pairwise compar￾isons. For this reason, similarity computation is almost always coupled with blocking and indexing techniques, whose goal is to restrict similarity evaluation to promising candidate pairs. A large body of work investiga… view at source ↗
Figure 3
Figure 3. A similarity graph with match (solid green) and non [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Progressive recall on real and synthetic datasets with [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Progressive recall on Cora for pERbacco and Oracle under the same LLM setting (GPT-5 mini, few￾shot, 10 positive and 10 negative example pairs), for batch sizes b ∈ {2, 5, 10, 20}. The x-axis reports the query budget normalized by ϕb, so curves with different batch siz…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Beyond Scale and Generation: Understanding Language Model-based Entity Matching

    cs.DB 2026-07 accept novelty 6.0 of 10

    Disentangling architecture, pretraining variant, and size shows embedding init is decisive for bi-encoders, joint encoding beats independent encoding, and generative matchers mainly help under distribution shift—not u...

Reference graph

Works this paper leans on

52 extracted references · 5 canonical work pages · cited by 1 Pith paper

  1. [1]

    An overview of end-to-end entity resolution for big data,

    V . Christophides, V . Efthymiou, T. Palpanas, G. Papadakis, and K. Ste- fanidis, “An overview of end-to-end entity resolution for big data,”ACM Comput. Surv., vol. 53, no. 6, pp. 127:1–127:42, 2021

  2. [2]

    Effective entity matching with transformers,

    Y . Li, J. Li, Y . Suhara, A. Doan, and W. Tan, “Effective entity matching with transformers,”VLDB J., vol. 32, no. 6, pp. 1215–1235, 2023

  3. [3]

    Progres- sive entity matching: A design space exploration,

    J. Maciejewski, K. Nikoletos, G. Papadakis, and Y . Velegrakis, “Progres- sive entity matching: A design space exploration,”PACMMOD, vol. 3, no. 1, Feb. 2025

  4. [4]

    Three-dimensional entity resolution with jedai,

    G. Papadakis, G. M. Mandilaras, L. Gagliardelli, G. Simonini, E. Thanos, G. Giannakopoulos, S. Bergamaschi, T. Palpanas, and M. Koubarakis, “Three-dimensional entity resolution with jedai,”Inf. Syst., vol. 93, p. 101565, 2020

  5. [5]

    Magellan: toward building ecosystems of entity matching solutions,

    A. Doan, P. Konda, P. S. G. C., Y . Govind, D. Paulsen, K. Chandrasekhar, P. Martinkus, and M. Christie, “Magellan: toward building ecosystems of entity matching solutions,”Commun. ACM, vol. 63, no. 8, pp. 83–91, 2020

  6. [6]

    Deepblock: A novel blocking approach for entity resolution using deep learning,

    D. Javdani, H. Rahmani, M. Allahgholi, and F. Karimkhani, “Deepblock: A novel blocking approach for entity resolution using deep learning,” inICWR, 2019, pp. 41–44

  7. [7]

    Pay-as-you-go entity resolution,

    S. E. Whang, D. Marmaros, and H. Garcia-Molina, “Pay-as-you-go entity resolution,”IEEE TKDE, vol. 25, no. 5, pp. 1111–1124, 2013

  8. [8]

    Aspdup: Ast-sequence- based progressive duplicate code detection tool for onsite programming code,

    Y . Yu, Z. Huang, Y . Zhou, W. Li, and Y . Shao, “Aspdup: Ast-sequence- based progressive duplicate code detection tool for onsite programming code,” inInternetware, 2020, pp. 260–264

Show all 52 references
  1. [9]

    Schema- agnostic progressive entity resolution,

    G. Simonini, G. Papadakis, T. Palpanas, and S. Bergamaschi, “Schema- agnostic progressive entity resolution,”IEEE TKDE, vol. 31, no. 6, pp. 1208–1221, 2019

  2. [10]

    Online entity resolution using an oracle,

    D. Firmani, B. Saha, and D. Srivastava, “Online entity resolution using an oracle,”PVLDB, vol. 9, no. 5, pp. 384–395, 2016

  3. [11]

    A theory for record linkage,

    I. P. Fellegi and A. B. Sunter, “A theory for record linkage,”J. Am. Stat. Assoc., vol. 64, no. 328, pp. 1183–1210, 1969

  4. [12]

    Set transformer: A framework for attention-based permutation-invariant neural networks,

    J. Lee, Y . Lee, J. Kim, A. R. Kosiorek, S. Choi, and Y . W. Teh, “Set transformer: A framework for attention-based permutation-invariant neural networks,” inICML, 2019, pp. 3744–3753

  5. [13]

    Match, compare, or select? an investigation of large language models for entity matching,

    T. Wang, X. Chen, H. Lin, X. Chen, X. Han, L. Sun, H. Wang, and Z. Zeng, “Match, compare, or select? an investigation of large language models for entity matching,” inCOLING, 2025, pp. 96–109

  6. [14]

    Crowder: Crowdsourc- ing entity resolution,

    J. Wang, T. Kraska, M. J. Franklin, and J. Feng, “Crowder: Crowdsourc- ing entity resolution,”PVLDB, vol. 5, no. 11, pp. 1483–1494, 2012

  7. [15]

    Facenet: A unified embed- ding for face recognition and clustering,

    F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embed- ding for face recognition and clustering,” inCVPR, 2015, pp. 815–823

  8. [16]

    Waldo: An adaptive human interface for crowd entity resolution,

    V . Verroios, H. Garcia-Molina, and Y . Papakonstantinou, “Waldo: An adaptive human interface for crowd entity resolution,” inSIGMOD, 2017, pp. 1133–1148

  9. [17]

    Training language models to follow instructions with human feedback,

    L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe, “Training language models to follow instructi...

  10. [18]

    A demonstration of PERC: probabilistic entity resolution with crowd errors,

    X. Ke, M. Teo, A. Khan, and V . K. Yalavarthi, “A demonstration of PERC: probabilistic entity resolution with crowd errors,”PVLDB, vol. 11, no. 12, pp. 1922–1925, 2018

  11. [19]

    Robust entity resolution using a crowdoracle,

    D. Firmani, S. Galhotra, B. Saha, and D. Srivastava, “Robust entity resolution using a crowdoracle,”IEEE Data Eng. Bull., vol. 41, no. 2, pp. 91–103, 2018

  12. [20]

    Crowd-based deduplication: An adaptive approach,

    S. Wang, X. Xiao, and C. Lee, “Crowd-based deduplication: An adaptive approach,” inSIGMOD, T. K. Sellis, S. B. Davidson, and Z. G. Ives, Eds., 2015, pp. 1263–1277

  13. [21]

    Select your questions wisely: For entity resolution with crowd errors,

    V . K. Yalavarthi, X. Ke, and A. Khan, “Select your questions wisely: For entity resolution with crowd errors,” inCIKM, 2017, pp. 317–326

  14. [22]

    A linear programming approach to the cutting-stock problem,

    P. C. Gilmore and R. E. Gomory, “A linear programming approach to the cutting-stock problem,”Oper. Res., vol. 9, no. 6, pp. 849–859, 1961

  15. [23]

    Multi-way number partitioning

    R. E. Korf, “Multi-way number partitioning.” inIJCAI, vol. 9, 2009, pp. 538–543

  16. [24]

    The densek-subgraph problem,

    U. Feige, D. Peleg, and G. Kortsarz, “The densek-subgraph problem,” Algorithmica, vol. 29, no. 3, pp. 410–421, Mar. 2001

  17. [25]

    Christen,Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection, ser

    P. Christen,Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection, ser. Data-Centric Systems and Applications. Springer, 2012

  18. [26]

    Sparkly: A simple yet surprisingly strong TF/IDF blocker for entity matching,

    D. Paulsen, Y . Govind, and A. Doan, “Sparkly: A simple yet surprisingly strong TF/IDF blocker for entity matching,”PVLDB, vol. 16, no. 6, pp. 1507–1519, 2023

  19. [27]

    Deep entity matching with pre-trained language models,

    Y . Li, J. Li, Y . Suhara, A. Doan, and W.-C. Tan, “Deep entity matching with pre-trained language models,”arXiv preprint arXiv:2004.00584, 2020

  20. [28]

    Using chatgpt for entity matching,

    R. Peeters and C. Bizer, “Using chatgpt for entity matching,” inADBIS, 2023, pp. 221–230

  21. [29]

    Sudowoodo: Contrastive self-supervised learning for multi-purpose data integration and preparation,

    R. Wang, Y . Li, and J. Wang, “Sudowoodo: Contrastive self-supervised learning for multi-purpose data integration and preparation,” inICDE, 2023, pp. 1502–1515

  22. [30]

    A survey of indexing techniques for scalable record linkage and deduplication,

    P. Christen, “A survey of indexing techniques for scalable record linkage and deduplication,”IEEE TKDE, vol. 24, no. 9, pp. 1537–1555, 2012

  23. [31]

    Scaling entity resolution to large, heterogeneous data with enhanced meta-blocking

    G. Papadakis, G. Papastefanatos, T. Palpanas, and M. Koubarakis, “Scaling entity resolution to large, heterogeneous data with enhanced meta-blocking.” inEDBT, 2016, pp. 221–232

  24. [32]

    GSM: A generalized approach to supervised meta-blocking for scalable entity resolution,

    L. Gagliardelli, G. Papadakis, G. Simonini, S. Bergamaschi, and T. Pal- panas, “GSM: A generalized approach to supervised meta-blocking for scalable entity resolution,”Inf. Syst., vol. 120, p. 102307, 2024

  25. [33]

    Deep learning for blocking in entity matching: a design space exploration,

    S. Thirumuruganathan, H. Li, N. Tang, M. Ouzzani, Y . Govind, D. Paulsen, G. Fung, and A. Doan, “Deep learning for blocking in entity matching: a design space exploration,”PVLDB, vol. 14, no. 11, pp. 2459–2472, 2021

  26. [34]

    Alaska: A flexible benchmark for data integration tasks,

    V . Crescenzi, A. De Angelis, D. Firmani, M. Mazzei, P. Merialdo, F. Piai, and D. Srivastava, “Alaska: A flexible benchmark for data integration tasks,”arXiv preprint arXiv:2101.11259, 2021

  27. [35]

    Wdc products: A multi-dimensional entity matching benchmark,

    R. Peeters, R. C. Der, and C. Bizer, “Wdc products: A multi-dimensional entity matching benchmark,”arXiv preprint arXiv:2301.09521, 2023

  28. [36]

    Mdedup: duplicate detection with matching dependencies,

    l. Koumarelas, T. Papenbrock, and F. Naumann, “Mdedup: duplicate detection with matching dependencies,”PVLDB, vol. 13, no. 5, pp. 712– 725, Jan. 2020

  29. [37]

    Fast unfolding of communities in large networks,

    V . D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,”J. Stat. Mech., vol. 2008, no. 10, p. P10008, 2008

  30. [38]

    From louvain to leiden: guaranteeing well-connected communities,

    V . A. Traag, L. Waltman, and N. J. Van Eck, “From louvain to leiden: guaranteeing well-connected communities,”Sci. Rep., vol. 9, no. 1, pp. 1–12, 2019

  31. [39]

    Near linear time algorithm to detect community structures in large-scale networks,

    U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,”Phys. Rev. E, vol. 76, no. 3, p. 036106, 2007

  32. [40]

    The map equation,

    M. Rosvall, D. Axelsson, and C. T. Bergstrom, “The map equation,” Eur. Phys. J. Spec. Top., vol. 178, no. 1, pp. 13–23, 2009

  33. [41]

    Network community detection: A review and visual survey,

    B. S. Khan and M. A. Niazi, “Network community detection: A review and visual survey,”arXiv preprint arXiv:1708.00977, 2017

  34. [42]

    Cost-effective in-context learning for entity resolution: A design space exploration,

    M. Fan, X. Han, J. Fan, C. Chai, N. Tang, G. Li, and X. Du, “Cost-effective in-context learning for entity resolution: A design space exploration,” in2024 IEEE 40th International Conference on Data Engineering (ICDE), 2024, pp. 3696–3709

  35. [43]

    Avenger: Ensembling and fine-tuning llms for select prompts in entity resolution,

    A. Zeakis, G. Papadakis, D. Skoutas, and M. Koubarakis, “Avenger: Ensembling and fine-tuning llms for select prompts in entity resolution,” inThe Semantic Web. Cham: Springer Nature Switzerland, 2025, pp. 301–320

  36. [44]

    Cost-efficient prompt engineering for unsupervised entity resolution in the product matching domain,

    N. Nananukul, K. Sisaengsuwanchai, and M. Kejriwal, “Cost-efficient prompt engineering for unsupervised entity resolution in the product matching domain,”Discover Artificial Intelligence, vol. 4, no. 1, p. 56, 2024. 13

  37. [45]

    Web-scale data integration: You can afford to pay as you go,

    J. Madhavan, S. Cohen, X. L. Dong, A. Y . Halevy, S. R. Jeffery, D. Ko, and C. Yu, “Web-scale data integration: You can afford to pay as you go,” inCIDR, 2007, pp. 342–350

  38. [46]

    Progressive duplicate detection,

    T. Papenbrock, A. Heise, and F. Naumann, “Progressive duplicate detection,”IEEE TKDE, vol. 27, no. 5, pp. 1316–1329, 2015

  39. [47]

    Entity resolution on-demand,

    G. Simonini, L. Zecchini, S. Bergamaschi, and F. Naumann, “Entity resolution on-demand,”PVLDB, vol. 15, no. 7, pp. 1506–1518, 2022

  40. [48]

    Interactive deduplication using active learning,

    S. Sarawagi and A. Bhamidipaty, “Interactive deduplication using active learning,” inProceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23-26, 2002, Edmonton, Alberta, Canada. ACM, 2002, pp. 269–278

  41. [49]

    The battleship approach to the low resource entity matching problem,

    B. Genossar, A. Gal, and R. Shraga, “The battleship approach to the low resource entity matching problem,”Proc. ACM Manag. Data, vol. 1, no. 4, pp. 224:1–224:25, 2023

  42. [50]

    Can foundation models wrangle your data?

    A. Narayan, I. Chami, L. J. Orr, and C. R ´e, “Can foundation models wrangle your data?”PVLDB, vol. 16, no. 4, pp. 738–746, 2022

  43. [51]

    Entity matching using large language models,

    R. Peeters, A. Steiner, and C. Bizer, “Entity matching using large language models,” inEDBT, 2025, pp. 529–541

  44. [52]

    In-context clustering-based entity resolution with large language models: A design space exploration,

    J. Fu, H. Tang, A. Khan, S. Mehrotra, X. Ke, and Y . Gao, “In-context clustering-based entity resolution with large language models: A design space exploration,”PACMMOD, vol. 3, no. 4, Sep. 2025. 14

Pith tools

Reviewed June 25, 2026 · model on record in the stance chip above.