逼近最大内积相似度的单向量嵌入维度下界接近最优。
Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
- 通过构造特定的布尔函数矩阵，结合多项式大小的DNF公式，实现近似秩分析。
- 在误差ε下，所需嵌入维度至少为 $ m^{c_δ/ε^{2-2δ}} $，逼近上界 $ m^{O(1/ε^2)} $。
- 适用于数据依赖型表示，且对单点查询的Chamfer相似度同样成立。
多向量嵌入用点云表示项目，通过Chamfer相似度比较查询与文档点云，而单向量嵌入使用普通内积。对于单点查询，Chamfer退化为最大内积相似度（MAX-IP）。在该设置中，MUVERA给出维度 $ m^{O(1/ε^2)} $ [DHJ+24]，而先前的下界 $ (ε^2m)^{Ω(1/ε)} $ [Jay26] 在 $ m $ 的指数中留下 $ 1/ε $ 与 $ 1/ε^2 $ 的差距。本文几乎填补该差距。对任意固定 $ δ∈(0,1) $，存在常数 $ A_δ, c_δ>0 $，使得当 $ ε>0 $ 足够小、$ m≥(1/ε)^{A_δ} $ 时，存在单位查询向量与最多 $ m $ 个单位向量的文档点云，使得所有两两 MAX-IP 值在加性误差 $ ε $ 内的单向量近似所需维度满足 $ D ≥ m^{c_δ/ε^{2-2δ}} $。该结论即使在数据依赖表示（查询数据后选择）下仍成立。由于 $ δ $ 可任意小，指数趋近于上界的 $ O(1/ε^2) $。证明结合了Sherstov的模式矩阵方法与多项式大小、常数宽度的DNF公式，其近似度为 $ Ω(k^{1-δ}) $。均匀宽度填充与块编码生成 $ Ω(ε) $ 间隙，哑坐标使所有假输入等价，得到单位球上的MAX-IP矩阵，其为精确的二值仿射映射，间隙至少为 $ 8ε $，从而适用近似秩界限。证明最初由谷歌内部开发的全自动Gemini代理系统完成，作者已验证并润色以提升可读性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。