acceptodds
Under review as a conference paper at ICLR 2027

SMCEvolve: Principled Scientific Discovery via Sequential Monte Carlo Evolution

Abstract

LLM-driven program evolution has emerged as a powerful tool for automated scientific discovery, yet existing frameworks offer no principled guide for designing their individual components and provide no guarantee that the search converges. We introduce SMCEvolve, which recasts program search as sampling from a reward-tilted target distribution and approximates it with a Sequential Monte Carlo (SMC) sampler. From this view, three core mechanisms emerge as principled components: adaptive parent resampling, mixture of mutation with acceptance, and automatic convergence control. We further prove finite-sample guarantees for the deployed sampler, both for the reward-tilted distribution it tracks and for its best program. Across math, algorithm efficiency, symbolic regression, and end-to-end ML research benchmarks, SMCEvolve surpasses state-of-the-art evolving systems while using fewer LLM calls under self-determined termination.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Agent, Sequential Monte Carlo, Self-Evolve

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_JV9DOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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.
  3. 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

Q1: 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.

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.

αGap: TV(η_T, p*)Mean reward under η_T
00.00000.9694
0.050.03280.9728
0.100.05520.9751
0.250.09270.9790
0.500.11890.9817
0.750.13100.9829
1.000.13790.9836

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.

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.

TaskSeed 101Seed 102Seed 103
Circle Packing0.99930.99790.9914
Kissing Number0.90010.90050.9000
Hexagon Packing (n = 11)0.98210.97420.9806
Heilbronn (convex, n = 13)0.91630.91170.9143
Heilbronn (triangle)0.89960.89450.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.

Reviewer_U9yROpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies automated scientific discovery through LLM-based program search. It proposes SMCEvolve, which combines ideas from sequential Monte Carlo: annealed reward weighting, importance-weight-based parent resampling, and Metropolis-style accept/reject mutations. It also proposes using ESS to adaptively control the annealing schedule, and the algorithm terminates upon reaching the prescribed final temperature. Experiments against ReEvo, OpenEvolve, and ShinkaEvolve show promising performance while using fewer LLM calls than the fixed-budget baselines.

Critical strengths
  1. Well-motivated algorithmic design. the SMC perspective provides a framework for combining annealing, resampling, and mutation. Combining these components through a temperature schedule offers a systematic approach to balancing exploration and exploitation.

  2. Promising empirical results. The experiments cover multiple scientific discovery domains and suggest improvements in both solution quality and LLM-call efficiency. The component ablations provide additional evidence supporting the proposed design.

Critical weaknesses
  1. Gap between the intended target and the theoretical guarantee. The practical mutation kernel does not generally preserve the intended bridging distribution ptp_t. Consequently, Theorem 4.1 controls particle approximation error around ηt\eta_t, which need not equal ptp_t. Although the authors acknowledge this distinction and bound the discrepancy in Proposition G.1, they do not establish that the bound is small for the deployed LLM proposals. Thus, approximating ηt\eta_t does not necessarily imply approximating the intended reward-tilted target. The motivation and claims should more consistently reflect this distinction.

  2. Limited justification for interpreting ESS-based termination as optimization convergence. ESS controls incremental weight degeneracy, while reaching the final temperature completes the annealing schedule. Neither condition establishes that the search has reached a high-quality region or that further computation would yield little improvement. For example, particles with similarly poor rewards can still have high ESS. The theoretical analysis therefore does not establish whether the deployed stopping rule is reliable.

Questions for authors
  1. ESS ablation: How does the adaptive schedule compare with fixed annealing schedules under matched LLM-call budgets? How sensitive are solution quality and stopping time to the ESS threshold? How much additional improvement can be obtained by continuing the search beyond the proposed termination point?

  2. Beyond best-of-three: Could you report mean performance and variability across seeds, alongside best-of-three results? Those would help assess whether the reported efficiency gains are reliable.

  3. Target discrepancy: Can the discrepancy between ηt\eta_t and ptp_t be meaningfully bounded or measured in a controlled setting? Otherwise, could the presentation more clearly distinguish the SMC-inspired motivation from the guarantees actually established for the implemented algorithm?

6 comments

