Malkov & Yashunin (2016/2018) — HNSW：分层小世界图做近似最近邻搜索

一句话总结

这篇论文提出了 HNSW（Hierarchical Navigable Small World）：用一个分层的图索引来做近似最近邻搜索。直觉上，它把“先粗找大方向、再细找局部邻居”变成了一个非常高效的图导航过程，因此在很多数据集上都能做到又快又准。

论文信息

标题：Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
作者：Yu. A. Malkov, D. A. Yashunin
arXiv：https://arxiv.org/abs/1603.09320
说明：论文最早提交于 2016，常引用版本是 2018 的 v4

这篇论文到底在解决什么问题

假设我们有一大堆向量：

图片 embedding
文本 embedding
用户 / 商品 embedding
任意定义了距离函数的数据点

给定一个查询向量 q，我们想找出数据库里离它最近的几个点。

最笨的方法是：

把 q 和库里每个点都算一遍距离
然后取最小的几个

这种做法是 线性扫描，数据量一大就太慢。

于是人们研究 ANN（Approximate Nearest Neighbor）：

不要求 100% 精确
允许“几乎总能找到真正最近邻”
换来巨大的速度提升

HNSW 就是在这个背景下提出的。

先给数学小白的核心直觉

把所有数据点想象成一张城市地图上的地点。

暴力搜索

像是：

你站在一个新地点
想知道离你最近的咖啡馆
于是把全城所有咖啡馆都走一遍比较距离

当然很慢。

普通图搜索（论文里的 NSW）

另一种办法是：

每个地点只连到它附近的一些地点
你从某个入口开始
每次都走向“离目标更近”的邻居

这像在地图上“顺着感觉越走越近”。

这个想法已经比暴力搜索快很多，但会有两个问题：

容易卡在局部最优：附近看起来没有更近的路了，但其实远一点有更好的方向。
数据量变大后，搜索路径和中间要看的节点也会越来越多。

HNSW 的关键升级

HNSW 说：

只给一层图不够，我给你很多层。

最上层：点很少，连的是很长距离的“高速路”
中间层：点更多，路更细
最底层：包含全部点，连的是局部短距离邻居

搜索时：

先从最上层开始，大步接近目标
到下一层后，从刚才找到的位置继续找
一层层往下，越来越精细
最后在底层得到近邻结果

这很像：

先坐飞机到目标城市附近
再坐高铁到目标城区
再打车到目标街区
最后步行到门口

这就是 HNSW 最核心的思想：

利用层级，把“远距离导航”和“近距离精修”分开做。

论文的核心贡献

作者自己强调的点，翻译成人话主要有 4 个：

1. 用分层结构替代单层小世界图

这是 HNSW 和 NSW 最本质的区别。

2. 明确选择搜索入口

搜索总是从最高层的入口点开始，不再像某些旧方法那样依赖多个随机入口。

3. 把不同尺度的边分开

上层保留长程边，下层保留短程边。这会让搜索更像“先看大局，再看细节”。

4. 用更聪明的邻居选择启发式

不是简单选最近的 M 个点，而是希望邻居方向更“多样化”，避免所有边都扎在同一个局部簇里。

这一点对聚簇数据特别重要。

HNSW 的数据结构到底长什么样

总体结构

HNSW 是一个多层图：

layer 0：底层，包含所有点
layer 1：上面一层，只包含部分点
layer 2：再上面一层，只包含更少的点
…
越往上点越少

每个点会被随机分配一个“最高层级”。如果一个点的最高层是 3，那么它会出现在：

layer 0
layer 1
layer 2
layer 3

但不会出现在更高层。

为什么高层点更少

论文里让层级满足一种指数衰减概率分布。直觉上就是：

大多数点只在底层
少数点能出现在更高层
极少数点出现在最高层

所以越高层越稀疏。

这和 skip list 很像：

底层存全部元素
上层只抽样一部分“代表点”

论文也明确说了：

HNSW 可以看作把 skip list 从“一维有序链表”推广到了“多维近邻图”。

这个类比非常重要。

skip list 是什么，为什么这里会提它

如果爹以前没碰过 skip list，可以这么理解：

普通链表查找像一步一步走路。 skip list 会加很多“快车道”，让你先跳着走，再落到局部细找。

HNSW 本质上做了同样的事，只不过：

skip list 里的“边”是有序链表上的 next 指针
HNSW 里的“边”是空间里“可能更接近目标”的邻居连接

