- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies efficient visual document retrieval with late-interaction models. It proposes CellCert, a method to reduce the MaxSim computation of late-interaction models, while keeping the exact same ordered top-k results as exhaustive scoring. The motivation is that approximate methods can maintain similar or even higher retrieval metrics but can change the retrieved pages, which may be less favorable in specific use cases.
The paper proposes a technique, adaptive cellwise certification. In visual late-interaction models, a "cell" represents the maximum similarity between one query token and the patches of one page. The method first uses deterministic Euclidean k-means to group the patch vectors within each page, and uses mean and radius of these groups to compute lower and upper bounds for each cell. Then, these bounds are combined to obtain page-level bounds. In the refinement phase, the method first defines admissible criteria for groups, and then selects cells to perform exact computation based on their bound widths and estimated computation costs. Through the method section (section 3), the proofs and calculations seem to be solid.
Using frozen ColSmol-256M embeddings, the paper evaluates CellCert on five ViDoRe datasets (including Pharmaceuticals as an untouched test set). It compares the results with page-level certification and approximate retrieval methods. Results show that CellCert preserves exact ordered results for all evaluated queries at k = 1, 5, and 10, and reduces FMA by at least 49.9% across all evaluated settings, with a query-weighted average of 55.4% at k = 5. Moreover, cell-level refinement reduces FMA operations compared with page-level certification
However, despite the FMA reduction, the current implementation is much slower than Flash-MaxSim, with GPU-resident latency around 60 times higher (e.g. 11.45 ms for CellCert, vs 0.191 ms for Flash-MaxSim) on the two development datasets: Economics and Biomedical. It also requires additional storage for the group summaries. The authors discuss possible implementation improvements, but these have not been tested.
Critical strengths
The paper shows convincing evidence that FMA operations can be reduced without changing the original ranking.
Results show that CellCert preserves exact ordered results for all evaluated queries at k = 1, 5, and 10, and reduces FMA by at least 49.9% across all evaluated settings, with a query-weighted average of 55.4% at k = 5. Moreover, cell-level refinement reduces FMA operations compared with page-level certification
As a further bonus that may be helpful in certain cases, the method preserves the exact ranking produced by exhaustive MaxSim scoring across all evaluated queries.
Critical weaknesses
1. Substantial runtime latency overhead
I understand that the motivation of building a search algorithm like this is to attaining higher efficiency than an exhaustive scoring (while maintaining the same performance). However, depiste achieving a significant reduction in the FMA proxy, the current implementation is much slower than Flash-MaxSim, with GPU-resident latency around 60 times higher (e.g. 11.45 ms for CellCert, vs 0.191 ms for Flash-MaxSim) on the two development datasets: Economics and Biomedical. The pinned-host results show a similar trend.
The substantial latency overhead makes it very hard to justify a practical benefit from the method. As the authors also acknowledge, this is a (major) limitation of the work. The authors discuss future improvements but none of them are implemented and evaluated. In its current form, I see the work more as an interesting exploration, but its practical value has not yet been demonstrated.
2. Additional storage overhead further limits the efficiency trade-off.
The work also introduces nontrivial storage overhead. The auxiliary summaries require an additional 36.7–47.7% of the FP16 token index size, while the original pacth index must still be persisted for exact fallback. That comes as another layer of additional cost which weakens the effiency trade-off contribution of the work.
Questions for authors
On motivation for exact ranking preservation: the paper mentions downstream pipelines and regression tests as use cases, but I am not fully convinced that this is a strong practical motivation.
Is there any real-world example where changing the top-k ranking would significantly impact downstream performance? Or, any example where preserving top-k ranking brings a clear benefit? Further, how would these trade-offs justify the additional cost of latency and storage?
2 comments
Thanks for the authors' response. I acknowledge the reduction in computation achieved by this method, but my concerns are on the more practical side.
First, the method adds complexity but does not reduce latency (it remains lower than Dense FP32 GEMM and Flash-MaxSim, and is only faster than the authors' own same-scorer exhaustive implementation).
Second, a major claim of this method is that it reduces computation without changing the ranking. The authors have further strengthened the "not changing the ranking" aspect, which I already acknowledged. My question is: why maintain a ranking that is not necessarily better? Could the authors provide some practical, real-world examples where maintaining the exact ranking is necessary?
Thank you for recognizing the arithmetic reduction and asking what ranking preservation adds in practice. We tested a stronger fixed shortlist, examined a concrete retrieval regression, ran a downstream QA pilot, and measured the updated executor.
1. Concrete value of adaptive refinement
CellCert targets the requirement that an optimized retrieval procedure preserve a specified scorer's ordered output. This matters when evidence identity and order form part of an output contract, such as retrieval regression testing, without assuming that the reference scorer always gives better answers.
Using the same frozen C=384 geometric lower bounds, we selected 32 pages and reranked them with the original FP32 reference scorer. Ordered top-5 agreement across all original queries was:
CellCert recovered the reference ranking in all 39/39 shortlist32 failures, replayed under the common historical FP32 evaluation. Budgets of 64 and 128 still leave nine and two ranking differences, respectively. This demonstrates the role of adaptive refinement beyond fixed budgets.
For the Industrial query, "Explain the components and design of the AFTF," shortlist32 lowers nDCG@5 by 0.2375; restoring the reference ranking recovers that loss. This is a concrete benchmark retrieval benefit, not a demonstrated generated-answer failure. The overall query-weighted mean nDCG@5 difference is about -0.00030, and ranking changes can leave relevance unchanged or improve it. We therefore motivate exactness through preserving required individual outputs.
2. Downstream QA evidence
We tested 16 fixed Pharmaceuticals questions using Qwen3.5-4B, greedy decoding, and the first 650 tokens of each of five retrieved page transcripts. Gold answers were withheld from the generator. Conditions were exhaustive retrieval, a scorer-matched Col-Bandit rule replay at alpha=0.2, and C=384 shortlist32.
After nine exhaustive-context outputs reached the initial 128-token cap, we repeated every question/method at 512 tokens, with no outputs reaching the cap. Mean token F1 was 0.25053/0.25146/0.25053 for exhaustive/replay/shortlist32. Only one replay context and answer differed, with slightly higher lexical F1. This small text-only pilot does not establish a downstream QA advantage; the demonstrated benefit is retrieval-output preservation and the query-level example above.
3. Implemented improvements and measured costs
We implemented a shared fixed-reduction FP32 scorer for exhaustive scoring, refinement, and rescoring. Current GPU-resident synchronized wall-time medians (ms) are:
Measurements use one RTX 5090, eight fixed queries/domain, three interleaved repetitions, and CUDA Graphs for every method. Medians are taken first within each query, then across queries. Setup/compilation are excluded; required host readbacks are included. These are new measurements; GEMM and Flash use different numerical contracts.
CellCert reduces latency against exhaustive execution of the same scorer on four of five domains. Optimized GEMM and Flash remain faster. Summaries add 36.7-47.7% to the FP16 patch-index size, with original patches retained. Thus, the evidence supports arithmetic savings and output preservation, rather than a general serving-cost advantage. Shortlist32 also retains the C=384 summaries, so that comparison isolates adaptive refinement, not summary-storage removal.
4. Scope of the contribution
The updated executor matches its exhaustive reference on 1,174/1,174 original queries and 96/96 stress configurations at k=5. Stress configurations comprise 48 synthetic inputs under two summary precisions; all real-query rankings also match the historical cache. This new numerical reference can differ from earlier reductions on near-ties. The theorem remains conditional on conservative intervals and aggregation.
The original experiments establish a query-weighted 55.4% reduction in the k=5 FMA proxy; the new shortlist study identifies cases where adaptive refinement preserves outputs that fixed budgets change. We will center the contribution on these results and report runtime, storage, and downstream quality separately.