acceptodds
Under review as a conference paper at ICLR 2027

Depth-as-Budget: Patch-Adaptive Residual Quantization for Visual Document Retrieval

Abstract

Late-interaction visual document retrieval (VDR) enables fine-grained patch matching, but its high storage and scoring costs make index compression essential at scale. The key challenge is to compress the index before future queries are known, even though these queries determine which patches matter for matching. Then, we propose PARQ (Patch-Adaptive Residual Quantization), which keeps every patch available for matching and distributes a fixed compression budget using document-side reconstruction gains. PARQ adaptively allocates residual codes based on reconstruction-error reduction. This allocation requires no query supervision or encoder fine-tuning. Grouped lookup-table scoring enables retrieval over variable-depth codes without reconstructing dense embeddings. On ViDoRe v1 and v2, PARQ retains and of the nDCG@5 of uncompressed ColPali and ColQwen2, respectively, at code-payload compression, and for both at . On a 1M-patch index, total query latency is ms versus ms for uncompressed ColPali.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Retrieval-augmented generation, Visual document retrieval

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_JVRaOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies query-independent compression of late-interaction visual document indexes. Its method, PARQ, retains every patch and allocates variable-length residual-quantization prefixes under a per-page code budget. Additional stages are assigned greedily according to marginal reconstruction-error reduction. A grouped lookup-table implementation evaluates MaxSim directly over these variable-depth codes. The paper provides a reconstruction-based bound on score distortion and proves greedy optimality under diminishing, nonnegative marginal gains. Experiments cover nine ViDoRe subsets and two frozen retrievers. At 64× code-payload compression, PARQ improves average nDCG@5 over fixed-depth RQ by 6.32 points for ColPali and 5.77 points for ColQwen2. Further experiments examine residual-error concentration, codebook transfer, and execution overhead.

Critical strengths
  1. The main allocation comparison isolates a useful design choice and shows substantial gains at tight budgets. Tables 1 and 2 retain the same patch set and match code budgets across fixed-depth, random, norm-based, and marginal-gain allocations. At 64×, PARQ improves nDCG@5 from 57.16 to 63.48 on ColPali and from 63.05 to 68.82 on ColQwen2, with improvements across all nine reported subsets. Random and norm-based allocations perform worse than fixed depth, making the result more informative than simply showing that variable-length codes can work. Achieving these gains without query supervision or encoder fine-tuning gives the method practical value.

  2. The residual-distribution analysis goes beyond an aggregate reconstruction-versus-retrieval correlation. Table 3 compares allocations with the same code budget and approximately matched average distortion. Reducing tail residuals improves nDCG@5 from 61.40 to 63.60 and reduces rank reversals from 15.0% to 10.5%. This is useful evidence that average reconstruction error alone does not characterize retrieval fidelity. The paper also appropriately limits its theoretical claims: Equation (8) bounds score error, while Appendix C establishes surrogate optimality only under stated assumptions and reports empirical violations of those assumptions.

Critical weaknesses
  1. The comparison with the strongest external baseline is not specified precisely enough to establish the claimed advantage. Appendix B.3 describes Light-ColPali/ColQwen2 using “pooling factors” and allows either official checkpoints or reproductions on frozen embeddings, without identifying which configuration produced each reported row. The original Towards Storage-Efficient Visual Document Retrieval: An Empirical Study on Reducing Patch-Level Embeddings (2025) defines the final Light method using semantic clustering after the projector together with fine-tuning. It is therefore important to distinguish that method from training-free pooling or clustering variants. At 64×, PARQ’s reported advantages over Light are only 0.27 and 0.26 nDCG points, with no uncertainty estimates. I cannot determine whether these differences represent a reliable advantage over the published method. This limits the external comparison, although it does not invalidate the larger gains over fixed-depth RQ.

  2. The physical-storage result is not yet auditable from the described layout. Appendix B.2.1 states that all required structures are included, but Table 5’s totals equal the listed patch-code bytes plus codebooks exactly at the displayed precision. Grouping patches by depth removes the need for an explicit depth field per patch, but decoding variable-size page/bucket groups still requires boundary information or an equivalent encoding. Its representation and byte cost are not explained. The listed codebook sizes also correspond approximately to a single 12-stage family with 16-bit coordinates, whereas the accuracy experiments fit domain-specific families. The paper needs to identify the collection and families used for this storage measurement. These omissions leave the claimed 25.51×/63.86× physical compression less well established than the nominal payload ratios.

Questions for authors
  1. Which exact checkpoints and merging procedures produced the Light rows in Tables 1 and 2? Were these the fine-tuned semantic-clustering models, or frozen-embedding adaptations? Please also report any available variability for the 64× comparisons. A faithful baseline configuration and a reproducible difference would strengthen the practical comparison; otherwise, I would treat these results as approximate parity with a different training requirement.

  2. How can the serialized index in Table 5 recover every page and depth-bucket boundary? Please provide the encoding and byte breakdown, identify the codebook families included, and clarify whether auxiliary bytes are contained within the “Patch code IDs” row. A self-contained layout that reconciles with the measured totals would resolve my storage concern.

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

PARQ compresses late-interaction visual document indexes by allocating residual-quantization depth across all patches within a page-level budget. Allocation uses document-side reconstruction gains; grouped lookup tables compute MaxSim without reconstructing dense vectors. The paper provides a score-error bound, conditional greedy analysis, and experiments on two backbones across nine ViDoRe subsets. Codebooks are fitted to unlabeled documents from each target subset.

