进化搜索中的计算分配：从深度-广度到多臂老虎机

# 进化搜索中的计算分配：从深度–广度到多臂老虎机  
来源：https://arxiv.org/html/2605.29268  

Sixue Xing¹，Haoyu He††footnotemark:²，Kerui Wu††footnotemark:³，Zhuo Yang⁴，Haozheng Luo⁵，Tianfan Fu⁶,⁷，Aarthy Nagarajan¹  

¹圣母大学  
²东北大学  
³马萨诸塞大学阿默斯特分校  
⁴东南大学  
⁵西北大学  
⁶南京大学  
⁷上海人工智能实验室  

###### 摘要  

LLM引导的进化搜索（Evolve系统）在数学和组合任务上取得了最先进的成果，然而大多数现有系统仅报告多次运行中的最佳结果，而未能记录运行间的分布情况。我们提出一个问题：固定数量的LLM调用应如何分配？以及单次运行达到报告数字的可靠性如何？通过扫描五个模型和三个任务的深度–广度网格，我们识别出两个经验规律：一条适应度–计算包络线，沿此线能力排序在大致有效的FLOPs上趋于一致；以及一个双线性深度–广度拟合，具有任务特定的交互；两者都受到模型–任务能力的门控。受这些规律启发，我们提出了BaSE（基于Bandit的自进化），一种多臂老虎机算法，用于在并行轨迹之间分配LLM调用。在不改变模型、提示或评估器的情况下，BaSE在8个（模型、任务）单元上，平均适应度比最强的岛屿协议基线提高了12.3%，在高方差设置上收益最大：仅通过分配就获得了可靠性增益。代码地址：https://github.com/keruiwu/self-evolving-allocation。  

## 1 引言  

