acceptodds
Under review as a conference paper at ICLR 2027

Exact, Batch-Invariant and Fast Test-Time Query Optimization for Late-Interaction Retrieval

Abstract

Test-time query optimization (TTO) refines a query embedding by gradient steps against a frozen candidate pool and lets compact multi-vector retrievers rival much larger ones. With late interaction, every step rescans every vector of every candidate, and how these scans are executed changes the result: TF32 tensor cores change maxima and selected vectors, and library matrix products change their bits with the batch a request is served in. We present ExactTTO, which makes TTO exact, that is, bitwise identical to a fixed FP32 reference, batch-invariant and fast by letting approximation decide only which products are computed, never their values, and fixing the order of all other arithmetic. Certified working sets skip rescans that provably cannot change the result. Tensor cores only filter candidates, whose FP32 maxima and selected vectors are recomputed exactly. A fused loop applies each step's gradient and Adam update in one kernel with a fixed operation order, so a query's trajectory does not depend on the requests it is batched with. Under the official protocol of Guided Query Refinement (GQR) on fourteen ViDoRe splits and four BEIR datasets, we recover GQR's gains. In batches of 64 requests, ExactTTO processes 3.05× as many queries per second as GQR's FP32 scorer in our fused loop and 3.95× as many as FLASH-MaxSim in FP32, and gives every query the bits it gets when served alone, which GQR's scorer does for 80.4% of the queries; a single ColNomic refinement runs 21× faster than GQR's released eager loop, mostly by removing framework overhead. ExactTTO also accelerates a second objective, distilling a cross-encoder into ColBERTv2 queries, which raises nDCG@10 on BEIR from 37.1 to 41.5.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Information Retrieval, Late Interaction, Test-Time Optimization, Query Refinement, Batch Invariance, Reproducibility, Tensor Cores, MaxSim

Reviews

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

This paper addresses reproducibility issues in test-time query optimization (TTO) for late-interaction retrieval, where processing the same query individually or in a batch can produce bit-level differences in scores, selected vectors, gradients, and final optimization results. The authors attribute these discrepancies to batch-shape-dependent matrix multiplication kernels, TF32/BF16 tensor-core arithmetic, and nondeterministic accumulation in backpropagation. They propose ExactTTO, built on three components: certified working sets, tensor-core exact maximum computation, and a document-major fused loop with batch-invariant execution. Experiments on 14 ViDoRe splits and four BEIR datasets reproduce GQR's gains, achieving 3.05× the throughput of the GQR FP32 scorer and 3.95× that of FLASH-MaxSim FP32 at batch size 64, while matching 57.6M maximum values bit-for-bit against a dense reference and achieving 0.0% batch-induced query variation.

Critical strengths
  1. Well-motivated and practically relevant problem. Batch invariance is an important but underexplored issue in retrieval-time optimization. The reported discrepancies are substantial: at batch size 64, 19.6% of queries produce different final scores with the GQR scorer, and in controlled batches of 16, all but 6 of 192 queries change their final scores in the autograd loop.

  2. A coherent and principled design. The principle that approximation should determine which products to compute, but never their values unifies the three components into a consistent exactness framework. Theoretical bounds, including the FP32 gap-radius test and the tensor-core accumulation analysis, strengthen the technical rigor.

  3. Strong correctness validation and practical gains. The paper reports zero bit-level discrepancies across 57.6M maximum values, batch invariance in all 960 comparisons, and agreement with the released GQR loop on top-5 results for 7,688 test queries. The throughput gains are substantial, and the ReFIT distillation results further demonstrate that the approach is not limited to GQR.

Critical weaknesses
  1. Single-request performance regression is insufficiently addressed. The paper should provide a latency breakdown for certification, verification, working-set refresh, and updates, and discuss whether certification for iteration (t+1) can overlap with the Adam update at iteration (t).

  2. Batch invariance and tensor-core exactness have different portability guarantees. Proposition 2's batch invariance rests on a fixed execution order and fixed reduction trees that do not depend on the batch shape, while exactness against the dense twin additionally requires the FP32 FMA routine and the tensor-core accumulation bound (Theorem 4), whose numerical constant is established via an A100-specific bit-accurate model.

Questions for authors

What accounts for the single-request latency overhead, and can the certification and refresh costs be reduced or overlapped with optimization updates?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Yv3P

(Current numbers: see Update 3.)

Thank you for two concrete suggestions. We followed up on both.

W1 / Q. Single-request latency: where does the time go, and can it be reduced? We profiled the graph replays of the fused loop for the first four test queries of every combination, served alone, recording every kernel (new Table 27 and Appendix K). With the batched launch, a single request is latency-bound. With pools of at most 20 documents the phases launch (medians) 15 thread blocks for the certificate test and for merging, 120 for refreshes and 2 for FP32 verification. Verification alone takes 39% of the exact dense operator's replay time (median), because every FP32 recomputation is one sequential chain of h fused multiply-adds.

