acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 candidates against query tokens form an matrix whose row-sums are the late-interaction scores, and identifying the top- rarely requires every entry. We cast this as fixed-confidence top- identification over a finite population and introduce Col-Bandit, a query-time estimator of the exhaustive-MaxSim top-: 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-, computing only the cells needed to separate the top-. A single relaxation knob tunes the compute–fidelity trade-off. We deploy , while the conservative admits a conditional -PAC guarantee under the implemented radius. On BEIR and REAL-MM-RAG, Col-Bandit preserves fidelity to the exhaustive top- on every corpus while cutting MaxSim FLOPs by up to , for mean single-thread CPU speedups of on x86 and on ARM, peaking at . 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).

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
late-interaction retrieval, multi-vector retrieval, ColBERT, efficient retrieval, MaxSim, reranking, query-time pruning, multi-armed bandits, top-K identification, SIMD, CPU inference

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_UkpjOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to reduce MaxSim scoring computation in ColBERT-style multi-vector retrieval. It treats the per-query-token MaxSim values for candidate documents as an implicit matrix, reveals entries in batches according to a shared random order, and constructs total-score intervals from the partial observations. Documents that appear unable to reach the top ranks are eliminated early, while the survivors are fully scored using the reference kernel. Experiments on text and multimodal retrieval datasets measure computational savings and CPU latency improvements, with additional evaluations integrating the method into PLAID, LEMUR, and MUVERA.

Critical strengths
  • Allocating different amounts of computation to different documents delivers practical CPU speedups---

The method stops scoring clearly inferior documents early and reserves more computation for candidates that are difficult to distinguish. It requires no retraining of the retrieval encoder and can operate on existing multi-vector representations. The full-corpus experiments report substantial single-thread CPU speedups using the same underlying kernel for exhaustive scoring and Col-Bandit. The no-elimination control also supports the conclusion that the gains mainly come from reducing scoring computation. Comparisons with static token selection provide further evidence for the value of allocating computation separately to each document.

  • Integration with recent efficient retrieval systems supports the method's practical value

The evaluation goes beyond full-corpus exhaustive scoring. With PLAID, the method achieves approximately 1.8-3.2x reranking speedups at 1,000 candidates. With the recent LEMUR system, it reports approximately 1.5-2x end-to-end speedups at 1,000-2,000 candidates, with small changes in Recall and nDCG. LEMUR is itself a competitive retrieval baseline, making this evidence persuasive. The authors also report that integrating Col-Bandit with MUVERA does not produce a speedup, giving a candid account of the method's scope.

Critical weaknesses

[W1] - The integration experiments do not yet fully establish a speed-quality advantage over tuned retrieval pipelines

The large speedups highlighted in the abstract mainly come from scoring the entire corpus. This setting is appropriate for isolating computational savings in the scoring stage, but practical retrieval systems can use an index to reduce the candidate set first. I therefore place more weight on end-to-end results with existing retrieval systems. The paper provides useful evidence here, but the LEMUR results report gains at candidate counts of 1,000 and 2,000 without showing complete speed-quality curves after tuning both systems.

Holding the candidate set fixed measures the incremental benefit of pruning, but the original system can also adjust the number of candidates to trade quality for speed. It remains unclear how much of the reported end-to-end advantage persists at matched final retrieval quality when the baseline can tune its retrieval and reranking parameters, and Col-Bandit can tune its elimination strength.

The MUVERA results also leave the conditions for obtaining a speedup unclear. The authors report no acceleration at 200, 500, or 1,000 candidates; on SciDocs with 200 candidates, reranking increases from 0.4 ms to 7.3 ms, which they attribute to round overhead. However, PLAID approaches break-even at approximately 100 candidates, so candidate count alone cannot explain the difference. The paper does not provide enough stage-level measurements to distinguish the effect of how readily candidates can be eliminated from implementation overhead. This limits a practitioner's ability to determine when to use Col-Bandit.

[W2] - The mathematical analysis does not establish the validity of the simplified confidence radius used in practice

Equation 5 omits the additive range term from the original empirical Bernstein-Serfling inequality, while Theorem 1 assumes that the simplified radius yields valid confidence intervals. The analysis therefore establishes the correctness of elimination given valid intervals, but does not prove that the intervals actually used in the method satisfy this premise. The authors explicitly acknowledge this limitation in Remark 2. This gap limits the theoretical support for the algorithm and leaves the interpretation of the confidence parameter delta and the conservative endpoint largely dependent on empirical results. I would like the authors either to state sufficient additional conditions for the simplified radius and prove its validity under those conditions, or to provide a version using a complete, valid confidence bound and measure the computational cost of restoring the guarantee. Otherwise, the current algorithm should be positioned more explicitly as an empirical heuristic, with a clear account of what the conditional theorem establishes in the practical setting.

Questions for authors
  1. At matched retrieval quality, how much end-to-end speedup does LEMUR plus Col-Bandit retain after fully tuning both systems?

  2. Why does MUVERA show no speedup at 1,000 candidates while PLAID approaches break-even at around 100? Can you provide a timing breakdown to explain the difference?

  3. Under what additional conditions is the simplified confidence radius in Equation 5 valid? If the additive range term is restored, how much practical speedup remains at alpha_ef=1?

6 comments
AuthorsOpenReview ↗

(1/3) The complete bound, added and measured

Thank you for the careful review. We did what W2 asks. The complete, valid confidence bound is added, we show why it always reduces to the hard bounds, and we timed it in our compiled kernel. The fast method stays an empirical approximation. All new results and clarifications below go into the revised paper.

W2: "Equation 5 omits the additive…"

Q3: "Under what additional conditions is…"

We restored the term and timed it in our CPU kernel. With the complete bound, Col-Bandit runs at 0.65 to 1.03× the speed of exhaustive scoring. With the simplified radius it runs at 1.66 to 2.19×. The simplified radius has no established δ-PAC guarantee, also at α=1.

