CS Paper Radar

Foresight: Learning Twisted SMC for Rare Events from Reversed Relaxations

Ziyi Fan, Yuxuan Qiu, Haibo Wang, Wentao Cui, Chen Fang

cs.LG ·submitted 2026-10-31 13:01 UTC · v1

Abstract

We consider the probability that a reversible Markov chain started in a set $A$ is in a rare set $B$ after a fixed horizon, a quantity often needed for many start laws, down to single states. Twisted sequential Monte Carlo (SMC) estimates such probabilities without bias, with small variance when its proposal and twist approximate the dynamics conditioned on reaching $B$, but these components are usually learned from forward simulations, which contain almost no successful paths when the event is rare. We introduce Foresight-SMC, which learns both components from the target side: under reversibility, relaxations started in $B$ that return to $A$ are, read backwards, exact samples of the conditioned paths, and their number is governed by the return probability rather than by the rare probability. Extending this reversal to the recorded propose--accept decisions of a Metropolis-adjusted sampler, we fit a controlled Langevin proposal with exact likelihood ratios by maximum likelihood, together with a classifier twist; the resulting estimator is unbiased for any start law. A variance analysis shows that resampling reduces the variance when the importance weights degenerate, as they do over long horizons. On an Allen--Cahn field, the learned proposal alone suffices, and one trained model is more accurate than splitting at equal cost. On alanine tripeptide, resampling with the learned twist is necessary, and Foresight-SMC needs less computation per query than adaptive multilevel splitting on localized start sets.

Comment
23 pages, 10 figures

Closest papers

Nearest neighbours by meaning across the whole index.

DPDP: Diffusion Policy-Steered Diffusion Planner for Offline Reinforcement Learning

cs.LG ·2026-11-07 ·Ruyi An, Mingyuan Zhou
similarity 0.63
Abstract · 23 pages

In offline reinforcement learning, diffusion models fill two roles with complementary strengths. Typically guided by a critic, a diffusion policy is value-aware and favors high-return, behavior-supported actions, but it is short-sighted: it never lays out the states it intends to visit. A diffusion planner is far-sighted, synthesizing such a long-horizon trajectory, but it is only behavior-driven at execution, realizing each planned transition using only offline behavior.Each is strong exactly where the other is weak. We introduce DPDP to bring them together at the planner's execution step, where a planned transition becomes an action. Reading the planner's inverse-dynamics executor as a posterior over actions: the environment's transition likelihood relates an action to the planned next state, while the behavioral prior determines its weight under the offline data. Replacing this prior with a value-optimized diffusion policy preserves the planned transition likelihood and favors valuable actions that can serve the plan. We target the resulting clean-action distribution in two ways. A training-free sampler composes policy and inverse-dynamics scores at matched action noise levels and applies Langevin correction; this route uses a shared action noise schedule and an approximately common terminal prior. A preference objective instead amortizes the transfer into a single diffusion executor. Across D4RL, DPDP improves the planner it builds on, staying competitive with reactive diffusion policies on locomotion and leading on long-horizon navigation.

0.14

Decoupled Marginal Sharpening for Training-Free Inference-Time Scaling

cs.LG ·2026-10-14 ·Weixin Wang, Wei Deng, Anderson Schneider, Yuriy Nevmyvaka, Pan Xu +1 more
similarity 0.63
Abstract · 17 pages, 3 figures, 6 tables

We study how to improve LLM reasoning at inference time without updating model weights or using external reward models. Recent reward-free power-sampling methods define the sequence-level power target $π_α(y\mid x)\propto p_0(y\mid x)^α$, where $α>1$, which increases the relative probability of completions that are already likely under the base model. Existing methods use Metropolis--Hastings or Sequential Monte Carlo (SMC) to approximately sample from this target. However, two challenges arise at different levels. At the target level, full-sequence sharpening can concentrate probability on a few exact reasoning--answer trajectories, suppressing alternative paths that support the same answer. At the sampler level, finite-particle SMC can suffer from path collapse when resampling repeatedly duplicates a few high-weight prefixes. To address these challenges, we propose Decoupled Marginal Sharpening (DMS), which separately controls how strongly the model favors particular reasoning paths and how strongly it favors final answers after aggregating support across those paths. At the target level, DMS first samples from a sharpened reasoning distribution, then marginalizes the model's answer probabilities over the resulting weighted reasoning population and sharpens the induced answer marginal. Separate exponents allow mild reasoning sharpening to encourage exploration of diverse paths, followed by stronger answer-marginal sharpening to concentrate probability on answers with greater aggregate support across those paths. At the sampler level, we develop Fully Adapted Annealed SMC, which combines an annealed sequence of power targets with locally fully adapted proposals and predictive ancestor resampling. Experiments on MATH500, GPQA-Diamond, HumanEval, and AIME24/25 across three base models show that DMS achieves the highest mean pass@1 among the compared methods in all tasks.

0.21

BridgeTwist: Twisting Schrödinger Bridges for Training-Free Conditional Sampling

cs.LG stat.ML ·2026-10-13 ·Mengyu Li, Qianqian Qu, Jun S. Liu
top venue similarity 0.62
Abstract · Accepted at NeurIPS 2026

