# Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

arXiv: https://arxiv.org/abs/2602.15008 · HTML: https://mlsanity.com/paper/2602.15008/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 8 of its 50 references that are in the map.
- First posted on arXiv 16 Feb 2026.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 8 of 8)

- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [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)
- [Scaling Behavior of Discrete Diffusion Language Models](https://mlsanity.com/paper/2512.10858/) (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)
- [Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics](https://mlsanity.com/paper/2512.00580/) (2025)
- [Sampling Binary Data by Denoising through Score Functions](https://mlsanity.com/paper/2502.00557/) (2025)

## Built on by (most cited first, 19 of 19)

- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [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)
- [Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling](https://mlsanity.com/paper/2607.00773/) (2026)
- [Provably adaptive sampling with uniform and remasking discrete diffusion models](https://mlsanity.com/paper/2608.23554/) (2026)
- [Vocabulary-size-independent Convergence of Discrete Diffusion Models: adjoint equations induce the right space](https://mlsanity.com/paper/2605.17232/) (2026)
- [Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions](https://mlsanity.com/paper/2605.30153/) (2026)
- [Minimax Optimality of Score-Entropy Discrete Diffusion](https://mlsanity.com/paper/2608.20635/) (2026)
- [ConvergeFlow: Language Flow with Provable Convergence to Token Embeddings](https://mlsanity.com/paper/2608.23551/) (2026)
- [The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling](https://mlsanity.com/paper/2608.28949/) (2026)
- [Discrete Flow Matching: Convergence Guarantees Under Minimal Assumptions](https://mlsanity.com/paper/2605.08882/) (2026)
- [From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models](https://mlsanity.com/paper/2605.27352/) (2026)
- [Diffusion Models Adapt to Low-Dimensional Structure Under Flexible Coefficient Choices](https://mlsanity.com/paper/2606.23627/) (2026)
- [Latent-Kernel Discrete Flow Maps for Few-Step Generation](https://mlsanity.com/paper/2607.27529/) (2026)
- [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026)
- [Schedule optimization for tau-leaping in masked discrete diffusion](https://mlsanity.com/paper/2609.21960/) (2026)
- [Sample complexity bounds for categorical Markov random fields via Discrete Diffusions](https://mlsanity.com/paper/2610.02128/) (2026)
- [Training Parallel Speculative Draft Models by Directly Minimizing Expected Decoding Rounds](https://mlsanity.com/paper/2610.10411/) (2026)

## Abstract (arXiv)

Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on τ-leaping-based samplers. We establish sharp convergence guarantees for attaining varepsilon accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that the τ-leaping algorithm achieves an iteration complexity of order tilde O(d/varepsilon), with d the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size S and improving existing bounds by a factor of d; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified τ-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by d log S but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.