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

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\times T$ matrix whose row-sums are the late-interaction scores, and identifying the top-$K$ rarely requires every entry. We cast this as fixed-confidence top-$K$ identification over a finite population and introduce Col-Bandit, a query-time estimator of the exhaustive-MaxSim top-$K$: it reveals matrix entries in batches without replacement, maintains a finite-population Bernstein-Serfling confidence interval on each candidate's score, whose radius collapses to zero at full reveal, and permanently drops any document whose upper bound shows it cannot finish in the top-$K$, computing only the cells needed to separate the top-$K$. A single relaxation knob ${\alpha }_{\mathrm{ef}}\in (0,1]$ tunes the compute–fidelity trade-off. We deploy ${\alpha }_{\mathrm{ef}}=0.2$, while the conservative ${\alpha }_{\mathrm{ef}}=1$ admits a conditional $\delta$-PAC guarantee under the implemented radius. On BEIR and REAL-MM-RAG, Col-Bandit preserves $\ge 90\%$ fidelity to the exhaustive top-$5$ on every corpus while cutting MaxSim FLOPs by up to $\sim 8\times$, for mean single-thread CPU speedups of $7.0\times$ on x86 and $12.9\times$ on ARM, peaking at $\sim 16\times$. A drop-in reranking layer, it needs no retraining or index changes. Our code is released as open-source software (anonymized repository: https://anonymous.4open.science/r/ColBandit-3DBE).