🤖 machine learning

LLM Program Optimization via Retrieval Augmented Search

本文介绍了检索增强搜索（RAS）和 AEGIS，这两种新颖的黑盒自适应方法利用大语言模型生成的自然语言描述和原子编辑，在优化 C++ 和 Python 程序的同时，显著超越了最先进的策略，并增强了可解释性且减少了代码改动。

原作者： Sagnik Anupam, Alexander Shypula, Osbert Bastani

发布于 2026-06-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Sagnik Anupam, Alexander Shypula, Osbert Bastani

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

想象你有一位非常有才华但缺乏经验的大厨（即大语言模型，简称 LLM），他正试图烹饪一顿美餐。目标不仅仅是让食物味道好，还要让它在不改变口味的前提下，烹饪得更快。

这篇论文提出了两种新的方法来帮助这位大厨更聪明地工作，利用一个“过去食谱的图书馆”（一个包含“慢速代码 vs 快速代码”的数据集）来引导他们。

问题所在：大厨卡住了

通常情况下，如果你要求这位大厨加速某道菜的烹饪过程，他可能会随机猜测，或者尝试一次性重写整个食谱。由于他没有见过足够多的关于“如何让事情变快”的具体案例，他经常会失败。他需要一位教练来展示具体的技巧。

方法 1：RAS（检索增强搜索）

类比：“智能图书管理员” vs. “关键词搜索”

想象大厨需要在庞大的图书馆中寻找类似的食谱以获取灵感。

旧方法（代码检索）： 大厨查看当前菜肴的食材清单（实际的代码），并在图书馆中搜索具有相似食材的食谱。这就像是搜索“面粉和鸡蛋”，结果却得到了一份蛋糕食谱，而你实际上需要的是一份恰好也用了面粉和鸡蛋的汤品食谱。这太过于字面化了。
新方法（上下文检索）： 大厨先请图书管理员为这道菜写一个摘要（例如：“这是一道通过慢炖蔬菜来提取风味的汤”）。然后，图书管理员会在图书馆中寻找其他执行相同功能的菜肴，而不论其具体食材是什么。
- 为什么有效： 它能找到解决相同问题的食谱，而不仅仅是那些在纸面上看起来相似的食谱。

搜索过程（束搜索/Beam Search）：
RAS 并没有要求大厨一步到位地完成对食谱的改进，而是将其分解：

大厨做出一个小改进。
图书管理员根据这个新版本找到一个新的、相关的示例。
大厨利用那个新示例再次尝试。
他们重复这个循环，就像一步步爬山一样，始终选择上升最快的路径。

结果： 这种方法使 C++ 程序运行速度提升了高达 2 倍，并显著提高了 Python 程序的运行速度。

方法 2：AEGIS（原子级编辑引导搜索）

类比：“乐高大师” vs. “拆迁队”

即使有了聪明的图书管理员，大厨可能仍然会做出巨大且令人困惑的改动（比如更换整个烹饪方式）。这很难理解且风险很高。

AEGIS 改变了图书馆本身。它不再存储完整的“慢速 vs 快速”食谱对，而是将它们分解为原子级编辑（Atomic Edits）。

过程： 系统获取一个慢速食谱和一个快速食谱，并请专家解释其中的细微差别，将其分解为极小的、单一的步骤。
- 第 1 步： “将木勺换成金属勺（热传导更快）。”
- 第 2 步： “把洋葱切得更碎（烹饪更快）。”
- 第 3 步： “使用锅盖来锁住蒸汽。”
泛化： 然后，它将这些步骤改写为通用的规则（例如，“针对高温使用金属器具”），以便可以将这些规则应用于任何食谱，而不局限于某一道特定的菜。

如何提供帮助： 当大厨需要优化一道新菜时，系统不会说“这是另一份完整的食谱”。它会说：“这是一个具体的、微小的技巧：‘换成金属勺’。试试看。”大厨应用一个微小的技巧，检查结果，然后尝试下一个。

结果：

它使改动变得更小且更容易理解（就像更换一个乐高积木，而不是重建整座城堡）。
与第一种方法相比，它将改动的大小减少了 17% 到 30%。
虽然它的运行速度略低于第一种方法，但它在速度方面依然表现出色，并且拥有更高的可控性和清晰度。

结果总结

RAS 就像是一位聪明的教练，通过一系列有信息的微小步骤引导你，寻找通往更快程序的最佳路径。它使 C++ 的速度提升了 2 倍，并使 Python 的平均速度提高了 10%。
AEGIS 就像是一位将问题分解为微小、易处理的乐高积木块的教练。它在效率方面提升了 1.37 倍，并使编辑变得更小、更安全，确保程序在尝试变快的同时不会出错。

简而言之，这篇论文告诉我们，要让 AI 代码变快，我们不应该只是让它去“猜测”。我们应该给它一位理解代码“故事”的图书管理员（上下文检索），以及一套用于进行一个个微小、安全改进的特定工具（原子级编辑）。

技术摘要：通过检索增强搜索实现 LLM 程序优化

问题陈述

大语言模型（LLMs）在代码生成方面展现了显著潜力，但在程序优化方面表现欠佳。传统的训练数据集缺乏足够的程序性能数据，使得直接适配变得困难。虽然最近的研究（Shypula 等人，2024）引入了“性能改进编辑”（PIE）基准，并证明了动态代码检索（基于代码嵌入相似度检索“慢-快”程序对）可以提升性能，但现有方法仍然是“端到端”的。它们要求 LLM 根据少量示例直接输出优化后的版本。这与现代编译器不同，后者通过一系列增量过程系统地修改程序。此外，端到端方法往往会产生巨大且难以解释的改动。

