acceptodds
Under review as a conference paper at ICLR 2027

Distribution Matching Evolutionary Algorithms for Rare Event Sampling

Abstract

A novel discovery is one which is both useful and surprising: a generative model’s output is a useful discovery if it has a low probability of being generated (it’s surprising) and a high reward (it’s useful). Global optimization can directly increase the probability of sampling high rewards but typically requires updating model weights. Such gradient based optimization is expensive and bars using capable closed-source models. Instead, modern search methods for discovery sacrifice the global target, and use evolutionary algorithms with local reward maximizing objectives, permitting the search to focus only on high probability samples. In this paper, we interpret various evolutionary algorithms as approximate Markov Chain Monte Carlo, an optimization-free method to sample from complex distributions. This interpretation allows developing Distribution Matching Evolutionary Algorithms (DME), a class of search methods which sample from a global target distribution without updating weights. Empirically, DME has a higher sample efficiency than existing methods on problems requiring many samples to find a solution.

Primary area:
foundation or frontier models, including LLMs
Keywords:
discovery, distribution matching, rare event sampling, search, evolutionary algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_LDGhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Distribution Matching Evolutionary Algorithms (DME), an inference-only approach for discovering high-reward solutions that have low generation probabilities under a fixed generative model.

The authors argue that conventional evolutionary algorithms typically rely on local reward maximization, which can lead to premature concentration on a limited number of high-reward regions. In contrast, distribution-matching methods such as GFlowNets aim to sample diverse high-reward solutions but generally require updating model parameters, introducing substantial computational costs and limiting their applicability to fixed-weight or closed-source models.

To address these limitations, the paper interprets certain evolutionary algorithms as approximate Markov Chain Monte Carlo (MCMC) methods and introduces DME. Specifically, DME generates batches of candidates using a fixed generative model and performs importance resampling based on the ratio between the target reward distribution and the model's proposal probabilities. The paper further introduces modifications for language models, including path marginalization and a length-aware prior.

Critical strengths

1. The paper addresses a practically meaningful problem.

For discovery tasks such as code generation and mathematical optimization, identifying high-quality solutions often requires extensive sampling. Conventional reward-maximizing search methods may become concentrated in a few high-reward regions, potentially overlooking other promising solutions. Investigating how to improve search efficiency without updating generative model parameters is therefore a meaningful direction, particularly when model fine-tuning is computationally expensive or unavailable.

2. The proposed method is simple and easy to integrate with existing generative models.

DME primarily consists of candidate generation, reward evaluation, and importance resampling, without requiring additional policy networks or gradient-based training. Compared with fine-tuning approaches such as RL and GFlowNets, this inference-only design offers practical advantages.

Critical weaknesses

1. Limited methodological novelty compared with existing importance resampling and MCMC methods.

The core mechanism of DME is closely related to established importance sampling, sampling-importance-resampling (SIR), and MCMC techniques. In particular, the paper itself acknowledges the connection to iterated SIR (i-SIR), which similarly generates multiple proposals and selects candidates according to importance weights.

Although applying these principles to evolutionary search with generative models is potentially useful, the underlying algorithmic components are largely established. The main contribution appears to be a reinterpretation and adaptation of existing sampling techniques rather than a fundamentally new methodological framework. I am therefore uncertain whether the degree of methodological novelty is sufficient for ICLR.

2. A substantial gap remains between the theoretical distribution-matching approximation and the practical algorithm.

A central claim of the paper is that DME approximately samples from the target distribution through importance resampling. However, the quality of this approximation depends on whether finite-batch resampling can adequately represent the desired target distribution.

Although Appendix B provides a first-order analysis of the approximation error in terms of batch size and the discrepancy between the proposal and target distributions, the paper does not empirically examine how accurately this approximation holds under the actual experimental settings.

In particular, the paper does not report the Effective Sample Size (ESS) of the importance weights or quantitatively evaluate the distribution-matching error under finite batch sizes. These measurements would be valuable for understanding whether the theoretical approximation remains reliable in practice.

3. The experiments do not directly validate distribution matching, despite it being the central motivation of the paper.

Although distribution matching is presented as the key motivation and distinguishing feature of DME, the main experiments primarily evaluate downstream search performance, such as problem-solving success rates and the quality of discovered mathematical bounds.

