作者：来自 ElasticSimon Cooper

学习如何使用 HNSW 图的 M 和 ef_construction 参数来提升搜索性能。

刚接触 Elasticsearch？加入我们的 Elasticsearch 入门网络研讨会。你也可以立即开始免费的云试用，或者在你的机器上尝试 Elastic。

---

分层可导航小世界（Hierarchical Navigable Small World – NNSW）向量搜索的原理首次在 Elasticsearch 8.0 中引入。但图是如何最初创建的？图的构建对搜索质量有什么影响？这些参数实际上是做什么的？

搜索图

首先，简单回顾一下 HNSW 图是如何工作的。HNSW 图是一种分层的数据结构，遵循以下规则：

• 所有向量都出现在最底层（第 0 tgcode层）；每个向量在该层由一个图节点表示。

• 向上层移动时，一个向量出现在每一层的概率按对数递减，因此每一层的向量数都会比下层少。

• 每个出现在某一层的向量在该层都有一个节点。相同向量的所有节点都与该向量关联。

• 如果一个向量出现在某一层，它也会出现在所有更低层，直到第 0 层。

• 每一层的每个节点都有指向该层某些其他节点的引用，通常是最接近的节点（由向量相似度决定，见下文）。

• 引用是单向的，所以如果节点 A 引用节点 B，节点 B 不一定引用节点 A。

• 每个 Lucene 索引段都有自己独立的 HNSW 图，只包含该段中的向量。多个段会被独立搜索。

HNSW 图不受向量维度数量的影响，因为它基于两个向量的相似度工作。这通常是余弦或点积（见此处示例），具体取决于索引的配置方式。相似度比较两个 n 维向量并生成一个单一的数值，表示这些向量的接近程度。用于构建 HNSW 图的是这些相似度数值，而不是向量本身。

跨 HNSW 图的搜索，为了找到与查询向量最近的 k 个向量，按以下阶段进行：

• 搜索从入口点节点开始。所有搜索使用相同的节点作为入口点，它是在构建过程中最先被添加到图最顶层的向量。

• 遍历顶层的节点，从入口点节点开始，找到该层中最接近查询向量的向量。

• 一旦找到最近的向量，就将其作为起点，在下一层继续搜索更接近的向量。

• 这一过程重复，直到在最底层找到入口点节点，该层包含所有向量。

• 在最底层中搜索该入口点的邻居，递归遍历从一个节点到另一个节点的邻居链接，直到找到最近的 k 个向量。

一切顺理成章。但图最初是如何构建的？层数是由什么决定的？为什么召回率不是完美的？

图构建

图的召回性能完全取决于它是如何构建的。图的构建由两个参数控制：

• M：某一层中一个向量节点最多能与多少个邻居建立连接（Lucene，以及 Elasticsearch，默认值为 16）

• ef_construction，也称为 beamWidth：在构建过程中添加新向量时，用于在该层寻找邻居的 kNN 搜索参数 k（Lucene 默认值为 100）

这些参数对图的构建影响很大。向图中添加一个新向量的步骤如下：

1. 确定向量会被添加到的层数。这是基于 M 值的随机结果。向量总会出现在第 0 层（底层）；出现在更高层的概率随着层数增加而按对数递减，并与 M 成比例。对于默认值 16，图通常会有 3–5 层。重要的是，这与图的现有结构无关 —— 某个向量最终存在的最高层是完全随机的。

2. 如果这是图中的第一个节点，或者是新顶层的第一个节点，它会被设置为该图的入口点（无论它在向量空间的实际位置如何）。

3. 对于向量所在的每一层，执行一次 HNSW 搜索，以在该层找到与新向量最近的节tgcode点。每层使用的 k 值就是 ef_construction 参数。

4. 在每一层，与最近的节点建立最多 M 个连接（如果在第 0 层，则为 M2）。同时建立反向连接，即现有节点到新节点的连接。两个方向都要考虑多样性（见下文）。

5. 由于每一层的向量数量比下层少，但最大连接数相同，因此高层的向量比低层的向量有更长距离的连接，有助于在搜索开始时从初始入口点快速跨越向量空间。有关如何加快 HNSW 在 kNN 搜索中的速度的更多信息，可参见此处示例。

多样性

关键问题是 —— 你将新节点连接到哪些节点？简单地说，你可能会选择 M 个最近的节点。但如果同一层中有几个向量彼此靠得很近，这可能会导致问题。这些向量可能形成一个团，几乎没有与其他节点的连接。一旦图遍历进入该团，可能很难出来，从而导致结果不理想。

为了解决这个问题，创建算法只会将新连接添加到那些比新节点的其他邻居节点更接近新节点的节点。例如：

节点 N 正在被添加到图中。新连接将从 N 到 A 和 B 建立，因为它们是最近的节点，但不会连接到 C，因为 C 离 B 比离 N 更近。然后，还会建立从 N 的新连接邻居回到 N 的入向连接（incoming connections）。这些连接同样考虑多样性，相对于现有节点，如果该节点的连接数达到上限，会移除现有连接以维持多样性。这确保了节点tgcode与多样化的其他节点相连，最大化它们从图中其他位置的可达性，并最小化完全连接团的形成。

但这也有缺点 —— 因为每个节点不一定直接连接到周围的所有节点，搜索该节点的链接邻居可能不会返回完整结果。这是近似 kNN 搜索可能遗漏某些节点（而在穷尽搜索中会返回）的原因之一，因此相比穷尽搜索，搜索召回率会降低（见示例）。

图参数

总结一下，用于构建 HNSW 图的两个参数是 M（节点的最大连接数）和 ef_construction（添加新向量时搜索邻居的节点数）。

• 增大 M 通过增加链接邻居数量和层数提高搜索精度，但会增加图的磁盘和内存使用、插入延迟以及搜索延迟。

• 增大 ef_construction 会对每个新向量进行更全面的邻居搜索，但会增加插入延迟。

HNSW 图常见问题解答：

以下是理解 M 和 ef_construction 图构建参数的关键点：

问题	答案
什么是 HNSW 图？	HNSW（分层可导航小世界）图是一种用于近似最近邻（ANN）搜索的分层数据结构。所有向量都存储在底层，而上层包含更少的向量作为捷径，使基于向量相似度的遍历更快。
HNSW 图如何工作？	HNSW 图通过自顶向下遍历各层来定位最近邻。搜索从最高层的入口点开始，找到最近的向量，并将其作为下一层的入口点。重复此过程直到到达底层，然后递归搜索识别 k 个最近邻。
为什么 HNSW 图重要？	HNSW 图重要因为它们实现了快速且可扩展的近似最近邻搜索。分层结构允许高效探索向量空间，在保持高召回率的同时减少搜索时间。
HNSW 图如何构建？	HNSW 图由两个参数构建：M（每个节点的最大连接数）和 ef_construction（邻居搜索宽度）。新向量的最高层随机选择，然后在每层找到其最近邻，并建立相应连接。
HNSW 图中的“多样性”是什么？	HNSW 中的多样性意味着算法通过连接到不同节点来避免形成团。新连接只会建立到比已有邻居更接近新向量的节点，这提高了可达性并防止孤立簇的形成。

原文：https://www.elastic.co/search-labs/blog/hnsw-graph