SMCEvolve：基于序贯蒙特卡洛演化的原则性科学发现

# SMCEvolve：通过序贯蒙特卡洛进化实现有原则的科学发现

来源：https://arxiv.org/html/2605.15308
Jiachen Jiang , Huminhao Zhu∗, Zhihui Zhu† 俄亥俄州立大学计算机科学与工程系 \{jiang\.2880, zhu\.4228, zhu\.3440\}@osu\.edu

###### 摘要

LLM驱动的程序进化已成为自动化科学发现的强大工具，然而现有框架缺乏设计其各组件的原则性指导，也不保证搜索能收敛。我们提出了SMCEvolve，它将程序搜索重新表述为从奖励倾斜的目标分布中采样，并通过序贯蒙特卡洛（Sequential Monte Carlo, SMC）采样器进行近似。从这个视角来看，三个核心机制作为有原则的组件自然浮现：自适应父代重采样、混合突变与接受，以及自动收敛控制。我们进一步提供有限样本复杂度分析，界定了达到目标近似误差所需的LLM调用预算。在数学、算法效率、符号回归以及端到端机器学习研究基准测试中，SMCEvolve在使用更少的LLM调用次数并在自行决定终止的条件下，超越了最先进的进化系统。代码可在https://github.com/kongwanbianjinyu/SMCEvolve获取。

参见说明图1：LLM驱动的程序进化通过序贯蒙特卡洛（SMC）瞄准奖励倾斜的分布。等高线描绘了程序空间上的分布；每个白点是一个粒子（程序）在进化群体中，虚线圆圈标记了高奖励区域。从LLM先验 p_{0} 抽取的粒子开始（*左图*），其中高奖励区域很少被覆盖，群体被LLM驱动向新的程序，这些程序形成一系列桥接分布 p_{0} e^{β_{t} R(x)}，奖励强度 β_{t} 递增，最终集中在目标 p_{0} e^{β_{T} R(x)} 上（*右图*）。这产生了一个有收敛保证的原则性进化框架SMCEvolve，与即兴的流水线形成对比。

## 1 引言

