HNSW

3 秒看懂

一句话定义： HNSW 是一种基于多层跳表 + 小世界图的近似最近邻（ANN）搜索算法，以”在海量高维向量中极速找到相似向量”为核心能力，是当前几乎所有主流向量数据库的默认索引方案。

类比： 想象一本词典——最顶层索引只覆盖极少数字母（“A、M、Z”），快速锁定大区间；逐层下降到更密的索引，直到最终页逐词查找。HNSW 对向量做的就是这件事，只不过”字母顺序”被替换成了高维空间中的图导航。

一句话投资意义： RAG（检索增强生成）的底层基础设施，没有 HNSW 级别的 ANN 引擎，大模型就无法高效检索外部知识。

3 分钟产业解释

为什么 HNSW 突然变重要？

2023 年以来，大语言模型（LLM）从”纯参数记忆”走向”检索增强生成（RAG）“范式：先把文档切成 chunk、编码为高维向量（通常 768-4096 维），存入向量数据库；推理时对用户 query 做向量编码，在库中做最近邻检索，将 Top-K 结果拼入 prompt 送入 LLM。

向量检索的性能瓶颈直接决定了 RAG 的延迟和吞吐。 精确最近邻（暴力扫描）在百万级以上向量库中不可接受（O(n) 复杂度），必须用 ANN（近似最近邻）做剪枝。HNSW 恰好是当前 ANN 领域综合召回率/延迟/QPS 最优的通用算法之一。

产业定位

用户 Query
    │
    ▼
┌──────────────┐
│ Embedding 模型 │ ← 产生高维向量
└──────┬───────┘
       │ (query vector, e.g. 1536-d)
       ▼
┌──────────────┐
│  向量数据库    │
│ ┌──────────┐ │
│ │ HNSW 索引 │ │ ← 本页主角: ANN 检索
│ └──────────┘ │
└──────┬───────┘
       │ (Top-K 相似文档 chunk)
       ▼
┌──────────────┐
│  LLM 生成器   │ ← RAG 推理
└──────────────┘

几乎所有主流向量数据库（Milvus、Weaviate、Qdrant、Pinecone、pgvector、Vespa 等）均将 HNSW 作为默认或主力 ANN 索引选项。Meta 的 FAISS 库实现了 HNSW，而 Google 的 ScaNN 未采用 HNSW，其核心算法是基于各向异性量化结合 IVFPQ 等方案。在 RAG 成为 LLM 应用主流范式的当下，HNSW 是 AI 基础设施栈中”数据层”的核心算法组件。

15 分钟专家深入

1. 核心思想：跳表 + 小世界图

HNSW 由 Yu. A. Malkov 和 D. A. Yashunin 在论文 “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”（首次提交于 2016 年 arXiv，正式发表于 IEEE TPAMI 2018）中提出。其核心融合了两个经典结构：

2. 结构解析

多层图（Hierarchical Graph）：

• Layer 0（最底层）： 包含全部 n 个向量节点，每个节点最多有 M 条双向边（M 是核心参数，典型值 16-64）。
• Layer 1, 2, … L（逐层向上）： 每个向量被随机分配到某个最高层 l_{max}。分配概率通常按指数衰减——层数越高，节点越稀疏。l_{max} 的选取通常按 l_{max} = \lfloor -\ln(text(uniform)(0,1)) \cdot m_L \rfloor，其中 m_L = 1 / \ln(M)（论文默认设定）。
• Layer L（最顶层）： 仅包含极少数”高速公路入口”节点。

搜索过程（Query-Time Greedy Search with Beam）：

1. 从最顶层 L 的某个入口点（通常是首次插入的节点，记为 entry_point）开始。
2. 在当前层执行 贪心波束搜索（beam search，宽度 = ef）：从入口点出发，沿图边跳到离 query 更近的邻居，直到局部最优（所有邻居都不比当前最近点更近）。
3. 将当前层的最近点作为下一层的入口点，下降到下一层。
4. 重复步骤 2-3，直到 Layer 0。
5. 在 Layer 0 做最终的 beam search（宽度 ef 或 ef_search），返回 Top-K 结果。

构建过程（Insert-Time）：

