PaperlayerView exact revision on arXiv

Source-linked AI summary

Retrieval Needs Multivectors: An Exponential Separation

Mihir Agarwal, Viraj Agrawal, Sabyasachi Basu, Ankit Garg, Kirankumar Shiragur

arXiv:2608.21494v1cs.IRcs.DBcs.LG

TL;DR

The paper asks whether multi-vector representations are fundamentally more expressive than single-vector embeddings for retrieval orderings. It proves an exponential separation and introduces ANDOR, where multi-vector models outperform single-vector models, including after fine-tuning.

  • Problem

    Whether multi-vector representations are fundamentally more expressive than single-vector embeddings for preserving retrieval orderings remains unresolved.

  • Method

    The paper constructs relevance matrices with polynomial-size multi-vector representations but exponential-dimensional single-vector representations, then develops ANDOR as a semantic benchmark inspired by this construction.

  • Results

    Multi-vector models outperform single-vector models by 2-10× zero-shot and 2× after fine-tuning on ANDOR.

  • Takeaways & Limitations

    ANDOR reveals a persistent expressiveness gap between single-vector and multi-vector retrieval models, including when models are co-trained under identical circumstances.

  • Takeaways & Limitations

    Although ANDOR has exactly two positive documents per test query, its existential 5-dimensional single-vector realization assumes the complete relevance matrix and does not provide a practical procedure for learning semantic embeddings.

Abstract

from arXiv · show

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.

1 Introduction

The paper establishes an explicit exponential separation between single-vector and multi-vector retrieval for preserving document orderings, then derives ANDOR as a benchmark that exposes this gap empirically.

  • Representational gap: Multi-vector retrieval retains token-level vector sets and scores query-document relevance with Chamfer matching, unlike single-vector dot-product similarity.This distinction motivates studying whether multi-vector representations are fundamentally more expressive.
  • Open question: Existing theory characterizes single-vector dimension through sign-rank but does not establish the representational power of multi-vector embeddings.Prior exponential separations concern preserving Chamfer scores, a stronger requirement than preserving document orderings.
  • Main contribution: The paper constructs relevance matrices with polynomial-size multi-vector representations but requiring exponential-dimensional single-vector embeddings to rank every relevant document above every irrelevant one.The result targets retrieval orderings rather than numerical score approximation.
  • Benchmark: ANDOR translates the theoretical structure into shopping retrieval with conjunctions of disjunctions and preserves a performance gap after fine-tuning.Multi-vector models outperform single-vector models by 2-10× zero-shot and 2× after fine-tuning.

2 Related Work

Related work studies single-vector failure cases, multi-vector score-approximation hardness, and benchmarks whose gaps may shrink with fine-tuning. This paper distinguishes those results from ordering hardness and introduces a complementary compositional benchmark.

  • Retrieval models: Dense retrieval maps each query and document to one vector, whereas late-interaction models retain token-level embeddings and use Chamfer scoring.ColBERT and ColBERTv2 exemplify the late-interaction approach.
  • Single-vector limitations: Prior worst-case analyses and LIMIT show that strong single-vector models can perform poorly, but do not formally prove a single-vector versus multi-vector separation.Controlled experiments also indicate that dimensionality alone does not fully explain LIMIT behavior.
  • Theoretical context: Earlier theory establishes exponential hardness for approximating Chamfer similarity scores with ordinary inner products.That objective is stronger than merely preserving relevant-over-irrelevant document orderings.
  • Benchmark context: ANDOR uses conjunctions of disjunctions over product attributes, providing a compositional e-commerce setting complementary to existing benchmarks.Its structure reflects multifaceted search.

3 Preliminaries

