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

Haowen Xiang, Yibo Yan, Xin Zou, Shuliang Liu, Yi Cao, Mingdong Ou, Xuming HuarXiv 2026 · arXiv

Visual document retrieval (VDR) has seen a massive leap in performance thanks to multi-vector models like ColPali, which can "see" the layout, tables, and figures of a page. However, this visual fidelity comes at a high price: encoding and matching thousands of vectors per page is computationally grueling.

FlexVDR introduces a smarter way to manage this cost. Instead of treating every query with the same "brute force" full-model approach, it learns to dynamically allocate a computational budget—adjusting model depth, embedding width, and token counts—on a per-query basis.

TL;DR

FlexVDR is a framework that allows visual document retrievers to adapt their computational effort to the difficulty of each query. By predicting the "utility" of different model configurations from early features, it maintains near-native retrieval quality while significantly reducing average latency and FLOPs.

What Problem Does This Paper Address?

In VDR, we often use "late interaction" models that represent a document as a collection of patch embeddings. While effective, the online cost of encoding a query and matching it against a massive corpus is high.

Existing "elastic" methods like Matryoshka embeddings allow us to use smaller representations, but they typically use a fixed budget for all queries. This is inefficient: an easy query (e.g., "What is the title of this document?") doesn't need the same 32-layer, 128-dimension heavy lifting as a complex one (e.g., "Compare the trends in Figure 3 and Table 2"). The challenge is deciding which budget to use before you've already spent the computation to run the full model.

Methods

The authors propose a two-stage approach:

  1. Learning a Joint Representation Family: They train a single "elastic" retriever that supports 64 different "routes." A route is a combination of encoder depth ($L$), embedding width ($D$), and token retention ratio ($T$). They use distillation from a frozen "Native Full" model to ensure that even the most compact routes (shallow, narrow, and sparse) retain as much information as possible.
  2. The Budget Allocator: This is a lightweight module that acts as a traffic controller. As shown in Figure 2, the query starts through the first few layers of the Transformer. At an "early layer" ($\ell_0$), the Allocator takes the intermediate features and predicts the retrieval utility (expected nDCG@5) for all 64 possible routes.
Figure 2: Training and query-time retrieval in FLEXVDR. (a) Retrieval supervision and distillation from frozen Native Full scores SF train compact routes with scores Sr. (b) Early query features z(q) and route utilities u(q) train the Budget Allocator. (c) Predicted utilities and resource preference λ select a route; encoding stops at its chosen exit, followed by MaxSim matching with document representations from the same route.

The final route selection is governed by a simple rule: pick the route that maximizes the predicted utility minus a cost penalty, scaled by a user-defined parameter $\lambda$. This $\lambda$ allows developers to tune the system for "speed" or "quality" at inference time without retraining the model.

Datasets

The researchers evaluated FlexVDR across five different model backbones (including ColPali, ColQwen2, and Nemotron) on the ViDoRe (Visual Document Retrieval) benchmarks:

  • ViDoRe V1: A collection of 10 tasks covering various visually rich domains.
  • ViDoRe V2: A more demanding set with complex query construction.
  • ViDoRe V3 public: A recent benchmark focused on multimodal RAG and source grounding.

Key Insights and Ideas

  • Query-Adaptive is Better than Fixed: Easy queries can "exit" the model early or use compressed vectors without losing accuracy. Hard queries get the full treatment. This "self-adaptive" approach is more efficient than any single fixed-budget compromise.
  • Separation of Utility and Preference: By training the Allocator to predict raw utility (quality) and handling the cost penalty ($\lambda$) separately, the model becomes highly flexible. You can change your hardware or latency requirements on the fly just by sliding the $\lambda$ value.
  • Multi-Axis Elasticity: The paper shows that depth, width, and token counts are complementary. If a query requires full depth to understand the semantics, you might still be able to save costs by reducing the embedding width or pruning redundant tokens.

Key Results

FlexVDR consistently achieves "near-native" performance with significantly less work:

  • Quality Retention: Across all backbones, the drop in nDCG@5 was typically less than 1 percentage point compared to the full-budget native models.
  • Efficiency Gains: For the webAI backbone on ViDoRe V1, FlexVDR assigned 99.97% of queries to lower budgets while maintaining a score of 86.50 (vs. 86.66 for the full model).
  • Tunability: As shown in Figure 1, FlexVDR moves beyond the "deployment-fixed" constraints of previous Matryoshka methods, allowing for a truly "self-adaptive" retriever.
Figure 1: Representation choices and budget selection. (a) Embedding MRL provides nested widths at the final layer; (b) MM-Matryoshka provides depth–width choices. Both illustrated settings use one fixed configuration across queries. (c) FLEXVDR selects depth, width, and query/document token budgets per query. L, D, and T label the depth, width, and token-count axes.

Limitations and Future Work

  • Storage Overhead: To support different layers and widths efficiently, the system currently requires storing some additional "compact" document representation streams, which increases disk usage.
  • Allocator Training: The Budget Allocator is currently trained on a deterministic local pool of documents. The authors suggest that training it against a more dynamic, global retrieval setting could further improve its predictive accuracy.
  • End-to-End Optimization: While the retriever and allocator are trained in stages, future work could explore joint training to further tighten the quality-computation trade-off.

Summary updated

Abstract

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.
BibTeX
@misc{xiang2026flexvdr,
  author = {Haowen Xiang and Yibo Yan and Xin Zou and Shuliang Liu and Yi Cao and Mingdong Ou and Xuming Hu},
  title = {{FlexVDR: Learning to Allocate Matryoshka Representation Budgets for Visual Document Retrieval}},
  year = {2026},
  eprint = {2610.30177},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30177},
}
Figure