Q1: Gap between the intended target and the theoretical guarantee. The practical mutation kernel does not generally preserve the intended bridging distribution p_t. Consequently, Theorem 4.1 controls particle approximation error around η_t, which need not equal p_t. Although the authors acknowledge this distinction and bound the discrepancy in Proposition G.1, they do not establish that the bound is small for the deployed LLM proposals. Thus, approximating η_t does not necessarily imply approximating the intended reward-tilted target. The motivation and claims should more consistently reflect this distinction.

Target discrepancy: Can the discrepancy between η_t and p_t be meaningfully bounded or measured in a controlled setting? Otherwise, could the presentation more clearly distinguish the SMC-inspired motivation from the guarantees actually established for the implemented algorithm?

R1: Our theorem guarantees how good the best program found by the algorithm is, and this bound (Eq. 14) does not contain p*, so the gap between η_T and p* does not affect it, however large the gap is. p* is used to derive the design of the algorithm, not to state the guarantee.

The goal of the method is to find a program with high reward, and this is the quantity reported in the experiments. Part 2 of Theorem 4.1 (Eq. 14) is a lower bound on exactly this quantity. The bound is written with the final value β_T of the annealing schedule and with P_r, the probability that a single run of LLM mutations without resampling has a weighted average reward of at least r. It is proved for the algorithm as it is run, with no invariance or ergodicity assumed. η_T and p* do not appear in it, so no condition on their gap is needed.

p* has a different role: the resampling weights, the acceptance rule and the schedule are derived from p* and its bridges p_t (Sec. 3). The paper discusses how η_T relates to p* right after the theorem (Sec. 4, "Relation to p*").

η_T, the limit in Part 1 (Eq. 13), is also a reward-tilted distribution. Sec. 4 describes it as follows: η_T "favors programs that the LLM reaches through high-reward intermediate programs, trading off reward against staying close to the LLM's own behavior". In other words, p* is the reward-tilted version of the LLM's one-shot prior, and η_T is the reward-tilted version of the LLM's mutation process (App. G, Step 4).

As you suggest, we also measured the gap 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.

αGap: TV(η_T, p*)Mean reward under η_T
00.00000.9694
0.050.03280.9728
0.100.05520.9751
0.250.09270.9790
0.500.11890.9817
0.750.13100.9829
1.000.13790.9836

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.

Q2: Limited justification for interpreting ESS-based termination as optimization convergence. ESS controls incremental weight degeneracy, while reaching the final temperature completes the annealing schedule. Neither condition establishes that the search has reached a high-quality region or that further computation would yield little improvement. For example, particles with similarly poor rewards can still have high ESS. The theoretical analysis therefore does not establish whether the deployed stopping rule is reliable.

How much additional improvement can be obtained by continuing the search beyond the proposed termination point?

R2: λ = 1 means that the annealing schedule has reached the target temperature β. It is the stopping rule of the sampler. We do not present it as a proof that the optimum has been found. No method can give such a proof for a black-box evaluator. What the rule gives is a stopping point that is set by the state of the population, not by an iteration count fixed in advance. The data show that it is a good stopping point.

To answer the question directly, we continued the search after termination, and the additional improvement is zero. On Circle Packing (3 seeds), after λ = 1 we ran 6 more mutation steps at the target temperature β, which about doubles the number of LLM calls.

SeedCalls at λ = 1Calls after 6 more stepsBest at λ = 1Best after 6 more steps
1011923680.99930.9993
1022033840.99790.9979
1031763680.99140.9914

The last two columns are the ones to compare: the best reward is the same in all three runs (the largest change is below 1e-6). Stopping at λ = 1 lost nothing.

Finally, most of the improvement also comes early in a run. Over all logged runs with the default configuration, most performance gains are achieved within the first half of LLM calls, indicating rapid early convergence. In over 70% of all runs, the last 10% of the calls bring no improvement.

Q3: ESS ablation: How does the adaptive schedule compare with fixed annealing schedules under matched LLM-call budgets?

R3: We ran this comparison. The algorithm, the population (2 islands × 8 particles), K = 2, β = 20, the LLM ensemble and the seeds are the same for both schedules, and only the schedule changes. Adaptive: the ESS rule with κ = 0.9 (default). Fixed: a linear schedule λ_t = t/T with the ESS rule turned off. Tasks: Circle Packing, Heilbronn (convex, n = 13), Hexagon Packing (n = 11) and Kissing Number from the Math suite, 3 seeds each. In the table, "At termination" gives the final best reward of each schedule and the calls it used. Entries are the best over the 3 seeds.

