betaFeedback

WorksComputer Science

Exact Sparse Assignment with Costly Target Embeddings: Fixed-Realization Certificates and an Empirical Audit

Abstract

Embedding-based one-to-one association is common in vision and data integration: detections are associated with tracks and records are linked across databases. Such pipelines often solve a sparse optional assignment whose edge scores add a cheap term to an inner product of neural embeddings. When target embeddings are costly, one can acquire them selectively and stop once a certificate proves that the current assignment is optimal. We give such a certificate for unit-norm embeddings. It bounds the unknown part of every reassignment by a support function and maximizes the resulting robust gains with a second sparse assignment; a shared owner-centred bound dominates any fixed-centre triangle bound. We make precise what is certified when network features are not batch-invariant: the realized values of the acquired rows and every unit-ball completion of the rest, not a second forward pass in a different batch. Auditing against a separately batched cache tests a different property; on our first pilot it produced a spurious 2.49×10−62.49\times10^{-6} objective failure. We audit the corrected protocol on four public text entity-matching benchmarks with two frozen encoders; no image data is used. All 96 certificate simulations and 120 online selective timings were exact on their own realization (largest objective gap 6.82×10−136.82\times10^{-13}). At group size 8 the shared certificate acquires on average 60% of candidate-active targets, against 74% (mean centre), 69% (MEB) and 60% (zero centre): it beats the mean and MEB centres but not the zero centre, and savings concentrate in one benchmark (7% acquired). The prespecified runtime claim is contradicted: selective execution is +0.510 s slower per run (dataset-cluster 95% interval [+0.248, +0.772]). Uniform-microbatch re-encodings preserved the optimum in only 5 of 8 encoder-dataset cells, and 45 of 120 online runs disagreed with an eager cache at near-ties.

Introduction

Many matching pipelines score candidate pairs with a learned embedding model and then select a one-to-one matching. In vision, tracking-by-detection associates detections with existing tracks by an assignment over cheap geometric cues and appearance-embedding affinities [3, 13]; there, track updates usually need every detection’s embedding anyway, so whether lazy acquisition helps is open. In data integration, entity resolution links records across databases in the same way [8, 9]. When the encoder is expensive relative to the assignment solve, a natural idea is to acquire target embeddings lazily. Start from the cheap scores, compute a provisional assignment, and request embeddings only for targets whose unknown features could still change the optimum (Figure 1). This combines exact assignment [7] with a robust-optimization treatment of the unknown features [2], and is related in spirit to threshold-style early stopping in top-kk retrieval [4] and to active feature acquisition [11].

Overview of exact assignment, certification, and audit

Figure 1. Overview. (a) A sparse optional assignment whose edge scores add a cheap term bijb_{ij} to an inner product with a costly target embedding zjz_j; only some targets have been acquired. (b) The certificate bounds the unknown part of every reassignment over the unit ball and maximizes the resulting robust gains with a second sparse assignment; if the maximum Γ\Gamma is at most zero the incumbent is optimal for every completion, otherwise the targets in the maximizing alternative are acquired. Bottom: the shared owner-centred bound (solid) is never looser than the triangle bound through a fixed centre cc (dashed) used by global-centre baselines. (c) Audit on four public text entity-matching benchmarks: mean fraction of candidate-active targets acquired at group size 8 (Table 3), exactness on the certified realization, dataset dependence of the savings, the negative runtime result, and the cross-batch diagnostic (§ 4). No image data is used.

The mathematics below applies to any assignment whose edge scores have the form of Eq. (1), with bounded-norm costly embeddings, whatever the modality. The empirical audit, however, uses only four text entity-matching benchmarks and two frozen text encoders. We ran no vision experiment and make no claim about image matching or tracking.

This paper makes four contributions.

  1. A fixed-realization certificate for sparse optional assignment with unit-ball target embeddings, computable with one additional sparse assignment (Theorem 1).

  1. A shared owner-centred support bound that is never looser than the bound from a global centre: zero, mean, or an approximate minimum enclosing ball [1] (Proposition 1).

  1. A precise statement of the numerical object being certified when transformer features vary with batch composition, together with a same-realization audit that tests Footnote: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

the theorem and a separate cross-batch audit that tests numerical portability (§ 4).

  1. A four-dataset, two-encoder evaluation that reports exactness, acquisition, runtime and batch sensitivity, including negative findings (§ 6).