The preliminaries formalize relevance matrices, single-vector and multi-vector scoring, and the retrieval-ordering objective. Pattern matrices and sign-rank provide the machinery for proving single-vector dimension lower bounds.

  • Problem setup: A relevance matrix R records whether each document is relevant to each query, and retrieval ordering requires every relevant document to score above every irrelevant document.The framework studies vector representations together with their scoring metrics.
  • Representations: Single-vector representations assign one d-dimensional vector to each query and document and score pairs by inner product.This is the baseline representation used in the ordering problem.
  • Representations: Multi-vector representations assign sets of vectors to queries and documents and use Chamfer scoring to compare them.The score matches query vectors to their most similar document vectors.
  • Pattern matrices: Pattern matrices partition N coordinates into n blocks, with selectors extracting one coordinate from each block before applying a Boolean function.The construction uses Minsky-Papert and NAND functions.
  • Sign-rank: If a d-dimensional single-vector representation preserves retrieval ordering, then d + 1 is at least the relevance matrix’s sign-rank.Sign-rank lower bounds therefore translate into embedding-dimension lower bounds.
  • Sign-rank: For the specified pattern matrix, the sign-rank is 2^Omega(m), supplying the exponential lower-bound ingredient.This lemma is used to argue about the required single-vector dimension.

4 Overview of Results

The paper proves an exponential ordering separation and evaluates its semantic analogue in ANDOR. Across models and settings, multi-vector retrieval maintains a substantial advantage, including after controlled fine-tuning.

  • Theoretical result: Theorem 1 gives a relevance matrix requiring single-vector dimension d = 2^Omega(m), while polynomial-size multi-vector embeddings preserve ordering with O(m^6) representation size.The multi-vector construction achieves a relevance separation margin of Theta(m^-2).
  • Relation to prior theory: The result complements prior Chamfer-score hardness because score-approximation hardness does not automatically imply hardness for retrieval ordering.The earlier hard instance admits an N-dimensional single-vector representation preserving ordering.
  • ANDOR: ANDOR translates the Boolean construction into e-commerce retrieval with product attributes, mandatory constraints, hard negatives, and variable query width.The benchmark tests compositional AND-of-OR semantics over a corpus of 50,000 products.
  • Empirical results: After fine-tuning, multi-vector models retain a significant lead across settings, with relative margins up to 153% for Recall@2 and 96% for Recall@100.The controlled Jina comparison updates both heads from the same checkpoint, isolating representation effects.

5 Proofs

The proof constructs a polynomial-size multi-vector representation for an AND-of-OR relevance matrix and proves that any ordering-preserving single-vector representation requires exponential dimension.

  • Multi-vector construction: The construction arranges n = mL Boolean variables into an m × L matrix, with each row representing a clause and relevance requiring every row to contain a 1.The Minsky-Papert function takes the OR of each row and then the AND across rows.
  • Multi-vector construction: Each query is represented by m clause vectors, while documents are represented by coordinate vectors whose inner products detect satisfied literals.The query vectors encode clause-specific signs and selected coordinates; document vectors encode bit values.
  • Multi-vector construction: The Chamfer score separates relevant from irrelevant pairs because every satisfied clause contributes a maximum of 1/L, whereas an unsatisfied clause contributes 0.A threshold between the two resulting values reconstructs the relevance matrix exactly.
  • Single-vector lower bound: Any ordering-preserving single-vector representation of the constructed matrix requires dimension d = 2^Ω(m), via a sign-rank witness derived from the thresholded inner-product matrix.The witness perturbs query-dependent thresholds so that all entries are nonzero, positive for relevant pairs, and negative for irrelevant pairs.
  • Main separation: The multi-vector representation has polynomial size O(m6) per query and document, sharply contrasting with the exponential single-vector lower bound.The construction uses m query vectors and N = 4cm3 document vectors, yielding representation size O(N2) = O(m6).
  • Main separation: The construction achieves a relevant–irrelevant Chamfer-score gap of Θ(m−2) after setting L = 4m2.The gap is obtained from a base separation of at least 1/(mL).

6 The ANDOR dataset

ANDOR instantiates the paper’s AND-of-OR construction as a faceted shopping benchmark, using realistic product attributes, controlled query widths, and challenging hard negatives.

  • Dataset design: ANDOR models shopping queries with twenty filter groups, each offering twenty possible attribute values.Filters correspond to product categories such as color or material.
  • Relevance rule: A document is relevant only when it matches at least one accepted attribute in every queried category.Categories combine with AND, while acceptable values within each category combine with OR.
  • Evaluation design: Train and test suites vary mean attributes per category, with test widths spanning 3.5 to 11.5 and training widths spanning 5.5 to 9.5.Each setting contains 1,000 test queries and 800 training queries; test queries have exactly two positive documents.
  • Evaluation design: The benchmark includes hard negatives that violate exactly k queried categories, alongside random distractors and designated positives.This prevents success through partial matches or simple heuristics.
  • Dataset rationale: ANDOR uses the same Boolean predicate as the theoretical construction while remaining interpretable as realistic faceted shopping queries.The dataset is designed to evaluate compositional AND-of-OR semantics.