LLM驱动的智能体已经实现了大规模的自动化科学发现：给定问题描述和评估器，智能体可以自主搜索优化目标目标的程序，基于评估反馈迭代地改进候选方案\[33 (https://arxiv.org/html/2605.15308#bib.bib6),19 (https://arxiv.org/html/2605.15308#bib.bib7),26 (https://arxiv.org/html/2605.15308#bib.bib10),24 (https://arxiv.org/html/2605.15308#bib.bib9),17 (https://arxiv.org/html/2605.15308#bib.bib8)\]。这一范式已迅速扩展到多个领域，包括数学发现\[11 (https://arxiv.org/html/2605.15308#bib.bib17)\]、符号回归\[29 (https://arxiv.org/html/2605.15308#bib.bib11)\]、材料设计\[1 (https://arxiv.org/html/2605.15308#bib.bib12)\]、机器学习\[4 (https://arxiv.org/html/2605.15308#bib.bib15),12 (https://arxiv.org/html/2605.15308#bib.bib14)\]以及端到端研究自动化\[31 (https://arxiv.org/html/2605.15308#bib.bib13)\].

尽管取得了这些成功，当前的智能体设计在很大程度上仍然是*经验性的*，该领域缺乏一个统一的*理论*框架来指导设计。以AlphaEvolve\[24 (https://arxiv.org/html/2605.15308#bib.bib9)\]、ShinkaEvolve\[17 (https://arxiv.org/html/2605.15308#bib.bib8)\]和其他一些系统\[33 (https://arxiv.org/html/2605.15308#bib.bib6),19 (https://arxiv.org/html/2605.15308#bib.bib7),13 (https://arxiv.org/html/2605.15308#bib.bib1),3 (https://arxiv.org/html/2605.15308#bib.bib33),32 (https://arxiv.org/html/2605.15308#bib.bib34),20 (https://arxiv.org/html/2605.15308#bib.bib35)\]为代表的典型流水线，维护一个候选程序群体，提示LLM根据上下文变异选定的父代，并将评估后的后代添加回群体中。缺乏理论指导留下了几个局限性。首先，没有原则性指导来设计流水线中的每个组件：诸如父代选择、上下文构建和群体管理等组件是孤立地手工制作的，并通过大量消融实验验证，而非源自一个连接它们的连贯原则。其次，流水线的收敛性无法保证，导致运行间存在相当大的随机性和高方差；此外，现有系统无法区分群体是收敛到了高奖励区域还是仅仅停滞在一个局部模式，这迫使迭代次数必须预先固定——要么太少而无法达到好的解，要么太多而浪费计算资源。这些观察激发了本工作的核心问题：

*我们能否将LLM驱动的程序进化建立在一个严格的概率框架上，该框架统一其组件并提供收敛保证？*

我们从一个简单的观察入手来解决这个问题：使用LLM搜索高奖励程序可以转化为*从奖励倾斜的目标分布中采样* p^{*}(x ∣ q) ∝ p_{0}(x ∣ q) e^{β R(x)}，该分布将LLM先验 p_{0} 对每个问题 q 的程序 x 的权重重新调整，偏向于具有高评估奖励 R 的程序。由于直接从 p^{*} 采样是不可行的，我们转向*序贯蒙特卡洛（SMC）采样器*\[7 (https://arxiv.org/html/2605.15308#bib.bib18),6 (https://arxiv.org/html/2605.15308#bib.bib19)\]，它通过一系列奖励权重递增的桥接分布，逐步将粒子从先验 p_{0} 传输到目标 p^{*}。将每个候选程序视为一个粒子，我们推导出SMCEvolve，这是一个完整的进化框架，其三个核心机制直接源于SMC理论：

- •**自适应父代重采样**。父代根据从当前桥接分布导出的重要性权重进行重采样，其中奖励对选择的影响随着搜索的进行而增强——从鼓励早期探索的近乎均匀采样，到驱动后期利用的尖锐奖励聚焦采样。这与现有系统形成对比，后者在整个搜索过程中依赖固定的选择规则。
- •**混合突变与接受**。为确保收敛，LLM在每一步生成多个提议，每个提议根据当前桥接分布相关的概率被接受或拒绝。为了加速收敛，我们进一步设计了一个LLM驱动的核混合体，沿着两个轴——编辑范围（局部差异 vs. 完整重写）和信息来源（单父代 vs. 跨程序灵感）——并通过Thompson采样\[28 (https://arxiv.org/html/2605.15308#bib.bib20)\]自适应地选择，该采样倾向于近期产生了高奖励提议的核。相比之下，现有系统无条件接受提议，并且依赖单一的变异策略或固定权重的策略组合。
- •**自动收敛控制**。迭代次数根据群体状态自适应确定，而非预先固定：当群体仍然分布在多样化的候选者中时，搜索以小步幅进行；一旦集中在高奖励程序上，则采取更大步幅；并在达到目标分布时自动终止。相比之下，现有系统运行预先指定的固定迭代次数，没有任何信号检测收敛或停滞。

这三个机制共同实例化了一个用于LLM驱动程序搜索的完整SMC采样器，并且所得框架允许进行正式的收敛分析，并附带有限样本复杂度保证。我们的主要贡献如下：

- •**一个用于进化程序搜索的原则性框架**。我们介绍了SMCEvolve，这是第一个组件设计——父代重采样、变异和收敛控制——源自SMC理论而非孤立手工制作的进化智能体。
- •**有限样本收敛分析**。我们提供了程序进化领域的首个收敛保证，表明达到目标近似误差所需的总计算成本由粒子预算、变异混合和奖励强度明确界定。
- •**跨多个领域的实证验证**。我们在涵盖数学\[24 (https://arxiv.org/html/2605.15308#bib.bib9)\]、算法效率\[25 (https://arxiv.org/html/2605.15308#bib.bib26)\]、符号回归\[30 (https://arxiv.org/html/2605.15308#bib.bib16)\]和LLM预训练\[14 (https://arxiv.org/html/2605.15308#bib.bib4)\]的多个领域上评估SMCEvolve，它在自动收敛控制下使用更少的LLM调用次数，在大多数任务上超越了最先进的进化系统。

参见说明图2：SMCEvolve概述。*左图：*主循环。从 N 个初始程序开始，每次迭代 T（*i*）对粒子进行重新加权和重采样；（*ii*）通过一个 K 步的MH链（包含LLM提议和接受/拒绝更新）对每个父代进行变异；（*iii*）通过ESS调度下一个 λ_{t}，当 λ_{t}=1 时终止。*右图，从上到下：*圆形堆积问题上的进化过程（每次迭代的最佳奖励）；由Thompson采样选择的四种变异核组成的混合体；以及自动收敛控制找到 ESS(λ) 与阈值 κN 交点处的 λ_{t}。

## 2 方法：作为序贯蒙特卡洛的程序进化

我们将程序搜索表述为从一个奖励倾斜的目标分布中采样，该分布平衡了奖励最大化与LLM先验的关系（第 2.1 节），并通过一个序贯蒙特卡洛采样器来近似这个难以处理的目标，其组件——中间分布、重要性权重、变异核和自适应调度——均源自SMC理论（第 2.2 节）。

#### 符号说明。

在整个过程中，令 X 表示任务 q 的可数程序空间。X 上的所有分布都是概率质量函数，积分 ∫_{X} f(x) dx 表示对程序的求和。给定一个LLM，令 p_{LLM}(· ∣ C) 表示在上下文 C 下从LLM采样所诱导的分布。我们定义 p_{0}(· ∣ q)=p_{LLM}(· ∣ q) 作为任务 q 的LLM先验，并定义 Q_{t}(· ∣ x, C_{t})=p_{LLM}(· ∣ x, C_{t}) 作为用于变异的阶段条件LLM提议分布，以当前程序 x 和上下文 C_{t} 为条件。令 R: X → R 为奖励函数，假设其在 supp(p_{0}) 上有界。记 R_{-}=inf_{supp(p_{0})}R，R_{+}=sup_{supp(p_{0})}R，以及 Δ_R = R_{+} - R_{-} < ∞。

### 2.1 奖励倾斜的目标分布

在多个领域，包括数学发现\[11 (https://arxiv.org/html/2605.15308#bib.bib17)\]、符号回归\[29 (https://arxiv.org/html/2605.15308#bib.bib11)\]、材料设计\[1 (https://arxiv.org/html/2605.15308#bib.bib12)\]，科学发现共享一个共同的结构：一个由评估器引导的程序空间 X 上的搜索问题，其目标是找到最大化奖励 R(x) 的程序。然而，程序空间是离散且巨大的，直接最大化是难以处理的。因此，我们利用LLM先验 p_{0} 来引导搜索朝着合理的程序进行。为了平衡奖励最大化与对先验的遵循，我们将LLM驱动的程序搜索公式化为以下KL正则化变分优化问题：

max_{p} E_{x∼p}[R(x)] - (1/β) D_{KL}(p ∥ p_{0}), (1)

其中最大化是在所有相对于 p_{0} 绝对连续的 X 上的概率质量函数上进行的。以下结果刻画了最优解。

###### 引理 2.1 (奖励倾斜的目标分布)。

(1) 的唯一最大化解为

p^{*}(x ∣ q) ≜ (1/Z(q)) p_{0}(x ∣ q) e^{β R(x)}, (2)

其中 Z(q) = ∫ p_{0}(x′ ∣ q) e^{β R(x′)} dx′ 是配分函数。

该证明来源于标准的变分法：将拉格朗日函数（带有归一化约束）的泛函导数设为零，直接得到 (2)，详见附录 B。有界波动假设确保了 e^{β R_{-}} ≤ Z(q) ≤ e^{β R_{+}} < ∞，因此 (2) 是 X 上相对于 p_{0} 绝对连续的定义良好的概率质量函数。

参数 β 在LLM先验（β→0）和纯奖励最大化（β→∞）之间进行插值。从 p^{*} 采样是难以处理的，因为归一化项 Z(q) 需要在极其庞大的程序空间上对所有程序求和。

### 2.2 序贯蒙特卡洛采样器

为了从难以处理的目标 p^{*}(· ∣ q) 中采样，我们转向序贯蒙特卡洛（SMC）方法\[7 (https://arxiv.org/html/2605.15308#bib.bib18),6 (https://arxiv.org/html/2605.15308#bib.bib19)\]。它通过一系列*桥接分布* p_0, p_1, ..., p_T = p^{*} 将 p_0 连接到 p^{*}，其中 p_t 写为 p_t(x) = γ_t(x) / Z_t，其中 γ_t 是未归一化的密度，Z_t 是归一化常数。采样器维护 N 个粒子 {x_{t-1}^{(n)}}_{n=1}^{N} 来近似 p_{t-1}，并通过重复三个操作*重加权*、*重采样*和*变异*将它们推进为来自 p_t 的样本：重加权步骤为每个粒子分配重要性权重，重采样步骤丢弃低权重粒子，变异步骤为每个粒子注入多样性。重加权步骤将重要性权重分配为\[6 (https://arxiv.org/html/2605.15308#bib.bib19),7 (https://arxiv.org/html/2605.15308#bib.bib18)\]

w_t(x_{t-1}, x_t) = [γ_t(x_t) L_{t-1}(x_t, x_{t-1})] / [γ_{t-1}(x_{t-1}) M_t^K(x_{t-1}, x_t)], (3)

其中对于每个粒子 n，有 (x_{t-1}, x_t) = (x_{t-1}^{(n)}, x_t^{(n)})，M_t^K(x_{t-1}, ·) 是*阶段前向核*——即单步核 M_t 的 K 次复合，用于将每个粒子从阶段 t-1 变异到阶段 t——而 L_{t-1}(x_t, ·) 是由SMC框架引入的辅助*后向核*，旨在使 (3) 易于处理。关键在于，SMC的有效性取决于这些组件是如何为目标问题*联合设计*的：桥接分布 {p_t} 决定了退火路径，M_t 控制着探索和提议质量，而后向核 L_{t-1} 稳定了重要性加权。

#### 核所需属性