How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models  via a Stochastic Integral Framework

Authors: Yinuo Ren, Haoxuan Chen, Grant M. Rotskoff, Lexing Ying
Primary area: generative models
Keywords: discrete diffusion models, poisson process, stochastic integral, continuous-time markov chain

Abstract:
Discrete diffusion models have gained increasing attention for their ability to model complex distributions with tractable sampling and inference. However, the error analysis for discrete diffusion models remains less well-understood. In this work, we propose a comprehensive framework for the error analysis of discrete diffusion models based on Lévy-type stochastic integrals. By generalizing the Poisson random measure to that with a time-independent and state-dependent intensity, we rigorously establish a stochastic integral formulation of discrete diffusion models and provide the corresponding change of measure theorems that are intriguingly analogous to Itô integrals and Girsanov's theorem for their continuous counterparts. Our framework unifies and strengthens the current theoretical results on discrete diffusion models and obtains the first error bound for the $\tau$-leaping scheme in KL divergence. With error sources clearly identified, our analysis gives new insight into the mathematical properties of discrete diffusion models and offers guidance for the design of efficient and accurate algorithms for real-world discrete diffusion model applications.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1730325397501

thread_type:
official_review

<thread_object>
creator: reviewer_5uy7

<content>
summary:
This paper investigates the error analysis of discrete diffusion models. To this end, the authors develop a framework based on Levy-type stochastic integrals and establish a stochastic integral formulation of discrete diffusion models. The framework is utilized to derive the first error bound and sheds insight into the design of efficient and accurate discrete diffusion models.

strengths:
1. This paper proposes the first error bound for the diffusion process, which provides insights and guidance for future research on discrete diffusion models.

2. Well-designed examples are presented for better illustration.

3. Rigorous theoretical analyses establish the foundation of the framework and the error bound for discrete diffusion models.

weaknesses:
1. This paper is of theoretical interest. Some simulation experimental results are suggested to confirm the error analysis if possible.

2. This paper is mathematic-heavy. Some insights, intuitions, or illustrations are suggested to provide for better comprehension.

3. The error analysis in Theorem 4.7 is built on four assumptions, which seems to weaken the practicality of the error bound. I suggest the authors justify or explain this point.

questions:
Please refer to the weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730633504301

thread_type:
official_review

<thread_object>
creator: reviewer_5nb2

<content>
summary:
The paper provides a framework to analyze the KL-error of discrete diffusion models using a stochastic integral approach. The authors introduce a formulation for discrete diffusion processes using Poisson random measures with time- and state-dependent intensities. This framework allows them to decompose the error into truncation, approximation, and discretization errors. The key contributions include considering the $\tau$-leaping scheme and establishing an error bound for it in terms of KL divergence.

strengths:
The integral formulation for discrete diffusion models is insightful and provides strong motivation for the proposed algorithms. The error bounds in theorems 4.7 and 4.9 are neat.

weaknesses:
While this is a theory-focused paper, some experimental evaluation would enhance the work, particularly to demonstrate the practical accuracy of the error bounds or the performance of Algorithm 1 and Algorithm 2 in generative applications.

The presentation is highly technical from the outset, assuming a strong theoretical background in diffusion models. The extensive use of dense notation and specialized terminology makes the paper challenging to read and less accessible.

questions:
How important is the request "Q symmetric" for assumptions 4.3--4.6?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699652872

thread_type:
official_review

<thread_object>
creator: reviewer_se7m

<content>
summary:
The paper develops a rigorous theoretical foundation for discrete diffusion models, drawing parallels with continuous diffusion models. The authors introduce a novel stochastic integral framework using Lévy-type integrals, which enables a structured representation of discrete diffusion processes. They establish change-of-measure techniques analogous to Girsanov’s theorem, facilitating error analysis in terms of KL divergence.
By decomposing errors into truncation, approximation, and discretization components, the paper provides the first KL divergence bounds for the τ-leaping scheme in discrete settings. This unified framework also compares $\tau$-leaping and uniformization methods, highlighting computational efficiency and accuracy. Overall, the work advances the theoretical understanding of discrete diffusion models, making it possible to design more accurate and efficient algorithms for real-world applications that require discrete data modeling.

strengths:
1.Theorem 3.3 establishes a change of measure theorem for Poisson random measures with evolving intensity, the authors introduce a discrete analog to Girsanov's theorem. This is a breakthrough, as it enables KL divergence analysis for discrete models, a theoretical advancement that makes error analysis feasible for the discrete setting.
2.Section 4, the paper follows a classical error analysis for diffusion models, breaking down error into truncation, approximation, and discretization components. This analysis, grounded in Theorems 4.7 and 4.9, is particularly valuable as it allows for practical application through the $\tau$-leaping and uniformization algorithms, with explicit convergence guarantees.
3.The paper presents the first KL divergence bounds for the t-leaping scheme in discrete diffusion models. This error bound is stronger and more informative than prior work using total variation distance.

weaknesses:
I don't see major weaknesses of this work, but I have some comments:
1. The paper provides rigorous theoretical error bounds for τ-leaping and uniformization (Theorems 4.7 and 4.9). Do the authors plan to empirically validate these bounds on synthetic or real-world datasets? 
2. Could the authors provide runtime or memory complexity comparisons for τ-leaping versus uniformization under varying parameters?
3. The paper centers on Lévy-type integrals for discrete diffusion models. Could the authors comment on other potential stochastic frameworks for discrete models and when the proposed Lévy-type integral framework would be preferable over alternatives?

questions:
see above Weaknesses section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730977731825

thread_type:
official_review

<thread_object>
creator: reviewer_xlaw

