Retrieval Needs Multivectors: An Exponential Separation
Mihir Agarwal, Viraj Agrawal, Sabyasachi Basu, Ankit Garg, Kirankumar Shiragur
cs.IR, cs.DB, cs.LG
2026-08-21
MSR India proves an exponential gap for ranking, not score matching. On ANDOR, multi-vector models stay about 2× ahead of single-vector after fine-tuning.
Late-interaction retrievers such as ColBERT keep a vector per token and score documents with Chamfer similarity: each query vector picks its best document vector, then those maxima are summed. That stack is already in Vespa and Qdrant. LIMIT showed single-vector models struggling, but later work recovered much of the gap with task-specific fine-tuning. So it was still open whether multi-vector embeddings are actually more expressive.
Jayaram et al. proved that approximating Chamfer scores pointwise can force exponential single-vector dimension. Retrieval only needs order: every relevant document above every irrelevant one. Score matching is a stricter demand, so that lower bound does not settle ranking. This paper asks the ranking question and gives an explicit family of relevance matrices.
The hard matrices are pattern matrices built from the Minsky-Papert function: a conjunction of m clauses, each an OR of L=4m² literals. A document is relevant iff every clause is hit at least once.
Single-vector scoring is an inner product. If it preserves per-query order, the embedding dimension is at least the sign-rank of the matrix. Known bounds give sign-rank 2^Ω(m), hence exponential dimension. The multi-vector side is constructive: one vector per query clause, one vector per document coordinate, Chamfer scores separated by Θ(m⁻²), representation size O(m⁶).
A sanity check closes a loophole. Jayaram’s NAND pattern matrix is hard for score approximation, yet it admits a Θ(N)-dimensional single-vector embedding that already preserves ranking. Hard scores do not imply hard order.
ANDOR turns the same AND-of-OR rule into faceted shopping search: 20 categories, 20 attributes each, 50,000 products. A document matches iff every queried category hits at least one accepted attribute. Each test query has exactly two positives, plus hard negatives that miss only 1–3 categories. Query width (mean accepted attributes per category) controls difficulty.
Zero-shot, multi-vector already leads by a wide margin. GTE ModernColBERT’s relative gains over the strongest single-vector model, Cohere Embed v4, are 80.6%, 93.8%, and 87.0% at Recall@2 / @10 / @100. Versus OpenAI text-embedding-3-large the Recall@2 gain is 1662%. Mean zero-shot gain at Recall@2 is about 6.3×.
Fine-tuning does not close the gap. Against Qwen3 Embedding 0.6B and Arctic Embed L v2, ColBERT stays about 99% ahead on Recall@2 and 58% on Recall@100 across the train–test grid. At the easiest test width 3.5, ColBERT reaches about 89–93% Recall@100; single-vector models remain well behind.
The cleanest control is Jina Embeddings v4, which emits both heads from one backbone. After joint fine-tuning, the multi-vector head still leads the single-vector head by 105%, 84%, and 62% at Recall@2 / @10 / @100. Data, parameter count, and optimizer are matched. The gap remains.
| Comparison | Recall@2 relative gain | Recall@100 relative gain |
| ColBERT vs mean zero-shot SV | 631.8% | 414.4% |
| ColBERT vs mean fine-tuned SV | 99.4% | 57.8% |
| Jina MV vs same-model SV (joint FT) | 104.8% | 61.5% |
LIMIT left an opening: maybe the models were undertrained. ANDOR narrows that opening. On a shared Jina backbone with joint fine-tuning, the multi-vector head is still about twice as strong. For faceted search, Boolean filters, and agentic retrieval, single-vector dense retrieval may hit a representation ceiling that extra training will not move.
The theorem is about worst-case dimension. ANDOR is a semantic cousin of that Boolean rule, not the pattern matrix in the proof. It is already hard enough that off-the-shelf single-vector models fail to learn a simple matching rule from text.
Every test query has two positives. An existence result says a 5-dimensional single-vector embedding can realize the ordering if the full relevance matrix is known. That construction is non-constructive and does not yield a recipe for learning embeddings from language. The experiments use ordinary semantic training, so there is no contradiction, and also no license to claim “real tasks need exponential dimension.”
All methods degrade as query width grows; the paper leaves the mechanism open. Two theory questions stay open: whether an approximate per-row ordering still forces an exponential gap, and whether preserving a specified ranking (not just relevant vs. not) still favors multi-vector embeddings exponentially.