Retrieval Needs Multivectors: An Exponential Separation

Mihir AgarwalViraj AgrawalSabyasachi BasuAnkit GargKirankumar Shiragur

article2026arXiv1 citations

Proves that single-vector retrieval models require exponential size compared to polynomial-size multi-vector representations to rank documents accurately, introducing the ANDOR benchmark to show how current single-vector systems fail on these instances even after fine-tuning.

Listen

Modern information retrieval systems increasingly rely on neural representations, primarily single-vector dense embeddings and multi-vector late-interaction architectures. While multi-vector approaches consistently deliver superior search accuracy, the industry has debated whether this advantage reflects fundamentally higher representational capacity or simply artifacts of better training pipelines. Understanding this boundary is critical for organizations choosing between simpler, less resource-intensive single-vector architectures and higher-latency, higher-cost multi-vector architectures.

The article resolves this question by evaluating the mathematical and empirical limits of both paradigms. Specifically, it demonstrates that multi-vector embeddings are exponentially more expressive than single-vector embeddings for ranking relevant documents ahead of irrelevant ones, and it validates this separation using a realistic benchmark.

To establish this result, the authors used communication complexity techniques to construct an explicit family of document-query relevance matrices with compositional Boolean logic. They complemented this theoretical proof with an empirical evaluation on ANDOR, a newly introduced e-commerce faceted search benchmark comprising 50,000 product documents and structured search queries. The benchmark evaluates zero-shot and fine-tuned performance across seven prominent retrieval models, including controlled experiments on a unified model architecture containing both single-vector and multi-vector projection heads.

The analysis produced three primary findings. First, single-vector models theoretically require an exponentially large embedding dimension to correctly rank documents for certain compositional queries, whereas multi-vector models achieve correct rankings with compact, polynomial-sized representations. Second, across zero-shot evaluations on ANDOR, multi-vector models systematically outperformed single-vector baselines by factors ranging from 2x to over 10x. Third, task-specific fine-tuning failed to close the performance gap; multi-vector models maintained a roughly 2x relative margin (over 100% relative gain at early retrieval cutoffs) post fine-tuning, and fine-tuning a single-vector head only managed to reach the baseline level of an untrained, zero-shot multi-vector head.

These findings prove that single-vector retrieval models possess an inherent representational ceiling when handling complex, multifaceted queries where multiple mandatory constraints must be satisfied. While prior benchmarks suggested fine-tuning could overcome single-vector limitations, the article demonstrates that this gap is mathematically intrinsic. Organizations deploying search and retrieval systems for complex reasoning, agentic workflows, or multifaceted product search face severe quality penalties if they rely solely on standard single-vector embeddings.

Decision-makers building retrieval infrastructure for complex search domains should adopt multi-vector or late-interaction architectures, such as ColBERT-based models, to avoid accuracy bottlenecks. In environments where low latency and constrained serving budgets make full multi-vector deployment challenging, teams should evaluate hybrid or cascading pipelines that use single-vector models for broad initial filtering and multi-vector models for precise re-ranking. Future research and development should explore whether these exponential gaps persist when allowing small tolerances for ranking errors.

The findings are supported with high confidence by rigorous mathematical proofs and controlled empirical evaluations on a fixed model backbone. However, readers should note that the empirical study specifically examined highly structured, constraint-heavy queries with sparse relevance. Simpler retrieval tasks that do not involve nested logical constraints may not experience the severe exponential degradation demonstrated here.

Microsoft marginals retrieval performance text document multi-vector retrieval dense retrieval exponential separation

arXiv: 2608.21494

