Overview

Importance sampling studies how to estimate expectations, probabilities, or gradients under a target distribution by drawing samples from another distribution and correcting them with weights. Adaptive and defensive proposals, sequential Monte Carlo, and self-normalized or tempered weights are used in settings ranging from rare-event estimation and Bayesian inference to off-policy evaluation and language-model policy optimization. Applications include estimating rare failures, reweighting data under distribution shift, and making learning or inference more computationally efficient. A central tension is that better correction can reduce bias but high-variance weights destabilize estimates, so current work develops clipping, calibration, effective-sample-size diagnostics, and guarantees for when reweighting is reliable.

Latest papers

82 papers10 papers in the last four weeks, down 57% on the four weeks before. 0.1% of all new papers.

Nov 18, 2026

Improved Leverage Score Sampling for Constrained Active Linear Regression

In this paper we study active learning for constrained linear regression. Given a design matrix A∈Rn×dA\in\mathbb{R}^{n\times d}, a constraint set C⊆RdC\subseteq\mathbb{R}^d, and query access to b∈Rnb\in\mathbb{R}^n, we seek an approximate solution to min⁡x∈C∥Ax−b∥22\min_{x\in C}\|Ax-b\|_2^2 using as few queries as possible. This problem arises in many scientific and engineering applications, and randomized leverage score sampling provides a powerful method to solve it. However, existing leverage score methods ignore the constraint or encode it through ridge regularization, suffering unfavorable query complexity for anisotropic constraint sets. We propose ellipsoid-regularized leverage scores, where we approximate the constraint set by an outer ellipsoid and use its shape matrix to bias sampling toward directions that matter under the constraint geometry. We prove that the query complexity is governed by an anisotropic effective dimension deff(C)≤dd_{\text{eff}}(C)\le d. With appropriate parameters, O(deff(C)log⁡d/ε2)O(d_{\text{eff}}(C)\log d/\varepsilon^2) queries suffice to return a point in CC with objective value at most (1+ε)(1+\varepsilon) times the optimum. This bound can substantially improve on the standard leverage-score bound, since anisotropic constraints can make deff(C)d_{\text{eff}}(C) much smaller than dd. For convex constraints, we improve the dependence on ε\varepsilon from 1/ε21/\varepsilon^2 to 1/ε1/\varepsilon. We also prove two lower bounds: first, the d/ε2d/\varepsilon^2 dependence is unavoidable without convexity assumptions on CC, and second, in some regimes, the effective dimension dependence deff(C)/εd_{\mathrm{eff}}(C)/\varepsilon is necessary for ellipsoidal constraints. Experiments on synthetic regression problems and a parametric heat conduction problem show lower regression error than standard baselines for similar query budget.
Nov 12, 2026

Tractable Importance Sampling for Monte Carlo Privacy Accounting

Evaluating tight Differential Privacy (DP) parameters for DP matrix factorization with privacy amplification by sampling requires analyzing high-dimensional, correlated Gaussian mixtures. Because integrating these mixture distributions to find the exact privacy failure probability (δδ) is analytically intractable, these mechanisms are typically analyzed using Monte Carlo accounting. However, standard sampling suffers from prohibitive variance when estimating small δδ associated with strict privacy guarantees, which in turn requires a large sample complexity, making Monte Carlo accounting inefficient. We demonstrate that Monte Carlo accounting can be made much more efficient via importance sampling. We give a shifted importance sampling proposal distribution parameterized by a stretch factor α>1α> 1. We prove a closed-form bound B(α)<1B(α) < 1 on the support of the importance-weighted estimator that holds identically for both directions of the hockey-stick divergence, show that BB is log-convex so that the optimal αα is a one-dimensional root-finding problem, and show that the resulting estimator seamlessly plugs into the KL-Hoeffding verification protocol used by past work, with a sample complexity reduced by exactly a factor of 1/B(α∗)1/B(α^*).
Nov 5, 2026

InstaGen: Group-Shared Importance Sampling for Fast Video Generation

