基于代码图的预算高效自动算法设计

大语言模型（LLM）已成为自动算法设计（AAD）的强大工具。然而，现有流水线仍然低效。它们以完整算法为粒度运作，冗余地重写反复出现的子结构，并丢弃可能含有宝贵算法特征的低适应度候选。我们形式化了预算高效的自动算法设计：搜索策略在有限计算成本约束下最大化所实现的适应度。我们提出算法的有向无环图表示，并构建一个充分利用LLM输出的搜索框架。我们不向LLM查询完整算法，而是用其获取修正：添加、替换或移除代码块的紧凑算子。每个修正都会扩展该图，产生可与先前修正组合的新算法。这种图结构将算法分解为修正的集合，实现修正级别的贡献归因，为后续查询提供依据。我们还以理论洞见补充该框架，阐明不同预算水平下搜索深度与广度之间的理想平衡。我们在三个组合优化问题上进行实证验证，表明在相同token预算下，基于图的搜索始终优于完整算法搜索。最后，我们的实验表明，只有当LLM的先验知识薄弱时，丰富上下文才有帮助，否则反而可能损害性能。