KNN 早期终止策略：在 Manticore Search 中削减高维向量检索的计算开销

在高维向量检索场景中，HNSW（Hierarchical Navigable Small World）图算法已成为业界标准。它通过构建多层图结构连接邻近向量，避免了全量扫描的线性复杂度。然而，HNSW 存在一个隐形的计算浪费问题：在遍历早期，几乎每次距离计算都能发现比当前结果集更优的候选；但当结果集趋于收敛后，算法仍会继续遍历直到耗尽预设的探索预算。这种 "无效遍历" 在检索大规模向量时尤为明显。

Manticore Search 近期引入的 KNN 早期终止（Early Termination）策略，正是针对这一痛点设计的优化方案。该策略通过监测 "发现率"（discovery rate）动态识别结果集的收敛点，在保证精度损失控制在 2-4% 的前提下，显著削减距离计算量。在百万级向量数据集的基准测试中，当 k=1000 时距离计算减少至原来的 30%，k=10000 时更是降至 20%。

核心机制：发现率监测与自适应阈值

早期终止策略的核心在于量化 "何时该停止"。Manticore 采用发现率作为收敛信号，其定义为每轮邻居扩展后进入候选堆的新节点比例：

discovery_rate = new_candidates_collected / distances_computed

在搜索初期，候选堆尚未填满，发现率通常较高；随着优质候选不断进入堆中，后续距离计算大多只是确认 "当前结果已足够好"。当发现率持续低于阈值时，即可判定搜索已收敛。

关键在于阈值的设定。固定阈值难以适应不同数据集和图区域的分布差异。Manticore 采用分位数自适应策略，持续估计近期轮次的低百分位数（L2 距离使用 14 百分位，余弦 / 内积距离使用 20 百分位）作为动态基线。这种设计使阈值能够根据局部搜索模式自动调整：进入稀疏图区域时阈值下降避免过早终止，进入稠密区域时阈值上升提高敏感度。

工程参数：耐心计数器与预热阶段

单一轮次的低发现率不足以触发终止 —— 这可能只是通往更优区域的暂时低谷。Manticore 引入 "耐心计数器" 机制，要求连续多轮低发现率才执行终止。该参数与 HNSW 的探索因子 ef 成反比：低 ef 时设置为 9 轮，高 ef 时降至 6 轮。较大的 ef 意味着更多总轮次，即使耐心值较低也能积累充分的收敛证据。一旦某轮发现率回升，计数器立即归零，防止在通往优质区域的路径上误判终止。

此外，算法设置了预热阶段。在候选堆未满（收集候选数少于 ef）时，发现率被人为抬高（几乎所有计算都会入堆），此时信号不可靠。早期终止仅在堆填满、新候选必须替换旧候选时才正式启用。

性能收益：计算量削减与并发增益

在 dbpedia-entities 数据集（100 万向量，768 维）的测试中，早期终止展现出显著的计算效率提升。随着 k 值增大，收益愈发明显：k=100 时距离计算近乎减半，k=1000 时节省 70%，k=10000 时节省 80%。值得注意的是，k≤10 时该策略自动禁用 —— 此时搜索本身开销有限，节省空间不足以 justify 任何精度损失。

更有趣的现象出现在并发场景。单线程下 k=1000 时延迟降低 24%，8 线程时提升至 45%，16 线程时达到 48%。距离计算的绝对减少量在各线程数下保持一致，但并发时的延迟收益近乎翻倍。原因在于内存系统压力的缓解：每次距离计算都会将向量数据和图链接载入缓存，多线程竞争共享缓存和内存带宽时，减少单查询的计算量能显著降低缓存抖动，使各线程工作集更小、相互干扰更少。

实践建议：启用条件与优化组合

早期终止默认启用，适用于大多数生产场景。但在以下情况建议显式禁用：

• 极致精度需求：若应用要求 HNSW 在特定 ef 下的最佳召回率，需关闭该策略以获得确定性行为
• 小 k 值检索：k 在 11-30 区间时性能收益有限，若观察到召回差异可安全关闭
• 基准测试：测量 HNSW 召回率时需禁用，避免自适应机制干扰结果

该策略与其他 KNN 优化手段形成良好互补。预过滤（prefiltering）在遍历阶段跳过被过滤的文档，早期终止则在收敛后停止遍历，二者解决不同层面的浪费。过采样（oversampling）默认 3 倍扩大候选集以恢复量化损失的精度，这恰好将查询推入 k 值更大的区间 —— 正是早期终止收益最大的范围。量化后的初始搜索阶段应用早期终止，能在重打分（rescoring）前减少候选评估量，形成完整的优化链路。

配置示例

通过 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 });

JSON 接口同样支持：

POST /search
{
    "table": "products",
    "knn": {
        "field": "embedding",
        "query": [0.12, 0.45, 0.78, 0.33],
        "early_termination": false
    }
}

对于需要处理大规模向量检索的搜索系统，早期终止提供了一种在精度与性能之间取得平衡的实用方案。通过监测发现率这一简单信号，结合自适应阈值和耐心机制，系统能够在结果集收敛时及时止损，将计算资源释放给更有价值的查询。

参考来源

• Manticore Search Blog: KNN early termination in Manticore Search

ai-systems