Efficient Vector Search in the Wild: One Model for Multi-K Queries

本文提出了 OMEGA，一种仅需在 K=1 上训练即可通过动态细化机制高效处理多 K 值向量搜索的通用模型，在显著降低预处理成本的同时实现了比现有最先进方法更低的延迟和同等召回率。

要点

这篇论文介绍了一个名为 OMEGA 的新系统，它旨在解决向量数据库（一种用于存储和搜索海量数据，比如图片、推荐内容或 AI 知识库的数据库）中一个非常头疼的问题：如何用一个模型，既快又准地回答各种不同数量的搜索请求。

为了让你轻松理解，我们可以把向量数据库想象成一个巨大的、迷宫般的图书馆，里面藏着几亿本书（向量数据）。

1. 核心痛点：图书馆的“死脑筋”管理员

在这个图书馆里，读者（用户）经常来问：“帮我找最像我手里这本书的 K 本书。”

• 有时候 K=1（只要一本最像的）；
• 有时候 K=10（要十本最像的）；
• 有时候 K=100（要一百本最像的）。

以前的做法（传统方法）：
图书馆管理员（搜索算法）为了保险起见，不管你要几本，他都盲目地跑遍整个迷宫，或者设定一个固定的“最大奔跑步数”。

• 问题： 如果你只要 1 本，他跑了 1000 步才找到，太慢了（浪费性能）；如果你要 100 本，他跑了 1000 步可能还没找全，结果不准（牺牲精度）。这就好比为了找一颗珍珠，把整个大海都捞了一遍，效率极低。

以前的“智能”尝试（现有 AI 模型）：
最近有人给管理员装了一个“智能大脑”（机器学习模型），让他学会在跑了几步后判断：“嗯，我觉得已经找到目标了，可以停下了！”

• 问题： 这个大脑是偏科生。如果你训练它专门找"K=1"，它找 1 本很快很准；但如果你突然让它找"K=100"，它就懵了，要么找不全（因为以前只练过找 1 个），要么为了找全而跑得太远（因为不知道 100 个需要跑多远）。
• 更糟糕的是： 如果要让它适应所有 K 值，就得给它重新训练很多次，这就像让管理员为了适应不同数量的请求，每天要花大量时间重新学习，准备时间（预处理成本）太长，图书馆根本等不起。

2. OMEGA 的解决方案：一个“万能”的聪明大脑

OMEGA 提出了一种全新的思路：“以不变应万变”。它只训练一个专门找“第 1 名”（Top-1） 的超级大脑，然后利用这个大脑，通过巧妙的技巧，搞定任何数量的 K 值搜索。

核心魔法一：剥洋葱法（动态精修）

想象你要找“前 5 名”的选手。

• 传统做法： 训练一个专门找前 5 名的模型。

• OMEGA 的做法：

  1. 先问大脑：“谁是第 1 名？”大脑很快找到了。
  2. 然后，把第 1 名从名单里暂时屏蔽（Mask） 掉，假装他不存在。
  3. 再问大脑：“现在谁是新的第 1 名？”（这其实就是原来的第 2 名）。
  4. 重复这个过程，直到凑齐 K 个。

  比喻： 就像剥洋葱。你不需要知道整个洋葱长什么样，你只需要知道怎么剥开最外面一层，露出里面新的一层，再剥下一层。OMEGA 的模型只擅长“剥开最外层找核心”，通过不断重复这个动作，就能找到任何数量的结果。

核心魔法二：看“走路轨迹”而不是“看距离”

为了让这个“剥洋葱”的方法有效，模型必须能识别出“什么时候该停”。

• 以前的模型： 看“距离”。比如“如果距离小于 5 米，就找到了”。但当你屏蔽掉第 1 名后，第 2 名的距离可能突然变大了，模型就傻眼了，以为还没找到。
• OMEGA 的模型： 看**“走路轨迹”（Trajectory）。
  比喻： 想象你在黑暗中找宝藏。以前的模型是看“离宝藏还有多少米”，但宝藏位置变了，米数就不准了。OMEGA 的模型是看“脚下的路”：它发现，当你越来越接近宝藏时，你每走一步，脚下的路会呈现出一种“越来越陡峭、越来越快”** 的下降趋势。
  无论你要找第 1 个还是第 100 个宝藏，这种“越来越快接近目标”的趋势（轨迹） 都是一样的。所以，只要模型学会了识别这种“下坡路”的轨迹，它就能在找第 1 个时学会，在找第 100 个时也能用，完全不需要重新训练！

