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/\epsilon^2)}$~\cite{dhulipala2024muvera}, whereas the previous
lower bound $(\epsilon^2m)^{\Omega(1/\epsilon)}$~\cite{jayaram2026expressive} left a
gap between $1/\epsilon$ and $1/\epsilon^2$ in the exponent of $m$.
We nearly close this gap. For every fixed $\delta\in(0,1)$, there are
constants $A_\delta,c_\delta>0$ such that, for all sufficiently small
$\epsilon>0$ and every $m\ge(1/\epsilon)^{A_\delta}$, 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
$\epsilon$ has dimension
\[
D \ge m^{c_\delta/\epsilon^{2-2\delta}}.
\]
This holds even for fully data-dependent representations chosen after seeing
the dataset. It also applies to Chamfer because all queries are singletons.
Since $\delta$ can be arbitrarily small, the exponent approaches the
$O(1/\epsilon^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(k^{1-\delta})$. Uniform-width padding and a block encoding create an
$\Omega(\epsilon)$ 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\epsilon$. 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.
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/\epsilon^2)}$~\cite{dhulipala2024muvera}, whereas the previous
lower bound $(\epsilon^2m)^{\Omega(1/\epsilon)}$~\cite{jayaram2026expressive} left a
gap between $1/\epsilon$ and $1/\epsilon^2$ in the exponent of $m$.
We nearly close this gap. For every fixed $\delta\in(0,1)$, there are
constants $A_\delta,c_\delta>0$ such that, for all sufficiently small
$\epsilon>0$ and every $m\ge(1/\epsilon)^{A_\delta}$, 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
$\epsilon$ has dimension
\[
D \ge m^{c_\delta/\epsilon^{2-2\delta}}.
\]
This holds even for fully data-dependent representations chosen after seeing
the dataset. It also applies to Chamfer because all queries are singletons.
Since $\delta$ can be arbitrarily small, the exponent approaches the
$O(1/\epsilon^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(k^{1-\delta})$. Uniform-width padding and a block encoding create an
$\Omega(\epsilon)$ 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\epsilon$. 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.
