- 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
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 for different methods, where is the specific methods’ proposal distribution and 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:
| Method | Mean KL (nats) |
|---|---|
| BoN | 693 |
| GFN | 601 |
| DME |
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 , where is the target distribution’s log-partition function. For BoN and GFN 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) term per regex by taking the log-expectation of DME’s importance weights, as , 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.
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:
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.