acceptodds
Under review as a conference paper at ICLR 2027

CellCert: Exact Visual Late-Interaction Retrieval by Adaptive Cellwise Certification

Abstract

Visual late-interaction retrieval captures fine-grained page information, but exhaustive MaxSim scoring compares every query token with every page patch. Compression and shortlisting reduce this cost without guaranteeing the original ranking. Page-level exact search preserves that ranking, yet may score an entire page because only a few query-token interactions remain uncertain. We present CELLCERT, a deterministic search algorithm that refines document–query-token maxima, or cells, independently. MaxSim’s additive structure allows the search to eliminate a page without resolving all of its cells. Quantization-aware geometric summaries bound each cell; a cost-normalized policy selects cells to refine, and group bounds exclude patches that cannot attain the cell maximum. The stopping rule certifies the original ordered top-k under the declared numerical and tie contract. Across 1,174 queries from five ViDoRe domains, including an untouched Pharmaceuticals domain, CELLCERT certifies and matches exhaustive ranking in all 3,522 query/k cases for k ∈ 1, 5, 10. At k = 5, it reduces the fused multiply–accumulate (FMA) proxy by 51.4–57.9% across domains (55.4% query-weighted), and by 18.3% relative to a matched page-level certificate on Pharmaceuticals. The tested contrastive variants do not reduce work further. The current executor remains slower than fused exhaustive Flash-MaxSim: the demonstrated gain is in score-evaluation arithmetic, not wall-clock latency.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
visual document retrieval, late interaction, MaxSim, exact retrieval, certified retrieval, efficient retrieval

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_UbutOpenReview ↗
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

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:

DomainMatching queries/total
Economics58/58
Biomedical159/160
Pharmaceuticals364/364
Finance291/309
Industrial263/283
Total1,135/1,174

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:

DomainCellCertExhaustive, same scorerDense FP32 GEMMFlash-MaxSim FP16
Economics1.3170.8470.2980.154
Biomedical1.4811.6590.5200.233
Pharmaceuticals2.6733.7021.0290.392
Finance4.2076.1561.7110.576
Industrial7.78011.1403.0250.995

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.

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?

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

The paper proposes CellCert, a deterministic search algorithm for exact ordered top-k retrieval under visual late-interaction scoring. Each page's patches are grouped offline by k-means (C=384), with FP16 centroid directions, quantization error bounds, and cap cosines stored. At inference time, every document-query-token maximum gets an interval from centroid lower bounds and ball/spherical-cap upper bounds. A width-per-cost rule selects cells to resolve exactly, and within each cell only groups whose upper bound reaches the cell lower bound are scored. Search stops when the lower-bound top-k is separated from all outsiders, followed by canonical rescoring of a tie envelope. On five ViDoRe domains, the method matches exhaustive ranking in all 3,522 query/k cases and reduces an FMA proxy by 51.4-57.9% at k=5. It improves on a matched page-level certificate by 18.3% on Pharmaceuticals.

Critical strengths
  1. Clear statement with a correct proof and a controlled ablation of the core idea. The tie rule, precision, and margins are declared explicitly, and the geometric bounds and the admissible-group argument are correct. The flat direct certificate uses the same C=384 group geometry, so the reduction from 0.5946 to 0.4859 FMA ratio isolates the effect of cellwise refinement. This directly supports the central claim.

  2. Careful evaluation protocol. The untouched domain was selected by a hash rule before download, hyperparameters were frozen, robustness and untouched domains are labeled separately, bound validity is checked against materialized cell scores, and negative runtime results are reported without reframing.

Critical weaknesses
  1. The FMA reduction is not further decomposed, and the required summary scan likely dominates the remaining work. From the storage formula and the reported auxiliary storage ratio, pages appear to contain roughly 870 to 1140 patches, so the summary scan over 384 groups alone costs about 0.34 to 0.44 of exhaustive scoring, against total FMA ratios of 0.39 to 0.50.

  2. The practical benefit is not established. The executor is 14 ~ 63x slower than Flash-MaxSim, the summaries add 37% to 48% storage while the original patches must be kept, and the FMA proxy excludes scalar bound operations and memory traffic. All results use one checkpoint and corpora of at most 5244 pages, and the best group budget differs across domains. This limits the significance of the contribution.