These results demonstrate improvements in search efficiency but do not directly establish that DME produces samples that better approximate the intended reward-proportional distribution.

For example, evaluating the discrepancy between the empirical sampling distribution and the target distribution, or measuring coverage across distinct high-reward modes, would provide more direct evidence supporting the central distribution-matching claim. Without such evaluations, it remains difficult to determine whether the observed performance gains are indeed attributable to improved distribution matching rather than more effective search heuristics.

Questions for authors

see weaknesses

4 comments

Thanks for the feedback on the paper, we address it and give clarifications below, with us currently working on incorporating these into the manuscript. Points are paraphrased as we understood them, so if there were any misunderstandings they would hopefully be clear:

“What is the paper’s novelty?”

Thanks for the question, it helped us see this was not clear due to insufficient contextualization on our part. Essentially, the paper proposes and demonstrates a useful, principled way to develop discovery algorithms by treating discovery problems as problems in probabilistic inference, with DME being a specific performant and simple instantiation thereof. For context, a plethora of recent works (e.g. OpenEvolve, ThetaEvolve, and an abundance of other SomethingEvolve papers) propose highly engineered methods for discovery. Simultaneously, there has been a line of recent works showing that when properly benchmarked these highly engineered methods tend to underperform much simpler methods which are also ad hoc - see [AlphaProofNexus, SimpleBaselines, NoUniversalHarness], with Figure 2 here also providing further evidence for many existing methods underperforming simpler ones.

This begs the question, how should one develop discovery algorithms that work well? Our work gives one answer, which is to treat the search as a problem in probabilistic inference, which allows drawing on a rich repertoire of existing tools. This connection and general approach is, in our opinion, the paper’s main contribution; DME is a useful concrete example thereof. To the best of our knowledge, DME is the first time a discovery algorithm for language models has been properly derived instead of ad hoc engineered.

We believe this was not previously clear as the paper was written with the typical discovery/evolutionary algorithms crowd in mind, hence the pedagogical approach. For statistics practitioners using MCMC to sample from a target distribution is admittedly trivial. We did not discuss MCMC more widely in the main body as we felt delving into technical details, e.g. relations to other algorithms, would be confusing for people not previously acquainted with MCMC. Nevertheless, the paper should ideally be appropriate to both audiences - we will update the intro and main body to better give this contextualization+refer to prior work.

Also, although it is not the paper’s main point, DME is technically an extension to i-SIR for non-independent (conditional) proposal distributions. i-SIR relies on independent proposals q(x), while DME uses conditional proposals q(x’|x). We are unaware of any prior work directly extending i-SIR to conditional proposals, although indirect variants thereof surely exist. Accordingly, the analysis in Theorem 1 is likely technically novel, although there are stylistically similar analyses in the literature for other MCMC algorithms. We will better emphasize these differences relative to i-SIR in the related work.

Does DME actually do distribution matching?

The short answer is yes, at least much more than competing methods, with the longer answer given below. We first give high level results and then some technical details.

To quantitatively test to what extent DME matches the target distribution we estimate for the regex task KL(q∥π)KL(q\|\pi) for different methods, where qq is the specific methods’ proposal distribution and π\pi is the target. We compare BoN as a baseline, GFNs as the one other distribution matching method, and DME. For DME we have only an upper bound on the KL as calculating one of the terms in the KL for it is intractable, see details below.

Averaged over the test regexes, DME has the lowest average KL by far:

MethodMean KL (nats)
BoN693
GFN601
DME≤121\leq 121

We see that GFNs do a bit better than BoN, in spite of having a worse success rate, as it is designed to do distribution matching. We speculate it is still so much worse than DME due to the training instabilities discussed in the main text. GFNs are generally notoriously difficult to train, see [GFNsTrainHard].

We hope this last point helps answer both your second and third concern, if not then please do let us know. Generally, with respect to distribution matching, we only argue for DME being better at distribution matching than GFNs and having some other nice properties, e.g. being more stable due to not requiring weight updates. There are reasons to believe all inference only methods, including DME, would struggle matching distributions beyond some extent due to adversarial examples. For example, both the gmail regex given in footnote 3 and ^(?:[\w.+\-]+@gmail\.com|k7Qp2XvR9mLw4TzN8bJc3HfY6sDg)$ would match gmail addresses but the latter would also accept a specific high entropy string, which the LLM has an incredibly low probability of generating. It would be very difficult for DME to sample from the vast space of such technically correct but extremely low probability strings, hence limiting the extent to which it can do distribution matching. We discuss this limitation in the last paragraph in the discussion - inference only methods like DME can be good search methods, but some outputs would be very difficult to sample without additional learning.