Paper: On the Theoretical Limitations of Embedding-Based Retrieval, Orion Weller et al. (2026). This foundational work establishes the theoretical capacity limits and dimensional lower bounds of single-vector embeddings and introduces the LIMIT benchmark directly analyzed and extended by the source.
Paper: ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction, Keshav Santhanam et al. (2022). This paper presents the ColBERT late-interaction paradigm, providing the primary practical multi-vector retrieval framework whose representational power is theoretically separated from single-vector models in the source.
Paper: M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation, Jianlv Chen et al. (2024). This work formulates unified architectures spanning dense single-vector and fine-grained multi-vector retrieval mechanisms, offering core operational context for their performance trade-offs.
Paper: Large Dual Encoders Are Generalizable Retrievers, Jianmo Ni et al. (2022). This article demonstrates the expressivity and generalization limits of standard dual-encoder single-vector representations when scaling parameters under fixed embedding dimensions.
Paper: BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models, Nandan Thakur et al. (2021). This benchmark paper establishes the empirical performance gaps between single-vector dense retrievers and late-interaction multi-vector architectures across diverse zero-shot retrieval tasks.

Paper: Can Language Models Actually Retrieve In-Context? Drowning in Documents at Million Token Scale, Siddharth Gollapudi et al. (2026). This work evaluates in-context language model retrieval on the LIMIT benchmark, exploring long-context generation as an alternative architecture to vector-based document retrieval.

Cover for Retrieval Needs Multivectors: An Exponential Separation

Abstract

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.

Topics

marginals retrieval performance text document electronic document tuning method numerical solution word embedding

Keywords

multi-vector retrieval dense retrieval exponential separation single-vector models relevance separation margin relevance matrices Boolean relevance ANDOR dataset

1 Introduction
2 Related Work
3 Preliminaries
4 Overview of Results
5 Proofs
5.1 A Lower Bound for Single Vectors
5.2 Proof of Theorem
5.3 The NANDn\operatorname{NAND}_{n} Pattern Matrix admits a linear single-vector representation
6 The ANDOR dataset
7 Experiments
7.1 Evaluation modes
7.2 Results
7.2.1 Zero-shot evaluation
7.2.2 Fine-tuned evaluation
7.2.3 Simultaneous SV-MV training
8 Discussion and Limitations
References
A Dataset Construction and Details
A.1 Encoding and relevance computation
A.2 Count sampling
A.3 Query suites and the nested width sweep
A.4 Corpus construction
A.5 Retrieval and relevance labels
A.6 Text rendering
A.7 Dataset statistics
A.8 Category and attribute vocabulary
B Additional Experimental Results
B.1 Model Settings
B.2 Training paradigms
B.3 Qwen, Snowflake and GTE-Modern Colbert Results
B.4 Variation across training widths
B.5 Jointly and Separately trained Jina representations

Knowls

