加速合并 HNSW 图表

从向量搜索到强大的 REST API，Elasticsearch 为开发人员提供了最全面的搜索工具包。探索 GitHub 上的示例笔记本，尝试新事物。您也可以立即开始免费试用或在本地运行 Elasticsearch。

过去，我们讨论过搜索多个HNSW 图表所面临的一些挑战，以及我们是如何缓解这些挑战的。当时，我们提到了我们计划进行的一些进一步改进。这篇文章就是这项工作的结晶。

你可能会问，为什么要使用多图表呢？这是 Lucene 架构选择的副作用：不可变的段。与大多数建筑选择一样，有利也有弊。例如，我们最近对无服务器 Elasticsearch 进行了 GA。在这种情况下，我们从不可变分段中获得了非常显著的优势，包括高效的索引复制以及将索引和查询计算解耦并独立自动扩展的能力。对于矢量量化，分段合并让我们有机会更新参数，使其适应数据特征。按照这种思路，我们认为有机会测量数据特征和重新审视索引选择还有其他好处。

在这篇文章中，我们将讨论我们为大幅降低构建多个 HNSW 图形的开销，尤其是降低合并图形的成本所做的工作。

背景

为了保持可管理的分段数量，Lucene 会定期检查是否应该合并分段。这相当于检查当前分段数是否超过目标分段数，目标分段数由基本分段大小和合并策略决定。如果超过该计数，Lucene 会合并片段组，同时违反约束条件。这一过程在其他地方有详细描述。

Lucene 选择合并大小相似的数据段，因为这样可以实现写入放大的对数增长。就向量索引而言，写入放大是指向量插入图形的次数。Lucene 会尝试以大约 10 个为一组合并数据段。因此，向量插入图的次数大约为1+\frac{9}{10} \log_ {10}\left (\frac{n}{n_0} \right ) 次，其中$n$是索引向量数，n $_0$是预期的基本段向量数。由于写入量呈对数增长，即使是庞大的指数，写入放大率也只有个位数。不过，合并图形所花费的总时间与写入放大率成线性比例。

在合并 HNSW 图形时，我们已经进行了小幅优化：保留最大分段的图形，并将其他分段的向量插入其中。这就是上述 9/10 因素的原因。下面，我们将展示如何通过使用我们正在合并的所有图表中的信息来大幅提高性能。

HNSW 图表合并

此前，我们保留了最大的图形，并从其他图形中插入矢量，但忽略了包含这些矢量的图形。我们在下文中利用的关键见解是，我们丢弃的每个 HNSW 图形都包含了有关其所含向量的重要邻近性信息。我们希望利用这些信息来加快插入至少部分载体的速度。

我们重点讨论将较小的图$G_s=(V_s,E_s)$插入较大的图$G$ _l=(V _l, E _l)的问题，因为这是一个原子操作，我们可以用它来构建任何合并策略。

策略是找到$J\subset V_s$的一个顶点子集，将其插入大图中。然后，我们利用这些顶点在小图中的连通性，加速插入剩余的顶点$V_s \setminus J$。在下文中，我们用$N_s(u)$和$N_l(u)$分别表示小图和大图中顶点$u$的邻居。具体流程如下

MERGE-HNSW

Inputs $G_s$ and $G_l$

1$\;\;$Find $J\subset V_s$ to insert into $G_l$ using COMPUTE-JOIN-SET
2$\;\;$Insert each vertex $u\in J$ into $G_l$
3$\;\;$for $u\in V_s \setminus J$ do
4$\;\;\;\;J_u\leftarrow J\cap N_s(u)$
5$\;\;\;\;E_u\leftarrow \cup_{v\in J_u} N_l(u)$
6$\;\;\;\;W\leftarrow\,$FAST-SEARCH-LAYER$(J_u, E_u)$
7$\;\;\;\;neighbors \leftarrow\,$SELECT-NEIGHBORS-HEURISTIC$(u, W)$
8$\;\;\;\;J\leftarrow J \cup \{u\}$

我们使用下面讨论的程序来计算集合$J$（第 1 行）。然后，我们使用标准的 HNSW 插入程序将$J$中的每个顶点插入大图中（第 2 行）。对于我们尚未插入的每个顶点，我们都要找到已插入的邻接顶点及其在大图中的邻接顶点（第 4 行和第 5 行）。我们使用FAST-SEARCH-LAYER 程序（第 6 行）作为种子程序，从 HNSW论文（第 7 行）中找到SELECT-NEIGHBORS-HEURISTIC 的候选者。实际上，我们在INSERT 方法（论文中的算法 1）中替换了SEARCH-LAYER 来查找候选集，其他方面没有变化。最后，我们将刚刚插入的顶点添加到$J 中$（第 8 行）。

