🤖 machine learning

Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

本文对多探针网格化近似最近邻（ANN）搜索进行了系统性分析，揭示了其相比于图、树及划分方法在处理高维数据时具有更优越的可扩展性和更低的索引成本，从而表明其在优化重构建任务应用和高效 Transformer 架构方面具有潜力。

原作者： Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

发布于 2026-07-03

📖 1 分钟阅读☕ 轻松阅读

原作者： Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：在不断增长且变化的草堆中寻找一根针

想象一下，你正在一个草堆里寻找一根特定的针。

针：你正在寻找的精确答案（“最近邻”）。
草堆： 海量的数据库（例如数百万个单词或图像）。
问题： 随着草堆变得越来越大（数据量增加）或者针变得越来越复杂（维度更高），寻找这根特定之针的过程会变得极其缓慢且困难。

这篇论文介绍了一种寻找“针”的新型、复古的方法，称为**“多探针网格搜索”（Multiprobe Grid Search）**。作者将这种方法与目前大家都在使用的现代高科技工具（如基于图和基于树的系统）进行了对比，并发现了一个令人惊讶的事实：当数据变得巨大或非常复杂时，基于网格（Grid-based）的方法实际上非常强大。

类比：超市 vs. 迷宫

为了理解这些方法之间的区别，我们使用两个类比：

1. 现代方法（图与树）：复杂的迷宫
目前流行的各种方法就像一个复杂的、多层的迷宫。要找到一根针，你必须沿着迷宫中蜿蜒曲折的路径前进。

缺陷： 随着迷宫变得越来越大（数据量增加）或者墙壁变得越来越混乱（维度更高），路径会变得更长、更纠缠。你会花费大量时间在回溯和迷路中。论文发现，随着数据的复杂化，这些“迷宫行者”的速度会显著变慢。

2. 新方法（多探针网格）：组织有序的超市
本文介绍的方法就像一个组织完美的超市。

运作方式： 它不是迷宫，而是将商店划分为简单的正方形货架（网格）。
诀窍： 当你想找一件商品时，你不仅仅检查你认为它所在的那个货架，还会检查该货架以及紧邻的周围货架。这被称为“多探针”（multiprobe）。
核心秘诀： 为了决定检查哪些货架，系统使用了一个简化的地图（“PCA 投影”），它忽略了一些令人困惑的细节，只关注主要布局。一旦选定了正确的货架，它会在真实的、详细的世界中进行快速的最终检查。

论文的发现

作者通过实验观察了当两个变量发生变化时，这些方法的表现如何：数据规模和数据复杂度。

1. “规模”测试（更大的草堆）

设置： 他们将数据量增加了一倍、两倍甚至三倍。
结果： “超市”（网格）方法的变慢速度与规模增长几乎完全同步。如果数据翻倍，耗时也大约翻倍。这被称为近线性扩展（near-linear scaling）。
竞争对手： “迷宫”方法在初期减速并不明显，但随着数据变得巨大，它们开始比网格法更加吃力。
结论： 网格方法非常可预测，并且能诚实地反映出随着数据增长所需的处理时间。

2. “复杂度”测试（维度的交叉点）

设置： 他们增加了数据的复杂度（增加了更多特征，比如从 2D 图形变为 3D 模型，再到 100D 模型）。
惊喜： 这是论文最大的发现。
- “迷宫”方法（图与树）随着复杂度的增加而变得慢得多。数据越复杂，它们就越难剔除（忽略）错误的路径。
- “超市”（网格）方法则保持稳定。因为它使用简化地图来决定检查哪些货架，所以不会被额外的复杂度所迷惑。
交叉点： 在达到一定的复杂度后，网格法实际上变得比现代的迷宫法更快了。论文称之为“交叉点”（crossover）。

3. 构建成本（搭建商店）

设置： 构建索引（即布置好货架）需要多长时间，然后才能开始搜索？
结果： 网格法的构建速度极快。组织一百万个项目仅需 4 到 36 秒。而现代的迷宫方法则需要几分钟甚至超过 25 分钟。
重要性： 如果你的系统需要不断丢弃旧数据并从头构建新索引（例如每小时更新一次的推荐系统），网格法将是赢家，因为它构建得非常快。

“总成本”公式