The reason is simple. The restored term is always wider than the paper's hard bounds (§4.1), so the hard bounds make every decision. After n of T cells, the hard bounds limit a document's score to an interval of width (T−n)R, and the estimate lies inside it. The restored term alone is T·κ·R·log(10NT/δ)/n, with κ = 7/3 + 3/√2 and R = 2 (cosine range [−1,1]). Since n(T−n) ≤ T²/4, this term is at least (T−n)R whenever T ≤ 4κ·log(10NT/δ). That holds up to T ≈ 185 even for N=1 at δ=0.01, and our queries have at most 112 tokens. So the complete bound gives exactly the run with the hard bounds alone, and screening ends up computing most of the cells.

The protocol uses 50 timed queries per corpus, K=5, M=5, δ=0.01, one thread, and the same kernel and machine.

CorpusNRadius, α=1Cells computedOv@5Speedup
SciDocs25,657Complete93.4%1.0001.03×
Simplified58.9%1.0001.66×
ArguAna8,674Complete96.3%1.0000.91×
Simplified57.7%1.0001.77×
Quora522,931Complete87.2%1.0000.65×
Simplified24.4%0.9962.19ׇ

Speedup is exhaustive scoring time divided by Col-Bandit time on the same queries. Below 1× means Col-Bandit is slower.

‡On Quora the simplified run gives 24.4% / 0.996 here vs 27.7% / 1.000 in the paper.

Theorem 1 holds only if the intervals are valid, and the deployed α=0.2 is an empirical setting. In practice, at α=1 the simplified intervals missed the true score in 0.15 to 1.45% of checks over 2,400 queries on six corpora, yet no true top-5 document was lost. These are fixed samples, not a calibrated failure rate. On your first option, we have no conditions under which the simplified radius is provably valid.

We take the route you suggest. The revision presents the fast method as an empirical approximation and states exactly what Theorem 1 gives, namely that elimination is correct whenever the intervals are valid, and that the complete bound makes them valid at the cost in the table.

In the revision, the complete bound and this argument go next to Eq. 5, Theorem 1 is stated as conditional, and every number is labeled with its operating point.

AuthorsOpenReview ↗

(2/3) MUVERA: Col-Bandit is faster from about 100 candidates

W1: "The MUVERA results also leave…"

Q2: "Why does MUVERA show no…"

With the new timing, MUVERA behaves like PLAID. Col-Bandit is faster on both from about 100 candidates up. Col-Bandit now scores MUVERA candidates 1.50 to 3.20× faster than full scoring at α=0.3, with Overlap@5 .974 to 1.000. At the deployed α=0.2 it is 1.80 to 4.36× faster, with Overlap@5 .944 to .978. Both hold for 200 to 1,000 candidates. The speed ratio grows from 200 to 500 to 1,000 candidates. At 1,000 candidates, the size in your question, it is 2.52 to 3.20× at α=0.3.

Your question led us to recheck the paper's SciDocs number of 0.4→7.3 ms. It came from an early implementation, and we should not have used it for MUVERA candidates on a CPU. We measured both methods again on the same candidates, on the same machine, with one thread. The revision labels the implementation and scope of every MUVERA number.

Both methods score the same saved MUVERA candidates. We use 100 queries per corpus, K=5 and safety margin M=5. Both methods run on one thread in the same compiled CPU kernel. Col-Bandit reads candidates straight from the corpus arrays, with no copying per query, and its remaining candidates are rescored with the same scorer as the baseline. Overlap@5 is agreement with Full-MaxSim on these candidates. It is not recall over the corpus.

CandidatesαSciDocsArguAnaQuora (523K)
2000.31.50× / .9961.79× / 1.0001.73× / .982
1,0000.32.52× / .9903.07× / .9943.20× / .976
2000.21.95× / .9782.34× / .9761.80× / .960
1,0000.23.54× / .9564.36× / .9623.50× / .944

Each cell gives speedup over full scoring / Overlap@5, on MUVERA candidates.

At these sizes, α=0.2 is faster than α=0.3 and has lower overlap. We did not split the gain into pruning and fixed overhead. Col-Bandit is slower at 25 candidates in all six runs and at 50 candidates in five of them (ArguAna at α=0.2 gives 1.14× at 50). It is faster at every size of 100 or more in the table. Timings leave out query work, candidate generation and preparing the candidate IDs. The candidate lists are newly generated and are not the exact lists of the submitted experiment.

On the PLAID side, screening computes 80.2, 67.6, 51.6 and 41.1% of the cells at 100, 200, 500 and 1,000 candidates, which gives scoring ratios of 1.13, 1.42, 1.95 and 2.39×. MUVERA candidates allow real pruning. Screening computes 16.4 to 82.5% of the cells across both α settings and all six sizes. In our runs, Col-Bandit is faster at every size of 100 candidates or more, on both PLAID and MUVERA candidates.

Our U8TN Q5 reply gives the measured stage shares.

AuthorsOpenReview ↗

(3/3) Tuned LEMUR: the gain grows with the candidate budget

W1: "The large speedups highlighted in…"

Q1: "At matched retrieval quality, how…"

We agree that real systems first use an index to cut the candidate set. Col-Bandit does not compete with that index. It replaces the exhaustive scoring step that LEMUR, PLAID and MUVERA run on their candidates. LEMUR's small candidate sets come from its trained index. Col-Bandit needs no index and no training. Its only preparation is one linear pass over the embeddings. So we test it on the same candidates, with nearly the same output in less time, and the gain is limited by that step's share of the total time.

After tuning, the answer depends on the candidate budget the pipeline needs. At every budget Col-Bandit's quality stays within noise of exact scoring. The two systems are close at 100 to 250 candidates, and Col-Bandit's speedup grows with the budget, up to 1.3 to 2.1× at 1,000 to 2,000.

We swept candidate budgets k′ of 100, 250, 500, 1,000 and 2,000 on SciDocs and ArguAna, at K=5 and K=10, with α of 0.2, 0.3 and 0.5. Both systems share LEMUR's candidate generation and rerank the same candidates at each k′. Only the rerank step differs. The baseline is LEMUR's own AVX-512 reranker, which is at least as fast as our exhaustive kernel on the same candidates. So the gain comes from skipping work, not from a faster kernel. Each run uses 100 queries, with timing on 95 queries after five warmups and one thread per reranker. Cost is LEMUR's candidate generation spread over the queries, plus the rerank of each query. Baseline times are pooled across runs, because α changes only Col-Bandit. At α=0.2, Col-Bandit's Recall@K stays within 0.01 of exact scoring at every budget.

