CS Paper Radar

Query-Aware Token Budgeting for Efficient Late-Interaction Visual Document Retrieval

PS Rishi, Rajeev Ranjan Dwivedi, Vinod K Kurmi

cs.IR cs.AI ·submitted 2026-09-07 09:18 UTC · v1
top venue

Abstract

Late-interaction visual document retrievers preserve fine-grained page evidence by storing many token embeddings per page, but the resulting storage and query-time interaction costs make large-scale deployment expensive. Pooling document tokens before indexing offers a natural remedy, yet static pooling must decide which visual evidence to preserve before the query is known. We study an alternative: a heavily compressed hot-path index generates candidates, after which query-aware token budgeting operates on the original token sets of the shortlisted pages. We formulate this stage-two selection as a budgeted MaxSim coverage problem, show that a clipped version is monotone submodular, and compare coverage-only, cluster-guided, token-wise, and marginal-gain policies. On ten ViDoRe tasks with ColModernVBERT, direct static pooling reduces macro normalized discounted cumulative gain at rank five from 0.6309 without compression to 0.4738 at a thirty-two-fold pool factor. Under the same candidate-generation regime and a pool-factor-eight-equivalent reranking budget, token top-k recovers 93.93 percent of the full-token score, while greedy marginal-gain selection recovers 98.39 percent. Held-out and leave-one-dataset-out evaluations yield positive greedy improvements over token top-k on every dataset. The latency analysis reveals two useful operating points: token top-k for interactive retrieval and the naive greedy implementation as a quality upper envelope. Together, these results show that late-interaction visual retrieval benefits from query-aware allocation rather than query-agnostic pooling alone.

Comment
Accepted at IEEE International Conference on Data Mining (ICDM)

Closest papers

Nearest neighbours by meaning across the whole index.

Unbalanced Optimal Transport for Efficient Visual Document Retrieval

cs.CV ·2026-10-07 ·Hoyeon Shin, Jeongyeon Kim, Yeong Jun Koh, Yeoneung Kim, Hanul Kim
top venuecode/data similarity 0.75
Abstract · Accepted at ECCV 2026

Vision-Language Models(VLMs)have advanced Visual Document Retrieval (VDR) by enabling OCR-free, multi-vector representations. However, these models generate excessive tokens to preserve dense visual details, which severely limits retrieval scalability. Existing compression methods mitigate this overhead but rely on isolated heuristics that fail to balance token importance, semantic redundancy, and coverage capacity. We propose a visual token compression framework formulated as an Unbalanced Optimal Transport (UOT) problem. Our approach unifies these three objectives into a single alternating optimization process. Furthermore, we theoretically show that minimizing the transport cost upper-bounds the MaxSim retrieval error, ensuring ranking stability. Extensive experiments on the ViDoRe V1 and V3 benchmarks demonstrate that our method preserves fine-grained document semantics and improves the efficiency-effectiveness trade-off over state-of-the-art base-lines. Code is available at https://github.com/shhhhhyy/Unbalanced-Optimal-Transport-for-EVDR.

0.39

FlexVDR: Learning to Allocate Matryoshka Representation Budgets for Visual Document Retrieval

cs.IR ·2026-10-19 ·Haowen Xiang, Yibo Yan, Xin Zou, Shuliang Liu, Yi Cao +2 more
similarity 0.74
Abstract · 21 pages, 5 figures

Visual document retrieval relies on rich multi-vector representations to capture fine-grained evidence in document pages, but encoding and matching these representations can be computationally expensive. Existing compression and elastic representation methods expose smaller configurations, yet making multiple budgets available does not determine which configuration a query should use. The allocation decision must estimate the retrieval value of alternative representations before incurring their full computation, while accommodating different resource preferences. We introduce FlexVDR, a framework for query-adaptive budget allocation within a single retriever. We construct a joint family of routes over encoder depth, embedding width, and token count. Retrieval supervision and distillation train the compact routes, while a native bypass preserves the full-budget reference. A Budget Allocator predicts route-specific retrieval utility from early query features and combines these predictions with a configurable resource preference to select a route. Experiments across five backbones on ViDoRe V1, V2, and V3 public show that FlexVDR retains much of the native retrieval quality while selecting compact routes for individual queries. A configurable resource preference allows the same retriever to adjust its computation without retraining or switching models.

