走过十年仍在第一梯队：千亿级数据！毫秒级搜索算法！

2016 年，我在博士期间提出了 EFANNA 算法；一年后，我又提出了 NSG（Navigating Spreading-out Graph） ——一种能让 AI 在亿级数据中实现毫秒级查找 的图向量检索算法。

从 EFANNA 到 NSG，这些算法已经陪我走过将近十年的研究旅程。站在 2025 年的今天，我也很好奇：它们现在还处在什么位置？

自己说好不算数，我们不妨看看外部视角：学术界和工业界的评价。最近，数据库领域国际顶会 SIGMOD 2025 公布了一篇来自法国团队的系统性研究——《Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art》。

这篇论文回顾了近十年来图向量检索算法的发展脉络，并在多个大规模数据集上对 12 种主流算法进行了对比实验（最大规模达到10亿向量）。

结果显示，性能最优的算法通常采用“邻域扩展（neighborhood propagation）”与“邻域多样化（neighborhood diversification）”两类设计策略。作为这一路线下的代表性方法，NSG 在评测中依旧展现出稳定而突出的表现，处在高召回、低延迟的第一梯队。

01

图向量检索的演化路径：

从结构探索到索引融合

我们先来看看，图向量检索算法经历了一个怎样的研究历程。这里作者们做了一个很好的脉络梳理，而我在这个总结的基础上给图算法发展进一步划分了三个阶段，如下图：

1. KNN 图与随机图

绿框是图算法发展的第一阶段：基于K近邻图和随机图的结构探索。无论什么图算法，主要通过贪婪游走（类A*算法）来完成检索。那么图结构及其理论支持最为重要。而在图几何拓扑的茫茫大海中，K近邻图（KNNG）和随机链接图拥有比较好的理论基础，那么初期的尝试也从此开始。

2. 图稀疏化：裁剪边，提升效率

红框是图算法发展的第二阶段，图的稀疏化。这一阶段研究者们发现图索引中，并不是所有边都有价值，因此我们可以对第一阶段的一些不错的图索引进行有效的裁剪，来得到一个精简、稀疏但高效的索引。

3. 索引融合：跨越单一瓶颈

最下面蓝框代表的是图算法发展的第三阶段：索引融合。这一阶段研究者们开始发现图索引的非最优性，即在特定的数据集上图算法出现明显的瓶颈，其中代表性的就是ELIPS——把图结构和Hercules EAPCA树进行结合。LSHAPG把图索引和哈希表结合。通过吸收不同向量检索算法的优势来强化效果。

从第三阶段的发展来看，我们也大概能得到一个结论：图索引的算法基础已经陷入明显的瓶颈。从我的NSG引入了图裁剪带来效果提升的理论基础后，后续几年图算法在裁剪策略上没有获得更明显、有效的提升了。

02

NSG 的定位与实证：

高性能算法第一梯队

在 SIGMOD 2025 的实验结果中，我曾提出的 NSG、SSG 依然稳居第一梯队，尤其在高召回、低延迟的任务中表现突出。这说明：尽管过去十年涌现了许多新方法，NSG 依旧是图检索的标杆算法之一。

上图我篮框圈选出来了文章实验部分NSG、SSG所在位置，处在高recall 低延迟的位置。

同时也能看到，单一图算法的优化已接近瓶颈。这为我们提供了一个重要启示：未来十年，复合索引将是主题。这一点也可以从广为人知的ANN Benchmark

https://github.com/erikbern/ann-benchmarks?tab=readme-ov-file的结果观察到：

图中第一梯队的方法Descartes(https://github.com/01-ai/Descartes）是零一万物开发的基于图和量化算法结合的复合型算法，利用了量化算法的距离计算加速和图算法的快速导航，是常见的两阶段或多阶段检索加速算法。

02

方法延伸：

从NSG到MAG的演进

如果说 NSG 解决的是 欧式空间中的图裁剪问题，那么我近年的工作则顺应了 内积相似度（cosine / dot product）崛起的趋势。

过去两年，向量检索研究已从 理论结构优化 转向 复合加速与产品化。在这一背景下，我研发了两类新算法：

1. PSP：定位与 NSG 类似，但作用在泛内积检索 场景。它首次证明了内积与欧式检索的对偶性，为内积检索奠定了系统的理论基础。

2. MAG：更强调产品化与易用性。它将内积和欧式度量统一在一套图索引中，用户无需维护多套索引，就能在两种度量之间无缝切换，大幅降低了工业应用门槛。

我们接下来的工作则是推动MAG的进一步产品化，在更加广泛的不同模态、维度、分布的大规模向量数据库中，分析当前图算法在内积、欧式两种度量下的短板，从而研发一种对数据集分布不敏感、自适应，同时融合多阶段复合索引的傻瓜式检索算法，尽量让用户可以一键集成、几乎无需调参就可以获得极致检索加速、享受高精度召回。

如果你对这方向感兴趣，欢迎加入我们的开源项目，我们的团队有工作十余年经验丰富的大厂老兵，有顶会发表多篇论文的博士生青年才俊，欢迎和我们一起探索下一代向量检索！

开源代码

NSG：https://github.com/ZJULearning/nsg

SSG：https://github.com/ZJULearning/SSG

PSP：https://github.com/ZJU-DAILY/PSP

MAG：https://github.com/ZJU-DAILY/MAG

欢迎同行们评论、留言、私信！

我是傅聪Cong，《业务驱动的推荐系统：方法与实践》作者，高性能向量检索算法NSG、SSG、PSP、MAG的发明者，资深算法专家，现居新加坡。

我们的算法团队和国内外很多一流大学和实验室都有长期paper合作，方向不限于大模型、搜推广、机器学习！

我们也非常欢迎各界研究者，一起合作探索出产学研结合、高可用性的算法！

github主页：https://github.com/CongFu92

个人邮箱：fucong92@126.com

傅聪Cong

NSG/SSG/PSP/MAG作者

向量检索/搜推广资深算法专家

别忘了点一下「在看」