Elasticsearch：在 HNSW 中提前终止以实现更快的近似 KNN 搜索

作者：来自 Elastic Tommaso Teofili

了解如何使用智能提前终止策略让 HNSW 加快 KNN 搜索速度。

在高维空间中高效地找到最近邻的挑战是向量搜索中最重要的挑战之一，特别是当数据集规模增长时。正如我们之前的博客文章中所讨论的，当数据集规模有限时，强力（brute force）最近邻搜索可能是最佳选择。另一方面，随着向量数据集规模的增加，切换到近似最近邻搜索有助于在不牺牲准确性的情况下保持查询速度。

Elasticsearch 通过分层可导航小世界算法（Hierarchical Navigable Small World algorithm）实现近似最近邻搜索。HNSW 提供了一种有效的向量空间导航方法，降低了计算成本，同时仍保持了较高的搜索准确性。特别是，它的分层结构使得能够访问候选邻居并决定是否将它们包含在最终结果集中，同时减少向量距离计算。

然而，尽管 HNSW 算法有其优势，但它可以进一步优化以适应大规模向量搜索。提高 HNSW 性能的一种有效方法是找到在特定情况下停止访问图的方法，这称为提前终止。这篇博文探讨了 HNSW 的提前终止概念以及它们如何优化查询执行。

HNSW 中的冗余

HNSW 是一种近似最近邻算法，它构建一个分层图，其中节点表示向量，边表示向量空间中向量之间的接近度。每层都包含越来越多的图节点。查询时，搜索会遍历此图，从随机入口点开始，然后通过各层导航到最近的邻居。

搜索过程是迭代的，随着检查更多节点和向量而扩展。速度和准确性之间的平衡是 HNSW 的核心，但它仍然会导致冗余计算，尤其是在涉及大型数据集时。

在 HNSW 中，冗余计算主要发生在算法继续评估新节点或候选节点时，这些节点或候选节点在查找查询的实际邻居方面几乎没有任何改进。发生这种情况的原因是，在标准 HNSW 遍历中，算法逐层进行，探索和扩展候选节点，直到所有可能的路径都用尽。

具体来说，当数据集包含高度相似或重复的向量、具有密集簇内连接的簇或具有很少内在结构的高维空间中的向量时，可能会出现这种冗余。这种冗余会导致访问不必要的边，增加内存使用量，并可能降低搜索性能而不会提高准确性。在相似度得分快速衰减的高维空间中，一些边（edges）通常无法在图中提供有意义的捷径，从而导致导航路径效率低下。

因此，如果在遍历图时可以执行大量不必要的计算，则可以尝试改进 HNSW 算法以缓解此问题。

提前终止 FTW

导航解决方案空间是优化和搜索算法中的一个基本概念，其目标是在一组可能的解决方案中找到最佳解决方案。解决方案空间代表给定问题的所有潜在解决方案，导航它涉及系统地探索这些可能性。这个过程可以可视化为通过一个图移动，其中每个节点代表一个不同的解决方案，目标是确定最符合问题标准的节点。了解如何有效地导航解决方案空间对于解决具有大量解决方案的复杂问题至关重要。提前终止是一种通用的优化策略，可以应用于任何此类算法，以在特定情况下做出何时停止搜索解决方案的明智决定。

如果任何解决方案被认为 “足够好” 以满足期望的标准，则可以停止搜索，并且该解决方案可以被视为良好候选或最佳解决方案。这意味着一些潜在的更好的解决方案可能仍未被探索，因此很难在最终解决方案的效率和质量之间找到完美的折衷方案。

HNSW 中的提前终止

在 HNSW 中，提前终止可用于在完全评估所有潜在候选节点（向量）之前停止搜索过程。评估候选节点意味着计算查询向量与正在处理的图中节点对应的向量之间的实际相似度；因此，在遍历每一层时跳过一堆这样的操作，可以大大降低查询的计算成本。

另一方面，跳过原本会产生真正最近邻居的候选节点肯定会影响搜索结果的质量，可能会遗漏一些接近查询向量的候选向量。

