近年来，近似最近邻（ANN）搜索的缩放规律分析几乎被图、树和分区类方法主导，而基于网格的方法却很少出现在现代系统性的缩放研究中。2026年7月1日提交至arXiv的论文《Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions》（arXiv:2607.01283v1，cs.LG，交叉cs.AI）填补了这一空白。该论文由Matthew J Liu等共7位作者完成，第一作者之外还包括Noah Flynn等贡献者，提交时间为2026年7月1日08:42:38 UTC，全文约449 KB，并提供PDF、实验性HTML以及TeX源码，代码已在GitHub的weiz345/MultiProbeANN仓库公开。
论文的核心工作是对一种多探针网格（multiprobe grid）算法进行系统性刻画，重点考察两个关键维度：数据集规模N和向量维度d。作者通过实验揭示了一个此前未被报告的维度缩放交叉现象。在GloVe嵌入系列数据集上，多探针网格搜索的维度缩放指数大致保持恒定，而其他基于图、树和分区的ANN方法在维度升高时吞吐量出现退化。换言之，当维度从较低水平逐步提升时，网格方法相对其他方法的速度优势会扩大，而不是像传统认知那样在高维下迅速崩塌。
这一优势并非没有代价，但代价的结构值得注意。多探针网格在查询阶段随N呈现近似线性缩放，意味着数据集增大时查询延迟的增长相对可控；同时，其索引构建成本低于竞争的ANN方法。对于需要频繁重建索引的场景——例如数据持续更新、嵌入模型频繁迭代或分布漂移需要重新索引的在线系统——较低的索引成本可能比单纯的查询速度更有价值。论文据此提出，多探针网格这类基于网格的方法在“重建密集型”或高维场景中具备竞争力，尤其是在索引成本和维度鲁棒性共同决定系统性能的场合。
论文还给出了更宏观的动机。近期有研究将自注意力形式化为一种ANN操作，如果这一视角成立，那么ANN算法在N和d上的缩放性质就可以用来指导高效Transformer架构的成本分析。换句话说，理解多探针网格在数据规模和维度上的行为，不仅关乎向量检索系统本身，也可能为注意力机制的近似计算与架构设计提供可迁移的成本模型。
需要指出的是，本文的结论建立在特定实验设置之上，最突出的证据来自GloVe嵌入家族上的维度缩放交叉；论文标题虽强调高维，但摘要并未声称在所有数据集族上普遍成立。作者将贡献定位为系统性表征和缩放规律刻画，而非提出一个全面超越现有方法的通用索引。代码开源为后续复现和扩展到其他嵌入族提供了基础。总体来看，这项工作把长期缺席于现代缩放分析的网格类ANN方法重新带回讨论中心，并提示研究社区在评估ANN算法时应同时报告N缩放、d缩放和索引成本三条曲线。