💬 NLP

CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

本文介绍了 CRINN，这是一种利用对比强化学习来自动生成高性能近似最近邻搜索算法的新范式，通过在保持准确性的同时优化执行速度，在多个基准测试中实现了最先进的结果，并展示了大语言模型在自动化复杂算法优化方面的潜力。

原作者： Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

发布于 2026-07-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你拥有一个拥有数十亿本书籍的巨大图书馆，而你需要找到一本听起来最像你刚刚输入的那句话的书。在计算机世界中，这被称为“近似最近邻搜索”（Approximate Nearest Neighbor Search，简称 ANNS）。它是许多酷炫技术背后的引擎，比如能记住你过去对话内容的 AI 聊天机器人，或者能寻找相似图像的机器人。但问题在于，在数十亿本书的图书馆里寻找那本完美的书是非常缓慢的。如果你检查每一本书，会耗费极长的时间。因此，计算机科学家们构建了一些“智能捷径”，通过牺牲极小部分的准确性来换取巨大的速度提升。

多年来，让这些捷径变得更快一直是仅靠人类完成的工作。这就像是在调校赛车的引擎：一位专家技师必须倾听引擎的声音，猜测哪个部件在拖后腿，在这里拧一下螺丝，在那里换一个齿轮，然后再次测试。这需要深厚的知识和极大的耐心。

于是，CRINN 诞生了，它提出了一个宏大的问题：我们能否教会一个 AI 来亲自调校这个引擎？

拥有超能力的机器人技师

CRINN 是一个“强化学习”框架。你可以把它想象成一个机器人技师，它不只是靠猜测，而是通过玩游戏来学习。这个游戏很简单：编写一段用于搜索图书馆的代码，运行它，然后观察它的速度有多快。

奖励： 如果代码找到书籍的速度很快，机器人就会获得高分。
教训： 机器人会将它的新代码与旧代码进行比较。它不仅仅看分数，还会观察为什么其中一个更快。是因为它跳过了某个步骤吗？还是因为它更好地组织了书籍？
循环： 机器人利用这种比较来编写下一个更快的版本。它不断重复这个过程，随着每一次尝试变得越来越聪明、越来越快。

论文显示，这个机器人技师在工作中表现得极其出色。在六种不同类型的“图书馆”（数据集范围从数字图像到词向量）进行测试时，CRINN 构建的搜索系统在其中三个数据集（GIST-960、MNIST-784 和 GloVe-25）上达到了世界最快，并在另外两个数据集（SIFT-128 和 GloVe-25）上并列第一。

它如何学会获胜

其核心秘诀被称为对比强化学习（Contrastive Reinforcement Learning）。想象一下，机器人被给予两个版本的代码片段：一个运行时间为 1 秒，另一个为 2 秒。机器人被要求解释为什么第一个更快。它可能会注意到：“啊，快速的那个一次检查三本书，而慢的那个一次只检查一本。”通过学习这些模式，机器人开始编写自然包含这些提速技巧的代码。

研究人员并没有让机器人随机猜测。他们给了它一个明确的目标：寻找速度与准确性之间的最佳平衡点。他们使用每秒查询数（QPS）——即系统在一秒钟内可以进行多少次搜索——来衡量性能，同时保持较高的召回率（recall）。例如，在 MNIST 数据集（手写数字）上，在保持极高准确度（0.999 召回率）的情况下，CRINN 比之前的最优系统快了 85.25%。这是一个巨大的飞跃！

“一劳永逸”的惊喜

这里是最有趣的地方。机器人的训练仅使用了一种类型的图书馆：SIFT-128 数据集，它使用一种特定的距离测量方式，即“欧几里得距离”（就像在地图上测量直线距离）。你可能会想：“如果我用轿车训练一名技师，他可能不会修理摩托车。”