1. 新节点 $q$ 被分配到最高层 l_{max}。
2. 从 Layer L 的 entry_point 开始，逐层贪心搜索到 l_{max}+1 层的最近邻，作为 l_{max} 层的入口。
3. 在 l_{max} 层及以下各层，分别做 beam search（宽度 = efConstruction），找到最近的 M 个邻居（Layer 0 为 2M），建立双向边。
4. 对每个邻居，检查其边数是否超过 M（或 2M），若超过则做 剪枝（pruning）：保留离邻居最近的 M 条边（启发式剪枝在论文中有详细描述，核心是保持图的连通性和多样性）。

3. 关键参数

⚠️ ef 是运行时可调的，这意味着用户可以在召回率和延迟之间动态权衡，无需重建索引——这是 HNSW 相比 IVF 等静态索引的显著优势。

4. 复杂度分析

核心痛点：内存。 对于 1 亿条 768 维 float32 向量，仅原始向量约占 307.2 GB（1e8 × 768 × 4 字节），加上 HNSW 图的邻接表（每条边 4 字节 int × 每节点约 2M-4M 条边 × 1e8 节点），图结构本身可能额外占用数十到数百 GB。实际部署中，HNSW 索引的内存占用通常为原始向量的 1.2-2 倍 [行业估算]。

技术原理（最深）

多层图结构详解

Layer L (最稀疏):     ●─────────●
                      ↑ 高速公路入口
Layer L-1:        ●───●─────●───●
                      ↑ 节点密度增加
Layer 1:      ●─●─●─●─●─●─●─●─●─●─●─●
                      ↑ 更密
Layer 0 (全集): ●●●●●●●●●●●●●●●●●●●●●●●●●●●●
               ↑ 所有 n 个向量，每节点 ≤ 2M 边

搜索过程伪代码

def hnsw_search(query, ef, K, entry_point, layers):
    # Step 1: 从顶层贪心下降到 Layer 1
    curr_nearest = entry_point
    for layer in range(max_layer, 0, -1):
        curr_nearest = greedy_search(query, curr_nearest, layer)
        # 在当前层沿最近邻边跳到局部最优(单点贪心)

    # Step 2: 在 Layer 0 做 beam search
    candidates = beam_search(query, curr_nearest, layer=0, ef=ef)
    # candidates: 一个大小 ≤ ef 的有序集合(按距离排序)
    # beam search 过程:
    #   - 维护 candidates (小根堆) 和 visited set
    #   - 从 entry_point 出发, 取堆顶(最近未访问节点)
    #   - 遍历其邻居, 若更近则入堆
    #   - 直到堆中最近的 ef 个节点都不再更新

    return top_k(candidates, K)  # 返回最近的 K 个

剪枝策略（Heuristic Pruning）

构建时，每个新节点找到 M 个候选邻居后，不是简单取最近的 M 个，而是执行启发式剪枝：

Prune(neighbors, M, new_node):
    result = []
    sorted_by_dist = sort(neighbors, by=distance_to(new_node))
    for candidate in sorted_by_dist:
        if |result| >= M: break
        # 只有当 candidate 比 result 中已有节点都"更不同"时才保留
        # (即 candidate 不被 result 中任何节点"覆盖")
        if dist(candidate, new_node) < dist(candidate, any_in(result)):
            result.append(candidate)
    return result

这一策略的核心目的是 保持图的多样性（diversity）——避免所有邻居都聚集在同一区域，从而保证搜索的全局可达性。这是 HNSW 召回率显著优于朴素 NSW 的关键设计之一 [Malkov & Yashunin, IEEE TPAMI 2018]。

小世界性质的保证

HNSW 继承了小世界图的长程/短程连接特性：在 Layer 0 的图中，每个节点既连接”近距离”邻居（greedy 搜索的有效局部导航），又连接”远距离”邻居（实现 O(log n) 跳数的”高速公路”）。上层进一步放大了”远距离跳跃”的效果——这正是 skip list 的核心思想，多层结构共同保证了搜索的对数扩展性。

技术演进史

技术路线对比

ANN 索引算法横向对比

注： 以上星评基于行业共识和典型 benchmark（ANN-Benchmarks、Big-ANN-Benchmarks）的定性总结，实际表现高度依赖数据集维度、分布、硬件配置。召回率/延迟的精确数字因测试条件不同差异较大，不在此编造具体数值。

上下游