Questions for authors
  1. What is the avg number of patches per page, and how does the FMA ratio split into summary scan, refinement, and tie rescoring?
  2. The analytic policy results in the contrastive comparison differ from the group-budget results for the same queries and C=384. Do they use different cost models?
  3. How was the floating-point guard chosen; what revalidation is needed on other hardware or kernels?
  4. What is the CellCert latency on Pharmaceuticals; what is the Flash-MaxSim latency at FP32?
1 comment

Thank you for recognizing the correctness argument and matched page-level comparison. We added the requested cost breakdown, accounting clarification, and executor measurements.

1. Patch counts and FMA decomposition

All original queries, k=5, C=384; entries are domain means normalized by exhaustive patch scoring.

DomainPatches/pageScanRefinementRescoringTotal
Economics1,076.60.35670.08470.01120.4526
Biomedical1,012.40.37930.03660.00500.4209
Pharmaceuticals870.40.44120.04250.00220.4859
Finance1,135.00.33830.08790.00170.4279
Industrial1,120.50.34270.08230.00090.4259

Refinement requires only 3.66-8.79% of exhaustive work after initialization, yielding 51.4-57.9% total arithmetic reduction. As you anticipated, the scan accounts for 79-91% of remaining work, identifying summary evaluation as the main optimization target. FMA measures useful dot-product work, excluding scalar bound operations, scheduling, masked execution, and memory traffic. Auxiliary summaries add 36.7-47.7% to the FP16 patch-index size; original patches remain available.

2. Analytic-policy accounting

The historical learned-policy comparison uses centroid-complement accounting; the final group-budget results use direct selected-group accounting. We will label these conventions explicitly rather than attribute their difference to policy quality.

Under common direct-group accounting, the complement-priority and direct policies give FMA ratios of 0.4971 and 0.4970 on the same 32 Pharmaceuticals queries at batch 256. This matched diagnostic reconciles the analytic controls; it is not a rerun of all learned policies.

3. Numerical guards and portability

The direction-quantization envelope is derived from stored direction error. The bound correction (2e-5), stopping margin (1e-5), and rescoring envelope (5e-5) are engineering safeguards validated empirically on the tested stack. The theorem requires conservative intervals and page aggregation under the declared scorer and tie rule; final rescoring cannot repair unsafe earlier elimination.

We implemented a shared fixed-reduction FP32 scorer for exhaustive evaluation, refinement, and rescoring. The updated executor matches ordered top-5 on 1,174/1,174 original queries and 96/96 stress configurations, with no observed initial bound violations. The stress set comprises 48 synthetic inputs under two summary precisions. Real-query rankings also match the historical cache. This is a new numerical reference that can differ from earlier reductions on synthetic near-ties.

Changes to hardware, compiler, precision, reduction kernel, or normalization require renewed interval and ranking checks. A formal floating-point guarantee additionally requires conservative error propagation through bounds, aggregation, and stopping. We will correct the historical CPU description: it applied the upper correction without the additional lower padding stated in the manuscript.

4. Pharmaceuticals latency and FP32 baseline

The updated CellCert executor takes 2.673 ms on Pharmaceuticals, versus 3.702 ms for exhaustive execution of the same fixed scorer, 1.029 ms for dense FP32 GEMM, and 0.392 ms for FP16 Flash-MaxSim. Thus, adaptive refinement helps within the shared scoring contract; optimized GEMM and Flash remain faster. A validated native FP32 Flash-MaxSim measurement is unavailable: dense FP32 GEMM is a separate comparator.

These are GPU-resident synchronized wall-time medians on one RTX 5090: eight fixed queries, three interleaved repetitions, CUDA Graphs for all methods, and medians first within queries then across queries. Setup/compilation are excluded; required host readbacks are included. GEMM and Flash have different numerical contracts. These updated timing samples and batching settings are separate from the original-query FMA decomposition.

5. Additional model coverage

