The reviewed record of science sign in
Pith

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

Entity Resolution via Batched Oracle Queries

Lorenzo Balzotti , Donatella Firmani , Luca Gagliardelli , Giovanni Simonini This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-25 21:54 UTCgrok-4.3pith:L533QI6Qrecord.jsonopen to challenge →

classification cs.DB cs.AI
keywords entity resolutionbatched queriesoracle queriesNP-hardnessbatch selectiondata integrationrecall optimization
0
0 comments X

The pith

Batched entity resolution casts oracle query selection as an NP-hard problem with an optimal solution when entity sizes satisfy a natural condition.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

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

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.

Figures

Figures reproduced from arXiv: 2606.24407 by Donatella Firmani, Giovanni Simonini, Lorenzo Balzotti, Luca Gagliardelli.

Figure 1
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. 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… view at source ↗
Figure 3
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 ↗
Figure 4
Figure 4. Figure 4: Progressive recall on real and synthetic datasets with [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
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 sizes are directly comparable up to 2ϕb. (e.g., [18]–[21]). In this work, we therefore abstract away from oracle errors to focus on the algorit… view at source ↗
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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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.

pith-pipeline@v0.9.1-grok · 5659 in / 1187 out tokens · 26040 ms · 2026-06-25T21:54:34.105801+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 5 canonical work pages · 2 internal anchors

  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

    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

    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

    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

    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

    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

    2019

  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

    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

    2020

  9. [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

    2019

  10. [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

    2016

  11. [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

    1969

  12. [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

    2019

  13. [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

    2025

  14. [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

    2012

  15. [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

    2015

  16. [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

    2017

  17. [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 instructions with human feedback,”arXiv preprint arXiv:2203.02155, 2022

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  18. [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

    1922

  19. [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

    2018

  20. [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

    2015

  21. [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

    2017

  22. [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

    1961

  23. [23]

    Multi-way number partitioning

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

    2009

  24. [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

    2001

  25. [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

    2012

  26. [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

    2023

  27. [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

    work page arXiv 2004

  28. [28]

    Using chatgpt for entity matching,

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

    2023

  29. [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

    2023

  30. [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

    2012

  31. [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

    2016

  32. [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

    2024

  33. [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

    2021

  34. [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

    work page arXiv 2021

  35. [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

    work page arXiv 2023

  36. [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

    2020

  37. [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

    2008

  38. [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

    2019

  39. [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

    2007

  40. [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

    2009

  41. [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

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  42. [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

    2024

  43. [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

    2025

  44. [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

    2024

  45. [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

    2007

  46. [46]

    Progressive duplicate detection,

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

    2015

  47. [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

    2022

  48. [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

    2002

  49. [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

    2023

  50. [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

    2022

  51. [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

    2025

  52. [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

    2025