Diffusion Transformers (DiTs) are the dominant architecture for video generation, but their quadratic attention complexity results in substantial computational cost and latency. Permuted block-sparse attention (PBSA) offers a promising approach to reducing this cost by selectively computing blocks of a semantically permuted attention matrix. However, existing approaches typically select only the top few key blocks for each query block, following a top-pp paradigm. We find that top-pp selection can be highly sample inefficient in high-entropy attention regimes, which are common in video generation. In these regimes, we show that sampling can provide substantially better approximations under the same computational budget. More generally, we cast block selection as importance sampling, where the top-scoring keys form an exact set that is computed in full and the remaining keys are represented by a sample drawn in proportion to their estimated attention and reweighted by inverse sampling probability. Building on this formulation, we present InstaGen, which can be parameterized by any PBSA method: it replaces the method's block selection with an exact set plus a weighted sample. Each query cluster draws one sample shared by all its queries, so the sampled keys form blocks amenable to efficient GPU execution. In this paper, we take the SVG family of PBSA methods and show that, on Wan2.1-T2V-1.3B and Wan2.1-T2V-14B, InstaGen parameterized by SVG2 improves PSNR over SVG2 by 3.4 dB and 2 dB, respectively, at matched attention density, and by 1.6 dB and 2.2 dB at matched wall-clock time. On Wan2.1-T2V-14B, InstaGen also beats SVG-EAR by 1.1 dB PSNR at nearly the same density while running faster (1.65x against 1.48x over dense).
Nov 4, 2026

Diversity-Aware Experience Replay via Statistical Leverage Scores

Off-policy deep reinforcement learning trains on random samples from a replay buffer of past experience. In physical robot settings, that buffer is dominated by routine: thousands of near-identical transitions from normal operation, while the rare events that define the edges of the task are rarely sampled. We propose scoring every stored transition by its statistical leverage, which measures how unusual it is relative to the buffer's own data, computed from the stored numbers alone, with no labels, rewards, or value network. We draw each mini-batch from a mixture of this score and uniform sampling. First, the natural way to build the score along the directions where the data varies most turns out to be blind when actions are stored as one-hot indicators, because indicator columns always win the variance ranking; we instead select the feature columns with the heaviest tails (largest kurtosis) where small far-away populations are revealed. Second, the importance weights that prioritized replay uses to keep gradients unbiased cancel the method exactly: with full correction, training matches uniform sampling, so we drop the correction and deliberately optimize the rebalanced objective. Third, when the rare situations of a log are relational, visible only in how a stretch of behavior relates to its goal, not in any single stored coordinate-per-transition scores are blind; applying the same tail rule to short trajectory windows described relative to their goal restores the signal, and on a three-joint arm that must push an object around an obstacle it raises the rare-task success from 0.49 to 0.69 against a labeled-oracle ceiling of 0.74.
Nov 3, 2026

Post-stratified importance sampling

Importance sampling is a building block of modern statistical computing, but the weighted estimate is prone to high or infinite variance. Moreover, its empirical standard error is often unreliable, leaving importance sampling without practical uncertainty quantification. Motivated by multilevel regression and poststratification (MRP) in survey sampling, we propose post-stratified importance sampling (PIS) for estimating target expectations from proposal draws. PIS reformulates arbitrarily high-dimensional weighting into two one-dimensional probabilistic modeling problems: regression for the conditional mean given the importance ratio and marginal density estimation for the importance ratio. Different modeling choices yield a family of PIS estimators, encompassing ordinary importance sampling as a special case. We develop a model-based implementation that combines one-dimensional Gaussian process regression for the conditional mean and score-informed heavy-tailed density estimation for the marginal law, using both the observed weights and the available density evaluations. We study the oracle gains of PIS and establish consistency under general and model-specific conditions. Simulations and applications to cross-validation demonstrate improvements in estimation accuracy and uncertainty quantification.
Oct 31, 2026

Foresight: Learning Twisted SMC for Rare Events from Reversed Relaxations

We consider the probability that a reversible Markov chain started in a set AA is in a rare set BB 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 BB, 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 BB that return to AA 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.
Oct 29, 2026

Numerical Integration on Bounded Domains via Learned Reflected Diffusions

We study high-dimensional integration on bounded convex domains. Given a non-negative integrand rr, the goal is to estimate Z=∫Dr(x) dxZ=\int_{D}r(x)\,\mathrm dx on D⊂RdD\subset\mathbb R^d. Standard Quasi-Monte Carlo does not adapt its evaluation points to the integrand, while effective importance sampling requires a proposal that captures its concentration. Learned diffusion samplers can supply such a proposal, but existing methods are formulated on Rd\mathbb R^d and do not respect the domain constraint x∈Dx\in D. We instead build the proposal from reflected dynamics that stay in DD by construction. A reflected diffusion progressively transforms the target distribution toward the uniform distribution on DD, and a neural score model is trained to reverse this process. A change-of-measure formula for reflected diffusions yields a training objective without additional boundary terms and an unbiased importance-sampling estimator of ZZ. For non-smooth integrands, where reparameterization gradients may be undefined or uninformative, we derive a REINFORCE estimator of the training gradient using Gaussian proposal densities before reflection, without evaluating reflected transition densities or differentiating rr. We evaluate on numerous synthetic targets and real-world problems, demonstrating strong performance of the proposed method, as well as favorable scaling with the dimension of the problem and the number of points used for the Monte Carlo estimate.
Oct 23, 2026

