# Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 43 of its 53 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## Placed in

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

## Builds on (most cited first, 30 of 43)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [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)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Video Diffusion Models](https://mlsanity.com/paper/2204.03458/) (2022)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [Cascaded Diffusion Models for High Fidelity Image Generation](https://mlsanity.com/paper/2106.15282/) (2021)
- [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [Fast Sampling of Diffusion Models with Exponential Integrator](https://mlsanity.com/paper/2204.13902/) (2022)
- [Label-Efficient Semantic Segmentation with Diffusion Models](https://mlsanity.com/paper/2112.03126/) (2021)
- [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)
- [Score-based diffusion models for accelerated MRI](https://mlsanity.com/paper/2110.05243/) (2021)
- [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024)
- [Deblurring via Stochastic Refinement](https://mlsanity.com/paper/2112.02475/) (2021)
- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Diffusion Probabilistic Modeling for Video Generation](https://mlsanity.com/paper/2203.09481/) (2022)
- [Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problem](https://mlsanity.com/paper/2206.04119/) (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)
- [Conditional Image Generation with Score-Based Diffusion Models](https://mlsanity.com/paper/2111.13606/) (2021)
- [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)
- [Protein Design with Guided Discrete Diffusion](https://mlsanity.com/paper/2305.20009/) (2023)
- [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)

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

- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [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)
- [Fine-Tuning Discrete Diffusion Models with Policy Gradient Methods](https://mlsanity.com/paper/2502.01384/) (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)
- [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)
- [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)
- [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)
- [A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations](https://mlsanity.com/paper/2508.14351/) (2025)
- [Corrected Samplers for Discrete Flow Models](https://mlsanity.com/paper/2601.22519/) (2026)
- [Minimax Optimality of Score-Entropy Discrete Diffusion](https://mlsanity.com/paper/2608.20635/) (2026)
- [A Continuous-Time Reinforcement Learning Framework for Fine-Tuning Discrete Diffusion Models](https://mlsanity.com/paper/2607.14522/) (2026)
- [Deterministic Discrete Denoising](https://mlsanity.com/paper/2509.20896/) (2025)
- [From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models](https://mlsanity.com/paper/2605.27352/) (2026)
- [On the ε-Free Inference Complexity of Absorbing Discrete Diffusion](https://mlsanity.com/paper/2509.21835/) (2025)
- [Discrete Diffusion with Sample-Efficient Estimators for Conditionals](https://mlsanity.com/paper/2602.20293/) (2026)
- [A Time-Reparameterized Cumulative Intensity Extrapolation Sampler for Discrete Flow Matching](https://mlsanity.com/paper/2606.24140/) (2026)
- [Sample complexity bounds for categorical Markov random fields via Discrete Diffusions](https://mlsanity.com/paper/2610.02128/) (2026)

## Abstract (arXiv)

Diffusion models have achieved great success in generating high-dimensional samples across various applications. While the theoretical guarantees for continuous-state diffusion models have been extensively studied, the convergence analysis of the discrete-state counterparts remains under-explored. In this paper, we study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space [S]d that utilizes score estimators at predefined time points. We derive convergence bounds for the Kullback-Leibler (KL) divergence and total variation (TV) distance between the generated sample distribution and the data distribution, considering both scenarios with and without early stopping under reasonable assumptions. Notably, our KL divergence bounds are nearly linear in the dimension d, aligning with state-of-the-art results for diffusion models. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function, which are essential for characterizing the discrete-time sampling process.