The table gives LEMUR time divided by Col-Bandit time, at α=0.2.

Settingk′=1002505001,0002,000
SciDocs, K=50.91×0.91×1.21×1.45×1.76×
ArguAna, K=51.02×1.21×1.48×1.79×2.10×
SciDocs, K=100.72×0.80×1.00×1.28×1.57×
ArguAna, K=100.80×0.97×1.21×1.54×1.85×

The paper's 1.5 to 2.0× is the large-budget end of this curve. Which end a pipeline sits on depends on its first stage. A trained index like LEMUR's reaches its recall with few candidates, so its scoring step is small. A pipeline without that training needs more candidates, and LEMUR's own documentation notes that skipping its encoder training needs 2 to 4 times more. That is where Col-Bandit helps most.

The two methods also aim at different goals. LEMUR is built for throughput. Its paper runs "on all 40 cores, parallelizing over queries" and reports queries per second, and its reranker scores the candidates of one query on one thread. Col-Bandit is built for the latency of a single query. It splits that query's documents across threads. Our comparison uses one thread per query.

Configurations are chosen on the evaluation queries, with no held out tuning set.

We hope these results address your questions, and we would be grateful if they could be reflected in your assessment.

Reviewer_U8TNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper accelerates late-interaction reranking by treating the MaxSim matrix H∈RN×TH \in \mathbb{R}^{N \times T}, with Hi,t=max⁡j⟨qt,edi,j⟩H_{i,t} = \max_{j} \langle q_t, e_{d_i,j} \rangle and document score Si=∑t=1THi,tS_i = \sum_{t=1}^{T} H_{i,t}, as a finite-population top-KK identification problem. Each round reveals B=4B=4 query-token columns for the active documents, following one random permutation of [T][T] shared by all documents. Each document keeps an interval [LCB(i),UCB(i)][\mathrm{LCB}(i), \mathrm{UCB}(i)]: an empirical Bernstein–Serfling radius scaled by αef\alpha_{ef}, intersected with hard support bounds. A document is dropped once UCB(i)<τr\mathrm{UCB}(i) \lt \tau_r, where τr\tau_r is the (K+M)(K+M)-th largest lower bound; survivors are rescored exactly. The paper states a conditional guarantee Pr⁡(T^K=TK⋆)≥1−δ\Pr(\hat{T}_K = T_K^{\star}) \ge 1-\delta at αef=1\alpha_{ef}=1 and deploys αef=0.2\alpha_{ef}=0.2 as a calibrated heuristic.

Experiments use five BEIR corpora (up to NQ, N=2.68N = 2.68M) and four REAL-MM-RAG corpora with ColBERTv2, Jina-ColBERTv2 and Granite Vision Embedding. The paper reports computing 13–22% of cells at Overlap@5 ≥0.90\ge 0.90, mean single-thread CPU speedups of 7.0×7.0\times (EPYC) and 12.9×12.9\times (M1) over exhaustive MaxSim, and composition results with PLAID, LEMUR and MUVERA.

Critical strengths
  1. Simple, training-free, drop-in idea with careful engineering. The fused SIMD kernel, the no-elimination control (bookkeeping within 1.3–4.4% of Full-MaxSim) and the static token-ordering ablation together make a convincing case that the cell savings come from adaptive elimination, not from kernel differences.
  2. Broad evaluation (three encoders, text and multimodal, KK sensitivity, full αef\alpha_{ef} sweep), with the regimes where the method loses (small candidate sets, MUVERA) reported rather than hidden.
Critical weaknesses
  1. The headline speedups come from an unrealistic regime. The 7×7\times / 12.9×12.9\times numbers are for exhaustive MaxSim over the entire corpus on one CPU thread. Deployed late-interaction systems rerank candidates from PLAID, WARP or MUVERA. With real PLAID candidates (Table 22) the speedup is 0.790.79–0.88×0.88\times at Kann=25K_{ann}=25, 1.041.04–1.32×1.32\times at Kann=100K_{ann}=100, and 1.81.8–3.2×3.2\times at Kann=1000K_{ann}=1000, with Ov@5 of only 0.94–0.96. With MUVERA candidates the rerank becomes slower (0.4 → 7.3 ms on SciDocs, R=200R=200). An unfused PyTorch dense MaxSim on an A100 already beats 16-thread Col-Bandit on every corpus that fits in memory (Table 25). The practical contribution is much smaller than the abstract suggests.
  2. The theory does not cover the evaluated method. Theorem 1 assumes that the implemented radius is a valid confidence radius, and Remark 2 admits it is not, because the additive O(1/n)O(1/n) range term is dropped. The guarantee therefore rests on an unverified premise. The deployed αef=0.2\alpha_{ef}=0.2, which also eliminates on int8 estimates, has no guarantee at all and is in effect a tuned pruning threshold that changes up to 8% of the exhaustive top-5 (HotpotQA, Ov@5 =0.92= 0.92). No held-out protocol for choosing αef\alpha_{ef} is described. The algorithm (successive elimination with Bernstein–Serfling bounds) is standard and close to BanditMIPS, so the "first" claims should be toned down.
Questions for authors
  1. With the O(1/n)O(1/n) term restored at αef=1\alpha_{ef}=1 (a valid guarantee), what are the coverage and wall-clock speedup? If they are near 1×1\times, the guarantee adds little in practice. (Affects soundness.)
  2. On which corpora and queries was αef=0.2\alpha_{ef}=0.2 selected? Were any test corpora involved? (Affects the "transfers without tuning" claim.)
  3. Is the permutation π\pi redrawn per query, or does the fixed seed give every query the same π\pi? In the latter case, what is the probability in Theorem 1 taken over? (Clarification.)
  4. How does Col-Bandit compare with deterministic safe pruning that uses per-document or centroid upper bounds (WAND-style), and with a fused GPU MaxSim kernel? The current baselines (Doc-Uniform, ball-carving) are weak. (Affects assessment.)
  5. In an end-to-end PLAID or WARP pipeline at standard settings, what fraction of query latency is the rerank stage? (Affects significance.)