因此，效率收益和准确度损失之间的权衡需要谨慎处理。提前终止在以下情况下很有用：

次线性效率（Sublinear Efficiency）：你希望优化性能以换取略低的召回率。
高吞吐量系统（High-Throughput Systems）：更快的响应时间比最高的准确度更有价值。
资源限制（Resource Constraints）：计算或内存限制使得无法完全遍历 HNSW 图。

在 HNSW 的上下文中，有多种选项可用于实施提前终止策略。

固定候选池大小：最简单的提前终止策略之一是限制候选池的大小（例如，搜索期间评估的节点数）。在 HNSW 中，搜索过程是迭代的，随着搜索的进行，会扩展到更多节点。通过设置考虑的候选数限制，我们可以提前终止搜索并仅根据整个图的子集返回结果。当然，这可以以分层方式实现，也可以考虑整个图中的所有节点。
基于距离阈值的终止：另一种可能有效的提前终止策略是根据查询向量与对应于 HNSW 节点的向量之间的距离计算做出明智的决策。可以根据查询向量与当前最近向量之间的距离设置阈值。如果发现距离低于指定阈值的向量，则可以提前停止搜索，假设进一步探索不太可能产生更好的结果。这与对节点以智能顺序访问的事实的限制相辅相成，以避免遗漏可能相关的邻居。
基于质量估计的动态提前终止：一种更复杂的方法是根据每次搜索查询期间发现的结果的 “质量” 动态调整终止标准。如果搜索过程快速收敛到高质量邻居（例如，距离非常近的邻居），算法可以提前终止，即使没有达到预定义的阈值。

前两种策略属于 “固定配置” 提前终止策略类别，即搜索根据固定约束条件终止，而不考虑特定查询的复杂性。实际上，并非所有查询的难度都是相同的。例如，当向量分布不均衡时，一些查询需要访问更多候选项。一些查询向量可能落入向量空间中的密集区域，因此它们拥有更多的候选最近邻；而另一些查询可能落入“稀疏区域”，这使得找到其真正的最近邻更加困难。

由于这种情况，能够适应向量空间密度（从而适应 HNSW 图的连通性）的提前终止策略似乎更适合实际场景。因此，确定停止搜索每个查询的最佳点更有可能在不影响准确性的情况下大幅减少延迟。这种类型的提前终止策略被称为自适应策略，因为它们会适应每个查询实例来决定何时终止搜索过程。

例如，自适应提前终止策略可以利用机器学习模型来预测给定查询需要多少搜索工作才能达到所需的准确性。这样的模型会根据单个查询的特征和中间搜索结果动态调整要探索的图的范围。

说到中间搜索结果，它们通常是进一步搜索的有力预测因素。如果初始结果已经接近查询，则可能很快就会找到最近的邻居，从而允许提前终止。相反，较差的初始结果表明需要进行更广泛的探索（参见本文）。

Lucene 可以通过 KnnCollector 接口实现 HNSW 的提前终止，该接口公开了 earlyTerminated() 方法，但它还为 HNSW 提供了几个固定配置的提前终止策略：

TimeLimitingKnnCollector 可以在达到特定时间阈值时停止 HNSW 图遍历。
AbstractKnnCollector 是一个基本的 KnnCollector 实现，一旦访问了固定数量的图节点，它就会停止图遍历。

作为另一个示例，为了实现基于距离阈值的终止，我们可以依赖 Lucene 在 HNSW 遍历期间记录的最小竞争相似性（用于确保只探索竞争节点），并在其低于给定阈值时提前退出。

public class MCSEarlyExitCollector implements KnnCollector {

  private final KnnCollector delegate;
  private final double mcsThreshold;

  public MCSEarlyExitCollector(KnnCollector delegate, double mcsThreshold) {
    this.delegate = delegate;
    this.mcsThreshold = mcsThreshold;
  }

  @Override
  public boolean earlyTerminated() {
    return delegate.earlyTerminated() || minCompetitiveSimilarity() < mcsThreshold;
  }

  ...
}