Multiple Importance Sampling for Guided Speculative Inference

We study an extension of the Guided Speculative Inference (GSI) algorithm for test-time-scaling of large language models (LLMs) to a novel setting where an ensemble of smaller LLMs proposes draft reasoning steps which are later verified by a larger base model and a process reward model. Using the established framework of multiple importance sampling (MIS), we introduce weighting schemes to aggregate samples from a diverse collection of proposal distributions. We provide new bounds on the KL divergence from the optimal reward-tilted target distribution and the expected reward degradation, then demonstrate that the well-known balance heuristic is optimal. Compared to GSI with a single well-tuned drafter, combining several diverse LLMs while retaining the same total number of samples maintains competitive pass-at-NN downstream performance while being mathematically robust to situations where the support of a single draft model does not cover that of the target, where GSI may fail.
Oct 21, 2026

Asynchronous, Generation-Free ABC: Streaming AMIS Reweighting for Heterogeneous Simulator Workloads on HPC

Approximate Bayesian computation (ABC) enables Bayesian inference for models with intractable likelihoods by estimating parameter posterior distributions from simulated data. Sequential ABC methods improve sampling efficiency by iteratively adapting the proposal distribution toward regions of high posterior probability. However, these methods typically operate in generations, where each generation must wait for its slowest simulation before the next can begin. On a parallel machine, this synchronization barrier leaves workers idle and reduces throughput, particularly when simulation runtimes vary substantially. We introduce a generation-free ABC sampler that updates its proposal when simulation results arrive and sends a new candidate to each available worker. The proposal is based on the best particles evaluated so far. To estimate the posterior, we reuse the full history and reweight particles against a reconstructed mixture of sampling proposals. We show how errors in approximating the mixture of sampling proposals affect the estimated posterior and establish consistency for the smooth-ABC posterior when the approximation becomes asymptotically exact. In our experiments, the method achieves well-calibrated posterior estimates where a pyABC baseline with the same kernel and bandwidth schedule under-covers. From the asynchronous run's timing alone, we predict how much a synchronization barrier would slow the sampler. These predictions agree with measured synchronization penalties ranging from 1.2x to 400x. On a Cellular Potts tissue simulator, the asynchronous sampler completes 2.1-2.4x as many evaluations as pyABC in the same hour, and the discrepancy threshold for its best 100 evaluations is 4.1x smaller. With the starting bandwidth set from prior-predictive discrepancies, it also produces a more concentrated two-parameter posterior with a larger effective sample size than pyABC.
Oct 21, 2026

ART-MPG: Autoregressive R/T Manifold Path Guiding

Specular chains concentrate important transport in small regions of path space and the structure depends on chain topology. We introduce ART-MPG, a compact neural model that samples chain length, an autoregressive reflection/transmission (R/T) string, and a direction from a topology-conditioned four-component von Mises-Fisher (vMF) mixture. We extend the repeated trial weighting in Manifold Path Guiding (MPG) by conditioning retry sampling on both chain length and the sampled R/T string, accounting for its known mass outside the stochastic re-hit trials. For a fixed proposal and target chain, this preserves the ideal expectation while reducing the expected retry count and reciprocal-estimator variance compared with retries conditioned on chain length alone. We distinguish the formal unbiasedness result from the capped and clamped renderer used in experiments. We evaluate fourteen scenes across a range of samples per pixel (SPP) against existing online and offline rendering algorithms. Our method consistently produces lower mean squared error at equal SPP than the online and offline baselines, with lower standard deviation across runs.
Oct 20, 2026

Stratified Sparse Attention: Reducing the Sparse-to-Dense Gap at Extreme Sparsity

Large Language Model inference over long contexts is increasingly bottlenecked by the cost of attending to a growing Key-Value (KV) cache. Sparse attention reduces this cost by accessing only a fraction of the cache, but existing methods face a trade-off between deterministic retrieval, which captures high-scoring tokens but discards residual attention mass, and sampling, which improves coverage at the cost of higher variance. Hybrid methods combine top-kk retrieval with uniform sampling, yet still exhibit a substantial gap from dense attention at aggressive sparsity. We introduce Stratified Sparse Attention (SSA), a unified framework combining deterministic retrieval with score-guided sampling. SSA deterministically attends to high-scoring tokens while sampling the residual using proxy attention scores and correcting for their inclusion probabilities, thereby recovering attention mass beyond the retrieval set. SSA encompasses top-kk, top-pp, and hybrid top-kk+sampling as special cases. Across RULER, LongBench, LOFT, and AIME, and five models ranging from 3B to 27B parameters, SSA consistently improves over the baselines at matched sparsity. On RULER-HARD with Ministral-3-8B, SSA improves accuracy over the strongest practical baseline from 81.8% to 84.2% at 32K and from 63.8% to 69.3% at 128K under 50×50\times attention sparsity, recovering 94% and 85% of dense-attention performance, respectively. With optimized CUDA kernels, SSA achieves up to 2.96×2.96\times decode speedup over FlashInfer at 1M context, demonstrating that its accuracy gains translate into practical long-context inference acceleration. We open-source our code at https://github.com/skylight-org/SSA-Paper-Code.
Oct 15, 2026