With C=384 frozen, ColQwen2 and ColSmol-500M match their references in all 192 model/query/k cases at k=1/5/10 on the same 32 queries from a cached 286-page TAT-DQA subset. Their k=5 FMA ratios are 0.7912/0.5959; auxiliary storage is 55.0%/38.9%. These arithmetic evaluations precede the shared-scorer update and extend checkpoint coverage without retuning C.

The central controlled result remains an 18.3% work reduction over the matched page-level certificate on Pharmaceuticals, isolating the benefit of adaptive cell refinement with the same group geometry.

Reviewer_Mo9SOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents CellCert, an adaptive exact-search algorithm for visual late-interaction retrieval. Exploiting the additive structure of MaxSim scores, the authors define each document-query-token maximum similarity as a cell and maintain separate lower and upper bounds for it. The method groups patches within each page to construct geometric summaries to obtain intervals. It selects cells for refinement using interval width normalized by computational cost, and further excludes patch groups that cannot attain the maximum within a selected cell. The experiments show the method is promising.

Critical strengths
  • The algorithm is clearly designed and effectively exploits MaxSim’s additive structure.

  • The evaluation checks per-query results and interval validity. The authors report ordered top-k agreement, certificate rates, and bound-validity checks. Approximate controls show that identical average nDCG does not imply identical retrieved pages.

The experimental process and negative results are reported. The authors distinguish development, untouched, and post-freeze robustness domains, document corrections to precision and index implementation, and report that learned policies do not outperform the analytic policy and that the current implementation provides no practical speedup.

Critical weaknesses
  • The deterministic exactness guarantee is not yet fully established for floating-point execution. Theorem 1 assumes that each group interval contains its true maximum, and the geometric argument is clear in real arithmetic. The implementation, however, additionally relies on fixed floating-point guards. The appendix uses a 2×10⁻⁵ bound correction, a 10⁻⁵ stopping margin, and a 5×10⁻⁵ final rescoring envelope, whose validity is primarily checked empirically on the current execution stack and datasets.

  • The final rescoring envelope must provably include every candidate whose ranking could change. Rescoring winners and nearby pages cannot recover a page that was previously eliminated by an unsafe upper bound. This paper should therefore distinguish more clearly between its conditional algorithmic theorem and the guarantees of the concrete floating-point executor.

  • Reduced arithmetic has not translated into practical efficiency gains. The reported GPU-resident median latencies on Economics and Biomedical are 11.45/18.76 ms, compared with 0.191/0.298 ms for Flash-MaxSim, a gap of approximately 60×. More regular execution variants also fail to provide speedups, and the portfolio selects the Flash-MaxSim fallback in every measured regime.

  • The contribution over the previous works requires stronger disucssion, especaily direct comparison with Col-Bandit is missing. Col-Bandit already represents MaxSim as a document-query-token matrix and reduces computation through progressive cell revelation and interval-based candidate elimination. Cell-level processing alone is therefore not a new idea. CellCert’s main distinctions are deterministic geometric intervals, cost-aware refinement, and within-cell group pruning.

  • Some design choices lack systematic ablation and cost analysis. The paper examines group budgets, scheduling policies, and several unsuccessful variants, but provides limited systematic analysis of the separate contributions of ball and spherical-cap bounds, within-cell pruning versus cross-cell scheduling, and reveal-batch size.

Questions for authors
  • How do certificate rates, FMA ratios, iteration counts, and auxiliary-index overhead change on larger corpora and other visual late-interaction models? What are the index construction and update costs?

  • Can the authors add ablations for ball versus spherical-cap bounds, within-cell pruning, and reveal-batch size, reporting FMA work, memory traffic, and actual latency together to explain why arithmetic savings have not yet translated into execution gains?

1 comment

Thank you. We added numerical tests, a Col-Bandit rule comparison, ablations, and scale/model evaluations.

1. Exactness and numerical execution

Theorem 1 requires valid group intervals, conservative page aggregation, and a consistent scorer and tie rule. Final rescoring cannot recover an unsafely eliminated page. The quantization envelope is derived; the bound correction (2e-5), stopping margin (1e-5), and rescore envelope (5e-5) are empirical safeguards, not a worst-case floating-point proof.

