CS Paper Radar

Provably adaptive sampling with uniform and remasking discrete diffusion models

Daniil Dmitriev, Zhihan Huang, Yuting Wei

cs.LG cs.ITmath.STstat.ML ·submitted 2026-08-24 17:54 UTC · v1

Abstract

Discrete diffusion models offer a promising alternative to autoregressive generation by enabling parallel updates, but their sampling efficiency can depend strongly on the choice of the forward process and the sampler. For the uniform forward process, existing lower bounds for the standard $τ$-leaping sampler scale linearly with the ambient dimension $d$, raising the question of whether this dependence is intrinsic to the forward process. We answer this question in the negative. We consider a first-order sampler based on the leave-one-out denoiser for uniform and remasking processes whose coordinate updates can be performed in parallel. In both cases, the sampler can correct denoising mistakes during the sampling process, which becomes necessary when many coordinates are updated together. Our main result establishes an adaptive sampling guarantee: up to logarithmic factors, $N = O(\mathrm{DTC}(X_0) / \varepsilon)$ discretization steps suffice to achieve sampling error $O(\varepsilon_{\mathrm{score}}+\varepsilon)$, where $\varepsilon_{\mathrm{score}}$ is the error in score estimation. Thus, the sampling complexity is governed by the intrinsic dependence structure of the target distribution, as measured by its dual total correlation $\mathrm{DTC}(X_0)$, rather than directly by the ambient dimension $d$. Our analysis proceeds through a Bayes-optimal auxiliary sampler that separates discretization error from score-estimation error. We also derive an exact information-theoretic representation of the discretization error in terms of the mutual information between different coordinates of the forward process at different times. This representation applies to general forward processes and, in the uniform and remasking cases, can be controlled by $\mathrm{DTC}(X_0)$. Numerical experiments on structured synthetic distributions illustrate the predicted dimension-adaptive behavior.

Comment
37 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

LEAP: Accelerating ODE-based Diffusion Sampling with Optimal Linear Leaps

cs.CV ·2026-10-19 ·Haowei Zheng, Zhenyu Zhou, Jiawei Chen, Can Wang, Defang Chen
top venuecode/data similarity 0.63
Abstract

Diffusion models primarily rely on general-purpose ODE-based numerical methods for training-free accelerated sampling, but performance degrades with coarse time discretization. In this paper, we propose optimal linear leaps (LEAP), a specialized method grounded in theoretical and empirical investigations of sampling trajectory geometry. Built upon low-dimensionality and cross-trajectory consistency, LEAP formulates a supervised least-squares optimization problem within the local trajectory subspace, achieving a precise approximation of future states without model evaluations. Extensive experiments demonstrate that LEAP outperforms previous methods across diverse modalities, including text-to-image (Stable Diffusion 3.5, FLUX.1-dev) and image-to-3D (TRELLIS.2) generation. Furthermore, LEAP can be seamlessly integrated into existing solver-based methods, offering a plug-and-play enhancement for modern diffusion models. Code is available at https://github.com/zju-pi/LEAP.

0.49

Lower Bounds for Parallel Diffusion Sampling

cs.DS cs.AIcs.CCcs.LG+1 ·2026-10-06 ·Yiwen Kou, Yimeng Wang
theoryhot direction similarity 0.63
Abstract

