Manticore Search 中的 KNN 早停机制深度解读

背景

现代搜索引擎的功能早已超越了简单的关键词匹配。当你搜索“设定在巴黎的舒适悬疑小说”时，搜索引擎返回的结果可能是“法国的大气侦探小说”，这正是向量搜索（Vector Search）在发挥作用。在这一过程中，文档和查询被转换为数字列表，即嵌入向量（Embeddings），搜索引擎通过计算这些数字之间的相似度，找到与查询向量最接近的文档。

Manticore Search 原生支持这一功能。其底层使用了一种名为 HNSW（Hierarchical Navigable Small World，分层导航小世界）的数据结构。HNSW 是一种图结构，通过连接相近的向量，使得搜索引擎无需扫描每一篇文档即可快速找到最近邻（Nearest Neighbors）。这使得向量搜索的速度足以在毫秒级时间内处理数百万篇文档。

然而，HNSW 算法存在一个效率瓶颈。在遍历的早期阶段，几乎所有的距离计算都能找到比当前结果集中更好的候选者。随着搜索的进行，这种改进变得越来越罕见，但算法仍会继续遍历图结构，直到耗尽探索预算（exploration budget）。此时，结果集通常已经收敛，剩余的计算工作对提升结果质量几乎没有贡献。早停机制（Early Termination） 正是为了解决这一问题：通过检测收敛点并提前停止搜索，从而节省计算资源。

核心内容

早停机制的必要性

早停的效果随着参数 $k$ 的增长而变得更加显著。$k$ 是查询要求 Manticore 返回的最近邻数量。返回更多的邻居需要更多的图探索，而其中很大一部分额外工作是在结果集已经稳定之后进行的。因此，早停机制的价值在于切断了这些不必要的计算。

这种浪费在使用 向量量化（Vector Quantization） 时尤为明显。量化通过压缩存储的向量来节省内存，但这会略微降低搜索精度。为了恢复精度，Manticore 采用 过采样（Oversampling） 技术：它获取比请求数量多 3 倍的候选者，然后使用原始全精度向量对它们进行重新评分。在默认的 3 倍过采样下，HNSW 每次查询会探索更多的候选者。应用程序通常会向向量索引请求数百或数千个候选者，然后将其重新评分、重排序或过滤，以减少最终结果集的大小，从而提高召回率和精度。这增加了延迟，而早停机制有助于挽回部分延迟。

性能提升数据

浪费是可衡量的。在包含 100 万个向量的数据集上的基准测试显示：

• 当 $k=60$（默认结果限制，配合默认 3 倍过采样）时，早停机制将距离计算量减少到完整搜索的约 65%。
• 当 $k=1000$ 时，计算量降至 30%。
• 当 $k=10000$ 时，仅占 20%。

搜索在探索预算耗尽之前很久就已经收敛，且节省的计算量随 $k$ 值的增大而增加。早停机制允许 Manticore 检测这种收敛并提前终止。该算法的设计目标是：与完整的 HNSW 搜索相比，结果集的精度损失不超过 2-4%。

算法工作原理

该算法跟踪一个简单的信号：发现率（Discovery Rate），即实际改善结果集的距离计算所占的比例。

每次计算新节点的距离时，会发生以下两种情况之一：

1. 它足够好，可以进入堆（Heap）——即保存当前最佳候选邻居的优先队列。进入堆被视为一次“发现”。
2. 它比堆中现有的所有候选者都差，因此被丢弃。

在搜索早期，发现很频繁，因为堆正在填充，大多数候选者都是有用的。随着搜索的进行，堆被良好的结果饱和，发现变得罕见。大多数新的距离计算只是确认算法已经找到了最佳候选者。

Manticore 监控这一转变。在每一轮邻居扩展后，它计算发现率： $$ \text{discovery_rate} = \frac{\text{new_candidates_collected}}{\text{distances_computed}} $$

如果这一比率在连续几轮中低于某个阈值，搜索就会停止。其核心思想很简单：如果算法不断计算距离但没有任何改进，说明搜索已经收敛。

阈值设定：基于分位数的自适应

这就引出了下一个问题：什么阈值算作“低”？固定阈值效果不佳，因为不同的数据集以及同一数据集的不同区域具有截然不同的发现率分布。什么是“低”取决于上下文。

Manticore 使用 基于分位数的自适应阈值（Quantile-based Adaptive Threshold）。它不是将发现率与固定数值进行比较，而是持续估计最近几轮的低百分位数（20 百分位数，L2 距离为 14 百分位数），并将其作为基线。这种方法保持了轻量级，同时允许其适应不同的数据集和图的不同区域。

换句话说，阈值会根据局部搜索模式进行调整。如果算法进入图的稀疏区域，阈值会降低，避免过早停止。如果进入更丰富的区域，阈值会升高。

耐心机制：多少次“坏轮次”后停止？

仅靠阈值是不够的。单次低发现率的轮次不足以宣告收敛，这可能只是找到更好路径前的暂时低谷。Manticore 使用 “耐心计数器”（Patience Counter），要求多个连续的“坏轮次”才会终止搜索。

耐心值与 $ef$（HNSW 探索因子，控制搜索保留多少候选者）成反比。例如，在低 $ef$ 值时，耐心值范围为 9；在极高 $ef$ 值时，降至 6。较大的 $ef$ 值意味着更多的总轮次，因此即使耐心值较低，算法在决定停止前也看到了更多的证据。每当一轮具有健康的发现率时，计数器重置为零，这意味着一次好的轮次会重启耐心窗口。这防止算法在通往图 productive 区域的暂时 plateau（平台期）期间停止。

预热阶段

在堆仍在填充（即收集到的候选者少于 $ef$）时，算法会忽略终止信号。在此阶段，发现率人为地高，因为几乎所有内容都进入堆，因此该信号没有用处。早停仅在堆满且新候选者必须替换现有候选者后才开始生效。

基准测试结果

分位数阈值经过调整，以保持精度损失在 2-4% 以内。它们针对 L2 和余弦/IP 距离度量分别进行了调整，并在量化和非量化数据上进行了验证。

以下基准测试在拥有 8 个物理核心/16 个逻辑核心的机器上，使用 dbpedia-entities 数据集（100 万个向量，768 维）运行。

• 精度（Precision）：指真实 $k$ 最近邻出现在结果集中的比例（固定 $k$ 时，等同于 Recall@k）。
• 精度比率（Precision Ratio）：带早停（ET）的 HNSW 精度除以不带早停的精度（1.0 表示无精度损失）。
• 访问比率（Visit Ratio）：执行的距离计算量与完整 HNSW 搜索的比率（越低越好）。

为了隔离早停对原始 HNSW 遍历的影响，过采样和重新评分被禁用。

图表中的绿线（精度）在所有 $k$ 值下几乎保持平坦，精度比率在整个基准测试中保持在 0.97 以上。与此同时，橙线（访问比率）急剧下降。

• 在 $k=100$ 时，它将近乎减半距离计算量。
• 在 $k=1000$ 时，节省了 70%。
• 在 $k=10000$ 时，节省了 80%。

当 $k \le 10$ 时，早停机制被禁用，因为搜索已经足够便宜，节省的计算量不足以证明任何精度损失的合理性。节省的计算量随 $k$ 增长，因为更大的结果集导致更多的邻居扩展轮次，从而有更多机会提前检测收敛。

并发负载下的性能

上述基准测试表明，早停大幅减少了距离计算，同时保持了精度。但这对于实际查询延迟意味着什么，特别是在并发负载下？下图显示了在同一 dbpedia 数据集上，1、8 和