Exact Sparse Assignment with Costly Target Embeddings: Fixed-Realization Certificates and an Empirical Audit
Organizations: Independent Researcher · University of Southern California · Islamic Azad University, Amol Branch
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 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 ). 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
| 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 |
| 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 |
| 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] |
| 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] |
| 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 |
| cell | max L2 | max coord. | max | 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 |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
| dataset | 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 |
| item | value |
|---|---|
| core run | snapshot A |
| corrected pilot | snapshot B |
| protocol | 5d77a4435ad7d0c9 |
| core configuration | 9dd0740d100656a2 |
| core run record | f27cc0ec0e7af72f |
| pilot configuration | 38164fa20b8a56d6 |
Cost-Aware Inference
Cost-aware inference allocates models, computation, and serving resources to meet quality goals at lower latency, energy use, and monetary cost.
See all 308 papers