7 Experiments

The experiments evaluate single-vector and multi-vector retrieval models on ANDOR across zero-shot and fine-tuned settings, widths, and recall cutoffs. Multi-vector models maintain substantial advantages, including in controlled comparisons using the same Jina model.

  • Evaluation setup: Seven retrieval models are evaluated on ANDOR, including two multi-vector modes and five single-vector models.The multi-vector models are GTE ModernColBERT v1 and Jina Embeddings v4 in late-interaction mode; the single-vector models include Jina, Qwen3, Snowflake Arctic, Cohere, and OpenAI embeddings.
  • Evaluation setup: Zero-shot evaluation scores the full 50,000-document corpus across nine suites of 1,000 queries spanning different widths.Single-vector models use cosine similarity, while multi-vector models use Chamfer score.
  • Results across widths: Across Figure 3’s nine test widths and three recall cutoffs, multi-vector models consistently outperform single-vector models, while both approaches decline as test width increases.The figure reports zero-shot results and results after fine-tuning at a training width of 9.5.
  • Zero-shot evaluation: GTE ModernColBERT achieves relative gains of about 81% in Recall@2 and 87% in Recall@100 over Cohere in zero-shot evaluation.Cohere is the strongest single-vector model at all test widths, while the other single-vector models are substantially worse.
  • Fine-tuned evaluation: After fine-tuning, ColBERT maintains margins of about 99% for Recall@2 and 58% for Recall@100 across the complete train–test grid and two single-vector baselines.The gap persists although fine-tuning improves single-vector models; at test width 3.5, GTE ModernColBERT reaches roughly 89–93% Recall@100 across training widths.
  • Simultaneous SV-MV training: Jina’s fine-tuned multi-vector head leads its fine-tuned single-vector head at all test widths, with relative gains of 105%, 84%, and 62% for Recall@2, Recall@10, and Recall@100.The comparison updates both heads from the same checkpoint, isolating representation mode while holding architecture, training data, and parameter count identical.

8 Discussion and Limitations

The paper's semantic benchmark mirrors the theoretical expressiveness gap, while identifying limitations in task scope and open questions about approximate or fully specified rankings.

  • ANDOR is a semantic e-commerce instantiation inspired by, but distinct from, the proof's pattern-matrix construction.
  • The authors report that ANDOR exposes an expressiveness gap in realistic semantic retrieval despite sparse relevance and a simple underlying rule.
  • Increasing test width consistently degrades retrieval performance across all methods, possibly because wider disjunctions increase representational demands.The paper leaves detailed investigation of this phenomenon to future work.
  • Every ANDOR test query has exactly two positive documents, so an existential 5-dimensional single-vector representation exists when the complete relevance matrix is available.This does not provide a practical procedure for learning semantic embeddings from queries and documents.
  • The proof establishes a separation for ranking relevant documents above irrelevant ones, leaving approximate retrieval ordering and specified per-query rankings as open directions.

A Dataset Construction and Details

ANDOR encodes conjunctions of category-level disjunctions with controlled masks, nested query widths, balanced document construction, and relevance-aware labeling.

  • Each document is a row of 20 category masks, each category uses 20 attribute bits, and the corpus contains 50,000 documents.Queries use the same representation.
  • Relevance is computed by requiring nonzero bitwise overlap in every queried category.The vectorized expression checks both within-category disjunctions and across-category conjunctions.
  • Test queries use maximum-entropy count distributions; at range 2–6 with mean 3.5, r = 0.77 and probabilities decline from 0.31 to 0.11.This makes narrow disjunctions more likely than wide ones.
  • Nine query-width suites share queries and widen accept sets by adding values, preserving exactly two relevant documents per test query.Nested accept sets let positives and hard negatives retain their relevance status across widths.
  • The corpus fixes category-count quotas, adds controlled distractors, repairs collisions, and permutes documents to remove construction-order signals.
  • Hard negatives miss 1, 2, or 3 queried categories, while negatives never omit queried categories, preventing models from succeeding by category counting alone.
  • Relevant-document grades combine normalized extra overlap with a deterministic document-quality tie-breaker; both test positives receive grade 2.
  • Human-readable documents mention every held attribute, use “or” within categories and “and” across categories, and conceal absent categories.