大型语言模型越来越多地被用作进化搜索中的变异引擎：给定一个候选程序，冻结的LLM提出变体；确定性评估器对其进行评分；最佳变体作为下一轮的种子（Romera-Paredes et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib3)；Novikov et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib4)）。由此产生的 *Evolve* 系统（Lange et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib5)；Wang et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib6)；Assumpção et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib47)；Cemri et al., 2026 (https://arxiv.org/html/2605.29268#bib.bib11)）已在数学发现、组合优化和算法设计方面取得了最先进的结果。然而， *Evolve* 系统报告的头条数字在系统上不可比较：FunSearch报告了4/140的命中率（Romera-Paredes et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib3)）；CodeEvolve显示“仅最佳”（Assumpção et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib47)）；AlphaEvolve在 \(n=26\) 的Circle Packing基准测试上报告了一个单一数字（Novikov et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib4)）。报告的单次运行成本跨越两个数量级以上，从ShinkaEvolve中约150次LLM调用（Lange et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib5)）到ThetaEvolve单次运行处理的204,800个候选（Wang et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib6)）。  

图1 (https://arxiv.org/html/2605.29268#S1.F1) 将这些报告绘制在同一坐标轴上：每个点是一个单独精心选择的配置，主导惯例是只报告未指定次数运行中的最佳结果。很少有系统报告这些头条数字背后的运行间分布。再加上报告的计算成本的数量级变化，这使得这些数字无法可靠地指导在现实部署条件下单次运行的性能：现有报告描述了在有利运行中可以实现什么，而不是从业者在有限计算成本下应预期什么。  

（图1：\(n=26\) Circle Packing (CP) 上的成本–性能前沿。）  

预期性能由多种设计选择塑造。更强的基模型可以生成更好的变异；更信息化的提示可以引导搜索朝向更有用的编辑；重要的是，分配决定了进化过程如何平衡探索和利用。这种分配效应与模型和提示质量正交，并且一旦模型、提示和评估器固定，它仍然有意义。更好的分配可以通过避免过早地承诺弱轨迹和在没有精炼的情况下过度扩展广度来改善预期结果。虽然 *Evolve* 系统通常被描述为迭代循环直到进展饱和，但实际部署必须在明确的资源约束下运行，例如固定数量的模型调用、有限的计算分配或受限的实验活动。这激发了对LLM引导进化搜索中预期性能和可靠性的受控研究。  

我们采用经典进化计算中的固定预算视角（Jansen and Zarges, 2012 (https://arxiv.org/html/2605.29268#bib.bib2)），并将其引入LLM引导的进化。为此，我们首次对LLM引导进化搜索中的成本分配进行实证研究，刻画如何花费固定数量的LLM调用，并利用得到的图景来询问分配是否可以离线预计算或必须在线发现。  

总之，我们的贡献如下：  

1. 提出了LLM引导进化搜索中探索与利用之间的固定预算分配的第一个系统实证测量。  
2. 识别出两个规律：（i）一个可达到适应度对有效FLOPs的性能–计算包络线，沿此线在有能力模型之间能力排序基本消失；（ii）一个参数化的深度–广度规律，描述每个模型–任务单元的特征。  
3. 设计了一个自适应bandit分配器（BaSE），在并行进化轨迹上运行，在8个（模型、任务）单元上，平均最佳适应度比最强的岛屿协议基线提高了12.3%——这不是模型改进，也不是提示改进，而是分配改进。  

## 2 相关工作  

**LLM引导的进化搜索。** FunSearch（Romera-Paredes et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib3)）将LLM作为进化程序合成中的变异算子引入，AlphaEvolve（Novikov et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib4)）将该范式扩展到最先进的结果。*Evolve* 变体在不同轴线上变化——样本效率（Lange et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib5)）、测试时RL（Wang et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib6)）、开源岛屿——以及代码、架构和提示的相关工作（Lehman et al., 2022 (https://arxiv.org/html/2605.29268#bib.bib7)；Chen et al., 2023 (https://arxiv.org/html/2605.29268#bib.bib8)；Yang et al., 2023 (https://arxiv.org/html/2605.29268#bib.bib9)）；所有工作都手动设置种群大小和代数。ThetaEvolve仅定性地指出，小型数据库早期进展更快，但大型数据库在规模上胜出（Wang et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib6)），而Population-Evolve在不保持总预算固定的情况下扫描种群大小（Zhang et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib10)）。邻近的分配工作将计算路由到岛屿之间（Cemri et al., 2026 (https://arxiv.org/html/2605.29268#bib.bib11)），将进化与best-of-N和顺序修订进行比较（Lee et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib53)），或关注父本采样（Novikov et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib4)；Lange et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib5)）和组合算子（Lange et al., 2023 (https://arxiv.org/html/2605.29268#bib.bib32)；Meyerson et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib33)）。最接近的先例是ShinkaEvolve（Lange et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib5)），它在最后阶段使用bandit集成模型；我们则针对运行内的深度–广度划分。  

**计算分配。** 推理扩展工作分配测试时计算（Snell et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib12)；Brown et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib13)；Wu et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib14)；Chen et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib15)），关于单查询推理和树搜索的广度vs深度研究（Sharma and Chopra, 2025 (https://arxiv.org/html/2605.29268#bib.bib16)；Wen et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib17)；Inoue et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib45)；Miyamoto et al., 2026 (https://arxiv.org/html/2605.29268#bib.bib19)）报告了经验的、依赖状态的曲线；没有一个针对基于种群且带有父本条件变异的进化。我们的在线分配器借鉴了多臂老虎机（Auer et al., 2002a (https://arxiv.org/html/2605.29268#bib.bib37)；Lattimore and Szepesvári, 2020 (https://arxiv.org/html/2605.29268#bib.bib38)）和固定预算最佳臂识别（Audibert and Bubeck, 2010 (https://arxiv.org/html/2605.29268#bib.bib40)；Karnin et al., 2013 (https://arxiv.org/html/2605.29268#bib.bib41)），其先例包括超参数搜索（Li et al., 2018 (https://arxiv.org/html/2605.29268#bib.bib42)）、提示选择（Shi et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib43)）、MCTS扩展（Inoue et al., 2025 (https://arxiv.org/html/2605.29268#bib.bib45)）、岛屿路由（Cemri et al., 2026 (https://arxiv.org/html/2605.29268#bib.bib11)）和代码修复（Tang et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib20)），所有这些都*假设*自适应分配有帮助。经典EA贡献了固定计算下最优种群分析（Nakano et al., 1994 (https://arxiv.org/html/2605.29268#bib.bib21)；Briesch et al., 2023 (https://arxiv.org/html/2605.29268#bib.bib22)）、子代规模理论（Jansen et al., 2005 (https://arxiv.org/html/2605.29268#bib.bib23)；Doerr and Künnemann, 2015 (https://arxiv.org/html/2605.29268#bib.bib24)；Gießen and Witt, 2017 (https://arxiv.org/html/2605.29268#bib.bib25)；Badkobeh et al., 2014 (https://arxiv.org/html/2605.29268#bib.bib26)）和固定预算框架（Jansen and Zarges, 2012 (https://arxiv.org/html/2605.29268#bib.bib2), 2014 (https://arxiv.org/html/2605.29268#bib.bib27)）；所有这些都假设随机变异，而LLM变异携带代码先验和离散吸引子，破坏了i.i.d.平均场假设，因此我们通过实证刻画这一表面。  

## 3 问题形式化  

**自进化。** 在高层次上，我们将自进化形式化为一个在固定推理预算 \(C\) 次LLM调用下的迭代优化过程。具体来说，如算法1所述，一个自进化系统反复生成候选响应，评估其质量，并根据历史响应-评估对精炼建议的解决方案。  

算法1 自进化过程  

1: 任务 \(q\)，基LLM \(f\)，提示生成器 \(h\)，预算（LLM调用次数） \(C\)  
2: **for** \(c = 1, \dots, C\) **do**  
3:    \(\text{prompt} \leftarrow h\bigl(q, \bigl(\text{response}^{(j)}, \text{score}^{(j)}\bigr)_{j \in [c]}\bigr)\)  
4:    \(\text{response}^{(c+1)} \leftarrow f(\text{prompt})\)  
5:    \(\text{score}^{(c+1)} \leftarrow \text{Eval}\bigl(q, \text{response}^{(c+1)}\bigr)\)  
6: **end for**  
7: \(c^* \leftarrow \arg\max_{c \in [C]} \text{score}^{(c)}\)  
8: **return** \(\text{response}^{(c^*)}\)  

这个过程的关键设计问题是算法1第3行描述的*父本采样协议*：系统在构建下一个提示时如何选择和重用历史响应？这个选择决定了进化过程如何在利用高性能解决方案和探索多样化备选方案之间取得平衡。在这项工作中，我们探索了两种代表性协议：*贪婪*和*岛屿*：  

**贪婪协议。** 在每一代，贪婪协议选择当前得分最高的响应作为父本，并并行生成 \(N\) 个子代。等价地，它每代花费 \(N\) 次LLM调用来精炼到目前为止找到的最佳解决方案。  

**岛屿协议。** 岛屿协议起源于经典进化计算（Tanese, 1989 (https://arxiv.org/html/2605.29268#bib.bib48)），并由FunSearch引入LLM引导的进化搜索（Romera-Paredes et al., 2024 (https://arxiv.org/html/2605.29268#bib.bib3)），后来被许多Evolve风格系统采用；它维护一个分为多个岛屿的种群数据库。在每一代，它首先根据MAP-Elites风格的覆盖规则选择一个岛屿（Mouret and Clune, 2015 (https://arxiv.org/html/2605.29268#bib.bib46)），然后从该岛屿均匀采样一个父本。  

**深度–广度分配问题。** 在贪婪协议下，预算为 \(C\) 的一次运行完全由该预算如何划分来指定：\(T\) 代，每代 \(N\) 个子代，因此：  

\[
C = N \cdot T
\]

这种划分的两端是熟悉的极限：\(T=1\) 将所有预算花费在单一代的并行样本上（best-of-\(N\)），而 \(T=C\) 沿一条轨迹精炼 \(C\) 个连续步骤。  

设 \(V(C, T)\) 为预算 \(C\) 和深度 \(T\) 下一次运行的最佳期望适应度。保持评估器、提示模板、基模型和初始程序固定，划分是唯一剩余的自由度，我们寻求*计算最优深度*：  

\[
T^*(C) = \arg\max_T V(C, T), \quad V_{\max}(C) = \max_T V(C, T).
\]

我们在第5节中提出的问题是 \(V(C, T)\) 如何随分配变化。  

## 4 实验设置  

**任务。** 我们评估来自AlphaEvolve并与OpenEvolve示例套件一起提供的三个几何优化任务：Circle Packing (CP, \(n=26\))、MinMaxDist (MMD, \(n=16\)) 和 Heilbronn Triangle (HT, \(n=11\))。对于每个任务，我们逐字使用OpenEvolve评估器和初始程序文件，并通过最佳已发表构造将原始目标归一化，使得 \(\text{fitness}=1.0\) 对应最先进水平。完整问题陈述和归一化因子见附录B。  

**模型。** 我们扫描开源Qwen3系列的四个大小：1.7B、4B、8B和14B，均启用思考模式，温度 \(0.6\)，top-\(p\) \(0.95\)。推理由vLLM v0.18提供服务，使用 `--quantization fp8`、`--max-model-len=40960`、`--max-num-seqs=16`。vLLM服务器在H100 GPU上最多支持16个并发LLM调用。  

**Bandit算法。** 在第6节中，我们探索不同运行对适应度得分性能的影响，并使用多臂老虎机（MAB）进行自适应轨迹分配。我们实现了三种经典MAB算法，即上置信界（UCB）（Auer et al., 2002b (https://arxiv.org/html/2605.29268#bib.bib34)）、高概率探索与利用的指数权重算法（EXP3.P）（Auer et al., 2002b (https://arxiv.org/html/2605.29268#bib.bib34)）和汤普森采样（Thompson, 1933 (https://arxiv.org/html/2605.29268#bib.bib35)；Agrawal and Goyal, 2012 (https://arxiv.org/html/2605.29268#bib.bib36)），以及一个朴素