Generative models are often required to serve many downstream conditional tasks. In the training-free setting, a pretrained unconditional model is reused as a prior and combined with a task-specific likelihood to sample from the corresponding posterior. While such training-free samplers have been developed for diffusion and flow models, their counterpart for Schrödinger bridge (SB) models remains unexplored, despite the growing appeal of SBs as flexible stochastic transport models between general source and target distributions. We propose BridgeTwist, a training-free conditional sampler for pretrained SB generative models, formulated as a tempered twisted sequential Monte Carlo scheme. Its twist is a closed-form plug-in surrogate, obtained by combining the velocity and score fields exposed by SB pretraining into an endpoint predictor and evaluating the likelihood there. Since this surrogate is less reliable near the source, we temper the twist with a time-varying exponent, downweighting its influence at early steps. We further introduce a bridge-shaped inference-time diffusion schedule that concentrates the proposal noise in the interior of the path. Telescoping importance weights then cancel all intermediate twist factors, yielding an asymptotically exact sampler for the posterior. Empirically, BridgeTwist outperforms training-free baselines on class-conditional and text-prompted image generation, and is competitive with specialized inverse problem solvers on inpainting, deblurring, and super-resolution.

0.29

Metropolized backward sampling for conditional sequential Monte Carlo

eess.SP stat.COmath.PRstat.ME+1 ·2026-10-28 ·Adrien Corenflos
theory similarity 0.61
Abstract · 12 pages + appendix. A Lean formalization was AI-generated after the draft of the paper was written as an experiment. I have subsequently ed…

Particle Gibbs samplers with backward sampling are widely used for sampling the smoothing distribution of state-space models, but, with few particles, the new trajectory often coincides with the current one at many time steps. A known but rarely used remedy replaces the random selection of the final particle by a Metropolis--Hastings move which avoids the current particle. We show that, with backward sampling, this remedy only helps at the last time steps, because its effect on the update rates decays geometrically with the distance to the final time. We propose instead Metropolized backward sampling, which makes such a move at every step of the backward pass, forcibly switching trajectories whenever possible. Additionally, we introduce a coupled version which prevents proposing the current trajectory, maximizing the chances of an actual switch versus the current trajectory and performing perfect sampling when the state-space model has no observations, a feature not shared by backward sampling. We prove that, at every time step, both methods dominate backward sampling as they update the state more often and have smaller lag-one autocorrelations than it does. Our methods are drop-in replacements for backward sampling, and can be used to improve any particle Gibbs sampler.

0.27

The cost of useful natural gradient updates

cs.LG cs.ITmath.OC ·2026-09-27 ·Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
similarity 0.60
Abstract · 43 pages, 8 figures, 10 tables

What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction $\varepsilon$ of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is $Θ(\log(1/δ)/(p\varepsilon^2))$ for small $\varepsilon$, where $p$ scales rare-state probabilities and $δ$ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.

0.25

Steering Diffusion Models to Rare Events with Sequential Monte Carlo

cs.LG stat.ML ·2026-10-06 ·Aavash Subedi, Tim Reichelt, Christopher Williams, Philip Stier, Yee Whye Teh +1 more
published similarity 0.60
Abstract · A previous version of this work was accepted at the NeurIPS 2026: AI for Stochastic Dynamics workshop

Diffusion models are increasingly used as surrogates for expensive simulators in weather prediction, molecular dynamics, and materials design. In these models, computing the probability $p_0[E]$ of an event $E$ is difficult, especially when the event of interest is rare. A stable estimate using Monte Carlo becomes computationally intractable, requiring a growing sample size $\propto\!1/p_0[E]$ to compensate for an increasing rarity. In this paper, we present Diffusion rare event sampling with Sequential Monte Carlo (DireSMC), a sequential Monte Carlo scheme that guides a population of weighted samples towards the rare event, giving access not only to samples but also to a calibrated estimate of its probability. We set up our guidance using an analytical relaxation of the event set, allowing the method to easily extend to a wide range of user-defined rare events. We validate our method on a toy problem with analytical solutions and on a score-based climate emulator, where we obtain accurate rare-event probabilities on a range of rarities from $10^{-3}$ to $10^{-5}$, achieving net speed-ups of $9\times$ to $1413\times$ over Monte Carlo.

0.29

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.60
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

Adaptive Multilevel Twisted Sequential Monte Carlo for Rare Events Estimation in Language Models

cs.LG ·2026-08-22 ·Zixuan Liu, Fangzheng Wu, Brian Summa, Zizhan Zheng
similarity 0.60
Abstract

Rare unsafe behaviors in large language models can remain practically significant even when their probability is extremely small, particularly at deployment scales involving millions or billions of interactions. Twisted Sequential Monte Carlo (SMC) provides a principled framework for rare-event probability estimation by learning twist functions that guide generation toward a target event. However, the standard twist learning framework relies on positive samples from the rare-event target distribution, which may be nearly absent before an informative twist has been learned, resulting in unreliable rare-event estimation. We propose Adaptive Multilevel Twisted SMC, which learns the rare-event twist through a sequence of progressively rarer intermediate events. At each level, the learned twist provides more informative positive examples for learning the next twist, ultimately leading to a more accurate final twist for the target rare event. Experiments across diverse tasks and model scales show that the proposed method produces more accurate rare-event probability estimates. By enabling more reliable discovery of hard-to-observe unsafe behaviors, our method provides a practical tool for strengthening the evaluation and safety alignment of deployed language models.

0.49