mlsanityData to 13 Oct 2026

Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization

arXiv 2402.08095 ↗First posted 12 Feb 2024stat.ML cs.LGcited by 44

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Diffusion models have achieved huge empirical success in data generation tasks. Recently, some efforts have been made to adapt the framework of diffusion models to discrete state space, providing a more natural approach for modeling intrinsically discrete data, such as language and graphs. This is achieved by formulating both the forward noising process and the corresponding reversed process as Continuous Time Markov Chains (CTMCs). In this paper, we investigate the theoretical properties of the discrete diffusion model. Specifically, we introduce an algorithm leveraging the uniformization of continuous Markov chains, implementing transitions on random time points. Under reasonable assumptions on the learning of the discrete score function, we derive Total Variation distance and KL divergence guarantees for sampling from any distribution on a hypercube. Our results align with state-of-the-art achievements for diffusion models in ℝd and further underscore the advantages of discrete diffusion models in comparison to the ℝd setting.

Key facts. Cited by 44 papers in the map (data through 13 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 28 of its 41 references that are in the map. First posted on arXiv 12 Feb 2024.

Builds on

28 of 41 references.

Closest ancestors · 16

Same direction, newest first

  1. 2023On the Generalization Properties of Diffusion Models3 Nov
  2. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  3. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models15 Jun
  4. 2023The probability flow ODE is provably fast19 May
  5. 2023Blackout Diffusion: Generative Diffusion Models in Discrete-State Spaces18 May
  6. 2022Score-based Continuous-time Discrete Diffusion Models30 Nov
  7. 2022From Denoising Diffusions to Denoising Markov Models7 Nov
  8. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  9. 2022Convergence of score-based generative modeling for general data distributions26 Sep
  10. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
  11. 2022Convergence of denoising diffusion models under the manifold hypothesis10 Aug
  12. 2022Convergence for score-based generative modeling with polynomial complexity13 Jun
4 more
  1. 2022A Continuous Time Framework for Discrete Denoising Models30 May
  2. 2021Improved Denoising Diffusion Probabilistic Models18 Feb
  3. 2021Maximum Likelihood Training of Score-Based Diffusion Models22 Jan
  4. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov

Other references · 12

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,023
  2. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,564
  3. 2021Zero-Shot Text-to-Image Generationcited by 4,284
  4. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,077
  5. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 570
  6. 2023MultiDiffusion: Fusing Diffusion Paths for Controlled Image Generationcited by 532
  7. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 266
  8. 2023A Reparameterized Discrete Diffusion Model for Text Generationcited by 152
  9. 2022Concrete Score Matching: Generalized Score Matching for Discrete Datacited by 146
  10. 2023Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generationcited by 46
  11. 2019Discrete Object Generation with Reversible Inductive Constructioncited by 16
  12. 2023Diffusion Models in Bioinformatics: A New Wave of Deep Learning Revolution in Actioncited by 15

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 9; 2025: 21; 2026: 14.

44 papers.

Sort:

By area:

  1. 2025Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusionscited by 211
  2. 2024Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Samplingcited by 206
  3. 2025Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmaskingcited by 129
  4. 2024Accelerating Convergence of Score-Based Diffusion Models, Provablycited by 74
  5. 2024An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimizationcited by 72
  6. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Modelscited by 64
  7. 2024DPLM-2: A Multimodal Diffusion Protein Language Modelcited by 61
  8. 2024How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Frameworkcited by 48
  9. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  10. 2025KLASS: KL-Guided Fast Inference in Masked Diffusion Modelscited by 46
  11. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  12. 2024Evaluating the design space of diffusion-based generative modelscited by 25
32 more
  1. 2025Optimal Inference Schedules for Masked Diffusion Modelscited by 25
  2. 2024Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysiscited by 24
  3. 2025Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Modelscited by 23
  4. 2025Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Modelscited by 20
  5. 2025MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Controlcited by 20
  6. 2025Discrete Diffusion Models: Novel Analysis and New Sampler Guaranteescited by 20
  7. 2025Solving Inverse Problems via Diffusion-Based Priors: An Approximation-Free Ensemble Sampling Approachcited by 18
  8. 2026Confidence-Based Decoding is Provably Efficient for Diffusion Language Modelscited by 17
  9. 2025Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamicscited by 11
  10. 2025Demystifying MaskGIT Sampler and Beyond: Adaptive Order Selection in Masked Diffusioncited by 10
  11. 2025What Exactly Does Guidance Do in Masked Discrete Diffusion Modelscited by 9
  12. 2025Error Analysis of Discrete Flow with Generator Matchingcited by 9
  13. 2026Adaptation to Intrinsic Dependence in Diffusion Language Modelscited by 9
  14. 2025Learnable Sampler Distillation for Discrete Diffusion Modelscited by 8
  15. 2026Sharp Convergence Rates for Masked Diffusion Modelscited by 8
  16. 2025Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusioncited by 6
  17. 2025On the Reasoning Abilities of Masked Diffusion Language Modelscited by 6
  18. 2025Discrete State Diffusion Models: A Sample Complexity Perspectivecited by 4
  19. 2026Discrete Adjoint Schr"odinger Bridge Samplercited by 4
  20. 2026Corrected Samplers for Discrete Flow Modelscited by 3
  21. 2026Flow Matching for Count Datacited by 3
  22. 2026Accelerating Discrete Diffusion Models with Parallel-In-Time Samplingcited by 3
  23. 2026Provably adaptive sampling with uniform and remasking discrete diffusion modelscited by 3
  24. 2025Foundations of Diffusion Models in General State Spaces: A Self-Contained Introductioncited by 2
  25. 2026Minimax Optimality of Score-Entropy Discrete Diffusioncited by 2
  26. 2025Non-asymptotic convergence bound of conditional diffusion modelscited by 1
  27. 2026From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Modelscited by 1
  28. 2026A Mathematical Introduction to Diffusion Modelscited by 1
  29. 2026Parallelism, critical windows, and separations among diffusion language modelscited by 1
  30. 2025On the ε-Free Inference Complexity of Absorbing Discrete Diffusioncited by 0
  31. 2026Discrete Diffusion with Sample-Efficient Estimators for Conditionalscited by 0
  32. 2026Sample complexity bounds for categorical Markov random fields via Discrete Diffusionscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
  2. 2025Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions
  3. 2022Diffusion Models for Graphs Benefit From Discrete State Spaces
  4. 2024Unified Discrete Diffusion for Categorical Data
  5. 2026Learning Discrete Diffusion of Graphs via Free-Energy Gradient Flows
  6. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
  7. 2024Discrete-state Continuous-time Diffusion for Graph Generation
  8. 2026Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size