[arXiv 2025] AlphaEvolve：LLM 驱动的代码演化如何攻克 80 年前的数学难题？

TL;DR

最近，来自 Google 和名校的研究团队通过一种名为 AlphaEvolve 的 LLM 变异智能体，成功刷新了 5 个经典 Ramsey 数 的下界纪录（包括 $R(3,13)$ 和 $R(4,15)$ 等）。不同于以往数学家绞尽脑汁设计的算法，这次的“功臣”是一个能够自动写代码、改代码并自我进化的 AI 系统。

背景定位：这是组合数学领域的一次重要 SOTA 刷新。它证明了 LLM 在数学发现中扮演的最佳角色可能不是“答题者”，而是“高效算法的设计师”。

1. 组合数学的“圣杯”：Ramsey 数

Ramsey 数 $R(r,s)$ 是组合数学中最著名的难题之一。简单来说，它是寻找一个最小的节点数 $n$，使得在任何有 $n$ 个点的图中，要么存在一个大小为 $r$ 的团（全连通子图），要么存在一个大小为 $s$ 的独立集（全不连通子图）。

数学大师埃尔德什（Erdős）曾有个著名的比喻：如果外星人威胁地球要求我们在一年内算出 $R(5,5)$，人类或许能举全球算力勉强保住地球；但如果要算 $R(6,6)$，我们还是直接准备投降吧。

目前的学术痛点在于：

• 搜索空间巨大：图的组合可能性随节点数呈指数级爆炸。
• 算法碎片化：之前的下界通常是由不同的实验室通过高度定制化的启发式搜索（如模拟退火）得到的，缺乏标准化。

2. AlphaEvolve：进化的元搜索算法

AlphaEvolve 的核心直觉是：与其让 AI 找图，不如让 AI 找“找图的程序”。

架构解析

AlphaEvolve 维护了一个搜索算法种群。其工作流程如下：

1. 选择与变异：从种群中挑选表现好的代码片段，交给 LLM 进行突变。
2. 执行与评分：运行生成的算法。如果算法能生成符合条件的有效图，则给予高分；如果生成的图虽然违规但“接近成功”（即违规点很少），也会给予奖励分。
3. 反馈循环：将表现优异的代码重新加入种群，继续演化。

注：AlphaEvolve 不断尝试改进和扩展现有的代数结构。

3. 核心发现：AI 自发生成的“奇招”

通过分析生成的算法（如 Algorithm 2 到 Algorithm 29），研究者发现 AI 自发学会了许多高级策略：

• 代数引导（Algebraic Seeding）：AI 学会了先利用 Paley 图或 3 次剩余图等高度对称的数学结构作为起点，再进行局部随机微调。
• 哈希遗传内存（Harmonic Genetic Memory）：在 R(4, 15) 的搜索中，算法会记录哪些边或轨道在以往成功的图中频繁出现，并给予权重奖励。
• 自适应退火：根据违反约束的严重程度，动态调整温度系数。

提示：此处应展示论文中的关键战绩表，显示 R(3,13) 从 60 -> 61 等数据。

4. 实验结果：刷新纪录

AlphaEvolve 不仅找回了所有已知的精确 Ramsey 数下界，还取得了以下突破：

• $R(3,13)\ge 61$（原纪录 60）
• $R(3,18)\ge 100$（原纪录 99）
• $R(4,13)\ge 139$（原纪录 138）
• $R(4,14)\ge 148$（原纪录 147）
• $R(4,15)\ge 159$（原纪录 158）

这些提升虽然看似只有“+1”，但在 Ramsey 数领域，每一个数字的推进都往往需要间隔数年甚至数十年的计算努力。

5. 深度洞察与总结

为什么 AlphaEvolve 有效？ 传统的搜索算法往往陷入局部最优，或者由于人为设计的启发式逻辑过于死板，无法处理特定参数下的微妙结构。AlphaEvolve 的优势在于它能通过代码变异，并行探索数千种不同的启发式组合。它不仅在使用现有的数学工具（如循环图），还在发明定制化的、人类难以直观构思的复杂局部搜索逻辑。

局限性： 虽然在寻找下界（构造实例）上表现卓越，但该方法无法处理上界问题。证明上界需要逻辑证明或穷举证明该尺寸下不存在任何图，这依然是 AI 目前的短板。

启发： 这项研究预示着，未来科学研究的范式将转向：人类定义目标函数（Objective Function） -> AI 演化发现算法（Algorithms） -> 算法产出科学结论。

参考文献： Nagda, A., Raghavan, P., & Thakurta, A. (2025). Reinforced Generation of Combinatorial Structures: Ramsey Numbers. Working Paper.