论文认为，你不应该只看搜索过程中的速度，而应该看总成本：

总成本 = (构建时间) + (搜索时间 × 搜索频率)

场景 A： 你构建一次索引，然后搜索一百万次。构建缓慢的迷宫方法可能会胜出，因为它们的单次搜索速度很快。
场景 B： 你频繁构建索引（重建频繁）或者搜索次数较少。网格法会胜出，因为它构建成本极低且极快。

为什么这对 AI 至关重要（“注意力”的联系）

论文提到，现代 AI（Transformer）通过进行“近似最近邻”（Approximate Nearest Neighbor）搜索来决定关注哪些单词。

如果一个 AI 模型需要随着新单词的进入不断更新其记忆（索引），那么网格法的低构建成本以及处理复杂数据而不减速的能力，可以让 AI 的运行变得更快、更便宜。

总结

论文的核心观点是：“不要忽视简单的网格。”
虽然大家都在痴迷于复杂的、迷宫式的搜索方法，但这种简单、有序的“超市”式方法（多探针网格）在处理以下情况时实际上表现更好：

海量数据集（速度可预测）。
极高复杂度的数据（它不会被高维数据搞糊涂）。
频繁重建（它能在秒级完成构建，而不是分钟级）。

这提醒我们，有时经过改良的“老派”方法，才是处理特定任务最高效的工具。

技术摘要：高维空间下基于网格的近似最近邻搜索的缩放法则

问题陈述

近似最近邻（ANN）搜索是现代机器学习中的一个基础原语，它既服务于传统的检索任务，也作为 Transformer 架构的计算构建模块发挥着新兴作用（其中自注意力机制被形式化为一种 ANN 操作）。虽然经验性的缩放法则指导着大规模模型的设计，但 ANN 算法相对于数据集规模 ( $N$ ) 和维度 ( $d$ ) 的缩放行为仍是一个关键但尚未得到充分表征的研究领域。

现有文献广泛分析了基于图（如 HNSW）、基于树和基于划分的方法。然而，基于网格的方法尽管在早期 ANN 理论中具有基础性作用，但在现代缩放分析中却长期缺位。本文通过系统地表征一种多探针网格算法（multiprobe grid algorithm），旨在填补这一空白，并具体研究其性能如何随 $N$ 和 $d$ 的变化而缩放，以及与最先进的竞争对手相比的表现如何。

方法论

多探针网格算法

作者提出了一种将单元格选择与全维度 $d$ 解耦的多探针网格算法。其工作流程包括：

PCA 投影： 将数据点从 $\mathbb{R}^d$ 投影到低维子空间 $\mathbb{R}^m$ （其中 $m \ll d$ ）。
网格划分： 将该子空间划分为 $G^m$ 个均匀网格单元。
多探针选择： 在查询时，算法识别“家”单元（home cell），并按照与查询点的平方墙距离（squared wall distance, $w_i^2$ ）排序，探测最多 $2^m - 1$ 个相邻单元。
重排序： 对从探测单元中收集到的候选点在原始高维空间 $\mathbb{R}^d$ 中进行重排序。

理论模型

作者推导了查询成本（每秒查询数，QPS）与召回率（ $R$ ）之间的闭式关系。

成本模型： 查询成本与探测单元的数量（ $n_{probe}$ ）以及每个单元内的点数（ $N/G^m$ ）呈线性关系。
召回率模型： 假设分布是均匀的，真最近邻落在被探测单元中的概率随墙距离呈指数级衰减。
结果关系： 该模型预测了 QPS 与召回率之间的对数线性关系： $\log(\text{QPS}) \approx \log(\text{const}) - \log(R)$ 。这源于成员概率在不同单元间的指数衰减以及候选集规模的线性增长。

实证评估

本研究使用 ann-benchmarks 框架，在两个数据集上将多探针网格与代表主要 ANN 家族的四种基准方法进行了对比：

基于图的方法： Voyager, PyNNDescent。
基于树的方法： Annoy。
基于划分/量化的方法： FAISS-IVF。

实验使用了以下两个数据集：

GloVe-200-angular（词嵌入， $d=200$ ， $N \approx 1.18 \times 10^6$ ）。
SIFT-128-euclidean（图像描述符， $d=128$ ）。