上游（HNSW 依赖什么）

┌──────────────────────────────────────────────────────┐
│                    上 游                               │
├───────────────┬──────────────────────────────────────┤
│ Embedding 模型 │ OpenAI text-embedding-3,              │
│               │ Cohere embed-v3,                       │
│               │ BGE/Jina/BAAI 等开源模型                │
│               │ → 产出高维向量(768-4096维)              │
├───────────────┼──────────────────────────────────────┤
│ 距离度量       │ Cosine, L2 (欧氏), Inner Product       │
│               │ → HNSW 图中边的距离计算基础              │
├───────────────┼──────────────────────────────────────┤
│ 计算基础设施   │ 大内存 CPU 服务器(DDR5)                 │
│               │ → HNSW 图需常驻内存                     │
├───────────────┼──────────────────────────────────────┤
│ SIMD/向量化指令│ AVX-512, NEON, SVE 等                  │
│               │ → 距离计算的硬件加速                     │
└───────────────┴──────────────────────────────────────┘

下游（谁消费 HNSW 的结果）

┌──────────────────────────────────────────────────────┐
│                    下 游                               │
├───────────────┬──────────────────────────────────────┤
│ 向量数据库     │ Milvus/Zilliz, Weaviate, Qdrant,      │
│               │ Pinecone, pgvector, Vespa, ChromaDB    │
├───────────────┼──────────────────────────────────────┤
│ RAG 应用      │ 企业知识库问答、代码检索、法律/医疗AI     │
├───────────────┼──────────────────────────────────────┤
│ 推荐系统      │ 用户/物品 embedding 的实时匹配           │
├───────────────┼──────────────────────────────────────┤
│ 多模态搜索    │ 图文检索(CLIP embedding)、音视频检索      │
├───────────────┼──────────────────────────────────────┤
│ 去重/聚类     │ 近重复检测、语义去重                      │
└───────────────┴──────────────────────────────────────┘

关键指标

性能评估指标体系

关键权衡三角

         召回率 (Recall)
            ▲
           / \
          /   \
         / HNSW \
        /  sweet  \
       /   spot    \
      /             \
     ▼───────────────▼
 延迟/吞吐          内存
 (Latency/TP)     (Memory)

→ M↑ / ef↑: 召回↑, 延迟↑, 内存↑
→ M↓ / ef↓: 召回↓, 延迟↓, 内存↓
→ ef 运行时可调, M 需建索引时确定

供需与市场数据

需求侧驱动力

供给侧格局

注意： 向量数据库市场的精确规模数据各家口径差异大，Gartner/IDC 尚未给出统一的独立分类报告。市场处于早期高速增长阶段，具体 TAM 数字不在此编造。

代表公司与资本映射

公司/项目与 HNSW 的关系

投资视角： HNSW 本身是开源算法，无法直接”投资 HNSW”。投资路径是通过搭载 HNSW 的向量数据库公司、使用向量检索的 AI 应用公司、以及为 HNSW 提供硬件加速的芯片公司。

投资逻辑

看多逻辑

1. RAG 是 LLM 落地的必经之路：纯参数记忆的 LLM 存在幻觉和知识过时问题，RAG 通过外部检索弥补。只要 RAG 继续是主流范式，向量检索基础设施就有刚需。
2. HNSW 是事实标准：在 ANN-Benchmarks 等公开评测中，HNSW 在中等规模（1M-100M 向量）场景下的 recall-latency 综合表现长期位居前列，生态锁定效应强。
3. 向量数据库是新基础设施层：类比关系型数据库之于 Web 应用，向量数据库之于 AI 应用有”必经之路”属性。
4. 增量更新能力：相比 IVF 需要定期重建聚类，HNSW 天然支持增量插入，适合生产环境中数据持续写入的场景。

看空/风险逻辑

1. 内存瓶颈：HNSW 的最大短板是内存占用大。当向量规模达到 10 亿级，即使有 PQ 压缩辅助，内存成本也极高。DiskANN 等”磁盘友好”方案可能在超大规模场景蚕食份额。
2. GPU 加速难：HNSW 的贪心搜索本质上是串行的（每步依赖上一步的结果），难以充分利用 GPU 的大规模并行能力。NVIDIA 的 CAGRA 等方案用不同的图构建/搜索策略来适配 GPU，可能在高吞吐场景替代 HNSW。
3. 长上下文/大窗口 LLM 的冲击：如果 LLM 的上下文窗口持续扩大（如 1M+ tokens），部分 RAG 场景可能被”塞进上下文”替代，减少向量检索需求。
4. 算法迭代风险：新 ANN 算法不断涌现（如 HNSW2、Vamana、NSSG、CAGRA 等），HNSW 的”事实标准”地位并非不可撼动。

