Distribution Matching Evolutionary Algorithms for Rare Event Sampling

• Novel discoveries are useful outputs that have low generation probability because the model has not seen them in its training data.Their utility can be measured using a verifier or reward.Source: §1 · p. 1
• Local reward maximization can get stuck in local modes, motivating sampling from a target distribution over all high-reward solutions instead.Evolutionary algorithms commonly select candidates by reward, which maximizes local reward.Source: §1 · p. 1
• Weight-updating distribution matching is expensive and bars the use of capable fixed-weight closed-source models, while MCMC's multi-step cost fits searches that stop once a discovery is made.MCMC is an optimization-free approach to sampling from a target distribution.Source: §1 · p. 2
• DME is more sample efficient than many existing methods on discovery problems requiring many samples to find a solution.The paper derives DME by interpreting evolutionary algorithms as approximate MCMC, without updating model weights.Source: §1 · p. 2

2.1 Sampling as Optimization

• Sampling from a target distribution can optimize a function: simulated annealing samples from πT(x) ∝ exp(−βf(x)), and as T approaches zero the samples minimize f.Sampling from πT can itself be nontrivial.Source: §2.1 · p. 2
• The ideal target πS samples uniformly from all maximum-reward solutions, but it is unattainable in practice and excludes every suboptimal sample.The maximum reward may be unknown, and πS provides no probability mass to suboptimal samples that could indicate progress.Source: §2.1 · p. 2, §2.2 · p. 2

2.2 Relaxing the Optimal Target

• The relaxed target π(x) = R(x)^β/Z trades sampling ease against fidelity: higher β better approximates πS but is harder to sample, while lower β assigns more mass to suboptimal solutions.Figure 1 contrasts the ideal target, a relaxation, and an over-relaxed target that becomes almost uniform and wastes samples.Source: §2.2 · p. 2, Figure 1 · p. 3

2.3 Markov Chain Monte Carlo

• Rejection sampling proposes from q(x) and accepts according to the target π(x), but can be inefficient when π is much less dense than the proposal.MCMC instead takes local steps, improving robustness to the proposal at the cost of multiple steps per independent sample.Source: §2.3 · p. 3

3 Evolutionary Algorithms as Approximate Markov Chain Monte Carlo

• Some evolutionary algorithms can be interpreted as approximate MCMC, with each implicitly defining a transition kernel and target distribution.The interpretation clarifies the approximations required and supports deriving algorithms suited to discovery.Source: §3 · p. 4

3.1 Random Search

• Random search has transition kernel q(x′|x) = p(x′) and target π(x) = p(x), so its MCMC interpretation requires no approximation.Random sampling always accepts generated samples.Source: §3.1 · p. 4

3.2 Hill Climbing Evolutionary Strategies

• Hill climbing's best-of-N selection can be represented by sampling N candidates and resampling in proportion to R(x′)^β, yielding a transition kernel proportional to p(x′|x)R(x′)^β.As β increases, this resampling simulates the hard maximum used by hill climbing.Source: §3.2 · p. 4
• For (1, N), always accepting proposals requires a symmetric generative conditional distribution, yielding target π(x) ∝ R(x)^β.The symmetry condition is p(x′|x) = p(x|x′).Source: §3.2 · p. 4
• For (1 + N), rejecting proposals worse than the parent corresponds in the infinite-β limit to target π(x) ∝ R(x)^kβ, where k > 1.Unlike (1, N), this strategy retains the parent when an offspring has lower reward.Source: §3.2 · p. 4

4 Distribution Matching Evolutionary Algorithms

• DME derives an evolutionary search that samples from the proxy target π(x) ∝ R(x)^β without requiring a symmetric transition kernel.It approximates the target transition by drawing proposals from a generative model and resampling them with importance weights; the algorithm returns the highest-reward sample.Source: §4 · p. 5

4.1 Quality of Approximation

• Finite batches make DME’s sampling approximate; the error vanishes when the proposal distribution matches the target and improves as their distributions become closer.Larger proposal batches and a better generative model or conditioning can improve the approximation; lowering β can also make the target more similar to the model.Source: §4.1 · pp. 5–6
• MCMC’s sequential steps compensate for an imperfect transition kernel, with better approximations requiring fewer steps to sample effectively from the target.The correction is zero when the target and proposal distributions match; its magnitude is characterized as a chi-squared divergence and a weighted mean-square error between them.Source: §4.1 · p. 6

4.2 Novelty, Heuristic Interpretations, and Proposal-Agnosticism