评估重点在于 $N$ 的缩放指数 ( $\alpha_N$ )、 $d$ 的缩放指数 ( $\alpha_d$ )、帕累托前沿（吞吐量 vs. 召回率）以及总成本分析（索引 + 查询时间）。

关键结果

1. 对数线性吞吐量-召回率关系

对 GloVe-200 的帕累托前沿分析证实了理论预测：多探针网格表现出随着召回率增加而导致的吞吐量对数线性下降。这种行为与基准方法截然不同，是由网格几何结构和最近邻成员概率的指数衰减驱动的。

2. $N$ 缩放：近线性退化

多探针网格随数据集规模 ( $N$ ) 呈近线性缩放。

在召回率 @10 = 0.80 时，缩放指数为 $\alpha_N \approx -0.94$ (GloVe) 和 $-0.83$ (SIFT)。
相比之下，基于图和基于树的基准方法表现出亚线性缩放（ $\alpha_N$ 范围在 $-0.44 $到$ -0.59$ 之间）。
含义： 虽然与图方法相比，多探罗网格的吞吐量随 $N$ 增长而退化得更快，但这属于该算法设计的机械性后果（即候选数量随 $N$ 线性增长）。

3. $d$ 缩放：关键交叉点

在 GloVe 嵌入族上观察到了此前未曾报道的 $d$ 缩放交叉现象。

基准方法： 随着维度 $d$ 增加，图、树和划分方法的吞吐量显著下降（具有陡峭的 $\alpha_d$ ），反映了“维度之咒”以及在高维空间中几何剪枝的失效。
多探针网格： 随着 $d$ 增加，其缩放指数 $\alpha_d$ 保持相对平坦且表现优异。
机制： 通过在低维 PCA 子空间（ $m \ll d$ ）中进行单元格选择，并根据 $d$ 和目标召回率调整网格参数（ $m, G$ ），该算法避免了遍历完整的全高维空间。重排序成本仅随候选数量线性增长，这比遍历完整 $d$ 维空间的算法成本增长要缓和得多。

4. 总成本与索引效率

论文分析了总成本函数 $J(N) = f_I \cdot I(N) + f_C \cdot C(N) + M(N)$ ，其中 $I$ 为索引成本， $C$ 为计算成本， $M$ 为内存占用。

索引速度： 多探针网格的构建速度明显快于基准方法。在 $N = 1.18 \times 10^6$ 时，它构建索引仅需 4–36 秒，而 Voyager 则需要 1,569 秒。
查询延迟： 多探针网格具有较高的单次查询延迟（在高召回率下比 Voyager 慢约 120 倍）。
竞争区间： 当重建-查询比（ $f_I/f_C$ ）较高时，该方法具有竞争力。具体而言，如果一个索引大约每 2,600 至 20,400 次查询重建一次，多探针网格能提供更低的总体成本。这使其适用于“重重建”场景。

意义与主张

本文声称，网格类方法（在现代缩放分析中常被忽视）在特定场景下提供了独特且具竞争力的权衡方案：

维度鲁棒性： 多探针网格在维度 $d$ 增加时具有独特的鲁棒性，在几何剪枝失效的高维设置中优于图和树方法。
低索引开销： 与需要复杂的、依赖数据的图构建过程相比，该算法提供了近乎瞬时的索引构建能力。
与 Transformer 的相关性： 鉴于自注意力机制被形式化为一种 ANN 操作，ANN 算法的 $N$ $N$ - 和 $d$ $d$ -缩放特性与 Transformer 的效率直接相关。作者指出，多探针网格可能在以下 Transformer 架构中具有优势：
- 上下文长度 ( $N$ ) 或头维度 ( $d$ ) 发生变化时。
- 增量更新频繁时（例如，扩展 KV 缓存），因为向网格添加一个 token 仅需执行单次单元格分配，而无需重新构建整个图。
总成本视角： 论文认为，选择 ANN 方法不应仅依赖于查询延迟，还必须考虑包括索引频率和重建成本在内的总成本函数。在高重建场景下，网格方法的低索引成本可以抵消其较高的查询延迟。

总之，这项工作重新确立了网格类方法作为高维学习系统中可行且具竞争力的选项，特别是在索引成本、重建频率和维度鲁棒性是主要约束条件的场景下。