Technical details:

For the given target distribution we have that KL(q∥π)=log⁡Z−H(q)−βEq[log⁡R(x)]KL(q\|\pi)=\log Z-H(q)-\beta E_q[\log R(x)], where log⁡Z\log Z is the target distribution’s log-partition function. For BoN and GFN qq is simply the density the LLM gives and is hence known, while for DME it is the transition kernel and generally not exactly known in closed-form. Due to this, for BoN and GFN we have an estimate of the KL while for DME we have an upper bound, where we discard the entropy term. We estimate the (shared) log⁡Z\log Z term per regex by taking the log-expectation of DME’s importance weights, as Z=Eπ[R(x)β]=Ep[R(x’)β/p(x’∣x)]Z=E_\pi[R(x)^\beta]=E_{p}[R(x’)^\beta/p(x’|x)], with the term inside the expectation being the importance weights. Note both DME and GFN use the same target distribution here. Note we report the total KL, not averaged per token, hence why it may seem large - the average is over different target regexes.

Thanks for the feedback, please feel free to ask more questions if you have any.

References

[AlphaProofNexus] Tsoukalas, George, et al. "Advancing mathematics research with AI-driven formal proof search."

[SimpleBaselines] Gideoni, Yonatan, Sebastian Risi, and Yarin Gal. "Simple Baselines are Competitive with Code Evolution."

[NoUniversalHarness] Gupta, Akshat, et al. "Automated Discovery Has No Universally Superior Harness."

[GFNsTrainHard] Shen, Max W., et al. "Towards understanding and improving gflownet training."

Dear reviewer LDGh, as the discussion period is drawing to a close it would be much appreciated if you could respond to our comments. We hope these properly answer your questions.

Thank you for the clarification and additional analysis, which address some of my concerns. While I appreciate the probabilistic-inference perspective, the methodological novelty relative to existing SIR/i-SIR methods remains unclear to me. In particular, the response does not sufficiently explain what additional algorithmic or theoretical contribution the use of state-dependent proposals introduces beyond prior methods. My concern about novelty therefore remains, and I will maintain my original score.

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

This paper proposes a method for efficiently creating high-reward samples from a target distribution without updating the parameters of the proposal distribution. The so-called distribution matching evolution (DME) is explained to have similarities to the Metropolis–Hastings algorithm but aims at being more sample-efficient. For language models, the paper then proposes two improvements to DME that are aimed at making it more suitable for this domain.

DME is empirically tested against several competing approaches and is found to have a generally favorable performance, usually outperforming the competition.

Critical strengths
  1. Simplicity. DME is a simple iterative general-purpose search heuristic. This makes it easy to implement and apply it to a variety of problems.

  2. Solid performance. DME typically produces results with a higher reward than the competition, and it usually also does so during the trajectory. That is, its any-time performance seems also favorable.

Critical weaknesses
  1. Limited evaluation.
  • The empirical evaluation comes sometimes off as a bit misleading. For example, the abstract claims that DME is more sample-efficient for problems that require many samples to find a solution. This can be interpreted in various ways. Figure 3 suggests that DME is more sample efficient when using a smaller budget. For larger budgets, it seems to be very close to the (selected) competition, which could potentially even diminish the benefit of DME.
  • Moreover, Table 2 highlights ranks, but the final numbers are oftentimes quite close. Using a test of statistical significance, which is missing, would provide more insights into how relevant such seemingly small deviations are. In addition, I am a bit surprised about the final probabilities in Figure 4, as Table 2 suggests that the probability of DME to be strictly better than the competition should be, at the end, at around 7/97/9, but it is depicted to be higher.
  • In addition, the parameter choice of the batch size is not explained. The simple evolutionary algorithms are thus treated as having no parameters, although this is not true.
  • In the same vein, there are more possibilities to play with the plus and the comma strategy, particularly allowing to maintain more than a single solution. Such approaches are dismissed, probably due to the analogy to the Metropolis–Hastings algorithm.

