分层可导航小世界 (HNSW) 内部机制

在数百万乃至数十亿高维向量 (vector)中执行精确最近邻搜索，对于实时语义搜索或检索增强生成 (RAG) 等实际用途而言，通常速度过慢。分层可导航小世界 (HNSW) 作为一种高效且普遍采用的近似最近邻 (ANN) 算法，在搜索速度、召回率（准确性）和内存使用之间取得了很好的平衡。它是一种图算法，其灵感源自可导航小世界 (NSW) 的原理，但加入了一项显著提升：分层结构。

多层架构

设想一下，在一个大国家里寻找一个具体地址。你不会去每一条本地街道都开一遍。相反，你很可能会先使用高速公路快速接近目的地，然后是区域道路，最后是本地街道来完成旅程的最后一部分。HNSW 采用一种类似的方法，使用多层图。

1. 分层结构： HNSW 构建多个图层。最底层（层 0）包含所有数据点（向量 (vector)）加入到索引中。其上每个后续层都包含其下方层中一部分点。最顶层通常只有少数几个点，作为图的主要进入点。
2. 快速通道和本地道路： 较高层作用如同“高速公路”，允许在搜索时在向量空间中进行远距离跳转。较低层代表“本地道路”，实现更细致的查找，以接近目标查询。
3. 层间连接： 每个点都存在于其被分配到的层以及其下方所有层。连接不仅存在于同一层内的点之间，也隐式连接各层，因为搜索会向下逐层转移。

带有三层的 HNSW 图结构简化示意图。连接存在于层内（实线），点也存在于下层（虚线表示存在，而非直接的层间边）。搜索通常从顶层进入点 (E) 开始并向下导航。

图构建算法

构建 HNSW 图是一个增量过程，点是逐个插入的。当添加一个新向量 (vector) $p$ 时：

1. 选择最大层 ($L_{max}$)： 新点 $p$ 的最大层 $L_{max}$ 是使用指数衰减概率分布随机选择的。这意味着大多数点只会存在于较低层，而少数点会到达较高的“快速通道”层。该概率由归一化 (normalization)因子 mL 控制。较高的 mL 会导致上层更稀疏。 $P(\text{层}) \propto e^{-\text{layer} / \text{mL}}$
2. 找到进入点： 插入过程从现有图的最高层开始。该层的指定进入点被用作起始点。
3. 搜索最近邻（自上而下）： 从新点 $p$ 将被插入的最高层（即层 $L_{max}$）开始，算法在每层向下直到层 0 执行贪婪搜索。
   • 层内操作： 从在上一层找到的进入点（或顶层的全局进入点）开始，它贪婪地在图中导航，总是移向更接近新点 $p$ 的邻居。
   • 候选列表 (efConstruction)： 在构建时的这个搜索邻居阶段，会维护一个到目前为止找到的最接近候选点的动态列表（优先级队列）。该列表的大小由参数 (parameter) efConstruction 控制。更大的 efConstruction 意味着在每一步查找更多可能的邻居，可能带来更高质量的图结构（后续有更好的召回率），但会增加索引构建时间。
4. 建立连接 ($M$)： 一旦层内搜索识别出 $p$ 的最近邻（根据 efConstruction），就会在 $p$ 和这些邻居中的一部分之间建立连接。
   • 最大连接数 ($M$)： 参数 $M$ 定义了一个节点在单层内可以拥有的最大出站连接数。
   • 启发式方法： 连接通常基于接近度选择。有时会使用启发式方法以确保良好的空间覆盖，并避免仅连接到紧密聚集的邻居。如果向 $p$ 添加连接会使某个邻居超出 $M$ 的限制，该邻居可能会放弃其最远的连接以容纳新的、更近的连接。层 0 可能会使用一个单独的参数 Mmax0，通常设置得更高（例如 $2M$），以改进基层连接性。
5. 对下层重复此过程： 算法使用在层 $l$ 中找到的最接近邻居作为在层 $l-1$ 中搜索的进入点。这个过程重复进行，在从 $L_{max}$ 到层 0 的每一层执行贪婪搜索和连接步骤。

这种分层构建方式，辅以受控连接性 ($M$) 和引导式搜索 (efConstruction)，旨在构建一个能实现从粗粒度到细粒度有效导航的图。

搜索算法

