高维网格近似最近邻搜索的缩放定律
本研究系统刻画了多探针网格算法在高维空间中的性能，发现其在GloVe嵌入上表现出独特的维度缩放交叉现象，与其他方法相比具有恒定维度指数、近线性查询缩放和更低索引成本的优势，对高效Transformer架构设计具有指导意义。
来源arXiv Machine Learning作者: Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn
近年来，近似最近邻（ANN）搜索在机器学习和人工智能领域占据了核心地位，尤其是随着高效Transformer架构的发展，自注意力机制已被形式化为ANN操作。然而，基于网格的方法在现代缩放分析中却长期被忽视。一项来自Matthew J. Liu等七位研究者、于2026年7月1日提交至arXiv的新研究填补了这一空白，系统性地分析了多探针网格算法相对数据集规模N和维度d的缩放行为。
研究团队在GloVe嵌入家族上进行了广泛的实验，揭示出一个此前未被报道的维度缩放交叉现象：多探针网格搜索能够维持一个大致恒定的维度缩放指数，而基于图（如HNSW）、树（如KD-tree）和划分（如IVF）的方法在高维情况下吞吐量显著下降。这一优势不仅体现在查询延迟上，网格方法还实现了近乎线性的查询缩放（相对于N），并且其索引构建成本显著低于竞争方法。例如，在需要频繁重建索引或维度极高的场景中，索引成本和维度鲁棒性成为性能瓶颈，而网格方法恰好在这两方面表现出色。
更广泛地，由于自注意力已被建模为ANN操作，ANN算法的N和d缩放性质可以为高效Transformer架构的成本分析提供理论指导。该研究的代码已在GitHub上公开（https://github.com/weiz345/MultiProbeANN），便于社区验证和扩展。这项发现不仅复兴了网格方法在ANN领域的地位，也提示研究者重新审视那些因高维诅咒而被放弃的简单方法。未来，网格方法或将成为构建大规模、高维机器学习系统的重要工具。