- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces SMCEVOLVE, a Sequential Monte Carlo framework for LLM-driven program evolution. It formulates program search as sampling from a reward-tilted distribution that combines the LLM prior with program evaluation rewards. Based on this formulation, the method derives three components: adaptive reward-based parent resampling, a mixture of LLM mutation kernels with reward-aware acceptance, and ESS-based adaptive convergence control. The paper provides finite-sample guarantees for the empirical particle distribution and the best program found, and characterizes conditions under which the limiting distribution coincides with the ideal reward-tilted target. SMCEVOLVE is evaluated on mathematical discovery, algorithm optimization, symbolic regression, and end-to-end ML pretraining benchmarks. It outperforms existing evolving systems on most tasks while using fewer LLM calls under adaptive termination, with ablations supporting the importance of its main design components.
Critical strengths
- Principled unification of LLM-driven program evolution. The paper provides a coherent SMC-based formulation that connects parent resampling, mutation with acceptance, and adaptive termination within a single probabilistic framework. This is consequential because it replaces several independently hand-crafted design choices with a common principle and enables formal finite-sample analysis.
- Broad empirical evaluation with improved sample efficiency. The method is evaluated across mathematical discovery, algorithm optimization, symbolic regression, and end-to-end ML research tasks. SMCEVOLVE achieves strong performance on most benchmarks while using fewer LLM calls under adaptive termination, and the ablation study supports the contribution of its main components. This breadth suggests that the proposed framework is relevant beyond a single benchmark or application domain.
Critical weaknesses
- The strongest convergence claim is conditional. The theorem guarantees approximation to η_T, while η_T=p^* requires p_t-invariant mutation kernels. The deployed reward-only acceptance rule for black-box LLMs generally does not satisfy this condition, and the resulting gap from p^* is not empirically quantified.
- The empirical evidence is limited. Results are reported as the best performance over only three seeds, with little uncertainty reporting. The comparison also uses adaptive termination for SMCEVOLVE but fixed call budgets for baselines, making the efficiency gains difficult to interpret fairly.
- The claimed generality is not fully established. The ablations are concentrated mainly on one task, and the method relies on several manually chosen hyperparameters and prompt designs. More cross-task sensitivity analyses and equal-budget evaluations are needed to show that the improvements come from the proposed SMC principle rather than task-specific engineering.
Questions for authors
In the deployed black-box LLM setting, the reward-only acceptance rule omits the prior and proposal probability ratios required for an exact MH correction. Consequently, Theorem 4.1 guarantees approximation toη_T, while identifying η_T with p^* requires additional conditions. Appendix G bounds their discrepancy using ϵ_t, which measures the proposal kernel’s deviation from detailed balance with the prior. How could ϵ_t be estimated or meaningfully upper-bounded for the LLM proposals used in the experiments? Can the authors provide empirical evidence that this discrepancy is small enough for the bound on‖η_T-p^* ‖_TV to be informative?
4 comments
Q2: The empirical evidence is limited. Results are reported as the best performance over only three seeds, with little uncertainty reporting. The comparison also uses adaptive termination for SMCEVOLVE but fixed call budgets for baselines, making the efficiency gains difficult to interpret fairly.
R2: We report the individual runs of SMCEvolve on five Math tasks, one column per seed, so the level and the variation across seeds can be seen directly.
The runs use the default configuration (LLM ensemble gpt-5.4-mini + gemini-3-flash). The table shows seeds 101, 102 and 103, and each entry is the best reward of one run.
| Task | Seed 101 | Seed 102 | Seed 103 |
|---|---|---|---|
| Circle Packing | 0.9993 | 0.9979 | 0.9914 |
| Kissing Number | 0.9001 | 0.9005 | 0.9000 |
| Hexagon Packing (n = 11) | 0.9821 | 0.9742 | 0.9806 |
| Heilbronn (convex, n = 13) | 0.9163 | 0.9117 | 0.9143 |
| Heilbronn (triangle) | 0.8996 | 0.8945 | 0.8963 |
The three runs of a task are close to each other, which shows the results are reliable.
Regarding the fairness of the comparison, in Tables 1–3, the fixed call budgets allocated to the baselines exceed the maximum number of calls used by SMCEvolve before adaptive termination. Thus, the baselines are given more LLM calls, yet SMCEvolve still achieves superior performance, demonstrating that its gains are not due to a larger computational budget.
Q3: The claimed generality is not fully established. The ablations are concentrated mainly on one task, and the method relies on several manually chosen hyperparameters and prompt designs. More cross-task sensitivity analyses and equal-budget evaluations are needed to show that the improvements come from the proposed SMC principle rather than task-specific engineering.
R3: There is no task-specific engineering: all tasks in all four domains use one configuration and one set of prompt templates, and every ablation changes only a choice inside the SMC algorithm.
The configuration is 2 islands × 8 particles, K = 2, β = 20, κ = 0.9, T_min = 3 and migration every 3 steps, with one set of four kernel prompt templates. The per-task files contain only the initial program, the evaluator, the task description and the evaluation timeout. None of them changes an algorithm, LLM or prompt setting. We will release the configurations.
The ablations (Sec. 5.2, Table 4) are all inside the SMC framework. Each variant changes one choice of the sampler: the resampling rule, the mutation kernel, or the split between the number of particles N and the chain length K. The task and the LLM-call budget are the same for all variants. So what Table 4 compares is choices of the SMC design, not task-specific choices.
Q4: In the deployed black-box LLM setting, the reward-only acceptance rule omits the prior and proposal probability ratios required for an exact MH correction. Consequently, Theorem 4.1 guarantees approximation to η_T, while identifying η_T with p* requires additional conditions. Appendix G bounds their discrepancy using ε_t, which measures the proposal kernel's deviation from detailed balance with the prior. How could ε_t be estimated or meaningfully upper-bounded for the LLM proposals used in the experiments? Can the authors provide empirical evidence that this discrepancy is small enough for the bound on ‖η_T − p*‖_TV to be informative?
R4: Our guarantee does not depend on ε_t being small: Theorem 4.1 needs no bound on ε_t, and the bound in App. G is used only to say when η_T = p* and what controls the gap between them.
ε_t can be estimated by Monte Carlo when the model gives likelihoods. From (36), ε_t = E_{x∼p0, x'∼Q_t(·|x)}[(1 − σ_t(x, x'))₊], where σ_t = p0(x')·Q_t(x|x') / [p0(x)·Q_t(x'|x)] is the factor that the reward-only rule leaves out of the full MH ratio (App. F). This is an average over the proposals that the algorithm makes, so it only needs the prior probability and the forward and reverse proposal probabilities of each sampled pair. An open-weights model gives these. The models in our experiments are closed APIs, which do not return them.
For empirical evidence, the synthetic experiment in R1 (300 states, no LLM calls) computes the gap exactly. When ε_t = 0 (α = 0, first row of the table), the gap is zero, as Prop. G.1 says. When ε_t > 0, the exact TV(η_T, p*) is 0.03–0.14, far below the bound. So the bound is a worst-case statement: it shows that the gap is controlled by ε_t and is zero when ε_t = 0.
Q5: Flag For Ethics Review: Yes
R5: The review does not give a reason for this flag. We are happy to answer if the reviewer or the AC can tell us what the concern is. For reference: the work uses public benchmarks (mathematical optimization, algorithm efficiency, symbolic regression and ML research), involves no human subjects or personal data, and uses LLMs only through standard APIs.
Thank you again for your review. We have posted our replies to your questions, including what Theorem 4.1 guarantees under the reward-only acceptance rule, the result of each seed, and the single configuration used for all tasks. Could you let us know whether they answer your questions? We are happy to discuss any point that is still open.
R1: Our claims do not depend on this condition: Theorem 4.1 is stated and proved for the reward-only acceptance rule that we deploy, with any LLM proposal, and it does not assume p_t-invariant kernels.
The theorem says that the population approximates η_T (Eq. 13) and gives a lower bound on the reward of the best program found (Eq. 14). Neither statement needs η_T = p*. The paper mentions η_T = p* only in a remark after the theorem (Sec. 4, "Relation to p*"), to say when the two are the same, and it is not claimed for LLM proposals.
We also quantified the gap between η_T and p* in a controlled setting. For LLM proposals, η_T and p* are distributions over all programs, so the gap cannot be computed. We built a small synthetic problem in which both are computed exactly. Its purpose is to show how the gap behaves when the condition for η_T = p* is broken step by step, and whether a larger gap means lower reward.
In this problem, 300 states stand for programs. Each state has a fixed reward in [0, 1], and good states are rare under the prior (0.5% of the prior mass has R ≥ 0.9). A fixed transition matrix Q_α takes the place of the LLM, so the experiment uses no LLM calls:
Q_α = (1 − α)·Q_rev + α·Q_seek
Q_rev is a proposal in detailed balance with the prior. This is the condition in Prop. G.1 under which η_T = p*. Q_seek is a proposal that prefers states with higher reward. It stands for a proposer that tries to improve the current program, and it does not satisfy the condition. So α is the share of the proposal that breaks the condition: at α = 0 the condition holds, and at α = 1 it is fully broken. The sampler is the one analyzed in Theorem 4.1.
The first column, α, is the mixing weight defined above. The second column is the gap between η_T and p*, measured as the total variation distance (0 means they are the same, 1 means they do not overlap). The third column is the mean reward under η_T; under p* it is 0.9694 in every row.
The table shows that the gap is zero when the condition holds and grows smoothly as the condition is broken, up to 0.14 at α = 1, while the mean reward does not fall (it rises slightly, because Q_seek prefers higher reward). So in this problem, a larger gap between η_T and p* does not mean lower reward. These numbers belong to this synthetic problem; they are not estimates for an LLM.