但论文发现，CRINN 在欧几里得距离上的训练在“角度距离”（Angular distance）数据集（如 GloVe 词向量）上也表现得惊人地好，尽管两者在数学上是不同的。这表明机器人学到了适用于规则略有变化的通用速度原则。然而，论文也指出了一个明显的界限：当在 NYTimes-256 数据集上进行测试时，CRINN 的表现实际上比现有的最优系统差了 82.85%。这告诉我们，虽然这个机器人是个天才，但它并非神话；面对与其学习内容差异极大的数据类型时，它仍然会感到吃力。

循序渐进的升级

研究人员并没有直接把机器人扔向整个问题，而是将搜索过程分解为三个阶段，就像分阶段升级汽车一样：

构建地图（图构建/Graph Construction）： 这是组织图书馆的阶段。CRINN 在这一阶段的提升最为显著，平均提升了 22.11% 的速度。它学会了使用“自适应搜索”，这意味着它只在真正需要时才投入更多精力寻找书籍，并使用了“多入口点”，允许它同时从多个门口开始寻找。
搜索地图（搜索/Search）： 地图构建完成后，你需要找到那本书。CRINN 通过“批处理”（同时检查一组书籍）和“提前终止”（一旦确定找到了最佳匹配就停止搜索）等技巧，将这一阶段的效率提升了 18.30%。
完善结果（精炼/Refinement）： 确保答案完美的最后一步。这一步带来的提升较小，为 9.67%，因为在这个阶段已经没有什么太大的改进空间了。

这意味着什么

论文认为，CRINN 证明了一个强大的观点：AI 可以实现复杂、专家级任务的自动化。 数十年来，让这些搜索算法变得更快需要经过多年训练的人类专家。现在，一个通过比较自身代码来进行学习的系统可以自动完成这项工作。

作者谨慎地表示，这并不是针对所有数据集都已解决的问题（如 NYTimes 的结果所示），但这是向前迈出的重要一步。他们指出，随着 AI 应用（如“检索增强生成”，即 AI 利用外部知识来回答问题）变得越来越流行，像 CRINN 这样的工具对于在无需人工微调每个设置的情况下保持高效运行将至关重要。

简而言之，CRINN 是一个学会了成为数据搜索领域“大师级技师”的机器人，它证明了通过正确的训练，机器不仅可以编写代码，还能找出如何让代码运行得比人类还要快的方法。

技术摘要：CRINN

问题陈述

近似最近邻搜索（ANNS）是现代 AI 应用的关键组成部分，特别是对于检索增强生成（RAG）和基于智能体（agent-based）的大语言模型（LLM）系统，这些应用需要从海量向量数据库中进行快速检索。虽然现有的开源 ANNS 解决方案（如 FAISS、DiskANN、ParlayANN）依赖于像 HNSW（分层可导航小世界图）这样强大的骨干网络，但其优化过程在很大程度上仍是一个高度依赖人工的过程。这一过程需要具备计算机体系结构、并行编程和算法特性的深厚专业知识，以识别瓶颈、调整参数（如图度数和搜索束宽）并设计具有内存局部性的数据结构。本文指出，这种手动精炼过程不仅耗时费力，同时也提出了一个问题：是否可以通过增强了强化学习（RL）的大语言模型（LLM），来自动化地生成并测试算法改进方案，从而发现人类工程师可能忽略的优化模式。

方法论

作者提出了 CRINN（用于近似最近邻搜索的对比强化学习），这是一个将 ANNS 优化视为强化学习问题的框架，其中执行速度被作为奖励信号。

核心框架

CRINN 利用对比强化学习模型对 ANNS 算法进行模块化优化（具体针对 HNSW 骨干网络中的图构建、搜索和精炼阶段）。该过程包括：