很明显，要做到这一点，$V_s \setminus J$中的每个顶点都必须在$J 中$至少有一个邻居。事实上，我们要求对于$V_s \setminus J$中的每个顶点，|J\cap$N_s(u) |\geq k_u$for some$k_u<$ M，即最大层连接性。我们观察到，在真实的 HNSW 图中，顶点度的分布相当广泛。下图显示了 Lucene HNSW 图表底层顶点度的典型累积密度函数。

我们探讨了$k_u$的固定值以及使其成为顶点度函数的方法。第二种选择会带来更快的速度，而对图形质量的影响却很小，因此采用了以下方案

请注意，根据定义，|N_s$(u)$| 等于小图中顶点$u$的度数。下限为 2 意味着我们将插入每个度数小于 2 的顶点。

一个简单的计数论证表明，如果我们仔细选择$J$ ，我们只需要在$G_l$ 中直接插入大约$\frac{1}{5} |V_s|。$具体来说，如果我们将一条图边的一个末端顶点恰好插入到$J 中$，我们就会给这条图边着色。那么我们知道，对于$V_s 中的每个顶点来说，要想在 J$ 中 至少有 $k_u$ 个 邻居，我们至少需要给$\sum_{u\in V_s\setminus J} k_u$ 条边着色。此外，我们预计

这里，${E}$_U（left[N_s(U)|\right]）是小图中的平均顶点度。对于$J 中的$每个顶点u\我们最多为 |N_s$(u)|$条边着色。因此，我们期望着色的边的总数最多为 |J|\$, \mathbb{E}$_U\left[|N_s(U)|\right].我们希望通过仔细选择$J$，使着色的边数接近这一数字，因此，为了覆盖所有顶点，$|$J| 需要满足以下条件

这意味着|J|=\frac{1}{4} (|V_s|-|J|)=\frac{4}{5} \frac {1}{4}|V_s|=\frac{1}{5} |V_s|。

如果SEARCH-LAYER 的运行时间占主导地位，这表明我们可以将合并时间最多提高$5 倍$。考虑到写入放大率的对数增长，这意味着即使对于非常大的索引，我们的构建时间通常也只比构建一个图形多一倍。

这种策略的风险在于会破坏图形质量。我们最初尝试使用无操作程序FAST-SEARCH-LAYER 。我们发现这降低了图表质量，以至于影响了作为延迟函数的召回率，尤其是在合并到单个片段时。然后，我们通过对图形的有限搜索，探索了各种替代方案。最终，最有效的选择是最简单的。使用SEARCH-LAYER ，但ef_construction 要低。通过这种参数设置，我们能够获得质量极佳的图形，同时还能将合并时间平均缩短 30% 多一点。

计算连接集

寻找一个好的连接集可以表述为一个 HNSW 图覆盖问题。贪婪启发式是一种简单有效的近似最优图覆盖的启发式。我们采用的方法是按增益递减的顺序逐个选取顶点添加到$J 中$。增益定义如下

这里，$c(v)$表示向量$v$在$J$中的邻域数，$1\{\cdot\}$是指示函数。增益包括我们添加到$J 中$的顶点计数的变化，即 \max$(k_v-c(v),0)$，因为我们添加了一个覆盖范围较小的顶点，从而更接近我们的目标。下图展示了中心橙色顶点的增益计算。

我们为每个顶点$v$ 维护以下状态

1. 是否陈旧、
2. 其增益$Gain(v)、$
3. $J$中相邻顶点的计数，用$c(v)$ 表示、
4. 范围为 [0,1] 的随机数，用于打破平局。

计算连接集的伪代码如下。

COMPUTE-JOIN-SET

Inputs $G_s$