7 comments
AuthorsOpenReview ↗

(1/3) What the full corpus runs measure, and candidate set results

Thank you for the careful review. We agree that the paper needs clearer limits on its theory and deployment claims. We now separate the variant with a valid bound from the fast approximation, we disclose how α was chosen, and we report stage costs and tuned baseline comparisons. All new results and clarifications below go into the revised paper.

W1: "The headline speedups come from…"

We agree. The full corpus runs measure the scoring step, not a whole retrieval system. The revision presents them as a controlled scoring experiment and puts the candidate set results at the center. Col-Bandit is not a retrieval system. It replaces the exhaustive scoring step that PLAID, MUVERA and LEMUR run on their candidates. Our Uhoq W1/Q1 reply lists the bounded settings where exhaustive scoring is used. The paper is not limited to one thread. Threads split the documents of one query, so each number at more threads is the latency of a single query. Figure 1 and Table 17 show 8 and 16 threads. At 8 threads Col-Bandit stays 2.4 to 6.2× faster at K=5 (mean 4.6×) and 2.5 to 7.5× at K=100 (mean 4.4×). NQ drops from 4.5 s to 0.71 s per query.

Col-Bandit now scores MUVERA candidates 1.50 to 3.20× faster than full scoring at α=0.3, with Overlap@5 .974 to 1.000. At the deployed α=0.2 it is 1.80 to 4.36× faster, with Overlap@5 .944 to .978. Both hold for 200 to 1,000 candidates. The speed ratio grows from 200 to 500 to 1,000 candidates.

The paper's SciDocs number of 0.4→7.3 ms came from an early implementation, and we should not have used it for MUVERA candidates on a CPU. We measured both methods again on the same candidates, on the same machine, with one thread. The revision labels the implementation and scope of every MUVERA number.

Both methods score the same saved MUVERA candidates. We use 100 queries per corpus, K=5 and safety margin M=5. Both methods run on one thread in the same compiled CPU kernel. Col-Bandit reads candidates straight from the corpus arrays, with no copying per query, and its remaining candidates are rescored with the same scorer as the baseline. Overlap@5 is agreement with Full-MaxSim on these candidates. It is not recall over the corpus.

CandidatesαSciDocsArguAnaQuora (523K)
2000.31.50× / .9961.79× / 1.0001.73× / .982
1,0000.32.52× / .9903.07× / .9943.20× / .976
2000.21.95× / .9782.34× / .9761.80× / .960
1,0000.23.54× / .9564.36× / .9623.50× / .944

Each cell gives speedup over full scoring / Overlap@5, on MUVERA candidates.

At these sizes, α=0.2 is faster than α=0.3 and has lower overlap. Col-Bandit is slower at 25 candidates in all six runs and at 50 candidates in five of them (ArguAna at α=0.2 gives 1.14× at 50). It is faster at every size of 100 or more in the table. Timings leave out query work, candidate generation and preparing the candidate IDs.

For PLAID, rescoring aligned with the reference raises overlap to .974 to 1.000. Scoring time goes up by 0.43 to 26.51% across settings, and by at most 5.37% for 500 or more candidates. On the same saved candidate sets, no query and budget gets a worse overlap. At 1,000 candidates the aligned version keeps 1.84 to 3.05× scoring speedups. Timings leave out input preparation. The revision adds a labeled comparison next to Table 22 and keeps the submitted numbers.

AuthorsOpenReview ↗

(2/3) The complete bound, and how α was chosen

W2: "The theory does not cover…"

Q1: "With the O(1/n) term restored…"

We restored the term and timed it in our CPU kernel. With the complete bound, Col-Bandit runs at 0.65 to 1.03× the speed of exhaustive scoring. With the simplified radius it runs at 1.66 to 2.19×. The simplified radius has no established δ-PAC guarantee, also at α=1.

The reason is simple. The restored term is always wider than the paper's hard bounds (§4.1), so the hard bounds make every decision. After n of T cells, the hard bounds limit a document's score to an interval of width (T−n)R, and the estimate lies inside it. The restored term alone is T·κ·R·log(10NT/δ)/n, with κ = 7/3 + 3/√2 and R = 2 (cosine range [−1,1]). Since n(T−n) ≤ T²/4, this term is at least (T−n)R whenever T ≤ 4κ·log(10NT/δ). That holds up to T ≈ 185 even for N=1 at δ=0.01, and our queries have at most 112 tokens. So the complete bound gives exactly the run with the hard bounds alone, and screening ends up computing most of the cells.

The protocol uses 50 timed queries per corpus, K=5, M=5, δ=0.01, one thread, and the same kernel and machine.

CorpusNRadius, α=1Cells computedOv@5Speedup
SciDocs25,657Complete93.4%1.0001.03×
Simplified58.9%1.0001.66×
ArguAna8,674Complete96.3%1.0000.91×
Simplified57.7%1.0001.77×
Quora522,931Complete87.2%1.0000.65×
Simplified24.4%0.9962.19ׇ

Speedup is exhaustive scoring time divided by Col-Bandit time on the same queries. Below 1× means Col-Bandit is slower.

‡On Quora the simplified run gives 24.4% / 0.996 here vs 27.7% / 1.000 in the paper.

Theorem 1 holds only if the intervals are valid, and the deployed α=0.2 is an empirical setting. In practice, at α=1 the simplified intervals missed the true score in 0.15 to 1.45% of checks over 2,400 queries on six corpora, yet no true top-5 document was lost. These are fixed samples, not a calibrated failure rate.