所以可以把 HNSW 看成：

一个为近邻搜索设计的、图版的 skip list。

搜索过程到底怎么做

论文给出了搜索算法（可理解为 K-NN-SEARCH）。

阶段 1：从顶层往下做贪心下降

从最高层入口点开始。在每一层：

看当前点的邻居
如果有邻居更靠近查询点，就走过去
重复直到这层走不动
然后下降到下一层

这里 ef=1，基本是非常轻量的贪心找路。

直觉：

顶层图很稀疏，但边很长
它适合做“全局导航”

阶段 2：到底层做更仔细的候选搜索

到了 layer 0 后，作者不再只用单一路径贪心，而是维护一个候选集。

可理解成：

不只盯着一个当前位置
而是保留一小撮“目前看起来最有希望的点”
不断扩展它们的邻居
最后从中返回前 K 个最近邻

这里的关键参数是：

ef

ef 越大：

搜得越仔细
召回越高
但速度越慢

所以 ef 是一个典型的精度 / 性能平衡旋钮。

论文里的 recall 是什么意思

这篇论文一直在讲 recall。

数学小白版定义：

假设真实最近的 10 个点里，算法找到了 9 个
那么 recall = 0.9

所以：

recall 越高，说明结果越接近真值
ANN 系统通常都是在比较“在某个 recall 下谁更快”

构图（插入）过程怎么做

论文不是先离线把整张图一次性算完，而是采用 incremental insertion：

点一个一个插进去
每插入一个点，就更新各层连接

这也是 HNSW 非常实用的地方：

它支持增量构建，不需要每次全量重建。

插入一个新点时做什么

假设新点是 q。

第一步：随机决定它能上到哪一层

论文中用的是随机层级生成：

层级越高，概率越低
所以高层是稀疏抽样

第二步：从当前最高层开始往下找

和搜索过程类似：

从入口点开始
在上层做轻量贪心下降
直到走到新点所属层级之上

第三步：在它出现的每一层里找候选邻居

从 min(当前最高层, 新点最高层) 一直到第 0 层：

在这一层做更充分的搜索
找到一批离 q 近的候选点
从这些候选点里挑出真正要连边的邻居

第四步：双向连边

q -> neighbor
neighbor -> q

如果某个旧节点的邻居数超出上限，就要裁剪邻居列表。

这就是构图的基本过程。

这篇论文最关键的工程点：邻居不是简单选最近的 M 个

这部分非常重要，也是 HNSW 为什么比“裸 kNN 图”更稳的关键之一。

朴素做法

如果只是把新点连到最近的 M 个点，会发生什么？

在聚簇数据里，很可能这 M 个点全在同一个小团里。这样会导致：

局部内部连得很密
不同簇之间缺少桥梁
搜索容易卡在簇边界出不去

HNSW 的启发式做法

论文里的 heuristic 大意是：

按照候选点离 q 的距离，从近到远看
准备把某个候选点 e 加进邻居集合时，不仅看它离 q 近不近
还看：它是不是被已经选中的那些点“遮住了”

如果 e 相对于 q 来说，并没有提供新的方向，而只是和已选邻居高度重复，那就不选它。

这样得到的邻居集合会更“分散”、更“多样”。

通俗理解

你不是只找“最近的几个朋友”，而是找：

左边有个熟人
右边有个熟人
前面有个熟人
远处还有个能通向另一个社区的熟人

这样整张图更容易导航。

为什么这对聚簇数据特别重要

论文里专门画图解释了这个问题：

新点在 Cluster 1 边界附近
如果只选最近点，可能全选 Cluster 1 里的点
这样 Cluster 1 和 Cluster 2 之间的桥就断了
heuristic 会有更大概率保留跨簇连接

所以 HNSW 在 clustered data 上更稳。

参数到底是什么意思

论文里最常见的参数有这些：

1. `M`

每个节点希望保留的邻居数规模。

通俗理解：

每个点最多愿意认识多少个“关键朋友”

M 小：

图更稀疏
内存更省
搜索更快
但 recall 可能下降

M 大：

图更密
内存更大
recall 往往更高
构建和查询都可能变慢

论文提到经验上合理范围常在 5 ~ 48。

2. `efConstruction`

构建时搜索候选邻居的宽度。

通俗理解：

新点插入图中时，你愿意多认真地找邻居

越大：

建图更慢
但图质量更高
后续查询 recall 通常更好