So we added a single-request launch configuration that spreads the same computations over more thread blocks. Verification gives each (page, token) pair its own warp with coalesced loads, refresh splits a page into up to 32 parts and keeps candidates by warp-wide selection, and merges reduce across a warp. No product changes its multiply-add order, and maxima and selected vectors are fixed by (value, index), so the results are bitwise identical; we checked every served test query of all 44 combinations, alone and in batches of 16 and 64. A step of the exact dense operator now takes 35 µs instead of 75 µs (GQR's scorer: 36 µs), and over the 44 A100 combinations single-request throughput goes from 0.49× to 1.03× that of GQR's scorer. Where the replay time goes now (medians):

  • exact dense operator: tensor-core filter 25%, FP32 verification 13%, fallback scans 30%, merge 11%, update 18%;
  • certified operator: certificate test 25%, refresh 39%, merge 16%, update 10%;
  • GQR's scorer: matrix product 47%, max reduction 23%, update 28%.

Each kernel now takes a few microseconds; fusing kernels could cut the remaining launch costs.

Overlap. The certificate test of a token at step t+1 needs that token's displacement from the Adam update of step t. The dependency is therefore per token, and across tokens or thread blocks the test could overlap with other updates, for instance inside a fused update kernel. Before building that kernel we bounded what it could gain: subtract the certificate-test kernels' recorded time (25%) and keep all other kernels unchanged. Even with a free test, a certified step would take 48 µs (median) against 35 µs for the exact dense operator, and it would be faster on only 11 of 44 combinations. Picking the faster operator per combination would raise single-request throughput by 1.03× (geometric mean; at most 1.59×). Given that bound we did not build the fused kernel, and ExactTTO serves single requests with the exact dense operator. With every input update paid for in a persistent graph (Table 24), single requests in this configuration run at 0.96× GQR's scorer, and batches amortize the remaining costs (2.14× at B=64).

W2. Portability of batch invariance versus tensor-core exactness. Agreed, and Section 6.5 (Portability) now says so. By portability we mean that each guarantee holds on each GPU separately. Bitwise equality across GPU models would also need identical compiled arithmetic, so we report it below as an observation on two GPUs, not as a guarantee. Proposition 2 holds on any GPU for scorers whose outputs for a query depend only on its own tokens and documents, which our operators ensure through fixed thread layouts and summation orders. Exactness of the FP32 operators needs binary32 fused multiply-adds with round-to-nearest and no overflow or underflow. Only the tensor-core operators add a hardware assumption, the accumulation bound of Theorem 4. On the A100 we now measure the accumulation error on both tensor-core paths (1.3 billion products for the Triton filter and 1.3 billion for the WMMA refresh; largest error 24× below our γ′\gamma'). We also reran all tensor-core and exactness experiments on an H20, a Hopper GPU with compute capability 9.0 like the H100, using the same kernel sources, inputs and operating points (Appendix L). On both tensor-core paths the largest error is 1.6×10^-6 of the summed magnitudes, 38× below our γ′\gamma' (A100: 24×). The lockstep audit (8.6 million maxima) and the tie and near-tie tests (9.1 million comparisons) find no differing bit. Every exact operator returns the same bits on the H20 as on the A100 for every query it serves, whereas FLASH-MaxSim's TF32 path agrees across the two GPUs on 0 queries. On the H20, the single-request launch configuration raises single-request throughput from 0.45× to 0.86× GQR's scorer (A100: 1.03×), with the A100's bits on all 2,782 served test queries. We have no Blackwell GPU, so that case is untested. On any other GPU the bound has to be re-established before the tensor-core operators are enabled. An audit gives empirical support, not a proof, so tensor-core exactness stays conditional on the bound, while the FP32 operators remain exact and batch-invariant without it.

AuthorsOpenReview ↗

Follow-up before the discussion deadline

Thank you for your constructive review. Before the discussion closes on November 18 (AoE), we would like to ask whether our response addresses your two points: single-request latency, including what overlapping the certificate test with the update could save, and the separate portability guarantees of batch invariance and tensor-core exactness, which the revised paper now distinguishes and which we also checked on an H20. We are happy to clarify anything further, and if the response resolves your concerns, we would be grateful if you would consider reflecting this in your assessment.

Thank you for the response. Given that I have already provided a positive assessment, I will maintain my positive score unchanged.

Thank you for reading our response and for your positive assessment. Your suggestions on single-request latency and on separating the two portability guarantees made the paper clearer and stronger. If any point would still benefit from clarification, we are happy to provide it before the discussion closes.

Reviewer_v1FAOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes ExactTTO, an executor for test-time query optimization (GQR, ReFIT) over late-interaction retrievers with sd(q)=1N∑i=1Nmax⁡j⟨qi,vdj⟩s_d(q) = \frac{1}{N} \sum_{i=1}^{N} \max_j \langle q_i, v_{dj} \rangle. Its goal is to be bitwise identical to a fixed-order FP32 reference and independent of batching. The principle is that approximation decides only which products are computed, never their values. It has three components:

  1. Certified working sets: a token–document pair skips its rescan while mdi>Rdj⋆∥Δqi∥2m_{di} \gt R_{dj^{\star}} \lVert \Delta q_i \rVert_2, with an FP32-rigorous version (Thm. 2) and a refresh bound K≤1+Li/ρminK \le 1 + L_i / \rho_{min} in terms of path length (Thm. 3).
  2. Tensor cores as a filter: a two-term BF16 split q=qhi+qlo+rq = q^{hi} + q^{lo} + r with ∣rk∣≤2−16∣qk∣\lvert r_k \rvert \le 2^{-16} \lvert q_k \rvert, a rigorous error bound, and FP32 recomputation of surviving candidates (Thm. 4).
  3. A fused, fixed-order kernel for the gradient and Adam step, giving batch invariance (Prop. 2).

Under GQR's protocol (14 ViDoRe splits, 4 BEIR datasets) the paper reproduces GQR's gains. At B=64B=64 it reports 3.05×3.05\times the throughput of GQR's FP32 scorer and 3.95×3.95\times that of FLASH-MaxSim FP32 with bit-identical results, and 21×21\times over GQR's released eager loop for one request. Audits find no bit differences over 57.6M maxima and 9.1M adversarial near-tie comparisons.

Critical strengths
  1. Technically rigorous. The floating-point analysis (guarded certificate, tensor-core error bound, binary32 Adam bound) is careful, and exactness is backed by large lockstep audits and adversarial tie and near-tie tests. The principle "approximation chooses the work, not the values" is clean and could be reused elsewhere.
  2. Honest about where it loses: at B=1B=1 GQR's own scorer is faster, FLASH-MaxSim's TF32 path is 1.50×1.50\times faster, and certification saves little at large step sizes.
Critical weaknesses
  1. The value of bitwise exactness is not demonstrated in this setting. By the paper's own measurements, batching changes the final scores of 19.6% of queries but never their top-5; TF32 changes the top-5 of 0.9% of queries with no significant change in nDCG@5 (p≥0.17p \ge 0.17); and two FP32 loops already differ by up to 12.1% with almost no effect on quality. No concrete use case (auditing, caching, regression testing, serving consistency) is shown where these differences change a decision. Without one, exactness is a cost rather than a benefit.
  2. The speed claims rest on narrow baselines and a niche workload. The 21×21\times headline is measured against an eager PyTorch loop and, as the paper says, mostly removes framework overhead; in the same fused loop at B=1B=1, ExactTTO runs at only 0.450.45–0.58×0.58\times the speed of GQR's scorer. The batched 3.05×3.05\times is measured against FP32 einsum and FLASH FP32, not against simpler routes to batch invariance (batch-invariant matmul kernels, fixed-shape padding, or TF32 plus an FP32 recheck). Certified working sets, the main theoretical piece, save little at GQR's operating points (80.6% of documents refreshed with the official padded ColNomic queries, 84.5% at η=10−3\eta = 10^{-3}), and the dense operator is selected in 29 of 44 configurations. Timings exclude query encoding (a 7B encoder) and first-stage retrieval, so the end-to-end effect of saving under 1 ms is unknown. Results come from a single GPU (A100), and Theorem 4 relies on an assumed tensor-core accumulation bound (γ′≤6.1×10−5\gamma' \le 6.1 \times 10^{-5}), not a hardware specification. The ReFIT gain (37.1 → 41.5 nDCG@10) belongs to ReFIT's objective and should not be presented as a contribution. Overall this is a numerics/systems paper about one niche procedure, so its fit with ICLR is limited.
Questions for authors
  1. Can you show an application where batch-dependent bits in TTO change an outcome (a cache hit, an audit, an A/B comparison) and quantify it? (Central to significance.)
  2. How does ExactTTO compare with a batch-invariant baseline built from existing batch-invariant kernels, or with TF32 plus FP32 recheck without certification? (Affects the novelty and speed claims.)
  3. What is the end-to-end per-query latency including query encoding and first-stage retrieval, and what share does the TTO loop take? (Affects significance.)
  4. Does the γ′\gamma' assumption behind Theorem 4 hold on H100 or Blackwell tensor cores, and what happens if it does not? (Affects soundness and generality.)
  5. Your reproduced GQR gain with Linq on ViDoRe v2 is +4.9 versus +2.5 reported. What explains the gap? (Clarification.)
7 comments
AuthorsOpenReview ↗

Response to Reviewer v1FA (1/2)

(Current numbers: see Update 3.)

Thank you for the careful review. Your questions made us measure several things we had only argued before.

Q1. Does batch dependence ever change an outcome? Yes, once the refined query is used again. You are right that under GQR's protocol batching never changed the top-5 of a 10 to 20 document pool in our measurements (19.6% of the queries change their final scores, none with another top-5). In ReFIT, however, the refined query retrieves again from the full corpus. New Section 6.3 and Table 2 measure this on 2,045 BEIR test queries, scoring refined queries against the full corpus in FP64 so that any difference comes from TTO alone.

  • Audit and replay. With GQR's autograd loop, a request served in a random batch of 64 and replayed alone gets back the same refined query for 0 of 2,045 queries, and a different top-100 for 2.1%. With ExactTTO every replay is bitwise identical. The same check decides whether a cached result can stand in for a recomputation (not measured).
  • Moving to a faster kernel. FLASH-MaxSim FP32 is batch-invariant here, so it supports replay, but it cannot move to its own fast path without changing results. Its TF32 path reorders the top-100 for 81.6% of the queries (23.3% get different documents) and the top-10 for 6.8%, while nDCG@10 changes for only 8 queries. An output comparison finds these changes; only a quality evaluation can say whether they are acceptable. Even two FP32 kernels disagree (FLASH-MaxSim FP32 against the reference: top-100 of 40 queries). ExactTTO's FP32, tensor-core and certified operators, in both launch configurations, are bitwise identical, so its per-shape switches are verified by a plain bitwise comparison.
  • Regression tests. Batching alone moves the autograd loop's refined queries by up to 2.2% in relative norm, so a per-query test needs a tolerance. With each dataset's tolerance set to the smallest value that never fires on the batching changes we measured, the test misses 9.0% of the queries changed by a different Adam epsilon (1e-7, the TensorFlow default) and 28.5% of those changed by one missing step, although the missing step changes the top-100 of every query. With ExactTTO the tolerance is zero and every changed query is flagged. To be fair to the baseline, a whole-set test still detects both, and a zero-tolerance per-query test works for the autograd loop if its reference reruns exactly the production batch (100.0% flagged). That requires logging each batch's composition, order and kernels; with ExactTTO a single replay is enough (Appendix I).

Q2. Batch-invariant kernels, fixed-shape padding, TF32 plus FP32 recheck. All three are in new Table 3: same fused loop, inputs and operating points, all 44 combinations.

  • Batch-invariant matrix products. Thinking Machines' kernels cover single products, so we applied them per query, and we wrote a batched batch-invariant product in Triton. In IEEE FP32 both reproduce the reference on all 2,782 test queries. At B=64 ExactTTO has 10.2× the throughput of the per-query kernels and 5.69× that of the batched product with fixed 32x64x32 tiles. Tuning the batched product's tiles, warps and pipeline stages per shape (48 configurations) brings this to 2.45× (1.91× at B=16, 1.48× for single requests). Tuning keeps the bits, since no configuration changes a dot product's summation order. A fused variant that never materializes the scores is slower (10.3×). In TF32 the batched product is as fast as ExactTTO at B=64 (0.97×) and our fastest tuned TF32 kernel is 2.18× faster, but neither matches the reference on any query.
  • Fixed-shape padding. Padding every batch to 64 queries before GQR's einsum is batch-invariant and here also equals the reference, but it is 3.10× slower than ExactTTO at B=64 and 55.4× slower for single requests.
  • TF32 plus a conservative bound plus FP32 recheck. We built it as our exact dense operator with a different filter: one TF32 product, with the bound derived as for γ′\gamma' but with the query's representation error 2−102^{-10} instead of our split's 2−162^{-16}. It is exact on all 2,782 queries. But its bound is 12× wider, so 11.4% of token–document pairs fall back to a full FP32 scan instead of 3.1%, and ExactTTO has 1.80× its throughput at B=64 (1.14× for single requests). On the A100, one TF32 product takes as many tensor-core cycles as our two BF16 products.

Your other points. We removed the 21× figure from the abstract, since it mostly measures framework overhead. Single requests, which our batched kernels left mostly idle (Table 27), now get their own launch configuration with identical bits: 1.03× GQR's scorer instead of 0.49× (Appendix K). We also quantify that certification contributes little at GQR's operating points (median 0.88× over the dense operator at B=64, faster on 20 of 44 combinations; the per-dataset choice adds 1.14×), and the contributions are reordered accordingly.

(continued below)

AuthorsOpenReview ↗

Response to Reviewer v1FA (2/2)

(Current numbers: see Update 3.)

(continued)

Q3. End-to-end latency. New Table 26 times the connected pipeline on one A100: the encoders' live output feeds first-stage retrieval, TTO in a persistent graph (with all input updates) and the final ranking, timed end to end. A second pass, synchronized at stage boundaries, gives the breakdown. For a single ColNomic request the total is 81.7 ms with ExactTTO and 81.8 ms with GQR's scorer in our loop. Query encoding with ColNomic-7B and Qwen3-Embedding-4B takes 78.5 ms, the first stage 0.96 ms, and TTO with ExactTTO 1.84 ms (2.2%). GQR's released eager loop alone would take 30.5 ms (Table 25). At B=64 the amortized time per ColNomic query is 6.99 ms with ExactTTO and 8.19 ms with GQR's scorer. So, as your question suggests, once TTO runs in a fused loop it is a small part of a request. ExactTTO's advantage over GQR's scorer is batched throughput; for single requests the two pipelines are within 0.2% of each other. The two exact operators returned identical bits on all 7,021 requests of this experiment.

Q4. Theorem 4 on other GPUs. We now separate the guarantees (Section 6.5).

  • Batch invariance (Prop. 2) holds on any GPU for scorers that meet its hypothesis (each query's outputs depend only on its own tokens and documents). Our operators meet it through fixed thread layouts and summation orders, and it does not depend on the tensor-core bound.
  • Exactness of the FP32 operators (dense twin, certified scoring with FP32 refreshes) needs binary32 fused multiply-adds with round-to-nearest and no overflow or underflow.
  • Only the tensor-core operators rely on the accumulation bound.

On the A100 we measured the accumulation error on both tensor-core paths: over 1.3 billion products for the Triton filter and 1.3 billion for the WMMA refresh, the largest error is 2.5×10^-6 of the summed magnitudes, 24× below our γ′\gamma'. A measurement shows the margin on our data; it cannot prove the bound for all inputs. We also reran all tensor-core and exactness experiments on an H20, a Hopper GPU with compute capability 9.0 like the H100, using the same kernel sources, inputs and operating points (Appendix L). On both tensor-core paths the largest error is 1.6×10^-6 of the summed magnitudes, 38× below our γ′\gamma' (A100: 24×). The lockstep audit (8.6 million maxima) and the tie and near-tie tests (9.1 million comparisons) find no differing bit. Every exact operator returns the same bits on the H20 as on the A100 for every query it serves, whereas FLASH-MaxSim's TF32 path agrees across the two GPUs on 0 queries. On the H20, the single-request launch configuration raises single-request throughput from 0.45× to 0.86× GQR's scorer (A100: 1.03×), with the A100's bits on all 2,782 served test queries. We have no Blackwell GPU, so that case is untested. If the bound failed on some GPU, a tensor-core operator could return a wrong maximum. So on new hardware we check γ′\gamma' against measurements (or a bit-accurate model with a safety factor) and run the lockstep audit before enabling tensor cores; until then ExactTTO runs its FP32 operators, which stay exact and batch-invariant. This is empirical support, and the tensor-core path's exactness remains conditional on γ′\gamma'.

Q5. The Linq gain on ViDoRe v2 (+4.9 against +2.5). Mostly page text. Linq reads the text of each page; GQR extracted it with Docling and we used RapidOCR, which is the one known difference between the two pipelines. We converted all four ViDoRe v2 splits with Docling 2.94.0 (the version GQR pins) using GQR's conversion code, encoded the text with Linq and reran the same grid, rebuilding each union pool from Linq's new top-10 as GQR's protocol does. Our runs on OCR text reproduce our table exactly. With Docling text the gain is +3.2 (95% CI [+2.1, +4.3]) instead of +4.9, and the interval contains GQR's +2.5. Most of the change comes from ESG-human, where Docling text lowers Linq alone from 66.4 to 56.4 nDCG@5 and the gain from +5.6 to +0.9. On ESG, Linq alone goes from 58.8 to 46.6 and the gain from +8.2 to +6.8. With GQR's zero-padded queries the gain is +3.4 (95% CI [+2.5, +4.3]). Some difference remains: with Docling text Linq alone averages 52.6 against the 55.3 GQR reports, and ESG still has the largest gain in the clean-query control (+6.8). GQR reports only the ViDoRe v2 average, so without its extracted text we cannot localize the rest. The main tables keep OCR text; Table 10 in Appendix E reports the control.

ReFIT and fit. Agreed on ReFIT: the gain belongs to ReFIT's objective, and the paper now presents it only as a check that the exact executor reproduces it. On fit, our contribution is a systems one: an executor that keeps TTO on a fixed FP32 reference while improving batched throughput. We also think the principle that approximation decides which products are computed, never their values, carries over to other test-time procedures built on max or argmax structure.

AuthorsOpenReview ↗

Follow-up to Reviewer v1FA: certification and the TF32 path

Update (Nov 16). Superseded by our follow-up below: FLASH-MaxSim's TF32 path is no longer faster at B=16 (ExactTTO reaches 1.07× its throughput).

Our new general comment ("Update: faster exact operators, same guarantees") revises both exact operators; the guarantees are unchanged. For your two speed points:

  • Certification now pays off at most of GQR's operating points. At B=64 the certified operator is faster than the exact dense one in 32 of 44 combinations (submitted version: 19), with median ratio 1.31, and it refreshes a median 39% of the documents per call. It still loses where steps are large, as on ColBERTv2.
  • At B=64, ExactTTO now has 1.21× the throughput of FLASH-MaxSim's TF32 path, which was 1.50× faster than the submitted version, and 4.46× that of the tuned batch-invariant FP32 product. At B=16 the TF32 path is still slightly faster (ExactTTO reaches 0.93× of its throughput), and a fused TF32 maximum with tuned tiles stays ahead at B=64; neither matches the FP32 reference on any query. Section 6.4 reports both.
Reviewer_dNGnOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the exact and batch-invariant test-time query optimization (TTO) for late-interaction retrieval. The floating-point execution details can otherwise change MaxSim selections and optimization trajectories. The authors propose ExactTTO, combining certified working sets, tensor-core candidate filtering with FP32 verification, and a fixed-order fused optimization loop. The experiments evaluate the correctness, retrieval quality, and throughput on ViDoRe and BEIR.

Critical strengths
  • The paper gives an exactness argument. Proposition 1 and Theorems 1-3 establish why certified working sets preserve MaxSim values, selected indices, gradients, and trajectories, while Theorem 4 makes the tensor-core path safe through filter-and-refine verification.

  • The experimental validation is effective. Table 15 shows that ExactTTO returns the same bits for every tested query when served alone or at batch size 64, while GQR’s FP32 scorer does so for only 80.4% of queries. Figure 2 and Tables 2, 7, and 16 show the throughput gains and their dependence on batching, pool size, and step size.

Critical weaknesses
  • The writing is not clear and verbose. For example, the experimental results are overly in detail reported in Abstract. I suppose a GPT writing paper.

  • A few related works are missing, such as Col-Bandit: Query-Time Top-K Estimation for Late-Interaction Retrieval, 2026. I suppose that the authors should discuss this work.

Questions for authors
  • Compared with FLASH-MaxSim, which is already batch-invariant in the reported experiments, what practical benefit does bitwise agreement with the specified FP32 reference provide?

  • How much of the throughput advantage remains after accounting for input updates and graph reuse for new requests?

  • At the selected operating points, what is the distribution of gains from working-set certification relative to the exact dense operator?

4 comments
AuthorsOpenReview ↗

Response to Reviewer dNGn

(Current numbers: see Update 3.)

Thank you for the review and for pointing us to Col-Bandit.

Writing. We agree; the abstract listed too many results. The revised abstract is about a quarter shorter, keeps the problem, the principle and the main result, and has fewer numbers. We also tightened the introduction and reordered the contributions.

Col-Bandit. It is now discussed in the related work. Col-Bandit estimates the top-K of one MaxSim call by revealing some entries and pruning candidates with confidence bounds, trading tunable fidelity for compute. TTO needs something different: the exact maxima and selected vectors of every document in the pool, at each of the T+1 calls, because the gradient flows through them. Our certificates skip work between the calls of an optimization loop, and they are deterministic and exact in FP32. The two ideas fit together: Col-Bandit could pick the first-stage pool, and ExactTTO would refine the query over it.

Q1. FLASH-MaxSim is already batch-invariant. What does bitwise agreement with the FP32 reference add? Batch invariance makes one kernel's output independent of the batch. It does not make two kernels agree, and that is where a shared reference matters. We now measure three consequences (Section 6.3, Table 2):

  • ExactTTO switches operators by request shape (exact dense or certified, tensor cores or FP32) and never changes a result by doing so. FLASH-MaxSim cannot switch to its own faster path that way. Relative to its FP32 path, its TF32 path reorders the full-corpus top-100 for 81.6% of refined ReFIT queries and the top-10 for 6.8%; for 23.3% of queries different documents enter the top-100. nDCG@10 changes for only 8 queries, so the switch may well be acceptable. But an output comparison can only show that results changed; whether the change is acceptable takes a quality evaluation.
  • FLASH-MaxSim's FP32 path is itself a different FP32 computation from the reference. Its refined queries differ in their bits for every query, and the top-100 changes for 40 of 2,045 queries. An offline audit with another FP32 kernel, such as our dense twin, therefore cannot reproduce its outputs bit for bit.
  • At B=64, FLASH-MaxSim in FP32 is 3.95× slower than ExactTTO.

Could FLASH-MaxSim's FP32 path serve as the reference instead? Any fixed FP32 computation could, as long as every operator reproduces it, and a pinned FLASH-MaxSim FP32 on its own would already support replay and zero-tolerance regression tests. We chose the order of a plain scalar loop (one fused multiply-add per term, in index order) because it does not depend on tiles or launch configuration. Our dense and certified operators, both launch configurations, the tensor-core and FP32 paths and a plain audit loop all reproduce it, and so does a batched FP32 product under each of the 48 tile configurations we tuned.

Q2. Throughput once input updates and graph reuse are counted. This is a new experiment (Section 6.4, Table 24). We capture one graph per operator, batch size and token bucket, and keep it. Each new batch is copied into static buffers, with the pool's documents and certificate data gathered from tensors precomputed once per corpus (114 ms, median). After capture, counting every input update in a serial loop, ExactTTO has 2.14× the throughput of GQR's scorer at B=64 and 1.97× at B=16 (geometric means over 44 combinations), compared with 3.05× at B=64 when graphs are only replayed. All 16,692 checks (every served test query, both exact operators, three batch sizes) match the results computed alone bit for bit. A capture costs 91 ms per shape (median) and is paid once. Single requests served this way, in the single-request launch configuration, run at 0.96× GQR's scorer (1.03× with replays only), again bitwise identical.

Q3. How the gain from certification is distributed. Over the 44 combinations at B=64, the certified tensor-core operator has 0.88× the throughput of the exact dense tensor-core operator (median; range 0.29 to 2.23; faster on 20). By retriever (geometric means): clean ColNomic 1.25×, ColPali 1.12×, ColNomic with GQR's zero-vector padding 0.71×, ColBERTv2 0.30×. For step sizes up to 1e-4 the median is 1.00×. For single requests, with both operators in the single-request launch configuration (Appendix K), the dense operator is faster on every combination (certified at 0.51×, median). Choosing between the two per dataset on development queries adds 1.14× over always using the dense one. So at GQR's operating points most of the batched speedup comes from the exact tensor-core maxima, and certification pays off when small steps meet larger pools: with 100-document pools at step size 1e-5 it refreshes 3.8% of the documents per call and is 9.19× faster than FLASH-MaxSim in FP32. Section 6.5 now says this, and the contributions are reordered to match.

If any concern about the proofs or the experiments remains, we are happy to go into it.

AuthorsOpenReview ↗

Follow-up to Reviewer dNGn: Q3 and Q2 with the revised operators

Update (Nov 16). With the kernels of our "Update 3" comment, the certified operator beats the exact dense one at B=64 in 31 of 44 combinations (median ratio 1.28), and served through persistent graphs with every input update paid, ExactTTO has 3.37× the throughput of GQR's scorer at B=64. The revised PDF has the current numbers.

Our new general comment ("Update: faster exact operators, same guarantees") revises both exact operators; exactness and batch invariance are unchanged. Updated answers:

  • Q3. At B=64, the certified operator's throughput relative to the exact dense one now has median 1.31 (submitted version: 0.88), range 0.69 to 2.85, and exceeds 1 in 32 of 44 combinations (submitted version: 19). By retriever (geometric means): 2.00× on clean ColNomic, 1.52× on ColPali, 1.08× on official ColNomic with its zero tokens, and 0.70× on ColBERTv2, whose steps are large. For η ≤ 1e-4 the median is 1.98.
  • Q2. Counting every input update for new requests in persistent graphs, ExactTTO now serves 3.24× as many queries per second as GQR's scorer at B=64 (round 1: 2.14×), and all results remain bitwise equal to those computed alone.
AuthorsOpenReview ↗

Follow-up before the discussion deadline

Thank you again for your review. As the discussion closes on November 18 (AoE), we would like to ask whether our replies and the revised PDF address your concerns: the shorter abstract and tighter writing, the discussion of Col-Bandit, what bitwise agreement with the FP32 reference adds beyond batch invariance, throughput once input updates and graph reuse are counted, and how the gains of certification are distributed. If any point remains unclear, we would be glad to clarify it. If our responses resolve your concerns, we would appreciate it if you would consider updating your assessment.

AuthorsOpenReview ↗

Final results for your three questions

To put our updates in one place: the revised PDF has a shorter abstract and discusses Col-Bandit (Section 7). On your three questions:

  • Q1: a shared FP32 reference lets ExactTTO switch operators by request shape without changing any result, whereas switching FLASH-MaxSim from FP32 to TF32 reorders the top-100 of 81.6% of refined queries (Section 6.3).
  • Q2: counting input updates, ExactTTO serves 3.37× as many queries as GQR's scorer at B=64 (Table 24).
  • Q3: certification beats the exact dense operator on 31 of 44 settings at B=64, median 1.28×, range 0.67–2.77× (Section 6.5).

Comments on the paper

4 comments
AuthorsOpenReview ↗

Summary of changes (marked in blue in the revised PDF)

Update (Nov 16). Numbers here are for the operators at the time of posting; the current numbers are in our "Update 3" comment and the revised PDF.

We thank all three reviewers. The reviews ask four main things: what bitwise exactness is worth in practice, how ExactTTO compares with simpler ways to get batch invariance, how it behaves outside our batched benchmark, and clearer writing. Here is what we added. New results are on the same A100 unless noted.

  1. What exactness buys (new Section 6.3, Table 2). We moved to a setting where the refined query is used again: under ReFIT's objective on BEIR it retrieves from the full corpus (2,045 test queries). With GQR's autograd loop, a request served in a random batch of 64 and replayed alone gets back the same refined query for 0 of 2,045 queries, and a different top-100 for 2.1%. Switching FLASH-MaxSim from FP32 to TF32 reorders the top-100 for 81.6% of queries (23.3% get different documents), while nDCG@10 changes for only 8 queries. Even FLASH-MaxSim FP32 and our FP32 reference disagree on the top-100 of 40 queries. All three exact operators reproduce the reference in every condition. We do not claim that replay or zero-tolerance regression tests need our reference; any fixed batch-invariant executor would do, a pinned FLASH-MaxSim FP32 included. What the shared reference adds is that ExactTTO can switch between its operators and launch configurations without changing a single result.
  2. Simpler routes to batch invariance (Table 3). We built them and ran them in the same fused loop on all 44 combinations. At B=64 (geometric means), ExactTTO has 10.2× the throughput of Thinking Machines' batch-invariant kernels applied per query, 3.10× that of padding every batch to a fixed shape, and 2.45× that of a batched batch-invariant FP32 product after tuning its tiles per shape (5.69× with fixed tiles). All of these FP32 routes reproduce the reference here. TF32 products are as fast or faster but match the reference on no query. TF32 filtering with a conservative bound and an FP32 recheck is exact, but its bound is 12× wider than that of our two-term BF16 filter, so 11.4% of token–document pairs fall back to a full FP32 scan instead of 3.1%, and ExactTTO is 1.80× faster at B=64.
  3. New requests (Section 6.4, Appendix J). With one persistent graph per shape and every input update paid for, ExactTTO still has 2.14× the throughput of GQR's scorer at B=64 (3.05× when graphs are only replayed). Results stay bitwise identical.
  4. End-to-end latency (Section 6.4, Table 26). We timed the connected pipeline: live encoder output, first-stage retrieval, TTO in a persistent graph and the final ranking. A single ColNomic request takes 81.7 ms with ExactTTO and 81.8 ms with GQR's scorer, and TTO is 2.2% of it. At B=64 the amortized time per ColNomic query is 6.99 ms against 8.19 ms. ExactTTO's speed advantage is a batching advantage; for single requests the two are on par.
  5. Single requests (Table 27, Appendix K). Profiling showed that our batched launch left most of the GPU idle for a single request (FP32 verification ran on 2 thread blocks). A new single-request launch configuration spreads the same arithmetic over more thread blocks, with identical bits. A step of the exact dense operator drops from 75 µs to 35 µs (GQR's scorer: 36 µs), and single-request throughput goes from 0.49× to 1.03× that of GQR's scorer.
  6. Portability (Section 6.5). The premises of each guarantee are now stated separately. Batch invariance needs only the hypothesis of Proposition 2, which our operators meet by construction on any GPU. Exactness of the FP32 operators needs binary32 FMA with round-to-nearest and no overflow or underflow. Exactness of the tensor-core operators also needs the accumulation bound of Theorem 4. We measured it on both tensor-core paths: the largest error is 24× below our γ′\gamma' on the A100 and 38× below it on an H20 (Hopper). That is a margin on our data, not a proof, so tensor-core exactness stays conditional on γ′\gamma'. On the H20 every exact operator also returns the A100's bits (Appendix L).
  7. Page text (Table 10). With Docling text for Linq, as GQR uses, on all four ViDoRe v2 splits, the gain is +3.2 (95% CI [+2.1, +4.3]), and the interval contains GQR's +2.5. Our OCR text gives +4.9. The main tables keep OCR text.
  8. Writing. The abstract is shorter and has fewer numbers. The contributions are reordered so that certification is presented as what it is: the component that pays off when small steps meet larger pools. The ReFIT gain is credited to ReFIT. The related work now covers Col-Bandit and batch-invariant kernels.
AuthorsOpenReview ↗

Update: faster exact operators, same guarantees (revised PDF, changes in a second color)

Update (Nov 16). The numbers below are from the previous kernels. With the kernels of our "Update 3" comment, ExactTTO serves 5.93× as many queries per second as GQR's scorer at B=64 and is faster than FLASH-MaxSim's TF32 path at B=16 (1.07×) as well as at B=64 (1.29×); the certified operator beats the exact dense one at B=64 in 31 of 44 combinations. The revised PDF has the current numbers.

We used the discussion period on the two speed points in the reviews. Reviewer v1FA noted that certification saves little at GQR's operating points and that FLASH-MaxSim's TF32 path is faster than ExactTTO; Reviewer dNGn asked how the gains of certification are distributed against the exact dense operator. Profiling showed that most of the remaining cost was in our kernels, not in the method. We changed two things, both within the paper's principle that approximation only decides which products are computed, never their values.

  1. Exact dense operator. The tensor-core filter now keeps the two best candidates of every token instead of one, and both are recomputed in FP32 (Theorem 4 with R=2). Near-ties between the winner and the runner-up no longer force a full FP32 scan: in a replay of the selected trajectories, the share of token–document pairs that fall back drops from 1.8% to 0.09% (median over the 44 combinations).
  2. Certified operator. The certificate has a second test (Proposition 1(b)): a pair also passes when the working set's current maximum exceeds the stored bound on every product outside it plus V·‖Δq‖. The operator computes that maximum anyway, so the test is free. It is exact in FP32 (new part (iii) of Theorem 2), and the refresh bound of Theorem 3 still holds. On the same trajectories it lowers the median share of documents refreshed per call from 54% to 41%. The kernels are also leaner: working sets are read in BF16 (exact), the reference query is stored once per query and call instead of once per pair, and a marked document is rescanned with the same tensor-core filter as in the dense operator.

Results on the same 44 combinations, frozen inputs and A100, with old and new operators timed in the same process:

  • At B=64, ExactTTO now serves 5.54× as many queries per second as GQR's FP32 scorer (old operators: 3.05×) and 1.21× as many as FLASH-MaxSim's inexact TF32 path, which was 1.50× faster than the submitted version. At B=16, the TF32 path is still ahead (ExactTTO reaches 0.93× its throughput).
  • The certified operator now beats the exact dense one at B=64 in 32 of 44 combinations (before: 19), with median ratio 1.31 (before: 0.88), range 0.69 to 2.85, and 1.98 for η ≤ 1e-4. It refreshes a median 39% of the documents per call. Large steps still favor the exact dense operator (ColBERTv2: 0.70×). The paper's rule, which times two development queries alone, picks the certified operator for only 15 of 44 combinations; timing one batch of 16 development queries instead picks it for 30 and would give 6.19× at B=64. All reported numbers keep the paper's rule.
  • The other batched comparisons were re-timed with the new operators. At B=64, ExactTTO now serves 4.46× as many queries as the tuned batch-invariant FP32 product (round 1: 2.45×) and 5.64× as many as fixed-shape padding (round 1: 3.10×). A fused TF32 maximum with tuned tiles is still 1.20× faster, and it matches the reference on no query. Served through persistent graphs with every input update paid, ExactTTO has 3.24× the throughput of GQR's scorer at B=64 (round 1: 2.14×), and all 16,692 results equal those computed alone.
  • Exactness is unchanged. In lockstep with the FP32 dense twin, each new operator returned the twin's bits on all 27.7 million token–document maxima, and every new operator keeps the bits of all 2,782 served queries at B=16 and B=64. The H20 (Hopper) results in Appendix L were obtained with the submitted operators; the new kernels have so far been checked on the A100 only.
  • Single requests are unchanged: they keep the single-request launch of the submitted dense operator (1.04× the throughput of GQR's scorer).

The revised PDF has the new test in Section 3 and Section 4, the kernels in Section 5, the new numbers in Section 6.4 and Section 6.5, and details in Appendix M; changed text is marked in a second color.

AuthorsOpenReview ↗

Addendum: the revised kernels on Hopper (H20)

Update (Nov 16). The new kernels of our "Update 3" comment were also checked on the H20: every exact operator returns the twin's bits there and the A100's final scores on all 2,782 served test queries. On the H20, ExactTTO now serves 4.46× as many queries per second as GQR's scorer at B=64 (2.01× at B=16, 0.92× for single requests).

The new kernels have now also run on the H20 (Hopper) of Appendix L, from the same sources and frozen inputs. In lockstep with the FP32 dense twin on the H20, each new operator returned the twin's bits on all 27.7 million token–document maxima, and every exact operator returns the same final scores on the H20 as on the A100 for all 2,782 served test queries at B=1, 16 and 64. On the H20, ExactTTO serves 4.65× as many queries per second as GQR's scorer at B=64 (1.86× at B=16, 0.88× for single requests). The revised PDF therefore again states that every exact operator returns identical bits on both GPUs (Section 6.5, Appendix M).

AuthorsOpenReview ↗

Update 3: faster kernels, same exact operators

We made one more pass over the kernels of the two revised exact operators. ExactTTO now has more throughput than FLASH-MaxSim's inexact TF32 path at B=16 as well as at B=64, and every exact operator still returns the FP32 dense twin's bits. Only the launch changed: every product, summation order, certificate test and fallback decision is the same as in our previous update.

  1. Reads before reductions. The verification and certify kernels now issue all reads for their token–document pairs (query rows, candidate indices, certificate fields) before reducing, instead of one query row at a time.
  2. Split fallback. A rejected pair used to be rescanned in FP32 by a single thread block. When few pairs fall back, the scan of a page is now split across thread blocks; segment maxima are merged with a 64-bit (value, index) atomic maximum, and the last block recomputes the winner's value with the same FP32 routine, so the result is bitwise the single-block result.
  3. Merged filter reductions. When the tensor-core filter updates a token's best candidates, it now pairs each value with its index in one reduction (two reductions per insertion round instead of four); candidate sets and their order are unchanged.

Results on the same 44 combinations, frozen inputs and A100, with all methods timed in the same process (geometric means):

  • At B=16, ExactTTO serves 4.53× as many queries per second as GQR's FP32 scorer and 1.07× as many as FLASH-MaxSim's TF32 path, which was still ahead at B=16 in our previous update. At B=64 the ratios are 5.93× and 1.29× (ahead of the TF32 path on 39 of 44 combinations), and 1.94× the throughput of the submitted operators.
  • ReFIT on BEIR (Section 6.6) is now timed with the revised operators: at B=64, ExactTTO runs 4.13× faster than GQR's scorer and 4.39× faster than FLASH-MaxSim in FP32. Its rankings and distillation gains are unchanged, because the bits are.
  • The other batched comparisons were re-timed with the new operators. At B=64, ExactTTO serves 4.76× as many queries as the tuned batch-invariant FP32 product and 6.03× as many as fixed-shape padding; served through persistent graphs with every input update paid, it has 3.37× the throughput of GQR's scorer, and all 16,692 results equal those computed alone. A fused TF32 maximum with tuned tiles is still 1.12× faster at B=64 and matches the reference on no query.
  • Exactness: in lockstep with the FP32 dense twin, each new operator returned the twin's bits on all 27.7 million token–document maxima, and each keeps the bits of all 2,782 served queries at B=16 and B=64. The new kernels also ran on the H20 (Hopper) of Appendix L from the same sources and frozen inputs: each new operator returned the twin's bits there on all 27.7 million maxima, and every exact operator returns the same final scores on the H20 as on the A100 for all 2,782 served test queries at B=1, 16 and 64.
  • Single requests keep the single-request launch of the submitted dense operator (1.04× the throughput of GQR's scorer).

The numbers in the revised PDF (Section 6.4, Section 6.5, Appendix M) come from these runs and replace those in our earlier updates.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.