TaskAdaptive at termination (calls)Fixed at termination (calls)
Circle Packing0.9993 (192)0.9485 (208)
Heilbronn (convex, n = 13)0.9163 (176)0.8601 (208)
Hexagon Packing (n = 11)0.9821 (176)0.9064 (208)
Kissing Number0.9005 (144)0.8106 (208)

The results show that adaptive schedule performs better than fixed annealing schedules with fewer LLM-call budgets. Additionally, the two schedules differ substantially in effective sample size. With the ESS rule, the effective sample size stays at 0.9 N. With the fixed schedule, its minimum over a run drops to between 0.12 N and 0.63 N.

Q4: How sensitive are solution quality and stopping time to the ESS threshold?

R4: Solution quality is not sensitive to κ.

We tested κ ∈ {0.5, 0.7, 0.9, 0.95} on Circle Packing and Kissing Number, with 3 seeds per value, the default T_min and the same LLM ensemble. The table reports the best reward over 3 seeds, along with the number of LLM calls at termination for the corresponding run.

κCircle Packing: best rewardCircle Packing: callsKissing Number: best rewardKissing Number: calls
0.500.99361690.8996139
0.700.99691700.9001140
0.90 (default)0.99931920.9005144
0.950.99232080.9000160

On quality, the best reward shows no trend in κ: it does not move in one direction as κ grows. On stopping time, the number of calls grows as κ increases. This is expected: a larger κ forces smaller temperature steps, so more steps are needed. So κ sets the cost of a run, and the results do not depend on a tuned κ.

Q5: Beyond best-of-three: Could you report mean performance and variability across seeds, alongside best-of-three results? Those would help assess whether the reported efficiency gains are reliable.

R5: Yes. The table lists 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, the same seeds as in R2–R4, and each entry is the best reward of one run.

TaskSeed 101Seed 102Seed 103
Circle Packing0.99930.99790.9914
Kissing Number0.90010.90050.9000
Hexagon Packing (n = 11)0.98210.97420.9806
Heilbronn (convex, n = 13)0.91630.91170.9143
Heilbronn (triangle)0.89960.89450.8963

The three runs of a task are close to each other, which shows the results are reliable.

Reviewer_L5ynOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper provides an algorithm for LLM-guided program evolution. The program uses an adaptively weighted parent resampling process to select promising parents more (especially later in training), Thompson sampling for whether a mutation is accepted, and an adaptive number of training steps. The paper provides a theoretical proof of convergence to a distribution. Evaluations on mathematical optimization, algorithm efficiency and symbolic regression show consistent and sizable improvements over prior methods.

Critical strengths

The empirical results presented here are quite strong. Due to this reason, I believe the paper can be a useful method to exist among the current set of methods.

Critical weaknesses
  • If I am interpreting Equation 13 correctly, the theoretical result shows that the algorithm converges to sampling from some fixed distribution - but this distribution need not be the optimal distribution under the reward function? In this light I fail to see the significance of this result.
  • The three aspects of the algorithm - weighted sampling of parents, thompson sampling, and adaptive number of steps - all appear to not be novel. I invite the authors to provide a clearer exposition on what the novelty of this paper is.
  • If I am interpreting the assumption of uniform Ergodicity correctly (i.e. translate it to lay-speak), it says that there exists some number kk of iterations such that no matter what the initial piece of text is, applying kk iterations of the LLM will be sufficiently close to the optimal distribution. This appears to be a very strong assumption and I am not convinced that this assumption reflects the status of reality.
Questions for authors

For the first and third weaknesses above, I would appreciate if the authors can confirm or clarify my interpretation of their equations. For the second question, I request them to provide some clarification of their novelty and positioning among prior work.

8 comments

Q1: If I am interpreting Equation 13 correctly, the theoretical result shows that the algorithm converges to sampling from some fixed distribution - but this distribution need not be the optimal distribution under the reward function? In this light I fail to see the significance of this result.

R1: Thanks for the question. We need to point out that Eq. (13) is only the first half of Theorem 4.1. The theorem has two parts, and they have to be read together.

Part 1 (Eq. 13) says what the population converges to. The N programs kept by the algorithm follow a limit distribution η_T, with an error of order N^(−1/2). η_T is not "some" distribution. It is defined exactly. App. G (Step 4) proves that η_T is the distribution of the final state under Q*, where Q* is the unique distribution over trajectories that maximizes E_Q[S] − KL(Q‖P). Here S = Σ_t Δβ_t·R(x_{t−1}) is the annealed reward collected along a trajectory, and P is the distribution of the LLM mutation chain without resampling. In summary: η_T is the LLM's mutation process, re-weighted toward high reward.