• As β → ∞, DME selects the highest-reward sample and favors the lower-probability candidate when rewards tie; finite β gives stochastic hill climbing.If one high-reward sample has much lower probability than the others, this limit acts like hill climbing with a lowest-probability tie-breaker.Source: §4.2 · p. 6
• Importance weights make DME approximately proposal-agnostic, though approximation quality means sample efficiency can still vary across generative models.Unlike typical evolutionary algorithms, DME corrects for the model’s probability of generating different samples.Source: §4.2 · p. 6

5 DME for Language Models

• The language-model adaptations modify DME’s importance weights while leaving its general algorithm unchanged.Other design choices can likewise produce valid distribution-matching evolutionary algorithms.Source: §5 · p. 6

5.1 Path Marginalization

• Path marginalization estimates the probability of a final answer regardless of the intermediate reasoning or tool-use trajectory that produced it.The probability is approximated with a single Monte Carlo sample; only the probability of the relevant output should be used, not the entire generated trajectory.Source: §5.1 · p. 7

5.2 Length-Respecting Uniform Prior

• A uniform prior over token sequences can artificially up-weight longer sequences, so DME defines a prior to reduce length dependence when shorter solutions are preferred.The passage introduces the prior’s construction but does not specify its resulting formula.Source: §5.2 · p. 7

5.3 Modified Importance Sampling Weights

• With path marginalization, the high-β heuristic picks the lowest-probability highest-reward sample using the probability of the relevant answer, not the entire generated sequence.Path marginalization is the default; the regular uniform prior remains the default unless specified otherwise.Source: §5.3 · p. 7

6.1 Regular Expressions

• The regex comparison includes gradient-based methods, prompt-search baselines, random sampling, hill climbing, and DME.The methods were tuned and generally used matched prompts; reward-based methods use test-case accuracy.Source: §6.1 · p. 8
• The regex benchmark filters 20 problems where best-of-N succeeds 5%–50% of the time, focusing on difficult but solvable cases.Methods use Qwen3-0.6B, a 100,000-sample cap, and one TitanRTX GPU; the setup supports probability and runtime comparisons.Source: §6.1 · p. 8

6.1.1 Results

• DME achieves the highest average success rate across regexes, nearly twice best-of-N’s rate.Figure 2 reports average success rates across regexes, with means and 95% confidence intervals.Source: Figure 2 · p. 8, §6.1.1 · p. 9
• For regexes, (1, N) hill climbing is the only baseline besides DME that notably beats best-of-N; the authors speculate its refreshed hint makes search more varied than (1 + N).(1 + N) changes its hint only when it improves on the best regex seen so far.Source: §6.1.1 · p. 9

6.2 Coding Competitions

• At about a 30% solve rate, DME needs 50 programs per question, versus about 100 for either evolutionary baseline.The comparison uses competitive coding problems; Figure 3 plots solve rate against programs generated per question.Source: §6.2 · p. 9, Figure 3 · p. 9

7 Math Bounds

• The comparison uses nine problems analyzed by Novikov et al., GPT-OSS 20B proposals, and a 5,000-program budget for each method.DME uses β = 10^6 and four chains; the model’s knowledge cutoff predates the cited solutions by about a year.Source: §7 · p. 10
• DME finds or ties for the best bound on all nine problems against best-of-N and sequential conditioned sampling, given 5,000 programs.Table 2 reports the best discovered bounds for each method; results are truncated to the first different significant digit for all problems except circle packing.Source: Table 2 · p. 10, §7 · p. 10
• At almost all sample budgets, DME is likely to improve on both baselines, measured by the probability it outperforms a method on a randomly chosen problem.Ties count as each method having an equal probability of winning.Source: §7 · p. 10

Related distribution matching

• Distribution-matching objectives can also be optimized with variational inference or reinforcement learning, but those approaches update model weights.For the DME target, the stated KL objective corresponds to a form of soft reinforcement learning.Source: §8 · pp. 10–11

Related search methods

• DME resembles generative stochastic superoptimization: both use MCMC to search for optimal programs, while DME also uses generative models to improve sample efficiency.Stochastic superoptimization uses MCMC over a finite instruction set.Source: §8 · p. 11

Related MCMC methods

• DME is related to i-SIR, which resamples among candidates using importance weights; DME can return a previously rejected candidate if it has the highest observed reward.i-SIR was proposed to use both rejected and accepted candidates when estimating expectations.Source: §8 · p. 11

