# Retrieval Needs Multivectors: An Exponential Separation

arXiv: https://arxiv.org/abs/2608.21494 · HTML: https://mlsanity.com/paper/2608.21494/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 21 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models](https://mlsanity.com/paper/2506.05176/) (2025)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction](https://mlsanity.com/paper/2112.01488/) (2021)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [jina-embeddings-v4: Universal Embeddings for Multimodal Multilingual Retrieval](https://mlsanity.com/paper/2506.18902/) (2025)
- [Arctic-Embed 2.0: Multilingual Retrieval Without Compromise](https://mlsanity.com/paper/2412.04506/) (2024)
- [MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings](https://mlsanity.com/paper/2405.19504/) (2024)
- [Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings](https://mlsanity.com/paper/2606.23475/) (2026)
- [Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity](https://mlsanity.com/paper/2607.20393/) (2026)
- [On Strengths and Limitations of Single-Vector Embeddings](https://mlsanity.com/paper/2603.29519/) (2026)
- [Quantifying and Expanding the Theoretical Capacity of Late-Interaction Retrieval Models](https://mlsanity.com/paper/2607.05803/) (2026)

## Built on by (most cited first, 3 of 3)

- [EigenLI: Spectral Approximations to Late Interaction](https://mlsanity.com/paper/2609.07561/) (2026)
- [NeoMME: A Single-Tower Multimodal-Native Multilingual Foundation Encoder for Efficient Fine-Tuning and Inference](https://mlsanity.com/paper/2609.01657/) (2026)
- [Simple Linear Corrections for Compression in Late Interaction](https://mlsanity.com/paper/2610.14196/) (2026)

## Abstract (arXiv)

Recent works have highlighted the expressive limitations of embedding based retrieval models through both theoretical analyses and challenging benchmarks such as LIMIT. While multi-vector embeddings consistently outperform single-vector embeddings, the precise representational gap between them remains poorly understood. In this work, following Jayaram's work, we provide the first explicit family of query and document sets, together with their relevance matrices, for which single-vector embeddings that rank all relevant documents above irrelevant ones require exponential size, whereas polynomial-size multi-vector embeddings suffice. Our result establishes an exponential separation between the expressive power of single-vector and multi-vector embeddings for the task of ranking of documents as opposed to approximating numerical scores as in the work of Jayaram. Motivated by our theoretical construction, we introduce ANDOR, a new retrieval benchmark that naturally instantiates these hard examples. We show that state-of-the-art single-vector embedding models perform poorly on ANDOR in the zero-shot setting and exhibit only marginal improvements after fine-tuning, highlighting the inherent difficulty of the benchmark compared to prior work. In contrast, multi-vector models consistently outperform their single-vector counterparts and improve substantially with fine-tuning, closely aligning with our theoretical predictions.