The results are mixed, and we report them as such. Exactness holds without exception on the certified realization. Feature savings are real but strongly dataset-dependent: large on one benchmark, negligible on two. The prespecified runtime comparison is negative, partly because its geometric schedule acquires almost every target. On these benchmarks the neural score adds no held-out F1 on average over a tuned lexical score. We report feature counts and latency separately and never present the former as the latter.

Problem

Let G=(S∪T,E)G=(S\cup T,E) be a frozen sparse bipartite candidate graph produced by a blocker. Each source i∈Si\in S and target j∈Tj\in T may be used at most once, and unmatched records contribute zero. An edge (i,j)∈E(i,j)\in E has score

sij=bij+λqi⊤zj,(1)s_{ij}=b_{ij}+\lambda q_i^\top z_j, \tag*{(1)}

where bijb_{ij} collects the cheap lexical score, a selected threshold offset and a deterministic 10−1010^{-10} tie term. qiq_i is a known source embedding, and zjz_j is a target embedding that is costly to acquire. We assume ∥zj∥2≤1\lVert z_j\rVert_2\le1. An optional assignment is a matching M⊆EM\subseteq E with value V(M)=∑(i,j)∈MsijV(M)=\sum_{(i,j)\in M}s_{ij}. We solve it exactly by adding a private zero-score dummy column per source and calling a sparse shortest-augmenting-path assignment solver [5].

At any time a set K⊆TK\subseteq T of targets is known. Writing a(j)a(j) for the owner of jj in an incumbent MM (with a(j)=0a(j)=0 and q0:=0q_0:=0 when jj is unmatched), the question is whether MM is optimal for every completion {zj:j∉K, ∥zj∥2≤1}\{z_j:j\notin K,\ \lVert z_j\rVert_2\le1\}.

Certificate

For an unknown target jj and a candidate owner ii (including the dummy), reassigning jj changes the unknown contribution by λ(qi−qa(j))⊤zj≤∣λ∣∥qi−qa(j)∥2\lambda(q_i-q_{a(j)})^\top z_j\le|\lambda|\lVert q_i-q_{a(j)}\rVert_2 by the Cauchy–Schwarz inequality, with equality attainable by a unit vector. Define the robust gain gj(a(j))=0g_j(a(j))=0 and, for i≠a(j)i\ne a(j),