Prior discovery methods

• Prior discovery work attributes success to strong generative models and large sample counts, while search-friendly problem formulations can also improve sample efficiency.The cited studies report simple heuristics performing comparably to more elaborate evolutionary pipelines under matched models and sample budgets.Source: §8 · p. 11

9 Discussion

• Proposed extensions include incorporating other MCMC or evolutionary methods, using Hamiltonian Monte Carlo when gradients are permissible, and tempering probabilities with p → p^α for 0 < α ≤ 1.These directions are left for future work.Source: §9 · p. 12
• Further work could test distribution matching with noisy or inexact rewards, where diverse high-proxy-reward candidates may be preferable to only the proxy maximum.The discussion contrasts this with local reward maximization, which it says would reward-hack the proxy.Source: §9 · p. 12
• DME requires unnormalized probability densities, which can add a forward pass for diffusion or flow models and may be unavailable from some closed-source language models.Adapting DME to these settings would require a new transition kernel and may be nontrivial.Source: §9 · p. 12
• Training-free methods may need an unreasonable number of samples to find discoveries with sufficiently low probability, especially when they are extremely dissimilar to training data.The discussion frames these methods as expanding reachable discoveries within a sample budget, followed by adding discoveries to training data and later fine-tuning or retraining.Source: §9 · p. 12

A Proofs

• The theorem assumes full support, finite χ2(π||p(·|x)) for all x, and a finite third absolute moment of the importance weight; for the expectation part where ∆ ≥ −S/2, E−i[|∆/S|3] = O(N^-3/2).Source: A Proofs · pp. 16–18

B.1 Example Prompts

• The validation materials pair prompts with dataset reference regexes, and hint-based methods use the previous regex as a prompt hint after the first step.The prompts describe regex behavior and give match and non-match examples; accuracy is measured over 25 examples per regex.Source: §B.1 · pp. 19–20, Table 3 · p. 20

B.2 Regex Baselines

• Baseline configurations were tuned on three validation regexes; the appendix reports sweeps for RS-GRPO, TTT-Discover, and GFlowNets.For RS-GRPO, β = 8 and learning rate 10^-6 performed best; for TTT-Discover, learning rate 10^-7 and KL coefficient 0 performed best; subtrajectory balance performed slightly better for GFlowNets.Source: §B.2 · pp. 20–21

B.3 Ablations

• DME’s average regex performance stabilizes above about β = 10^3, although performance does not increase monotonically on every problem.On one validation regex, success is 96% at β = 100 and 86% at β = 3000.Source: §B.3 · p. 21, Figure 5 · p. 21
• Path marginalization and the length-respecting prior make little apparent difference to regex-task performance, with Table 4 reporting average success rates and roughly ±5% confidence intervals.The authors attribute the limited effect to the relatively short outputs, which lack long explicit reasoning trajectories.Source: §B.3 · p. 21, Table 4 · p. 21

C.1 DME Ablations and Hyperparameter Selection

• β = 103 seems to work better than β = 101 or β = 106, but only with the length-respecting uniform prior.The sweep used 100 distinct, harder LiveCodeBench problems; Figure 6 reports shaded-region mean and standard deviation over two seeds.Source: §C.1 · p. 22, Figure 6 · p. 22

D.1 DME Details and Hyperparameter Tuning

• DME hyperparameter tuning used short, single-chain runs of up to 1000 programs on the third autocorrelation inequality problem; the standard prior and higher β seemed helpful.Table 5 reports the best discovered upper bound per run, with lower values better; DME’s reward is ebound, with its sign flipped when minimizing.Source: §D.1 · p. 22, Table 5 · p. 23

C.2 Results for a Reasoning Model

• With Qwen3-1.7B, DME using β = 106 slightly underperforms both (1, N) and (1 + N).The authors say the reason is unclear, although they report DME can be competitive with reasoning models across many problems.Source: §C.2 · p. 22, Figure 7 · p. 23

D.2 Probability of Improvement Calculations

• Probability-of-improvement estimates were bootstrapped by sampling BoN programs, SCS trials, and DME chains without replacement.The procedure added 1000 programs each for BoN and SCS, plus three DME chains matching the original four chains’ step count.Source: §D.2 · p. 23

D.3 Per-Problem Breakdown

• Per-problem estimates are much less reliable than the aggregate estimate because they are based on less data.Figure 8 presents DME’s per-problem probability of improvement.Source: §D.3 · p. 23, Figure 8 · p. 24