3. `ef`

查询时底层搜索的候选列表大小。

越大：

查询更慢
但 recall 更高

这是线上服务里最常调的参数之一。

4. `mL`

控制层级分布的参数。

论文建议一个自然选择：

mL ≈ 1 / ln(M)

你不用死记公式，只要记住它在控制：

高层到底稀不稀
各层之间重叠多少
搜索时“层级分解”效果好不好

5. `Mmax0`

底层允许的最大连接数。

论文发现：

如果底层连接数限制太小，会影响高 recall 表现
经验上 Mmax0 ≈ 2 * M 是不错的选择

这也是后续很多实现里的常见经验。

为什么它能做到接近对数复杂度

这是论文最“数学味”的部分，但其实直觉可以讲得很简单。

单层图为什么不够好

如果只有一层图：

图里既有近邻关系，又承担远程导航任务
随着数据增大，搜索通常要经过越来越多“枢纽”
节点度数和路径代价都会变大
所以复杂度容易变成 polylog 或更差

分层之后发生了什么

HNSW 把路按尺度拆开：

顶层负责长距离跳跃
中层负责中等尺度修正
底层负责局部精修

每一层只需要处理自己这个尺度的导航问题。

如果：

每层平均花的工作量是常数量级
层数是 O(log N)

那么总复杂度就是：

O(log N)

这就是论文声称“logarithmic complexity scaling”的核心来源。

论文的更正式说法

论文在复杂度分析里大意是：

每层之间的点是随机抽样形成的，和空间位置不强相关
在理想图条件下，从上一层降到下一层后，找到该层最合适位置所需的步数，期望可以看作有界
总层数随数据规模是对数增长
所以整体搜索复杂度接近 O(log N)

当然这是带假设的分析，并不是“任何数据都严格数学证明成立”。论文也坦诚说：

实际图不是精确 Delaunay graph
高维情况下更难严格分析
但实验上看 scaling 非常好

Delaunay graph、relative neighborhood graph 这些名词到底要怎么理解

这几个词一眼看上去很吓人，但不用怕。

Delaunay graph

可把它理解成：

一张“理想导航图”
如果你有它，贪心走图就很容易找到最近邻

但问题是：

它往往难构建
尤其高维下更难

relative neighborhood graph

这是比 Delaunay 更“稀”一些的图。可以理解成：

只保留那些非常有必要的边
去掉很多冗余边

论文说他们的邻居选择 heuristic，在候选足够多时，会逼近一种有利于保持全局连通性的图结构。

爹完全不需要背定义，只要记住：

作者想要的是一种既不太密、又足够容易导航、还能保留跨簇连接的图。

HNSW 的 heuristic 就是在近似干这个事。

论文中的 SEARCH-LAYER 在做什么

它可以理解成“带回溯的 best-first 图搜索”。

维护两个集合：

候选集 C
当前最好结果集 W

过程是：

从入口点开始
每次取候选集中最靠近查询的点 c
扩展它的邻居
如果发现了更好的点，就加入候选和结果
当候选集中最好的点都已经不可能改进当前结果时，停止

这比简单贪心更稳，因为：

你不是一条道走到黑
你保留了回头试别的支路的机会

这也是底层 recall 能上去的重要原因。

HNSW 和 NSW 的差别

NSW

单层图
也利用小世界导航
已经很强
但更容易受数据结构影响
在低维或聚簇数据上会明显退化

HNSW

多层图
更好的入口策略
更好的邻居选择 heuristic
更好的复杂度 scaling
更稳健

论文的结论很明确：

HNSW 基本上把 NSW 的弱点补掉了。

论文实验讲了什么

论文实验部分主要做了几类比较。

1. 和基础 NSW 比

结论：

HNSW 在相同 recall 下需要更少距离计算
数据规模变大时，HNSW scaling 更好
实际耗时也更好

2. 和当时多个开源 ANN 方法比

包括：

FLANN
Annoy
VP-tree
FALCONN
以及产品量化类方法的对比

论文整体结论是：

在很多向量数据集上，HNSW 明显领先
高维数据上尤其强
低维和聚簇数据上也比旧 NSW 稳很多

3. 在一般 metric space 上也表现稳定

这点很重要。很多方法只适用于向量空间、L2、cosine 之类。而论文强调 HNSW 是：

general metric space method

也就是说，只要你有距离函数，不一定非要是欧氏向量，也能用。

