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 个最近邻居所需的向量比较次数。在某些过滤器集大小下，向量比较的次数可能会显著增加，从而降低搜索性能。

由于 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) 的分数，就不会探索扩展邻域。这使得搜索者能够利用连接更紧密的邻域，其中邻域连通性与过滤器高度相关。

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