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

arXiv: https://arxiv.org/abs/2607.20393 · HTML: https://mlsanity.com/paper/2607.20393/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2026.

## Built on by (most cited first, 5 of 5)

- [Retrieval Needs Multivectors: An Exponential Separation](https://mlsanity.com/paper/2608.21494/) (2026)
- [EigenLI: Spectral Approximations to Late Interaction](https://mlsanity.com/paper/2609.07561/) (2026)
- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)
- [Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention](https://mlsanity.com/paper/2608.11427/) (2026)
- [Simple Linear Corrections for Compression in Late Interaction](https://mlsanity.com/paper/2610.14196/) (2026)

## Abstract (arXiv)

Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner products. For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP). In our setting, MUVERA gives dimension mO(1/ε2) [DHJ+24], whereas the previous lower bound (ε2m)Omega(1/ε) [Jay26] left a gap between 1/ε and 1/ε2 in the exponent of m. We nearly close this gap. For every fixed δ∈(0,1), there are constants Aδ,cδ>0 such that, for all sufficiently small ε>0 and every m≥(1/ε)Aδ, there exist unit query vectors and document point clouds of at most m unit vectors for which every single-vector approximation of all pairwise MAX-IP values to additive error ε has dimension [ D ≥ m^cδ/ε2-2δ. ] This holds even for fully data-dependent representations chosen after seeing the dataset. It also applies to Chamfer because all queries are singletons. Since δ can be arbitrarily small, the exponent approaches the O(1/ε2) dependence of the upper bound. The proof combines Sherstov's pattern matrix method with polynomial-size, constant-width DNF formulas computing functions of approximate degree Omega(k1-δ). Uniform-width padding and a block encoding create an Omega(ε) gap. A dummy coordinate then equalizes all false inputs, yielding a unit-sphere MAX-IP matrix that is an exact two-valued affine image of the DNF pattern matrix with gap at least 8ε. This allows the approximate-rank bound to apply. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.