HNSW — 多层近邻图让向量检索从 O(N) 降到近似 O(log N)

是什么

HNSW（Hierarchical Navigable Small World，分层可导航小世界图）是一套给海量向量做”找近邻”的索引结构。日常类比：在一个大商场找一家奶茶店，你不会一家家挨着扫——先看楼层导览（最高层稀疏、跳得远），再看楼层平面图（中间层），最后走到那条走廊（最底层精确定位）。HNSW 就是把”楼层导览”思想搬到向量索引上。

底层数据是一堆 d 维向量（比如把每篇文档做 embedding 得到 768 维数字）。HNSW 不存树也不存哈希桶，只存一张”每个向量连着 M 个最近邻居”的图，再把它分成多层：

Layer 2:  •—————————•           # 几百个点，长边多，用来跳
Layer 1:  •—•———•——•——•         # 几千个点
Layer 0:  •—•—•—•—•—•—•—•—•—•   # 全部点，短边多

查询从最高层一个入口点开始，每层贪心走到该层局部最近，再下一层继续，直到第 0 层返回 K 个最近邻。

为什么重要

不理解 HNSW，下面这些事都没法解释：

• 为什么 ChatGPT 那种 RAG 系统能在百万文档里 50ms 内召回相关段落
• 为什么 Pinecone / Milvus / Qdrant / Weaviate / pgvector 默认都选 HNSW，不用 KD-tree 或 LSH
• 为什么调向量库时总出现 M、efConstruction、ef 三个参数——它们直接控制召回-延迟曲线
• 为什么向量库内存占用比”原始数据 + 一点索引”大得多，删数据还可能越删越慢

核心要点

HNSW 的精髓可以拆成 三个机制：

1. 跳表式分层：每个新点按概率 p = 1/ln(M) 决定它最高出现在哪一层。类比：跳表（skip list）里高层节点稀疏。这样上层只有少数点，搜起来跳得远；下层节点全，搜得精。

2. 小世界图 + 贪心搜索：每层都是一个”邻居图”——每个点连到自己最近的 M 个邻居。查询时从入口点出发，只看邻居里离 q 最近的那个，跳过去；不能再近了就停。这一步类比：在朋友圈里找”认识 Linus 的人”，每问一个朋友给你最接近的下一个介绍。

3. ef 搜索宽度：贪心容易卡局部最优。HNSW 同时维护一个”动态候选堆”，宽度由 ef 参数控制——ef=1 是纯贪心，ef=200 是几乎全图扫。ef 越大召回越高、QPS 越低，是最重要的运行时旋钮。

实践案例

案例 1：用 hnswlib 建一个 100 万向量的索引

import hnswlib, numpy as np

dim, num = 128, 1_000_000
data = np.random.random((num, dim)).astype('float32')

# 1. 建索引：M=每点邻居数，ef_construction=建图时搜索宽度
p = hnswlib.Index(space='cosine', dim=dim)
p.init_index(max_elements=num, M=16, ef_construction=200)
p.add_items(data)

# 2. 查询：ef 越大越准，但越慢
p.set_ef(50)
labels, distances = p.knn_query(data[:5], k=10)

逐部分解释：

• M=16 每个点连 16 个邻居——经验值，越大越准但内存翻倍
• ef_construction=200 建图时为每个新点找邻居用的候选宽度
• ef=50 查询时的宽度，调它换召回-延迟

案例 2：参数怎么影响召回-延迟（最容易踩的地方）

for ef in [10, 50, 100, 200]:
    p.set_ef(ef)
    # 跑 1000 次查询，跟暴力解对比
    recall, qps = benchmark(p, queries, ground_truth)
    print(f"ef={ef}  recall={recall:.3f}  QPS={qps:.0f}")
# ef=10   recall=0.71   QPS=18000
# ef=50   recall=0.95   QPS=9000
# ef=100  recall=0.98   QPS=5000
# ef=200  recall=0.99   QPS=2500

这条曲线每个数据集都不一样，必须自己跑——别照搬别人的 ef。

案例 3：在 Postgres 里启用（pgvector 0.5+）

CREATE EXTENSION vector;
CREATE TABLE docs (id bigserial, emb vector(768));

-- HNSW 索引（pgvector 默认与 IVFFlat 二选一）
CREATE INDEX ON docs USING hnsw (emb vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);

-- 查询时调宽度
SET hnsw.ef_search = 100;
SELECT id FROM docs ORDER BY emb <=> '[...]' LIMIT 10;

<=> 是 pgvector 的余弦距离运算符；ef_search 就是上面那个 ef。

踩过的坑

