Coverage Matters: MarginMerge for Compressing Multi-Vector Visual Document Retrievers
Ailar Mahdizadeh, Aria Salari, Sohail Rajabi, Shahriar Mirabbasi, Panos Nasiopoulos, Alireza Morsali
cs.IR
2026-08-04
Multi-vector visual retrievers like ColPali and ColQwen store many patch vectors per page, making indexes large and MaxSim scoring costly. MarginMerge is a post-hoc method for a frozen model: pick coverage-aware anchors, cluster, and use a 1,057-parameter net to synthesize one representative per cluster, compressing once at indexing while retrieval keeps standard MaxSim. At 5%/10% retention it preserves 97–99% of average nDCG@5 and cuts ranking flips by about 41% versus geometric merging.
Visual document retrievers like ColPali and ColQwen retrieve directly on rendered page images, skipping OCR. They store many fine-grained patch vectors per page and score with MaxSim (ColBERT-style late interaction), comparing each query token against document patches. This multi-vector representation is why they are accurate, since different query tokens pull evidence from different page regions (text passages, tables, figures, layout). But a page can hold hundreds or thousands of vectors, so both index size and retrieval cost scale with the patch count.
The difficulty: aggressive pruning can remove exactly the evidence that makes late interaction work. The real problem is building a compact multi-vector representation that preserves the original model's retrieval behavior.
The paper's key claim is "query-relevant coverage": compression should not select patches independently by salience, but preserve the complementary regions that may become the strongest MaxSim match across different queries. This view also explains why content types compress differently. Dense rendered pages (repeated glyphs, cells, backgrounds, layout) have many substitutable patches and compress well; natural photographs are locally distinct and resist compression.
MarginMerge is a post-hoc method for a frozen retriever, in three steps. First, coverage-aware anchor selection: a bank of 128 "prototype directions" is built from training queries (approximating the query directions patches will meet at retrieval), then k anchors are selected greedily so the set collectively covers as many query directions as possible rather than re-covering the same one. This objective is monotone submodular, so greedy gives a (1−1/e) approximation guarantee. Second, each patch is assigned to its nearest anchor to form clusters. Third, a shared tiny network (only 1,057 parameters, 15→32→16→1) learns to synthesize one representative per cluster as a convex combination of its patches, combining existing evidence rather than inventing an embedding.
Training uses "ranking-margin distillation": instead of reconstructing absolute scores, it preserves the positive-negative score margins that determine ordering (Huber loss, with larger weight on pairs near the ranking boundary). Compression runs once at offline indexing; retrieval stores k representatives and keeps the standard MaxSim, with no query-dependent compression and no engine changes.
Six datasets (ArxivQA, DocVQA, InfoVQA, TAT-DQA, TabFQuad, Flickr) on two backbones, ColQwen2.5 and ColPali. At 5% and 10% retention, MarginMerge has the highest query-agnostic average on both backbones.
| ColQwen2.5, 5% retention | Avg nDCG@5 |
| Full index | 0.892 |
| Light-ColPali (geometric merging) | 0.839 |
| MarginMerge | 0.865 |
Against the full index of the same backbone, it preserves 97% to 99% of average nDCG@5 while cutting stored vectors by 90% to 95%. At 5% retention it cuts ranking flips relative to geometric merging on all six ColQwen2.5 datasets by about 41% on average. A model trained once at 5% transfers to 10% and 20% without retraining; it is trained only on ArxivQA, TabFQuad, and Flickr, with the rest zero-shot.
Several solid findings on mechanism. Salience-based pruning underperforms even random retention on unseen queries: learned selectors fit training queries but keep similar patches and miss complementary regions. Random and k-center selection beat salience, so preserving diversity matters more than concentrating on "important" patches. Ablations show learned representative synthesis is the dominant gain; coverage-aware anchors help most when aggregation is constrained; score reconstruction and margin matching perform similarly.
For engineers building document retrieval or RAG indexes, this is a practical way to compress an expensive multi-vector index to a tenth or a twentieth of storage with almost no quality loss, without touching the retrieval engine or depending on the query. The coverage analysis also guides any multi-vector compression: stop picking individually important tokens and preserve complementary directions instead.
The authors note that greedy anchor selection is slow at indexing (about 1.7 seconds per TAT-DQA document in their implementation); the paper reports vector retention rather than bytes and does not compare full search latency against quantized systems; the redundancy analysis is observational rather than causal, and per-document statistics are weak predictors, useful only as a dataset-level explanation.
One more point: on two of the six datasets (InfoVQA and TabFQuad at 5% retention), MarginMerge is marginally below geometric merging (−0.003 and −0.009), so the win is not universal across every dataset and setting. The edge comes mainly from natural images (largest gain on Flickr, +0.097 at 5%) and zero-shot DocVQA, and rests on replacing "retain original patches" with "learn a synthesized representative."