Mathematical discoveries from program search with large language models (FunSearch)
这是什么
很多数学与组合优化问题'验证容易、求解难':给一个候选解,打分是多项式时间的,但找到好解极难。FunSearch 针对这类问题,不直接搜解本身,而是搜'生成解的程序':维护一个程序种群,反复让 LLM 读几个高分程序、写出改进版,由自动 evaluator 执行打分,分数高的存回种群。LLM 是冻结的(不做任何 fine-tune),只靠 API 采样;evaluator 负责挡掉幻觉和错误代码。
论文的卖点在于结果是'可验证的新知识':在 extremal combinatorics 的 cap set 问题上,FunSearch 找到的构造超过了人类已知最优,这排除了'LLM 只是背出训练数据'的解释。同时在 online bin packing 上进化出的启发式在 OR-Library 和 Weibull 基准上全面超过 first fit / best fit。作者强调搜程序而非搜构造还有两个附带好处:程序更短(相当于偏好低 Kolmogorov 复杂度的解,能 scale 到 20 多万个向量的实例)、更可读(数学家 Ellenberg 从进化出的代码里读出了一个此前未知的对称性,反过来收窄搜索空间进一步改进结果)。
这是 2023 年 12 月的 Nature 论文(无 arXiv 版),Google DeepMind 出品,作者含组合数学家 Jordan Ellenberg。截至 2026-08,Semantic Scholar 引用约 1239;它是后来 AlphaEvolve、OpenEvolve、ShinkaEvolve 这条 'LLM + 进化搜索程序空间' 路线公认的源头。
机制与做法
问题规格:evaluate + skeleton,只进化关键函数
用户提供三样东西:一个 evaluate 函数(给候选解打分)、一个初始程序(可以是平凡的常数函数)、以及一个 skeleton——包含样板代码和已知问题结构的'解题骨架'。FunSearch 只进化 skeleton 里最关键的那个函数。比如 cap set:skeleton 是一个贪心算法(从空集开始,每步加入 priority 最高且不违反约束的向量),进化的只是 priority: Z_3^n -> R 这个打分函数;bin packing 则进化'给每个 bin 打分'的 heuristic 函数。
作者明确说固定 skeleton 虽然限制了程序空间,但整体效果更好——LLM 的算力全部花在最难的核心逻辑上,而不是反复重写已知结构(重写还容易出错导致整个程序作废)。这个'把进化面收窄到一个函数'的设计后来被 AlphaEvolve 等继承。
![cap set 主结果(论文 Fig 4):(a) n=8 时 FunSearch 找到 512 元素 cap set,超过已知最优 496;(b) 进化出的 priority 函数只有几十行,其中'首尾对称位置'(el[i]==el[-i])的加权提示了 reflection 结构;(c) 人工从代码提炼出的显式构造。这张图是'搜程序比搜解可解释'论点的直接证据。](../figures/mathematical-discoveries-from-program-search/fig02_capset_512.png)
best-shot prompting + islands 进化
每次构造 prompt 时从 programs database 采 k=2 个程序,按分数升序命名为 priority_v0、priority_v1 拼进 prompt,末尾留一个空的 priority_v2 函数头让 LLM 补全——LLM 实际扮演 crossover 算子,从两个版本里找模式并泛化(k=2 优于 1,再多收益递减)。
多样性靠 islands model 维持:种群分成 m 个岛独立进化,每 4 小时淘汰最优个体分数最低的一半岛,用幸存岛的最优程序重新播种。岛内再按 signature(程序在各输入上的分数元组)聚类,采样时先按 Boltzmann 分布选簇(偏好高分),簇内偏好更短的程序——显式的短程序偏置就是'低 Kolmogorov 复杂度'归纳偏好的来源。
分布式系统与成本取舍
三类 worker 异步通信:programs database、samplers(调 LLM)、evaluators(沙箱执行打分)。典型配置 15 个 sampler + 150 个 CPU evaluator,单次实验总采样量在 10^6 量级。一个反直觉的工程结论:快而弱的模型胜过慢而强的模型——采样吞吐比单条质量更重要;并且结果对具体 LLM 不敏感,附录里用开源 StarCoder 也能跑出改进。
论文自己披露了成功率:admissible set I(12,7) 的实验 100% 超过旧的下界(60% 找到 full-size 集合),但 n=8 直接构造 512-cap 的实验只有 4/140 成功——头条结果是大量重复实验里挑出来的,论文在 Methods 里写明了这一点。
数学结果是怎么来的:人机回环
capacity 下界 2.2202 不是一步搜出来的:FunSearch 先找到一个生成 I(12,7) admissible set 的 priority 函数(下界 2.2180→2.2184);Ellenberg 读代码发现它把 12 个坐标按 4 组三元组对称处理,提炼出'symmetric admissible sets'这个此前未知的结构;然后把搜索空间限制到对称集合(空间小得多,能上更高维),FunSearch 在里面找到 I(15,10) 和一个 237,984 元素的 A(24,17) 部分可容集,推到 2.2202。
这个'机器给构造、人读代码提炼结构、再用结构收窄搜索'的循环是论文最有意思的部分,也是'搜程序而非搜解'的最强论据——如果输出是 20 多万个向量的列表而不是几行代码,对称性根本读不出来。
关键结果
- Cap set:n=8 维找到 512 元素的 cap set,超过已知最优 496,确立 c8 >= 512;n=3..7 均复现已知最优(9/20/45/112/236)。
- Cap set capacity 下界:2.2180 -> 2.2184(I(12,7))-> 2.2202(对称化后 I(15,10) 与 237,984 元素的 A(24,17)),论文称是该下界 20 年来最大改进(上界 2.756,差距仍很大)。
- Online bin packing(excess bins 相对 L2 下界,越低越好):OR1-4 上 FunSearch 5.30/4.19/3.11/2.47%,best fit 为 5.81/6.06/5.37/4.94%;Weibull 100k items 上 FunSearch 仅 0.03%,best fit 3.79%。启发式只在 OR1 规模上训练,能泛化到更大实例且差距拉大。
- 发现的启发式有可解释的共同策略:不总是塞最满的 bin,只有塞进去后'几乎填满'才用 best fit,否则留到更空的 bin——避免留下永远填不上的小缝隙。
- 结果对 LLM 选择不敏感(StarCoder 开源模型也能出改进),但对成功率敏感:512-cap 仅 4/140 实验成功;单次实验 ~10^6 samples,15 samplers + 150 CPU evaluators。
- 附带结果(补充材料):cycle graph 强积的独立集在 C9、C11 上超过已知最优,corners problem 也有新构造,但都未直接改进 Shannon capacity 估计。
实证核查
与我们方向的关系
这是本方向(ai4ai / 算法发现)的奠基条目:AlphaEvolve、OpenEvolve、ShinkaEvolve 的核心循环——LLM 变异 + 自动 evaluator + 种群多样性维护——全部在这篇里定型。读它主要是搞清三个设计决策的理由:(1) 只进化 skeleton 里的一个函数而不是整个程序;(2) islands + signature 聚类 + 短程序偏置这套多样性机制;(3) '快模型大采样量'优于'慢模型高质量',这条在 2023 年的模型上成立,AlphaEvolve 时代改成了强弱模型混采,值得对比。
对自己上手的提醒:FunSearch 只适合'evaluator 高效 + 打分信号连续(非 0/1)+ 关键逻辑可隔离成单个函数'的问题(论文 Discussion 自列的三条),定理证明这类二值反馈问题明确不适用;而且要对成功率有预期——头条结果是 140 次实验挑 4 次,复现建议从 jonppe/funsearch 或 OpenEvolve 起步而不是官方 repo(缺 LLM/沙箱组件)。