Manticore Search中的KNN提前终止

# Manticore Search 中的 KNN 早期终止 来源：https://manticoresearch.com/blog/knn-early-termination/ 现代搜索引擎远不止关键词匹配。当你搜索“温馨的巴黎谋杀案”却得到“法国的悬疑小说”结果时，这正是向量搜索在发挥作用：文档和查询被转换为数字列表（称为嵌入），搜索引擎会找到那些数字与查询最接近的文档。 Manticore Search 原生支持这一功能。其底层使用了一种名为 HNSW 的数据结构：一个连接相邻向量的图，从而无需扫描每个文档即可快速找到最近邻。这使得向量搜索能够在毫秒级别处理数百万条文档。 > 但 HNSW 存在一个低效之处。在遍历初期，几乎每次距离计算都会找到一个比结果集中现有候选更优的候选。 随着搜索的进行，这种改进变得稀少，但算法会继续遍历图，直到耗尽探索预算。此时，结果集通常已经收敛，剩余的工作对改进结果几乎毫无贡献，甚至毫无贡献。早期终止通过检测到这个节点并提前停止，解决了这一问题。 随着 `k` 的增大，这种效果愈发明显。`k` 是查询要求 Manticore 返回的最近邻数量。返回更多邻居需要更密集的图探索，而这些额外工作大多发生在结果集稳定之后。这也让早期终止更有价值，因为它可以削减更多不必要的工作。 向量量化（https://manual.manticoresearch.com/Searching/KNN#Vector-quantization）会加剧这一现象。量化压缩存储的向量以节省内存，但会略微降低搜索精度。为恢复精度，Manticore 使用了过采样（https://manual.manticoresearch.com/Searching/KNN#KNN-vector-search）：它获取请求数量 3 倍的候选，然后使用原始的完整精度向量重新打分。在默认的 3 倍过采样下，HNSW 每次查询会探索更多候选。大 `k` 值通常来自这种候选扩展：应用可能从向量索引中请求数百或数千个候选，然后重新打分、重新排序或筛选，得到更小的最终结果集，以提高召回率和精度。这会增加延迟，而早期终止有助于挽回部分延迟。 这种浪费是可衡量的。在一个 100 万向量的数据集上进行的基准测试显示，当 `k=60`（默认 3 倍过采样下的默认结果限制）时，早期终止将距离计算减少到完整搜索的约 65%。当 `k=1000` 时，计算量降至 30%。当 `k=10000` 时，仅为 20%。搜索在探索预算耗尽之前很久就已收敛，且节省幅度随 `k` 增长。 早期终止让 Manticore 能够检测到这种收敛并停止。该算法设计时设定了特定的精度目标：相比完整的 HNSW 搜索，结果集精度损失不超过 2-4%。 ## 工作原理 该算法追踪一个简单信号：发现率——即实际改进结果集的距离计算所占的比例。 每次计算新节点的距离时，有两种情况：要么足够好进入堆（保存当前最佳候选邻居的优先队列），要么比堆中所有现有结果都差，被丢弃。进入堆计为一次“发现”。搜索初期，发现频繁——堆正在填满，大多数候选有用。随着搜索进行，堆中充满优质结果，发现变得稀少。大多数新的距离计算只是确认算法已经找到了最佳候选。 Manticore 监控这一转变。在每一轮邻居扩展后，它计算发现率： `` discovery_rate = new_candidates_collected / distances_computed `` 如果该比率连续多轮低于某个阈值，搜索停止。 > 思路很简单：如果算法不断计算距离但结果毫无改进，那么搜索已经收敛。 ## 阈值：基于分位数的自适应 这就引出了下一个明显的问题：什么样的阈值才算“低”？固定阈值效果不佳——不同数据集甚至同一数据集的不同区域，发现率的分布差异很大。何为“低”取决于上下文。 Manticore 使用基于分位数的自适应阈值。它不将发现率与固定数值比较，而是持续估计最近几轮的低百分位数（20 百分位数，对于 L2 距离则为 14 百分位数）并以此作为基线。这使方法保持轻量，同时能适应不同数据集和图的不同区域。 换句话说，阈值会自适应局部搜索模式。如果算法进入图的稀疏区域，阈值会降低，避免过早停止。如果进入更密集的区域，阈值会升高。 ## 耐心：停止前需要多少轮低效 仅仅阈值还不够。单轮低发现率不足以判定收敛，可能只是暂时的低谷，之后搜索会找到更好的路径。Manticore 使用一个“耐心计数器”，要求在停止前连续出现多轮低效。 耐心值与 `ef`（HNSW 探索因子，控制搜索继续探索的候选数量）成反比。例如，耐心值在低 `ef` 时为 9，在高 `ef` 时降至 6。更大的 `ef` 意味着总轮数更多，即使耐心值较低，算法在决定停止前也已看到更多证据。每当一轮的发现率健康时，计数器重置为零，因此单轮良好表现会重启耐心窗口。这防止了算法在通往图高产区间的临时平台期停止。 ## 预热阶段 当堆尚未填满（即收集的候选少于 `ef`）时，算法忽略终止信号。在此阶段，发现率人为偏高，因为几乎所有内容都进入堆，信号不可用。早期终止仅在堆满且新候选必须替换现有候选时才开始。 ## 基准测试结果 分位数阈值经过调优，确保精度损失控制在 2-4% 以内。它们分别针对 L2 和余弦/IP 距离度量进行了调整，并在量化和非量化（https://manual.manticoresearch.com/Searching/KNN#Vector-quantization）数据上进行了验证。 以下基准测试使用 dbpedia-entities（https://huggingface.co/datasets/KShivendu/dbpedia-entities-openai-1M）数据集（100 万向量，768 维），在 8 物理核心 / 16 逻辑核心的机器上运行。 - “精度”在此指真实 k 近邻出现在结果集中的比例（固定 k 下，与 recall@k 相同）。 - “精度比”是启用早期终止（“ET”）的 HNSW 精度除以未启用时的精度（1.0 表示无精度损失）。 - “访问比”是执行的距离计算数量与完整 HNSW 搜索的比例（越低越好）。 过采样和重打分（https://manual.manticoresearch.com/Searching/KNN#KNN-vector-search）已被禁用，以隔离早期终止对原始 HNSW 遍历的影响。 精度比 vs 访问比 图表上的绿线（精度）在所有 `k` 值下几乎保持平坦，精度比在整个基准测试中保持在 0.97 以上。同时，橙线（访问比）急剧下降。在 `k=100` 时，距离计算几乎减半。在 `k=1000` 时，节省 70%。在 `k=10000` 时，节省 80%。 在 `k <= 10` 时，早期终止被禁用，因为搜索已经非常便宜，节省的收益不足以抵消任何精度损失。节省幅度随 `k` 增大而增长，因为更大的结果集导致更多轮的邻居扩展，也有更多机会提前检测到收敛。 ## 并发负载下的性能 上述基准测试表明，早期终止大幅减少了距离计算，同时保持了精度。但这对于实际查询延迟意味着什么，尤其是在并发负载下？下图显示了在相同 dbpedia 数据集上，1、8 和 16 个并发线程下的延迟比（ET / 无 ET）： 按线程数的早期终止延迟比 在 `k=1000` 时，早期终止将距离计算减少 71%（比率为 0.29）。延迟改进取决于同时运行的线程数： - **1 线程：** 快 24%（比率 0.76） - **8 线程：** 快 45%（比率 0.55） - **16 线程：** 快 48%（比率 0.52） > 距离计算的节省量不随线程数变化，但延迟优势从 1 线程到 16 线程几乎翻倍。 主要原因是降低了 CPU 内存系统的压力。每次距离计算都会将向量数据和图链接拉入缓存。当多个线程同时运行 HNSW 遍历时，它们会竞争共享缓存和内存带宽。每次查询执行更少的距离计算减少了内存流量，使每个线程的工作集更小，并减少了查询间的缓存抖动。结果，每个线程完成得更快，且相互干扰更少。 单线程基准测试低估了早期终止的优势。在生产级并发负载下，延迟减少的百分比大约翻倍。 ## 早期终止何时生效（以及何时不生效） 早期终止默认启用，适用于量化和非量化向量数据。当 `k <= 10` 时自动禁用。 收益随有效探索预算（即 `max(ef, k)`）增长。由于 hnswlib 内部使用此值作为保持的候选数量，更大的 `k` 意味着更多候选、更多轮次以及更多检测收敛的机会。 量化向量通常与重打分和过采样（默认均启用）一起使用，以恢复量化导致的精度损失。过采样（默认 3 倍）会放大传递给 HNSW 的有效 `k`。例如，`k=100` 的查询在过采样为 3 倍时内部使用 300 个候选。更大的搜索预算给早期终止更多空间来检测收敛并提前停止。由于早期终止的性能优势随 `k` 增加，过采样将查询推入节省最大的范围。 ## 语法 早期终止默认开启。要禁用： **SQL：** `` -- 默认：早期终止启用 SELECT id, knn_dist() FROM products WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33)); -- 显式禁用早期终止 SELECT id, knn_dist() FROM products WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { early_termination=0 }); -- 与其他 KNN 选项结合 SELECT id, knn_dist() FROM products WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { ef=200, early_termination=0 }); `` **JSON：** `` POST /search { "table": "products", "knn": { "field": "embedding", "query": [0.12, 0.45, 0.78, 0.33], "early_termination": false } } `` ## 何时禁用 在某些场景下你可能希望关闭早期终止： - **最大精度至关重要。**早期终止牺牲少量召回率换取速度。如果你的应用要求在给定 `ef` 下获得 HNSW 所能提供的绝对最佳召回率，请禁用它。 - **小 k 值（<= 30）。**算法在 `k <= 10` 时自动禁用，但即使 `k` 在 11 到 30 之间，性能提升也有限。如果你在此范围内注意到任何召回率差异，禁用早期终止只会带来很小的延迟代价。 - **基准测试 HNSW 召回率。**如果你在测量 HNSW 召回率，可能需要确定性行为，无需自适应捷径。禁用早期终止以获得干净的基线。 ## 与其他 KNN 优化的关系 早期终止是 Manticore 应用于 KNN 搜索的多项优化之一。它独立于其他优化并可与它们叠加： - 预过滤（https://manticoresearch.com/blog/knn-prefiltering/）通过在 HNSW 遍历期间跳过已过滤的文档来减少浪费的工作。早期终止通过在结果集收敛后停止遍历来减少浪费的工作。它们解决不同问题，且配合良好。 - 过采样（https://manticoresearch.com/blog/quantization/#why-oversampling--rescoring-matters）检索比 `k` 更多的候选，以提高重打分后的召回率。早期终止可以通过在找到足够好的候选后停止，来降低这种扩展搜索的成本。 - 重打分（https://manticoresearch.com/blog/quantization/#why-oversampling--rescoring-matters）在使用量化向量进行初始搜索后，使用全精度向量重新计算距离。早期终止在初始量化搜索阶段运行，在重打分启动前减少评估的候选数量。 - **自动暴力回退**在线性扫描成本更低时完全跳过 HNSW。早期终止仅在实际使用 HNSW 时适用。