On your point that α=0.2 changes up to 8% of the exhaustive top-5, the change is small in task terms. Against the qrels in our K=100 experiment, nDCG@10 moves by at most 0.0072 on all nine corpora and MAP@100 by at most 0.0012 (our Uhoq W7 reply). On int8 estimates, int8 only picks candidate tokens, and every cell value in the bounds is computed in fp32. Running the whole elimination loop in fp32 leaves Overlap@5 unchanged on SciDocs and within 0.7 points on HotpotQA-500K (Appendix D.11).

In the revision, the complete bound and this argument go next to Eq. 5, Theorem 1 is stated as conditional, and every number is labeled with its operating point.

We will also narrow the "first" claims. BanditMIPS has its own high probability guarantee for MIPS and top-k. It samples scalar coordinates with replacement, at O(1) cost per pull. Our structured MaxSim cells cost O(L_d·d) per pull and are sampled without replacement. Its sub-Gaussian interval does not shrink to zero, while our simplified radius does at full reveal. These are differences between related methods, not reasons to dismiss BanditMIPS.

Q2: "On which corpora and queries…"

We chose one global α=0.2 from development sweeps on our evaluation corpora (SciDocs, ArguAna, Quora, NQ, HotpotQA, FinSlides and TechReport), with no held out protocol. A leave one corpus out check after the fact picks the same α=0.2 in all nine folds at an Overlap@5 target of 0.95. We will remove any suggestion that the choice was independent of the evaluation data.

The check uses K=5. In each fold we pick the smallest α whose mean Overlap@5 over the other eight corpora reaches the threshold, and apply it unchanged to the held out corpus.

Held out corpusThreshold ≥0.95: α chosenHeld out Overlap@5Threshold ≥0.96: α chosenHeld out Overlap@5
ArguAna0.2.9800.31.000
SciDocs0.2.9600.3.988
Quora0.2.9400.2.940
NQ0.2.9480.2.948
HotpotQA0.2.9240.2.924
FinReport0.2.9840.3.996
FinSlides0.2.9640.3.984
TechReport0.2.9560.3.976
TechSlides0.2.9760.3.980

At the 0.95 threshold, all nine folds pick α=0.2. HotpotQA's .924 matches the paper's rounded 0.92. At 0.96, six folds pick 0.3 and three pick 0.2.

What the paper calls transfer is that one value behaves the same way on every corpus. It gives Overlap@5 of 0.92 or more at 13 to 21% of the cells, across all nine corpora and both modalities (Table 2). The revision states this meaning clearly and adds the leave one corpus out check above.

These checks support the paper's guidance of 0.2 for speed and 0.3 for extra fidelity.

AuthorsOpenReview ↗

(3/3) Permutation, safe pruning, and stage costs

Q3: "Is the permutation π redrawn…"

Theorem 1 is a statement about one query. Its probability is over one uniform random permutation of the query tokens, drawn independently of the score matrix and shared by all documents. In the deployed build, every query of the same length uses the same permutation (fixed seed 42). So the theorem's probability applies to each query on its own, not independently across queries. We will state this clearly.

The paper's seed table shows how much the choice of permutation matters. Across seeds, Overlap@5 varies with a standard deviation of 0.5 to 3.4 points (median 1.3). This shows sensitivity to the seed, not correctness for a given seed.

Q4: "How does Col-Bandit compare with…"

We tested deterministic safe pruning with per-document bounds. On dense embeddings it keeps almost all of the work. Each document stores the max and min of each embedding dimension over its tokens, which bounds every cell. With these bounds, WAND-style document-at-a-time scoring still scores 100% of the documents, and round-based safe elimination computes 88 to 96% of the cells (ArguAna, SciDocs, FinSlides, TechReport, 100 queries each, K=5, exact top-5 every time). Col-Bandit at α=0.2 computes 13 to 21%. The bounds are loose because each document's tokens spread over the whole range of every dimension.

The global and per-token caps behave the same way. As shown in W2/Q1, the restored interval never tightens the global cap, so the complete bound runs at only 0.65 to 1.03× of exhaustive scoring.

The paper's fixed token orderings (uniform, query norm, IDF and uniCOIL) need about 40% coverage to reach Overlap@5 of 0.74 to 0.98, while Col-Bandit reaches 0.92 to 0.97 at 13 to 15%. At matched coverage the best of them trails by 8 to 46 points (§5).

We have not tested centroid bounds, which need an index. On a fused GPU kernel, Col-Bandit is a CPU method, and our Uhoq Q2 reply explains why a GPU version is a separate systems problem, not a direct port.

Q5: "In an end-to-end PLAID or…"

In PLAID the rerank stage is a small part of the time. In LEMUR it is most of the time, and there Col-Bandit makes the pipeline faster.

For PLAID at K_ann=1000 in our setup, reranking is about 18% of the measured stage time (stage 1 takes about 96 ms per query). WARP has no exhaustive rerank stage for Col-Bandit to replace.

For LEMUR, the compiled AVX-512 reranker takes 86 to 98% of the measured time at 500, 1,000 and 2,000 candidates, with one thread per reranker. This timing is a batched first stage spread over the queries plus a per query rerank, not an online single query latency. In the paper's fixed budget LEMUR experiment, Col-Bandit makes the pipeline 1.5 to 2.0× faster at 1,000 and 2,000 candidates. After tuning, Col-Bandit's gain grows with the candidate budget, up to 1.3 to 2.1× at 1,000 to 2,000 candidates (our Ukpj W1/Q1 reply).

We hope these results address your concerns, and we would be grateful if they could be reflected in your assessment.

Reviewer_UhoqOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The authors present a query-time top-K pruning algorithm for late-interaction retrievers called ColBandit. They posit that the full MaxSim matrix, N x T (N documents, T query tokens), need not be computed exhaustively. Instead, they observe that most documents can be eliminated from top-K contention after revealing a few cells per row (which would contribute to the row-sum). ColBandit casts this as a fixed-confidence top-K identification problem over a finite population, and executes batched progressive elimination.