2 Too little focus on the main contribution. Although the paper is easy to read, a fair amount of the content is not primarily focused on the main selling point of the paper, namely, DME. The introduction provides pseudocode of an algorithm that barely matters in this context, and the preliminaries, in particular Figure 1, seem rather verbose. Also Section 3, is longer than necessary, with Section 3.1 being entirely superfluous, in my opinion. In turn, a lot of more interesting information is deferred to the appendix. In my opinion, this paper could be far improved by kicking out a substantial part of the more verbose sections and replacing them with more insights from the appendix.

Honorable mention. This paper does not come with a code appendix. Although the details of the experiments are decently well explained, this makes the reproducibility at the moment challenging. The paper claims that such code will be released upon acceptance, and I do not doubt this, but it is still a bit unfortunate from a review point of view.

Questions for authors

I would like the authors to address my points listed as critical weaknesses.

  1. What is the authors’ response to my points made with respect to the limited evaluation of DME?

  2. Why does Section 6.2 only consider two competitors? Is there a correlation between this task and the one from Section 6.1 that suggests that the top-performing algorithms there are likely to be best suited for this task as well?

  3. Will the authors update the presentation of their paper? If so, how?

Additional comments. The following points are merely suggestions. I did not know where to put them else. They did not affect my rating of the paper.

  • Using contraction such as “it’s” (twice in the abstract) is too colloquial to me and should be changed to the long version.

  • Plots such as in Figure 3 are hard to read in grayscale. I recommend using different line types in addition to different colors.

  • In Table 2, the row for “First autocorr. ineq.” has no underlined entry, although it seems that SCS should place second.

  • The references use an inconsistent capitalization for items of the same category, and proper nouns are also not always capitalized. I recommend polishing the references.


Update During the Rebuttal Phase

In increased my rating to a weak accept, as my concerns have been sufficiently well addressed.

7 comments

Thanks for the feedback on the paper, we address it and give clarifications below, with us currently working on incorporating these into the manuscript. Points are paraphrased as we understood them, so if there were any misunderstandings they would hopefully be clear:

“DME seems to be more sample efficient at small, not large budgets”

Although the coding competition problems specifically show DME’s performance over a relatively small budget (300 programs per coding problem), the other experiments show DME works well both at small and very large budgets. The regex is very high budget (100k samples per regex), and the math bounds uses a decently high budget (5k programs per problem). For comparison, [ShinkaEvolve] used ~150 programs per problem for one of the math bounds problem. Figure 4 shows that DME tends to outperform the two baselines at almost all budgets for the math problems. Thus, the problems cover all budgets.

“Are the chosen baselines competitive”?

We believe so, as we have taken special effort to try and make the baselines be as competitive as possible. For the regex, all baselines had their hyperparameters tuned, see Appendix D.2. We intentionally designed the task so it would allow comparing many different baselines, with many considered performant in their own papers. For the math bounds, the baselines are taken from a paper titled “Simple Baselines are Competitive for Code Evolution”, which shows the two baselines beating more established methods on a wide variety of problems, including the math bounds they are benchmarked on here. The coding competitions baselines are addressed in the next clarification:

“Why do the coding competitions use only the (1,N) and (1+N) baselines, is it because those performed best for the regex task?”

Yes, that is why those two baselines were chosen, see the second paragraph in section 6.2. We opted to use just the two baselines that seemed like they would be the most competitive as the experiment is fairly computationally expensive, taking a few days to run per method. Some of the other baselines, like the gradient based ones, would be difficult to run given so few samples.

“What is the main point of the paper, why does it focus so much on introducing existing tools/methods?”

Thanks for the question, it helped us see this was not clear due to insufficient contextualization on our part. Essentially, the paper proposes and demonstrates a useful, principled way to develop discovery algorithms by treating discovery problems as problems in probabilistic inference, with DME being a specific performant and simple instantiation thereof. We believe this was not previously clear as the paper was written with the typical discovery/evolutionary algorithms crowd in mind, hence the pedagogical approach. For statistics practitioners, something like using MCMC to sample from a target distribution is admittedly trivial. Nevertheless, the paper should ideally be appropriate to both audiences - we will update the intro and main body to better give this contextualization+refer to prior work. We will also highlight which parts are purely pedagogical and can generally be skipped by readers with the right background knowledge, e.g. section 3 and much of the intro, and move as many insights from the Appendix to the main paper as the page limit will allow.