0.12

MAGIC: Marginal-Guided Compression with Optimal Transport for Efficient Visual Document Retrieval

cs.CV cs.IR ·2026-09-17 ·Xu Yuan, Hua Liu, Wenqi Fan, Qing Li
code/data similarity 0.73
Abstract

Recent visual document retrieval (VDR) systems such as ColPali use multi-vector page embeddings, in which patch-level vectors enable fine-grained evidence matching but incur substantial index storage and MaxSim scoring overhead. Post-hoc merging offers a practical route to efficient VDR by reducing this cost without retraining the retriever, but its uniform reconstruction objectives are poorly aligned with the sparse, non-uniform patch usage induced by late-interaction retrieval. Under aggressive compression, this misalignment can preserve rarely used patches while concentrating retrieval activity on too few retained representatives. To address this misalignment, we propose Marginal-Guided Compression with Optimal Transport (MAGIC), a training-free post-hoc compressor for efficient retrieval with frozen multi-vector embeddings. MAGIC derives a MaxSim-induced compression surrogate and optimizes it through a two-marginal entropic optimal-transport formulation, where a retrieval-demand source marginal prioritizes high-use patches and a balanced target marginal regularizes retained-facet usage. Across ViDoRe benchmarks, keep ratios, and retrieval backbones, MAGIC consistently outperforms strong post-hoc compressors, with particularly large gains in the aggressive-compression regime; component ablations verify the complementary effects of its two marginals. We release the code at: https://github.com/xandery-geek/MAGIC.

0.23

Token-Budgeted Escalation for Financial Document Question Answering: Cost Is Predictable, Benefit Is the Bottleneck

cs.IR ·2026-10-06 ·Junru Zhu, Yixin Yang, Xiaoqing Ding, Ruoyu Qi
code/data similarity 0.72
Abstract · 6 pages; revised evaluation and discussion, added references, and corrected formatting. Code and aggregate artifacts: https://github.com/jun…

Retrieval-augmented generation systems can route difficult queries to deeper context, but batch deployments must allocate a shared token budget across calls whose costs vary by query. We formulate selective escalation as finite-batch allocation for financial document question answering. Each of 150 FinanceBench questions first receives a top-1 retrieval answer. Predictors estimate the adjudication-quality gain and token cost of an optional top-5 call, and the allocator prioritizes calls by predicted gain per token. At the nominal 10% budget, gain-per-token allocation improves adjudication quality over gain-only ranking by 0.034 (95% document-bootstrap confidence interval [0.001, 0.072]) while using 46.6% fewer total tokens than one-pass top-5 retrieval. Additional-call cost is accurately predictable (R-squared 0.93), whereas beneficial escalation remains difficult to rank (area under the receiver operating characteristic curve 0.60). These results show that heterogeneous cost is actionable under tight constraints, while progress across the full budget frontier depends on stronger query-specific benefit estimates.

0.22

Test-Time Adaptation with Query-Dependent Residuals for Visual Document Retrieval

cs.IR ·2026-09-23 ·Zeliang Li, Xiaofen Xing, Kailing Guo, Xiangmin Xu
similarity 0.71
Abstract

Visual document retrieval (VDR) systems depend on page embeddings computed before deployment, which makes adaptation difficult when encoder parameters or corpus re-encoding are unavailable. Rerankers provide useful relevance signals, but conventional reranking applies them only to selected queries and candidate pages. We introduce Q-REACT, a query-side test-time adaptation method that converts limited reranker feedback into reusable retrieval improvements. Q-REACT learns a shared low-rank transformation that produces query-dependent residuals, combines adapted query scores with document-level context, and distills reranker preferences with a student distribution normalized over the complete task-specific page index. This design lets unscored pages compete through cached embeddings while keeping the encoders and page index fixed. Across eight ViDoRe V3 tasks and five open-weight and proprietary backbones, Q-REACT improves average retrieval over evaluated baselines at sparse and full-coverage budgets, transfers to held-out queries and tasks, and adds little inference overhead. The results show that finite reranker feedback can be amortized across a query collection without retraining or rebuilding the retriever.