B.2 Training paradigms

The experiments compare single-vector, late-interaction, joint, and separately trained paradigms under shared fine-tuning conditions and system settings.

  • All fine-tuning runs use 800 training queries, 6,250 optimizer steps, effective batch 32, and 32 scored candidates per query.
  • The experiments use shared optimization and truncation settings, with final reported results taken from checkpoint 6,250.
  • P1 and P2: single-vector baselines: Qwen3 Embedding 0.6B and Snowflake Arctic Embed L v2 are single-vector baselines trained with a multi-positive objective and cosine similarity.
  • P3: late interaction: GTE ModernColBERT v1 retains one vector per token and uses length-normalized MaxSim scores in a one-positive training objective.
  • P4: joint single- and multi-vector training: Jina Embeddings v4 jointly trains single-vector and multi-vector heads using Matryoshka losses, multi-vector scores, and symmetric KL coupling.
  • P5: separately trained single- and multi-vector models: P5 trains single-vector and multi-vector representations as independent runs with scoring-function-specific settings.

B.3 Qwen, Snowflake and GTE-Modern Colbert Results

Performance declines as test widths increase, with late interaction generally degrading less than the single-vector baselines across recall, nDCG, and MRR.

  • Recall: 91.4% to 25.4%: GTE ModernColBERT's Recall@100 falls across test widths 3.5 to 11.5, a 66.0 pp loss and 3.6× decrease.
  • Recall: 1.75×: GTE ModernColBERT's maximum Recall@100 ratio lead over the stronger single-vector model occurs at test width 7.5.Its absolute lead reaches 27.3 pp at width 4.5 and narrows to 7.6 pp at width 11.5.
  • nDCG: 4.9×, 4.7×, and 6.6×: nDCG@100 decreases for ColBERT, Qwen3, and Snowflake, respectively, from test width 3.5 to 11.5.Relevant documents found at deep cutoffs on wide suites increasingly occur at poor ranks.
  • nDCG: nDCG@2 stays within 8% of Recall@2 across the grid because every test query has exactly two relevant documents.
  • MRR: Roughly 80%: pooled over the train–test grid, late interaction leads the single-vector models on MRR by this relative margin.Snowflake loses an order of magnitude from the narrowest to widest suite, while the other models lose about a factor of six.

B.4 Variation across training widths

Training on wider queries substantially improves robustness to wide test suites while having little cost on narrow ones, although optimal training width varies by model.

  • At test width 11.5, ColBERT Recall@100 rises from 17.10% to 32.50% as training width increases from 5.5 to 9.5.This is a 15.40 percentage-point or 90% relative improvement.
  • At test width 3.5, ColBERT spans only 3.45 percentage points across training widths, from 92.55% at 5.5 to 89.10% at 9.5.
  • ColBERT and Snowflake improve monotonically with training width, peaking at 9.5, whereas Qwen3 peaks at 7.5 and is the most sensitive.Matching training width to test width is therefore not generally optimal.
  • ColBERT remains above both single-vector models at every training and test width.

B.5 Jointly and Separately trained Jina representations

Across jointly and independently trained Jina representations, multi-vector retrieval preserves a substantial advantage over single-vector retrieval across widths and evaluation metrics.

  • Cross-model consistency: Recall, nDCG, and MRR decrease monotonically as test suites widen, while multi-vector representations lead single-vector representations at all 45 train–test combinations and every cutoff.
  • Cross-model consistency: The multi-vector lead is widest at shallow cutoffs, roughly doubling Recall@2 and adding about 60% at Recall@100.nDCG and MRR fall between these Recall margins.
  • Cross-model consistency: Fine-tuning lifts the single-vector representation far more in relative terms, but its absolute gain shrinks steadily as suites widen.
  • Joint versus independent training: Independent training raises grid-mean Recall@100 by about 4% relative for both representations, while their separation changes little.
  • Joint versus independent training: The performance gap survives joint and independent training, but the two settings are not a clean ablation because corrected reruns also changed temperature and learning rate.
Loading 2608.21494v1…