1$\;\;C\leftarrow\emptyset$
2$\;\;Gain_{exit}\leftarrow 0$
3$\;\;$for $u\in G_s$ do
4$\;\;\;\;C\leftarrow C \cup \{(\text{false}, k_u+deg(u), 0, \text{rand in }[0,1])\}$
5$\;\;\;\;Gain_{exit}\leftarrow Gain_{exit}+k_u$
6$\;\;Gain_{tot}\leftarrow 0$
7$\;\;$while $Gain_{tot}<Gain_{exit}$ do
8$\;\;\;\;v^*\leftarrow\,$ maximum gain vertex in $C$
9$\;\;\;\;$Remove the state for $v^*$ from $C$
10$\;\;\;$if $v^*$ is not stale then
11$\;\;\;\;\;J\leftarrow J\cup\{v^*\}$
12$\;\;\;\;\;Gain_{tot}\leftarrow Gain_{tot}+Gain(v^*)$
13$\;\;\;\;\;$for $u \in N_s(v^*)$ do
14$\;\;\;\;\;\;\;$mark $u$ as stale if $c(v^*)<k_{v^*}$
15$\;\;\;\;\;\;\;$mark neighbors of $u$ stale if $c(u)=k_u-1$
16$\;\;\;\;\;\;\;c(u)\leftarrow c(u)+1$
17$\;\;\;$else
18$\;\;\;\;\;Gain(v^*)\leftarrow \max(k_v-c(v^*),0)+\sum_{u\in N_s(v^*)\setminus J} 1\left\{c(u)<k_u\right\}$
19$\;\;\;\;\;$if $Gain(v^*)>0$ then
20$\;\;\;\;\;\;\;C\leftarrow C \cup \{(\text{false},Gain(v^*),c(v^*),\text{copy rand})\}$
21$\;\;$return $J$

我们首先在第 1-5 行中初始化状态。

在主循环的每次迭代中，我们首先提取最大增益顶点（第 8 行），然后随机打破平局。在进行任何更改之前，我们需要检查顶点的增益是否过时。特别是，每次我们将一个顶点添加到$J 中时$，都会影响其他顶点的增益：

1. 由于它的所有邻居在$J$中都多了一个邻居，因此它们的收益会发生变化（第 14 行）
2. 如果它的任何一个邻居现在被完全覆盖，其所有邻居的收益都会发生变化（第 14-16 行）

我们以一种懒散的方式重新计算增益，因此只有当我们想要将某个顶点插入$J 时$，才会重新计算该顶点的增益（第 18-20 行）。由于增益只会减少，我们永远不会错过应该插入的顶点。

请注意，我们只需跟踪我们添加到$J 中$的顶点的总增益，就能确定何时退出。此外，当Gain_{tot}< Gain_ {exit} 时，至少有一个顶点的增益不为零，因此我们总能取得进展。

实施结果

我们在四个数据集上进行了实验，这四个数据集涵盖了我们支持的三种距离度量（欧氏、余弦和内积）：

1. quora-E5-small：522931 个文档，384 个维度，使用余弦相似性、
2. cohere-wikipedia-v2：1M 文档，768 维度，使用余弦相似性、
3. gist：100 万个文档、960 个维度并使用欧氏距离，以及
4. cohere-wikipedia-v3：100 万文档，1024 维度，使用最大内积。

对于每个数据集，我们都会评估两种量化水平：

1. int8 - 每个维度使用一个 1 字节的整数，而
2. BBQ - 每个维度使用一个比特。

最后，在每个实验中，我们在两个检索深度对搜索质量进行了评估，并在建立索引后和强制合并为单一片段后对搜索质量进行了检查。

总之，我们在索引和合并方面实现了持续的大幅提速，同时保持了图的质量，因此在所有情况下都能保持搜索性能。

实验 1：int8 量化

从基线到候选方案（建议的修改）的平均提速为

索引时间加速：1.$28$ 次

强制合并加速：1.$72$ 次

运行时间细分如下

为完整起见，确切时间为

下面我们展示了候选方案（虚线）与基线在两种检索深度下的召回率与延迟对比图：多段索引的召回率@10 和召回率@100（我们的默认合并策略在索引所有矢量后的最终结果），以及强制合并为单段后的召回率与延迟对比图。曲线越高、越靠左越好，这意味着在较低的延迟条件下有更高的记忆率。

正如您所看到的，对于 Cohere v3 数据集来说，候选者的多分段指数更好，而对于所有其他数据集来说，候选者的多分段指数稍差，但几乎不相上下。合并为单一网段后，所有情况下的召回曲线几乎相同。

实验 2：烧烤量化

从基准线到候选方案的平均加速度为

索引时间加速：1.$33$ 次

强制合并加速：1.$34$ 次

运行时间细分如下

为完整起见，确切时间为

对于多分段索引，候选者在几乎所有数据集上都更胜一筹，但 cohere v2 除外，基线略胜一筹。就单段指数而言，所有情况下的召回曲线几乎相同。

结论

本博客中讨论的算法将在即将发布的 Lucene 10.2 以及基于该算法的 Elasticsearch 版本中提供。用户将能利用这些新版本中改进的合并性能和缩短的索引构建时间。这一变更是我们为使 Lucene 和 Elasticsearch 在矢量和混合搜索方面快速高效而不断努力的一部分。