Baselines and Score Centering in Policy Gradient Estimation

Reinforcement learning has become a widely used approach to post-training large language models. In a typical implementation, learning is off-policy: The policy generating the responses differs from the policy being trained because of training-inference mismatch or policy staleness in asynchronous training. This discrepancy is commonly addressed by importance sampling, whose ratio is usually regularized in practice through truncation, masking, or clipping. Under regularized importance sampling, the importance-weighted policy gradient is no longer invariant to constant shifts in the reward. This invariance is recovered by using the covariance between the reward and the importance-weighted score as the estimand, which coincides with the policy gradient when the ratio is not regularized. This note develops this covariance perspective for both sequence-level and token-level importance sampling. The covariance perspective reveals the roles of the group-mean baseline and score centering in policy gradient estimation. Both perform centering in covariance estimation, but they differ in the mean being subtracted: The group-mean baseline uses a sample mean, whereas score centering uses a population mean. The two lead to distinct unbiased covariance estimators with different variances. Whether both forms of centering should be used simultaneously depends on whether importance sampling is applied at the sequence level or at the token level. With sequence-level importance sampling, score centering adds no benefit once the group-mean baseline is used; with token-level importance sampling, using the group-mean baseline without score centering generally introduces bias when the importance ratio is regularized.
Oct 13, 2026

Enabling Token-wise Importance Sampling in Off-Policy RLVR with Proximal KL Regularization

Off-policy data in reinforcement learning with verifiable rewards (RLVR) can arise from asynchronous generation, rollout-training mismatch, and response reuse. Token-wise importance weighting avoids multiplying likelihood ratios across a response but generally biases policy gradients. We prove that, under coverage and local expressiveness conditions, full future KL credit makes the exact proximal optimizer the update's unique stationary policy, even for mixtures of older policies, without full-response weights or a fitted critic. We further establish convergence of continuous-time tabular population updates under persistent coverage and time-varying behavior policies, and a finite-sample reward guarantee for linear logistic models under additional assumptions. These results motivate Proximal KL, a practical off-policy RLVR method that separates the proximal reference from the sampling policy and replaces PPO clipping with bounded future KL credit. Across all seven matched off-policy comparisons on Qwen3-1.7B and Qwen3-4B, spanning two learning rates, response reuse, and rollout staleness, Proximal KL outperforms GRPO in micro-averaged accuracy over eight math benchmarks by up to 2.58%. A separate on-policy comparison yields comparable aggregate accuracy. In periodic-refresh experiments, Proximal KL avoids the collapses observed in PG and CISPO, exceeds GRPO's training accuracy, and reaches higher accuracy in fewer policy updates. Ablations show that token-wise correction outperforms sequence-level and unweighted controls. With token-wise correction retained, future KL feedback reduces sensitivity to the tested baseline perturbation relative to PPO clipping. A finite future horizon improves AIME24 mean@16 and pass@16 over the full tail, while fixed-policy measurements show that truncation reduces correction variance over the tested horizons.
Oct 12, 2026

Amortised adaptive importance sampling

Monte Carlo sampling algorithms aim to produce samples from a target distribution with a given unnormalised probability density function. The high cost of running Monte Carlo algorithms, with many simulation steps or particles needed to obtain a good empirical approximation to the target, can be reduced by introducing learnable components into the sampler -- a form of amortisation. Once these components are trained, amortised samplers can produce high-quality samples with less computation at sampling time than training-free algorithms would require. We propose an amortised sampler built upon the framework of adaptive importance sampling -- a hierarchical importance sampling procedure where the proposal is iteratively adapted. Our amortised adaptive importance sampling algorithm fits a lightweight neural network that adapts the proposal using information obtained over the course of sampling. By training our sampler over many different targets taken from the same family of distributions, we obtain a sampler that can adapt to a specific target at sampling time without a priori access to the target's parameters. We show that our procedure can efficiently sample from targets within the family the sampler was trained on, giving improvements over target-specific amortised samplers and training-free adaptive importance sampling algorithms. We also explore the potential for generalisation, where the trained sampler is used to sample from targets outwith its training family.
Oct 11, 2026

