高维空间中基于网格的近似最近邻搜索的缩放规律

# 高维空间中基于网格的近似最近邻搜索的缩放定律 来源：https://arxiv.org/html/2607.01283 \\hldauthor\\Name Matthew J\. Liu\\Emailmatthewliu@berkeley\.edu \\addr加州大学伯克利分校 and\\NameWei Hang Zheng\\Emailweihang\_zheng@berkeley\.edu \\addr加州大学伯克利分校 and\\NameVidhan Purohit\\Emailviddyp1804@gmail\.com \\addr多伦多大学圣乔治校区 and\\NameSiqi Xie\\Emailsiqixie@alumni\.cmu\.edu \\addr独立研究者 and\\NameChieh\-En Li\\Emailchiehenli@gmail\.com \\addr独立研究者 and\\NameJerry Li\\Emailli\.zhiyi\.jerry@gmail\.com \\addr滑铁卢大学 and\\NameNoah Flynn\\Emailnoahflynn@berkeley\.edu \\addr加州大学伯克利分校 ###### 摘要 基于网格的近似最近邻（ANN）搜索方法在当前的缩放分析中鲜有涉及。我们系统性地刻画了一种多探针网格算法在数据集大小 \(N\) 和维度 \(d\) 上的表现。实验揭示了一个此前未报道的 \(d\) 缩放交叉现象：在 GloVe 嵌入族上，多探针网格搜索保持近似恒定的维度缩放指数，而其他基于图、树和划分的方法吞吐量则持续下降。该优势体现在近乎线性的 \(N\) 查询缩放，同时索引构建成本也低于同类 ANN 方法。我们的结果表明，在索引重建频繁或高维场景下，多探针网格等基于网格的方法可能具有竞争力，因为这些场景中索引成本与维度鲁棒性对性能起决定性作用。更广泛而言，近期研究将自注意力机制形式化为 ANN 操作。因此，ANN 算法的 \(N\) 和 \(d\) 缩放特性可指导高效 Transformer 架构的成本分析。代码开源地址：\\urlhttps://github\.com/weiz345/MultiProbeANN\. ## 1 引言 近似最近邻（ANN）搜索是现代机器学习系统处理大型高维数据集的核心技术\[darrell\_nearest\-neighbor\_2005\]。除了经典的检索作用外，ANN 已成为 Transformer 架构中的计算原语。近期研究将自注意力形式化为针对令牌嵌入的 ANN 操作，从而实现了对全注意力的次二次近似\[haris\_knn\_2025,liu\_fast\_2025,kang\_attention\_2025\]。随着经验缩放定律指导 Transformer 设计\[kaplan\_scaling\_2020\]，ANN 算法的缩放行为对开发更高效的 Transformer 架构愈发重要。具体而言，缩放数据集大小 \(N\) 会考验候选过滤与索引效率，而缩放维度 \(d\) 则会加剧维度灾难，降低几何剪枝的有效性。因此，包括基于图、树和划分的 ANN 方法表现出随场景变化的权衡，没有任何方法能普遍占优\[xiao\_enhancing\_2024,iff\_benchmarking\_2026\]。基于网格的方法（划分方法的一种变体）在早期 ANN 理论中发挥了奠基作用\[indyk\_approximate\_1998,chan\_approximate\_1997\]，但在现代缩放分析中相对于基于图和树的方法仍缺乏充分刻画（参见附录A (https://arxiv.org/html/2607.01283#A1)相关工作）。在本工作中，我们刻画了一种多探针网格算法（概述见第2节 (https://arxiv.org/html/2607.01283#S2)）的 \(N\) 与 \(d\) 缩放关系。该算法将单元格选择与 \(d\) 解耦——单元格选择指查询时确定哪些网格单元提供候选向量的过程。这种解耦通过在 PCA 降维子空间 \(\mathbb{R}^m\) 中执行单元格选择，同时在 \(\mathbb{R}^d\) 中对候选进行重排序来实现。我们表明，虽然多探针网格在 \(N\) 上呈现近线性缩放，但其 \(d\) 缩放行为在维度增加时依然保持有利。本工作将基于网格的方法置于更广泛的 ANN 设计空间中，并展示了其在具备竞争性权衡的场景。 ## 2 多探针网格搜索的理论缩放模型 我们提供多探针网格算法的理论概述，推导出查询成本与召回率之间的闭式关系。附录B (https://arxiv.org/html/2607.01283#A2) 包含完整讨论，图D1 (https://arxiv.org/html/2607.01283#A4.F1) 提供了算法概览示意图。 ##### 成本模型。 经 PCA 投影到 \(\mathbb{R}^m\) 后，空间被划分为 \(G^m\) 个单元格，每个单元格包含 \(N/G^m\) 个点。查询 \(q\) 探测总共 \(1 \leq n_{\mathrm{probe}} \leq 2^m\) 个单元格，包括主单元格 \(c_h\)（定义见附录B.1 (https://arxiv.org/html/2607.01283#A2.SS1)）以及最多 \(2^m-1\) 个按壁距离 \(w_i^2\) 升序排列的相邻单元格（附录B.2 (https://arxiv.org/html/2607.01283#A2.SS2)）。每个探测到的单元格平均贡献 \(N/G^m\) 个候选，因此成本为： \[\mathrm{cost} = 1/\mathrm{QPS} = K \cdot n_{\mathrm{probe}} \cdot \frac{N}{G^m}.\] (1) ##### 召回率模型。 设 \(P_i = \Pr[x^* \in c_i]\) 为真实最近邻位于第 \(i\) 个探测单元格的概率。在均匀分布假设下，\(P_i\) 随 \(w_i^2\) 单调递减，我们采用指数近似（附录B.3 (https://arxiv.org/html/2607.01283#A2.SS3) 和 B.6 (https://arxiv.org/html/2607.01283#A2.SS6)）： \[P_i \approx P_h e^{-\mu w_i^2},\qquad P_h := P_0,\ \mu > 0\] (2) ##### 闭式形式。 利用均值间隙的线性近似 \(\mathbb{E}[w_i^2] \approx \theta i\)（附录B.4 (https://arxiv.org/html/2607.01283#A2.SS4)），可得： \[R(n_{\mathrm{probe}}) = P_h \sum_{i=0}^{n_{\mathrm{probe}}-1} \Delta^i = P_h \cdot \frac{1-\Delta^{n_{\mathrm{probe}}}}{1-\Delta},\quad \Delta := e^{-\mu\theta} \in (0,1)\] (3) ##### 对数线性关系。 解方程3 (https://arxiv.org/html/2607.01283#S2.E3) 求 \(n_{\mathrm{probe}}\)，代入方程1 (https://arxiv.org/html/2607.01283#S2.E1) 并求逆，得： \[\mathrm{QPS}(R) = \frac{G^m}{KN} \cdot \frac{|\ln\Delta|}{-\ln(1-R/R_{\max})}.\] (4) 取对数得 \(\log \mathrm{QPS}(R) \approx \log(\mathrm{const}') - \log R\)。因此，我们的框架预测 QPS 与召回率之间呈对数线性关系，这源于最近邻隶属概率在探测单元格中的指数衰减以及候选集大小随 \(n_{\mathrm{probe}}\) 线性增长。 ## 3 经验缩放定律 我们在四种代表主要 ANN 家族的基线上评估多探针网格算法：Voyager（基于图）\[noauthor\_spotifyvoyager\_2026\]、PyNNDescent（基于图）\[mcinnes\_lmcinnespynndescent\_2026\]、Annoy（基于树）\[noauthor\_spotifyannoy\_2026\] 和 FAISS-IVF（基于量化划分）\[noauthor\_facebookresearchfaiss\_2026\]。算法使用 ann-benchmarks 框架进行评估\[aumuller\_ann\-benchmarks\_2020, aumuller\_reproducibility\_2021\]，每种方法在专用 Docker 容器中执行以实现单 CPU 隔离。基线实现使用高度优化的 C++ 实现，而我们的多探针网格实现是基于 Python 的概念验证。因此，测得的 QPS 可能低估了同等优化实现下可达到的吞吐量。尽管如此，我们相信这里报告的相对缩放趋势仍具有参考价值，因为多探针网格的每查询时间主要花费在 NumPy/BLAS 上（参见附录C (https://arxiv.org/html/2607.01283#A3) 的性能分析）。基线算法使用其已建立的 ann-benchmarks 参数扫描，这代表了经过充分探索、社区验证的搜索空间；多探针网格算法则需要定制的 NSGA-II 调参来识别具有竞争力的配置（附录C (https://arxiv.org/html/2607.01283#A3) 实现细节）。 ### 3.1 Pareto 前沿揭示多探针网格的吞吐量-召回率对数线性关系 图1 (https://arxiv.org/html/2607.01283#S3.F1) 展示了五种算法在 GloVe-200-angular 数据集（\(N=1.18\times 10^6\) 个点）\[pennington\_glove\_2014, aumuller\_ann\-benchmarks\_2020, aumuller\_reproducibility\_2021\] 上的 Pareto 前沿。与第2节 (https://arxiv.org/html/2607.01283#S2) 一致，多探针网格显示 \(\log(\mathrm{QPS})\) 随召回率增加而线性下降，表明性能由网格几何决定。在 recall@k=10 > 0.9 时，多探针的吞吐量趋近于暴力搜索：高召回率需要要么粗粒度的 PCA 投影（\(m=2\)）导致单元格密度高，要么在更高 \(m\) 下进行穷尽多探针，从而对大部分数据集进行排序。我们在图D2 (https://arxiv.org/html/2607.01283#A4.F2)–D3 (https://arxiv.org/html/2607.01283#A4.F3) 中展示了 GloVe-200 和 \(d\)（GloVe-25, 50, 100, 200）每个子采样 \(N\) 下的单独 Pareto 前沿。 请参见图注 图1：GloVe-200-angular（\(d=200\)，\(N=1.18\times 10^6\)）的 Pareto 前沿。 ### 3.2 \(N\) 缩放：多探针网格随数据集大小近似线性缩放 #### 3.2.1 GloVe 数据集（角距离） 图2 (https://arxiv.org/html/2607.01283#S3.F2)a 显示了五种 ANN 算法的 \(N\) 缩放指数 \(\alpha_N\) 随召回率的变化。在 recall@k=10=0.80 时，多探针网格的 \(\alpha_N = -0.94\)（\(R^2=1.00\)），表明 QPS 随数据集大小近乎线性下降。相比之下，我们观察到基线的次线性缩放，\(\alpha_N\) 在 \(-0.44\) 到 \(-0.59\) 之间。图D4 (https://arxiv.org/html/2607.01283#A4.F4) 展示了每个目标 recall@k=10 下的 \(\log_{10}(\mathrm{QPS})\) 与 \(\log(N)\) 图，用于推导图2 (https://arxiv.org/html/2607.01283#S3.F2)a 中的指数。多探针的近线性 \(N\) 缩放在机制上符合预期：对于固定的网格参数 \((m,G)\)，每个单元格的候选数按 \(N/G^m\) 增长，重排序成本与候选数线性相关。随着召回率目标增加，所有算法的指数趋向 \(\alpha_N = -1\)，这反映了完美召回需要穷尽搜索。多探针的指数在整个召回范围内已接近渐近值，而基线方法在更高召回率时下降更快。 #### 3.2.2 SIFT-128 数据集（欧氏距离） 为了考察观察到的 \(N\) 缩放关系是否适用于词嵌入之外的数据，我们在 SIFT-128-euclidean（图像描述符，\(d=128\)）\[jegou\_product\_2011\] 上重复了分析。多探针网格的对数线性 Pareto 行为（图D5 (https://arxiv.org/html/2607.01283#A4.F5)）以及 \(\alpha_N\) 的相对趋势得以保留（图D6 (https://arxiv.org/html/2607.01283#A4.F6)–D7 (https://arxiv.org/html/2607.01283#A4.F7)）。在 recall@k=10=0.80 时，多探针网格的缩放指数 \(\alpha_N = -0.83\)（\(R^2=1.00\)），而基线算法介于 \(-0.27\) 和 \(-0.39\) 之间。跨数据模态（图像 vs. 词）和相似性度量（欧氏 vs. 角距离）的一致性表明，多探针网格的 \(N\) 缩放在算法本身而非特定数据集。 请参见图注 图2：五种算法的缩放指数与 recall@k=10 的关系。(a) \(N\) 缩放指数 \(\alpha_N\)。数据集：不同 \(N\) 子采样的 GloVe-200-angular（\(d=200\)）。(b) \(d\) 缩放指数 \(\alpha_d\)。数据集：GloVe-25-, 50-, 100-, 200-angular（\(N=1.18\times 10^6\)）。 ### 3.3 \(d\) 缩放：多探针网格在高维数据上竞争力增强 图2 (https://arxiv.org/html/2607.01283#S3.F2)b 显示了 \(d\) 缩放指数 \(\alpha_d\) 随召回率的变化，揭示多探针网格与其他四种算法之间存在非单调的交叉现象。当召回率超过 0.7 时，除多探针网格外所有算法的 \(\alpha_d\) 急剧变陡，反映吞吐量随维度增加而下降。与此同时，多探针网格的 \(\alpha_d\) 保持相对平缓。这一对比值得注意，因为先前的实证研究（包括我们自己在图2 (https://arxiv.org/html/2607.01283#S3.F2)a 中的结果）通常发现 \(N\) 缩放指数在算法家族间高度一致\[sun\_scaling\_2025\]。而 \(d\) 缩放的交叉打破了这种普遍性——具有最不利 \(N\) 缩放的算法，在高召回率下同时表现出最有利的 \(d\) 缩放。图D8 (https://arxiv.org/html/2607.01283#A4.F8) 展示了每个目标 recall@k=10 下的 \(\log_{10}(\mathrm{QPS})\) 与 \(\log(d)\) 图，用于推导图2 (https://arxiv.org/html/2607.01283#S3.F2)b 中的指数。\(\alpha_d\) 的交叉源于每种算法与 \(d\) 的交互方式。基于图的方法（Voyager, PyNNDescent）在全 \(d\) 维空间中构建和遍历邻近图。在高召回率下，准确检索需要探索更大的邻域和更多的回溯。类似地，基于树（Annoy）和基于量化划分（FAISS-IVF）的方法操作原始 \(d\) 维向量，随着 \(d\) 增大剪枝效果下降。相比之下，多探针网格在维度 \(m \ll d\) 的 PCA 子空间中进行单元格选择。尽管 PCA 随着 \(d\) 增大保留的总方差比例减小（图D9 (https://arxiv.org/html/2607.01283#A4.F9)），Pareto 最优的 \((m,G)\) 会随 \(d\) 和目标召回率自适应调整，而非固定（附录表E1 (https://arxiv.org/html/2607.01283#A5.T1)）。在高 \(d\) 下，倾向于更少的单元格总数 \(G^m\)，从而在每个探测单元格中集中更多候选以保持召回率。由于重排序仅随候选数线性增长，查询成本随 \(d\) 的增长比遍历全 \(d\) 维空间的方法更温和。我们注意到，我们的 \(d\) 缩放刻画受限于 \(d=200\)，这是 GloVe 家族中可用的最大维度（ann-benchmarks 中唯一提供 \(d\) 变化数据集系列）。虽然这一范围展示了 \(\alpha_d\) 的交叉，但将分析扩展到更高 \(d\) 的场景（例如现代 Transformer 嵌入的 \(d \geq 512\)）是未来工作的关键方向（第3.5节 (https://arxiv.org/html/2607.01283#S3.SS5)）。 ### 3.4 总成本分析揭示多探针网格的竞争性场景 图D10 (https://arxiv.org/html/2607.01283#A4.F10) 展示了在实现 recall@k=10 ≈ 0.80 的 Pareto 最优配置下，构建时间随 \(N\) 的缩放。多探针网格和 FAISS-IVF 在所有 \(N\) 下构建最快。当 \(N=1.18\times 10^6\) 时，多探针网格根据所选超参数配置在 4–36 秒内构建索引（最小配置 \(m=2, G=4\) 为 4 秒；最大配置 \(m=7, G=7\) 为 36 秒）。我们测得 FAISS-IVF 为 206 秒，Annoy 为 333 秒，PyNNDescent 为 500 秒，Voyager 为 1569 秒。多探针网格索引构建仅需 PCA 拟合、单元格分配和 BFS 预计算，而基线依赖于数据相关操作，如通过重复最近邻查询进行图插入（Vo