In case of interest, the following two paragraphs give some additional context on the paper’s main point as we see it and would like it to be understood. A plethora of recent works (e.g. OpenEvolve, ThetaEvolve, and an abundance of other SomethingEvolve papers) propose highly engineered methods for discovery. Simultaneously, there has been a line of recent works showing that when properly benchmarked these highly engineered methods tend to underperform much simpler methods which are also ad hoc - see [AlphaProofNexus, SimpleBaselines, NoUniversalHarness], with Figure 2 here also providing further evidence for many existing methods underperforming simpler ones.

This begs the question, how should one develop discovery algorithms that work well? Our work gives one answer, which is to treat the search as a problem in probabilistic inference, which allows drawing on a rich repertoire of existing tools. This connection and general approach is, in our opinion, the paper’s main contribution; DME is a useful concrete example thereof. To the best of our knowledge, DME is the first time a discovery algorithm for language models has been properly derived instead of ad hoc engineered.

“Why does Table 2 have no magnitude comparisons for the math bounds?”

When discovering math bounds even small changes can be meaningful, and some small differences can be much harder to achieve than others. Accordingly, all prior work we are aware of, including Deepmind’s AlphaEvolve (the paper that introduced these problems), do not compare magnitudes but chiefly relative rankings. Many of the magnitude differences between methods here are of the same order if not better than the differences AlphaEvolve reported between their results and the prior best human found bound.

“Shouldn’t the probability of improvement be closer to 7/9?”

Note that ties are counted as 50%/50% splits, so as DME is outright better on 7/9 problems and tied on 2/9, its probability of improvement is approximately 7/9+0.5*2/9=8/9, which as Figure 4 shows is approximately 88%.

“How was the batch size selected, does it matter? Why are the simple evolutionary algorithms presented as having no parameters?”