<content>
summary:
This paper addresses the challenge of error analysis in discrete diffusion
models. To bridge the gap between discrete and continuous diffusion models
(for which the error analysis is better understood), the authors propose a
framework based on Levy-type stochastic integrals, by generalizing Poisson
random measures to support state-dependent and time-varying intensities
under assumptions of regularity of rate matrix, and bounded and continuous
score function. This framework allows for error decomposition into
components such as truncation, approximation, and discretization errors,
providing clearer insight into error sources.  The analysis is performed
for tau-leaping and uniformization methods, two methods to simulate the
backward process. They establish stronger error bounds compared to previous
work using KL divergence.

strengths:
Pros:
- Very non-trivial theoretical work.

weaknesses:
Cons:
- Positioning of the work is not clear. It is not compared clearly with
  previous work.
- Motivation and implications for practical usage not provided.
- Very dense writing. Hard to understand.

Details:
The main results are two theorems, one for tau-leaping and the other for
uniformization. No attempt is made to provide outlines of the proofs. What
is the basic motivation for this research? How does it contribute to the
field (reduce algorithmic complexity, improve guarantees, etc.)?
The reader could greatly benefit from proof outlines.

The paper is very hard to understand. For a reader who is not deeply
immersed in this topic, it is almost impossible to understand the
implications, general approaches, and the proofs themselves.

The third bullet in contributions says that the work unifies and fortifies
existing research on discrete diffusion models. The reviewer did not come
across any statement in support of this or elaborating this point.

Related works does not cover any theoretical work on discrete diffusion
models. The introduction does mention several papers in this regard.
Organization can be made better.

The paper starting at Preliminaries is very dense. That said, the authors
have put effort to state the assumptions clearly and provided discussions
on differences between continuous and discrete diffusion models w.r.t. the
various errors considered.

questions:
Questions inserted in weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731977232300

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common Responses

comment:
We sincerely thank all the reviewers for their constructive feedback and for recognizing the contributions of our work. We are encouraged by the positive comments describing our framework as "*insightful*" and a "*breakthrough*," with "*well-designed examples*" and "*stronger and more informative*" results. Below, we address two common concerns raised by multiple reviewers.

---

## Regarding the Presentation (Reviewers XLAW, 5nb2, 5uy7)

We acknowledge the reviewers' concerns about the paper's readability and accessibility. As a theoretical work, our primary objective is to develop a rigorous stochastic integral-based framework for discrete diffusion models. At the same time, we aim to draw clear comparisons with continuous diffusion models to provide insight into the implications and guarantees of our results. This dual focus inevitably involves significant mathematical depth and detailed notations.
 
However, we recognize that the presentation may have become overly dense, potentially making it less accessible to a broader audience who may not have the opportunity to delve into all the technical details. To address these issues, we propose the following revisions:

- **Section 1 (Introduction)**: We will clarify the differences between continuous and discrete diffusion models, emphasize the motivations for discrete formulations, and outline the challenges in their theoretical analysis compared to continuous counterparts.
- **Section 3 (Stochastic Integral Formulation)**: We will supplement the existing formal definitions with verbal explanations and illustrative examples. Some technical details will be moved to the appendix to improve the flow of the main text. To aid understanding, we will introduce examples demonstrating the properties of Poisson random measures with evolving intensities. We will also expand the discussion on the motivation for using Lévy-type integrals to provide a more intuitive interpretation.
- **Section 3.2 (Change of Measure)**: This section will be expanded to elaborate on the connection between the continuous and discrete frameworks. Specifically, we will clarify how the change of measure theorem parallels Girsanov's theorem for continuous models and its role in enabling the error analysis for the $\tau$-leaping and uniformization algorithms.
- **Section 4 (Error Analysis)**: We will provide clearer algorithmic descriptions and brief justifications for the $\tau$-leaping and uniformization methods. Additionally, we will outline the analytical challenges each algorithm presents, including their error decomposition into truncation, approximation, and discretization components.
- **Proof Sketches for Theorems**: Proof sketches for Theorems 4.7 and 4.9 will be included in the appendix to outline the key ideas and techniques used in the proofs, addressing the feedback about providing insights into the theoretical foundations of our results.
  
We believe these revisions will significantly enhance the accessibility of the paper without compromising its rigor. They will help readers better grasp the theoretical contributions and implications, and facilitate further research in discrete diffusion models.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732522359607

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revision Summary

comment:
We appreciate all the reviewers for their constructive feedback, which have greatly helped improve the quality of our manuscript. We have revised our manuscript to enhance readability and accessibility as suggested and marked all modifications in blue. Notable changes include clearer motivations in the introduction, and enriched explanations and insights in Section 3. We have also streamlined the main text by relocating some complex details to the appendix, and adding proof sketches for key theorems in Appendix C.1 to clarify our theoretical approaches. These revisions aim to make our content more accessible and understandable without compromising its rigor. We are grateful for your insights and hope our revision has addressed their concerns on the presentation of our work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
In order to unify the theoretical analysis of continuous and discrete diffusion models, this paper introduces a stochastic integral formulation based on Lévy-type stochastic integrals and generalizes the Poisson random measure to one with time-independent and state-dependent intensity. It provides change of measure theorems analogous to Itô integrals and Girsanov's theorem for continuous diffusion models. The proposed framework unifies and strengthens existing theoretical results, offering the first error bound for the τ-leaping scheme in KL divergence. This paper has received unanimous support from the reviewers. Therefore, I recommend acceptance. In the camera-ready version, the authors are encouraged to include a more detailed comparison with the concurrent work by Zhang et al. (2024), as both works analyze K states for each discrete random variable/token. While the sampling algorithms differ (uniformization vs. τ-leaping), the main theorems appear similar, thus a comparison between them would be helpful.