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

Abstract

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 $m^{O(1/\hat{I}{\mu }^2)}$ [DHJ+24], whereas the previous lower bound $(\hat{I}{\mu }^{2}m{)}^{\hat{I}\text{c◯}(1/\hat{I}\mu )}$ [Jay26] left a gap between $1/\hat{I}\mu$ and $1/\hat{I}{\mu }^2$ in the exponent of $m$. We nearly close this gap. For every fixed $\hat{I}´\in (0,1)$, there are constants $A_{\hat{I}}´,c_{\hat{I}}´>0$ such that, for all sufficiently small $\hat{I}\mu >0$ and every $m\ge (1/\hat{I}\mu {)}^{A_{\hat{I}}´}$, 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 $\hat{I}\mu$ has dimension \[ D \ge 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 $\hat{I}´$ can be arbitrarily small, the exponent approaches the $O(1/\hat{I}{\mu }^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 $\hat{I}\text{c◯}(k^{1-\hat{I}´})$. Uniform-width padding and a block encoding create an $\hat{I}\text{c◯}(\hat{I}\mu )$ 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\hat{I}\mu$. 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.