Retrieval Needs Multivectors: An Exponential Separation

• URL: http://arxiv.org/abs/2608.21494v1
• Date: Fri, 21 Aug 2026 13:26:44 GMT
• Title: Retrieval Needs Multivectors: An Exponential Separation
• Abstract summary: We introduce ANDOR, a new retrieval benchmark that naturally instantiates these hard examples.<n>We show that state-of-the-art single-vector embedding models perform poorly on ANDOR in the zero-shot setting.<n>In contrast, multi-vector models consistently outperform their single-vector counterparts and improve substantially with fine-tuning.
• Score: 14.201575154107294
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• DocRetriever: A Plug-and-Play Framework for Multimodal Document Retrieval with Comprehensive Benchmark [48.84943754804533]
  Multimodal documents contain diverse elements, such as tables, figures, and layouts.<n>Current approaches typically combine dense visual embedding models with supervised rerankers to achieve high-precision retrieval.<n>We propose DocRetriever, a plug-and-play framework that enhances visual retrieval via a layout-aware sparse embedding technique.
  arXiv  Detail & Related papers  (2026-05-28T14:50:53Z)
• On Strengths and Limitations of Single-Vector Embeddings [13.712240635014775]
  We show that dimensionality alone cannot explain the observed failures.<n>We find that domain shift and misalignment between embedding similarities and the task's underlying notion of relevance are major contributors.
  arXiv  Detail & Related papers  (2026-03-31T10:04:54Z)
• Measuring Orthogonality in Representations of Generative Models [81.13466637365553]
  In unsupervised representation learning, models aim to distill essential features from high-dimensional data into lower-dimensional learned representations. Disentanglement of independent generative processes has long been credited with producing high-quality representations. We propose two novel metrics: Importance-Weighted Orthogonality (IWO) and Importance-Weighted Rank (IWR)
  arXiv  Detail & Related papers  (2024-07-04T08:21:54Z)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Refine, Discriminate and Align: Stealing Encoders via Sample-Wise Prototypes and Multi-Relational Extraction [57.16121098944589]
  RDA is a pioneering approach designed to address two primary deficiencies prevalent in previous endeavors aiming at stealing pre-trained encoders. It is accomplished via a sample-wise prototype, which consolidates the target encoder's representations for a given sample's various perspectives. For more potent efficacy, we develop a multi-relational extraction loss that trains the surrogate encoder to Discriminate mismatched embedding-prototype pairs.
  arXiv  Detail & Related papers  (2023-12-01T15:03:29Z)
• Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality [84.94877848357896]
  Recent datasets expose the lack of the systematic generalization ability in standard sequence-to-sequence models. We analyze this behavior of seq2seq models and identify two contributing factors: a lack of mutual exclusivity bias and the tendency to memorize whole examples. We show substantial empirical improvements using standard sequence-to-sequence models on two widely-used compositionality datasets.
  arXiv  Detail & Related papers  (2022-11-28T17:36:41Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• Efficient Iterative Amortized Inference for Learning Symmetric and Disentangled Multi-Object Representations [8.163697683448811]
  We introduce EfficientMORL, an efficient framework for the unsupervised learning of object-centric representations. We show that optimization challenges caused by requiring both symmetry and disentanglement can be addressed by high-cost iterative amortized inference. We demonstrate strong object decomposition and disentanglement on the standard multi-object benchmark while achieving nearly an order of magnitude faster training and test time inference.
  arXiv  Detail & Related papers  (2021-06-07T14:02:49Z)
• Learning Ising models from one or multiple samples [26.00403702328348]
  We provide guarantees for one-sample estimation, quantifying the estimation error in terms of the metric entropy of a family of interaction matrices. Our technical approach benefits from sparsifying a model's interaction network, conditioning on subsets of variables that make the dependencies in the resulting conditional distribution sufficiently weak.
  arXiv  Detail & Related papers  (2020-04-20T15:17:05Z)
• Better Set Representations For Relational Reasoning [30.398348643632445]
  relational reasoning operates on a set of entities, as opposed to standard vector representations. We propose a simple and general network module called a Set Refiner Network (SRN)
  arXiv  Detail & Related papers  (2020-03-09T23:07:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.