ML-CLAPPS: A Probabilistic Framework for Imbalanced Multilabel Learning under Class Prioritization

Real-world datasets often exhibit severe class imbalance, degrading the performance of deep learning models, particularly on rare classes. While imbalance is well studied in binary and multiclass settings, it is substantially more challenging in multilabel problems due to complex label co-occurrence. In clinical applications such as ECG classification, this challenge is coupled with a second critical challenge: the need to prioritize high-risk conditions, regardless of their prevalence, to mitigate the high cost of false negatives. We introduce the Multilabel Class-Prioritized Probabilistic Sampler (ML-CLAPPS), a learnable sampler that optimizes a distribution over training instances to control the model's exposure to different classes. This approach addresses multilabel imbalance while enabling prioritization of significant conditions via a user-defined importance vector (IV). Empirical evaluation on a real-world multilabel ECG image dataset demonstrates that ML-CLAPPS achieves state-of-the-art performance. We show that it aligns class exposure with the specified IV, and that increasing a class's importance leads to corresponding improvements in its classification performance, enabling explicit prioritization of clinically critical conditions.
Oct 10, 2026

Target-ESS Tempered Policy Optimization (TETPO): Smooth Variance Control via Bridge Importance Sampling

Asynchronous reinforcement-learning post-training of large language models is computationally efficient but inherently off-policy: the learner updates on rollouts generated by a stale policy, while correcting this mismatch requires importance weights that can be extremely heavy-tailed. A small number of trajectories may then dominate an update, collapsing the effective sample size (ESS) and increasing the variance and instability of the resulting gradient estimates. Existing stabilizers apply fixed interventions regardless of the realized severity of weight concentration, either discarding selected samples or reweighting them without adapting the correction strength. We introduce Target--ESS Tempered Policy Optimization (TETPO), which replaces each importance weight ρρ by ραρ^α for a data-adaptive exponent α∈[0,1]α\in[0,1]: α=1α=1 preserves the original importance weights, whereas α=0α=0 assigns uniform coefficients. For each prompt group, TETPO selects the largest αα whose tempered weights satisfy a target ESS fraction κκ, applying little tempering to healthy groups and stronger tempering when weight degeneracy is severe. At the population level, the tempered coefficients are exact importance weights for a geometric bridge between the sampler and learner policies. The exponent is efficiently found by one-dimensional bisection, while the resulting weights satisfy deterministic bounds on normalized-weight dispersion and weighted-gradient norm that are independent of policy drift, together with a fixed-αα bound on bridge-target discrepancy. Power tempering also introduces no explicit zero-weight mask. On mathematical-reasoning benchmarks under high staleness, TETPO outperforms strong on- and off-policy baselines.
Oct 9, 2026

Universal Bounds for Self-Normalized Kullback-Leibler Estimation

This work studies an entropy-based estimator of Kullback-Leibler (KL) divergence constructed from normalized importance weights. We prove a universal finite-sample bound showing that its expectation can exceed the target-proposal KL divergence by at most log⁡2\log 2 for any sample size. We then characterize the KL divergence between the distribution induced by importance-weighted resampling and the proposal, showing that it is upper bounded by both the expectation of the entropy-based estimator and the target-proposal KL divergence. Importantly, these bounds require neither bounded importance weights nor finite higher moments. We apply these results to test-time alignment of generative models via Soft Best-of-NN sampling, an importance-sampling-based scaling technique proposed by Verdun et al. (2025), and to relative entropy coding, obtaining finite-sample policy-divergence certificates and moment-free bounds on coding cost.
Oct 6, 2026

Sampling SU(N) gauge theory on a 2D lattice from independent plaquettes via holonomies and corner reweighting

In the Wilson formulation of lattice gauge theory, the fundamental degrees of freedom are group-valued link variables, while the action is a sum over the trace of the plaquettes, the smallest Wilson loops. For generative sampling methods such as normalizing flows, this poses a challenge: the distribution of an individual plaquette is easy to model, but mapping sampled plaquettes to the links is the obstruction. We explore a statistical way around this in two dimensions for the SU(N)\mathrm{SU}(N) gauge theory with the Wilson plaquette action. The action can be written in terms of holonomy variables, which determine the links once a consistency condition at the four corners of an extended lattice is satisfied. Using a boundary condition that only affects the holonomies, we trade this consistency condition for a conditional sampling problem, which reduces to sampling X,Y∈SU(N)X,Y\in\mathrm{SU}(N) given the group commutator Z=XYX†Y†Z=XYX^\dagger Y^\dagger, where Z∈SU(N)Z\in\mathrm{SU}(N) depends on the four corners. Plaquettes are sampled independently, and the resulting configurations carry weights due to the additional conditional sampling. We obtain the density of ZZ, which determines these weights, in closed form for SU(2)\mathrm{SU}(2) and SU(3)\mathrm{SU}(3). A normalizing flow models the single-plaquette distribution for SU(2)\mathrm{SU}(2) and SU(3)\mathrm{SU}(3); for the group-commutator problem we use a closed-form sampler for SU(2)\mathrm{SU}(2) and a trained normalizing flow for SU(3)\mathrm{SU}(3). In our tests on 2×22\times2 and 32×3232\times32 lattices at two couplings each, per-plaquette acceptance rates exceed 99%99\% and the effective sample size of the final weights is moderate, typically above one half.
Oct 6, 2026

