Budget-Efficient Automatic Algorithm Design via Code Graph

📄 arXiv: 2605.10598v1 📥 PDF

作者: Maxime Bouscary, Manxi Wu, Saurabh Amin

分类: cs.AI

发布日期: 2026-05-11

💡 一句话要点

提出基于代码图（Code Graph）的自动算法设计框架，通过增量式修正实现预算高效的算法搜索。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 自动算法设计 大语言模型 有向无环图 组合优化 代码生成 计算效率

📋 核心要点

  1. 现有AAD方法以完整算法为搜索粒度，存在重复重写子结构及浪费低适应度候选方案中潜在价值的问题。
  2. 提出基于有向无环图（DAG）的算法表示，通过LLM生成增量式代码修正算子，实现算法的模块化演进与组合。
  3. 在组合优化任务中，该方法在同等Token预算下显著优于全算法搜索，并揭示了上下文信息与模型先验知识的权衡关系。

📝 摘要（中文）

大语言模型（LLM）已成为自动算法设计（AAD）的有力工具，但现有流程效率低下。它们通常以完整算法为粒度进行操作，导致重复重写通用子结构，并丢弃了可能包含有价值算法特征的低适应度候选方案。本文形式化了预算高效的自动算法设计问题，旨在有限计算成本下最大化搜索策略的适应度。我们提出了一种算法的有向无环图（DAG）表示，并构建了一个充分利用LLM输出的搜索框架。该方法不直接查询完整算法，而是利用LLM生成“修正”：即添加、替换或删除代码块的紧凑算子。每个修正都会扩充图结构，产生与先前修正组合的新算法。这种图结构将算法分解为修正集，实现了基于修正的信用分配，从而指导后续查询。此外，我们从理论上探讨了不同预算水平下搜索深度与广度的平衡。在三个组合优化问题上的实验表明，在相同Token预算下，该方法优于全算法搜索。研究还发现，丰富的上下文仅在LLM先验知识匮乏时有效，否则可能适得其反。

🔬 方法详解

问题定义：论文旨在解决自动算法设计中计算资源利用率低的问题。现有方法将算法视为不可分割的整体，导致LLM在每次迭代中重复生成冗余代码，且无法有效利用搜索过程中产生的中间算法片段。

核心思路：引入代码图（Code Graph）表示法，将算法视为一系列增量修正的组合。通过将搜索空间从“完整算法”降维至“代码修正算子”，实现对算法结构的精细化控制与复用，从而在有限的Token预算下最大化搜索效率。

技术框架：框架包含三个核心模块：算法图构建器、修正生成器（LLM）以及基于图的搜索策略。搜索过程通过对当前算法图应用修正算子（添加、替换、删除代码块）来生成新候选，并利用图结构进行信用分配，指导后续的搜索方向。

关键创新：核心创新在于将算法演化过程建模为有向无环图（DAG），实现了算法层面的模块化分解。这种表示允许系统保留并重用高质量的算法子结构，避免了全量重写带来的计算浪费。

关键设计：设计了基于修正的信用分配机制，根据修正对适应度的贡献更新搜索策略。此外，通过理论分析确定了在不同计算预算约束下，搜索深度（修正链长度）与搜索广度（分支数量）的最优平衡点，并验证了上下文窗口大小对LLM性能的非线性影响。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在三个组合优化基准测试中，该方法在同等Token预算下表现出显著优于全算法搜索的性能。实验数据表明，基于图的增量式搜索能更有效地收敛至高质量算法，且研究揭示了当LLM具备较强先验知识时，精简上下文反而能提升搜索效率的现象。

🎯 应用场景

该方法适用于组合优化、启发式算法设计及自动化软件工程领域。通过高效利用计算资源，它能显著降低复杂算法自动生成的成本，特别是在需要探索大规模算法空间且计算预算受限的工业场景中具有极高的应用价值。

📄 摘要（原文）

Large language models (LLMs) have emerged as powerful tools for automatic algorithm design (AAD). However, existing pipelines remain inefficient. They operate at the granularity of full algorithms, redundantly rewriting recurring substructures and discarding low-fitness candidates that may contain valuable algorithmic features. We formalize budget-efficient automatic algorithm design, wherein the search policy maximizes realized fitness subject to limited computational cost. We propose a directed acyclic graph representation of algorithms and build a search framework that fully exploits the LLM's output. Instead of querying the LLM for full algorithms, we use it to obtain corrections: compact operators that add, replace, or remove code blocks. Each correction augments the graph, yielding new algorithms that compose with prior corrections. This graph structure decomposes algorithms into sets of corrections, enabling correction-level credit assignment that informs subsequent queries. We complement this framework with theoretical insights into the ideal balance between search depth and breadth at different budget levels. We validate our method empirically on three combinatorial optimization problems, demonstrating consistent superiority of our graph-based search over full-algorithm search at equal token budget. Finally, our experiments suggest that rich contexts help only when the LLM's prior knowledge is shallow, and can hinder performance otherwise.