Distribution Matching Evolutionary Algorithms for Rare Event Sampling

Yonatan Gideoni; Yarin Gal

cs.NEOct 2, 2026

Distribution Matching Evolutionary Algorithms for Rare Event Sampling

Authors: Yonatan Gideoni, Yarin Gal

Organizations: University of Oxford

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.

Figures & tables

Figure 1: Given some reward function (a) sampling uniformly over all high reward solutions requires sampling from

\pi_{S}

(b).

\pi_{S}

is difficult to sample from due to slightly suboptimal solutions having no probability, so it is easier to sample from a relaxation (c). If relaxed too far, the target distribution will be almost uniform, leading to many wasted samples (d).

Figure 2: Average success rate across regexes for different methods. Black lines denote means, shaded regions are 95% confidence intervals.

	RS-GRPO	TTT-Discover	GFlowNets	BoN	SCS	GEPA	(1+N)	(1,N)	DME
Time per run (minutes)	$154.8\pm 41.5$	$324.3\pm 56.4$	$238.8\pm 92.6$	$3.0\pm 0.4$	$18.1\pm 2.9$	$47.5\pm 14.9$	$6.7\pm 1.9$	$6.5\pm 0.9$	$7.2\pm 0.5$
Markovian	✓		✓	✓	✓		✓	✓	✓
Requires a meta-model					✓	✓
Requires weight updates	✓	✓	✓
Requires log-probs	✓	✓	✓						✓

Table 1: Properties of different methods. DME is relatively fast, Markovian, does not need auxiliary models, and is inference only. However, it does require access to the generative model’s (potentially unnormalized) density. Runtime uncertainties are standard deviations.

Figure 3: Different methods’ solve-rate for competitive coding problems as a function of the number of generated programs per question. Shaded regions denote the standard deviation over 5 seeds.

Problem	BoN	SCS	DME
# problems DME $\geq$ method	9/9	9/9
Average rank ( $\downarrow$ )	2.6	1.8	1.0
First autocorr. ineq. ( $\downarrow$ )	1.524	1.517	1.510
Second autocorr. ineq. ( $\uparrow$ )	0.8779	0.8784	0.8868
Uncertainty ineq. ( $\downarrow$ )	0.3521	0.3521	0.3521
Erdős’ min. overlap ( $\downarrow$ )	0.3815	0.3812	0.3809

Table 2: Best discovered bounds by different methods when given 5000 samples. DME either finds the best bound or ties for first place for all problems. Arrows denote whether higher/lower is better. For all problems except circle packing results are truncated to the first different significant digit. Best results are bolded, second best are underlined.

Figure 4: DME’s probability of improvement over both baselines as a function of the number of generated programs. For most sample budgets DME is likely to outperform both baselines. For per problem breakdowns see Appendix D.3 .

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Example correct regex	Description
^\d+([^.,])?$	Accepts positive integers. Match examples: - “34” - “1” - “1000000000” Non-match examples: - “-34” - “-1”
^\d+/?\d*$	Used to validate fractions or UK odds. It will match integers, allowing 10/1 to be entered as 10, and fractions. It will not match negative numbers or fractions, spaces or any alphabetical characters. Match examples: - “10” - “2/3” - “100/30” Non-match examples: - “-10” - “-2/3”
^-?\d+(.\d+)?$	Matches any unsigned or signed floating point number/numeric string. Match examples: - “123” - “3.14159” - “-1.2” Non-match examples: - “abc” - “3.4.2”

Appendix

Table 3: Prompts ( refined_prompt in the dataset) and reference regexes for the three validation regexes. References are the ground-truths given in the dataset of Siddiq et al. [2024] .

Figure 5: DME’s average performance for the regex task increases with

\beta

, stabilizing after

\beta=10^{3}

. Uncertainties are 95% confidence intervals.

		Path Marginalisation
		✓	✗
Length-Respecting Prior	✓	45.5%	49.5%
Length-Respecting Prior	✗	46.5%	48.5%

Appendix

Table 4: DME average success rate (

\beta=1000

), with and without the length-respecting prior and path marginalisation. 95% confidence intervals are about

\pm 5\%

for all cells.

Figure 6: DME for different betas and with different priors, over a hard 100 question subset of LiveCodeBench. Configurations with shaded regions report mean and standard deviation over two seeds.

Figure 7: Different methods’ performance when using a reasoning model as the proposer. Surprisingly, here DME slightly underperforms both evolutionary strategies.

	Length-respecting prior
$\beta$	✓	✗
$10^{3}$	1.556	1.508
$10^{6}$	1.489	1.488

Appendix

Table 5: DME hyperparameter tuning on the third autocorrelation inequality problem, lower is better. Each entry is the best discovered upper bound.

Figure 8: Per-problem DME probability of improvement.

Distribution Matching

Distribution matching measures and aligns probability distributions to transfer data structure across models, domains, and generated outputs.

See all 80 papers

FUND: Density Flow for Sampling Unnormalised Distributions
Sep 26, 2026Vikas Kanaujia, Vipul AroraSampling from Unnormalized Distributions Boltzmann Sampling
Department of Electrical Engineering IIT Kanpur · Department of Electrical Engineering KU Leuven
A Deterministic Sampling Method via Maximum Mean Discrepancy Flow with Adaptive Kernel
Nov 21, 2021Yindong Chen, Yiwei Wang, Lulu Kang +1Maximum Mean Discrepancy
Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, U.S.A. · Department of Mathematics, University of California, Riverside, CA, U.S.A. · Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA, U.S.A.
Manifold Sampling via Entropy Maximization
May 12, 2026Cornelius V. Braun, Tilman Burghoff, Marc ToussaintMarkov Chain Monte Carlo Constrained Sampling
Technische Universität Berlin · Robotics Institute Germany

Sep 26, 2026J/K move · Enter open · S save

FUND: Density Flow for Sampling Unnormalised Distributions

Vikas Kanaujia, Vipul Arora

Department of Electrical Engineering IIT Kanpur · Department of Electrical Engineering KU Leuven

Sampling from Unnormalized Distributions Boltzmann Sampling Flow-Based Generative Modeling Flow Matching Markov Chain Monte Carlo

Open paper AskPDF arXiv

Efficient sampling from Boltzmann distributions is central to modelling complex physical systems. Markov Chain Monte Carlo (MCMC) methods suffer from critical slowing down, high autocorrelation, and poor mode-mixing, limiting their scalability. Recent advances, like Boltzmann Generators, offer a promising alternative but remain constrained by costly MCMC-based training, inefficient sampling, and poor ergodicity. We introduce an algorithm for learning Boltzmann distributions that does not require any true samples for training. Our approach draws inspiration from flow matching but departs fundamentally from sample-trajectory matching to distribution-trajectory matching. The algorithm iteratively reshapes the target distribution, using model generated samples to guide learning and ensure comprehensive mode coverage. We validate our method on standard benchmarks, including a 2D Gaussian mixture, Many-Well distributions, and high-dimensional scalar

φ^4

theory. The proposed approach not only improves sampling performance and accuracy over traditional MCMC and flow-based baselines but also establishes a new method for sample-free learning of complex physical distributions.

Abstract

Distribution Matching

Explore similar work

FUND: Density Flow for Sampling Unnormalised Distributions

A Deterministic Sampling Method via Maximum Mean Discrepancy Flow with Adaptive Kernel

Manifold Sampling via Entropy Maximization