这项由加州大学伯克利分校、多伦多大学圣乔治校区、卡内基梅隆大学及滑铁卢大学等多所机构研究人员共同完成的研究发表于2026年7月1日的HiLD 2026第四届高维学习动态研讨会论文编号为arXiv:2607.01283v1。有兴趣深入了解原始研究的读者可通过该编号在arXiv平台查阅完整论文。**当图书馆的书越来越多、书架越来越复杂你该怎么找书**假设你管理着一座不断扩张的图书馆馆藏书籍数量从几千本增长到几百万本而每本书的描述标签也从十几个变成了两百个。你的任务是每当读者说出一个大致需求你要在几毫秒内找出最符合需求的十本书。这就是近似最近邻搜索Approximate Nearest Neighbor Search简称ANN要解决的问题。在真实的机器学习系统里这个图书馆可能是一个存储了数百万条词语含义的数据库每条记录都用一串数字向量表示读者的需求则是一个查询向量而找书的过程本质上是在高维空间里找到最靠近查询点的几个数据点。实际上ANN搜索不只用于检索。最近几年研究人员发现大型语言模型比如ChatGPT背后的Transformer架构里的注意力机制在数学本质上也是一种ANN操作——模型在处理文字时需要快速找到上下文中最相关的词语。因此ANN算法效率的提升直接关系到这类大模型运行的速度和成本。然而当这座图书馆的规模和复杂度同时增长时麻烦就出现了。现有的主流搜索方法——不论是基于图结构的、树结构的还是分区分块的——在数据量N增大或者标签维度d增高时都会以不同方式出现性能下降。研究团队发现在所有这些方法的大规模对比测试里有一类古老的方法几乎从未被认真纳入现代性能分析基于网格划分的方法。研究团队的核心问题是这种看似过时的网格搜索方法在数据量和维度同时变化时究竟表现如何它是否存在某些被忽视的优势---一、什么是多探针网格搜索把图书馆分成格子来找书要理解这个研究首先得搞清楚网格搜索是怎么运作的。回到图书馆的比喻——传统的网格搜索就像是把图书馆的地板划分成一个个方格子每本书都根据它的标签特征被放进某个格子里。当读者来查询时你先确定查询对应哪个格子主格子然后只检查那个格子里的书而不必翻遍整个图书馆。这种方法简单直接但有一个经典难题如果读者要找的那本书恰好放在主格子隔壁该怎么办多探针的思路就是为了解决这个问题而生的——它不只看主格子还会根据读者需求与格子边界的距离从近到远依次检查邻近的格子直到找到足够好的结果。不过这项研究里的多探针网格搜索有一个关键的聪明设计它并不在原始的高维空间比如200个标签维度的空间里划格子而是先用一种叫做PCA主成分分析的技术把数据压缩到一个低维子空间比如只有6个维度里进行格子划分然后在这个压缩版的简化地图上决定要查哪些格子最后再用完整的200维原始数据做精确比较。这个设计的意义非常关键。决定查哪些格子这件事只需要在低维压缩空间里做完全不受原始高维数据的影响而最终的精确排名虽然在高维空间做但因为候选集已经被大幅缩小计算量也是可控的。换句话说这个方法把找到候选人和精确评分这两步彻底解耦了让维度的增长对第一步几乎没有伤害。在实现细节上研究团队还为这个网格添加了一个兜底机制用广度优先搜索BFS预先计算好每个空格子离最近的非空格子有多远。这样当查询落在一个恰好没有数据的格子时系统可以立刻找到替代方案而不会崩溃。---二、从数学到直觉为什么查询速度会随召回率指数级下降研究团队不只是做了实验他们还建立了一套数学模型来预测这个算法的行为并从理论上解释了实验中观察到的现象。模型的核心思路其实很符合直觉。假设格子总数是固定的数据总量是N那么每个格子平均放了N/格子总数条数据。每检查一个额外的格子候选集的大小就线性增加这么多。与此同时越靠近主格子的邻居格子越可能包含查询的真正最近邻离得越远的格子包含真正答案的可能性呈指数级衰减——就像你找钥匙时距离你最后放钥匙的地方越近找到的概率越大而且这个概率随距离的增加会很快变小。把这两点结合起来就得到一个数学上很清晰的结论查询速度每秒能处理多少次查询即QPS与召回率找到真正最近邻的比例之间在对数坐标系下呈现近似直线关系。也就是说如果你画一张图横轴是召回率纵轴是查询速度的对数那么多探针网格的表现应该是一条向下倾斜的直线。召回率越高需要探针的格子越多速度越慢这个慢是以指数级的代价换取线性的精度提升。研究团队在实验中验证了这一点结果与理论预测高度吻合——在GloVe-200-angular这个包含118万个词向量的标准数据集上多探针网格的性能曲线确实呈现了预测的对数线性形状。值得一提的是当召回率超过90%时这个方法的查询速度会急剧下降趋近于暴力搜索遍历所有数据的水平。这是因为要找到几乎所有真正的最近邻要么需要把所有数据塞进很少的几个大格子里要么就必须检查绝大多数格子本质上等于全库搜索。这是网格方法固有的局限并非实现上的缺陷。---三、数据量扩大十倍速度就慢十倍——这个代价公平吗研究团队用GloVe-200数据集保持维度d200不变把数据量N从一万增加到118万和SIFT-128数据集图像描述符d128做了系统的N-scaling数据量缩放实验。实验方法是对每个算法、每个数据量级找出在某个固定召回率目标下的最优配置然后测量对应的查询速度画出速度-数据量的双对数图用直线的斜率来衡量数据量增大时速度下降的快慢这个斜率被称为N-缩放指数αN。αN越接近-1说明数据量增大一倍时速度几乎减半是线性代价αN越接近0说明数据量增大时速度几乎不变是亚线性代价。在GloVe-200上召回率目标为0.80时多探针网格的αN为-0.94R?1.00拟合极为精确非常接近-1意味着数据量增大时速度几乎线性下降。相比之下其他四种算法的αN在-0.44到-0.59之间也就是说它们在数据量增大时速度下降得相对较慢。这是否意味着多探针网格更差并不那么简单。αN接近-1是因为多探针网格在每个数据量级下几乎已经达到了完全线性的理论极限——它的设计决定了每多一条数据候选集就线性增大没有任何捷径可以压缩。而其他方法比如图搜索通过构建复杂的索引结构实现了亚线性增长但代价是建立这些索引需要大量时间和资源。在SIFT-128上同样的规律完整保留多探针网格的αN为-0.83而其他算法在-0.27到-0.39之间。两个完全不同的数据集一个是词向量、角度相似性另一个是图像描述符、欧氏距离得出了一致的结论说明这种N-scaling模式是算法本身的内在特性与数据类型无关。---四、最令人意外的发现维度越高它反而越有竞争力研究中最出乎意料的发现来自d-scaling维度缩放实验。研究团队利用GloVe词向量家族同一批词但分别用25、50、100、200个维度表示在数据量保持不变均为118万条的情况下测试了所有算法随着维度增加时的速度变化。对于图搜索方法Voyager和PyNNDescent以及树方法Annoy和分区方法FAISS-IVF维度增加的结果是明显的召回率目标越高维度增加对速度的伤害就越大。到了召回率0.9附近这四种算法的d-缩放指数αd急剧变陡降到-1.6甚至-2.0的水平意味着维度翻番时速度会下降到原来的四分之一甚至更少。这正是所谓维度诅咒的体现——在高维空间里几何结构变得均匀化原本高效的剪枝和导航技巧会失效算法被迫检查越来越多的数据。而多探针网格的αd表现截然不同在整个召回率范围内αd保持相对平稳没有出现其他方法那种高召回率时急剧变陡的现象。当召回率超过0.7时其他方法的αd纷纷急跌而多探针网格的αd曲线依然基本平缓。这个交叉点被研究团队称为d-scaling crossover维度缩放穿越是整篇论文中最核心的实证发现。为什么会这样原因正是前面提到的设计——格子划分在低维压缩空间里进行不受原始高维度的直接影响。当原始维度从25增加到200时PCA压缩能保留的方差比例确实在下降从GloVe-25中m8的压缩可以保留40%方差到GloVe-200中同样m8只能保留约8%方差但算法会自动适应在更高维度下超参数优化会选择更少的格子总数更大的格子让每个格子里包含更多候选点以此保住召回率。由于最终的精确排名是线性增长的整体查询代价对维度的依赖比其他方法要温和得多。研究团队也诚实地指出了这个发现的局限整个d-scaling实验受限于GloVe家族的最高维度200这是ann-benchmarks框架内唯一提供d变化系列的数据集。未来是否在d≥512的现代Transformer嵌入向量上同样成立是一个明确提出但尚未回答的开放问题。---五、建索引的时间这才是网格方法真正的竞争优势所在理解了查询性能之后研究团队进一步分析了完整的总拥有成本也就是不只看查询有多快还要看建索引建立搜索结构有多慢、内存占用有多大。在GloVe-200全量数据集N118万、召回率目标0.80时各算法建索引时间的测量结果差距惊人。多探针网格在最小配置m2G4下只需4秒最大配置m7G7也只需36秒平均约8.4秒。而FAISS-IVF需要206秒Annoy需要333秒PyNNDescent需要500秒VoyagerHNSW变体则需要惊人的1569秒——将近26分钟。为什么网格方法建索引这么快因为它的索引建立过程只需要三步做一次PCA降维、把数据点分配到对应格子、预计算一次广度优先搜索。这三步都不需要任何数据点之间的相互比较。相比之下图搜索方法的索引建立过程本质上是通过反复执行找最近邻来插入每一个数据点是一个递归依赖自身的过程自然慢得多。不过快速建索引是有代价的多探针网格的每次查询延迟约76.98毫秒而Voyager只需约0.62毫秒相差约120倍。查询速度慢很多。那么什么情况下网格方法的低建索引成本能够弥补这一劣势研究团队通过一个简单的经济学模型给出了答案。设fI为索引重建的频率fC为查询的频率当每次重建所节省的索引时间超过每次查询多花费的时间时网格方法的总成本更低。以与Voyager相比为例重建一次网格索引节省了约1560秒每次查询多花费约76毫秒因此只要每次索引重建之间的查询次数少于约20432次即约一次重建对应不超过两万次查询网格方法的总成本就更低。与FAISS-IVF相比这个临界值是约2591次查询。研究团队指出这个高重建频率的场景在实践中并不罕见。推荐系统需要随着用户行为持续更新候选库检索增强生成RAG系统需要随着文档库的更新频繁重建索引Transformer的KV缓存在处理长文本时每增加一个新词就需要更新一次索引。这些场景的共同特点是写多读少或索引更新频繁正是网格方法的舒适区。---六、算法的性能是真实的还是Python实现的假象研究团队的实现坦诚地承认了一个潜在问题对比实验中四种基线算法Voyager、PyNNDescent、Annoy、FAISS-IVF都是经过多年打磨的C高性能实现而多探针网格是一个Python概念验证版本。Python程序通常比C慢十倍甚至更多这会不会导致网格方法的绝对查询速度被低估从而影响结论研究团队用cProfile工具对网格搜索的每个步骤做了详细的计时分析在GloVe-200数据集上跨越三个数量级的数据量10万到118万进行了追踪。结果显示整个查询过程的时间开销几乎完全由两类NumPy/BLAS计算主导候选向量的收集从格子里取数据和精确重排名计算真实距离。这两步直接调用底层C库不受Python解释器影响。而纯Python的开销部分查找格子编号、枚举邻居格子、组装候选列表等由于每次查询只需处理固定数量的格子最多2^m个与数据量N无关在N118万时只占总查询时间的0.01%以下。这意味着即使未来用C重写网格搜索绝对速度会提升但缩放指数αN和αd不会改变因为它们反映的是算法本质不是实现语言。换句话说本文报告的所有相对性能趋势都是真实的算法行为而非Python开销造成的假象。---七、这一切对大型语言模型意味着什么研究团队在最后专门讨论了这些发现对Transformer架构的含义。如果把注意力机制理解为ANN搜索那么上下文长度对应数据量N每个注意力头的维度通常64到128维恰好在本研究覆盖的范围内对应dKV缓存的更新每处理一个新词就要往缓存里加一条记录对应索引更新频率。在这个映射下网格方法的特性——低索引更新成本、维度缩放表现平稳——恰好对应了长文本推理中KV缓存频繁增长、每次只插入一条记录而非重建整个索引的场景。研究团队指出网格方法插入一条新数据时只需要做一次格子分配操作远比图搜索方法的插入需要更新整个邻居图便宜。当然这个每次插入的具体成本以及它与预计算BFS兜底机制的交互效果研究团队明确列为待解决的未来工作。另一个未解问题是d-scaling crossover在Transformer的Key向量分布上是否依然成立GloVe向量有相对均匀的分布特性而Transformer的注意力Key向量通常具有更强的非均匀性和更重的尾部分布这可能会影响网格方法中均匀分格的假设成立程度。---归根结底这项研究做了一件看似简单却颇有价值的事把一个几十年前就存在、后来被边缘化的算法思路放进现代标准化评测框架里认真量化它在数据量和维度两个维度上的表现并与当前主流方法做了全面对比。结果发现它在N-scaling这一维度上的表现接近线性的代价在某些应用场景里是完全可以接受的而在d-scaling这一维度上它随维度增加的性能退化明显比其他方法温和——这个发现在现代高维嵌入盛行的背景下具有实际意义。与此同时它极低的索引建立成本使其在数据频繁更新的系统里具备了真正的竞争窗口。这并不是说网格方法要取代HNSW或FAISS而是说当你面对的系统需要频繁重建索引、数据维度持续增高、对每次查询的绝对延迟不那么敏感时有一个被遗忘的老方法值得重新考虑。---QAQ1多探针网格搜索在数据量很大时速度会变慢为什么还值得使用A多探针网格搜索在数据量增大时确实接近线性减速每多一倍数据速度大约慢一倍这比图搜索方法的亚线性代价要差。但它的优势在于建立索引极快——在118万条数据的测试中只需约8秒而图搜索方法需要几百甚至一千多秒。当一个系统需要频繁更新索引比如推荐系统实时加入新内容或者语言模型处理长文本时不断扩展缓存每次重建索引的时间节省可以弥补查询速度上的劣势使整体总成本更低。Q2多探针网格搜索为什么在高维数据上的性能退化比其他方法慢A核心原因是格子划分这个决策步骤在低维压缩空间通过PCA降维后的空间通常只有几个维度里进行完全不受原始高维度的影响。原始维度增加时只有最终的精确排名步骤会受到影响但这一步的计算量与候选数量线性相关并不因维度增高而产生指数级膨胀。相比之下图搜索方法需要在完整的高维空间里构建和遍历邻居图维度越高图中每个节点的邻域越难精确定义需要检查的节点就越多。Q3多探针网格搜索的三个超参数m、G、nprobe分别控制什么Am是PCA压缩的目标维度数决定把原始高维数据压缩到几维来做格子划分m越大格子分得越细但候选区域也越多G是每个维度上划分的格子数量G越大单个格子越小、里面的候选点越少nprobe是每次查询时检查的格子数量nprobe越大召回率越高但速度越慢。这三个参数共同决定了算法在召回率和查询速度之间的权衡点研究团队通过多目标优化算法NSGA-II系统地搜索了它们的最佳组合。