CS Paper Radar

Distribution Matching Evolutionary Algorithms for Rare Event Sampling

Yonatan Gideoni, Yarin Gal

cs.NE cs.AIcs.LG ·submitted 2026-10-02 12:31 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Rare Event Estimation via Iterative Unalignment

cs.LG cs.AI ·2026-09-21 ·Hanming Yang, Daksh Mittal, Jing Dong, Hongseok Namkoong
code/data similarity 0.61
Abstract

As agents are deployed with increased autonomy, even extremely rare events along their stochastic output trajectories can occur and prove catastrophic. Safe deployment therefore does not depend on whether these events can occur, but on how often they might. We study the problem of estimating the probability of rare events that arise from stochastic variation in the agent's own actions. Estimating this type of risk requires searching over the combinatorially vast space of trajectories. Naive Monte Carlo is computationally prohibitive in this regime, and constructing effective importance sampling (IS) proposals requires coordinated changes to a context-dependent chain of conditional distributions. We develop a new IS method that perturbs the original model's weights to construct the proposal. The proposal is itself a differentiably parameterized language model, enabling gradient-based search over weight space. We formulate an objective that combines a differentiable surrogate for event amplification and an adaptive regularization scheme that dynamically balances amplification against estimator stability. We evaluate our approach on $\sim$120M and $\sim$2.6B models across three event families spanning 300+ rare events as rare as $10^{-9}$, with reference probabilities computed with $<10\%$ relative standard error. In our most verifiable settings, we observe that our IS estimator achieves over $800\times$ compute-weighted efficiency gains over naive Monte Carlo for events with probabilities lower than $10^{-7}$. Our implementation is available at https://github.com/namkoong-lab/iterative-unalignment.

0.35

MaD-RL: Matching Distributions for Calibrating LLMs with Reinforcement Learning

cs.LG cs.AI ·2026-09-12 ·Sourabh Kulkarni, Ksheeraj Sai Vepuri, Basar Demir, Jason Bohrer, Emily Shen +6 more
similarity 0.60
Abstract

Reinforcement learning (RL) is widely used in language-model post-training to maximize rewards assigned to individual model outputs, such as scores from binary verifiers or reward models trained on human feedback. However, applications such as synthetic-data generation, fairness-related constraint satisfaction, and policy exploration require controlling the distribution of outputs across model generations rather than only maximizing expected reward. We propose a general RL-based framework for \textit{Distribution Matching} allowing matching the distribution of a latent categorical attribute of model outputs to a specified target distribution. Empirically, we demonstrate that dominant post-training recipes such as Group Relative Policy Optimization (GRPO) reduce output diversity by concentrating policy probability towards a single mode. Entropy regularization and sampling temperature can improve the spread of the distribution but have constrained effectiveness, limited to apply only in token space and toward uniform distributions. We show that prior work in this area is a specific case of Distribution Matching involving the $L_2$ divergence. We then propose reward functions for other divergences such as KL and Jensen-Shannon and motivate them with theoretical justification. Finally, we demonstrate the effectiveness of our approach on a set of experiments involving mathematical reasoning and programming.

0.30

LATS: Levy Adaptive Tree Sampling for Feedback-Driven Diverse Target Discovery

cs.LG ·2026-09-06 ·Binglin Ji, Anindya Sarkar, Hengchang Lu, Lecheng Kong, Yixin Chen +1 more
similarity 0.60
Abstract · 19 pages, 6 figures, preprint

While diffusion models excel at capturing complex data distributions, scientific discovery often requires steering generation toward specific, uncharacterized regions that maximize a target objective. These high-utility modes frequently reside in low-likelihood tail regions and are only revealed sequentially through interactive feedback. Existing diffusion samplers fail in this regime: they inherit the pre-trained model's bias toward high-density regions, leaving rare yet promising phenomena underexplored. Conversely, exploration-heavy samplers ensure broad coverage but fail to efficiently exploit high-utility modes when constrained by a strict sampling budget. To resolve this dilemma, we introduce Levy Adaptive Tree Search (LATS), a principled sampling framework for online feedback-driven search. LATS leverages heavy-tailed exploration coupled with tree-based value backpropagation to progressively uncover preferred modes. By maintaining broad distributional coverage, LATS successfully discovers low-likelihood, high-utility regions while preserving sample fidelity and structural diversity. Experiments across diverse benchmarks, including materials science, demonstrate that LATS significantly outperforms baselines in target discovery efficiency.

0.35

Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures

cs.LG ·2026-10-05 ·Paweł Lorek, Rafał Nowak, Rafał Topolnicki, Tomasz Trzciński, Maciej Zięba
top venuecode/data similarity 0.59
Abstract · Accepted at NeurIPS 2026

We study estimating rare-event probabilities $I = \mathbb{P}(g(\mathbf{X}) > γ)$ with $\mathbf{X} \sim \mathcal{N}(\boldsymbolμ, \boldsymbolΣ)$ and general $g : \mathbb{R}^d \to \mathbb{R}$. We address this problem through importance sampling, and propose a framework that substantially improves efficiency and robustness over baselines such as crude Monte Carlo, adaptive cross-entropy, variational-inference-based methods (including reverse- and forward-KL approaches), as well as Safe-ICE, Subset Simulation, and Sequential Monte Carlo, drawing on ideas from both rare-event estimation and cross-entropy optimization. The key contribution has two parts: first, we separate the problem into coverage, to overcome the cold-start barrier, and fitting, to refine proposals once a meaningful signal is available; second, we constrain the final GMM proposal so that it has finite importance-sampling variance (since coverage alone is not sufficient -- without safeguards, importance sampling may still suffer from infinite variance). Together, these ingredients yield expressive proposals; finite variance does not by itself guarantee practical stability at a fixed sampling budget. Extensive experiments demonstrate substantial variance reduction, strong robustness across diverse benchmarks, and favorable cost--efficiency trade-offs, with the proposed approach often outperforming these baselines, particularly in high-dimensional and multimodal settings where competing methods frequently become unstable or fail. Our code is available at https://github.com/lorek/robust-cfi-is.