This elimination process chooses a shared uniform random permutation π\pi of [T] to determine the reveal order. Each round reveals the next B=4 cells for every surviving document in one pass. Every surviving document gets a confidence interval built from the intersection of deterministic support bounds and the empirical Bernstein-Serfling radius. Any document whose upper confidence bound falls below the largest lower confidence bound is eliminated. They provide a calibration parameter αef\alpha_{ef} which enables a δ\delta-PAC guarantee (Theorem 1).

ColBandit is tested on nine corpora - five from the BEIR benchmark and four from the REAL-MM-RAG multimodal benchmark - with three late interaction encoders. At the deployed αef=0.2,M=5,δ=0.01,K=5\alpha_{ef} =0.2, M=5, \delta=0.01, K=5, Col-Bandit reports preserving Overlap@5 ≥ 0.90 on every corpus at 13%–22% MaxSim cell coverage, delivering mean single-thread CPU speedups of 7.0× on AVX2 (EPYC 7763) and 12.9× on NEON (M1 Max) against Full-MaxSim applied to the entire corpus.

Critical strengths
  1. The CB-NK fused kernel is a good systems contribution. The authors compare against the Rust SIMD baseline (maxsim-cpu) and beat it by 11x on the x86 architecture. They provide a two-phase int8-coarse to fp32-refine pipeline alongwith a cache-separated memory layout, register tiling and cross instruction set architecture porting.

  2. Casting top-K identification as bandit exploration, while confining to finite population seems novel in the scope of such late interaction retrieval methods. Using Bernstein-Serfling to get a radius that collapses deterministically to zero at full reveal is interesting, and does not suffer the “asymptotic” issue.

Critical weaknesses
  1. One of the many issues I have with this paper is that its headline speedup is measured against a non-standard baseline. ColBandit’s 7x - 12.9x advertised speedup is against exhaustive MaxSim scoring, applied to the whole corpus, for a max N of 2.68M corpus items. This is not a comparison that typically appears in late interaction IR papers. The original ColBERT paper, for example, introduces FAISS index based filtering (as a first-stage retriever) specifically to avoid exhaustive scoring. Subsequent methods in the same family or adjacent to it - ColBERTv2, PLAID, MUVERA, LEMUR, WARP - preserve this two-stage structure. The paper shows in its “composition” experiments (Table 22) that at a realistic, post-PLAID budget set of {100, 200, 500, 1000}, the speedup is somewhere between 1x to 3.2x, which is far more modest.

  2. Following on from the first point, Appendix C.1 describes the main-text setup as “full-corpus reranking regime where the candidate set is the entire corpus”. This is not what reranking typically means in IR literature. It wouldn’t be called a “rerank” if we were exhaustively scoring over the entire corpus, rather than a filtered candidate set received from a first-stage retriever. What the paper calls “full-corpus reranking” is first-stage exact/exhaustive retrieval. The abstract calls the key contribution a “drop-in reranking layer”, which makes it sound like it should be applied on top of a first-stage retriever. If deployed as a true reranker over PLAID candidates, the N it operates on is 100–1000, not the 8K–2.68M that justifies the headline speedup.

  3. Theorem 1 does not really cover the advertised operating point. The PAC guarantee is available only if αef=1\alpha_{ef} = 1. The headline numbers are provided at αef=0.2\alpha_{ef} = 0.2, shrinking the radius 5x. At 1, Table 19 states that the speedup is around ~1.5-5.1x.

  4. For T=32 (ColBERTv2) or T=64 (Jina-ColBERTv2), the “finite population” is extremely small, and the Bernstein–Serfling radius’s collapse at n → T does not buy us much in terms of statistical power. What it does provide is an early-stopping mechanism as most documents are eliminated after B=4 cell reveals. But even then, T=32 or 64 is quite low. I understand that the algorithm rests on N (and therefore N x T) being large, but that is already an issue.

  5. GPU comparisons are relegated to the appendix. If MaxSim scoring is the bottleneck, I imagine the first (naive) solution one would think of is to compute batched document vs query token MaxSims on the GPU. Appendix D.13 acknowledges “on GPU, dense batching is efficient enough that fine-grained per-round elimination does not pay” and defers fused GPU Col-Bandit to future work.

  6. I expected larger corpora in the experiments. The max N size here is 2.68M, and even HotpotQA has been downsized to 500K. BEIR provides HotpotQA (5.2M), Fever (5.4M) and MSMARCO (8.8M) for large scale experiments, and for a paper whose major contribution is approximating full-corpus MaxSim, the corpus size comes up short. Another benchmark that could have been used (and has been used in earlier work) is the LoTTe benchmark. That being said, given the fundamental misunderstandings in points 1 and 2, I don’t think experimenting on these datasets would help at this juncture.

  7. Standard IR metrics (nDCG, Recall, MRR) are reported mostly in Appendix D with limited coverage in the main text. The issue is that these results are framed as retention against exhaustive Full-MaxSim scores, not as absolute scores against ground-truth qrels. The latter is the IR community standard and is what enables comparison against the broader BEIR leaderboard. I was expecting a Pareto style plot of time taken vs standard IR metric which is not present in this paper. Also, MAP is a standard metric on the BEIR benchmark and it is absent altogether from this paper.

On the flipside, arguing in favour of the paper, one regime I imagine ColBandit could have been useful in is that of single-shot multi-hop RAG on modest CPU-only deployments. This regime might benefit from ColBandit’s ability to maintain high Overlap@100 at ~4.7× speedup on 500K-scale corpora. However, modern multi-hop RAG pipelines (IRCoT, Self-Ask, ReAct, HippoRAG) address the recall problem through iterative retrieval and query decomposition rather than K-scaling, which the field has moved on from. At K=1000, Table 23 already shows ColBandit speedup degrading to 1.6×.

Questions for authors
  1. What is the deployment case for exhaustive full-corpus Full-MaxSim as a baseline? Which production late-interaction system corresponds to this regime?
  2. What is the fused-GPU-kernel speedup when Col-Bandit is implemented on GPU and compared against FLASH-MAXSIM?
  3. What is the composition speedup against WARP, TACHIOM, SSR end-to-end, at matched quality?
  4. What is the Overlap@K at αef=1\alpha_{ef}=1 across all nine corpora at K=5, and what is the corresponding wall-clock speedup?