Part 2 (Eq. 14) says how good the best program is. With probability at least 3/4,

R_best ≥ max_r { r − (1/β_T)·[log(1/P_r) + log 2] },

where R_best is the best reward found by the algorithm and P_r is the probability that one LLM mutation chain without resampling reaches weighted average reward r. Running single chains again and again needs about 1/P_r tries to reach level r. In (14), a rare level r costs only log(1/P_r).

Together, the two parts are significant for the goal of the method, which is to find good programs. Part 1 shows that the population follows a known distribution that is re-weighted toward high reward. Part 2 gives a lower bound on the reward of the best program found. Both hold for the algorithm as it is run, with a black-box LLM and reward-only acceptance: no invariance or ergodicity is assumed. Neither part needs η_T to be the reward-optimal distribution p*. η_T = p* holds when the mutation kernel is p_t-invariant (full MH ratio, or a proposal in detailed balance with the prior), and Theorem 4.1 is proved without this condition.

Q2: The three aspects of the algorithm - weighted sampling of parents, thompson sampling, and adaptive number of steps - all appear to not be novel. I invite the authors to provide a clearer exposition on what the novelty of this paper is.

R2: Novelty must be judged for the whole algorithm and its guarantee, not part by part. Every SMC sampler is built from reweighting, resampling and a mutation kernel. Every evolutionary method is built from selection and variation. The fact that each part exists somewhere else does not show that a method is not new. The paper contributes three things.

(1) A unified derivation and a shared control variable. In earlier LLM-evolution systems, parent selection, acceptance and stopping are designed separately, each with its own settings. In SMCEvolve one quantity, the bridge temperature β_t, sets all three: the resampling weights are softmax(Δβ_t·R), the acceptance probability is min(1, exp(β_t·ΔR)), the next β_t is found by solving ESS = κN, and the run stops when β_t reaches β. Sec. 3.3 shows that AlphaEvolve-style and ShinkaEvolve-style loops are special cases: a fixed β_t, one proposal that is always accepted (K = 1), and a number of iterations fixed in advance.

(2) A finite-sample guarantee for the algorithm that is actually run. To our knowledge, no earlier LLM-evolution system has a finite-sample result for the population it keeps or for the best program it finds. Theorem 4.1 gives both for the reward-only acceptance rule, without invariance or ergodicity assumptions (see R1).

(3) A different setting from earlier work that combines SMC and LLMs. Lew et al. (2023), Zhao et al. (2024) and Feng et al. (2025) run SMC inside one generation: the particles are partial or complete responses. ModelSMC (Wahl et al., 2026) weights candidate mechanistic models by likelihood-based criteria. SMCEvolve runs SMC over complete programs, and the only signal is a black-box evaluator: no likelihood and no token-level access. This is why it works with closed-API LLMs and on pure optimization tasks.

If the reviewer knows an LLM-evolution system in which selection, acceptance and stopping all follow from one annealing parameter, or one that has a finite-sample guarantee, we would be glad to know about it.

References

  • Feng et al. (2025). Step-by-step reasoning for math problems via twisted sequential Monte Carlo. ICLR 2025.
  • Lew et al. (2023). Sequential Monte Carlo steering of large language models using probabilistic programs. arXiv:2306.03081.
  • Wahl et al. (2026). A probabilistic framework for LLM-based model discovery. arXiv:2602.18266.
  • Zhao et al. (2024). Probabilistic inference in language models via twisted sequential Monte Carlo. ICML 2024.

Q3: If I am interpreting the assumption of uniform Ergodicity correctly (i.e. translate it to lay-speak), it says that there exists some number k of iterations such that no matter what the initial piece of text is, applying k iterations of the LLM will be sufficiently close to the optimal distribution. This appears to be a very strong assumption and I am not convinced that this assumption reflects the status of reality.

R3: This interpretation of Def. 3.3 is not accurate. It differs from the definition in two ways. First, the kernel is not the LLM alone: it is the mutation kernel M_t, an LLM proposal followed by an accept/reject step. Second, the target is not the optimal distribution: at stage t it is the intermediate distribution p_t ∝ p0·exp(β_t·R). The ESS rule keeps p_{t−1} and p_t close to each other, and the particles that enter stage t are already close to p_{t−1}. Uniform ergodicity of this kind is a standard condition in the analysis of SMC samplers.

