Entity Resolution via Batched Oracle Queries Lorenzo Balzotti∗ , Donatella Firmani∗ , Luca Gagliardelli† , Giovanni Simonini‡ ∗ Sapienza University of Rome, Rome, Italy
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 stateof-the-art baselines. Index Terms—Entity resolution, oracle queries, progressive resolution, batched clustering.
(a)
WD V Fun Cam C8oter din Cor er 0 s g a a
arXiv:2606.24407v1 [cs.DB] 23 Jun 2026
Emails: {lorenzo.balzotti, donatella.firmani}@uniroma1.it ORCID: 0000-0001-6191-9801, 0000-0003-0358-3208 † Università eCampus, Italy Email: [email protected]; ORCID: 0000-0001-5977-1078 ‡ University of Modena and Reggio Emilia, Modena, Italy Email: [email protected]; ORCID: 0000-0002-3466-509X
1.00 1.00 1.00 1.00 1.00
2
F-score (gpt-5-mini) 0.97 1.00 0.96 1.00 1.00
0.95 1.00 0.98 1.00 1.00
0.85 0.79 0.95 0.99 1.00
0.84 0.80 0.95 0.98 0.50
5
10 20 Batch Size
50
(b)
Token Saving Factor 12x 8x 4x 0x
2
5 10 Batch Size
20
(c)
Fig. 1: (a) Entity Resolution workflow with an oracle: pERbacco selects b records and passes that batch as a single invocation of the oracle. (b) F-score of an LLM (GPT-5 mini) employed as a matching oracle, as a function of the batch size. (c) Average token savings computed across all datasets w.r.t. the pairwise case.
I. BATCHED E NTITY R ESOLUTION Entity Resolution (ER) is the task of identifying records that refer to the same real-world entity (in other words: that match). It is central to data integration and knowledge base construction, and a core challenge in large-scale data management. State-of-the-art ER systems [1]–[3] rely on a common abstraction: a binary matching function that takes two records as input and returns a match or non-match decision. This pairwise abstraction underlies classical rule-based approaches, supervised learning methods [4], [5], and recent neural models [2]. As a result, ER pipelines are typically organized around pairwise comparisons, whose number grows quadratically with the dataset size. For large collections, controlling this cost is therefore a primary concern, motivating extensive work on blocking [4], [6], and prioritization techniques [3], [7]–[10] to reduce the number of comparisons. While pairwise matching has been the dominant abstraction for over half a century [11], many modern approaches [12]– [15] operate at a higher level of granularity by jointly analyzing a batch of items to produce a clustering. In such models, the cost of processing a batch typically scales with the batch size b, while asingle clustering result can resolve the match status of all 2b record pairs induced by the batch. For instance, Set Transformer architectures [12] can be used to learn permutation-invariant embeddings of the elements in a batch, followed by a clustering head that assigns (entity) group memberships based on joint reasoning over a set of records.
Similarly, vision-based face and identity clustering systems process bounded collections of images (e.g., photo albums) and directly group them into entity clusters without decomposing the task into independent pairwise decisions [15]. In human-in-the-loop settings, crowdsourcing-based ER approaches often present workers with small groups of records and ask them to cluster the records directly, implicitly leveraging transitivity and global context [14], [16]. Also Large Language Models (LLMs) [17] provide a further example of this paradigm: an LLM can be prompted with a batch of records and asked to jointly analyze them, performing ER by returning a clustering of the input [13]. In Figure 1b, we randomly sampled 100 batches of close records in a similarity graph (see Section III-A for a formal definition) and computed the F-score obtained using OpenAI GPT-5 mini, with ten positive and ten negative record pairs as few-shot examples in the prompt. We observe that the F-score is equal or very close to 1 for batch sizes up to 10, while in some datasets it degrades for larger batch sizes. These models act as oracles operating under inherent con-
1
straints: LLMs face context window limits and per-token costs; crowdsourcing systems must present workers with manageable tasks; neural models process fixed-size batches. In all cases, budget constraints (monetary, computational, or human) make it infeasible to exhaustively query the entire dataset in a single step. This naturally aligns with the pay-as-you-go paradigm [7]: progressively improve resolution quality while maintaining control over costs. In Figure 1c we estimate the average token savings computed across all datasets with respect to the pairwise case. In particular, we consider the same prompt that yields the results of Figure 1b, and a number of queries equal to the minimum required to find all matches (see Section II-C). The main challenge in this setting becomes to determine how to allocate the available budget so as to maximize the benefit (e.g., recall) obtained at each step. Unlike pairwise ER where the search space is well-understood [3], batched ER involves exponentially many possible batch selections, and the benefit of querying a batch depends on all previous queries. To study this problem in a model-agnostic manner, we abstract the resolution mechanism as an oracle that, given a bounded-size set (a batch) of records, returns a partition of that set into clusters corresponding to real-world entities. At any point during the resolution process, the task is therefore to decide which batch of records should be queried next so as to maximize the number of matches discovered for the budget spent so far. We refer to this task as progressive batched entity resolution and assume a consistent oracle that returns only correct match decisions. An overview of our proposed approach pERbacco is reported in Figure 1a. We note that this abstraction deliberately idealizes the behavior of the oracle. Handling noisy or inconsistent oracle outputs (e.g., errors arising from human annotation or imperfect models) is an important and challenging problem in its own right, and has been studied extensively in the context of crowdsourced ER [18]–[21]. In this work, we focus on the algorithmic problem of allocating oracle queries under budget constraints, and leave robustness to oracle errors to future work. Contributions. By moving beyond the strictly pairwise paradigm, this work makes the following contributions: • A formal definition of the progressive batched entity resolution problem, where an oracle jointly resolves batches of records and the objective is to progressively maximize resolution quality under a limited budget of oracle calls. • A proof that an optimal sequence of batches does not always exist, and that selecting the next batch by maximizing the estimated gain is NP-hard, establishing the intrinsic computational difficulty of allocating oracle queries at the dataset level. This result generalizes the known findings for pairwise ER. • An approximate solution that guides batch selection to maximize the benefit (number of newly discovered matches) obtained at each oracle invocation. • An experimental evaluation on real-world and synthetic datasets, showing the effectiveness of the proposed approach
and its superiority over state-of-the-art baselines under comparable budgets. Paper organization. Section II presents formal problem definitions and theoretical results including NP-hardness proofs and query bounds. Section III describes our pERbacco algorithm. Section IV presents experimental evaluation. Section V discusses related work, and Section VI concludes. II. P RELIMINARIES AND THEORETICAL RESULTS This section formalizes batched ER and its progressive version, shows that optimal progressive schedules may not exist, and relates the problem to two NP-hard selection tasks. The lower bound on the number of queries is used in Section IV as a stopping reference, while the sufficient condition in Subsection II-E motivates the suboptimal baseline used in the experiments. A. Problem Definition The input is a dataset R in which different records may represent the same entity. If two records r, r′ represent the same entity, we say that r matches r′ . Let us denote by ∼ the match relation. Accordingly, for r, r′ ∈ R, we write r ∼ r′ if and only if r matches r′ . Note that ∼ is reflexive, symmetric, and transitive, thus it is an equivalence relation. Let us denote by ̸∼ the non-match relation, which denotes two records that do not match each other. Observe that ̸∼ is not a relation of equivalence, as it is not reflexive. A match edge is a matching pair in the complete graph over R; this terminology is independent of the similarity graph introduced later. b We assume access to an oracle Oracle : Rb → {0, 1}(2) , which, given a batch B ⊆ R of b ≥ 2 records, returns a match/non-match decision for every unordered pair of records in B. In other words, a single oracle query over a batch provides complete pairwise matching information within that batch. Let Q = (q1 , q2 , . . . , qT ) be a sequence of batch queries. We denote by ∼Q the equivalence relation induced by the match information obtained from the queries in Q; that is, for r, r′ ∈ R, we write r ∼Q r′ if the Oracle answers to the queries in Q allow us to infer that r matches r′ . Let ReprQ = R/ ∼Q be the quotient set of the record set R by ∼Q , and let [r]∼ denote the equivalence class of r. If, based on the answers to the queries in Q, we can infer that two representatives r, r′ ∈ ReprQ do not match, we write r ̸∼Q r′ (and r′ ̸∼Q r). Note that ̸∼Q is not an equivalence relation. Moreover, two relations ∼1 and ∼2 are considered equivalent if they coincide on all pairs, and we write ∼1 =∼2 . To better illustrate this notation, let us show two opposite examples. If Q = ∅, then [r]∼Q = {r} for each record r, and there do not exist two records r, r′ such that r ̸∼Q r′ . Conversely, if Q contains all pairs in R2 , then ∼Q =∼, and r′ ∈ [r]∼Q if and only if r′ ∼ r. We are now ready to formalize the entity resolution problem via batch queries. Given an integer b, we define a b-batch as a batch containing at most b records.
2
Problem 1 (Batched Entity Resolution). Given a set of records R, an oracle accessing ∼, an integer b, find a minimal sequence Q of b-batches such that ∼Q =∼ and ̸∼Q ≠∼.
C. Minimum Number of Queries In this subsection, we focus on upper and lower bounds on the minimum number of queries required to discover all match edges in Problem 1. Indeed, in a progressive approach, only the optimization of match edges is considered, not that of non-match edges. It can be proven by the same reduction that finding this number is an NP-hard problem. These bounds are theoretically significant, and our experiments in Section IV show that they provide estimates on real datasets with an error below 3% (see Table III). We remark that the upper bound requires the solution of an instance of the bin packing problem, while the lower bound can be computed in O(|R|) time. Therefore, the lower bound is not only efficient to compute but also a tight approximation of the true value. First, we determine the minimum number of b-batches required to discover all matches for a single entity. Consider an entity e = {r1 , . . . , r8 } of 8 records, and let us assume that b = 3. To find all matches in e, four 3-batches are required. Indeed, we can start by querying the Oracle with the 3-batches {r1 , r2 , r3 } and {r4 , r5 , r6 }. After this, we have only two records not already visited, r7 and r8 , but at least one record from the first 3-batch must be compared with one from the second 3-batch. Thus, the following batch can be {r1 , r4 , r7 }. After this, the standard ER equivalence closure tells us that all records r1 , . . . , r7 match each other. Finally, we need a last 3-batch containing a record among r1 , . . . , r7 and r8 . No solution uses fewer than three 3-batches full and one with only two records. We want to generalize the example. We need some definitions.
Given a sequence of batches Q = (q1 , q2 , . . . , qT ), we define MatchQ as the number of match edges discovered by Q. Moreover, for t ≤ T , we denote by Qt the subsequence (q1 , q2 , . . . , qt ). Definition 1. Let R be a set of records, b an integer, Q a sequence of T b-batches. We say that Q is a b-optimal for R if for any sequence Q′ of b-batches, MatchQt ≥ MatchQ′t , for all t ≤ T , • MatchQ equals the number of match edges in R. •
Theorem II.1. A b-optimal solution for R does not always exist for every integer b and set of records R. Proof. Let b = 5 and R consist of the following 7 entities: {a1 , a2 , a3 }, {b1 , b2 , b3 }, {c1 , c2 , c3 }, {d1 , d2 }, {e1 , e2 }, {f1 , f2 }, {g1 , g2 }. Let Q be the sequence of batches consisting in Q1 = {a1 , a2 , a3 , d1 , d2 }, Q2 = {b1 , b2 , b3 , e1 , e2 }, Q3 = {c1 , c2 , c3 , f1 , f2 }, and Q4 = {g1 , g2 }, and Q′ consisting in Q′1 = {a1 , a2 , a3 , b1 , b2 }, Q′2 = {b1 , b3 , c1 , c2 , c3 }, Q′3 = {d1 , d2 , e1 , e2 }, Q′4 = {f1 , f2 , g1 , g2 }. It holds that MatchQ1 = MatchQ′1 = 4, MatchQ2 = 8 < 9 = MatchQ′2 , MatchQ3 = 12 > 11 = MatchQ′3 , and MatchQ4 = MatchQ′4 = 13. Since the number of match edges is 13, and there does not exist Q′′ satisfying MatchQ′′1 ≥ 4, MatchQ′′2 ≥ 9, and MatchQ′′3 ≥ 12, then the thesis holds. Since a b-optimal solution cannot always be guaranteed, we aim to maximize the increase in match edges at each query in a progressive manner.
Definition 2. Let x and b be two positive integers. We define the recursive rest of x modulo b as ( x, if x < b, rec rb (x) = rec ′ rb (n + x ), if x = nb + x′ , for x′ < b, n ≥ 1. (1) We define the recursive quotient of x modulo b as ( 0, if x < b, rec qb (x) = n + qbrec (n + x′ ), if x = nb + x′ , for x′ < b, n ≥ 1. (2)
Problem 2 (Progressive Batched Entity Resolution). Given a set of records R, an integer b, and a sequence of queries Q, find a b-batch q that maximizes MatchQ◦q , where Q◦q denotes the sequence Q extended by q. B. Batched Entity Resolution is NP-hard To prove that Problem 1 is NP-hard, we first introduce the bin packing problem (also known as the one-dimensional cutting stock problem), which is a classical NP-hard problem [22]. The bin packing problem can be stated as follows.
We observe that rbrec (x) = 0 if and only if x = 0, for any integer b. Let us apply Definition 2 to the previous example. We have b = 3 and x = 8, where x denotes the cardinality of the entity e. We have rbrec (x) = r3rec (8) = 2 and qbrec (x) = q3rec (8) = 3. To find all matches in e we needed exactly three batches completely full of records in e and one batch with exactly two records in e. So, before finding all matches in e, we first reduced it to a set of only 2 records. We want to formalize this concept. Let E denote the set of entities in R, i.e., the set of distinct real-world entities in R. By our notation E = R/ ∼. Additionally, for an entity e ∈ E let |e| indicate its cardinality, i.e., |e| = |{r ∈ R | r ∼ e}|. We can now formally define the representatives of an entity.
Problem 3 (Bin packing problem). Given a set I of items, a size s(i) ∈ N for each i ∈ I, and a positive integer bin capacity b, find the minimum integer ℓ such that there exists a partition of I into disjoint sets I1 , . . . , Iℓ where the sum of the sizes of the items in each Ij is b or less. Problem 1 is NP-hard by reduction from the restricted binpacking variant in which all bins must be exactly full, i.e., k-way number partitioning [23]. Given such an instance, use the items as entities and the bin capacity as the batch size. Any minimal batch schedule that fully resolves these entities induces a valid exact bin packing, and vice versa.
3
i.e., Q extended by q. Moreover, let ∆Q q denote the number of match edges discovered by querying the Oracle with q, assuming the queries in Q have already been asked, formally, ∆Q q = MatchQ◦q − MatchQ . For a record r, let |r|Q denote the cardinality of [r]∼Q , i.e., the number of records known to match r after the queries in Q. It holds X 1{r∼r′ } |r|Q · |r′ |Q . ∆Q (4) q = q (r,r ′ )∈(2)
Definition 3. Let R be a set of records, e an entity in E, and Q a sequence of queries. We say that e is reduced to ℓ representatives by Q if there exist e1 , e2 , . . . , eℓ records in R such that, for every r ∼ e, there is a unique 1 ≤ i ≤ ℓ satisfying r ∼Q ei . The records e1 , e2 , . . . , eℓ are called representatives of e. We generalize the previous example in the following lemma. Lemma II.1. Let R be a set of records, e an entity in E, and b an integer. To reduce e to rbrec (|e|) representatives, at least qbrec (|e|) b-batches are required. Moreover, if exactly qbrec (|e|) b-batches are used, then each of these batches consists exclusively of representatives of e.
Definition 4. Let R be a set of records, Q a sequence of batches, and b an integer. For two distinct elements r, r′ in R/ ∼Q we define ( 0, if r ̸∼ r′ , b ′ gainQ (r, r ) = |r|Q · |r′ |Q · (1 + i· b 1·|e |2 ), if r, r′ ∈ ei . (2) 1 (5) Moreover, let GainbQ denote the complete graph on R/ ∼Q in which the edges’ weights are given by gainbQ .
Proof. We proceed by induction on |e|, the size of e. If |e| < b, then qbrec (|e|) = 0 and rbrec (|e|) = |e|, so the statement holds by taking each record in e as its own representative. Assume the statement is true for all |e| ≤ N − 1, and let us prove it for |e| = N . Let [e]∼ = {r1 , r2 , . . . , rN }, and let e′ be a dummy entity satisfying [e′ ]∼ = {r1 , r2 , . . . , rN −1 }. By induction, e′ can be reduced to rbrec (|e′ |) representatives using qbrec (|e′ |) bbatches. Now there are two cases: either rbrec (|e′ |) < b − 1, or rbrec (|e′ |) = b − 1. In the first case, it holds that rbrec (|e|) = rbrec (|e′ |) + 1. Thus, no additional b-batches are required: it suffices to keep the same representatives of e′ and consider rN as its own representative. Being qbrec (|e|) = qbrec (|e′ |), the claim is true in this case. In the second case, we have rbrec (|e|) = 1, and a b-batch containing rN together with all representatives of e′ is required. After this batch, e is reduced to a single representative. Since qbrec (|e|) = qbrec (|e′ |) + 1, the claim holds.
The importance of the coefficient (1 + i· b 1·|e |2 ) is neces(2) 1 sary to prioritize larger entities without affecting the number of new match edges discovered with a b-batch, as formalized in the following lemma. Lemma II.2. Let R be a set of records, Q a sequence of batches, and b an integer. Let q be a b-batch in R/ ∼Q , then X ∆Q gainbQ (r, r′ ) < ∆Q (6) q ≤ q +1 (r,r ′ )∈(q2) b 2 Proof. By Equation 4 it suffices to prove that ∆Q q < 2 ·|e1 | . b We have exactly 2 pairs in q, and each pair can discover at most |e1 |(|e21 |−1) < |e1 |2 match edges. The thesis follows.
Theorem II.2. Given a set of records R and an integer b, let Φb be the minimum number of b-batches required to discover all matches in R. Then 1 X rec Ω+ rb (|e|) ≤ Φb ≤ Ω + BP P (E1 ) (3) b
To proceed, we first introduce a classical graph problem, whose NP-hardness was established in [24]. Problem 4 (Heaviest Subgraph Problem (HSP)). Given an edge-weighted graph G and an integer k, find a subset S of k vertices of G such that the sum of the edges’ weight in G[S] is maximized.
e∈E1
where Ω = e∈E qbrec (|e|), E1 = {e ∈ E | rbrec (|e|) > 1}, and BP P (E1 ) is the solution of Problem 3 for E1 , in which the capacity is b, the items are the entities in E1 , and the size of each entity e is rbrec (|e|). P
Let us define HSP (G, k) as a solution for Problem 4 for graph G and integer k. In the following proposition, we describe the solution of Problem 2. Proposition 1. Let R be a set of records, Q a sequence of queries, and b an integer. Let q be a b-batch in R/ ∼Q that Q ′ is a solution of HSP for GainbQ . Then ∆Q q ≥ ∆q ′ for every q b-batch in R/ ∼Q .
Proof. By Lemma II.1, at least Ω b-batches are required to reduce every entity e to rbrec (|e|) representatives. The remaining representatives of the entities in E1 must still be P joined, which requires at least 1b e∈E1 rbrec (|e|) additional batches. Conversely, using BP P (E1 ) batches, the remaining representatives can be packed so that each entity is reduced to a single representative, proving the upper bound.
Proof. Let H be the graph in R/ ∼Q in which the weight of the edge between records r, r′ is |r|Q · |r′ |Q , for every r, r′ ∈ R/ ∼Q satisfying r ∼ r′ , and 0 otherwise. By Equation 4, the maximum ∆Q q is obtained by a solution q of HSP on H. By Lemma II.2, q is a solution of HSP for GainbQ if and only if q is a solution of HSP for H. The thesis follows.
D. Hardness of Batch Selection From now on, let E = (e1 , e2 , . . .) denote the sequence of entities ordered by cardinality, i.e., |e1 | ≥ |e2 | ≥ . . .. Given a sequence of batches Q = (q1 , q2 , . . . , qT ) and a batch q, we recall that Q ◦ q denotes the sequence (q1 , q2 , . . . , qT , q),
In practice ∼ is unknown, so any algorithm must select batches by maximizing an estimate of the gain (such as the
4
benefit introduced in Section III), which can form an arbitrary edge-weighted graph. The following theorem shows that this selection problem is NP-hard.
from the Oracle. A schematic overview of pERbacco is shown in Figure 2. Let us briefly analyze these steps one by one. There are several methods in the literature to compute a similarity graph G; we refer to Subsection III-A for further details. We emphasize that our approach does not rely on any specific method. In the second step, we partition the similarity graph G into heavy communities. All records that do not belong to any heavy community form the residual graph. A heavy community is a subgraph of G whose density is greater than a fixed threshold (see Subsection III-B). Since the weights of match edges in G are expected to be higher than those of non-match edges, a heavy community should mainly consist of match edges. We define the intra-recall as the ratio between the number of match edges that belong to at least one heavy community and the number of match edges in G. The desiderata for heavy communities are: • a high number of match edges within each heavy community, • a low number of match edges between different heavy communities, • an intra-recall close to the overall recall of G, • community sizes roughly comparable to b. By following the structure induced by these heavy communities, the discovery of match edges should be accelerated. The algorithm for this second step is explained in Subsection III-B, and experiments are in Subsection IV-C. In the last step, we decide whether it is more convenient to try to enlarge already visited entities or visit new records belonging to the same community. The main idea is that visiting new records should discover fewer match edges (see Table I and Subsection III-C3). So, if by trying to enlarge already visited entities we discover a few edges, then in the next query we visit new records of the current community. The decisions are driven by an evolving parameter called temperature, see Subsection III-C4. This temperature is linked to the concept of benefit, where the benefit, introduced in [10] and formally defined in Subsection III-C1, is a measure of the expected gain in match edges – and thus, gain in recall. Note that this last step is repeated for each query.
Theorem II.3. Let R be a set of records, Q a sequence of queries, and b an integer. Given a weight function ĝ on the pairs of R/P∼Q estimating gainbQ , finding a b-batch q that maximizes (r,r′ )∈(q) ĝ(r, r′ ) is NP-hard. 2
Proof. We reduce from Problem 4. Given an instance (G, k) of HSP with non-negative weights, we construct the instance in which R = V (G), Q = ∅, b = k, and ĝ = w. Since Q = ∅, every record is its own representative; thus the b-batches of R/ ∼Q coincide with the k-subsets of V (G), and a bbatch maximizing the total estimated gain is exactly a solution of HSP (G, k). The thesis follows from the NP-hardness of Problem 4 [24]. E. Sufficient Conditions for the Existence of Optimal Solution In this subsection, we show that, under certain conditions, an optimal solution exists and describe it. The proposed approach generalizes the method introduced in [10] for the pairwise case. Theorem II.4. Let R be a set of records, and b an integer. Let Q = (q1 , q2 , . . .) be a succession of b-batches defined as ( HSP (Gainb∅ , b) if t = 1, (7) qt = HSP (GainbQt−1 , b) if t > 1. If rbrec (|e|) = 1 for each entity e in R, then Q is b-optimal for R. Proof. By Lemma II.1, each entity e with rbrec (|e|) = 1 can be reduced to one representative using qbrec (|e|) batches containing only representatives of e. Thus, as in the pairwise case [10], the optimal order is to reduce entities in nonincreasing size because match edges grow quadratically with entity size. The coefficient in Equation 5 enforces this order without changing the number of newly discovered match edges, and Proposition 1 ensures that each selected batch maximizes the immediate gain among schedules with this order. We observe that when b = 2, rbrec (|e|) = 1 for every entity e, so an optimal solution for pairwise batches always exists by Theorem II.4. In addition, the optimal solution described in Theorem II.4 coincides with the one described in [10].
A. Similarity Graph A similarity graph is a weighted graph where the vertices are records in R, and an edge weight is an uncalibrated similarity score: higher weights indicate stronger evidence that two records match. The construction of similarity graphs has been extensively studied in the context of entity resolution and data integration. Classical approaches compute pairwise similarities by combining attribute-level similarity functions, such as string edit distances, token-based measures (e.g., Jaccard or TF–IDF), and numeric distance functions, often using manually defined rules or weighted combinations [25], [26]. More advanced methods adopt learning-based models, where similarity functions or matching scores are learned from data [27]–[29].
III. P ROPOSED APPROACH : P ER BACCO In this section, we present our approach for progressive Entity Resolution via batched queries and community detection (called pERbacco). It consists of three steps: computing a similarity graph G on R, partitioning G by recursively calling a Community Detection Algorithm (CDA), and adaptively deciding whether to enlarge already visited entities or visit new records belonging to the same community. The first two steps are static, while the third depends on the answers obtained
5
pop
Records
Similarity Graph
Community Detection
Community
Queue heavy comm.
update
update
Benefit
Enlarge visited entities
Yes
Temperature
No
Heavy community?
Oracle
Visit new records
update
Step I: Similarity Graph
Step II: Graph Partitioning
Step III: Creating Batches
Fig. 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 comparisons. 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 investigates blocking methods, which are commonly integrated into both traditional and learning-based ER pipelines [6], [30]–[33]. In this work, we assume that a similarity graph G on R is given, and let w : E(G) → [0, 1] be the edge-weight function; without loss of generality, we assume that the maximum weight is 1. Our approach is independent of the specific technique used to compute similarities, and can operate with any method that assigns edge weights reflecting matching evidence. a) The role of the similarity graph: The similarity graph serves as the starting point for both Problem 1 and Problem 2. Consequently, different similarity graphs yield different performance for our method and competing approaches. In our experiments, we use a uniform procedure to construct the similarity graph across all datasets, see [4]. The resulting graphs show standard characteristics, with recall above 0.9 and precision on the order of 0.03 or lower. Regarding the time required to compute the similarity graph, it ranges from a few seconds for small datasets to a few minutes for the largest ones. This computation represents only a small fraction of the overall procedure. Our method is robust to variations in the precision and recall of the similarity graph; as expected, higher-quality similarity graphs lead to improved performance.
Fig. 3: A similarity graph with match (solid green) and nonmatch (dotted orange) edges. Heavy and light communities are marked with solid blue and dotted gray, respectively. In Figure 3, there is a similarity graph G, where edge thickness denotes weights. A heavy community is highlighted in blue, and a light (i.e., not heavy) one in gray. Recursively, light communities are sent to the CDA to further split them until they become either heavy or indivisible. The records that do not belong to any heavy community form the residual graph. Note that in Figure 3 the only one heavy community contains a relevant part of the match edges. After the computation of the heavy communities, we order them by their weights (see Equation 8). We denote this order by C = (c1 , c2 , . . . , cr ). We will analyze the communities by following this order; the pseudocode is shown in Algorithm 1. In the whole paper and in all presented algorithms, ties are broken randomly. An empirical analysis on the CDAs, the heaviness threshold λw , and how to obtain the desiderata described at the beginning of this section are in Subsection IV-C. We define the weight of a community c as X w(c) = w(e), (8) e∈c
The main idea is that the higher w(c), the higher the number of expected match edges. Moreover we define the density ρ(c) of a community c as the classical edge-weighted density:
B. Graph Partitioning We need to balance the weight and the size of the communities. Indeed, splitting a community into two or more subcommunities may increase the average weight, but we might lose some edges that match. We find communities via a Community Detection Algorithm (CDA), and we say that a community is indivisible for CDA if the CDA cannot divide it into more subcommunities. Finally we define min size = max(b, 10), and we do not consider small communities, i.e., communities with less than min size records.
ρ(c) =
w(c) . |c|(|c| − 1)/2
(9)
C. Creating Batches This subsection details the adaptive batch-selection step. We score candidate representative pairs by benefit, use a greedy HSP routine to form high-benefit batches, and alternate between current-batches that can enlarge known entities
6
of match edges discovered if r matches r′ . a) Matching coefficient: Given two records r and r′ , there is no unique way to define µQ (r, r′ ), but higher values should indicate stronger matching evidence. We therefore use µQ (r, r′ ) only as an uncalibrated likelihood proxy. We define CrossQ (r, r′ ) = {(u, v) ∈ E(G) | u ∈ [r]∼Q and v ∈ [r′ ]∼Q }. Basically, CrossQ (r, r′ ) is composed by all edges in G having one endpoint in [r]∼Q and the other in [r′ ]∼Q , i.e., the edges that cross [r]∼Q and [r′ ]∼Q . In [10] (see Equation (2) with our notation), µQ (r, r′ ) is defined as the maximum edge weight in CrossQ (r, r′ ), that is
Algorithm 1: Communities (G, λw , CDA) Input: a graph G, a threshold λw , and a community detection algorithm CDA Output: a queue of heavy communities of G 1 light communities = [V (G)]; 2 heavy communities = []; 3 while light communities ̸= [] do 4 c = pop(light communities); 5 sub communities = CDA(c); 6 for each c′ ∈ sub communities do 7 if ρ(c′ ) ≥ λw then 8 add c′ to heavy communities; 9
10
′
′ µmax Q (r, r ) =
′
if ρ(c ) < λw and c is not indivisible for CDA then add c′ to light communities;
Discard from heavy communities all the communities having less than min size records; 12 Sort the communities in heavy communities w.r.t. w; 13 return heavy communities
(11)
′ Let us briefly explain Equation 12. Note that µmean Q (r, r ) ∈ ′ [0, 1], since there are at most |r|Q ·|r |Q edges in CrossQ (r, r′ ). A value close to 1 indicates that CrossQ (r, r′ ) contains many edges with high weights. Conversely, a value close to 0 means that either there are few edges, their weights are low, or both. In Section IV we show that the presented algorithms perform better using µmean than µmax Q Q in Equation P 10. Note that using mean µQ implies that benefitQ (r, r′ ) = e∈CrossQ (r,r′ ) w(e). 2) A greedy algorithm for the Heaviest Subgraph Problem: As we will explain in Subsection III-C3, at each step of our algorithm we need to select a subset of b records that maximizes the sum of benefit edges. This corresponds to solving an instance of Problem 4, which, as previously stated, is NP-hard. Therefore, we use a greedy approach for Problem 4. If b = 2, we simply select the two vertices of the edge with the maximum weight in G, which is the optimal solution. Otherwise, we start with S = {v}, where v is the vertex whose incident edges have P the maximum total weight. Formally, we define we (x) = e∈E(G),x∈e w(e), thus v = argmaxx∈V (G) we (x). Then, until |S| = b, we iteratively either add the vertex that maximizes the sum of the edge weights, or add the two vertices of the edge with maximum weight in the graph G \ G[S]. The pseudocode is reported in Algorithm 2. 3) Current-batches and community-batches: We now have all the necessary definitions to describe our approach in detail. As mentioned at the beginning of this section, at each step we decide whether it is more convenient to try to enlarge already visited entities or to explore new records within the same community. This decision is guided by introducing two subsets of the records: current and unqueried. At each step, only a subset of the records, called current, is considered. The subset current follows the sequence of heavy communities c1 , c2 , . . .: at the first query current is equal to c1 ; once all records in c1 have been queried at least once to the Oracle, current is equal to c1 ∪ c2 ; once all records in c2
and community-batches that introduce unqueried records. The temperature parameter controls this alternation. a) From theory to algorithm.: Proposition 1 shows that the ideal next batch is an HSP solution on the gain graph, but that graph depends on the unknown ground truth and HSP is NP-hard. The algorithm below is the observable counterpart of that characterization: it replaces the hidden gain graph with the benefit graph induced by similarity scores and previous oracle answers, uses GreedyHS as the HSP surrogate, and restricts exploration through heavy communities to focus the search on dense regions of the similarity graph. 1) Benefit: As we query the Oracle, the number of records that are representative of more than one record increases. So it may be helpful for the progressive recall to create batches composed by the representatives that are likely to match. We need a measure that expresses this. Given a sequence of queries Q and a pair of records r and r′ , we define the benefitQ (r, r′ ) as the potential gain in matches obtained by asking the Oracle whether r and r′ match, as done in [10]. We want benefitQ (r, r′ ) to be proportional to |r|Q · |r′ |Q , which corresponds to the number of match edges that would be discovered if r matches r′ . Moreover, benefitQ (r, r′ ) should increase with the evidence that r and r′ match. We capture this evidence through an uncalibrated matching coefficient µQ (r, r′ ). The formula for benefitQ (r, r′ ) follows: if r ̸∼Q r′ , otherwise. (10) If Q is clear from the context, then we omit it. Note that the term |r|Q · |r′ |Q in Equation 10 corresponds to the number benefitQ (r, r′ ) =
w(e).
We believe that the maximum is not representative enough of the aggregate matching evidence between r and r′ . So we introduce a mean version: P e∈CrossQ (r,r ′ ) w(e) mean ′ . (12) µQ (r, r ) = |r|Q · |r′ |Q
11
(
max
e∈CrossQ (r,r ′ )
0, µQ (r, r′ ) · |r|Q · |r′ |Q ,
7
ground truth of the dataset; and records may have already been queried. In contrast, community-batches are disjoint; all records belong to the same community; there exists an upper bound on the number of possible discovered match edges; and all records are unqueried.
Algorithm 2: GreedyHS(G, b) Input: an edge-weighted graph G and an integer b Output: a suboptimal solution to Problem 4 1 if b = 2 then 2 let e = (u, v) be the edge with the maximum weight; 3 return {u, v}
Type
u = argmaxx∈V (G) we (x); 5 v = argmaxy neighbor of u w((u, y)); 6 S = {u, v}; 7 while |S| < b and |S| < |V (G)| do 8 let (x, y) be the heaviest edge in G \ G[S]; 9 let z be the vertex in G that maximizes W = w(G[S ∪ {z}]); 10 if w(G[S]) + w((x, y)) > W and |S| ≤ b − 2 then 11 add x and y to S; 12 else 13 add z to S; 4
14
Disjoint Communities # Matches Queried/Unqueried
Current
No
Any
Unlimited
Both
Community
Yes
Same
≤ b(b−1) 2
Unqueried
TABLE I: Comparison community-batches.
between
current-batches
and
4) Setting the temperature: We now describe how to set the parameter t, which depends on the evolution of the benefit values. However, the benefit’s value depends on the input dataset we are examining. For instance, if the input dataset has many entities with a huge number of duplicated records, then it is possible to have high benefit values; conversely, if each entity of the input dataset has at most a few duplicates, then it is impossible to have high benefit values. In a nutshell, there is no single value of t that works for all input datasets. Therefore, we introduce two criteria to determine when the value of t is too high and when it is too low. Since we consider only two kinds of batches – currentbatches and community-batches – the only alternative to querying the Oracle with a current-batch is to query it with a community-batch. Thus, the criterion to determine when the value of t is too low is to check whether the match edges discovered through a current batch are greater than the average number of match edges discovered through previous community batches. To formalize this criterion, we introduce I be the number of match the following notation. Let Mcomm edges discovered after querying the Oracle with the first I I /I be the = Mcomm I community-batches, and let τcomm average of match edges discovered. If no confusion arises, then we omit the index I. Let M be the number of match edges discovered after querying the Oracle with a current batch. The criterion is: if M < τcomm , then t is too low; therefore we double it (see Algorithm 3 line 16). The criterion for determining when the value of t is too t high is to check whether Bcurrent contains at least b vertices. If not, we decrease the value of t by multiplying it by the factor (1 − 1b ) (see Algorithm 3 line 18). This ensures that we query the Oracle with a current-batch approximately every b queries. Through experiments, we observed that our algorithm’s performance improves when the frequency of current-batches is inversely proportional to b, which motivates the factor (1− 1b ). By having the previous two criteria for high and low values of t, the choice of the initial value of t is not relevant. By default, we choose t = b at the beginning of the algorithm. Our main algorithm pERbacco is reported in Algorithm 3, where query(S) means “query the Oracle with the records in S”.
return S
have been queried, then current is equal to c1 ∪ c2 ∪ c3 ; and so on. The set unqueried corresponds, at each step of the algorithm, to the subset of records in current that have not yet been queried to the Oracle. We now define two specific benefit graphs. Definition 5. Given a sequence of queries Q and a set of records V , we define the benefit graph on V , BV (Q), as the graph on V / ∼Q in which edge weights represent the benefit among records. Moreover, given a temperature t, we define BVt (Q) as the subgraph of BV (Q) induced by all edges whose weight is higher than t. In Definition 5, if Q is clear from the context, we omit it. At each step, we aim to maximize the sum of benefits by considering either all records in current or only the subset unqueried. Considering current corresponds to try to enlarge already t visited entities, which is done by GreedyHS(Bcurrent , b), where the parameter t is fixed in the next subsection. Considering unqueried corresponds to visiting new records within the same community, which is done by GreedyHS(Bunqueried , b). For convenience, we refer to a batch composed of records in current as a current-batch, and a batch composed of records in unqueried as a community-batch. In the next subsection, we explain how to set the temperature t, which determines whether it is more advantageous to proceed with a currentbatch or a community-batch. A summary of the differences between current-batches and community-batches is reported in Table I. In particular, current-batches are not disjoint, meaning that the same record may appear in multiple current-batches; records may belong to different communities; the number of discovered match edges is unbounded, as it depends solely on the (a priori unknown)
8
graph. This choice reflects a concrete instantiation of the similarity graph abstraction introduced in Subsection III-A and does not affect the generality of the proposed approach. We report progressive recall, i.e., the fraction of groundtruth match edges discovered after each query budget. Under our consistent-oracle assumption, every discovered positive match is correct, so the precision of discovered matches is 1 and the corresponding F1-score is 2 · recall/(1 + recall), a monotone transformation of recall. If the oracle is noisy, precision and F1 become essential metrics; modeling that setting is orthogonal to the batch-scheduling problem studied here. Regarding the running time, the blocking and CDAs require from a few seconds on small datasets to about ten minutes on the largest ones. The algorithm pERbacco and its competitors (see Section IV-A) require at most a few seconds per query when using the ground truth as the Oracle. When using an LLM (in our case, GPT-5 mini), the time required to compute Figure 5 on Cora dataset ranges from 2 seconds for b = 2 to 20 seconds for b = 20. Consequently, since blocking and CDAs are executed only once, the main bottleneck is determined by querying the Oracle for each query. In addition to execution time, the monetary cost of using an LLM must also be considered. For this reason, it is important to study entity resolution in a progressive manner, showing that, at the same level of recall, our approach requires fewer calls to the Oracle.
Algorithm 3: pERbacco Input: a set of records R and an integer b Output: a sequence of b-batches of R 1 Compute a similarity graph G on R; 2 Compute set C of heavy communities in G by Algorithm 1; 3 t = b; 4 current = ∅; 5 for c ∈ C do 6 current = current ∪ c; 7 unqueried = c; 8 while |unqueried| ≥ b do 9 community batch = GreedyHS(Bunqueried , b); 10 query(community batch); 11 unqueried = unqueried \ community batch; t 12 while |V (Bcurrent )| ≥ b do t 13 current batch = GreedyHS(Bcurrent , b); 14 query(current batch), and let M be the number of match edges discovered; 15 unqueried = unqueried \ current batch; 16 if M < τcomm then 17 t = 2t; 18 t = 1 − 1b · t; current = V (G); while there are non-inferable edges do t , b); 21 current batch = GreedyHS(Bcurrent 22 query(current batch);
19 20
A. Competing Algorithms Firmani et al. [10] presented two algorithms for the progressive entity resolution with pairwise adaptive query. The two algorithms are called sedge and shybrid ; we do not deeply explain these algorithms, and we refer to [10] for further details. In a nutshell, sedge queries the Oracle each time with the edge having the highest benefit, and shybrid queries the Oracle with the edges adjacent to the vertex with the highest total benefit (i.e., the vertex whose sum of benefits of adjacent edge is maximized), until a match edge is discovered or a prefixed number of edges have been queried. We merge both algorithms in Algorithm 4: when b = 2, we obtain exactly sedge because of the case b = 2 in Line 1 of Algorithm 2; when b > 2, we adapt shybrid to the batch-queries case by using the GreedyHS algorithm. In our experiments, we denote by pERbac (resp., Oracle) the results of Algorithm 4 when the benefits are computed using µmean (resp., µmax ). Note that pERbac coincides with pERbacco when there are no heavy communities. Moreover, in [10] (titled Online Entity Resolution Using an Oracle), the benefits are computed with µmax . These observations motivate the naming of the algorithms.
IV. E XPERIMENTAL E VALUATION In this section, we discuss the results of our experimental evaluation. We compare all algorithms on publicly available datasets and synthetic ones. The datasets used in our experiments are described in Subsection IV-B. To the best of our knowledge, there are no known algorithms for progressive entity resolution via adaptive batch query; so we extend the algorithms in [10] from the pairwise query case to the batch query case, see Subsection IV-A. We omit several non-adaptive competitor algorithms, such as the ones in [1], [3], [14], since their performance is strictly lower than that of competing algorithms described in Subsection IV-A. Indeed, adapting the queries to the Oracle based on previous answers provides a significant advantage in terms of progressive recall. All algorithms are implemented in Python, in a common framework1 , where ties are broken randomly. We ran experiments on a machine with an AMD Ryzen 9 5950X CPU, 64 GB RAM, and an NVIDIA RTX 3090 GPU under Ubuntu 22.04. In our experimental evaluation, the similarity graph is built using standard-blocking and meta-blocking in the JedAI library [4]. For each dataset, we tune the meta-blocking parameters to achieve a recall above 0.9, ensuring that the majority of true match edges were preserved in the resulting
B. Datasets and Query Complexity We evaluate pERbacco and competing algorithms on five real datasets, spanning domains such as product, business, and citation, and on synthetic datasets. The Cora dataset consists of 1,295 bibliographic records of machine-learning
1 https://github.com/Stravanni/pERbacco
9
Dataset
Algorithm 4: batched ER without communities Input: a set of records R and an integer b Output: a sequence of b-batches of R 1 Compute a similarity graph G on R; 2 while there are non-inferable edges do 3 query(GreedyHS(BV (G) , b));
Cora Camera Funding WDC-80 Voters Synth10k
Entity Sizes Mean Med. Max 17184 93 (112) 13.7 7 64 541411 2087 (9005) 9.9 4 256 135122 2351 (3113) 6.5 4 115 8971 1000 (1000) 3.5 2 11 9819 5657 (6692) 2.3 2 8 915128 3890 (10000) 8.5 3 257
Records Matches 1295 29787 16258 3841 14183 39161
Entities
TABLE II: Dataset statistics. The Entities column reports the number of entities with size at least 2, with the total number of entities shown in parentheses. The Entity Sizes column excludes entities of size 1.
publications [10]. Camera contains 29.8k specifications of real-world cameras collected from 24 e-commerce websites, originally used in the ACM SIGMOD 2020 programming contest [34]. Funding2 includes 16.3k records on financing requests submitted to the NYC Council Discretionary Funding. The Web Data Commons Products dataset [35]3 contains product offers extracted from 3,259 web shops in 2020 via schema.org annotations; we use the WDC-80 variant, comprising 3,841 offers that describe 1,000 unique real-world products. Finally, the Voters4 dataset contains demographic information on 14.2k registered voters from North Carolina, grouped by sex and race [36]. We selected these datasets because they exhibit different entity size distributions (see Table II that summarizes key statistics for each dataset). Moreover, we did not consider one-to-one datasets, as they are not suitable for studying entity resolution in a progressive manner via batch queries. The synthetic datasets are randomly generated according to a specific distribution of weights and edges. The distribution of entity sizes follows the entity size distribution observed in the Camera dataset, which exhibits power-law behavior; to avoid excessively large entities, we impose a maximum size of 300. We generate a dataset, Synth10k, consisting of approximately 39k records and exactly 10k entities. The recall is fixed at 0.95, while we create three variants with precision values of 0.5, 0.2, and 0.05, respectively. The missing match edges and the non-match edges are generated randomly. To model edge weights, we analyzed the similarity graphs of the real datasets (Subsection III-A): non-match weights consistently follow a power-law distribution, whereas match weight distributions vary substantially across datasets, so we generate the latter using a uniform distribution. Table III reports the lower and upper bounds of Φ10 , as defined in Equation 3, denoted by ϕ10 and Φ10 , respectively. The upper bound Φ10 is computed using the Python library binpacking5 , which successfully finds the exact solution for all instances of Problem 3 considered in our experiments. We observe that the lower and upper bounds differ by at most 3%, indicating that the lower bound provides a tight approximation of Φ10 .
Bound Cora Camera Funding WDC-80 Voters Synth10k ϕ10 137 2436 1612 391 1315 3514 Φ10 137 2455 1640 396 1354 3544 error 0% 0.7% 1.7% 1.2% 2.9% 0.8%
TABLE III: Upper and lower bound of Φ10 for all datasets.
C. A Priori Selection of CDAs We tested four edge-weighted CDAs: Louvain [37], Leiden [38], Asynchronous Label Propagation [39], and Infomap [40]; see [41] for a survey. The only parameter we expose in the main text is the heaviness threshold λw . Empirically, Louvain and Leiden most often yield the highest record ratio, and low λw values help dense datasets because they preserve more candidate matches inside heavy communities. On sparse datasets, the same choice can add many non-match edges, so pERbac, which does not use communities, may be preferable. Table IV illustrates this behavior on one dense dataset (Funding) and one sparse dataset (Voters), using b = 10. The table is not used to tune per-dataset parameters in the main comparison: unless stated otherwise, we use Louvain with λw = 0.05. Dataset
Funding
Voters
λw
CDA
0.05
Louvain Leiden
0.98 0.71
0.884 0.856
0.15
Louvain Leiden
0.83 0.28
0.843 0.797
//
w/o CDA
//
0.817
0.05
Louvain Leiden
0.80 0.10
0.232 0.280
0.15
Louvain Leiden
0.08 0.01
0.289 0.284
//
w/o CDA
//
0.284
record ratio recall
TABLE IV: Performance of pERbacco for b = 10, on different datasets, CDAs and values of λw . When no CDA 2 https://raw.githubusercontent.com/qcri/data civilizer system/master/grecord is used, then pERbacco reduces to pERbac. Bold indicates service/gr/data/address/address.csv the best combination of CDA and λ for each dataset, and 3 https://webdatacommons.org/largescaleproductcorpus/wdcunderlined results are close to the best. The recall is computed products/index.html#toc5 4 https://hpi.de/naumann/projects/repeatability/datasets/ncvotersafter ϕ10 queries. dataset.html 5 https://pypi.org/project/binpacking/
10
decreases to 0.05 – which is more realistic at a recall of 0.95 – pERbacco significantly outperforms pERbac. It is worth noting that there is a huge difference between all algorithms in Camera and Synth10k with precision 0.05, although the distributions of communities, edges, and weights are similar. This is due to the randomness of non-match edges in Synth10k. In contrast, in the real dataset Camera, the similarity graph is obtained via distances between records, thus similar records that do not represent the same entity are likely to share a heavy edge. This makes it more difficult to discover heavy communities composed mainly by match edges. Figure 5 reports an illustrative LLM run on Cora with GPT5 mini, few-shot prompting, and b ∈ {2, 5, 10, 20}, using the normalized query budget up to 2ϕb . pERbacco is largely insensitive to b, while Oracle improves as b increases; the plateau after ϕb is due to LLM errors. Handling such errors and optimizing prompt-level cost-quality tradeoffs [42]–[44] are complementary to our focus on budget-aware batch selection.
D. Suboptimal Solution As stated in Theorem II.1, a b-optimal solution does not exist in the general case, and selecting the batch that maximizes the estimated gain is NP-hard (Theorem II.3). Nevertheless, Theorem II.4 characterizes a b-optimal solution for some special cases, and Proposition 1 shows that this solution maximizes the number of match edges at each query. Its implementation requires solving an instance of the NPhard Heaviest Subgraph Problem for each query; we therefore call suboptimal solution the algorithm of Theorem II.4 where HSP is replaced by GreedyHS1000 , where GreedyHS1000 (G, b) denotes GreedyHS(G1000 , b), and G1000 is the subgraph of G induced by its 1000 heaviest edges. If b = 2, a 2-optimal solution exists, as discussed in Subsection II-E. For other values of b, we do not have any theoretical guarantee about the performance of the suboptimal solution. Nevertheless, in all our experiments the suboptimal solution achieves a recall of at least 0.98 after ϕb queries on every tested dataset.
V. R ELATED WORK
E. Evaluation
Pay-as-you-go data integration. The pay-as-you-go (a.k.a. progressive) approach to data integration was introduced to address scenarios in which integrating all data upfront is infeasible or impractical [45]. In this line of research, progressive methods for entity resolution (ER) prioritize candidate record pairs according to their estimated likelihood of being true matches, to discover as many matches as early as possible [3], [7], [9], [46], [47]. Active-learning ER is related because it scores candidate pairs, but its goal is to minimize labeled pairs for training a supervised matcher rather than to schedule oracle calls for progressive resolution quality [3], [48], [49]. To the best of our knowledge, we propose the first study of a pay-as-you-go ER setting in which progress is achieved by querying an oracle over bounded-size sets of records, rather than individual pairs. ER using an oracle. In the crowdsourcing literature, several works have explored ER abstractions that go beyond purely pairwise queries [14], [16]. These approaches are motivated by human-in-the-loop settings, where an oracle (the crowd) is queried to determine match relationships among small groups of records. However, their setting is substantially different from ours. The hybrid approach in [16] relies on both pairwise and batch queries. Pairwise comparisons are considered more reliable and are used to resolve pairs with discordant answers across different batch queries. The method in [14] processes all the batches in parallel. As a result, answers obtained from earlier queries cannot be exploited to guide subsequent batch selection, preventing a truly progressive, pay-as-you-go resolution process. Moreover, this approach does not study how to adaptively select batches under a budget, nor does it provide a formal, model-independent oracle abstraction. Similarly, we do not consider noisy or inconsistent oracle answers in this work. Handling errors arising from imperfect models or human annotation is a challenging problem in its own right and has been studied extensively in the context of crowdsourced ER, where the oracle abstraction is comparable
We compare our approach pERbacco with the competing algorithms pERbac and Oracle described in Subsection IV-A, and with the suboptimal solution discussed in Subsection IV-D, denoted by SubOpt. In Figure 4, we compare the algorithms on datasets listed in Table II with b equal to 10. For algorithm pERbacco, as discussed in Subsection IV-C, we use the Louvain method as CDA, and λw = 0.05. All algorithms are implemented with GreedyHS1000 in place of GreedyHS to further speed up the computation. First, note that pERbac outperforms Oracle on all datasets at each query, even though pERbac is obtained from Oracle with a small improvement (i.e., µmean instead of µmax in Equation 10). On the Funding and WDC-80 datasets, pERbacco outperforms both competitors at every query. On Cora, the algorithms perform similarly during the initial queries, after which pERbacco achieves higher recall. Note that, on Cora, all algorithms stop before 3ϕ10 queries, as they resolve all edges in the similarity graph. On Camera, pERbacco exhibits a slow start. Upon inspection, we observed that the initial heavy communities contain few match edges, despite having many heavy edges, which explains the slow initial behavior. As noted in Subsections III-B and IV-C, the construction of heavy communities is based on a heuristic approach. Nevertheless, after ϕ10 queries, the recall values achieved by pERbacco are higher than those of the competing algorithms. On Voters, algorithm pERbacco performs worse than pERbac because the dataset is sparse. We point out that this behavior could be predicted a priori based on the analysis reported in Subsection IV-C. On the synthetic dataset Synth10k, we observe that both pERbac and pERbacco are close to the suboptimal solution when the precision is 0.5 or 0.2. When the precision
11
10
2 10
number query ( 10 = 1315) (e) Voters
0
3 10
0
10
10
2 10
number query ( 10 = 1612)
SubOpt pERbacco pERbac Online
recall
0.0 0.2 0.4 0.6 0.8 1.0
3 10
3 10
0
(c) Funding
2 10
number query ( 10 = 3514)
3 10
(f) Synth10k, precision 0.5
10
2 10
2 10
3 10
(d) WDC-80
SubOpt pERbacco pERbac Online 0
10
number query ( 10 = 391)
number query ( 10 = 3514)
3 10
(g) Synth10k, precision 0.2
SubOpt pERbacco pERbac Online
recall
SubOpt pERbacco pERbac Online
recall
0.0 0.2 0.4 0.6 0.8 1.0
0
2 10
(b) Camera
SubOpt pERbacco pERbac Online
recall
0.0 0.2 0.4 0.6 0.8 1.0
(a) Cora
10
number query ( 10 = 2436)
0.0 0.2 0.4 0.6 0.8 1.0
0
recall
recall
3 10
0.0 0.2 0.4 0.6 0.8 1.0
2 10
SubOpt pERbacco pERbac Online
recall
10
number query ( 10 = 137)
SubOpt pERbacco pERbac Online
0.0 0.2 0.4 0.6 0.8 1.0
0
0.0 0.2 0.4 0.6 0.8 1.0
recall
0.0 0.2 0.4 0.6 0.8 1.0
SubOpt pERbacco pERbac Online
0
10
2 10
number query ( 10 = 3514)
3 10
(h) Synth10k, precision 0.05
Fig. 4: Progressive recall on real and synthetic datasets with b = 10.
Progressive Recall
1.0
and infer clusters without reducing the task to independent pairwise comparisons. Our proposal is complementary to these lines of work. Rather than introducing a new oracle implementation, we study ER as a dataset-level inference problem under budget constraints, focusing on how to progressively resolve an entire dataset by adaptively selecting bounded-size oracle queries.
0.8 0.6 0.4 Online+LLM (b=2) Online+LLM (b=5) Online+LLM (b=10) Online+LLM (b=20)
0.2 0.0
0
num queries ( )
pERbacco+LLM (b=2) pERbacco+LLM (b=5) pERbacco+LLM (b=10) pERbacco+LLM (b=20)
VI. C ONCLUSIONS
2
This paper studies entity resolution in a pay-as-you-go setting where an oracle jointly resolves bounded-size batches of records under a limited budget. This abstraction captures a wide range of modern resolution mechanisms, including setbased [12], [15] models, human-in-the-loop systems [14], [16], and LLMs [13], while remaining agnostic to the specific underlying model. We show that moving beyond pairwise queries fundamentally changes the problem: an optimal sequence of batch queries may not exist, and selecting the next batch by maximizing the estimated gain is NP-hard. These results clarify why strategies designed for pairwise ER [10] do not directly extend to the batched setting. Building on this analysis, we proposed a practical approach for progressive batched entity resolution that adaptively allocates oracle calls by exploiting similarity structure and previously acquired information. Experiments on real and synthetic datasets demonstrate that this strategy consistently achieves higher progressive recall than state-of-the-art baselines under comparable budgets, highlighting the benefits of explicitly reasoning over batches. As a final remark, we note that our solution assumes a consistent oracle to isolate the algorithmic problem of budgetaware batch selection. Extending the framework to handle noisy or erroneous oracle outputs, incorporating uncertainty into batch selection, and accounting for heterogeneous oracle costs are important, non-trivial directions for future research.
Fig. 5: Progressive recall on Cora for pERbacco and Oracle under the same LLM setting (GPT-5 mini, fewshot, 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 algorithmic problem of budgetaware batch selection. ER with LLMs and Set-based models. Besides the seminal paper [50], Peeters et al. [51] provide a comprehensive analysis of LLM-based ER, which is primarily based on pairwise entity matching. More recently, LLM-CER [52] and C OM ME [13] show that LLMs can effectively act as bounded oracles for ER by jointly clustering small sets of records within a single, carefully designed prompt, thus making multi-record ER feasible. However, these works focus on the behavior of individual queries and do not address how to allocate a limited budget of LLM calls at the dataset level. The idea of resolving entities by jointly analyzing sets of records is not specific to LLMs. Set-based models such as Set Transformers [12], as well as vision-based identity clustering systems [15], directly operate on bounded collections of items
12
ACKNOWLEDGMENT
[19] 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. [20] S. Wang, X. Xiao, and C. Lee, “Crowd-based deduplication: An adaptive approach,” in SIGMOD, T. K. Sellis, S. B. Davidson, and Z. G. Ives, Eds., 2015, pp. 1263–1277. [21] V. K. Yalavarthi, X. Ke, and A. Khan, “Select your questions wisely: For entity resolution with crowd errors,” in CIKM, 2017, pp. 317–326. [22] 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. [23] R. E. Korf, “Multi-way number partitioning.” in IJCAI, vol. 9, 2009, pp. 538–543. [24] U. Feige, D. Peleg, and G. Kortsarz, “The dense k-subgraph problem,” Algorithmica, vol. 29, no. 3, pp. 410–421, Mar. 2001. [25] P. Christen, Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection, ser. Data-Centric Systems and Applications. Springer, 2012. [26] 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. [27] 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. [28] R. Peeters and C. Bizer, “Using chatgpt for entity matching,” in ADBIS, 2023, pp. 221–230. [29] R. Wang, Y. Li, and J. Wang, “Sudowoodo: Contrastive self-supervised learning for multi-purpose data integration and preparation,” in ICDE, 2023, pp. 1502–1515. [30] P. Christen, “A survey of indexing techniques for scalable record linkage and deduplication,” IEEE TKDE, vol. 24, no. 9, pp. 1537–1555, 2012. [31] G. Papadakis, G. Papastefanatos, T. Palpanas, and M. Koubarakis, “Scaling entity resolution to large, heterogeneous data with enhanced meta-blocking.” in EDBT, 2016, pp. 221–232. [32] L. Gagliardelli, G. Papadakis, G. Simonini, S. Bergamaschi, and T. Palpanas, “GSM: A generalized approach to supervised meta-blocking for scalable entity resolution,” Inf. Syst., vol. 120, p. 102307, 2024. [33] 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. [34] 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. [35] R. Peeters, R. C. Der, and C. Bizer, “Wdc products: A multi-dimensional entity matching benchmark,” arXiv preprint arXiv:2301.09521, 2023. [36] l. Koumarelas, T. Papenbrock, and F. Naumann, “Mdedup: duplicate detection with matching dependencies,” PVLDB, vol. 13, no. 5, pp. 712– 725, Jan. 2020. [37] 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. [38] 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. [39] 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. [40] M. Rosvall, D. Axelsson, and C. T. Bergstrom, “The map equation,” Eur. Phys. J. Spec. Top., vol. 178, no. 1, pp. 13–23, 2009. [41] B. S. Khan and M. A. Niazi, “Network community detection: A review and visual survey,” arXiv preprint arXiv:1708.00977, 2017. [42] 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,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE), 2024, pp. 3696–3709. [43] A. Zeakis, G. Papadakis, D. Skoutas, and M. Koubarakis, “Avenger: Ensembling and fine-tuning llms for select prompts in entity resolution,” in The Semantic Web. Cham: Springer Nature Switzerland, 2025, pp. 301–320. [44] 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.
This work is partly funded by the HORIZON Research and Innovation Action 101135576 INTEND “Intent-based data operation in the computing continuum”. The authors used OpenAI ChatGPT/Codex to assist with grammar polishing, phrasing suggestions, LaTeX and code-generation support, and automation of experiment-running scripts. The AI-assisted editing was applied throughout the manuscript to text written by the authors; the code and automation assistance supported the experiments reported in Section IV. The authors reviewed, verified, and approved all content, code, experimental results, claims, and conclusions, and no AI-generated text was used as substantive scientific content. R EFERENCES [1] V. Christophides, V. Efthymiou, T. Palpanas, G. Papadakis, and K. Stefanidis, “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] 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] J. Maciejewski, K. Nikoletos, G. Papadakis, and Y. Velegrakis, “Progressive entity matching: A design space exploration,” PACMMOD, vol. 3, no. 1, Feb. 2025. [4] 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] 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] D. Javdani, H. Rahmani, M. Allahgholi, and F. Karimkhani, “Deepblock: A novel blocking approach for entity resolution using deep learning,” in ICWR, 2019, pp. 41–44. [7] 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] Y. Yu, Z. Huang, Y. Zhou, W. Li, and Y. Shao, “Aspdup: Ast-sequencebased progressive duplicate code detection tool for onsite programming code,” in Internetware, 2020, pp. 260–264. [9] G. Simonini, G. Papadakis, T. Palpanas, and S. Bergamaschi, “Schemaagnostic progressive entity resolution,” IEEE TKDE, vol. 31, no. 6, pp. 1208–1221, 2019. [10] D. Firmani, B. Saha, and D. Srivastava, “Online entity resolution using an oracle,” PVLDB, vol. 9, no. 5, pp. 384–395, 2016. [11] I. P. Fellegi and A. B. Sunter, “A theory for record linkage,” J. Am. Stat. Assoc., vol. 64, no. 328, pp. 1183–1210, 1969. [12] 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,” in ICML, 2019, pp. 3744–3753. [13] 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,” in COLING, 2025, pp. 96–109. [14] J. Wang, T. Kraska, M. J. Franklin, and J. Feng, “Crowder: Crowdsourcing entity resolution,” PVLDB, vol. 5, no. 11, pp. 1483–1494, 2012. [15] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in CVPR, 2015, pp. 815–823. [16] V. Verroios, H. Garcia-Molina, and Y. Papakonstantinou, “Waldo: An adaptive human interface for crowd entity resolution,” in SIGMOD, 2017, pp. 1133–1148. [17] 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. [18] 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.
13
[45] 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,” in CIDR, 2007, pp. 342–350. [46] T. Papenbrock, A. Heise, and F. Naumann, “Progressive duplicate detection,” IEEE TKDE, vol. 27, no. 5, pp. 1316–1329, 2015. [47] G. Simonini, L. Zecchini, S. Bergamaschi, and F. Naumann, “Entity resolution on-demand,” PVLDB, vol. 15, no. 7, pp. 1506–1518, 2022. [48] S. Sarawagi and A. Bhamidipaty, “Interactive deduplication using active learning,” in Proceedings 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. [49] 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. [50] A. Narayan, I. Chami, L. J. Orr, and C. Ré, “Can foundation models wrangle your data?” PVLDB, vol. 16, no. 4, pp. 738–746, 2022. [51] R. Peeters, A. Steiner, and C. Bizer, “Entity matching using large language models,” in EDBT, 2025, pp. 529–541. [52] 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