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

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 $90.3\%$ and $89.2\%$ of the nDCG@5 of uncompressed ColPali and ColQwen2, respectively, at $64\times$ code-payload compression, and $97.9\%$ for both at $26\times$. On a 1M-patch index, total query latency is $6.09$ ms versus $39.11$ ms for uncompressed ColPali.