方法论

本文提出了两种主要方法来解决这些局限性：检索增强搜索（RAS）和原子编辑引导搜索（AEGIS）。

1. 检索增强搜索 (RAS)

RAS 是一种黑盒适配方法，它在候选优化方案上执行束搜索（beam search），并整合了两个关键见解来改进动态检索：

上下文检索： RAS 不再基于原始源代码检索示例，而是使用 LLM ( $F_{context}$ ) 生成程序核心算法和数据结构的自然语言描述。随后将该描述进行嵌入（ $\psi$ ），以检索最相关的“慢-快”训练对。作者假设这种抽象化使得系统能够基于意图和逻辑而非表面的语法相似性来检索示例。
迭代束搜索： RAS 不仅仅是检索一次固定的示例集，而是执行一个“检索-优化-评估”的循环。在每一步 $i$ ，给定当前程序 $p_{i-1}$ ，系统根据上下文嵌入检索出与 $p_{i-1}$ 最相似的前 $k$ 个训练对。LLM ( $F_{opt}$ ) 随后生成 $k$ 个候选优化方案。系统选择最快的正确程序作为 $p_i$ ，并重复该过程 $m$ 步。

2. 原子编辑引导搜索 (AEGIS)

为了解决大规模、单体式改动带来的可解释性问题，AEGIS 引入了一个预处理步骤，将训练示例分解为“原子编辑”。

分解： LLM ( $F_{decomp}$ ) 分析一个“慢-快”程序对 $(p, p')$ ，并将该转换分解为一系列自然语言描述 $[s_1, ..., s_r]$ ，其中每个 $s_i$ 解释了一个特定的增量变化及其性能原理。
生成与泛化： 系统使用 LLM ( $F_{edit}$ ) 将每个描述 $s_i$ 顺序应用于慢速程序，以生成中间程序。然后，泛化 LLM ( $F_{gen}$ ) 将每个具体的编辑描述重写为适用于更广泛程序的通用“原子编辑” $e_i$ 。
基于原子编辑的搜索： 生成的数据集 $\Pi_{atomic}$ 由元组 $(e_i, (p_{i-1}, p_i))$ 组成。随后在这一数据集上运行 RAS，其中的检索步骤寻找最相关的原子编辑，并提示 LLM 将该特定增量编辑应用于当前程序。这强制优化过程更加增量化且具有可解释性。

核心贡献

上下文检索的优越性： 本文证明，基于 LLM 生成的自然语言描述进行检索，其效果显著优于基于原始源代码嵌入的检索。这表明，通过抽象算法意图对于有效的少样本学习（few-shot learning）至关重要。
RAS 框架： 作者提出了 RAS，它将上下文检索与迭代束搜索相结合。该方法将优化视为一个序列搜索问题，而非单步生成任务。
用于可解释性的 AEGIS： 本文引入了 AEGIS，一种将训练数据提炼为原子化、可泛化编辑的方法。这使得系统能够在保持性能增益的同时，以更小、更具可解释性的步骤进行优化。
全面的评估： 研究在 PIE 基准（C++）和 Mercury 基准（Python）上对方法进行了评估，并与包括动态检索、仅指令提示以及人类表现水平在内的最先进基准进行了对比。

结果

C++ 优化 (PIE 基准)

RAS 性能： 使用 Qwen3-Coder，RAS 实现了 8.70× 的平均加速比，而之前的最先进动态检索基准为 4.23×。这代表了相对于基准的 2.06× 提升。
AEGIS 性能： 使用 GPT-4o，AEGIS 实现了 6.08× 的平均加速比。虽然略低于实现更高加速比的特定模型下的完整 RAS，但 AEGIS 产生的编辑规模明显更小。
编辑规模： 与使用 GPT-4o 的 RAS 相比，AEGIS 将平均编辑规模（以字符串编辑距离衡量）降低了 17%；在仅考虑搜索过程中的第一次编辑时，降幅达 30%。
准确率： 在 GPT-4o 实验中，RAS 保持了 99.5% 的准确率（程序通过所有测试用例），而 AEGIS 达到了 100%。通过对 DeepSeek 3.2 输出的一个子集进行 CBMC 形式化验证，确认了 10 个案例中有 8 个在语义上是等价的，其余 2 个仅在微小的格式（换行符）上存在差异。

Python 优化 (Mercury 基准)

使用带有 Qwen2.5-7B-Instruct 的 RAS，其平均运行时百分位数指标（Beyond@1）比基准提升了 10.27，显著缩小了该模型与大型推理模型之间的性能差距。

意义与主张

本文声称，通过检索增强搜索将程序优化分解为增量步骤，可以显著提高 LLM 进行代码优化的能力。作者强调，上下文检索（使用自然语言描述）是超越基于代码检索的关键因素。此外，他们认为 AEGIS 提供了一条通过强制增量变化来使 LLM 驱动的优化更具可解释性和更安全的有效路径，且不会损失实质性的性能增益。这项工作将这些黑盒适配策略定位为一种实用的替代方案，可以取代微调，利用现有的“慢-快”对训练数据集在程序优化方面达到最先进的结果。