6 comments
AuthorsOpenReview ↗

(1/3) Where exhaustive scoring is used, and terminology

Thank you for the careful review. The new results answer your main points. We restored the complete bound and measured its cost, Col-Bandit is now 1.50 to 3.20× faster on MUVERA candidates, and we added absolute IR metrics for all nine corpora. We also agree on two points, and the revision says them clearly. The full corpus runs measure the scoring step, not a whole retrieval system, and the guarantee covers the complete bound, not the fast setting. All new results and clarifications below go into the revised paper.

As you note, Col-Bandit is 11× faster than maxsim-cpu on x86.

W1: "…its headline speedup is measured against…"

Q1: "What is the deployment case…"

Col-Bandit is not a retrieval system. It replaces one step, scoring every document in a given set to find the top K. PLAID, MUVERA and LEMUR use an index to pick candidates. Then each of them scores every candidate in full. Col-Bandit replaces that last step. The full corpus run is the largest case of the same step. It measures how much scoring work top-K selection can skip when there is no candidate generator. It is a controlled measurement. We do not suggest scanning millions of documents in production.

Exhaustive scoring does have bounded uses in practice.

First, small collections where an index does not pay off. Vespa shows it on sets of about 1K document pages (blog.vespa.ai/scaling-colpali-to-billions). Mixedbread's maxsim-cpu targets CPU scoring of up to about 1,000 documents (mixedbread.com/blog/maxsim-cpu). Visual document collections fit here. Each page has hundreds of patch vectors, so a few thousand pages is already a heavy scoring job. On our four visual corpora (1.7K to 2.7K pages each), Col-Bandit scores 21% of the cells on average, at Overlap@5 0.97.

Second, data with no index yet. Col-Bandit needs no training and no clustering. Its only preparation is one linear pass over the embeddings, about 1.5 seconds per million token slots (Appendix F.3). PLAID needs clustering and LEMUR needs per corpus training before the first query can run.

Third, second stage reranking of 1,000 or more candidates from BM25 or a single vector index. This is the reranking setup of the original ColBERT paper. Qdrant documents this pattern too, with brute-force MaxSim after a dense first stage (qdrant.tech/documentation/tutorials-search-engineering/using-multivector-representations). Current PLAID tooling scores thousands of candidates at this step. PyLate's (https://github.com/lightonai/pylate) PLAID index computes full scores for 8,192 candidates by default, and FastPlaid for 4,096. Our ArguAna and SciDocs corpora (8.7K and 25.7K documents) are at this size and just above, and there Col-Bandit is 6.3 to 6.4× faster at one thread (Table 2).

Fourth, filtered search. A metadata filter (a user, a date range, a product) often leaves too few documents for an index to work well, so systems score every document that passes it. Weaviate, for example, switches to brute-force search when a filter becomes too restrictive (docs.weaviate.io/weaviate/concepts/filtering). Scoring 10K to 500K filtered documents is the same computation as our full corpus runs at those sizes (Table 2 covers 8.7K to 523K documents, at 4.7 to 7.4× with one thread).

Where the claim stops. For large indexed corpora, exhaustive scoring is not a sensible design. Our 2.68M NQ run is a stress test of scoring cost, not a deployment proposal.

Our practical evidence is the candidate set work. For PLAID, the smaller Table 22 gains are the relevant ones. The new MUVERA results are 1.50 to 3.20× faster at Overlap@5 .974 to 1.000 (α=0.3, 200 to 1,000 candidates, see our Ukpj Q2 reply). For LEMUR, the result depends on the recall target, as our Ukpj W1/Q1 reply shows.

W2: "Following on from the first…"

You are right. We will replace "full-corpus reranking" with "exhaustive full corpus scoring" and remove the word "standard". We will use "drop-in reranking layer" only for candidate sets of 100 to several thousand documents.

AuthorsOpenReview ↗

(2/3) Pipelines, the complete bound, and α=1 on nine corpora

Q3: "What is the composition speedup…"

We have not run end to end tests at matched quality against TACHIOM or SSR. Col-Bandit replaces one step, scoring a given candidate set, so our test inside a pipeline is the same candidates in, nearly the same top-K out, in less time. A whole-system comparison would also measure each system's first stage and its index. TACHIOM and SSR build an index before the first query (clustering, compression or training), and their small candidate sets come from that work. Col-Bandit needs no index and no training. Its only preparation is one linear pass over the embeddings. Without an index, the candidate set is the whole collection, which is the setting of our full corpus runs. Our evidence covers the scoring stage of PLAID, the timed parts of MUVERA (candidate preparation excluded) and LEMUR's first stage plus rerank timing.

WARP fills in missing similarities in the XTR style. It has no exhaustive candidate scoring stage for Col-Bandit to replace. We will fix §2, which wrongly listed WARP among the systems that score every kept candidate exhaustively.

W3: "Theorem 1 does not really…"

We restored the term and timed it in our CPU kernel. With the complete bound, Col-Bandit runs at 0.65 to 1.03× the speed of exhaustive scoring. With the simplified radius it runs at 1.66 to 2.19×. The simplified radius has no established δ-PAC guarantee, also at α=1.

The reason is simple. The restored term is always wider than the paper's hard bounds (§4.1), so the hard bounds make every decision. After n of T cells, the hard bounds limit a document's score to an interval of width (T−n)R, and the estimate lies inside it. The restored term alone is T·κ·R·log(10NT/δ)/n, with κ = 7/3 + 3/√2 and R = 2 (cosine range [−1,1]). Since n(T−n) ≤ T²/4, this term is at least (T−n)R whenever T ≤ 4κ·log(10NT/δ). That holds up to T ≈ 185 even for N=1 at δ=0.01, and our queries have at most 112 tokens. So the complete bound gives exactly the run with the hard bounds alone, and screening ends up computing most of the cells.

The protocol uses 50 timed queries per corpus, K=5, M=5, δ=0.01, one thread, and the same kernel and machine.

