分层可导航小世界图 (HNSW)

分层可导航小世界图(Hierarchical Navigable Small World,简称 HNSW)是一种高效的近似最近邻(ANN)搜索算法。它通过构建多层图结构,在高维向量空间中以对数级复杂度快速找到与查询向量最相似的若干邻居,是现代向量检索系统的核心索引之一。

概述

随着嵌入向量在语义检索、推荐和 RAG 中的普及,如何在海量高维向量里快速找相似项成为关键问题。精确检索需逐一比对,代价高昂。HNSW 借鉴小世界网络理论,把向量组织成分层图:上层稀疏、跨度大,用于快速接近目标区域;下层稠密、连接细,用于精确定位。查询时自顶向下逐层贪心跳转,大幅减少比较次数。

核心原理

• 分层结构:节点按概率分配到不同层数,越高层节点越少,连接跨度越大。
• 贪心导航:搜索从顶层入口开始,每层向最接近查询的邻居移动,再下沉到下一层。
• 可导航小世界:每层图既有近距离连接保证精度,又有长程连接保证跳转效率。
• 近似权衡:通过邻居数量等参数,在检索精度、速度和内存占用之间调节。

应用场景

HNSW 被 FAISS、Milvus、Qdrant、Weaviate 等主流向量数据库采用,支撑语义搜索、以图搜图、推荐系统和检索增强生成等应用。在 RAG 流程中,它负责从知识库中快速召回与用户问题最相关的文档片段,是整条链路的性能关键。

常见问题

问:HNSW 检索是精确的吗?答:不是。它属于近似最近邻算法,会以极小的召回损失换取巨大的速度提升,实际应用中通过参数调节可以让近似结果非常接近精确解。

问:HNSW 的主要缺点是什么?答:它的图结构需要常驻内存,索引占用较大;且插入和删除数据的动态更新成本较高,不如某些索引对增量更新友好。