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

Neural Information Retrieval (IR) has shifted from single-vector (SV) models, which represent data as a single point in space, to multi-vector (MV) models, which represent data as a set of vectors (a point-cloud) scored via Chamfer similarity. While MV models consistently outperform SV models on benchmarks, it has remained an open theoretical question whether this superiority is fundamental or if a sufficiently high-dimensional SV model could approximate any MV model. This paper addresses whether MV embeddings are provably more expressive than SV embeddings at a fixed representation size.

The author investigates the dimensionality $D$ required for a single-vector model to approximate the Chamfer similarity of two sets of $m$ vectors in $d$ dimensions. The paper utilizes the Pattern Matrix Method, a technique from communication complexity, to construct a hard instance where the Chamfer similarity matrix encodes the $NAND_k$ boolean function. By lower-bounding the approximate rank of this matrix, the author determines the minimum dimension $D$ required for any single-vector approximation.

The study proves that any single-vector approximation of the Chamfer similarity requires a dimension of $D = (\epsilon^2 m)^{\Omega(1/\epsilon)}$. This result establishes a strong separation between MV and SV embeddings: for any constant error tolerance $\epsilon$, the required dimension for an SV model grows polynomially with $m$, and for $\epsilon = 1/poly(m)$, it grows exponentially. This confirms that multi-vector models can express complex similarities that are fundamentally inaccessible to single-vector models of the same size, providing a theoretical foundation for the continued use of multi-vector architectures in IR.