arXiv 论文提出 Agentic Algorithm Design:LLM 在 Lean 中设计进化算法并证明运行时界
Per Kristian Lehre 等提出分阶段管线,让智能体提出黑盒优化算法,用 Lean 证明期望运行时界并过滤缺陷设计。智能体给出的算法在 CycleUncover 问题达 O(n²),而经典 (1+1) EA 需 e^Ω(n);在 8 个问题类上,15 次运行中 12 次用前沿模型完成机器验证的运行时证明,消融显示去掉分阶段会导致照抄基线或证明不完整。
推荐理由:论文展示了分阶段管线让智能体在 Lean 中机器验证算法运行时证明,为无实证评估的开放式算法发现提供了可检验的替代路径。