# Provably adaptive sampling with uniform and remasking discrete diffusion models arXiv: https://arxiv.org/abs/2608.23554 · HTML: https://mlsanity.com/paper/2608.23554/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. - Builds on 32 of its 36 references that are in the map. - First posted on arXiv 24 Aug 2026. ## Placed in - Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/) ## Builds on (most cited first, 30 of 32) - [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021) - [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024) - [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023) - [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024) - [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022) - [Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data](https://mlsanity.com/paper/2406.03736/) (2024) - [Remasking Discrete Diffusion Models with Inference-Time Scaling](https://mlsanity.com/paper/2503.00307/) (2025) - [Energy-Based Diffusion Language Models for Text Generation](https://mlsanity.com/paper/2410.21357/) (2024) - [Generalized Interpolating Discrete Diffusion](https://mlsanity.com/paper/2503.04482/) (2025) - [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024) - [Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models](https://mlsanity.com/paper/2405.14861/) (2024) - [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025) - [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024) - [Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality](https://mlsanity.com/paper/2410.18784/) (2024) - [Low-dimensional adaptation of diffusion models: Convergence in total variation](https://mlsanity.com/paper/2501.12982/) (2025) - [Fine-Tuning Masked Diffusion for Provable Self-Correction](https://mlsanity.com/paper/2510.01384/) (2025) - [Don't Settle Too Early: Self-Reflective Remasking for Diffusion Language Models](https://mlsanity.com/paper/2509.23653/) (2025) - [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025) - [Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixtures](https://mlsanity.com/paper/2504.05300/) (2025) - [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025) - [Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models](https://mlsanity.com/paper/2506.02318/) (2025) - [Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees](https://mlsanity.com/paper/2509.16756/) (2025) - [Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees](https://mlsanity.com/paper/2602.15008/) (2026) - [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026) - [Uniform Diffusion Models Revisited: Leave-One-Out Denoiser and Absorbing State Reformulation](https://mlsanity.com/paper/2605.22765/) (2026) - [Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics](https://mlsanity.com/paper/2512.00580/) (2025) - [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026) - [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (2026) - [The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity](https://mlsanity.com/paper/2608.13520/) (2026) - [Balancing Understanding and Generation in Discrete Diffusion Models](https://mlsanity.com/paper/2602.01362/) (2026) ## Built on by (most cited first, 4 of 4) - [The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling](https://mlsanity.com/paper/2608.28949/) (2026) - [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026) - [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026) - [Sample complexity bounds for categorical Markov random fields via Discrete Diffusions](https://mlsanity.com/paper/2610.02128/) (2026) ## Abstract (arXiv) 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(DTC(X0) / varepsilon) discretization steps suffice to achieve sampling error O(varepsilonscore+varepsilon), where varepsilonscore 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 DTC(X0), 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 DTC(X0). Numerical experiments on structured synthetic distributions illustrate the predicted dimension-adaptive behavior.