Critical strengths
  1. Substantial gains at a tight budget. At 64×, PARQ improves average nDCG@5 over fixed-depth RQ from 57.16 to 63.48 on ColPali and from 63.05 to 68.82 on ColQwen2 (Tables 1–2). The consistent gains across two backbones support adaptive precision allocation.

  2. A useful practical and empirical contribution. PARQ requires no additional supervised encoder fine-tuning, and grouped LUTs make variable-depth codes usable for direct scoring. Matched-distortion controls, fixed-payload parameter sweeps, and transfer experiments provide evidence beyond the main compression results.

Critical weaknesses
  1. Adaptive residual depth (VRVQ), variable code counts across image locations (Baldassarre et al., 2023), compressed multi-vector scoring (WARP), and diminishing-returns allocation (Federgruen and Groenevelt, 1986) have precedents. These differ in task or representation; PARQ’s contribution is primarily their VDR-specific integration. At 26×, gains over fixed-depth RQ are only 0.49/0.45 points, limiting evidence of a broader advance beyond the tight-budget setting.

  2. Section 3.3 motivates the norm-based comparison through the distinction between current residual magnitude and next-stage gain, but Norm Adaptive’s norm input and priority/update rule are not defined. It is therefore unclear whether Tables 1–2 and 10 test that distinction. This limits interpretation and reproducibility of the mechanism comparison, although the principal fixed-depth results remain meaningful.

  3. Appendix B.3 lists official checkpoints, released settings, and frozen-embedding reproductions without mapping them to the Light rows. This matters because the reported 64× margins are only 0.27/0.26 points and the comparison also invokes Light’s supervised fine-tuning. The missing provenance limits how confidently the external results support the quality and training-cost tradeoff.

Questions for authors
  1. Please give its stage-priority formula, specify which vector’s norm is used, and state whether priorities are updated after each allocation. Does this baseline directly test current-residual magnitude against PARQ’s next-stage gain?

  2. Please identify the checkpoint or reproduction configuration and fine-tuning status for each Light-ColPali and Light-ColQwen2 row at 26× and 64× in Tables 1–2.

  3. Please state the backbone, evaluation subsets and aggregation, and any settings differing from Tables 1 and 8. Give the exact 100k-patch values at 64× and 26× and clarify whether they use the main-table configuration.

  4. At the reported budgets, were any negative-gain stages selected? If so, how were they handled given Equation (5)’s ≤ budget constraint?

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

This paper tackles the massive storage and compute overhead of late-interaction visual document retrieval models (like ColPali and ColQwen2). Instead of dropping patches through aggressive pruning or pooling, the authors propose PARQ (Patch-Adaptive Residual Quantization). PARQ keeps every single visual patch alive and dynamically allocates residual quantization depths (code lengths) to each patch based on its marginal reconstruction-error reduction under a fixed page bit-budget. At query time, patches are grouped into buckets by their depth, enabling direct MaxSim computation via grouped lookup tables (LUTs) without dense-vector reconstruction or GPU branch divergence. Experiments across 9 ViDoRe subsets show that PARQ retains ~90% nDCG@5 at 64× compression without requiring any query supervision or encoder fine-tuning.

Critical strengths
  1. Pruning or pooling visual tokens permanently destroys fine-grained details (like small table values or footnotes). PARQ keeps all patches searchable while matching or beating supervised methods like Light-ColPali at 64× compression.

  2. Variable-length codes usually kill GPU throughput with thread divergence. By grouping patches into depth-specific buckets, PARQ achieves clean, batched table lookups, adding only 0.17 ms over uniform RQ on a 1M-patch index.

  3. Experiments like Table 3 (controlling average distortion while swapping tail errors) and Table 10 (tracking winner preservation) clearly substantiate why adaptive allocation helps beyond just varying bit rates.

Critical weaknesses
  1. The bound connecting L2 reconstruction loss to MaxSim score error is very loose. A visually noisy background patch might have huge reconstruction error and consume extra bits, even though no user query will ever match it. L2 loss is an imperfect heuristic for ranking.

  2. Blank pages or simple text pages end up wasting bits, while information-dense infographics and tables are starved of budget.

  3. Table 9 shows that transferring codebooks from one domain to another drops nDCG@5 by nearly 5 points. In open-domain web search, training a separate 100k-patch codebook for each document domain is impractical.

  4. At 26× compression, PARQ only beats fixed-depth RQ by 0.49 on ColPali and 0.45 on ColQwen2. The real benefit only shows up under severe bit budgets (64×).

  5. Theorem 1 relies on strictly diminishing marginal gains (Δj,t≥Δj,t+1\Delta_{j,t} \ge \Delta_{j,t+1}). However, Table 7 reveals that over 18%–20% of patch chains violate this assumption, meaning greedy allocation is not strictly optimal.

Questions for authors
  1. Why restrict the bit budget strictly per page? What happens to overall nDCG@5 if you run greedy allocation globally across all pages in a document or corpus under the same total bit budget?

  2. What is the performance drop if you train one single universal codebook on a general document mixture and test it across all 9 ViDoRe subsets, rather than training specialist codebooks per dataset?

  3. How long does it take to compute stage-wise marginal reconstruction gains and sort them per page?

  4. Does the greedy heuristic trap allocation in local sub-optima for complex patches?

  5. The MaxSim bound assumes all query tokens have equal weight. ColPali token norms and attention weights vary significantly across query tokens. Does accounting for query-side token variance change your theoretical bound?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.