cs.LGNov 15, 2026

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

Authors: Hamidreza Hasani Balyani, Mahtab Movahhedrad, Seyed Pouyan Mousavi Davoudi

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

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 7, 2026

Nearly Optimal Attention Coresets

We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values (K,V)(K,V) in Rd\mathbb{R}^d, there exists a subset (K′,V′)(K',V') of size at most O(deρ+o(ρ)/ε)O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon}) such that ∥Attn⁡(q,K,V)−Attn⁡(q,K′,V′)∥≤ε\left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon simultaneously for all queries whose norm is bounded by ρρ. This outperforms the best known results for this problem. We also offer an improved lower bound showing that ε\varepsilon-coresets must have size Ω(deρ/ε)Ω({\sqrt{d} e^ρ/ε}).
Jul 23, 2026

Incremental Optimal Assignment for Real-Time Crowd Tracking

Multi-object tracking in dense crowds requires solving a bipartite assignment problem between detections and trajectories at every video frame. The classical Hungarian algorithm solves this in O(N3)O(N^3) time, which becomes a bottleneck for large scenes with hundreds of people. We propose an incremental assignment algorithm that exploits the block-sparse structure of crowd tracking cost matrices --- dense within each crowd cluster, near-zero between clusters. We compute the exact same optimal N×NN \times N assignment as the Hungarian algorithm, but via an incremental strategy: we add one person at a time, exploiting the fact that after step n−1n-1 the dual potentials are exactly optimal for the (n−1)×(n−1)(n-1)\times(n-1) subproblem --- a strictly stronger condition than the intermediate feasibility maintained by the Hungarian algorithm during its NN outer iterations. Each new step therefore requires only a single augmenting path search from a certified optimal starting point. This avoids repeated full-matrix scans while guaranteeing an identical globally optimal result. A diagonal-reordering invariant keeps the data structure compact and cache-friendly. On realistic crowd benchmarks with N∈[200,5000]N \in [200, 5000] people organised into dense clusters, our algorithm achieves \textbf{3.7--6.5×\times speedup} over the Hungarian baseline while producing provably optimal matchings identical to those of Hungarian. The speedup grows with NN and remains stable beyond N=3000N=3000, making the method especially attractive for large-scale crowd scenes such as stadium exits and mass public events.
Oct 17, 2026

Exact Risk Certificates for Pairwise-Judged Reranking

Pairwise relevance judgments constrain both the loss numerator and the ideal-ranking denominator of nDCG. We characterize the exact worst-case loss of replacing a ranking with a fixed proposal. Binary gains attain this loss and provide an inspectable witness. Threshold verification reduces to at most K+1K+1 maximum-closure problems. Our exposure-flow ablation isolates denominator coupling: on shared judge trajectories, exact verification saves 2.34 comparisons per TREC-DL development query and 1.98 per confirmation query at a budget of 32. Savings transfer to BEIR and a second proposer. Predictive gates achieve higher deployment gains, while certificates expose the worst gains still permitted by accepted comparisons.