核心魔法三：统计预测（不用每次都问大脑）

虽然“剥洋葱”很聪明，但如果 K=100，就要问大脑 100 次，大脑也会累（调用模型太多次，耗时）。

• OMEGA 的优化： 它利用统计学规律。
  比喻： 就像你爬山。如果你已经爬到了半山腰（找到了前 20 个），根据经验（统计表格），你大概率已经覆盖了山顶附近 80% 的区域。这时候，你不需要再一步步问“还有多远？”，直接查一下**“经验表”** 就能算出：“哦，按照这个进度，再爬几步肯定够了。”
  如果经验表告诉你“肯定够了”，OMEGA 就直接停止搜索，不再调用大脑，从而大大节省时间。

3. 最终效果：又快、又准、又省钱

OMEGA 在阿里巴巴的真实生产环境和公开数据集上进行了测试，效果惊人：

1. 准备时间（预处理）极短： 只需要训练一次“找第 1 名”的模型，就像只练了一次基本功，就能应付所有考试。相比其他方法，它的准备时间只有别人的 16% - 30%。
2. 搜索速度（延迟）更快： 在同样的准确率下，OMEGA 比目前最先进的其他方法快 6% - 33%。因为它不会为了找小 K 值而盲目跑太远，也不会为了大 K 值而犹豫不决。
3. 适应性强： 无论用户要 1 个结果还是 100 个结果，它都能游刃有余。

总结

OMEGA 就像一位只练过“单挑”冠军的武术大师。

• 别人让他打 1 个对手，他秒杀；
• 别人让他打 10 个对手，他不需要重新练“群战”，只需要把打过的对手一个个“暂时封印”，然后继续用“单挑”的本领去解决剩下的，直到全部搞定。
• 而且，他还会看“战局走势”，如果感觉已经稳赢了，就直接收手，不再浪费体力。

这项技术让向量数据库在面对千变万化的用户需求时，既能秒回，又能精准，还不用花大价钱去重新训练系统，是真正“野性”（Real-world）场景下的高效解决方案。

技术摘要

这是一篇关于向量数据库高效检索的学术论文总结，论文标题为 《Efficient Vector Search in the Wild: One Model for Multi-K Queries》（野外高效向量搜索：一种模型应对多 K 查询），提出了名为 OMEGA 的系统。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 背景：向量数据库广泛应用于推荐系统、RAG（检索增强生成）等场景，核心操作是近似最近邻搜索（ANNS）。基于图的索引（如 HNSW）是目前的主流，但存在精度与延迟的权衡（Trade-off）。
• 现有挑战：
  1. 多 K 查询需求（Multi-K Queries）：现实生产环境中，不同应用甚至同一应用的不同请求需要不同的结果数量 $K$。现有的基于学习的方法（如 DARTH, LAET）通常针对特定的 $K$ 值训练模型。
  2. 泛化能力差：针对特定 $K$ 训练的模型无法直接泛化到其他 $K$ 值。
     • 若用大 $K$ 模型处理小 $K$ 查询，会导致过度搜索（Over-search），增加延迟。
     • 若用小 $K$ 模型处理大 $K$ 查询，会导致搜索不足（Under-search），降低召回率（Recall）。
  3. 预处理成本高昂：为了支持多 $K$ 查询，传统方案需要为每个常用 $K$ 训练单独的模型，或者训练一个覆盖所有 $K$ 的大模型。这导致预处理时间（Preprocessing time）成倍增加（论文测量显示增加约 1.95 倍），而向量数据库的预处理成本（如索引压缩）本身已占服务成本的 22%，过高的预处理成本在实际部署中是不可接受的。

2. 方法论 (Methodology: OMEGA)

OMEGA 提出了一种**K 泛化（K-generalizable）**的向量搜索方法，其核心思想是：仅训练一个针对 $K=1$ 的基础模型，通过动态细化（Dynamic Refinement）和统计预测来支持任意 $K$ 值的查询。

核心组件：

1. 基于轨迹的特征工程 (Trajectory-based Features)

   • 挑战：在将 Top-K 问题转化为 $K$ 个 Top-1 问题（通过掩码已找到的向量）时，传统的特征（如最小距离）会失效，因为掩码改变了距离分布。
   • 解决方案：OMEGA 引入了**距离轨迹（Distance Trajectory）**特征，即搜索过程中查询向量与访问向量之间距离的变化趋势。
   • 优势：研究发现，无论搜索目标是第 1 近邻还是第 $x$ 近邻（在掩码后），距离急剧下降的趋势模式是相似的且对掩码鲁棒。这使得仅用 Top-1 数据训练的模型也能准确预测 Top-$x$ 的搜索状态。

