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

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.