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

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.