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

• URL: http://arxiv.org/abs/2607.20393v2
• Date: Sat, 25 Jul 2026 05:20:41 GMT
• Title: Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
• Abstract summary: For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
• Score: 75.14269295861845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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/ε^2)}$ [DHJ+24], whereas the previous lower bound $(ε^2m)^{Ω(1/ε)}$ [Jay26] left a gap between $1/ε$ and $1/ε^2$ in the exponent of $m$. We nearly close this gap. For every fixed $δ\in(0,1)$, there are constants $A_δ,c_δ>0$ such that, for all sufficiently small $ε>0$ and every $m\ge(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 \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 $δ$ 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 $Ω(k^{1-δ})$. Uniform-width padding and a block encoding create an $Ω(ε)$ 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.

Related papers

• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  We prove $c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$ with no sign, sparsity, or squareness restriction.<n>Within the pure-$varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both $(varepsilon-2log3(n+1))$.
  arXiv  Detail & Related papers  (2026-07-30T14:41:34Z)
• Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings [5.90432887297327]
  We show that MV embeddings can express similarities which cannot even be approximately represented by single vector embeddings.<n>Our results confirm a long-held belief in the IR community: at a fixed representation size, multi-vector embeddings can express similarities which cannot even be approximately represented by single vector embeddings.
  arXiv  Detail & Related papers  (2026-06-22T15:22:05Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  We show that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be nearly achieved in dimension $d = O(mathsfmmathsfrd(+infty, A)-2log n)$.<n>Our main theorem establishes that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be
  arXiv  Detail & Related papers  (2026-05-22T12:22:20Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• On the Intrinsic Dimensions of Data in Kernel Learning [1.675218291152252]
  We show that for kernels such as the Laplace kernel, the effective dimension $d_K$ can be significantly smaller than the Minkowski dimension $d_$ provably holds on regular domains.<n>Our results show that, for kernels such as the Laplace kernel, the effective dimension $d_K$ can be significantly smaller than the Minkowski dimension $d_$ provably holds on regular domains.
  arXiv  Detail & Related papers  (2026-01-22T17:32:24Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation.<n>We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Sparsifying Suprema of Gaussian Processes [3.898355636811022]
  We give a dimension-independent sparsification result for suprema of centered Gaussian processes.<n>We show that given any norm $nu(x)$ on $mathbbRn$, there is another norm $psi(x)$ depending only on the projection of $x$ onto $O_varepsilon(1)$ directions.
  arXiv  Detail & Related papers  (2024-11-22T01:43:58Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
  arXiv  Detail & Related papers  (2024-06-04T15:50:42Z)
• Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
  A random $mtimes n$ matrix $S$ is an oblivious subspace embedding (OSE) We show that an $mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$. We use this to construct the first oblivious subspace embedding with $O(d)$ embedding dimension that can be applied faster than current matrix multiplication time.
  arXiv  Detail & Related papers  (2023-11-17T18:01:58Z)
• Dimension-Independent Kernel ε-Covers [8.234735564035567]
  A kernel range space concerns a set of points $X subset mathbbRd$ and the space of all queries by a fixed kernel.<n>We introduce the notion of an $varepsilon$-cover for a kernel range space.
  arXiv  Detail & Related papers  (2023-06-28T19:19:33Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• A closer look at the approximation capabilities of neural networks [6.09170287691728]
  A feedforward neural network with one hidden layer is able to approximate any continuous function $f$ to any given approximation threshold $varepsilon$. We show that this uniform approximation property still holds even under seemingly strong conditions imposed on the weights.
  arXiv  Detail & Related papers  (2020-02-16T04:58:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.