HNSW 搜索的快速过滤模式

Filtered HNSW search, fast mode

多年来，Apache Lucene 和 Elasticsearch 一直支持带有 kNN 查询的过滤搜索，允许用户检索符合特定元数据过滤条件的最近邻。然而，当处理半限制性过滤器时，性能一直较差。在 Apache Lucene 中，我们引入了一种 ACORN-1 的变体，这是一种新的过滤 kNN 搜索方法，在召回率几乎不下降的情况下，搜索速度提高了最多 5 倍。

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

为什么搜索更少的文档反而更慢

反直觉地，过滤文档从而减少候选数量实际上会使 kNN 搜索变慢。对于传统的词法搜索，文档越少，评分操作越少，搜索速度越快。然而，在 HNSW 图中，主要成本是识别 k 个最近邻所需的向量比较数量。在某些过滤器设置大小下，向量比较的数量可能会显著增加，导致搜索性能变慢。

未过滤的图搜索

这是一个未过滤的图搜索示例。注意这里大约有 6 次向量操作。

由于 Apache Lucene 中的 HNSW 图在构建时并不知道过滤条件，它完全基于向量相似性构建。当应用过滤器以检索 k 个最近邻时，搜索过程会遍历更多图。这是因为本地图邻域内的自然最近邻可能被过滤掉，需要更深入的探索并增加向量比较的数量。

过滤后的图搜索示例

这是当前过滤后的图搜索示例。“虚线圈”表示不匹配过滤条件的向量。我们甚至对被过滤掉的向量进行向量比较，导致更多的向量操作，总共约 9 次。

你可能会问，为什么对完全不匹配过滤条件的节点进行向量比较？实际上，HNSW 图已经是稀疏连接的。如果我们在探索过程中只考虑匹配的节点，搜索过程可能会轻易地卡住，无法有效遍历图。

典型图

注意在入口点和第一个有效过滤集之间的过滤“鸿沟”。在典型图中，可能存在这样的间隙，导致探索提前结束，导致召回率较低。

我们必须加快速度

由于图不考虑过滤条件，我们必须更多地探索图。此外，为了避免卡住，我们必须对被过滤掉的节点进行向量比较。我们怎样才能减少向量操作的数量而不被卡住？这正是 Liana Patel 等人在他们的 ACORN 论文中解决的问题。

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

ACORN 算法在行动

在这里你可以看到 ACORN 算法在行动。只对有效匹配的向量进行向量比较和探索，迅速从直接邻居扩展。总共只有约 6 次向量操作。

在 Lucene 中，我们稍微调整了 ACORN-1 算法。只有当直接邻居中超过 10% 的向量被过滤掉时才会探索扩展邻居。此外，如果我们已经评分了至少 neighborCount * 1.0/(1.0 - neighborFilterRatio)，则不会探索扩展邻居。这允许搜索器利用更密集连接的邻域，其中邻域连接性与过滤条件高度相关。

我们还注意到，在反向相关过滤器（例如，只匹配距离查询向量较远的向量的过滤器）或非常严格的过滤器中，仅探索每个邻居的邻域是不够的。当没有通过过滤器的有效向量时，搜索器还会尝试进一步分支邻居的邻居。然而，为了防止在图中迷失，这种额外的探索是有界的。

数据不会撒谎

在多个真实世界数据集中，这种新过滤方法提供了显著的速度提升。以下是随机过滤 0.05% 1M Cohere 向量 的结果：

1M Cohere 向量

图中向上和向左的部分表示“胜利”，表明候选者显著更好。不过，要达到相同的召回率，需要调整搜索参数（例如 num_candidates）。

为了进一步研究随着通过过滤器的向量数量增加而带来的改进，我们进行了另一个测试，涉及 8M Cohere 维基文档数据集。通常，无论过滤的向量数量如何，你都希望有更高的召回率和更少的访问向量。量化这一点的简单方法是检查召回率与访问率的比率。

过滤搜索方法

在这里我们看到新的过滤搜索方法在召回率与访问率比率上取得了更好的效果。

显然，在接近 60% 时，改进趋于平稳或消失。因此，在 Lucene 中，当过滤掉 40% 或更多的向量时才会使用这种新算法。

即使是在我们的夜间 Lucene 基准测试中，这一变化也带来了令人印象深刻的改进。

Apache Lucene 运行 8M 768 文档向量

Apache Lucene 在 8M 768 文档向量上运行，随机过滤允许 5% 的向量通过。这种图表让我感到高兴。

必须快速前进

在元数据上进行过滤 kNN 搜索对于真实世界的用例非常重要。在 Lucene 10.2 中，我们通过使用更少的资源并保持高召回率，使搜索速度提高了最多 5 倍。我非常兴奋地期待在未来的 Elasticsearch v9 版本中将这一功能交到用户手中。