CorpusNRadius, α=1Cells computedOv@5Speedup
SciDocs25,657Complete93.4%1.0001.03×
Simplified58.9%1.0001.66×
ArguAna8,674Complete96.3%1.0000.91×
Simplified57.7%1.0001.77×
Quora522,931Complete87.2%1.0000.65×
Simplified24.4%0.9962.19ׇ

Speedup is exhaustive scoring time divided by Col-Bandit time on the same queries. Below 1× means Col-Bandit is slower.

‡On Quora the simplified run gives 24.4% / 0.996 here vs 27.7% / 1.000 in the paper.

Theorem 1 holds only if the intervals are valid, and the deployed α=0.2 is an empirical setting. In practice, at α=1 the simplified intervals missed the true score in 0.15 to 1.45% of checks over 2,400 queries on six corpora, yet no true top-5 document was lost. These are fixed samples, not a calibrated failure rate.

We hope this addresses the concern about soundness. The revision separates what is proven from what is measured. The complete bound is valid and its cost is reported, the fast setting is presented as an empirical approximation, and every number states its operating point.

Q4: "What is the Overlap@K at…"

The paper's α=1 table (Table 20, Appendix D.8) already lists all nine corpora at K=5. Overlap@5 is 0.98 to 1.00 and single thread speedups are 1.53 to 5.10×. For example, NQ gives 5.1× at Overlap@5 0.996. This radius has no established δ-PAC guarantee.

AuthorsOpenReview ↗

(3/3) Short queries, GPU, scale, IR metrics, and multi-hop RAG

W4: "For T=32 (ColBERTv2) or T=64…"

Part of this is right. With B=4 and T=32, the first round already reads 12.5% of the cells. NQ, Quora and HotpotQA (13 to 14%, Table 2) sit close to this floor, because most documents leave after the first round.

But a small T works for us, not against us. For a fixed number of reveals n, a smaller T gives a larger finite population reduction of the variance term. At T=32, the factor √ρ_n cuts that term by 12%, 19%, 27%, 37%, 49% and 64% after 8, 12, 16, 20, 24 and 28 reveals. If the population were large, say T=10,000, the same reveals would cut it by less than 0.2%. So the finite population effect is strongest exactly at small T.

The later rounds also matter, and they are cheap. In the paper's one traced SciDocs query, round 1 leaves 2,705 of 25,657 documents. Rounds 2 to 8 bring that set down to 10 documents and add only 2.05 percentage points of cell coverage, not counting the final rescoring. Scoring all 2,705 of those documents in full would have added 9.2 points (2,705 × 28 of 821,024 cells).

A larger T does not hurt much either. With the T=64 encoder, coverage on the four shared corpora rises only from 13.7% to 18.5%, with similar fidelity (Appendix D.14).

These savings come from the simplified rule, which has no established δ-PAC guarantee (see W3).

W5: "GPU comparisons are relegated to…"

We agree. Appendix D.13 already shows that dense GPU batching makes round by round elimination unhelpful. On a GPU with T=32, a fused kernel would read each document from memory once, and Col-Bandit also reads each document in its first round, so skipping cells would save little memory traffic. Our contribution is on the CPU side. A fused GPU Col-Bandit is future work.

Q2: "What is the fused-GPU-kernel speedup…"

Col-Bandit is a CPU method. We have no GPU version yet, so we cannot give this number. We agree it is the natural next step, and the paper names it as future work (Appendix A and Appendix D.13).

It is also a hard systems problem, not just a port. FLASH-MAXSIM is fast because it is IO-aware (and needs no padding for documents of different lengths). It loads each document tile from HBM once, keeps it in on-chip memory (shared memory and registers), scores all query tokens against it there, and drops it. There are no HBM round trips. Col-Bandit works in rounds. It scores a few query tokens, removes documents, and comes back to the survivors. A direct GPU port would read the survivors from HBM again in every round, which is exactly the cost a fused kernel exists to avoid. A good GPU Col-Bandit has to make its elimination decision inside the kernel, while the document is still on chip, and handle survivor sets that shrink unevenly across thread blocks. We see this as the most interesting open direction for this work.

W6: "I expected larger corpora in…"

We agree that larger corpora alone would not answer the main concern. The nine corpus analysis includes NQ at 2.68M passages, with an 8.5× scoring speedup. It shows the scoring cost at scale, as W1 explains.

W7: "Standard IR metrics (nDCG, Recall…"

We added absolute nDCG@10, MAP@100 and Recall@100 against the qrels for all nine corpora, at K=100, one thread, 50 query subsets. At α=0.2, scoring on the five text corpora is 3.7 to 8.5× faster (a new 50 query run, so it differs a little from Table 2). nDCG@10 is unchanged on 5 of 9 corpora and moves by at most 0.0072 anywhere. MAP@100 stays within ±0.0012.

The nDCG changes include SciDocs +0.0002, Quora +0.002, NQ +0.007 and FinReport −0.007. We do not read the increases as real gains. Recall@100 changes on four corpora, NQ 0.96→0.94, ArguAna 0.86→0.84, SciDocs 0.388→0.384 and FinReport 0.98→1.00. It is unchanged on the others. On NQ (2.68M passages) one query takes 39.5 s→4.7 s (8.5×), with nDCG@10 0.495→0.502.

These are 50 query subsets of our evaluation corpora, not BEIR leaderboard numbers. Both methods run under the same conditions.

We will add the nine panel quality versus time figure and move the absolute metrics into the main text.

Flipside: "However, modern multi-hop RAG pipelines…"

We agree, and we will not present K=1000 single shot retrieval as the answer to multi-hop RAG. Multi-hop retrieval actually favors fast small K scoring. These pipelines run several retrieval steps one after another inside the LLM loop, each with a small K, so the scoring time of every step adds to the answer time. This is the K=5 setting where Col-Bandit saves the most.

One reading note on Table 23. Its K is the K of Top-K, the number of results returned, not the number of candidates. On ArguAna, K=1000 is 11.5% of the whole corpus. The same row shows 2.7× on SciDocs and 5.5× on HotpotQA.

We hope these results address your concerns, and we would be grateful if they could be reflected in your assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.