ShinkaEvolve: Towards Open-Ended and Sample-Efficient Program Evolution
这是什么
AlphaEvolve(DeepMind, 2025)证明了'LLM 当变异算子 + 进化搜索'能发现超越人类的算法,但它闭源、且单个任务动辄消耗上千到上万次程序评估。ShinkaEvolve(shinka 是日语'進化')是 Sakana AI 对这条路线的开源回应,目标直指两个痛点:样本效率和可用性。作者是 Robert Lange、Yuki Imajuku、Edoardo Cetin 三人,2025 年 9 月放出 arXiv 和代码,后被 ICLR 2026 接收。
框架本体是一个进化循环:维护若干 island 子种群的程序 archive,每代采样 parent + inspiration 程序塞进 prompt,让一个 LLM ensemble 提出 diff / full rewrite / crossover 三种变异,通过新颖性过滤后执行评估,把 fitness、公开指标和文本反馈写回 archive。用户只需要提供 initial.py(用 EVOLVE-BLOCK 标记可变异区域)和 evaluate.py(verifier),适用于一切'有可自动打分的 verifier'的任务。
论文在四个差异很大的任务上做了演示:circle packing 数学构造、AIME 数学推理的 agent scaffold 设计、ALE-Bench 组合优化编程赛、以及 MoE 负载均衡损失(LBL)的发现——最后一个是直接'用 AI 改进 AI 训练组件'的案例,发现的新损失项迁移到 2.7B 模型 30B token 训练上仍然一致优于 Qwen3 用的 global-batch LBL。
机制与做法
Parent 采样:在探索和利用之间做概率插值
Archive 按 island 组织(独立子种群 + 偶尔迁移,最优个体不迁移以保护多样性),每代先均匀抽一个 island,再从中选 parent。核心是 weighted sampling:性能项用 sigmoid(λ·(fitness − 种群中位数)),新颖性项用 1/(1+后代数),两者相乘作为采样权重——分数高且还没被反复挖掘过的程序优先当 parent。备选还有 power-law 排名采样(α=0 退化为均匀,α→∞ 退化为 hill climbing)。消融显示 weighted sampling 全程稳定爬升,hill climbing 起得快但很快平台期,best-of-N 最差。
新颖性拒绝采样:不浪费评估预算在重复程序上
LLM 提出的变异先不急着执行:把可变异代码段用 embedding 模型(text-embedding-3-small)编码,和 island 内已有程序算余弦相似度,超过阈值(0.95)就再让一个便宜 LLM 当 novelty judge 判断是否'实质不同',不新颖就拒绝重采。消融里这是收益最大的组件之一:embedding 拒绝采样对比不做拒绝提升显著,LLM judge 在其上只有边际增益。评估很贵、LLM proposal 相对便宜,这一步是样本效率的主要来源。
Bandit 动态选 LLM + meta-scratchpad
变异模型从一个池子(如 gpt-4.1、claude-sonnet-4、o4-mini、gemini-2.5 系)里选,用改造过的 UCB1 在线调整各 LLM 的采样概率:reward 不用绝对 fitness,而是 exp(max(r − baseline, 0)) − 1,baseline 取 parent 和初始程序的较高者——只奖励真正带来改进的模型,且 exp 放大鼓励'高风险高回报'的大胆变异而非安全的小修小补。
每 T 代跑一次 meta-agent,总结近期成功程序的共性策略,生成'实施建议'附到后续变异 prompt 里,相当于把进化过程中的经验蒸馏成显式知识。执行反馈除标量 fitness 外还包括公开指标和文本反馈(text_feedback),都进 prompt 上下文。
四个任务的实验设置
Circle packing(26 圆放进单位方,最大化半径和):跑 150 代,fitness 用 OpenEvolve 的 verifier(容 1e-6 数值 slack);发现的解组合了黄金角螺旋初始化 + SLSQP 梯度精修 + 模拟退火全局扰动。AIME 2024:进化 agent scaffold,基座 gpt-4.1-nano、每题限 10 次 LLM 调用、75 代,每个候选跑 3 遍全卷。ALE-Bench LITE:以 ALE-Agent 的最优解为初始程序,50 代,public test 分数当 fitness。MoE LBL:在 556M 参数(64 专家选 8)、2B token fineweb 预训练上进化 30 代,fitness = 最终 CE + 负载不均衡度,然后把最优损失迁移到 2.7B/30B token 验证。
关键结果
- Circle packing:约 150 次程序评估达到 2.635983(slack verifier),把每个半径缩 1e-8 后严格可行、和为 2.6359828,略超 AlphaEvolve;对照组 OpenEvolve 约 460 次评估只到 2.63543,LLM4AD 用约 10^4 次评估到 2.63594。论文图中整个 run 的累计 API 成本约 12 美元。
- AIME 2024:进化出'3 个不同 persona 专家并行解题(temp 0.7)→ 各自被低温(0.1)审稿人批判 → 主编(temp 0)合成'的 7-call scaffold,明显超过 majority voting 基线;迁移到 AIME 2025 增益更大(2023 增益小,作者归因于训练数据污染),换 gpt-4.1-mini/gpt-4.1/o4-mini 基座仍有效。
- ALE-Bench LITE:在 ALE-Agent 最优解基础上平均再提升约 2.3%(10 个任务);ahc039 从'假想排名'第 5 提到第 2(AtCoder 榜 2880→3140)。作者自己承认改进多是实现层面的,算法上贴着初始解走,有过拟合初始化之嫌。
- MoE LBL:发现的损失 = global-batch LBL + 一个熵加权的最低使用率惩罚项(对 token 分配低于阈值 τ=0.064/N_E 的'半死专家'施加梯度、且在路由熵低时加强),迁移到 2.7B 模型、30B token、三档 λ 下 perplexity 和 7 个下游基准一致占优,λ 越大差距越大。
- 消融(circle packing 上):三个组件都有贡献,weighted parent sampling > hill climbing > best-of-N;bandit LLM ensemble > 固定均匀 ensemble > 单 LLM;embedding 拒绝采样贡献显著,LLM-novelty-judge 只有边际增益。
- 外部战绩与采用度:支持 Team Unagi 拿下 ICFP 2025 编程赛冠军;S2 引用 140,GitHub 1361 stars,ICLR 2026 接收;仓库到 2026-08 仍在活跃开发(PyPI 包、文档站、Claude Code/Codex agent skills、W&B 集成)。
实证核查
与我们方向的关系
对 ai4ai / 算法发现方向,这是目前最值得直接上手的开源 evolutionary coding harness:与 AlphaEvolve(闭源)和 OpenEvolve(社区复刻)相比,它的三个机制——novelty 拒绝采样、UCB1 动态选 LLM、性能×新颖性加权的 parent 采样——都有消融支撑,而且都是可以单独摘出来用在自己搜索系统里的组件。'评估贵、proposal 便宜,所以在执行前用 embedding 过滤重复'这个思路对任何 LLM 驱动的搜索循环都适用。
MoE LBL 案例是'LLM 进化改进 LLM 训练组件'的直接模板:把训练组件(损失函数)写成可进化代码块、用小规模训练当 fitness、再放大验证迁移性。哪怕它的代码未开源,这个 pipeline 设计本身可以在课题组内复刻(556M 模型 2B token 的 fitness 评估在实验室算力范围内)。实际使用注意两点:样本效率数字建立在前沿 API 模型上,预算规划别按本地小模型估;仓库 2026-02 重构后与论文实验的对应关系变弱,复现论文要 checkout 早期 commit(如 c686d7f)。