当然，工业界今天最常见的还是 embedding 向量场景。

为什么 HNSW 后来这么火

因为它同时满足了几个工业界极其看重的性质：

1. 快

搜索性能非常强。

2. 准

用合适参数能把 recall 拉得很高。

3. 支持增量构建

不是只能离线一次性建完。

4. 结构简单、工程可实现

没有过于复杂的训练过程，也不依赖很重的量化前处理。

5. 适配范围广

对不同数据分布通常都比较稳健。

这几个性质叠在一起，让它几乎成了近几年向量检索系统里的“默认强基线”。

如果我是数学小白，我应该怎么理解“分层小世界图”

可以直接记成这句话：

底层管精确邻居，上层管快速导航。

再展开一点：

每个点在底层都有
只有少数点能升到高层
高层像稀疏骨架
搜索时先在骨架上快速接近目标
再落到底层精修

这个直觉已经足够理解 HNSW 80% 的本质。

如果我是工程师，我应该抓住哪些最关键的点

1. HNSW 不是树，它是图

所以它不像 KD-tree 那样容易被高维严重打爆。

2. 真正决定效果的是三件事

分层
底层 beam search（ef）
多样化邻居选择 heuristic

3. 参数调优方向很明确

提高 recall：增大 ef、efConstruction、可能增大 M
降低内存 / 提高速度：减小 M 或 ef

4. 它是 ANN，不是 exact NN

如果你把参数压得太狠，它也会漏真近邻。

论文的局限和没讲透的地方

这篇论文虽然非常经典，但也不是完美无缺。

1. 理论分析不算彻底

它给了很强的直觉和部分分析，但不是“所有情形下严格证明”。尤其在高维空间里，很多性质更多依赖实验结果而不是完全严密的理论闭环。

2. 删除 / 更新问题没有完整展开

论文主要关注插入和查询。真实系统里，删除、更新、压缩、并发等问题会更复杂。

3. 分布式实现只是提了方向

论文说和 skip list 类似，理论上可做 balanced distributed implementation，但具体工业级分布式方案不是这篇论文重点。

4. 高维数据上的“为什么这么有效”更多是经验与结构直觉

不是严格证明说“所有 embedding 分布都一定最好”。不过工程上它的效果已经足够强，大家愿意先用再说。

这篇论文真正重要的历史意义

它的重要性不只是“提出一个更快算法”，而是：

1. 统一了一个很强的工程范式

即：

用图做 ANN
用层级解决全局导航
用 beam/candidate list 提升底层搜索质量

2. 让图索引成为主流路线

后来的大量向量数据库、ANN 库都直接或间接受到它影响。

3. 它在“效果 / 速度 / 可实现性”之间取得了极好平衡

很多论文理论更漂亮，但工程落地没这么顺。 HNSW 是少数既经典又真正被大规模采用的方案。

我自己的理解

我觉得这篇论文最厉害的地方，是它把几个原本分散的想法揉成了一个很优雅的整体：

小世界导航：图上贪心走，能很快靠近目标
层级抽样：高层做粗导航，低层做细搜索
候选集回溯：避免纯贪心卡死
多样化邻居选择：保持图可导航性和跨簇连通性

每个点单独看都不是石破天惊，但组合起来就非常强。

这类论文特别像优秀系统论文：

未必用最重的数学
但抓住了真正影响性能的结构因素
最后做出“理论足够、工程极强、实验非常赢”的方案

给数学小白的最终复述

如果爹只想记住最核心的一版，可以记这段：

HNSW 是一种近似最近邻搜索方法。它把数据点连成多层图：上层点少、边长，适合快速从远处接近目标；下层点多、边短，适合局部精修。搜索时从最高层入口开始，一层层往下，每层都把当前位置往更靠近查询的方向推进，最后在底层用一个更仔细的候选搜索得到结果。它比旧的单层图方法更快、更稳，对高维、低维、聚簇数据都表现很好，因此后来成了向量检索领域最经典、最实用的索引之一。

可以继续深挖的后续问题

HNSW 和 IVF / PQ / ScaNN / DiskANN 的本质差别是什么？
HNSW 的 M、efConstruction、efSearch 在工业上怎么调？
为什么图索引在 embedding 检索里这么强？
HNSW 在内存占用、动态更新、删除上的真实代价是什么？
向量数据库里的 HNSW 实现和原论文相比改了什么？

风车车知识库

探索

hnsw-malkov-yashunin-2016

目录