揭秘高维向量相似度检索算法：从 ANN 到 HNSW

或哈希表实现 $O(\log N)$ 或 $O(1)$ 的精确匹配。然而，在处理由大模型产生的上百维甚至上千维的向量嵌入时，由于**“维度灾难（Curse of Dimensionality）”**，高维空间中任意两点之间的距离趋于相近，传统的空间分区索引（如 KD-Tree）会退化为 $O(N)$ 的暴力全表扫描。

为了在毫秒级内完成海量向量的检索，科学家们提出了近似最近邻搜索（ANN, Approximate Nearest Neighbor）。其中，最闪耀的明星算法当属 HNSW（Hierarchical Navigable Small World）。

1. 从最近邻（KNN）到近似最近邻（ANN）

精确最近邻搜索（KNN）要求必须返回全局绝对最近的点。但在数十亿级高维向量场景下，计算每个向量的距离在数学上是不现实的。

近似最近邻（ANN）做出了妥协：允许牺牲极小比例的精度（Recall），换取成百上千倍的检索速度提升。ANN 算法的核心在于如何快速缩小搜索空间，目前主流的 ANN 方法有三类：

1. 基于树的方法（Tree-based）：如 KD-Tree、Annoy。通过超平面将空间反复切分。
2. 基于量化的方法（Quantization-based）：如 PQ、IVF。将高维空间离散化为聚类点，降低数据维度和计算复杂度。
3. 基于图的方法（Graph-based）：以 HNSW 为代表。通过在向量点之间构建空间邻近图进行路径寻优。

2. 深入理解 HNSW 的前身：NSW 算法

要理解 HNSW，必须先了解 NSW（Navigable Small World，可导航小世界图） 算法。

NSW 的本质是一个小世界网络（Small World Network）。在建图过程中，节点随机插入，并与最近的若干节点连接。NSW 的特点是：

• 图中既有连接邻近节点的短边（Short-range edges），负责局部微调；
• 也有跨越空间的长边（Long-range edges），负责实现快速的“跳转”。

在检索时，算法从一个入口节点开始，计算其邻居与目标向量的距离，并贪婪地向距离最近的邻居移动（类似于山脚下爬山），直到所有邻居都比当前节点离目标更远时停止。

然而，NSW 在大规模数据集下面临着**局部极小值（Local Minima）**陷阱，且在初期由于缺乏全局视角导致收敛速度变慢。

3. HNSW 的魔法：多层图结构

HNSW（发表于 2018 年的 IEEE 论文 Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs）通过引入**跳转表（Skip-list）**的思想，将单层图 NSW 演进为了多层图结构。

3.1 结构设计

• 多层金字塔：最顶层（Layer $L$）节点最稀疏，边最长；越往下层节点越密集，最底层（Layer 0）包含数据集中所有的向量点。
• 贪婪路由：
  1. 检索从顶层唯一的入口点开始。
  2. 在当前层进行贪婪搜索，找到该层的局部最近邻。
  3. 将该局部最近邻作为下一层的入口点，降层继续搜索。
  4. 重复此过程，直到降到 Layer 0，并在 Layer 0 中探索更多步数以确保召回率。

Layer 2 (Top)     [●] -----------------------------> [●]
                   |                                  |
Layer 1            [●] ---------> [●] --------------> [●] ----> [●]
                   |               |                  |          |
Layer 0 (Bottom)   [●] -> [●] -> [●] -> [●] -> [●] -> [●] -> [●] -> [●]

3.2 为什么 HNSW 检索速度极快？

在顶层，长边帮助算法快速跨越空间，迅速逼近目标向量的大致区域，这避免了低效的盲目搜索。随着层级降低，图的分辨率增加，算法在极小的范围内进行微调，最终精确定位。

在时间复杂度上，HNSW 将检索复杂度降低到了 $O(\log N)$，这使其成为了大模型检索（RAG）时代最具普适性的高性能底座。