1. ef 选小了召回崩：默认 ef=10 在大维度上常常召回 < 80%，业务以为”模型不行”，其实是索引参数没调；必须画召回-QPS 曲线再选。
2. 内存爆：每个向量除了原始 d×4 字节浮点，还要存 M~32 条邻居指针（每条 4-8 字节），1 亿 × 768 维向量轻松吃 100GB+；上线前必须算清楚。
3. 删除会让图退化：HNSW 没有原地删除。删点要么留墓碑（图越来越烂、召回降），要么定期全量重建（停服几小时）；高更新场景要慎选。
4. 距离函数 / 归一化不一致：训 embedding 时用 cosine，但建索引选了 L2，召回会莫名很差；很多人调一周才发现是这里。

适用 vs 不适用场景

适用：

• RAG / 语义搜索：百万到十亿级 embedding，要求毫秒级 top-K
• 推荐召回：用户/物品向量化后做 ANN 候选集
• 图像 / 音频去重：CLIP / wav2vec embedding 后近邻搜索
• 数据基本只追加、偶尔批量重建

不适用：

• 数据频繁单条删除 / 更新（图退化严重）
• 内存吃紧、向量量极大但预算紧 → 考虑 IVF-PQ 量化方案
• 需要精确最近邻（HNSW 是近似，召回 99% 也意味着 1% 偏差）
• 维度极低（< 10 维）→ KD-tree 通常更优

历史小故事（可跳过）

• 1998 年：Watts & Strogatz 提出 small world 网络模型——少量”长程边”能让任意两点平均跨 6 步可达，启发了后续的近邻图算法。
• 2014 年：Malkov 等提出 NSW（Navigable Small World），单层近邻图，但搜索容易在密集区卡死。
• 2016 年 3 月：Malkov & Yashunin 把跳表（Pugh 1990）的分层思想搬到 NSW，发 arXiv 1603.09320。
• 2018 年：论文正式发表于 IEEE TPAMI，立刻成为向量检索新基线。
• 2019 年起：Faiss、Milvus、Pinecone、Qdrant、Weaviate、pgvector、Lucene 9 相继把 HNSW 作为默认或一等公民索引。LLM RAG 浪潮把它推到几乎”事实标准”。

学到什么

1. 跳表 + 小世界图 + 贪心 = ANN 实战最优解——理论简单、工程友好、参数少。
2. 召回-延迟是一条曲线，不是一个点；任何向量库选型都必须画出这条曲线再决策。
3. 建图和查询是同一段代码——HNSW 不引入额外辅助结构，运维心智负担低。
4. 任何”看似简单”的图算法落地都会被高维灾难、内存、删除、并发折磨——读论文和上生产中间还有大量工程细节。

延伸阅读

• 论文 PDF：arXiv:1603.09320（30 页，前 10 页就够）
• 视频：Pinecone — How HNSW Works（带动画）
• 实战库：hnswlib 原作者实现，C++/Python
• 工程帖：Qdrant — HNSW Internals
• skip-list-1990 —— HNSW 的分层结构来自跳表
• graphrag —— RAG 系统里 HNSW 是默认召回引擎

关联

• skip-list-1990 —— 跳表是 HNSW 分层概率 1/ln(M) 的直接灵感来源
• comer-1979-btree —— B-Tree 解决磁盘随机访问，HNSW 解决高维近邻；都是”分层降复杂度”思路
• graphrag —— RAG 检索层几乎都用 HNSW
• spanner-2012 —— 同样是工业界主流默认实现，但解决的是分布式事务问题
• lsm-tree-1996 —— LSM 优写、HNSW 优查；现代向量库经常 LSM 存原向量 + HNSW 做索引
• shannon-1948 —— embedding 本质是把高熵语义压成低维向量，HNSW 在这空间里找近邻

反向链接

• comer-1979-btree —— Comer 1979 — B-Tree 综述：为什么这棵树到处都有
• diskann-2019 —— DiskANN — 单机十亿向量近邻检索（图存 SSD）
• faiss —— FAISS — 向量检索的标准件库
• graphrag —— GraphRAG — 微软的知识图谱 + RAG
• hnswlib —— hnswlib — HNSW 论文作者写的参考实现，业界向量库都基于它
• lsm-tree-1996 —— LSM-Tree 1996 — 写优化存储引擎
• product-quantization-2011 —— Product Quantization — 把向量切碎再压成几个字节
• salton-vsm-1975 —— Salton VSM 1975 — 把文档变成向量再用余弦比相似度
• scann-2020 —— ScaNN — 让向量量化只精修「客户会看到的那一面」
• shannon-1948 —— Shannon 1948 — 信息论的诞生
• skip-list-1990 —— Skip List — 用抛硬币代替平衡树
• spann-2021 —— SPANN — 内存放中心、SSD 放向量的十亿级近邻检索
• spanner-2012 —— Spanner 2012 — 用原子钟和 GPS 给全球数据库发时间戳
• vespa —— Vespa — Yahoo 检索 + 排序引擎
• youtube-two-tower-2019 —— YouTube 双塔召回 — 把 DSSM 搬进推荐并补上两件工业关键