# Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization

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

## Key facts

- Cited by 44 papers in the map (data through 14 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.

## Placed in

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

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

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Maximum Likelihood Training of Score-Based Diffusion Models](https://mlsanity.com/paper/2101.09258/) (2021)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [MultiDiffusion: Fusing Diffusion Paths for Controlled Image Generation](https://mlsanity.com/paper/2302.08113/) (2023)
- [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Score-based Continuous-time Discrete Diffusion Models](https://mlsanity.com/paper/2211.16750/) (2022)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [Concrete Score Matching: Generalized Score Matching for Discrete Data](https://mlsanity.com/paper/2211.00802/) (2022)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [On the Generalization Properties of Diffusion Models](https://mlsanity.com/paper/2311.01797/) (2023)
- [From Denoising Diffusions to Denoising Markov Models](https://mlsanity.com/paper/2211.03595/) (2022)
- [Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generation](https://mlsanity.com/paper/2301.00427/) (2023)
- [Blackout Diffusion: Generative Diffusion Models in Discrete-State Spaces](https://mlsanity.com/paper/2305.11089/) (2023)
- [Discrete Object Generation with Reversible Inductive Construction](https://mlsanity.com/paper/1907.08268/) (2019)
- [Diffusion Models in Bioinformatics: A New Wave of Deep Learning Revolution in Action](https://mlsanity.com/paper/2302.10907/) (2023)

## Built on by (most cited first, 30 of 44)

- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling](https://mlsanity.com/paper/2409.02908/) (2024)
- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [Accelerating Convergence of Score-Based Diffusion Models, Provably](https://mlsanity.com/paper/2403.03852/) (2024)
- [An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimization](https://mlsanity.com/paper/2404.07771/) (2024)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [DPLM-2: A Multimodal Diffusion Protein Language Model](https://mlsanity.com/paper/2410.13782/) (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)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [KLASS: KL-Guided Fast Inference in Masked Diffusion Models](https://mlsanity.com/paper/2511.05664/) (2025)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Evaluating the design space of diffusion-based generative models](https://mlsanity.com/paper/2406.12839/) (2024)
- [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025)
- [Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis](https://mlsanity.com/paper/2410.02321/) (2024)
- [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025)
- [MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control](https://mlsanity.com/paper/2508.10684/) (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)
- [Solving Inverse Problems via Diffusion-Based Priors: An Approximation-Free Ensemble Sampling Approach](https://mlsanity.com/paper/2506.03979/) (2025)
- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics](https://mlsanity.com/paper/2512.00580/) (2025)
- [Demystifying MaskGIT Sampler and Beyond: Adaptive Order Selection in Masked Diffusion](https://mlsanity.com/paper/2510.04525/) (2025)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [What Exactly Does Guidance Do in Masked Discrete Diffusion Models](https://mlsanity.com/paper/2506.10971/) (2025)
- [Error Analysis of Discrete Flow with Generator Matching](https://mlsanity.com/paper/2509.21906/) (2025)
- [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (2026)
- [Learnable Sampler Distillation for Discrete Diffusion Models](https://mlsanity.com/paper/2509.19962/) (2025)
- [On the Reasoning Abilities of Masked Diffusion Language Models](https://mlsanity.com/paper/2510.13117/) (2025)
- [Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion](https://mlsanity.com/paper/2505.21892/) (2025)
- [Discrete State Diffusion Models: A Sample Complexity Perspective](https://mlsanity.com/paper/2510.10854/) (2025)

## 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.