0.07

Cascaded Retrieval with Cross-Modal Query Refinement for Efficient Visual Document Search

cs.CL ·2026-10-14 ·Diana Turmakhan, Aseem Srivastava, Vivek Gupta, Iryna Gurevych, Thamar Solorio
similarity 0.71
Abstract

Retrieving information from visually rich documents requires matching queries against pages that contain complex evidence in tables, figures, and layout-dependent structures. Current vision-language retrievers address this but incur query-time costs that grow with corpus size and are impractical to scale. We propose SCOUT, a cascaded two-track retrieval framework that separates retrieval performance from exhaustive search. The visual track first uses a lightweight parent retriever to filter the corpus to a compact candidate pool, then applies a stronger multi-vector reranker only to those candidates. In parallel, a semantic track retrieves over hierarchical page and document summaries generated offline to provide a signal complementary to visual matching. The outputs are fused through cross-modal query refinement, which uses semantic scores to adjust the visual query representation before final ranking. We evaluate SCOUT on 4 major benchmarks against 6 baselines and observe a significant query-time latency improvement up to 80.7x (28.8x on average) relative to the best baseline, while exceeding state-of-the-art retrieval performance by up to 7.8% NDCG across all benchmarks.

0.16

DocPC: Document-Level Visual Retrieval via Representative Page Composition

cs.IR ·2026-08-26 ·Chengsong You, Qiyi Jiang, Junwei Zhou, Xiaoyu Cao, Weiyao Wang +10 more
benchmarkcode/data similarity 0.70
Abstract · 15 pages, 5 figures, 8 tables

Visual document retrieval has advanced by encoding page screenshots with vision-language models, bypassing OCR pipelines. However, existing methods remain page-centric, misaligned with real-world scenarios requiring complete document retrieval. A naive page-then-document aggregation suffers from linear indexing cost and degraded retrieval when relevance spans multiple pages. We propose DocPC, a document-level visual retrieval framework based on Representative Page Composition: selecting representative pages and composing them into a single grid image for document-level indexing, reducing indexed images, vectors, and storage by 10.1x and end-to-end indexing time by roughly 7.7x. To handle multi-positive supervision prevalent at the document level, we combine multi-positive contrastive learning with sparsely scheduled listwise optimization. We also introduce DocViRe, a benchmark with multi-positive relevance annotations. DocPC-ColQwen achieves NDCG@5 of 44.09 on DocViRe, outperforming the strongest page-level baseline at 38.91 while reducing storage by 10.1x. Code is available at https://anonymous.4open.science/r/DocPC-Document-Level-Visual-Retrieval-via-Representative-Page-Composition-1D52. Data is available at https://huggingface.co/datasets/anonymous-7219/docpc.

0.49

BoundaryMORPH: Budgeted Reranking via Active Set Selection for Diffuse Retrieval

cs.IR ·2026-09-23 ·Eylon Caplan, Shamik Roy, Shib Sankar Dasgupta, Yingfan Wang, Rashmi Gangadharaiah
similarity 0.70
Abstract · Under review

Open-ended queries in modern Retrieval-Augmented Generation (RAG) are increasingly "diffuse," requiring a large set of documents to be assembled into a finite LLM context window. To ensure retrieval quality, systems use fast dual-encoders and more expensive cross-encoders (CEs) to score candidates. However, the CE budget $B$ is strictly bounded by latency and is often smaller than the context window capacity $k$. This mismatch makes standard reranking structurally flawed: it wastes compute verifying obvious top candidates while ignoring relevant documents further down the initial ranking. To address this, we introduce BoundaryMORPH, a novel algorithm that allocates CE budget specifically for the LLM's context capacity $k$. Using a Gaussian Process, BoundaryMORPH treats the initial dual-encoder ranking as a structural prior and intelligently spends CE calls on resolving top-$k$ set membership at the boundary, rather than seeking a single most-relevant document. Information from each CE call propagates to unscored documents, maximizing the utility of the budget. We demonstrate that BoundaryMORPH achieves state-of-the-art set retrieval quality across multiple models and datasets with open-ended queries ($+5.4$ nCG@100 over the strongest baseline).

0.15