# Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics arXiv: https://arxiv.org/abs/2512.00580 ยท HTML: https://mlsanity.com/paper/2512.00580/ ## Key facts - Cited by 11 papers in the map (data through 14 Oct 2026). - Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. - Builds on 22 of its 48 references that are in the map. - First posted on arXiv 29 Nov 2025. ## Placed in - Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/) ## Builds on (most cited first, 22 of 22) - [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020) - [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022) - [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020) - [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) - [WaveGrad: Estimating Gradients for Waveform Generation](https://mlsanity.com/paper/2009.00713/) (2020) - [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022) - [Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning](https://mlsanity.com/paper/2208.04202/) (2022) - [Discrete Flow Matching](https://mlsanity.com/paper/2407.15595/) (2024) - [Score-Based Generative Modeling with Critically-Damped Langevin Diffusion](https://mlsanity.com/paper/2112.07068/) (2021) - [Continuous diffusion for categorical data](https://mlsanity.com/paper/2211.15089/) (2022) - [Generator Matching: Generative modeling with arbitrary Markov processes](https://mlsanity.com/paper/2410.20587/) (2024) - [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024) - [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024) - [Categorical SDEs with Simplex Diffusion](https://mlsanity.com/paper/2210.14784/) (2022) - [Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis](https://mlsanity.com/paper/2410.02321/) (2024) - [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) - [Error Analysis of Discrete Flow with Generator Matching](https://mlsanity.com/paper/2509.21906/) (2025) - [Sampling Binary Data by Denoising through Score Functions](https://mlsanity.com/paper/2502.00557/) (2025) - [Piecewise deterministic generative models](https://mlsanity.com/paper/2407.19448/) (2024) ## Built on by (most cited first, 11 of 11) - [Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees](https://mlsanity.com/paper/2602.15008/) (2026) - [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (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) - [Non-Asymptotic Error Bounds for SMC with Biased Proposals: Application to Conditional Diffusion Sampling](https://mlsanity.com/paper/2607.04780/) (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) - [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) ## Abstract (arXiv) Diffusion models for continuous state spaces based on Gaussian noising processes are now relatively well understood from both practical and theoretical perspectives. In contrast, results for diffusion models on discrete state spaces remain far less explored and pose significant challenges, particularly due to their combinatorial structure and their more recent introduction in generative modelling. In this work, we establish new and sharp convergence guarantees for three popular discrete diffusion models (DDMs). Two of these models are designed for finite state spaces and are based respectively on the random walk and the masking process. The third DDM we consider is defined on the countably infinite space mathbbNd and uses a drifted random walk as its forward process. For each of these models, the backward process can be characterized by a discrete score function that can, in principle, be estimated. However, even with perfect access to these scores, simulating the exact backward process is infeasible, and one must rely on time discretization. In this work, we study Euler-type approximations and establish convergence bounds in both Kullback-Leibler divergence and total variation distance for the resulting models, under minimal assumptions on the data distribution. To the best of our knowledge, this study provides the optimal non-asymptotic convergence guarantees for these noising processes that do not rely on boundedness assumptions on the estimated score. In particular, the computational complexity of each method scales only linearly in the dimension, up to logarithmic factors.