作者：来自 Elastic Tommaso Teofili
介绍Elasticsearch中 HNSW 的一种新的自适应提前终止策略。
从向量搜索到强大的REST API，Elasticsearch为开发者提供了最全面的搜索工具包。在Elasticsearch Labs仓库中，探索我们的示例笔记本，尝试一些新东西。你也可以开始免费试用，或者今天就在本地运行Elasticsearch。
弹性搜索使用层级可导航小世界（HNSW）算法在邻近图上进行向量搜索。HNSW已知能在k个最近邻（KNN）结果的质量与相关成本之间做出良好的权衡。
在HNSW中，搜索通过迭代扩展图中的候选节点进行，保持迄今为止发现的有界最近邻集合。每个扩展都有其成本（向量运算、随机寻盘等），随着搜索的推进，这些成本的边际收益通常会减少。
优化HNSW图遍历的一种方法是，当找到新真邻居的边际概率不增加时停止搜索。因此，在 Elasticsearch 9.2 中，我们引入了新的早期终止机制。当访问图节点连续次数不足够多地提供足够新的最近邻时，这会停止搜索过程。
本文将引导您了解我们如何改进HNSW早期终止机制，使其更适合不同的数据集和数据分布。
HNSW 中的提前终止
在 HNSW 中，搜索通过在邻近图中迭代扩展候选节点进行，同时维护一个当前已发现的最近邻的有界集合，直到访问完整个图或满足某些提前停止条件。
因此，提前终止并不一定只是优化手段，它本身就是搜索算法的一部分。我们决定何时停止，将决定效率与召回率之间的平衡。在 Elasticsearch 中，针对 HNSW 的查询已经有多种提前终止方式：
这些规则虽然简单且可预测，但基本上与实际搜索过程无关。此外，它们主要用于确保查询能在合理时间内为终端用户完成。
在之前的一篇博客文章中，我们介绍了 HNSW 中冗余的概念。简而言之，当 HNSW 持续评估新的候选节点却未能找到更多最近邻时，就会发生冗余计算。
耐心：衡量进展而不是付出
“耐心” 这一概念将提前终止从关注付出转变为关注进展。
与其问：
“我们已经走了多少步？”
新的问题变成：
“在失去希望之前，我们愿意接受多少计算被浪费？”
在 HNSW 搜索过程中，早期探索通常会为 top-k 候选集合带来最显著的改进。在 HNSW 图探索的最初阶段，随着算法不断发现更接近查询向量的邻居，邻居集合会持续更新。随着时间推移，当搜索逐渐收敛，这些改进会变得越来越少。基于耐心的终止机制会监控这一模式，一旦在持续一段时间内不再出现改进，就会终止搜索。
在实践中，当我们遍历 HNSW 图时，还会在跳转候选节点的过程中计算队列饱和率。该指标衡量在访问最近一个图节点时，有多少比例的最近邻保持不变（或者说，是最近一次迭代引入的新邻居数量的反比）。当这一比例在连续多次迭代中变得过高时，我们就会停止遍历图。
从概念上讲，耐心将 HNSW 搜索视为一个边际收益递减的过程。当收益趋于平缓时，继续探索图带来的收益就很小。
这种框架之所以强大，是因为它将终止条件直接与可观察的结果相关联，而不是依赖任意的固定限制。
使用这种智能提前终止技术的好处在于，HNSW 图遍历通常会访问更少的图节点，同时仍然保持几乎完美的相对召回率。
为了进行可视化，我们可以绘制基于耐心的提前终止（标记为 et=static）与默认 HNSW 行为（标记为 et=no）在多个数据集（FinancialQA 和 Quora）以及模型（JinaV3 和 E5 -small）上的每访问节点召回率对比。
![]()
![]()
静态阈值与 HNSW 动态特性
在实践中，在 Elasticsearch 中这是通过静态阈值实现的。一个阈值是饱和阈值：即我们认为不理想的饱和比例。另一个阈值是耐心阈值：即在队列饱和度仍然不理想的情况下，我们允许连续访问的图节点数量。
当我们在 Elasticsearch 9.2 中引入这种提前终止策略时，我们选择了较为保守的默认值，以尽可能保持召回率，同时在延迟和内存消耗方面获得收益。因此，我们将饱和阈值设置为 100%，并将耐心阈值设置为 KNN 查询中num_candidates的（有界）30%。
在许多场景下，这些设置运行良好；然而，两个请求相同邻居数量的查询可能具有截然不同的收敛行为。有些查询会遇到密集的局部邻域并迅速饱和；而另一些则必须遍历较长且稀疏的路径，才能找到有竞争力的候选节点。后者是最难有效处理的情况。
因此，我们有时会观察到：
因此，我们意识到固定阈值隐含了关于收敛行为的全局假设，而我们可以让 HNSW 更好地适应不同的动态特性。
让 HNSW 的提前终止自适应化
自适应提前终止从不同的角度解决这一问题。与其强制执行预定义的停止阈值，算法会从搜索动态本身推断何时停止。
因此，我们不再仅仅比较两个连续候选节点之间的队列饱和率，而是引入了瞬时平滑发现率 d_q,i（表示在第 i 次访问时，查询 q 引入了多少新的邻居），以及在图遍历过程中该发现率的滚动均值 μ_q,i 和标准差 σ_q,i（使用Welford 算法计算）。这些关于发现率的统计数据是按查询单独计算的，因此可以利用这些信息为每个查询决定不同程度的 “耐心”。
![]()
先前的静态阈值现在根据发现率统计数据进行自适应调整：饱和阈值变为滚动均值加上标准差；而耐心阈值则进行自适应调整，并与标准差成反比缩放。
![]()
提前退出规则保持不变；当瞬时发现率低于自适应饱和阈值时，就认为发生了饱和。如果这种饱和在连续访问的候选节点次数超过自适应耐心阈值时仍然持续，图遍历就会停止。
通过这种方式，我们获得了一种不依赖于 KNN 查询中 num_candidates 参数的行为（该参数可能始终被设置或保持默认，而与提前退出无关），并且能够根据每个查询和向量分布动态地更好适应。
在 FinancialQA 和 Quora 数据集上，采用自适应策略（标记为 et=adaptive）的每访问节点召回率，相较于静态策略（et=static）和默认 HNSW 行为（et=no）更高。
![]()
![]()
在 Elasticsearch 9.3 中，自适应提前终止默认在 HNSW 密集向量字段上启用（并且也可以通过相同的索引级设置将其关闭）。
原文：Elasticsearch HNSW: Adaptive early termination for vector search - Elasticsearch Labs