More importantly, uniform ergodicity is not an assumption of our theorem. Theorem 4.1 states that "no invariance or ergodicity is assumed", and both of its guarantees (see R1) hold without it. We do not claim that it holds for LLM proposals. That is the reason Theorem 4.1 is proved without it.

Def. 3.3 is given in Sec. 3 as background on classical SMC analysis. It also explains the design of the kernel mixture: local diff edits and full rewrites, with and without inspiration programs, can reach programs that one edit style alone cannot reach.

Reviewer_L5ynOpenReview ↗

Thank you for the response

Thank you for rebutting my review. I respond below.

  • The interpretation of Equations 13 and 14. Thank you, I understand better now. However, the following question remains in my mind. In your paper, nowhere have you made any strong assumptions on what the implicit induced reward function is. Under such an arbitrary reward function, I find it difficult to believe that any strong guarantees of convergence or goodness can even exist. For instance, if my evolution simply rewards all programs equally, surely I will not converge to a great endpoint. This is probably what the term "(1/β_T)·[log(1/P_r)" in Equation 14 refers to; but in that case I am not sure how we can interpret whether that term will be small or large. In case I have missed the assumptions made on the reward that make this term small, I would be happy to be corrected.
  • Novelty must be judged for the whole algorithm and its guarantee, not part by part. I disagree - if three components already exist, then simply putting them together does not constitute something novel. The novelty should come from either significant departure from prior norms, or a sufficiently innovative method of combining existing ingredients, which I do not see here. What I do see are some performance guarantees, but my concerns remain:
    • First, I am not convinced that any strong guarantees on performance can ever be achieved without strong assumptions on the improvement as well, which would then rely on the LM used.
    • While this does not necessarily mean that the algorithm cannot perform well in practice (and yours does seem to), for this reason I don't think a theory of convergence or convergence guarantees is very meaningful for the kind of evolution considered here. If there were a particular beautiful structure to them, or other connections to theoretical results, I would agree that studying them would be worthwhile - but I don't see anything of that sort here.
    • Given this, I believe that any argument for the merit of SMCEvolve must be based on strong performance. In this regard, I think a sufficient case could be made, but that case would involve a very different style of paper (one focusing wholly on empirical results, and with the theory relegated to the background).

For these reasons, I will keep my score for now even though I appreciate the clarification advanced by the authors.

Comments on the paper

1 comment

We thank all reviewers. Our replies are posted under each review. The new results used in the replies are listed here.

On the theory (L5yn R1, R3; U9yR R1; JV9D R1, R4), Theorem 4.1 does not assume invariance or ergodicity of the LLM kernel. Its Part 2 (Eq. 14) is the guarantee on the best program, and it does not involve p*. Uniform ergodicity (Def. 3.3) is used only in Corollary H.1. Reviewer U9yR asked for a measurement of the gap between η_T and p* in a controlled setting, and Reviewer JV9D asked for an empirical quantification of it. We did this on a synthetic problem with 300 states and no LLM calls, where η_T and p* are computed exactly (setting and table in U9yR R1 and JV9D R1). There, the gap is zero when the kernel is invariant and grows smoothly as this condition is broken, while the mean reward does not fall.

On results over several seeds (U9yR R5; JV9D R2), we list the individual runs of SMCEvolve on several tasks with different seeds.

On the schedule (U9yR R2–R4; JV9D R2–R3), we ran three experiments on Math tasks, with 3 seeds per setting.

  • Adaptive schedule vs. fixed linear schedule: Adaptive schedule achieves better rewards than fixed with fewer LLM-call budgets. The adaptive schedule needs no T and keeps the effective sample size at 0.9 N, while the fixed schedule drops to 0.12–0.63 N.
  • κ from 0.5 to 0.95: the result shows our SMCEvolve is insensitive to κ changes in terms of final rewarda.
  • Continuing after termination: about twice as many calls after λ = 1 leave the best reward unchanged in 3 of 3 runs.

On ablation study (JV9D R3), all tasks in all four domains use the same configuration and the same prompt templates, with no per-task tuning.

On novelty (L5yn R2), to the best of our knowledge, no existing LLM-based evolutionary system unifies selection, acceptance, and stopping under a principled SMC framework, nor does any provide finite-sample theoretical guarantees.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.