# Col-Bandit: Query-Time Top-K Estimation for Late-Interaction Retrieval

arXiv: https://arxiv.org/abs/2602.02827 · HTML: https://mlsanity.com/paper/2602.02827/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2026.

## Built on by (most cited first, 2 of 2)

- [AdaptiveEmbed: Sample-Adaptive Multi-Vector Representation for Multimodal Retrieval](https://mlsanity.com/paper/2608.25412/) (2026)
- [BoundaryMORPH: Budgeted Reranking via Active Set Selection for Diffuse Retrieval](https://mlsanity.com/paper/2609.27213/) (2026)

## Abstract (arXiv)

Multi-vector late-interaction retrievers such as ColBERT achieve state-of-the-art quality, but their query-time cost is dominated by exhaustively computing token-level MaxSim interactions for every candidate document. The MaxSim scores of N candidates against T query tokens form an N× T matrix whose row-sums are the late-interaction scores, and identifying the top-K rarely requires every entry. We introduce Col-Bandit, a query-time estimator of the exhaustive-MaxSim top-K: it reveals matrix entries in batches, maintains a finite-population Bernstein-Serfling confidence interval on each candidate's score, and permanently drops any document whose upper bound falls below the K-th largest lower bound, computing only the cells needed to separate the top-K. A single relaxation knob αef∈(0,1] tunes the compute-fidelity trade-off. We deploy αef=0.2, while αef=1 admits a δ-PAC guarantee under a simplified radius. On BEIR and REAL-MM-RAG, Col-Bandit preserves ≥ 90% fidelity to the exhaustive top-5 on every corpus while cutting MaxSim FLOPs by up to ~8×, for up to ~13× single-thread CPU speedups across x86 and ARM. A drop-in reranking layer, it needs no retraining or index changes.