搜索查询向量 (vector) $q$ 的 $k$ 个最近邻与插入过程类似，但仅关注寻找最接近的点，而不修改图：

1. 找到进入点： 从图的最顶层的进入点开始搜索。
2. 贪婪搜索（自上而下）： 从顶层的进入点开始，贪婪地向更接近查询向量 $q$ 的节点导航。记录在该层中找到的最接近的节点。
3. 逐层迭代细化： 使用在层 $l$ 中找到的最接近节点作为在层 $l-1$ 中开始贪婪搜索的进入点（或其中一个进入点）。
4. 候选列表 (efSearch)： 与构建过程类似，在跨层搜索期间，会维护一个到目前为止找到的候选最近邻的动态优先级队列。搜索期间此候选列表的大小由参数 (parameter) efSearch 控制。这是调整搜索速度和召回率（准确性）之间权衡的一个重要参数。
   • efSearch 必须至少为 $k$（请求的邻居数量）。
   • 更大的 efSearch 会查看图中更多路径，增加了找到真实最近邻的概率（召回率更高），但耗时更长（延迟更高）。
   • 更小的 efSearch 会导致搜索更快，但可能遗漏一些真实邻居（召回率更低），从而满足于“足够好”的近似邻居。
5. 终止： 搜索逐层向下进行。这个过程通常涉及主要在层 0 中查找邻居，由从上层找到的进入点引导。一旦根据 efSearch 标准的搜索完成（例如，优先级队列无法再优化），算法将从最终候选列表中返回找到的 $k$ 个最接近的向量。

核心参数 (parameter)及调整事项

有效使用 HNSW 通常需要调整几个重要参数：

• M (每层最大连接数)： 控制每层内图的密度（层 0 可能除外）。
  • 影响： 较高的 M 增加图连接性，可能改善召回率和鲁棒性。但它也会显著增加索引的内存占用和图的构建时间。
  • 典型值： 5 - 48。
• efConstruction (构建候选列表大小)： 控制索引构建期间为新点查找邻居时执行的搜索深度。
  • 影响： 较高的 efConstruction 带来更高质量的图结构（实际搜索期间召回率更好），但会显著增加索引构建时间。与 M 相比，它对索引大小的影响较小。
  • 典型值： 64 - 512（甚至更高，取决于期望的质量与构建时间）。
• efSearch (搜索候选列表大小)： 控制查询时执行的搜索深度。
  • 影响： 直接影响搜索速度（延迟）和召回率之间的权衡。较高的 efSearch 会提高召回率但会减慢查询速度。必须 $\ge k$。
  • 典型值： $k$ 到 512（或更高，取决于所需的召回率/延迟）。通常根据应用需求通过离线评估或 A/B 测试进行调整。
• mL (层归一化 (normalization)因子)： 影响构建期间层分配的概率分布。
  • 影响： 影响节点在各层中的分布。值越小，上层越密集。通常保留默认值（例如 $1 / \ln(M)$）。

调整这些参数对于根据特定数据集特点和应用需求（例如，优先考虑低延迟而非最大化召回率）优化 HNSW 十分重要。

HNSW 的优缺点

优点：

• 先进性能： 与其他许多 ANN 方法相比，通常在非常高的查询速度下实现了高召回率。
• 内存效率： 尽管基于图，但其内存使用通常比暴力搜索或某些其他复杂结构更易于管理，尤其是在与量化 (quantization)（后续会讨论）结合时。
• 支持更新： 增量构建过程使得向现有索引添加新点相对简单，无需完全重建（尽管删除可能更复杂）。
• 良好的通用性： 在各种数据分布和维度下表现良好。

缺点：

• 构建时间： 构建 HNSW 图，特别是当 efConstruction 较高时，对于非常大的数据集而言可能很耗时。
• 参数 (parameter)调整： 找到 M、efConstruction 和 efSearch 的最佳组合可能需要细致的实验和评估。
• 复杂性： 底层算法比 IVF 等更简单的方法更为复杂，可能使实现或修改更具挑战性。

HNSW 因其卓越的性能特点而成为现代向量 (vector)搜索的一种重要算法。理解其分层结构、构建过程和搜索机制，对于构建高效且有效的语义搜索和 RAG 系统非常重要。在后续章节中，我们将讨论 IVF 和 PQ 等其他重要的 ANN 技术，并随后讨论它们有时如何与 HNSW 结合以实现进一步优化。