Knowl 1 — Exponential Separation Between Single-Vector and Multi-Vector Retrieval Ordering
theoretical result
For any integer $m \ge 2$ , let $L = 4m^2$ , $n = mL = 4m^3$ , and $N = 176n$ . There exists a Boolean relevance matrix $R = \text{PM}(N, n, \text{MP}_{m,L}) \in \{0, 1 aus^{(2c)^n \times 2^N}$ based on the Minsky-Papert function $\text{MP}_{m, L}$ such that:
1. Any unit-norm single-vector embedding in $\mathbb{R}^d$ that preserves the retrieval ordering of $R$ (ranking every relevant document strictly above every irrelevant document) requires an embedding dimension of:
$d = 2^{\Omega(m)}$
1. In contrast, there exists a multi-vector representation using the Chamfer score (MaxSim) with a polynomial representation size of $O(m^6)$ per query and document ( $m$ vectors per query and $N = 4c m^3$ vectors per document, each in $\mathbb{R}^N$ ) that preserves the retrieval ordering of $R$ while achieving a relevance separation margin of $\Theta(m^{-2})$ between relevant and irrelevant documents.
Knowl 2 — Retrieval Ordering Problem and Vector Scoring
definition
Let $\mathcal{Q}$ denote a set of queries, $\mathcal{D}$ a set of documents, and $R \in \{0, 1\}^{|\mathcal{Q}| \times |\mathcal{D}|}$ a Boolean relevance matrix where $R(q, p) = 1$ if document $p$ is relevant to query $q$ and $R(q, p) = 0$ otherwise. The retrieval ordering problem requires designing vector representations for queries and documents alongside a similarity scoring function $\text{score}(q, p)$ such that every relevant document is scored strictly above every irrelevant document:
$\min_{p: R(q,p)=1} \text{score}(q, p) > \max_{p: R(q,p)=0} \text{score}(q, p) \quad \forall q \in \mathcal{Q}$
Two scoring paradigms are considered:
1. Single-vector representation: Assigns vector $q_i \in \mathbb{R}^d$ to query $i$ and vector $p_j \in \mathbb{R}^d$ to document $j$ , scoring similarity via the inner product $\langle q_i, p_j \rangle$ . If a single-vector representation of dimension $d$ preserves retrieval ordering, then $d + 1 \ge \text{sign-rank}(R)$ .
2. Multi-vector representation: Assigns a set of vectors $Q(i) = \{q_1, \dots, q_{L_Q}\}$ to query $i$ and a set of vectors $P(j) = \{p_1, \dots, p_{L_P}\}$ to document $j$ , scoring similarity via the Chamfer score (MaxSim):
$S(Q(i), P(j)) = \frac{1}{L_Q} \sum_{q \in Q(i)} \max_{p \in P(j)} \langle q, p \rangle$
Knowl 3 — Multi-Vector Construction for Minsky-Papert Pattern Matrices
model/method
Let $N = cn$ for an integer $c \ge 2$ , with $[N]$ partitioned into $n$ blocks $B_1, \dots, B_n$ of size $c$ . A query is indexed by a pair $(\mu, w)$ where $\mu \in \{0, 1\}^N$ is a block selector (satisfying $\sum_{t \in B_s} \mu_t = 1$ for all $s \in [n]$ ) and $w \in \{0, 1\}^n$ is a sign mask. A document is indexed by $x \in \{0, 1\}^N$ . The extracted string $y = \pi_\mu(x) \oplus w \in \{0, 1\}^n$ is viewed as an $m \times L$ array with $n = mL$ , evaluated under the Minsky-Papert function $\text{MP}_{m, L}(y) = \bigwedge_{i=1}^m \bigvee_{j=1}^L y_{(i-1)L+j}$ .

In $\mathbb{R}^N$ endowed with the standard basis $\{e_1, \dots, e_N\}$ :
1. The query $(\mu, w)$ is represented by $m$ unit vectors $Q(\mu, w) = \{q_1, \dots, q_m\}$ :
$q_i = \frac{1}{\sqrt{L}} \sum_{s=(i-1)L+1}^{iL} \left( (-1)^{w_s} \sum_{t \in B_s} \mu_t e_t \right)$
1. The document $x$ is represented by $N$ vectors $P(x) = \{p_j : j \in [N]\}$ :
$p_j = (-1)^{x_j + 1} e_j$
For each clause $i \in [m]$ , $\max_{p \in P(x)} \langle q_i, p \rangle = 1/\sqrt{L}$ if the $i$ -th clause is satisfied (the $i$ -th row of $y$ contains at least one 1), and $0$ otherwise. Consequently, the Chamfer score satisfies:
$S(Q(\mu, w), P(x)) = \begin{cases} \frac{1}{\sqrt{L}} & \text{if } \text{MP}_{m,L}(y) = 1 \\[6pt] \le \frac{m-1}{m\sqrt{L}} & \text{if } \text{MP}_{m,L}(y) = 0 \end{cases}$
Setting the decision threshold to $\gamma = \frac{m - 1/2}{m\sqrt{L}}$ achieves an exact separation margin of $\frac{1}{2m^2} = \Theta(m^{-2})$ .
Knowl 4 — Single-Vector Embedding for the NAND Pattern Matrix Retrieval Ordering
theoretical result
The relevance matrix $R = \text{PM}(N, n, \text{NAND}_n)$ defined by $R_{(\mu, w), x} = \text{NAND}_n(\pi_\mu(x) \oplus w)$ admits a unit-norm single-vector representation in dimension $N$ that preserves retrieval ordering with a relevance separation margin of $\frac{2}{\sqrt{nN}}$ between relevant and irrelevant documents.

For queries $(\mu, w)$ and documents $x \in \{0, 1\}^N$ , define:
$q_{\mu, w} = \frac{1}{\sqrt{n}} \sum_{s=1}^n \sum_{t \in B_s} \mu_t (-1)^{w_s} e_t, \qquad p_x = \frac{1}{\sqrt{N}} \sum_{t=1}^N (-1)^{x_t} e_t$
The inner product equals:
$\langle q_{\mu, w}, p_x \rangle = \frac{2r - n}{\sqrt{nN}}$
where $r = |\{s \in [n] : \pi_\mu(x)_s = w_s\}|$ is the number of coordinate matches. Because $\text{NAND}_n(\pi_\mu(x) \oplus w) = 1 \iff r \ge 1$ , setting the threshold $\gamma = \frac{1 - n}{\sqrt{nN}}$ yields:
$\langle q_{\mu, w}, p_x \rangle \ge \frac{2 - n}{\sqrt{nN}} > \gamma \iff R_{(\mu, w), x} = 1$
while irrelevant pairs have $\langle q_{\mu, w}, p_x \rangle = \frac{-n}{\sqrt{nN}} < \gamma$ . This establishes that score-approximation hardness under Chamfer distance does not imply hardness for the retrieval ordering objective.
Knowl 5 — ANDOR Retrieval Benchmark Specification
experimental setup
The ANDOR dataset is an e-commerce retrieval benchmark implementing compositional AND-of-OR semantics over 20 product categories (such as color, material, fit, style), each containing 20 discrete attribute options (400 attributes total).

Relevance rule: For a query $q$ specifying queried categories $\mathcal{C}_q$ and acceptable values $A_q(c)$ for each category $c \in \mathcal{C}_q$ , a document $d$ with attributes $V_d(c)$ is relevant if and only if:
$\forall c \in \mathcal{C}_q, \quad V_d(c) \cap A_q(c) \ne \emptyset$
Corpus and query parameters:
- Corpus: 50,000 product descriptions; exactly 10,000 documents for each category count in $\{11, 12, 13, 14, 15\}$ , with 2 to 4 attributes per present category (mean 38.71 total values per document).
- Test suites: 9 test suites sharing 1,000 query skeletons (querying 7, 8, or 9 categories). Query width (mean acceptable attributes per queried category) ranges from 3.5 to 11.5 using nested accept sets $A_{3.5}(c) \subset A_{4.5}(c) \subset \dots \subset A_{11.5}(c)$ . Every test query has exactly 2 relevant documents across all 9 widths.
- Hard negatives: 38,780 injected near-misses failing exactly $k \in \{1, 2, 3\}$ queried categories (level- $k$ negatives) and 9,220 random distractors.
- Training suites: 5 suites sharing 800 training queries (querying 5, 6, or 7 categories; training width from 5.5 to 9.5) with dense relevance labels.
Knowl 6 — General Contrastive Loss for Multi-Positive Retrieval Fine-Tuning
model/method
During retrieval fine-tuning, each query is scored against a batch of $D$ candidate documents containing $P$ positive documents. The model is trained using the contrastive loss:
$\mathcal{L} = \log \left( \sum_{d=1}^D e^{s_d / \tau} \right) - \frac{1}{P} \sum_{p=1}^P \frac{s_p}{\tau}$
where $\tau > 0$ is the softmax temperature and $s_d$ is the similarity score between the query and candidate document $d$ .
- At $P = 1$ , the loss is the InfoNCE cross-entropy loss against a single positive document.
- At $P = 2$ , the objective is a multi-positive loss that rewards both positive documents without penalizing the relative rank between them.
Knowl 7 — Collision Repair Algorithm for Synthetic Corpus Construction
algorithm
To ensure that synthetic positive and hard negative documents satisfy only their designated target query without introducing category distribution artifacts, candidate documents are repaired in place at the widest test suite.
Input: Candidate document d, target query q_target, test query set Q_test, category quota C_d
Output: Valid document d colliding with no query in Q_test \ {q_target}
collisions = {q in Q_test \ {q_target} : d satisfies q}
if collisions is empty then
    return d
for round = 1 to 100 do
    q_colliding = randomly select from collisions
    for category c in satisfied categories of q_colliding in random order do
        best_score = |collisions|
        best_values = current values of d in category c
        for attempt = 1 to 16 do
            redraw values of d in category c respecting construction constraints and C_d
            temp_collisions = {q in Q_test \ {q_target} : d satisfies q}
            if |temp_collisions| < best_score then
                best_score = |temp_collisions|
                best_values = redrawn values of d in category c
        set values of d in category c to best_values
    collisions = {q in Q_test \ {q_target} : d satisfies q}
    if collisions is empty then
        return d
discard document d and fail

Knowl 8 — Multi-Vector vs Single-Vector Performance on ANDOR

empirical result

Evaluating zero-shot and fine-tuned retrieval models on the ANDOR benchmark demonstrates that multi-vector models substantially outperform single-vector models across all query widths, and the separation persists even after task-specific fine-tuning.

Zero-shot baselines	Recall@2	Recall@10	Recall@100
Cohere v4	80.6%	93.8%	87.0%
Qwen3 Embedding 0.6B	352.2%	346.8%	223.8%
Snowflake Arctic Embed L v2	432.3%	396.9%	321.9%
OpenAI text-embedding-3-large	1662.1%	1204.5%	1025.0%
Mean gain	631.8%	510.5%	414.4%
Fine-tuned baselines	Recall@2	Recall@10	Recall@100
Qwen3 Embedding 0.6B	98.7%	92.4%	55.8%
Snowflake Arctic Embed L v2	100.1%	91.8%	59.7%
Mean gain	99.4%	92.1%	57.8%

The table reports relative gains of GTE ModernColBERT v1 over zero-shot and fine-tuned single-vector baselines. In zero-shot evaluation, GTE ModernColBERT achieves a 631.8% average relative gain in Recall@2 over single-vector models. After fine-tuning single-vector models (Qwen3 and Snowflake) on ANDOR training suites, GTE ModernColBERT maintains a ~99.4% relative gain in Recall@2 and a 57.8% gain in Recall@100 across test widths. While increasing test width (wider disjunctions) degrades recall across all models, multi-vector models preserve a consistent advantage.

Knowl 9 — Separation Persistence Under Joint Single- and Multi-Vector Head Training

empirical result

Using Jina Embeddings v4, where a 2048-dimensional single-vector (SV) head and a 128-dimensional/token multi-vector (MV) head are co-trained from the same backbone checkpoint on identical training batches, isolates representational expressiveness from training dynamics and parameter differences.

Key empirical findings from joint and independent training:

Fine-tuning the single-vector head only recovers the retrieval performance that untrained, zero-shot multi-vector late interaction already achieves at Recall@2.
Jointly fine-tuned MV leads jointly fine-tuned SV across all test widths, with relative advantages of 104.8% at Recall@2, 83.8% at Recall@10, and 61.5% at Recall@100 (evaluated at test width 3.5 after fine-tuning at training width 5.5).
When SV and MV heads are trained independently, the pooled multi-vector-to-single-vector performance ratios remain virtually identical (2.07 at Recall@2, 1.89 at Recall@10, 1.61 at Recall@100 under independent training vs 2.05, 1.84, 1.61 under joint training).

Coverage note — Omitted the exhaustive 20x20 category/attribute vocabulary catalog (Table 9), detailed cluster/GPU training environment settings (Table 12), and intermediate lemma derivations (Lemmas 1-4) that serve purely as intermediate steps for Theorems 1 and 2.

References

1.O. Ben-Yitzhak et al. ‘Beyond basic faceted search’. In: Proceedings of the 2008 International Conference on Web Search and Data Mining. 2008.
2.C. Campagnano, A. Mallia, and J. Pertschuk. Cascading retrieval with multi-vector representations: balancing efficiency and effectiveness. Pinecone. May 2025. url: https://www.pinecone.io/blog/cascading-retrieval-with-multi-vector-representations/.
3.A. Chaffin. GTE-ModernColBERT-v1. LightOn. Apr. 2025. url: https://huggingface.co/lightonai/GTE-ModernColBERT-v1.
4.Cohere. Introducing Embed 4: Multimodal Search for Business. Cohere. Apr. 2025. url: https://cohere.com/blog/embed-4.
5.L. Dhulipala et al. ‘MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding’. In: Advances in Neural Information Processing Systems. Vol. 37. 2024.
6.M. G¨unther et al. jina-embeddings-v4: Universal Embeddings for Multimodal Multilingual Retrieval. 2025. arXiv: 2506.18902 [cs.AI]. url: https://arxiv.org/abs/2506.18902.
7.R. Jayaram. Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings. 2026. arXiv: 2606.23475 [cs.DS]. url: https://arxiv.org/abs/2606.23475.
8.R. Jayaram et al. Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity. 2026. arXiv: 2607 . 20393 [cs.DS]. url: https : / /arxiv.org/abs/2607.20393.
9.V. Karpukhin et al. Dense Passage Retrieval for Open-Domain Question Answering. 2020. arXiv: 2004.04906 [cs.CL]. url: https://arxiv.org/abs/2004.04906.
10.O. Khattab and M. Zaharia. ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT. 2020. arXiv: 2004 . 12832 [cs.IR]. url: https ://arxiv.org/abs/2004.12832.
11.J. Killingback et al. Quantifying and Expanding the Theoretical Capacity of Late-Interaction Retrieval Models. 2026. arXiv: 2607.05803 [cs.IR]. url: https://arxiv.org/abs/2607.05803.
12.LanceDB. Late Interaction & Efficient Multi-modal Retrievers Need More Than a Vector Index. LanceDB. 2024. url: https : / / www . lancedb . com / blog / late - interaction -efficient-multi-modal-retrievers-need-more-than-just-a-vector-index.
13.K. Lukawski. Late Interaction Retrieval with Dense Token Embeddings. Qdrant. Aug. 2024. url: https://qdrant.tech/articles/late-interaction-models/.
14.Mixedbread Team. Inside Mixedbread: How We Built Multimodal Late-Interaction at Billion Scale. Mixedbread. Jan. 2026. url: https : / / www . mixedbread . com / blog / multimodal -late-interaction-billion-scale.
15.A. van den Oord, Y. Li, and O. Vinyals. Representation Learning with Contrastive Predictive Coding. 2018. arXiv: 1807.03748 [cs.LG]. url: https://arxiv.org/abs/1807.03748.
16.OpenAI. New Embedding Models and API Updates. OpenAI. Jan. 2024. url: https : / /openai.com/index/new-embedding-models-and-api-updates/.
17.A. A. Razborov and A. A. Sherstov. ‘The Sign-Rank of AC0’. In: SIAM Journal on Computing 39.5 (2010), pp. 1833–1855. doi: 10.1137/080744037. eprint: https://doi.org/10.1137/080744037. url: https://doi.org/10.1137/080744037.
18.A. S et al. On Strengths and Limitations of Single-Vector Embeddings. 2026. arXiv: 2603.29519 [cs.IR]. url: https://arxiv.org/abs/2603.29519.
19.K. Santhanam et al. ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction. 2022. arXiv: 2112.01488 [cs.IR]. url: https://arxiv.org/abs/2112.01488.
20.A. A. Sherstov. ‘The Pattern Matrix Method’. In: SIAM Journal on Computing 40.6 (2011), pp. 1969–2000.
21.A. A. Sherstov and P. Wu. Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0. 2019. arXiv: 1901.00988 [cs.CC]. url: https://arxiv.org/abs/1901.00988.
22.K. Sohn. ‘Improved Deep Metric Learning with Multi-class N-pair Loss Objective’. In: Advances in Neural Information Processing Systems (NeurIPS). 2016.
23.G. Storli, T. Egge, and J. K. Bergum. Revolutionizing Semantic Search with Multi-Vector HNSW Indexing in Vespa. Vespa. Mar. 2023. url: https://blog.vespa.ai/semantic-search-with-multi-vector-indexing/.
24.D. Tunkelang. Faceted Search. Synthesis Lectures on Information Concepts, Retrieval, and Services. Springer, 2009.
25.D. Vandic, F. Frasincar, and U. Kaymak. ‘Facet selection algorithms for web product search’. In: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. 2013.
26.O. Weller et al. On the Theoretical Limitations of Embedding-Based Retrieval. 2025. arXiv: 2508.21038 [cs.IR]. url: https://arxiv.org/abs/2508.21038.
27.P. Yu et al. Arctic-Embed 2.0: Multilingual Retrieval Without Compromise. 2024. arXiv: 2412.04506 [cs.IR]. url: https://arxiv.org/abs/2412.04506.
28.Y. Zhang et al. Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models. 2025. arXiv: 2506.05176 [cs.CL]. url: https://arxiv.org/abs/2506.05176.

Citation

MLA

Agarwal, M., et al. “Retrieval Needs Multivectors: An Exponential Separation”. arXiv, 2026, http://arxiv.org/abs/2608.21494v1.

APA

Agarwal, M., Agrawal, V., Basu, S., Garg, A., & Shiragur, K. (2026). Retrieval Needs Multivectors: An Exponential Separation. arXiv. http://arxiv.org/abs/2608.21494v1

Chicago

Agarwal, M., V. Agrawal, S. Basu, A. Garg, and K. Shiragur. 2026. “Retrieval Needs Multivectors: An Exponential Separation”. arXiv. http://arxiv.org/abs/2608.21494v1.

Harvard

Agarwal, M. et al. (2026) “Retrieval Needs Multivectors: An Exponential Separation”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2608.21494v1.

Vancouver

1. Agarwal M, Agrawal V, Basu S, Garg A, Shiragur K (2026) Retrieval Needs Multivectors: An Exponential Separation. arXiv

BibTeX

@article{agarwal2026retrieval,
  title = {Retrieval Needs Multivectors: An Exponential Separation},
  author = {Agarwal, Mihir and Agrawal, Viraj and Basu, Sabyasachi and Garg, Ankit and Shiragur, Kirankumar},
  year = {2026},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2608.21494v1},
  eprint = {2608.21494}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-sa/4.0/

Baseline comparison (Jina v4 MV)	Recall@2	Recall@10	Recall@100
Over SV fine-tuned	104.8%	83.8%	61.5%
Over SV zero-shot	1613.8%	1263.3%	767.5%

Retrieval Needs Multivectors: An Exponential Separation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Exponential Separation Between Single-Vector and Multi-Vector Retrieval Ordering

Knowl 2 — Retrieval Ordering Problem and Vector Scoring

Knowl 3 — Multi-Vector Construction for Minsky-Papert Pattern Matrices

Knowl 4 — Single-Vector Embedding for the NAND Pattern Matrix Retrieval Ordering

Knowl 5 — ANDOR Retrieval Benchmark Specification

Knowl 6 — General Contrastive Loss for Multi-Positive Retrieval Fine-Tuning