AI summaryⓘ
The authors study two ways to represent data for search tasks: using multiple vectors per item (multi-vector embeddings) versus just one vector (single-vector embeddings). They prove that multi-vector embeddings can express certain similarity measures that single-vector embeddings cannot approximate well unless the single-vector dimension is extremely large. This means multi-vector embeddings are fundamentally more powerful for representing complex similarities at the same storage size. Their proof uses a mathematical tool called the Pattern Matrix Method and encodes a complex Boolean function to demonstrate this difference formally. These results confirm what many in information retrieval suspected but hadn't rigorously shown before.
multi-vector embeddingssingle-vector embeddingsChamfer similarityneural information retrievalPattern Matrix Methodrepresentation dimensionboolean functionsNAND functionapproximate similarityembedding expressiveness
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.