arXiv · AI· Per Kristian Lehre·· 1 天前AI 评分49
首个自动化管线在 Lean 中设计进化算法并机器验证其运行时界
Agentic Algorithm Design: LLMs that Propose, Formalise, and Prove Runtime Bounds for Evolutionary Algorithms in Lean
AI 导读
首个自动化管线实现了 LLM 设计黑盒优化算法,并在 Lean 中完成其预期运行时的机器验证。 Agent 针对 CycleUncover 问题提出了 $O(n^2)$ 算法,优于基线的 $e^{\Omega(n)}$;在 8 个问题类中,15 次运行有 12 次成功产出有效证明。 消融实验表明分阶段方法优于零样本生成,Lean 规范可替代开放式算法发现的实证评估。
来源:arXiv · AI · arxiv.org