Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings

• URL: http://arxiv.org/abs/2606.23475v1
• Date: Mon, 22 Jun 2026 15:22:05 GMT
• Title: Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings
• Abstract summary: We show that MV embeddings can express similarities which cannot even be approximately represented by single vector embeddings.<n>Our results confirm a long-held belief in the IR community: at a fixed representation size, multi-vector embeddings can express similarities which cannot even be approximately represented by single vector embeddings.
• Score: 5.90432887297327
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-vector (MV) embeddings have become a powerful paradigm in neural information retrieval (IR), achieving high retrieval accuracy by representing data with multiple vectors and scoring them via the non-linear Chamfer similarity. Despite their widely perceived superiority over single-vector (SV) embeddings which use inner product similarity, to date there is no formal proof that SV similarities cannot approximate MV similarities with the same representation size. Specifically, we ask the following: for any bounded dataset size $n \leq 2^{poly(m)}$, what is the smallest dimension $D$ so that given any collection of MV embeddings $Q_1,\dots,Q_n,X_1,\dots,X_n \subset \mathbb{R}^d$ containing at most $m$ vectors each, there always exist $q_1,\dots,q_n$, $d_1,\dots,d_n \in \mathbb{R}^{D}$ satisfying $|\langle q_i, d_j \rangle - \texttt{Chamfer}(Q_i,X_j)| \leq ε$ for all $i,j$? Recently, the MUVERA algorithm demonstrated that $D = m^{O(1/ε^2)}$ is possible. If improved to $D = md$, this would imply that MV embeddings are no more expressive than SV embeddings. In this paper, we rule out this scenario. Specifically, we prove the existence of a collection of MV embeddings in $\mathbb{R}^d$, each containing at most $m$ vectors, which require single-vector dimension of $D =(ε^2 m)^{Ω(1/ε)}$ to approximate, establishing a strong separation in representation size between MV and SV embeddings. Our proof leverages the Pattern Matrix Method by constructing a hard instance whose Chamfer similarity matrix encodes the $NAND_k$ boolean function. Our results confirm a long-held belief in the IR community: at a fixed representation size, multi-vector embeddings can express similarities which cannot even be approximately represented by single vector embeddings.

Related papers

• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval [99.8640829555514]
  This paper studies the minimal dimension required to embed subset memberships ($m$ elements and $mchoose k$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED)<n>The tight bounds of MED are derived theoretically and supported empirically for various notions of "distances" or "similarities," including the $ell$ metric, inner product and cosine similarity.
  arXiv  Detail & Related papers  (2026-01-28T18:45:43Z)
• On the Emergence of Linear Analogies in Word Embeddings [8.981531144549129]
  Models such as Word2Vec and GloVe construct word embeddings based on the co-occurrence probability $P(i,j)$ of words $i$ and $j$ in text corpora.<n>We introduce a theoretical generative model in which words are defined by binary semantic attributes, and co-occurrence probabilities are derived from attribute-based interactions.
  arXiv  Detail & Related papers  (2025-05-24T11:42:26Z)
• Multi-thresholding Good Arm Identification with Bandit Feedback [1.079960007119637]
  We consider a good arm identification problem in a bandit setting with multi-objectives.<n>We propose the Multi-Thresholding UCB(MultiTUCB) algorithm with a sample complexity bound.
  arXiv  Detail & Related papers  (2025-03-13T14:04:04Z)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors [47.927989749887864]
  We study beyond worst-case dimensionality reduction for $s$-sparse vectors.<n>For any collection $X$ of $s$-sparse vectors in $mathbbRO(s2)$, there exists a linear map to $mathbbRO(s2)$ which emphexactly preserves the norm of $99%$ of the vectors in $X$ in any $ell_p$ norm.<n>We show that both the non-linearity of $f$ and the non-negativity of $
  arXiv  Detail & Related papers  (2025-02-27T08:17:47Z)
• On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of $\mathbb{R}^N$ with Boundary [0.4125187280299246]
  We consider the probability that a random matrix $A in mathbbRm times N$ will serve as a bi-Lipschitz function $A: mathcalM rightarrow mathbbRm$ with bi-Lipschitz constants close to one. We present a new class of highly structured distributions for embedding sufficiently low-dimensional submanifolds of $mathbbRN$.
  arXiv  Detail & Related papers  (2021-10-08T15:27:52Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems [58.83118651518438]
  We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $boldsymbolumathrmTboldsymbolMboldsymbolv$ over a fixed field. We provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs.
  arXiv  Detail & Related papers  (2020-06-24T19:33:49Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)

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.