Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

In modern information retrieval, multi-vector embeddings (like those used in ColBERT) represent data items as sets of vectors to capture fine-grained interactions, which are then aggregated via Chamfer similarity. A central question is whether these complex multi-vector structures can be compressed into a single-vector representation (using standard inner products) without significant loss of accuracy. This paper investigates the minimum dimension $D$ required for such single-vector surrogates to approximate the MAX-IP (a special case of Chamfer similarity) within an additive error $\epsilon$.

The authors utilize the pattern matrix method, a powerful technique in communication complexity and circuit theory. They construct a MAX-IP matrix that acts as an affine image of a pattern matrix derived from a specific Boolean function. To achieve a tight lower bound, they employ a polynomial-size, constant-width DNF formula with high approximate degree. By carefully padding these formulas to ensure exact width and using a block-encoding strategy, they construct a set of query and document vectors that force any single-vector approximation to have a high rank, directly corresponding to the required embedding dimension.

The study proves that for any fixed $\delta > 0$, the dimension $D$ required to approximate MAX-IP to additive error $\epsilon$ is at least $m^{\Omega(1/\epsilon^{2-2\delta})}$. Since $\delta$ can be chosen to be arbitrarily small, this lower bound approaches the $O(1/\epsilon^2)$ upper bound established by previous work (MUVERA). This confirms that the high dimensionality required for single-vector surrogates is an inherent limitation of the representation, rather than a deficiency of existing embedding algorithms.