[Paper] 受控自我进化用于算法代码优化

发布: 1周前 (2026年1月12日 GMT+8 17:23)

8 min read

原文: arXiv

Source: arXiv - 2601.07348v3

概述

本文介绍了 Controlled Self‑Evolution (CSE)，一种新框架，使大语言模型（LLMs）能够迭代改进它们为算法问题生成的代码。通过加入更智能的初始化、基于反馈的遗传算子以及过去尝试的层次记忆，CSE 在有限的计算预算内显著提升了发现更高效算法的能力。

多样化规划初始化 – 在开始时创建一组根本不同的算法策略，防止搜索陷入解空间的狭窄区域。
反馈引导的遗传进化 – 用有针对性的编辑和组合交叉取代盲目的随机突变，这些操作受验证信号（例如正确性、运行时间）的引导。
层次进化记忆 – 在两个层次（跨任务和单任务内部）存储成功和失败的尝试，并复用这些经验来指导后续代。
全面的实证验证 – 在新发布的 EffiBench‑X 基准上进行的大量实验显示，在多个 LLM 主干（如 GPT‑4、Claude‑2、LLaMA‑2）上相较于强基线有持续的提升。
开源发布 – 实现代码和基准套件已公开，可实现可复现性并促进进一步研究。

问题设置 – 每个任务都是算法编码挑战（例如，排序、图遍历）。目标是生成既正确又高效（低时间/空间复杂度）的代码。
生成‑验证‑改进循环 – 传统的自我进化重复三个步骤：生成候选代码、验证它（运行测试、测量性能），并根据结果进行改进。CSE 保持此循环，但升级每个组件。
多样化规划初始化
- 轻量级规划器生成若干高层次的算法“计划”（例如，分治 vs. 迭代）。
- 每个计划为一个独立种群提供种子，确保早期覆盖多样的解族。
带反馈的遗传进化
- 变异：CSE 不再进行随机 token 替换，而是针对验证器标记为瓶颈的特定程序结构（循环、递归深度、数据结构）进行变异。
- 交叉：从两个高性能候选中组合子例程，保持功能正确性的同时混合优化思路。
- 验证器提供一个适应度分数，该分数融合了正确性、渐进复杂度以及基准输入上的运行时间。
层次化进化记忆
- 任务间记忆：存储在不同问题中证明有用的模式（例如，“使用堆进行 top‑k 选择”）。
- 任务内记忆：记录每个任务的成功与失败，使系统能够避免重复无效的变异。
- 检索机制使得变异操作符的选择倾向于历史上产生改进的那些。

整个管线在固定的代数内运行，或直到性能出现平台期为止，同时保持在预定义的计算预算内。

Model / Baseline	Avg. Speed‑up vs. Original Code	Success Rate (≥ Correct & Efficient)	Generations to First Success
GPT‑4 + CSE	3.2×	87 %	2
Claude‑2 + CSE	2.9×	84 %	3
LLaMA‑2‑70B + CSE	2.5×	78 %	4
GPT‑4 + Standard Self‑Evolution	1.6×	61 %	6
Random Search	1.1×	45 %	—

开发者工具: 集成到 IDE 助手中，CSE 可以自动将天真的代码片段重构为更高性能的版本，从而节省开发者在手动优化上的时间。
自动化基准测试套件: 生成大型代码库的公司（例如自动生成的 API）可以将 CSE 作为后处理步骤运行，以在不进行人工调优的情况下满足严格的延迟或内存预算。
边缘与嵌入式系统: 对于资源受限的环境，CSE 能够发现低开销的算法，适配紧迫的运行时间或功耗限制，从而将 LLM 生成的代码推广到物联网设备。
教育平台: 学生可以看到从简单解法到最优解的多条演化路径，加深对算法设计模式的理解。
研究加速: 通过公开可复用的算法技巧记忆，未来的程序合成研究可以基于更丰富的知识库进行构建，而不必每次都从头开始。

验证成本： 对大规模输入进行准确的运行时间测量可能成本高昂；当前设置假设能够访问可靠的基准测试框架。
领域范围： 实验聚焦于经典算法问题；将 CSE 应用于 I/O 密集、外部 API 或非确定性行为的领域仍是一个未解的挑战。
内存管理： 随着任务数量的增加，层次化内存会增长；要扩展到数千个多样化问题可能需要剪枝或更复杂的索引机制。
未来方向： 作者提出 (1) 将 CSE 扩展到多目标优化（例如能耗 + 延迟），(2) 融合符号推理以在数学层面指导变异，(3) 探索持续学习设置，使记忆在产品发布之间演进。