Steering Diffusion Models to Rare Events with Sequential Monte Carlo

Diffusion models are increasingly used as surrogates for expensive simulators in weather prediction, molecular dynamics, and materials design. In these models, computing the probability p0[E]p_0[E] of an event EE is difficult, especially when the event of interest is rare. A stable estimate using Monte Carlo becomes computationally intractable, requiring a growing sample size ∝ ⁣1/p0[E]\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−310^{-3} to 10−510^{-5}, achieving net speed-ups of 9×9\times to 1413×1413\times over Monte Carlo.
Oct 5, 2026

Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures

We study estimating rare-event probabilities I=P(g(X)>γ)I = \mathbb{P}(g(\mathbf{X}) > γ) with X∼N(μ,Σ)\mathbf{X} \sim \mathcal{N}(\boldsymbolμ, \boldsymbolΣ) and general g:Rd→Rg : \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.
Oct 3, 2026

Risk-Calibrated Proposal Transport for Finite-Particle Diffusion Steering

Inference-time steering combines pretrained diffusion experts or rewards without retraining by changing the dynamics that transport noise to data. Feynman-Kac correction compensates for proposal mismatch through importance-weighted sequential Monte Carlo (SMC), whose finite-particle behavior depends on the proposal. Variance-controlling guidance (VCG) improves that proposal by fitting a linear drift correction to minimize empirical log-weight-rate variance. Although its population optimum cannot worsen residual variance, finite-particle VCG can nearly eliminate its fitting residual while increasing residual risk on new states by orders of magnitude. The resulting update can degrade unweighted generation or accelerate particle collapse. We show that the centered Feynman-Kac rate is the normalized transport residual and that expected out-of-fit benefit is exactly population headroom minus coefficient-estimation penalty. Under regularity assumptions, a Wasserstein analysis bounds the unweighted proposal's terminal error using this residual. These results motivate Risk-Calibrated Proposal Transport (RCPT), which uses deletion leave-one-out residuals to calibrate the retained fraction of the VCG update, adding no model calls and only small linear-algebra overhead. Experiments on 2D checker distributions, scaffold decoration, molecular property optimization, and class-conditional CIFAR-10 generation demonstrate recovery from harmful fitted updates. Across molecular and image domains, RCPT mitigates harmful fitted updates and improves a broad range of terminal metrics relative to uncalibrated VCG.
Oct 2, 2026

Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved O(ε−3)O(ε^{-3}) sample complexity to find an εε-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are Θ(ε−4)Θ(ε^{-4}) with bounded-variance one-policy feedback and Θ(ε−3)Θ(ε^{-3}) with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the O(ε−4)O(ε^{-4}) and O(ε−3)O(ε^{-3}) upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.
Oct 2, 2026

Probe the Harness: Setup Checks for Stale-Data RL Comparisons in Language Models

Methods for training language models on stale samples are judged by comparisons against importance-corrected baselines. We show that details of the experimental harness can reverse the observed ranking of methods, and we introduce PTH (Probe The Harness), a set of checks that makes the harness visible. Our case is a comparison between SAN, a behaviour-free method, and truncated importance sampling (TIS) on verl and in a single-GPU trainer, in which SAN first finished ahead in both stacks. Four details of the harness changed this comparison: the PPO ratio was taken against the learner's own recomputed probabilities, the data seed did not reach the TIS arm, the replay queue reused its first batch for 33 updates, and two loss normalisers differed from their description. In each case the logged quantity looked consistent with a working setup, while the quantity that defines the comparison went unchecked. With the harness checked, TIS matches SAN on verl, and in the trainer TIS learns steadily while SAN keeps a margin. We contribute the signature of each detail and its effect on the comparison, reference results for TIS and uncorrected GRPO under sampler lag, and the PTH checklist.
Oct 1, 2026

Efficient Neural Field Learning via Adaptive Coverage and Focused Sampling