2. 动态细化搜索 (Dynamic Refinement)

   • 机制：将 Top-$K$ 搜索分解为 $K$ 次 Top-1 搜索。
     • 首先找到 Top-1。
     • 将 Top-1 从候选集中“掩码”（Mask），此时原 Top-2 变为新的 Top-1。
     • 复用同一个 Top-1 模型继续搜索，直到找到所有 $K$ 个结果。
   • 优势：避免了为不同 $K$ 训练不同模型，极大降低了预处理成本。

3. 基于统计的预测优化 (Statistical Forecast)

   • 挑战：直接进行 $K$ 次模型调用虽然比全量搜索快，但累积的推理开销仍可能抵消收益，尤其是对于大 $K$。
   • 解决方案：利用统计规律。给定已找到 $N$ 个最近邻，第 $r$ ($r > N$) 个真值向量位于当前搜索集中的概率遵循特定的分布。
   • 实现：离线构建一个查找表（Lookup Table），记录 $P(\text{第}r\text{个真值被找到} | \text{已找到}N\text{个})$。
   • 流程：在搜索过程中，先查表估算当前搜索集满足目标召回率的概率。如果概率已达标，则直接停止搜索，无需再调用模型。这显著减少了模型调用次数。

3. 主要贡献 (Key Contributions)

1. 首个 K 泛化的学习式搜索方法：OMEGA 是第一个仅需训练一个 Top-1 模型（最小化预处理成本）即可高效支持任意 $K$ 值查询的图索引搜索系统。
2. 创新的特征设计：提出了“距离轨迹”特征，解决了掩码操作下模型特征失效的难题，实现了从 Top-1 到 Top-K 的无缝泛化。
3. 统计驱动的优化：设计了基于统计分布的预测机制，在无需模型推理的情况下提前终止搜索，进一步降低了推理开销。
4. 系统实现与开源：OMEGA 已开源，并正在集成到阿里巴巴的开源向量数据库 Zvec 中。

4. 实验结果 (Results)

论文在多个公开数据集（BIGANN, DEEP, GIST）和阿里巴巴生产环境数据集上进行了评估：

• 预处理成本：
  • OMEGA 仅需训练一个模型，其预处理时间仅为现有最佳方法（如 DARTH 为多 K 训练多个模型）的 16% - 30%。
• 延迟性能 (Latency)：
  • 在相同的预处理预算下，OMEGA 比 SOTA 学习式搜索方法（DARTH, LAET）的平均延迟低 6% - 33%。
  • 在达到相同召回率目标的前提下，OMEGA 比阿里巴巴内部使用的手动调优参数方法（Fixed）低 25% - 65% 的延迟。
  • 即使 OMEGA 的预处理时间仅为基线方法的 16-30%，其平均延迟仅比基线方法的“最优延迟”高 1-28%，性价比极高。
• 召回率 (Recall)：
  • 在所有测试集上，OMEGA 均能达到 95% 的目标召回率，且在大 $K$ 和小 $K$ 查询上表现一致，没有泛化带来的精度损失。
• 总计算成本：
  • 综合考虑预处理和服务阶段的 CPU 消耗，OMEGA 比基线方法减少了 4% - 24% 的总计算资源。

5. 意义与价值 (Significance)

• 解决“野外”部署痛点：直接针对生产环境中“多 K 查询”和“低预处理成本”的矛盾，提供了切实可行的解决方案。
• 打破精度与成本的权衡：证明了通过巧妙的算法设计（特征工程 + 统计预测），可以在不牺牲精度的前提下，大幅降低学习式搜索的部署门槛（预处理时间）。
• 通用性强：该方法基于图索引的通用搜索模式（距离轨迹），不仅适用于 HNSW，也适用于 Vamana 等其他图索引结构，具有广泛的适用性。
• 工业界落地：已在阿里巴巴大规模向量数据库集群中验证，并集成至开源项目，具有极高的实用价值。

总结：OMEGA 通过“一个模型解决所有 K"的范式，利用距离轨迹特征实现模型泛化，结合统计预测减少推理次数，成功在保持高召回率的同时，显著降低了向量搜索的延迟和预处理成本，是向量数据库领域的一项突破性进展。