Elasticsearch：过滤 HNSW 搜索，快速模式

作者：来自 Elastic Benjamin Trent

通过我们的 ACORN-1 算法实现，探索我们对 Apache Lucene 中的 HNSW 向量搜索所做的改进。

多年来，Apache Lucene 和 Elasticsearch 一直支持使用 kNN 查询的过滤搜索，允许用户检索符合指定元数据过滤器（metadata filter）的最近邻居。然而，处理半限制性（semi-restrictive）过滤器时性能总会受到影响。在 Apache Lucene 中，我们引入了 ACORN-1 的变体 —— 一种用于过滤 kNN 搜索的新方法，可实现高达 5 倍的速度提升且召回率几乎没有下降的搜索速度。

本博客将讨论过滤 HNSW 搜索所面临的挑战，解释了为什么随着过滤的增加性能会变慢，以及我们如何使用 ACORN-1 算法改进 Apache Lucene 中的 HNSW 向量搜索。

为什么搜索较少的文档实际上速度更慢

与直觉相反，过滤文档（从而减少候选数量）实际上会使 kNN 搜索变得更慢。对于传统的词汇搜索，更少的文档意味着更少的评分操作，意味着更快的搜索。然而，在 HNSW 图中，主要成本是识别 k 个最近邻居所需的向量比较次数。在某些过滤器集大小下，向量比较的次数可能会显著增加，从而降低搜索性能。

这是未过滤图形搜索的一个例子。请注意，有大约 6 个向量运算。

由于 Apache Lucene 中的 HNSW 图在构建时并不了解过滤标准，因此它纯粹基于向量相似性进行构建。当应用过滤器检索 k 个最近邻居时，搜索过程会遍历更多的图。发生这种情况的原因是，局部图邻域内的自然最近邻可能会被过滤掉，从而需要更深入的探索并增加向量比较的次数。

请注意入口点和第一个有效过滤集之间的过滤 “差距”。在典型的图表中，可能会存在这样的差距，导致探索过早结束并导致召回率不佳。

我们必须加快速度

由于该图并未考虑过滤条件，我们需要对图进行更深入的探索。此外，为了避免陷入死胡同，我们必须对被过滤掉的节点执行向量比较。那么，如何在避免卡住的同时减少向量操作的数量呢？这正是Liana Patel等人在他们的 ACORN 论文中所解决的核心问题。

虽然本文讨论了多种图形技术，但我们关心的 Apache Lucene 具体算法是他们的 ACORN-1 算法。主要思想是你只探索满足你的过滤的节点。为了补偿增加的稀疏性，ACORN-1 将探索范围扩展到邻近区域之外。现在，我们不再只是探索直接的邻居，还探索每个邻居的邻居。这意味着对于具有 32 个连接的图，探索不会只查看最近的 32 个邻居，而是会尝试在 32*32=1024 个扩展邻域中寻找匹配的邻居。

在 Lucene 中，我们通过以下方式对 ACORN-1 算法进行了轻微的调整。仅当邻域中超过 10% 的向量被过滤掉时，才会探索扩展邻域。此外，如果我们已经获得至少 neighborCount * 1.0/(1.0 - neighborFilterRatio) 的分数，就不会探索扩展邻域。这使得搜索者能够利用连接更紧密的邻域，其中邻域连通性与过滤器高度相关。

我们还注意到，无论是在逆相关过滤器（例如，仅匹配远离查询向量的向量的过滤器）还是极其严格的过滤器中，仅探索每个邻居的邻域是不够的。当没有找到通过过滤器的有效向量时，搜索器还将尝试比邻居的邻居分支得更远。然而，为了防止在图中迷失，这种额外的探索是有限的。

数字不会说谎

在多个真实世界的数据集中，这种新的过滤方法带来了显著的速度提升。以下是对 100 万 Cohere 向量按 0.05% 进行随机过滤的效果：

左上方是 “获胜”，表明该候选人明显更胜一筹。然而，为了达到相同的召回率，需要调整搜索参数（例如 num_candidates）。

为了进一步研究随着更多向量通过过滤器而导致的改进减少，我们对 8M Cohere Wiki 文档数据集进行了另一项测试。一般来说，无论过滤的向量数量有多少，你都希望获得更高的召回率，同时访问的向量更少。量化这一点的一个简单方法是检查召回率与访问率的比率。

在这里，我们看到新的过滤搜索方法如何实现更好的召回率 vs. 访问率。

显然，当达到 60% 左右时，改进水平将会下降或者消失。因此在 Lucene 中，只有当 40% 以上的向量被过滤掉时，才会使用这个新算法。

即使我们的夜间 Lucene 基准测试也因这一变化而取得了令人瞩目的进步。

必须快点

通过元数据过滤 kNN 搜索是实际用例的关键。在 Lucene 10.2 中，我们将其速度提高了 5 倍，使用了更少的资源，并且保持了较高的召回率。我非常高兴能够在未来的 Elasticsearch v9 版本中将它交到用户手中。

Elasticsearch 包含许多新功能，可帮助你为你的用例构建最佳的搜索解决方案。深入了解我们的示例笔记本以了解更多信息，开始免费云试用，或立即在本地机器上试用 Elastic。

原文：Filtered HNSW search, fast mode - Elasticsearch Labs