Implicit neural representations (INRs) provide a flexible framework for modeling high-dimensional continuous fields, but their training is often inefficient due to uniform subsampling that ignores spatial heterogeneity. Existing adaptive sampling methods partially address this issue by prioritizing high-error samples, but typically operate at the point level, often leading to redundant sampling in localized regions and insufficient coverage of the domain. We propose ACES (Adaptive Coverage-aware Efficient Sampling), a structured sampling framework that improves training efficiency by decoupling coverage and importance. ACES constructs adaptive spatial partitions to ensure domain coverage and reduce redundancy, and applies region-level importance weighting to prioritize informative regions during training. We provide a theoretical analysis showing that adaptive partitioning reduces gradient variance by increasing within-region homogeneity, and that controlled bias in region-level weighting may improve optimization efficiency relative to standard unbiased estimators. Experiments on scientific field learning tasks demonstrate that ACES achieves faster convergence and lower error than uniform and pointwise adaptive sampling baselines, with the largest gains in fields with highly localized complexity.
Sep 30, 2026

Free Everywhere, Exact on Trees: PPO's Dropped Correction Buys Sample Efficiency Under Aggressive Reuse

Common policy improvement methods, including TRPO, PPO, and GRPO, estimate policy improvement under the behavioral policy's state-visitation distribution rather than the improved policy's own. The substitution makes the objective estimable from the behavioral policy's rollouts but adds a bias growing with policy divergence, hence the trust region or clip, and hence no reuse of a batch far off-policy. We show that under history-injective dynamics, where each state is reached by exactly one history, the dropped state-visitation ratio equals the product of per-step policy ratios along the sampled prefix, on every trajectory and not only in expectation. The ratio is therefore restored exactly, from log-probabilities PPO already computes. Autoregressive generation and canonical-order constructive optimization are both history-injective. The exact correction pays importance-sampling variance that grows with the horizon, so we generalize it to a one-parameter family with PPO (α=0α{=}0) and the full correction (α=1α{=}1) as endpoints: a single bias--variance knob. A gradient-level analysis of the unclipped surrogate identifies two channels the correction acts through and three conditions under which it carries signal; an enumerable testbed confirms the conditions' predictions. On hard credit-assignment scheduling tasks, a short corrected warmup with aggressive early sample reuse learns faster than PPO and than the same reuse uncorrected; the marginal gain grows with task difficulty (+0.02+0.02 to +0.09+0.09 learning-curve AUC), and the early win over PPO tracks the prefix bias that reuse incurs. A correction held throughout, or applied where clipping already contains the reuse bias, is null to harmful.
Sep 30, 2026

Search Shapes Conclusions: Auditing Evidence Selection Bias in Deep Research Agents

Deep Research agents synthesize evidence into cited reports, yet a well-cited report can still reach a misleading conclusion. Citation correctness checks whether cited sources support individual claims. It does not show whether adaptive search exposed a representative view of all documents made available for evaluation, which we call the candidate pool. Early findings redirect later queries, document choices, and stopping, so the documents an agent reads form a selective sample. Existing evaluations rarely account for this selection. We formulate the problem as adaptive evidence sampling and introduce Causal Evidence Selection Correction (CESS). CESS predicts each candidate document's evidence direction and corrects the candidate-pool average using the logged probabilities of selecting each document and reaching each search round. Shrinkage stabilizes short searches, while intervals replace point estimates when some documents cannot be sampled. We also prove that estimating the average evidence direction of a common pool differs from measuring how a change in search policy alters the evidence read. The latter requires intervention. On questions from the MS2 systematic-review benchmark, CESS reduces mean absolute error against the candidate-pool average by 9.2%9.2\% and reduces the estimate's change under opposing document rankings by 39.4%39.4\% relative to averaging the evidence scores of documents read. Across trajectories from a public Open Deep Research agent, the corresponding reductions reach 60.1%60.1\% and 87.2%87.2\%. A further 4,800 trajectories under paired interventions confirm that correcting a pool estimate and measuring a policy effect are different tasks. CESS therefore audits whether the evidence direction underlying a report reflects the documents available for evaluation, while a separate intervention analysis measures the effect of search decisions.
Sep 29, 2026

The Advantages of Fresh Sketching for Ridge Regression

Over the past 25 years, sketching and sampling have become widely used tools for accelerating large-scale regression. In iterative randomized solvers, a basic design choice is whether to reuse\textit{reuse} the same sketch or draw fresh\textit{fresh} randomness at every step. For (under-constrained) iterative ridge regression with column sampling, whether fresh sketches offer provable advantages has remained open: We show that they do.\textit{We show that they do.} Fresh sketching lets us analyze error only along the current residual solution, rather than uniformly over the entire Gram matrix. This directional view yields sharper convergence guarantees for leverage score and ridge leverage score sampling and, more importantly, leads to residual-aware sampling rules. By minimizing the variance of the relevant sketched matrix-vector product, we derive an oracle distribution and practical approximations to the oracle distribution, including a mixture sampling distribution with (somewhat weaker) convergence guarantees. Experiments on synthetic and real data, including ridge probes on Qwen2.5 representations, support our theory, showing substantially faster convergence.
Sep 29, 2026