0.46

Bootstrap Stochastic Interpolant Tree for Inference-time Search Under Sparse Reward

cs.LG cs.AI ·2026-10-16 ·Binglin Ji, Anindya Sarkar, Yevgeniy Vorobeychik
similarity 0.58
Abstract · 26 pages, 12 figures, Preprint

Tree-based samplers offer a compelling alternative for scalable inference-time search, bypassing the per-step reward and gradient dependencies that introduce systematic bias into SMC-style frameworks. Despite this advantage, contemporary tree samplers fail to achieve broad exploration. Their reliance on learned, DDPM-like transitions inherently couples neighbor states in a trajectory, thereby restricting child-parent feature divergence in the tree sampler. Consequently, these samplers suffer from restricted coverage of the target marginal distribution, severely hindering the exploration critical for efficient search under sparse reward. To overcome these limitations, we introduce a simple yet effective Bootstrap Stochastic Interpolant Tree (BSIT) sampler that decouples child node generation from explicit parent dependencies. By expanding the degrees of freedom during child node sampling, BSIT encourages diverse trajectory rollouts and unlocks broader path-space diversity-the exact catalyst needed for efficient exploration. Crucially, we show that BSIT's improved exploration accelerates convergence to the target distribution while achieving broader distributional coverage than samplers that rely on DDPM-like transitions for child-node generation, all without incurring additional function evaluations or reward feedback, thereby providing a highly efficient basis for rare target search. Extensive experiments across diverse search settings, including rare-species discovery and target-aligned molecule generation tasks, demonstrate BSIT's superior search efficiency over the baselines.

0.22

FestDPO: Few-step Generator Alignment with Direct Preference Optimization

cs.LG ·2026-09-28 ·Jaewoo Lee, Kyuil Sim, Hyeongyu Kang, Kanghoon Lee, Woocheol Shin +1 more
similarity 0.56
Abstract · Preprint. Under Review

Few-step generative models can generate high-fidelity samples within a few function evaluations. Despite this efficiency, generated samples may not exhibit desirable properties. When these properties are difficult to encode as an explicit reward function, direct preference optimization (DPO) can align generative models using pairwise preference feedback without training a separate reward model. However, extending DPO to few-step generative models is challenging because few-step generative models are generally implicit, making the likelihood evaluation required by DPO intractable. To address this challenge, we introduce Few-step DPO (FestDPO), an extension of DPO for few-step generative models that leverages nonparametric likelihood estimation from empirical samples. By exploiting the fast sampling capabilities of few-step generative models, our approach makes sample-based approximation of DPO loss computationally feasible. Furthermore, the sample-based formulation makes FestDPO agnostic to the model family and sampling procedure. Our toy experiment demonstrates that FestDPO matches the reward-tilted target distribution across four few-step generators. For real-world tasks, we evaluate FestDPO in two domains: text-to-image generation and protein backbone generation. In text-to-image generation, FestDPO outperforms preference optimization baselines in both win rates against the base models and human evaluation scores. In protein backbone generation, it achieves a higher $β$-sheet fraction and better structural designability than the baselines.

0.24

MiniMMD: Minimization of MMD for Sampling, Inference and Integration

cs.LG stat.ML ·2026-10-28 ·Zonghao Chen
similarity 0.56
Abstract

Many problems in computational statistics and machine learning can be formulated as approximating a target distribution by minimizing a discrepancy over a restricted class of candidate distributions. This minimum-discrepancy viewpoint appears, for example, in numerical integration, sampling, generative modelling, and statistical inference, but these instances are often studied separately in the literature. This thesis develops the first unified treatment of these many problems through the minimization of the maximum mean discrepancy (MMD), a kernel-based discrepancy between probability measures. The central theme is that MMD is not only a statistically meaningful distance between probability distributions, but also a tractable optimization objective to design practical and efficient algorithms. This thesis summarizes the recent theoretical and empirical advancements of such minimum-MMD based algorithms.

0.29

High-Dimensional Black-Box Optimization via Guidance Sampling of Diffusion Models

cs.LG cs.AI ·2026-11-17 ·Xiaoyan Hu, Rohit Sonker, Jalal Butt, Jiayu Chen, Egemen Kolemen +1 more
similarity 0.56
Abstract

Many real-world optimization problems involve optimizing black-box objectives for which only a limited number of evaluations are available. Bayesian optimization (BO) is a powerful framework for such problems, but its effectiveness often deteriorates in high-dimensional spaces. Recent work leverages diffusion models for black-box optimization, often through pre-training a reward-conditioned score network to steer generation towards high-reward samples. Alternatively, gradient-based guidance methods assume access to a differentiable reward function from which guidance gradients are queried. However, these approaches either require large amounts of labeled data for offline training or access to exact reward gradients, limiting their applicability in black-box settings. We propose BReaD (Black-box Reward-guided Sampling of Diffusion Model), a guidance sampling framework for optimizing black-box rewards without assuming access to a labeled dataset or reward gradients. The proposed method uses a Gaussian process (GP) as a differentiable surrogate for the unknown objective and actively queries labels for the generated samples. We provide a theoretical analysis of the total-variation distance between the generated distribution and the target distribution. Using Upper Confidence Bound (UCB) as guidance signals, our method balances exploration and exploitation during generation and enables the discovery of high-reward regions in the data space. Numerical experiments on scientific discovery and image generation tasks demonstrate that our framework can effectively optimize black-box rewards in low-data scenarios.

0.11