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−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−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.
Figures & tables
Figure 1: Overview. (a) A sparse optional assignment whose edge scores add a cheap term bij to an inner product with a costly target embedding zj ; 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 Γ 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 c (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 ( Tab. 3 ), exactness on the certified realization, dataset dependence of the savings, the negative runtime result, and the cross-batch diagnostic ( Sec. 4 ). No image data is used.
exact
cache
method
scope
group
runs
(same)
mismatch
shared
e2e
128
40
40
15
shared
known
128
40
40
15
zero
known
128
40
40
15
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.
dataset
encoder
cand. recall
λ
thr.
F1 full
F1 lexical
Δ F1
Abt–Buy
BGE-small
1.000
0.25
0.35
0.942
0.939
+0.003
Abt–Buy
MiniLM-L6
1.000
0.25
0.35
0.944
0.939
+0.004
Amazon–Google
BGE-small
0.999
0.5
0.8
0.694
0.683
+0.010
Amazon–Google
MiniLM-L6
0.999
0.5
0.8
0.696
0.683
+0.013
Walmart–Amazon
BGE-small
1.000
0.25
0.8
0.676
0.693
-0.017
Walmart–Amazon
MiniLM-L6
1.000
0.25
0.8
0.682
0.693
-0.011
Table 2: Held-out quality of the eager full assignment (the object every exact selective method reproduces). λ and threshold chosen on development data; lexical-only threshold selected separately. Δ F1 is computed before rounding.
group
shared
mean
MEB
zero
shared − best global
8
0.596
0.737
0.691
0.604
-0.008 [-0.078, +0.041]
32
0.611
0.748
0.711
0.631
-0.018 [-0.082, +0.026]
128
0.692
0.790
0.768
0.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.
baseline
mean difference
95% 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).
Figure 2: Fraction of candidate-active targets acquired before certification by group size (simulations, witness order, mean over two encoders).
variant
selective
full
ratio
acquired
shared/e2e/geo/g128
1.566
1.059
1.33
0.980
shared/known/geo/g128
1.255
0.733
1.53
0.980
zero/known/geo/g128
1.160
0.733
1.44
0.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.
cell
max L2
max coord.
max ∣Δs∣
mapping eq.
bidir. optimal
Abt–Buy / BGE-small
1.55e-03
9.60e-04
7.07e-05
1.00
1.00
Abt–Buy / MiniLM-L6
1.18e-03
2.86e-04
7.92e-05
0.00
0.00
Amazon–Google / BGE-small
1.66e-03
9.83e-04
2.02e-04
0.00
0.00
Amazon–Google / MiniLM-L6
1.44e-03
3.79e-04
2.17e-04
0.25
0.25
DBLP–ACM / BGE-small
1.68e-03
9.90e-04
1.84e-04
1.00
1.00
DBLP–ACM / MiniLM-L6
1.48e-03
3.82e-04
2.41e-04
1.00
1.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.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
dataset
g=8
g=32
g=128
eager (s)
Abt–Buy
0.86
0.89
1.00
0.65
Amazon–Google
0.51
0.51
0.67
0.93
Walmart–Amazon
0.07
0.07
0.11
5.43
DBLP–ACM
0.95
0.97
0.99
1.20
Appendix
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.
item
value
core run
snapshot A
corrected pilot
snapshot B
protocol
5d77a4435ad7d0c9
core configuration
9dd0740d100656a2
core run record
f27cc0ec0e7af72f
pilot configuration
38164fa20b8a56d6
Appendix
Table 8: Run record: code snapshots and SHA-256 prefixes.