Cool the Sampler, Not the Learner: Sampling Temperature Moves the Staleness Cliff of Importance-Corrected GRPO

Production RL for language models lets the sampler fall behind the learner and repairs the resulting mismatch with a truncated importance weight. We ask how long the sampler can go without a refresh under that correction, and find a cliff: on Qwen2.5-Math-1.5B and GSM8K, importance-corrected GRPO refreshed every 192 updates learns well for 180 steps and then degrades severely in all three data seeds before the refresh arrives. Published remedies for staleness act on the update; we act on the sampler instead. Decoupled cooling draws samples at temperature 0.8 while the learner, the reference model and the importance weights stay at temperature 1, with the behaviour probability recorded from the tempered distribution, so the learner's objective is unchanged. All corresponding cooled runs are stable, and the longer interval keeps what the short one delivered: at the same update budget, a cooled sampler refreshed every 192 steps matches an uncooled sampler refreshed every 96 at the end of training (0.857 for both) and averaged over it (0.79), whereas lowering the learning rate to a safe value ends 3-7 points lower. On Qwen2.5-Math-7B the degradation points at interval 192 predict that an interval of 144 is fatal without cooling and survivable with it; on two data seeds the uncooled runs degrade before their first refresh and the cooled runs pass it and end at 92-93% against 68-81%, with one cooled run degrading transiently late in the second cycle. The benefit has a window: at three times the safe interval and in a high-mismatch MATH setting cooling delays degradation without preventing it, stronger cooling is not better, and cooling without the correction collapses. Sampling temperature is a control on staleness tolerance, and temperature and refresh interval should be chosen together.
Sep 28, 2026

One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices

In ecology, psychometrics, and the analysis of social and financial networks, binary matrices are often analyzed conditional on their observed row and column sums, which restricts the problem to a finite sample space of matrices with the same margins. Two fundamental problems are to count this space and to sample uniformly from it. Sequential importance sampling (SIS) addresses both with independent weighted samples and an unbiased count estimator, but its efficiency depends critically on the proposal distribution. Existing proposals are analytically designed, and their accuracy can vary substantially with the margins. We show that the ideal SIS proposal, under which every weight equals the count and the variance vanishes, is exactly the policy of a generative flow network (GFlowNet) with unit reward on every matrix that has the given margins. We therefore propose MarginFlow, a framework that turns the design of the proposal into a learning problem and amortizes it across margins by exploiting their self-similarity. Every partial matrix is itself an instance with reduced margins, so one set transformer that reads the remaining margins serves every margin. We train MarginFlow on a pool of 1904 margins and evaluate it zero-shot on 1190 held-out margins, synthetic and real, from 3×33\times3 to 870×6870\times6. On 1187 of the 1190 margins it matches or beats the best of 31 analytically designed configurations, chosen post hoc for each margin, and its median effective sample fraction is 99.8%. On the 56 margins where that best loses more than one nat of effective sample size, MarginFlow wins every one and raises the median effective sample fraction from 10.3% to 94.1%.
Sep 26, 2026

Rethinking Training-Inference Mismatch in LLM Reinforcement Learning: Where It Arises and How to Correct It

We study training-inference mismatch in reinforcement learning with verifiable rewards (RLVR) for large language models, where rollouts are sampled by an inference engine while gradients are computed by a training engine, and the two engines assign different probabilities to the same tokens. To account for this discrepancy in policy updates, we introduce calibrated importance sampling (CIS). CIS is motivated by an empirically supported logit-displacement characterization that expresses the mismatch as an additive displacement εt\varepsilon_t in log-odds, determined by the per-logit perturbation before the softmax, whose distribution is approximately invariant to token confidence. This characterization motivates a confidence-aware truncation: large positive displacements are truncated at a single constant threshold, which maps back to an importance-ratio cap that tightens as token confidence increases. Theoretically, we show that CIS replaces the unbounded second moment that governs the error of exact importance sampling with a term bounded by a constant, at the cost of a bias controlled by the truncated excess. In evaluation across three mixture-of-experts models and five mathematical reasoning benchmarks, CIS achieves the highest five-benchmark average on all three models among the evaluated baselines. Diagnostic analyses show that CIS places less truncation bias on low-confidence tokens than truncated importance sampling, while upward clipping of small importance weights reduces held-out accuracy.