The batch size was not especially selected for as it is a joint hyperparameter between all methods. To test its effect we ran DME for the regex task with different batch sizes, see here for the result (https://anonymous.4open.science/r/dme_anon-8C73/dme_bs_sweep.png), which we will add to the Appendix. In short, DME seems to unsurprisingly work better for larger batch sizes, and already works decently well for batch sizes >=32 for the regex task. Note that all batch sizes used the same total budget of 100k samples per run.

What about more variations to the plus and comma evolutionary strategies?

We are not entirely sure what the reviewer meant here, so please feel free to correct us if there was a misunderstanding. Presuming you meant “why not base DME on a different version of the plus or comma evolutionary strategies?”, this would certainly be possible, as the derivation given can be changed to build on other kinds of evolutionary algorithms, hence why we classify DMEs as a class of algorithms. The DME given here is a specific member of that more general class. We leave building even more performant variations of DME to future work.

How will the paper be updated following feedback from this and other reviews?

We will incorporate the following changes:

  • Updating the abstract and intro to better contextualize the paper, namely how existing discovery methods are ad hoc, here we demonstrate a framework for building more principled discovery algorithms (broadly, treating the search problem as a problem in probabilistic inference).
  • Better specify in the background and section 3 how both are chiefly pedagogical and can be skipped for knowledgeable readers.
  • Given space, move some sections from the Appendix into the main body, namely Theorem 1, its corollary, and related work.
  • The additional comments you pointed out, some updates to the Appendix (e.g. adding the batch size ablation), and other points that may arise later in these discussions.

Code?

Please see anonymized repo here: https://anonymous.4open.science/r/dme_anon-8C73/

Additionally, we would like to clarify the following point:

“DME is similar to Metropolis-Hastings MCMC”

DME is a specific approximate instantiation of Metropolis-Hastings MCMC, and is effectively a tweak to (1,N) hill climbing to make it better implement Metropolis-Hastings, e.g. without requiring the generative model to be symmetric (which in practice certainly does not hold). In this sense it is more than loosely based on it.

Thanks for the feedback, please feel free to push back or ask additional questions if relevant. We hope this helped clarify the paper.

References

[ShinkaEvolve] Lange, Robert, Yuki Imajuku, and Edoardo Cetin. "Shinkaevolve: Towards open-ended and sample-efficient program evolution."

[AlphaProofNexus] Tsoukalas, George, et al. "Advancing mathematics research with AI-driven formal proof search."

[SimpleBaselines] Gideoni, Yonatan, Sebastian Risi, and Yarin Gal. "Simple Baselines are Competitive with Code Evolution."

[NoUniversalHarness] Gupta, Akshat, et al. "Automated Discovery Has No Universally Superior Harness."

I thank the authors for the feedback and for making the code accessible. Many of my questions have been addressed rather satisfactorily, but I am under the impression that we missed each other’s points from time to time. In particular, I cannot always match the authors’ summary of my points to the actual question or remark that I had. This makes some of the replies odd. Given that the authors’ response is quite verbose in general, I prefer it if they would more clearly say which point they are currently addressing.

Here are some points that I feel were misunderstood or not properly addressed. I also added a new follow-up question that is more of a natural result of my previous questions.

  1. Is DME significantly more sample-efficient for larger budget sizes? My point was that Figure 3 shows rather comparable performance among all three listed methods for larger budgets. The authors replied by pointing to Figure 4. This addresses my point only partially. I am wondering whether there seems to be a general, impactful, benefit of DME even for larger budgets. Figure 3 gives off a mixed impression at the moment.

  2. Do the performances from Section 6.1 matter for Section 6.2? This was part of my initial second question, and it has not been addressed so far. I was wondering whether basing the selection for Section 6.2 on the performance from Section 6.1 makes sense. Is there any correlation between these problems that suggests that algorithms that perform well on one task will also perform well on the other? Or were other factors part of this decision?

  3. What about evolutionary baselines that maintain more than a single solution? My initial question meant to ask why the authors restrict themselves to evolutionary baselines that only maintain a single solution, that is, (1+N)(1+N) and (1,N)(1,N) methods. A more general approach is to use (M+N)(M+N) and (M,N)(M,N) methods. Hence, I was wondering why the paper only considers the case M=1M=1. Is it clear that maintaining multiple solutions is going to be worse? Or is this just not an interesting setting?

  4. Can the authors upload an updated PDF? Given that I am asking for a not unsubstantial rewrite of the paper and that this rebuttal process allows the authors to update their submitted PDF, is it okay for the authors to upload a PDF that highlights the changes that they made (or claim to make) to the paper? From my point, it is sufficient to focus on the changes that regard the presentation. However, maybe it also makes sense to incorporate other reviewer feedback that seems reasonable to the authors.

Reviewer_maU5OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper presents an MCMC perspective on evolutionary algorithms. The authors claim that their novel interpretation is instrumental to define a new type of algorithm that can be used to sample a target distribution. They validate this proposal on some LLM realistic examples, with some necessary tweaks.

Critical strengths

The paper is well written, I particularly appreciate the pedagogical approach of the authors in the introduction, as well as in the theory part on MCMC, DME and before the application to LLMs. The experiments are also well documented and show scalability of the methods to a real setup.

Critical weaknesses

Unfortunately, the main issue of the paper is that its content is not novel in my opinion, or, better said, not enough to justify a publication in this venue. To better specify:

  • Positioning among literature (1): for a paper on MCMC, not mentioning related works in the main body is a strong limitation, given the extension of the literature on the topic. In particular, just to mention some related works which are not cited and that appears particularly relevant/overlapping with the first claim of the paper "First, we demonstrate how some evolutionary algorithms can be interpreted as im- plementing approximate MCMC.":

    • Evolutionary Monte Carlo (Liang & Wong, 2000, Statistica Sinica)
    • Braak, C.J.F.T. A Markov Chain Monte Carlo version of the genetic algorithm Differential Evolution: easy Bayesian computing for real parameter spaces. Stat Comput 16, 239–249 (2006).
    • Drugan, M.M., Thierens, D. (2004). Evolutionary Markov Chain Monte Carlo. In: Liardet, P., Collet, P., Fonlupt, C., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2003. Lecture Notes in Computer Science, vol 2936. Springer, Berlin, Heidelberg.
    • Del Moral (2004), Feynman-Kac Formulae Genealogical and Interacting Particle Systems with Applications, Springer.
  • Positioning among literature (2): it is not transparent the very very close similarity between DME and i-SIR. The paper mentions this review "Iterated sampling importance resampling with adaptive number of proposals, Pietari Laitinen, Matti Vihola, 2025" just in a very small paragraph in the appendix, and it is evident how Algorithm 3 (DME) is very close to a specification of Algo 1 in the review. To be precise, the proposal of the authors seems a biased version of I-SIR since they do not include the previous state in the pool.

  • Title is misleading: the sentence "rare event" appears just twice in the paper, and so the title is unjustified in my opinion; in other words, from the title it seems that most of the paper will discuss rare event sampling, which is not the case.

Questions for authors
  • Could you please specify the theoretical novelty of the paper as opposed to the reference I mentioned above? In other words, could you motivate the need to give a new name to something that appears to be a particular case of an existing method?

  • Could you clarify why is it needed to introduce the bias in an unbiased algorithm?

At this stage, the experimental strengths of the paper are not central and cannot justify acceptance on my side, especially given the lack of literature comparison.

4 comments

Thanks for the feedback and pushback on the paper, it helped us understand how some points were not being well communicated. We address your feedback and give clarifications below, with us currently working on incorporating these into the manuscript. Points are paraphrased as we understood them, so if there were any misunderstandings they would hopefully be clear:

“What is the paper’s main contribution?”

Thanks for the question, it helped us see this was not clear due to insufficient contextualization on our part. Essentially, the paper proposes and demonstrates a useful, principled way to develop discovery algorithms by treating discovery problems as problems in probabilistic inference, with DME being a specific performant and simple instantiation thereof. For context, a plethora of recent works (e.g. OpenEvolve, ThetaEvolve, and an abundance of other SomethingEvolve papers) propose highly engineered methods for discovery. Simultaneously, there has been a line of recent works showing that when properly benchmarked these highly engineered methods tend to underperform much simpler methods which are also ad hoc - see [AlphaProofNexus, SimpleBaselines, NoUniversalHarness], with Figure 2 here also providing further evidence for many existing methods underperforming simpler ones.

This begs the question, how should one develop discovery algorithms that work well? Our work gives one answer, which is to treat the search as a problem in probabilistic inference, which allows drawing on a rich repertoire of existing tools. This connection and general approach is, in our opinion, the paper’s main contribution; DME is a useful concrete example thereof. To the best of our knowledge, DME is the first time a discovery algorithm for language models has been properly derived instead of ad hoc engineered.

We believe this was not previously clear as the paper was written with the typical discovery/evolutionary algorithms crowd in mind, hence the pedagogical approach. For statistics practitioners using MCMC to sample from a target distribution is admittedly trivial. We did not discuss MCMC more widely in the main body as we felt delving into technical details, e.g. relations to other algorithms, would be confusing for people not previously acquainted with MCMC. Nevertheless, the paper should ideally be appropriate to both audiences - we will update the intro and main body to better give this contextualization+refer to prior work.

“Is DME meaningfully different to i-SIR?”

Although we stress the paper’s novelty is in using existing tools in a novel way in a relatively new domain, there are still ways in which DME meaningfully differs to i-SIR. i-SIR relies on independent proposals q(x), while DME uses conditional proposals q(x’|x). We are unaware of any prior work directly extending i-SIR to conditional proposals, although indirect variants thereof surely exist. Accordingly, the analysis in Theorem 1 is likely technically novel, although there are stylistically similar analyses in the literature for other MCMC algorithms. We will better emphasise these differences relative to i-SIR in the related work.

“Why not use the parent in the selection pool, as i-SIR does? Doesn’t discarding the parent introduce bias in an unbiased algorithm?”

When using conditional proposals keeping the parent in the selection pool still introduces bias - i-SIR relies on all the samples, including the parent, coming from the same distribution for its unbiasedness (see section 2 in [UniformErgodicity]). We believe keeping the parent in DME would introduce more bias in the algorithm, resulting in an additional target-independent term in Theorem 1 (equation 7), although I have not thoroughly derived this. Generally, DME is designed to be a practical algorithm without requiring some bits that would make it much more expensive, e.g. calculating reverse probabilities (p(x|x’) in addition to p(x’|x)). Generally, we are unsure if it is possible making an unbiased algorithm without needing reverse probabilities or other changes which would make the algorithm much more expensive or less performant. A silly tweak would be making the proposal distribution independent (no conditioning on prior examples) and then using i-SIR, which would be unbiased but likely very inefficient.

“What’s the relation and novelty of section 3, the evolutionary algorithms as approximate MCMC interpretation, relative to the listed prior work?”

The differences between these existing works and ours are subtle but important, and we will better emphasize them in the updated manuscript. Broadly, these works use tools from MCMC to develop better evolutionary algorithms and vice versa, which indeed we also do. What this work includes which prior works do not is the specific way in which this is done, where existing algorithms are interpreted as implementing MCMC as they are, and this connection is then directly used to develop better evolutionary algorithms. Here “better” means developing algorithms with weaker assumptions, e.g. not requiring the generative model’s proposal distribution to be symmetric. The listed prior work takes different approaches, with the closest one likely being that of Liang and Wong, where they show how different operators in evolutionary algorithms can be ported into MCMC frameworks, which we agree section 3 shows a specific instance thereof.

Why is rare event sampling in the title if it’s barely discussed in the paper?

The paper throughout discusses sampling low probability high reward outputs - this is a problem in rare event sampling. We will make this connection clearer throughout. Accordingly some of the tools for both are related, e.g. the RL/variational inference interpretation given at the start of the related work section is effectively the cross-entropy method, just with the opposite KL.

Thanks again for the feedback, we believe it will help improve the paper, especially for audiences coming from more of a statistics background. If you have any further questions or think anything should be better clarified please do say so.

References

[UniformErgodicity] Andrieu, Christophe, Anthony Lee, and Matti Vihola. "Uniform ergodicity of the iterated conditional SMC and geometric ergodicity of particle Gibbs samplers."

[AlphaProofNexus] Tsoukalas, George, et al. "Advancing mathematics research with AI-driven formal proof search."

[SimpleBaselines] Gideoni, Yonatan, Sebastian Risi, and Yarin Gal. "Simple Baselines are Competitive with Code Evolution."

[NoUniversalHarness] Gupta, Akshat, et al. "Automated Discovery Has No Universally Superior Harness."

  1. The novelty does not hold, even in its reformulated version. The paper’s stated contribution, evolutionary algorithms as approximate MCMC, is essentially conceded by the authors to be a special case of Liang & Wong (2000), and it is close to ter Braak (2006). The new contribution proposed in the rebuttal, treating discovery as probabilistic inference, is also already explored: SMC steering of LLMs (Lew et al., 2023), twisted SMC (Zhao et al., 2024), and particle filtering for inference-time scaling (Puri et al., 2025). None of these are discussed. At the algorithmic level, schemes with multiple conditional proposals and weight-based selection already exist: multiple-try Metropolis (Liu, Liang & Wong, 2000), Tjelmeland (2004), and Calderhead (2014). So the difference from i-SIR is not enough to justify a new method.

  2. The theoretical foundation of the algorithm is incomplete. DME is admittedly biased. To the central question of why the parent is excluded from the pool, the authors answer with a conjecture they have not derived. They do not quantify the gap between DME’s stationary distribution and the target. They also do not compare against the exact version, which would be feasible at moderate cost given access to logits, since scoring a sequence is cheaper than generating it. Without this, “approximate MCMC” remains a descriptive label rather than a result.

  3. The required changes amount to a different paper. The rebuttal implies a new framing, a new statement of contributions, related work moved into the main body, positioning relative to i-SIR, MTM, and Liang & Wong, and a justification of the title. These are not camera-ready corrections. They are a rewrite that calls for a new review cycle.

I will keep my score.

We appreciate the additional pushback but believe some of the claims here are imprecise, and we wish to clarify a few points further. While the listed papers in point 1 combine probabilistic inference and LLMs, they do not do so for discovery. None of the listed papers study discovery problems or are targeted at discovery, and accordingly use probabilistic inference techniques over a different space than the one studied here, namely using SMC over a single (sub)trajectory while we study search over entire trajectories.

On point 2, quantifying the gap between DME and the target distribution, please see our response to reviewer LDGh, where this comparison is done. There we quantitatively show that DME has a much smaller KL between its proposals and the target distribution than other methods. The ways in which DME is approximate MCMC, namely the approximations, are mentioned in section 4 of the current paper. If the approximations were not well defined, an analysis as is done in Appendix B (“Quality of approximation”) would not be possible.

On point 3, in practice this would be a sentence to the abstract, a paragraph to the intro+maybe discussion, and moving a section from the appendix to the main body. This level of changes is typical between submissions and final manuscripts.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.