对比提示（Contrastive Prompting）： LLM 会接收到一个包含先前代码实现及其执行得分的提示词。模型被指示进行对比分析，以识别为什么某些实现优于其他实现，从而区分有效策略与无效策略。
迭代生成： 基于这种分析，LLM 合成新的代码变体。
奖励信号： 生成的代码会被执行，并根据性能计算奖励。为了解决由于 QPS（每秒查询数）与召回率（Recall）之间的权衡而导致的 ANNS 算法难以比较的问题，作者采用了一种特定的评估策略：
- 通过改变搜索参数 $ef$ 来生成一组 (QPS, recall) 点集。
- 他们过滤出处于 $[0.85, 0.95]$ 召回率范围内的点，这是一个“甜点区”，在此区间内大多数算法都有足够的数据，且性能差异具有显著意义。
- 奖励被定义为由这些过滤后的点形成的曲线下面积（AUC），从而为 RL 目标提供一个标量值。
训练算法： 系统采用了群体相对策略优化（GRPO）。对于每个输入提示，模型生成一组代码补全。奖励在组内进行归一化，并通过更新策略来最大化生成高奖励代码的可能性，同时保持一个针对参考策略偏离过远的约束（KL 散度）。

实现细节

基准（Baseline）： 该框架使用 GLASS 作为初始起点，这是一个基于图的 ANNS 库，并按顺序优化其各个组成模块。
训练数据： RL 模型仅在 SIFT-128-Euclidean 数据集上进行训练，以保持单一的可泛化代码库。
输出结构： LLM 被约束为输出包含“性能分析”、“算法设计”和“代码实现”的结构化响应。

核心贡献

自动化优化范式： CRINN 引入了一种全新的范式，即通过 RL 增强的 LLM 实现 ANNS 优化的自动化，消除了对人工、专家驱动型调优的需求。
对比学习机制： 通过将示例代码和执行指标直接集成到提示词中，模型能够通过直接比较而非仅仅依靠试错，来学习关于性能关键模式的推理。
奖励工程： 本文通过利用特定且实用的召回率范围（ $[0.85, 0.95]$ ）内的 QPS-recall 曲线 AUC，解决了定义 ANNS 标量奖励的挑战，从而实现了不同离散参数设置下的公平比较。
渐进式优化： 系统证明了对不同模块（图构建、搜索、精炼）进行顺序优化可以产生累积性的性能提升。

实验结果

作者在六个广泛使用的基准数据集上对 CRINN 进行了评估：SIFT-128、GIST-960、MNIST-784、GloVe-100、GloVe-25 和 NYTimes-256。

性能表现： CRINN 在三个数据集上达到了顶尖水平（GIST-960-Euclidean、MNIST-784-Euclidean 和 GloVe-25-angular），并在另外两个数据集上并列第一（SIFT-128-Euclidean 和 GloVe-25-angular）。
定量收益：
- 在 MNIST-784 上，与最佳基准（ParlayANN）相比，CRINN 在 0.999 召回率下的 QPS 提升高达 85.25%。
- 在 GIST-960 上，它在 0.99 召回率下实现了 72.68% 的提升。
- 在 SIFT-128（训练数据集）上，不同召回率水平下的提升范围为 +3.25% 到 +25.57%。
局限性： 在 NYTimes-256（一个角度距离数据集）上，CRINN 在 0.9 召回率时的表现比最佳基准低 82.85%。作者将其归因于模型仅在欧氏距离数据上进行训练，这表明角度相似性的优化模式可能存在显著差异。
模块贡献： 图构建模块产生的个体增益最为显著（平均 +22.11%），其次是搜索（+18.30%）和精炼（+9.69%）。

意义与主张

本文声称，CRINN 的成功意义已超越了针对特定 ANNS 算法的优化本身。它验证了通过强化学习增强的 LLM 可以作为有效的工具，实现复杂的算法优化自动化，而这类优化传统上需要专门的领域知识和耗时的人工精炼。

作者认为，随着 RAG 和基于智能体的 LLM 应用的激增，对高效向量搜索的需求不断增长，像 CRINN 这样的框架对于在不断演进的硬件架构和应用需求中保持竞争性能将变得愈发重要。这项工作证明，自动化系统不仅可以匹配、甚至在特定语境下可以超越人类工程设计的最先进解决方案。