Standard diffusion samplers generate samples through sequential evaluations of a learned score function, with each query depending on previous answers. Parallel samplers seek to accelerate this process by making multiple score queries simultaneously. We ask how many adaptive rounds are necessary when each round allows polynomially many queries. We establish the first polynomial lower bounds on the round complexity of diffusion sampling with approximate scores satisfying a mean-square accuracy guarantee. Specifically, we prove (1) a $\widetildeΩ(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $\mathbb{R}^d$, and (2) a tight $Ω(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. Our near-isotropic construction follows the blockwise approach of earlier lower bounds for parallel matroid search and discrete sampling \cite{KUW85,AGR24}. We use independent coordinate blocks containing random codebooks with well-separated rates and construct approximate score oracles whose responses in each block depend on consistency tests in earlier blocks. Together, the rate separation and these tests ensure that each round reveals information about at most one additional block with high probability.

0.50

Adaptive Second-Order Solvers for Fast Stochastic Diffusion Sampling

cs.LG cs.CLcs.CV ·2026-10-02 ·Ella Kemperman, Luca Ambrogioni
code/data similarity 0.62
Abstract · Submitted to ICLR 2027

Diffusion models rely on numerical solvers requiring time-discretization, which has a large influence on the tradeoff between sampling cost and quality. However, the computational difficulty of the reverse process varies along the sampling trajectory and across data distributions, making the choice of discretization important. We adapt proportional-integral (PI) step-size control to diffusion, using our diffusion noise-normalised error estimator. Unlike existing adaptive methods in diffusion that respond only to the current error, the PI solver also incorporates the previous error, yielding smoother step adaptation. We further show that these per-sample trajectories exhibit shared structure and can be aggregated into a fixed schedule that retains much of the benefit of adaptive sampling. We evaluate both approaches on natural-image and language datasets, in terms of quality, measured by FID at a matched number of neural network evaluations (NFE), comparing them with widely used stochastic solvers and schedules. For images, our fixed discretization outperforms the commonly used EDM schedule in terms of sample quality when used with the stochastic Heun sampler, and with the EDM-churn sampler at low NFE. Additionally, our PI adaptive solver obtains better FID than most stochastic and adaptive baselines, although it does not beat the EDM-churn sampler at low NFE. Moreover, we find our solver outperforms both the EDM and the entropy schedule on language diffusion at low-to-medium NFE in terms of perplexity, with the drawback of lower token entropy. Lastly, we find that the benefit of per-sample adaptivity is problem-dependent. It is highly beneficial in 1D toy examples, while only marginal for image and language data, where the average schedule sometimes even outperforms the PI-adaptive solver. Code is available at https://github.com/ellakemperman/adaptive-second-order-diffusion-solvers

0.60

An ODE-based Sampler for Discrete Diffusion Models

cs.LG stat.ML ·2026-10-29 ·Samson Gourevitch, Yazid Janati, Eric Moulines, Eric P. Xing, Alain Durmus +1 more
theory similarity 0.61
Abstract

The marginals of a continuous diffusion model can be reproduced by a deterministic ordinary differential equation (ODE), known as the probability flow ODE, which provides a foundation for accelerated sampling and consistency distillation. In this paper we address the question whether an analogous formulation exists for discrete diffusion models and answer it affirmatively by introducing exponential residual flows (ERFs). Our framework augments the discrete state with a continuous residual variable for each token and position. These residuals evolve deterministically according to piecewise-defined ODEs whose vector fields depend on the current discrete state and the forward and backward rate matrices of the prescribed diffusion model. The discrete state changes whenever a residual reaches zero. We prove that this construction preserves the marginals of the original diffusion. We derive a practical discretization of our sampler and specialize it to masked and uniform diffusion. The deterministic trajectories of ERFs support consistency distillation and yield empirical improvements over previous approaches across a variety of benchmarks including code and text generation tasks.

0.16

Randomization Beyond Deterministic Adaptivity in Parallel Sampling

cs.IT ·2026-10-02 ·Da Li, Bo Jin, Xiaopeng Wei
similarity 0.61
Abstract · 20 pages

Parallel samplers, including masked diffusion models, generate several coordinates per round from conditional marginals, and their accuracy depends on which coordinates are revealed together. A schedule can be improved in two natural ways: adaptively, by choosing later batches from the values already generated, or by randomization, by drawing the schedule at random. We show that randomization is strictly more powerful. For every $r \geq 1$ we construct a full-support distribution on $9r$ binary coordinates such that every deterministic three-round sampler, even with value-dependent batches and arbitrary product kernels, has forward Kullback-Leibler divergence at least $γr - \log 4$ with $γ\approx 0.0966$, whereas drawing one of four fixed schedules with two fair bits drives the divergence below $18 r β^r$ with $β\approx 0.966$. Both samplers query conditionals of the same target. The separation holds for every fixed number of rounds $T \geq 2$, a strict advantage survives perturbations of the target and errors in the conditional predictor, and exact rational arithmetic certifies the gap at nine coordinates, where trained neural predictors preserve it. The mechanism is a hidden mixture: each schedule preserves the dependence pattern of one component, while no deterministic first batch can serve them all.

0.47

Kinetic Langevin Meets Split Gibbs: Accelerated Posterior Sampling for Imaging Inverse Problems with Diffusion Priors

cs.LG stat.ML ·2026-10-07 ·Dai Hai Nguyen, Duc Dung Nguyen
theory similarity 0.61
Abstract

Split Gibbs sampling (SGS) is a popular framework for posterior sampling in Bayesian imaging inverse problems. It decouples a Gaussian data-fidelity term from a complex prior through an auxiliary variable, so the data variable is updated exactly and only the prior-side conditional is hard to sample. Existing samplers treat this conditional in one of two ways. Plug-and-play SGS runs a multi-step diffusion denoiser at every iteration, which is expensive and lacks non-asymptotic guarantees. Langevin-within-SGS takes cheap overdamped Langevin steps but needs many iterations. We propose RED-KLwSGS, which keeps the exact Gaussian update for the data variable and updates the auxiliary variable with underdamped (kinetic) Langevin diffusions driven by a one-shot denoising score, at the same per-iteration cost as Langevin-within-SGS. We prove non-asymptotic Wasserstein-2 convergence in continuous and discrete time for strongly log-concave priors. We also introduce Joint-RED-KLwSGS, which applies kinetic Langevin diffusions to both variables. Experiments with Denoising diffusion probabilistic models as diffusion priors on FFHQ and ImageNet datasets show faster convergence and high-quality image reconstruction.

0.19

Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models

cs.LG stat.ML ·2026-10-09 ·Qiuyun Zhu
similarity 0.61
Abstract · 31 pages

We establish finite-sample guarantees for conditional diffusion models learned from data and implemented with finitely many denoising steps. Our approach aligns the score-training objective with the sampling grid, allowing statistical estimation and numerical discretization errors to be analyzed together. Under a smooth conditional density model, we derive high-probability bounds on the generated distribution's error and quantify the required number of score evaluations. For every smoothness index $β>0$, a suitable grid yields averaged conditional Kullback--Leibler (KL) divergence $\widetilde O_p(n^{-2β/(d_x+d_y+2β)})$ relative to the original target with or without early stopping. Both the full and early-stopped samplers attain average target total-variation (TV) error $\widetilde O_p(n^{-β/(d_x+d_y+2β)})$. Here $n$ is the sample size, $d_x,d_y$ are the data and conditioning dimensions, and errors are averaged over the conditioning variable. The total-variation bound matches the rate established in existing conditional distribution-estimation theory, up to logarithmic factors.

0.32

A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning

cs.LG eess.SPmath.OC ·2026-09-24 ·Ids van der Werf, Sergio Rozada, Antonio G. Marques
similarity 0.61
Abstract · 5 pages, 1 figure

Many iterative algorithms rely on bootstrapping. A variable is updated using a second, frozen copy as a target, which is periodically replaced with the updated variable. Majorize-minimize and inexact proximal-point methods share this structure, as does temporal-difference (TD) learning. However, existing convergence guarantees for scenarios that combine sampled updates with targets refreshed only every $K$ steps rely on the specific structure of the update, such as linear approximation or gradient-based inner steps, and on uniformly bounded sampling error. We instead model the sampled update as a stochastic operator on the parameter space, which reduces the analysis to a contraction argument that needs no gradient structure and allows the sampling error to grow with the iterates. Within this framework, we derive a finite-time bound for i.i.d. samples and any target-update period $K$. We show that the iterates converge geometrically in root mean square to a ball around the fixed point, provided the sensitivity to the frozen target is smaller than the contraction slack of the inner map. Existing deterministic frozen-target contraction and stochastic-gradient-type bounds follow as special cases of our framework, and simulations of TD learning reproduce the predicted contraction rate and scaling of the error floor with the step size.

0.21