Fugu-MT 論文翻訳(概要): Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

論文の概要: Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

arxiv url: http://arxiv.org/abs/2607.20393v2
Date: Sat, 25 Jul 2026 05:20:41 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-28 12:52:43.707859
Title: Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
Title（参考訳）: 最大内積類似性の単ベクトル埋め込みに対する近似次元下界
Authors: Rajesh Jayaram, Honghao Lin, Vahab Mirrokni, David P. Woodruff,
Abstract要約: シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: マルチベクター埋め込みは、ポイントクラウド単位でアイテムを表現し、クエリとドキュメントポイントクラウドをChamferの類似性を使って比較する。シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。我々の設定では、MUVERA は次元 $m^{O(1/ε^2)}$ [DHJ+24] を与えるが、以前の下界 $(ε^2m)^{Ω(1/ε)}$ [Jay26] は$m$の指数で $1/ε$ と $1/ε^2$ の差を残している。私たちはこのギャップをほぼ埋めた。すべての固定された$δ\in(0,1)$に対して、すべての定数 $A_δ,c_δ>0$ が存在し、十分小さい$ε>0$ とすべての $m\ge(1/ε)^{A_δ}$ に対して、最小の$m$単位ベクトルの単位クエリベクトルとドキュメントポイントクラウドが存在し、すべてのペアワイズMAX-IP値を加法誤差 $ε$ は次元 \[D \ge m^{c_δ/ε^{2-2δ}} を持つ。これは、データセットを見た後に選択された完全なデータ依存表現でさえ保持します。すべてのクエリがシングルトンであるため、Chamferにも適用される。 δ$は任意に小さくできるので、指数は上界の$O(1/ε^2)$依存に近づく。この証明はシェルストフのパターン行列法と多項式サイズで定数幅のDNF公式を組み合わせることで、近似次数$Ω(k^{1-δ})$の計算関数を計算する。均一幅のパディングとブロック符号化は$Ω(ε)$ギャップを生成する。ダミー座標は、すべての偽入力を等しくし、DNFパターン行列の正確な2値アフィン像である単位球MAX-IP行列を少なくとも8ε$で生成する。これにより、近似ランク境界が適用できる。この証明は、Google社内で開発された完全に自動化されたジェミニベースのエージェントシステムを用いて最初に得られた。著者らは証明を検証し、提示の明確さのために編集した。

論文の概要: Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

関連論文リスト