A new shared fixed-reduction FP32 scorer now serves exhaustive scoring, refinement, and rescoring. Ordered top-5 matches in 1,174/1,174 original queries and 96/96 stress configurations, with no observed initial interval violations. The latter comprise 48 synthetic inputs under two summary precisions. All real-query rankings also match the historical cache. This new numerical target can differ from earlier reductions on near-ties; the theorem remains conditional on conservative bounds. We will correct the historical CPU description: it applied upper padding without the additional lower padding stated in the paper.

2. Contribution beyond Col-Bandit

The contribution is page-local geometric bounds, cost-aware cell selection, and pruning within each selected cell, beyond the shared idea of progressive cell revelation. We replayed Col-Bandit's confidence/elimination rules using common materialized FP32 cells: 16 queries per domain from Economics/Biomedical/Pharmaceuticals, full corpora, k=5.

MethodOrdered matchesMean FMA ratio
CellCert, C=38448/480.4536
Rule replay, alpha=0.246/480.3027
Rule replay, alpha=148/480.9510

Crediting revealed-cell reuse lowers alpha=1 to 0.8501, still above CellCert. Alpha=0.2 trades less work for two ranking differences. This adapted work comparison does not measure official-code runtime or establish a universal guarantee.

3. Bounds, pruning, and batching

For 32 queries/domain, C=384, batch 256, FMA ratios are:

ConfigurationEconomicsBiomedicalPharmaceuticals
Ball+cap, pruning0.44470.42070.4970
Ball only0.46510.43170.5074
Cap only0.44440.42060.4970
Ball+cap, no pruning0.65370.57890.6930

Within-cell pruning substantially reduces work; cap alone captures essentially all combined-bound benefit here. Separately, on all Pharmaceuticals queries, cellwise refinement reduces FMA from the matched page-level certificate's 0.5946 to 0.4859 (18.3%).

On 32 Pharmaceuticals queries, batch 64 to 4,096 changes FMA 0.4943 to 0.5189, mean rounds 415.2 to 8.7, and median CUDA time 223.50 to 22.82 ms. At batch 256, removing pruning changes FMA 0.4970 to 0.6930 but time 66.48 to 58.92 ms. These earlier unfused-executor diagnostics show why execution overhead matters alongside arithmetic. Actual DRAM traffic was not measured; FMA excludes scalar operations, scheduling, and memory traffic.

4. Scale, models, and index costs

Nested pools use eight common queries, five repetitions, the optimized executor before the shared-scorer update, batch 4,096, and graph-enabled baselines:

PagesMean FMAMean roundsCellCert/dense FP32 median ms
1,0000.55224.7501.842/0.600
5,0000.453612.8755.115/2.563
11,9670.420521.37511.426/6.064

All 24 query/size cases match the reference; auxiliary storage is 39.1-39.2% of the patch index. Pools retain existing duplicates and are scaling diagnostics, not an independent benchmark or formal certificate validation.

With frozen C=384, ColQwen2/ColSmol-500M match all 192 model/query/k cases (k=1/5/10; 32 shared queries, cached 286-page TAT-DQA subset). Their k=5 FMA ratios are 0.7912/0.5959; auxiliary storage is 55.0%/38.9%. These arithmetic tests also precede the shared-scorer update.

On 48 sampled pages, two builds/page and four CPU threads, median build costs are 88.0/91.9/71.3 ms/page for Economics/Biomedical/Pharmaceuticals, including grouping, geometry, and in-memory serialization, excluding encoding/disk I/O. Page-local insertion/replacement leaves other entries unchanged.

5. Updated runtime

For those three domains, current CellCert medians are 1.317/1.481/2.673 ms, versus dense FP32 GEMM 0.298/0.520/1.029 and FP16 Flash 0.154/0.233/0.392. These GPU-resident synchronized wall times use one RTX 5090, eight fixed queries/domain, three interleaved repetitions, and CUDA Graphs throughout; medians are taken within then across queries, excluding setup/compilation and including required host readbacks. The optimized controls use different numerical contracts and remain faster. Our demonstrated gain is reduced scoring work through geometric exclusion across and within cells.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.