mlsanityData to 7 Oct 2026

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

arXiv 2410.02321 ↗First posted 3 Oct 2024cs.LG stat.MLcited by 24

On the map: Diffusion models → Diffusion foundations and sampling

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.

Key facts. Cited by 24 papers in the map (data through 7 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.

Builds on

43 of 53 references.

Closest ancestors · 22

Same direction, newest first

  1. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models5 Aug
  2. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel3 Jun
  3. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity24 May
  4. 2024Accelerating Convergence of Score-Based Diffusion Models, Provably6 Mar
  5. 2024Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization12 Feb
  6. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  7. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models15 Jun
  8. 2023The probability flow ODE is provably fast19 May
  9. 2022Score-based Continuous-time Discrete Diffusion Models30 Nov
  10. 2022From Denoising Diffusions to Denoising Markov Models7 Nov
  11. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  12. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
10 more
  1. 2022Convergence of denoising diffusion models under the manifold hypothesis10 Aug
  2. 2022Convergence for score-based generative modeling with polynomial complexity13 Jun
  3. 2022A Continuous Time Framework for Discrete Denoising Models30 May
  4. 2022Fast Sampling of Diffusion Models with Exponential Integrator29 Apr
  5. 2021Conditional Image Generation with Score-Based Diffusion Models26 Nov
  6. 2021Structured Denoising Diffusion Models in Discrete State-Spaces7 Jul
  7. 2021Cascaded Diffusion Models for High Fidelity Image Generation30 May
  8. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  9. 2020Denoising Diffusion Implicit Models6 Oct
  10. 2020Denoising Diffusion Probabilistic Models19 Jun

Other references · 21

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  2. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  3. 2022Video Diffusion Modelscited by 2,280
  4. 2020DiffWave: A Versatile Diffusion Model for Audio Synthesiscited by 1,339
  5. 2022Diffusion-LM Improves Controllable Text Generationcited by 1,006
  6. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 566
  7. 2021Label-Efficient Semantic Segmentation with Diffusion Modelscited by 495
  8. 2021Score-based diffusion models for accelerated MRIcited by 308
  9. 2024Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Designcited by 294
  10. 2021Deblurring via Stochastic Refinementcited by 248
  11. 2022Diffusion Probabilistic Modeling for Video Generationcited by 237
  12. 2022Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problemcited by 229
9 more
  1. 2023Protein Design with Guided Discrete Diffusioncited by 154
  2. 2023A Reparameterized Discrete Diffusion Model for Text Generationcited by 152
  3. 2022Concrete Score Matching: Generalized Score Matching for Discrete Datacited by 144
  4. 2022High-Frequency Space Diffusion Models for Accelerated MRIcited by 41
  5. 2023Stochastic Segmentation with Conditional Categorical Diffusion Modelscited by 38
  6. 2023Convergence of flow-based generative models via proximal gradient descent in Wasserstein spacecited by 34
  7. 2023ArchiSound: Audio Generation with Diffusioncited by 20
  8. 2023Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Timecited by 20
  9. 2023Diffusion Models in Bioinformatics: A New Wave of Deep Learning Revolution in Actioncited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 14; 2026: 8.

24 papers.

Sort:

By area:

  1. 2025Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmaskingcited by 128
  2. 2024DPLM-2: A Multimodal Diffusion Protein Language Modelcited by 59
  3. 2024How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Frameworkcited by 48
  4. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  5. 2025Fine-Tuning Discrete Diffusion Models with Policy Gradient Methodscited by 36
  6. 2025Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Modelscited by 20
  7. 2025Discrete Diffusion Models: Novel Analysis and New Sampler Guaranteescited by 20
  8. 2025Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamicscited by 11
  9. 2025Demystifying MaskGIT Sampler and Beyond: Adaptive Order Selection in Masked Diffusioncited by 10
  10. 2025Error Analysis of Discrete Flow with Generator Matchingcited by 9
  11. 2025Learnable Sampler Distillation for Discrete Diffusion Modelscited by 8
  12. 2026Sharp Convergence Rates for Masked Diffusion Modelscited by 8
12 more
  1. 2025Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusioncited by 6
  2. 2025Discrete State Diffusion Models: A Sample Complexity Perspectivecited by 4
  3. 2025A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equationscited by 3
  4. 2026Corrected Samplers for Discrete Flow Modelscited by 3
  5. 2025Deterministic Discrete Denoisingcited by 1
  6. 2026From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Modelscited by 1
  7. 2026A Continuous-Time Reinforcement Learning Framework for Fine-Tuning Discrete Diffusion Modelscited by 1
  8. 2026Minimax Optimality of Score-Entropy Discrete Diffusioncited by 1
  9. 2025On the ε-Free Inference Complexity of Absorbing Discrete Diffusioncited by 0
  10. 2026Discrete Diffusion with Sample-Efficient Estimators for Conditionalscited by 0
  11. 2026A Time-Reparameterized Cumulative Intensity Extrapolation Sampler for Discrete Flow Matchingcited by 0
  12. 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. 2025The Effect of Stochasticity in Score-Based Diffusion Sampling: a KL Divergence Analysis
  3. 2026Tightening the Score Matching Gap for Diffusion Models
  4. 2023KL Convergence Guarantees for Score diffusion models under minimal data assumptions
  5. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions
  6. 2024Unified Convergence Analysis for Score-Based Diffusion Models with Deterministic Samplers
  7. 2024Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorial
  8. 2026Diffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guarantees