关键观察点

• 向量数据库公司的真实 ARR 和客户留存率
• 主要云厂商是自研 ANN 还是依赖开源库
• GPU-native ANN 索引（CAGRA 等）是否在 benchmark 上系统性超越 HNSW
• RAG 范式是否被长上下文 LLM 侵蚀

常见误读纠偏

❌ 误读 1：“HNSW 是精确搜索”

纠偏： HNSW 是 近似 最近邻（ANN）搜索。它不保证返回真正的 Top-K，而是在 ef 参数足够大时以高概率接近精确结果。当 ef = n（等于全部向量数）时退化为精确搜索，但此时无加速效果。实际部署中，Recall@10 在 95%-99.5% 的区间被认为是可接受的。

❌ 误读 2：“HNSW 只能在内存中工作”

纠偏： 经典 HNSW（如 hnswlib）确实要求全图驻留内存，但后续研究已将 HNSW 扩展到磁盘友好场景。典型代表包括：

• DiskANN（Microsoft Research）：使用 Vamana 图（与 HNSW 思路相似但做了磁盘 I/O 优化），向量存储在 SSD 上，仅将图结构和导航信息保留在内存中。
• hnswlib 的 mmap 模式：可通过内存映射将索引文件映射到虚拟内存，利用 OS 的页面管理做部分换入换出。
• SPANN（Microsoft Research）：将向量聚类到磁盘上的 posting list 中，仅在内存中保留索引结构。

因此更准确的表述是：经典 HNSW 是内存优先（memory-centric）的算法，但已有变体将其扩展到磁盘辅助场景。

❌ 误读 3：“HNSW 不支持删除”

纠偏： HNSW 原始论文未详细讨论删除操作，但实践中主流实现（如 FAISS、Milvus、Weaviate）都通过 标记删除（tombstone/deletion flag）+ 定期 compaction 的方式支持删除。即：逻辑删除时仅标记节点为已删除，查询时跳过；物理删除在后台 compaction 时重建受影响的边。这会带来一定的空间浪费和召回率波动。

❌ 误读 4：“HNSW 不需要调参，开箱即用”

纠偏： HNSW 的性能高度依赖 M、efConstruction 和 ef 三个参数的配置。M 和 efConstruction 在索引构建时确定且不可更改（需要重建索引），ef 可运行时调整。不当的参数选择会导致：

• M 过小 → 图连接度不足 → 召回率下降
• efConstruction 过小 → 图质量差 → 召回率天花板低
• ef 过大 → 延迟过高

生产环境中，参数调优通常是基于业务的数据规模、维度分布和延迟 SLA 的反复实验过程。

学习路径

推荐学习路径

Level 0: 概念理解
├── 阅读本文
├── 理解"为什么需要 ANN"和"HNSW 的多层图思想"
│
Level 1: 动手实验
├── 安装 hnswlib (pip install hnswlib)
├── 在 10 万条随机向量上体验 M/efConstruction/ef 的效果
├── 用 ann-benchmarks 跑对比测试
│
Level 2: 原理深入
├── 精读原论文: Malkov & Yashunin, IEEE TPAMI 2018
├── 阅读 hnswlib 源码（C++，约 2000 行，可读性好）
├── 理解 heuristic pruning 的数学直觉
│
Level 3: 系统集成
├── 在 Milvus/Weaviate/Qdrant 中部署 HNSW 索引
├── 测试不同 M/ef 对召回率/延迟/QPS 的影响
├── 研究标量过滤 + HNSW 搜索的融合策略（如 pre-filter vs post-filter）
│
Level 4: 前沿研究
├── 对比 DiskANN (Vamana)、CAGRA、HNSW2 等变体
├── 研究 GPU 加速 ANN 的并行化挑战
├── 关注标量-向量混合索引（hybrid index）的最新进展

关键论文/资源