gj(i)={sij−sa(j)j,j∈K,bij−ba(j)j+∣λ∣∥qi−qa(j)∥2,j∉K,(2)g_j(i)= \begin{cases} s_{ij}-s_{a(j)j}, & j\in K,\\ b_{ij}-b_{a(j)j}+|\lambda|\lVert q_i-q_{a(j)}\rVert_2, & j\notin K, \end{cases} \tag*{(2)}

for edges (i,j)∈E(i,j)\in E and for i=0i=0 (dropping jj), with s0j=b0j=0s_{0j}=b_{0j}=0.

Theorem 1 (Fixed-realization certificate). Let Γ=max⁡M′∑jgj(a′(j))\Gamma=\max_{M'}\sum_j g_j(a'(j)), where a′a' ranges over the owner maps of optional assignments M′M' in GG. If Γ≤0\Gamma\le0, then V(M)≥V(M′)V(M)\ge V(M') for every optional assignment M′M' and every unit-ball completion of the unknown targets.

Proof. For any M′M' with owner map a′a', V(M′)−V(M)=∑j∈T(sa′(j)j−sa(j)j)V(M')-V(M)=\sum_{j\in T}(s_{a'(j)j}-s_{a(j)j}) because both values decompose over targets and unmatched targets contribute zero. For j∈Kj \in K the term equals gj(a(j))g_j(a^{(j)}). For j∉Kj \notin K it equals ba′(j)j−ba(j)j+λ(qa′(j)−qa(j))⊤zj≤gj(a′(j))b_{a'(j)j} - b_{a(j)j} + \lambda(q_{a'(j)} - q_{a(j)})^\top z_j \le g_j(a'(j)) for every ∥zj∥≤1\lVert z_j\rVert\le1. Hence V(M′)−V(M)≤∑jgj(a′(j))≤Γ≤0V(M') - V(M) \le\sum_j g_j(a'(j)) \le\Gamma\le0. The maximization over a′a' is itself an optional assignment on the gain matrix, since a′a' must use each source at most once.

The guarantee conditions on the realized source rows and the realized values of the acquired target rows. It is a statement about one numerical instance.

Global-centre baselines. For any fixed centre cc, ∥qi−qa(j)∥≤∥qi−c∥+∥qa(j)−c∥\lVert q_i - q_{a(j)}\rVert\le\lVert q_i - c\rVert+ \lVert q_{a(j)} - c\rVert. Replacing the shared term by this triangle bound gives a valid but looser certificate. We use c=0c = 0, the arithmetic mean of owner vectors, and a deterministic Badoiu–Clarkson approximate minimum-enclosing-ball (MEB) centre [1].

Proposition 1 (Dominance at a fixed known set). For the same incumbent and known set, every robust gain under the shared bound is at most the corresponding gain under any fixed-centre bound. Hence Γshared≤Γc\Gamma_{\mathrm{shared}} \le\Gamma_c, and whenever the centre-cc certificate certifies, the shared certificate does as well.

A short proof is given in Sec. A. The proposition compares bounds at a fixed state. It does not imply that the shared method acquires fewer targets along an adaptive trajectory, because different bounds request different targets. That comparison is empirical.

Remark 1 (No worst-case savings). Savings cannot be guaranteed in the worst case. If two sources compete for one target and their lexical scores tie, then gj≥∣λ∣∥q1−q2∥>0g_j \ge\lvert\lambda\rvert\lVert q_1 - q_2\rVert> 0 until zjz_j is known, so no certificate can stop without acquiring jj. Replicating this gadget across all targets forces full acquisition.

Acquisition rule. The nominal incumbent sets every unknown zj=0z_j = 0. When Γ>0\Gamma> 0, the maximizing alternative (the witness) identifies unknown targets whose owners change. Those targets are requested first, ordered by their robust-gain priority, and the group is filled to the requested size by priority. The rule stops as soon as the certificate holds or all candidate-active targets are known, in which case the exact full scores are used. Group sizes are fixed or geometric (start at gg and double per round).

The numerical object being certified

A frozen transformer is a deterministic function only up to floating-point execution order. Under FP16 inference, encoding the same text in different batch compositions changes coordinates by up to ≈10−3\approx10^{-3} (Table 6). We therefore define the feature oracle explicitly. It consists of the frozen revision, tokenizer and text template, FP16 inference, FP64 direction normalization, FP32 storage with a conservative downward norm correction (so that every row lies in the closed unit ball checked in FP64), and FP64 score and objective accumulation with outward rounding of robust terms.

cellmax L2max coord.max ∣Δs∣|\Delta s|mapping eq.bidir. optimal
Abt–Buy / BGE-small1.55e-039.60e-047.07e-051.001.00
Abt–Buy / MiniLM-L61.18e-032.86e-047.92e-050.000.00
Amazon–Google / BGE-small1.66e-039.83e-042.02e-040.000.00
Amazon–Google / MiniLM-L61.44e-033.79e-042.17e-040.250.25
DBLP–ACM / BGE-small1.68e-039.90e-041.84e-041.001.00
DBLP–ACM / MiniLM-L61.48e-033.82e-042.41e-041.001.00
Walmart–Amazon / BGE-small2.15e-031.21e-031.24e-041.001.00
Walmart–Amazon / MiniLM-L61.32e-033.74e-041.13e-041.001.00

Table 6. Re-encoding all candidate-active targets at fixed microbatches (1, 8, 32, 64) relative to the canonical cache: largest row L2 and coordinate drift, largest edge-score change, fraction of microbatches with an identical optimal mapping, and fraction where each assignment remains optimal under the other’s scores. Every audited row had FP64 norm at most 1.

Same-realization audit (correctness gate). After a timed selective run, the acquired rows are kept bit-for-bit. Only the missing candidate-active targets are encoded, and the full optional assignment is solved on this completed array. The run is exact if the reference objective exceeds the selective objective by at most 10−7+10−12max⁡(1,∣Vref∣,∣Vsel∣)10^{-7} + 10^{-12}\max(1,\lvert V_{\mathrm{ref}}\rvert,\lvert V_{\mathrm{sel}}\rvert). This is exactly the instance quantified by Theorem 1, since the completion is one admissible unit-ball completion.

Cross-batch audit (diagnostic). Our first pilot instead compared the incumbent against an eagerly encoded full cache produced in a different batch composition. That cache changes the acquired rows themselves, so a gap there measures whether the assignment is batch-invariant, not whether the certificate is valid. On that pilot the zero-centred method showed a gap of 2.4886×10−62.4886 \times10^{-6} in all five repetitions (allowed 10−710^{-7}), and the run was stopped by protocol. A corrected pilot reproduces the cross-batch gap (2.49×10−62.49 \times10^{-6}) on the same variants while every same-realization audit is exact. This identifies the original failure as a batch-sensitivity effect on a near-tie, not a certificate violation. We report the cross-batch comparison and re-encodings at fixed microbatches as a separate numerical-portability result.

Experimental protocol

Data and encoders. We use the Abt–Buy, Amazon–Google, Walmart–Amazon and DBLP–ACM text entity-matching benchmarks [6, 9] from pinned, byte-hashed snapshots. The encoders are BGE-small-en-v1.5 [14] and all-MiniLM-L6-v2 [10, 12] at fixed model revisions, with a maximum length of 256 tokens. Each dataset is split 20/80 into development and test sets by gold connected components, so no entity crosses the split.

Blocking and tuning. A character 3–5-gram TF-IDF blocker is used, taking the smallest prespecified width that reaches 0.99 development candidate recall. The embedding weight λ∈{0.25,0.5,1,1.5}\lambda\in\{0.25, 0.5, 1, 1.5\} and threshold are chosen on development data only, and a lexical-only threshold is selected separately. Test labels choose nothing.

Methods. Eager full encoding is the reference. The selective methods are the shared, mean-centred, MEB-centred and zero-centred certificates. Simulations use one frozen embedding matrix with groups of 8, 32 and 128 and witness ordering. Online timings run actual batched FP16 inference with five repetitions in a balanced cyclic order. They cover two scopes: known-source (source embeddings given, as in the formal problem) and end-to-end (source encoding charged). The prespecified primary runtime contrast is shared, end-to-end, geometric from 128 versus full, end-to-end. Disclosure: this primary variant was declared after the first pilot showed a slow fixed-32 schedule, so it is not blind to that single observation.

Statistics. Contrasts are paired and bootstrapped over dataset-level clusters (10,000 draws). Models, groups and repetitions nested within a dataset are not treated as independent. With four datasets these intervals are coarse, and we read them descriptively. Hash prefixes of the protocol, configurations and run records are given in Sec. C.

Results

Exactness

Every one of the 96 simulations (96 exact) and 120 online selective timings (120 exact) was audited on its own realization; the largest same-realization objective gap was 6.82×10−136.82 \times10^{-13}, at floating-point round-off. Against a separately batched eager cache, 45 of 120 online timings would have failed a cache-based audit (largest gap 2.49×10−62.49 \times10^{-6}; Table 1). These are the cross-batch effects discussed in § 4; they are not certificate violations.

methodscopegrouprunsexact (same)cache mismatch
sharede2e128404015
sharedknown128404015
zeroknown128404015

Table 1. Online selective timings: same-realization exactness (the gate) versus a separately batched cache comparison (diagnostic), pooled over datasets and encoders. Scope: e2e = end-to-end, known = known-source; all three variants use the geometric schedule.

Task quality and blocking

Averaged within dataset, the neural score changes held-out F1 by +0.000 relative to the separately tuned lexical-only assignment (dataset-cluster bootstrap 95% interval [-0.010, +0.009], four clusters; Table 2). Minimum test candidate recall is 0.999; quality conclusions are restricted to the frozen candidate graph.

datasetencodercand. recallλ\lambdathr.F1 fullF1 lexicalΔ\DeltaF1
Abt–BuyBGE-small1.0000.250.350.9420.939+0.003
Abt–BuyMiniLM-L61.0000.250.350.9440.939+0.004
Amazon–GoogleBGE-small0.9990.50.80.6940.683+0.010
Amazon–GoogleMiniLM-L60.9990.50.80.6960.683+0.013
Walmart–AmazonBGE-small1.0000.250.80.6760.693-0.017
Walmart–AmazonMiniLM-L61.0000.250.80.6820.693-0.011
DBLP–ACMBGE-small1.0000.50.650.9850.987-0.002
DBLP–ACMMiniLM-L61.0000.50.650.9900.987+0.003

Table 2. Held-out quality of the eager full assignment (the object every exact selective method reproduces). λ\lambda and threshold chosen on development data; lexical-only threshold selected separately. Δ\DeltaF1 is computed before rounding.

Acquisition

Table 3 and Figure 2 report the fraction of candidate-active target embeddings acquired before certification. Per dataset, the shared certificate acquires Abt–Buy 0.86 at 8, 0.89 at 32, 1.00 at 128; Amazon–Google 0.51 at 8, 0.51 at 32, 0.67 at 128; Walmart–Amazon 0.07 at 8, 0.07 at 32, 0.11 at 128; DBLP–ACM 0.95 at 8, 0.97 at 32, 0.99 at 128 of the active targets.

Figure 2. Fraction of candidate-active targets acquired before certification by group size (simulations, witness order, mean over two encoders).

groupsharedmeanMEBzeroshared−best global
80.5960.7370.6910.604-0.008 [-0.078, +0.041]
320.6110.7480.7110.631-0.018 [-0.082, +0.026]
1280.6920.7900.7680.702-0.010 [-0.037, +0.009]

Table 3. Mean fraction of candidate-active target embeddings acquired before certification (simulations, witness order), averaged over the eight dataset–encoder cells, and the shared-minus-best-global contrast with a dataset-cluster bootstrap 95% interval.

The dataset-cluster intervals for shared minus mean-centred and shared minus MEB-centred lie below zero, but shared is statistically indistinguishable from the zero-centred bound (Table 4). One explanation, not tested here, is that in optional assignment many robust moves drop a target. For a drop (owner 0, q0=0q_0 = 0) the shared and zero-centred bounds coincide at ∥λ(qj)∥\lVert\lambda(q_j)\rVert, whereas a centre c≠0c \ne0 gives λ(∥c∥+∥qj−c∥)\lambda(\lVert c\rVert+ \lVert q_j-c\rVert).

baselinemean difference95% interval
mean-0.125[-0.271, -0.022]
MEB-0.090[-0.190, -0.020]
zero-0.013[-0.055, +0.021]

Table 4. Paired comparison of shared minus each global-centre certificate (acquired fraction, witness order; dataset-cluster bootstrap over the four datasets, pooled over encoders and groups).

Runtime

The geometric schedule removes most selectivity. The prespecified timing variants double the group each unresolved round. They acquired 92%–100% of active targets in every dataset, including Walmart–Amazon (92%), where fixed-group certification needed only 7%–11%. The runtime comparison therefore measures a schedule that encodes nearly everything plus certificate overhead. The wall time of a fixed small-group selective run in the high-savings regime was not measured; that is the main open runtime question. Eager end-to-end encoding of all active targets took Abt–Buy 0.65 s, Amazon–Google 0.93 s, Walmart–Amazon 5.43 s, DBLP–ACM 1.20 s (median).

For the prespecified primary contrast (shared, end-to-end, geometric from 128, versus full end-to-end), the selective-minus-full wall time is +0.510 s (per encoder and dataset, the difference of median wall times, averaged within each dataset and then over the four datasets; dataset-cluster bootstrap 95% interval [+0.248, +0.772]), so the prespecified runtime claim is CONTRADICTED (§ 6.6). Known-source timing, reported separately, gives the same direction (Table 5).

variantselectivefullratioacquired
shared/e2e/geo/g1281.5661.0591.330.980
shared/known/geo/g1281.2550.7331.530.980
zero/known/geo/g1281.1600.7331.440.980

Table 5. Online wall time (seconds, median over cells of per-cell medians) for each selective variant and its scope-matched eager baseline; ratio is the geometric mean over cells of selective/full (above 1 means slower). Acquired: fraction of active targets.

Numerical portability across batch sizes

Uniform re-encodings change features (Table 6), and the optimal assignment is bidirectionally preserved at every tested microbatch in only 5 of 8 cells. In contrast, online acquisition mixes rows from batches of different composition, and 45 of 120 online runs produced an incumbent that was exactly optimal on its own realization yet sub-optimal by up to 2.49×10−62.49 \times10^{-6} on the eager cache. The assignment is therefore not batch-invariant, although the certificate is exact on every realized instance.

Prespecified claims

Scored from these records, the prespecified claims receive the following labels: assignment is invariant to tested batch sizes: CONTRADICTED; blocking preserves gold candidate recall: SUPPORTED; canonical embeddings satisfy unit ball: SUPPORTED; exact recovery with certificate: SUPPORTED; exact recovery with certificate on same realization: SUPPORTED; neural score improves over lexical only:

WEAKENED; selective acquisition improves end to end run-time: CONTRADICTED; shared certificate reduces acquisition vs global centers: WEAKENED; task quality matches full model: SUPPORTED. With four dataset clusters, a SUPPORTED label means every cluster agrees in sign, not that the effect is precisely estimated.

Discussion

Runtime. The runtime claim is contradicted. Eager encoding of all active targets takes a few seconds at most with these small encoders, and the prespecified geometric schedule acquired almost every target, so the selective loop paid the certificate and solver overhead without saving features. In the one regime with large savings (Walmart–Amazon, about 7% of 17,646 active targets needed at small fixed groups), selective wall time was not measured. That comparison, ideally with a more expensive encoder, is the main open question and would need a new prespecified variant.

Acquisition. Savings are strongly dataset-dependent: large for Walmart–Amazon, moderate for Amazon–Google and negligible for Abt–Buy and DBLP–ACM, where nearly every target is needed. The shared bound beats the mean and MEB centres but not the zero centre.

Task value of the costly feature. After development-only tuning, the neural score changes held-out F1 by about zero relative to an independently tuned lexical-only assignment. Exact selective recovery reproduces the full model, but on these benchmarks the full model is not clearly better than the cheap one.

Numerical portability. The certificate is exact on the realized instance, but the optimal assignment itself is not batch-invariant (three of eight cells under uniform re-encoding; 45 of 120 online runs against an eager cache). Deployments that re-encode features must treat batch invariance as a separate requirement; the certificate does not provide it.

Limitations. The evidence covers four text benchmarks, two small frozen encoders and a frozen blocker graph; no image data is used, so transfer to vision association problems is untested. With four dataset clusters the bootstrap intervals are coarse.

LLM Usage Statement

The authors developed the research ideas and proofs. AI tools provided coding, debugging, writing, and editing support, including polishing the exposition and presentation of the proofs. The authors reviewed and verified the resulting material and retain responsibility for the research questions, methods, proofs, experiments, interpretation, and final content.

Proof of Proposition 1 (dominance at a fixed known set)

Fix the incumbent MM with owner map aa and the known set KK. For a fixed centre cc, the centre-cc certificate uses the robust gains gjc(i)g_j^c(i) obtained from Eq. (2) by replacing the unknown-target term ∣λ∣∥qi−qa(j)∥2|\lambda|\lVert q_i-q_{a(j)}\rVert_2 with ∣λ∣(∥qi−c∥2+∥qa(j)−c∥2)|\lambda|(\lVert q_i-c\rVert_2+\lVert q_{a(j)}-c\rVert_2); known targets and the incumbent owner (gj(a(j))=0g_j(a(j))=0) are treated identically by both certificates.

Gains. For j∈Kj\in K the two gains coincide. For j∉Kj\notin K and any candidate owner ii (including the dummy i=0i=0 with q0=0q_0=0), the triangle inequality gives ∥qi−qa(j)∥2≤∥qi−c∥2+∥qa(j)−c∥2\lVert q_i-q_{a(j)}\rVert_2\le\lVert q_i-c\rVert_2+\lVert q_{a(j)}-c\rVert_2, so gjshared(i)≤gjc(i)g_j^{\mathrm{shared}}(i)\le g_j^c(i) entrywise.

Certificate values. Both Γshared\Gamma_{\mathrm{shared}} and Γc\Gamma_c are maxima over the same set of owner maps a′a' of optional assignments in GG (Theorem 1). For every such a′a', ∑jgjshared(a′(j))≤∑jgjc(a′(j))≤Γc\sum_j g_j^{\mathrm{shared}}(a'(j))\le\sum_j g_j^c(a'(j))\le\Gamma_c; taking the maximum over a′a' gives Γshared≤Γc\Gamma_{\mathrm{shared}}\le\Gamma_c. Hence Γc≤0\Gamma_c\le0 implies Γshared≤0\Gamma_{\mathrm{shared}}\le0: whenever the centre-cc certificate certifies, the shared certificate does as well. □

As stated in § 3, this compares bounds at one fixed state; it says nothing about the number of targets acquired along an adaptive trajectory, which is measured empirically.

Per-dataset acquisition and eager encoding time

Table 7 restates, in table form, the per-dataset acquired fractions of the shared certificate reported in § 6 (simulations, witness order, mean over the two encoders), together with the fraction acquired by the prespecified geometric timing schedule and the median eager end-to-end encoding time of all active targets.

datasetg=8g=8g=32g=32g=128g=128eager (s)
Abt–Buy0.860.891.000.65
Amazon–Google0.510.510.670.93
Walmart–Amazon0.070.070.115.43
DBLP–ACM0.950.970.991.20

Table 7. Shared certificate: fraction of candidate-active targets acquired at fixed group sizes 8, 32 and 128, and median eager end-to-end encoding time of all active targets.

The prespecified geometric timing variants acquired 92%–100% of active targets in every dataset, including Walmart–Amazon (92%), where fixed-group certification needed only 7%–11%. Walmart–Amazon has 17,646 active targets.

Reproducibility record

The reported core run and the corrected pilot each executed one pinned code snapshot (snapshot A and snapshot B, respectively). Table 8 lists the recorded SHA-256 prefixes of the protocol, the run configurations and the run records, so that the material used for the reported numbers can be matched unambiguously.

itemvalue
core runsnapshot A
corrected pilotsnapshot B
protocol5d77a4435ad7d0c9
core configuration9dd0740d100656a2
core run recordf27cc0ec0e7af72f
pilot configuration38164fa20b8a56d6
pilot run record29b81aec174cd264

Table 8. Run record: code snapshots and SHA-256 prefixes.

References

  1. [1]Mihai Bădoiu and Kenneth L. Clarkson. Smaller core-sets for balls. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 801–802, 2003.DOI
  2. [2]Aharon Ben-Tal and Arkadi Nemirovski. Robust optimization – methodology and applications. Mathematical Programming, 92(3):453–480, 2002.
  3. [3]Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, and Ben Upcroft. Simple online and realtime tracking. In IEEE International Conference on Image Processing (ICIP), pages 3464–3468, 2016.DOI
  4. [4]Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences, 66(4):614–656, 2003.
  5. [5]Roy Jonker and Anton Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4):325–340, 1987.
  6. [6]Hanna Köpcke, Andreas Thor, and Erhard Rahm. Evaluation of entity resolution approaches on real-world match problems. Proceedings of the VLDB Endowment, 3(1–2):484–493, 2010.DOI
  7. [7]Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2):83–97, 1955.
  8. [8]Yuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan. Deep entity matching with pre-trained language models. Proceedings of the VLDB Endowment, 14(1):50–60, 2020.DOI
  9. [9]Sidharth Mudgal, Han Li, Theodoros Rekatsinas, AnHai Doan, Youngchoon Park, Ganesh Krishnan, Rohit Deep, Esteban Arcaute, and Vijay Raghavendra. Deep learning for entity matching: A design space exploration. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD), pages 19–34, 2018.DOI
  10. [10]Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using Siamese BERT-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing (EMNLP-IJCNLP), pages 3982–3992, 2019.arxiv.org/abs/1908.10084
  11. [11]Maytal Saar-Tsechansky, Prem Melville, and Foster Provost. Active feature-value acquisition. Management Science, 55 (4):664–684, 2009. 1
  12. [12]Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. MiniLM: Deep self-attention distillation for task-agnostic compression of pre-trained transformers. In Advances in Neural Information Processing Systems, pages 5776–5788, 2020. 3arxiv.org/abs/2002.10957
  13. [13]Nicolai Wojke, Alex Bewley, and Dietrich Paulus. Simple online and realtime tracking with a deep association metric. In IEEE International Conference on Image Processing (ICIP), pages 3645–3649, 2017. 1arxiv.org/abs/1703.07402
  14. [14]Shitao Xiao, Zheng Liu, Peitian Zhang, Niklas Muennighoff, Defu Lian, and Jian-Yun Nie. C-Pack: Packed resources for general Chinese embeddings. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 641–649, 2024. 3arxiv.org/abs/2309.07597

Paper details

vlnc:W_z6en6vyc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI tools

View statement
Looking for related papers…
Contents