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
Venue: ICLR 2025 Poster (2025)
Keywords: Discrete diffusion models
Poisson process
stochastic integral
continuous-time Markov chain
Primary area: generative models
TL;DR: We represent discrete diffusion models as stochastic integrals, offering a general framework for their error analysis.

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.

Published as a conference paper at ICLR 2025
How DISCRETE AND CONTINUOUS DIFFUSION MEET: COMPREHENSIVE ANALYSIS OF DISCRETE DIFFUSION MODELS VIA A STOCHASTIC INTEGRAL FRAMEWORK
Yinuo Ren
Haoxuan Chen
ICME
ICME
Stanford University Ainuoren@stanfozee
Stanford University
haoxuano@stanforddcc
Grant M. Rotskoff
Lexing Ying
Department of Chemistry and ICME
Department of Mathematics and ICME
Stanford University
Stanford University
rot wwkoff@sttanfrd....
Boking@stanfordd edu
ABSTRACT
Discrete diffusion models have gained increasing attention for their ability model complex distributions with tractable sampling and inference. However, the eπтоr analysis for discrete diffusion models remains less well-understood. In this work, we propose a comprehensive framework for the error analysis of dis- crete diffusion models based on Lévy-type stochastic integrals. By generalizing the Poisson random measure to that with time-independen and state-dependent intensity, we rigorously establish a stochastic integral formulation of discrete dif- fusion models and provide the corresponding change of measure theorems that are intriguingly analogous
integrals and Girsanov's theorem for their con- tinuous counterparts. Our framework unifies and strengthens the current theoret- ical results on discrete diffusion models and obtains the first error bound for the r-leaping scheme in KI. divergence. With 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.
sources clearly identified,
INTRODUCTION
Diffusion and fow-baaed models designed for discrete distributions have gained significant attention in recent years due to their versatility and wide applicability across various domains. These models have been proposed and refined in several key works (Sohl bickstenn ctal 2015 Aushi ef all 2021; Floto et al, 2023; Hoogeboom all 2021a:6; Meng all 2022: Richemond et all 2022: Sun all 2022: Santos et all 2023). The appeal of such models stems from their potential to address challeng- ing problems in fields like computational biology, where they have shown promise tasks such as molecule, protein, and DNA sequence design etal, 2019; Alamdari el all 2023: Avdeyev et al,,
2023% 5mami et all 202% Frey all, 2023; Watson all 2023: Yang et all, 2020 Campbell all
2024:
Stark el all 2022: Kerby & Moon, R0ZE: Y el all 2024). Additionally, these approaches have
proven effective combinatorial optimization (L all (022))) modeling retrosynthesis (Lgashov et all 2023), image synthesis (Lezama et all 2022: Gu et all (022), text summarization DDat et all
2024)) along with the generation of graph (Niu et all 2026 Shi all 2020: QQn all 2023: ML
gnac et all 2022).. layout (Inoue et all, 2023; Zhang et all, 20233) motion (Chi et all 2024 Lou
all 2023). sound (Campbell et all, 2022: Yang et all MI23a),, image (En all 2022: Zhu
2022)
Ren etll 20258), speech (Wi et all (0244 and text (He all 202% Wi et all 212K Gong
al. 2023 Zheng et all 2023; Zhou et all 212E Shi et all 2024, Sahoo et all (022)) Discrete
diffusion models also synergize with other methodologies, including tensor networks (C (Causer
2024), enhanced guidance mechanisms (Gruver et al. 2024; Nisonoft all 2024 Li Liet all 2024H)
structured preferential generation (Rissanen all 2024). and altemative metrics, e.g. the Fisher

---

Published as a conference paper at ICLR 2025
information metric (Davis all
2023). These developments highlight the growing importance of discrete modeling in advancing both theoretical understanding and efficient implementations. For a more complete review of related literature, may refer to the appendix of Ren al (2025a).
Partly due to the absence of a discrete equivalent to Girsanov's theorem, the error analysis for dis- crete diffusion models remains underdeveloped compared their continuous counterparts. Existing theoretical work, including a Markov chain-based error analysis for r-leaping in total variation dis- tance by Campbell al. (2022) and further advancements for the particular state space X = {0, 1jdd by Chen & Ying (2024), are largely algorithm-specific and not quite easy to be generalized. In this work, our goal to establish comprehensive framework for analyzing discrete diffusion mod- els through a stochastic analysis perspective, which is motivated by the theory of continuous dif- fusion models and different from previous works in many aspects. Drawing on tools from Lévy processes and methodologies for analyzing the simulations of chemical reactions (Li, 2007; Ander son all I0TI), we extend Poisson random measures to those with evolving intensities, iee. both time-inhomogencouus and state-dependent intensities (Profter, 1T83), introduce Lévy-type stochastic integrals (Applebaum, 2009), and articulate corresponding change of measure theorems, which are analogous the Itō integrals and Girsanov's theorem in continuous settings.
We further demonstrate that discrete diffusion models implemented via either the r-leaping or the uniformization scheme can be formulated as stochastic integrals w.r.t Poisson random measures with evolving intensity, which leads to a unified framework for error analysis. This new stochas- tic integral- -based framework, marking first for discrete diffusion models, is especially convenient and straightforward for decomposing inference error into three parts: truncation, approximation, and discretization, drawing satisfying parallels with state-of-the-art theories for continuous diffu- sion model (Chen et all 2022: 20233: [Benton et all, 2023a). Our approach thus provides intuitive explanations for the loss design and unifies the eтror analysis across both schemes, enhancing the comparative understanding of their convergence characteristics. Notably, we achieve stronger con- vergence results in KI. divergence and relax some of the stringent assumptions previously required for the state space, the rate matrix, and the estimation of score functions, etc., thereby paving the way for the analysis of a broader class of discrete diffusion models of interest, providing valuable tools for designing efficient and accurate algorithms tailored to the practical demands of discrete diffusion models in real-world applications, and facilitating the transfer of theoretical and practical insights between continuous and discrete diffusion models.
1.1 CONTRIBUTIONS
Our main contributions are summarized as follows:
We develop rigorous framework for discrete diffusion models using Lévy-type stochastic inte- grals based on the Poisson random measure with evolving intensity, which includes formulating discrete diffusion models into stochastic integrals and establishing change of measure theorems that facilitate explicit logelikelioood ratio calculations;
Our framework extends to comprehensive, continuous-timg analysis for error decomposition in discrete diffusion models, drawing clear parallels with the methodologies used in continuous models and enabling more effective adaptations of techniques across different model types;
We unify and fortify existing research on discrete diffusion models by deriving the first error bound for r-leaping in terms of KL divergence, stronger compared to earlier results in TV dis- tance, and providing a comparative study of r-leaping and uniformization implementations.
1.2 RELATED WORKS
Continuous Diffuusio Models, Continuous diffusion models have been one of the most active research areas in generative modeling. Earlier work on continuous diffusion models and probability
flow-based models include (Sohl-Dickstein et all, 20155; Zhang et all 2018; /Sng & Ermon, 2019
Ho all 2020: Song all, 2020, 2021; Lipman et al., 2022 Liu all 2022 Albergo & Vanden- Einnden 2122; Albergo el all 2023). It has shown state-of- performance in various fields of science and engineering. For some recent work and comprehensive review articles, one may refer
to (Xu et all R022 Yang el al, 2023;; Chani 2024; Wang et al, 2023% Alakhdar et all 2024; Chen
202215
et all 2024k Guo et 2024: RieseLetal 2024: elal 2024)..
Theory of Continuous Diffusion Models. In addition to the huge success achieved by diffusion models in empirical studies, many works have also tried to establish sampling guarantees for diffu-
2

---

Published as a conference paper at ICLR 2025
sion and probability flow-based models, such as (Izen & Raginsky, 2019 Block et all 2020: Benton
etall 20235; Cheneral 20235; MMacke & Rivasplata 2023: Liang et al. 2024; Benton et all 2024
Ren et all (0256). Regarding theoretical analysis of continuous diffusion models, (Lee et all 2022) provided the first sampling guarantee under the smoothness and isoperimetry assumptions. Follow- up work removed such assumptions (Chen et all, 2022; 2023a Lee et all 2023) and obtained better convergence results (Benton et all Ma2 Pedrott el all 2023: Lt el all
M02:; (0227))) For the
probability flow-based implementation, sampling guarantee was also established and further refined in many recent work (Chen et all, 2(224) Gao & Zhu, R0224 Huang et al. 20224 Li 2(224)))
PRELIMINARIES
In this section, we introduce the basic concepts of both continuous and discrete diffusion models and then roughly outline the emror analysis for continuous diffusion models, which will serve reference for the error analysis for discrete diffusion models.
2.1 CONTINUOUS DIFFUSION MODELS
In diffusion models, the forward process is designed an Itô process (æt)ugigr in Rd satisfying the following stochastic differential equation (SDE):
dæ: b, b. (dl + gidwu, with 20 po:
(2.1)
where (w;)c20 is standard Brownian motion. The probability distribution of æt is denoted by Pt, and the distribution po time t (I, (es)s of (2.J) satisfies the backward process:
the target distribution for sampling. The time-reversal
dē = [- 1- (t..) + G. v logă, (t.) ds + J.w..,
(2.2)
where v, denotes #2-a, with Po = Pr and PT = Pu-
One of the common choices for the drift b, and the diffusion coefficient g is by(x) = - and 9 BII, under which (2.I) is an Ornstein-Uhlenber (OU) process converging exponentially, Le. pr ~ Ps == -N(0, I)), and the forward process (2.J) and the backward process (2,2) reduce the following form:
[ Fr. + o² log). ds ov d,d.. (2.3) dæ, 2 Brardt + V Bidur, and dē, = 3,
1
In practice, the score function (xx)) == V log p. (ax)) is often estimated by neural network &4 (a:). where 0 denotes the parameters, and trained via denoising score-matching (Hyvärıen & Dayan, 2005. Vincent I)::):
0 arg min
thy Paeeeee (Vllogp((z)) - $ (a:)) (a:))) dt
(2.4)
log P()o(11(z0) - 3/t ||]] dt,
= arg min
Jo
yby Eyeoorp (m0
as where (=) is the transition distribution from æn to under (2.3)) with an explicit form
N N where μu, Bge $ fo d,de and of = o² (1-c B,
A,dt
(2.5)
and tha is a weighting function for the loss at time 1. After obtaining the NN-based score function of (x.),, the backward process in (2.3) is approximated as:
dy.
2 yo (y.) ds + dw,, with yo ~ qu -
(2.6)
2.2 DISCRETE DIFFUSION MODELS
In discrete diffusion models, one turns to consider continuous-tims Markov chain (#:)oSesT in space X of finite cardinality as the forward process. We denote the probability distribution of æ, by a vector P. E A | where A [x] denotes the probability simplex in R Given the target distribution
Po. the Markov chain satisfies the following master equation:
dp:
= Q.pt. where
Q: = (Qi(y, 2)). E ER X|||
(2.7)
dt
3

---

Published as a conference paper at ICLR 2025
is the rate matrix at time t. The rate matrix Qi satisfies the following two conditions: (i Qr(æ, x) - -e(, Vo E X; (ii) Qr(a, v) 2 0, vr + X.
yf
In the following, will use shorthand notation Q: to denote the matrix Qr with the diagonal elements set to zero. It can be shown that the corresponding backward process is of the same form but with different rate matrix (Kelly, 20LT):
dp. = Q.P. where Q,(,,)) ds
(v) Q. (z. (.)
Vr + E X,
(2.8)
- -E (v(
Vo = y X
The rate matrix Qi is often chosen to possess certain sparse structures such that the forward process converges to a simple distribution that is easy to sample from. Several popular choices include the uniform and absorbing transitions (Lou et all 2024).
The common practice to define the score function (or rather the score vector) as 8 (a) (st (z, y)) (r), network is trained by minimizing the score entropy (Benton al 2022
Pr for any X and estimate it by neural network (z)), where the neural
2024))
0 = arg min
Wy
Σ ッoz
log
(2 (x
14 +
3 (a.w)) (x(
se(sr, (QQ,,,
(2.9)
=
arg min
the
Bx
Σ
pe(uzzo)
log 8. (2, + 57 (I. Qr( (le...)dde. (r(a
Similar the continuous case, the backward process is approximated by the continuous-time Markov chain with the following master equation with qu P and rate matrix Q
dg. = Q.9s, qs, where (1. = s (x. y) (z. v). Va E X. ds and sampling is accomplished by first sampling from the distribution Pae and then evolving the Markov chain accordingly.
(2.10)
2.3 ERROR ANALYSIS OF CONTINUOUS DIFFUSION MODELS
Before we proceed to error analysis of discrete diffusion models, we first review that the error analysis of continuous diffusion models, which is often conducted by considering the following three error terms:
Truncation Error: The error caused by approximating pr by Pee. which is often of the order ((dex)(-T) due to exponential ergodicity;
Approximation Error: The error caused by approximating the score function V log p. (a:) by a neural network & (ax.), which is often assumed to be of order (c)), where is small threshold, given a thorough training process:
Discretization Error: The error caused by numerically solving the SDE (26 with Euler-
Maruyama scheme or other schemes, e.g. exponential integrator (Zhang & Chen, 2022).
The total error is obtained from these three error terms with proper choices of the order of the time horizon T and the design of the numerical scheme. We extract the following theorem from the state-to-the-ar theoretical result (Benton et all, 2023a) for later comparison:
Theorem 2.1 (Error Analysis of Continuous Diffusion Models). Suppose the time discretization scheme ($))e(o with = 0 and s = T - satisfies 3641-5, I x([-sk+1) for k [0 N-1). Assume (pv I, and the score function V log pt (xx,) is estimated by the neural network 8 (xx) with c-accuracy, i.e.
N
|| V Vogg.. (āo..) - 50 (xse
(kk41 - Ex) ~..,
Sc.
k=0 Then under the following choice of the order of parameters
T = (log(ds (de -1),, K = Old
)); N
())
we have DRt. (ps| S where quy is the distribution of the approximate backward process (2.6 implemented with exponential integrator after N steps.
4

---

Published as a conference paper at ICLR 2025
3 STOCHASTIC INTEGRAL FORMULATION OF DISCRETE DIFFUSION MODELS
In this section, we introduce the stochastic integral formulation of discrete diffusion models. The goal is to establish path evolution equation analogous to Itô integral (or equivalently, stochas- tic differential equations) with the master equation (2.7) and (AS) analogous the Fokker-Planck equation in the continuous case.
3.1 POISSON RANDOM MRASURE WITH EVOLVING INTENSITY
In the following, the Poisson distribution with expectation À denoted by P()).
Definition 3.1 (Poisson Random Measure with Evolving Intensity). Let F.P) be probability space and (X, B, v) be a measure space and (g) a non-negative predictable process on R x X Ω satisfying for any T > 0, S fx 1V yl V lul X (v)u(dy)dt s0, a.s., The random measure N [[)] dy) on Et x % is called Poisson random measure with evolving intensity (y()) if
(i) For any B E B and 0 < < t, NNN](((s 8 x B) ~ P (I. JB Ar (w)d(d))r))
(ii) For any t 2 and disjoint sets [BijiemM C B. {NI[A](B,) = N[A]((O, x B.) are independent stochastic processes.
Well-definedness of the Poisson random mea- sure with evolving intensity non-trivial and
refer readers Appendix A for more de- tails and discussions. Intuitively, Poisson ran- dom measures randomly assign jumps to inter- vals along the evolution, with the number of points in each region following Poisson distri- bution, while those with evolving intensity not only assign jumps but also locations controlled by the intensity function (y).. In the follow- ing, we will denote the filtration generated by the Poisson random measure N (dt, dy) by (Fi)120
0.5 -2
Figure Example trajectories of stochastic in- tegrals (I.II w.r.t. Poisson random measure with different evolving intensities. The intensity is cho- sen as \x 50ft if It- = 1 or otherwise O, as shown dashed lines. Intuitively, A con- trols the rate of jumps at time / and location y.
The Poisson random measure defined above ad- mits similar properties as the standard Poisson random measure and the Brownian motion. In particular, one can extend the Itō integral to the Lévy-type stochastic integral w.r.t. Poisson ran- dom measure with evolving intensity for pre- dictable processes, also admits Itô isometry, Itô's formula (Theorem ization theorem (Theorem A.9), for which we refer readers to Appendix for details.
and Lévy's character-
Now we turn the setting of discrete diffusion models, where the state space X is finite endowed with the natural olalgebra B = 2 and the counting measure v = Epex 5y.
Proposition 3.2 (Stochastic Integral Formulation of Discrete Diffusion Models). The forward pro- cess in discrete diffusion models (2.7) can be represented by the following stochastic integral:
(u-
dy), with Xr(y) Q-(,,
(3.1)
and the backward process in discrete diffusion models 2. can be represented by the following stochastic integral:
F. = ( dy), with μ4 (,, (
(3.2)
where X,- denotes the left limit of càdlåg process X, time
The proof of Proposition 5. is provided in Appendix A.4 Figure Willustrates the stochastic integral in (),,),, comparing different intensity functions. is evident that jumps oceur more frequently
5

---

Published as a conference paper at ICLR 2025
in regions where the intensity is higher and less frequently where it is lower. Additionally, the intensity function, which encapsulates key information about the stochastic process, is often much easier and more straightforward analyze compared to the complex trajectories of the process.
We would like to remark that the stochastic integral formulation in Proposition BM2 is tantalizingly close to the Itō integral in continuous diffusion models in the form of stochastic differential equations (ef. (2.3)) and () ). Recalling that in the continuous case, Girsanov's 's theorem is applied to SDEs for deriving the score-matching loss (ME)) and also for the error analysis by associating the loss with the KL divergence, one may wonder if similar techniques can be applied to discrete diffusion models. The following section gives an affirmative answer this question by providing change of measure for Poisson random measures with evolving intensity, which is the theoretical foundation of our stochastic integral-basee -ased error analysis framework for discrete diffusion models.
3.2 CHANGE OF MEASURE
The following theorem provides a change-of ofange-of-nne saaee-offmaassee measure argument for stochastic integrals w.r.t. Pois- son random measures with evolving intensity, analogous to Girsanov's 's theorem for Itô integrals w.r.. Brownian motions.
Theorem 3.3 (Change of Measure for Poisson Random Measure with Evolving Density). Let N [[d dy) be a Poisson random measure with evolving intensity )e()) in the probability space (2,,,11) P), and hely) be a positive predictable process on IR x Q. Suppose the following exponential process is local Fe-martingale:
2 = exp (1o²) log h (N) x dgy S: (hh,(w) - 1) (
[
(W)((d))dr)
(3.3)
and Q is another probability measure on FF) such that Q < P with Radon-Nikodyy derivative dQ/ 1Q//Pl/, = Zg(h). Then the Poisson random measure N (d) dy) under the measure Q is a Poisson random measure with evolving intensity >x (e)
Intuitively, Theorem 3R depicts the relations between the Gandom-Nikodyne derivative (Z,(h) of the probability measures on which two Poisson random measures with different intensities are de- fined. [h[ also roughly translates to the likelihood ratio between two paths generated with different intensities, with which one could work on stronger convergence results, e.g. KL. divergence.
straightforward to derive the following corollary, which was derived in (Benton et all, 2022)
with a different technique with Feller processes and adopted in (Lou et all 2024 Chen & Ying.
2022)) in the design of loss functions for the neural network training:
Corollary 3.4 (Equivalence between KL Divergence and Score Entropy-based Loss Function). Let Po.r and qo:T be the path measures of the backward process (2 and the approximate backward
process (0. then it holds that (Frl(1)))) S DEL (Puer (lgo:)
[
(3.4)
-DKl(5oll90) + E
3, (ū, (F)(((..))
(d)ddd
where K(x)= x 1 - log x 2 O, and the expectation is taken w.r.t. paths generated by the back- ward process (1.2). Consequently, minimizing the loss function for discrete diffusion models is equivalent to minimizing the KL divergence between the path measures of the ground truth and the approximate backward process.
Proofs of the change of measure- related arguments above will be provided in Appendix A One should recall that in the continuous case with Itô integrals, the proximity of two paths in KL diver- gence only requires small difference between the drift terms by Girsanov's 's theorem, and thus the score function can be trained with the mean squared error loss (2 (Song all 2020), while in the discrete case, the proximity of two paths requires the likelihood ratio to be close to one, accounting for more complicated score entropy design (2.9) (Benton et all 2022; Lou et al. 2024)
ERROR ANALYSIS OF DISCRETE DIFFUSION MODELS
In this section, we firstly review two different implementations of the discrete diffusion models, namely 7-leaping (Gillespie, (X0I) and uniformization (Van Dijk, 1992), derive their stochastic integral formulations in Proposition 8.2, and provide our main results for their error analysis.

---

Published as a conference paper at ICLR 2025
4.1 ALGORITHMS
4.1.1 T-LEAPING.
A straightforward algorithm for simulating the backward process is to discretize the integral in (6.2) with an Euler-Man Mally-mma scheme. This leads the r-leaping algorithm summarized in Algorithm II The main idea is to employ predetermined time discretization scheme and approximate the infer- ence process within each interval using the intensity observed at the time and location corresponding to the start of the interval.
Algorithm 1: 7- L-apping Algorithm for Discrete Diffusion Model Inference
Input: 3o ~ yo. time discretization scheme (si)sejo:N] with so = 0 and &N = 8, intensity function g. defined in Proposition A.1. and neural network-basee score function
estimation S7-
Output: A sample Vax ~ Tyy for n 0 to N do
Tant1 + Us.. + EyEX(U (U Bs.,)((Te) (v)(5a+1 - 8n))):
(4.1)
3 end
As shown in the following proposition, r-leaping can be formulated as a stochastic integral. Proposition 4.1 (Stochastic Integral Formulation of r-Leaping)- The r-leaping algorithm (Algo- rithm M1) is equivalent to solving the following stochastic integral equation:
U. To + '." J(( 1lu-0.a
D. - [ [(dr(ddddy)))
(4.2)
where the evolving intensity T. (v) is given by [[r]()) (v) 8 50 (01-J- [ 12 (v).
in which we used the symbol [T] Sn. for [Sn; 1n+1). We will call the process Us the interpo- lating process of the r-leaping algoritium and denote the distribution of D. by qs.
In general, the stochastic integral associated with r-leaping (H.2) is computed using a piecewise constant intensity rather than the original continuous intensity. This approximation introduces dis- cretization eтror as trade-off for more efficient implementation. We refer to Remark A.13 for further justification of the --eeapigg algorithm.
4.1.2 UNIFORMIZATION
Another algorithm considered for simulating the backward process in discrete diffusion models is uniformization. The algorithm is summarized in Algorithm in which (m) denotes the m-th order statistic of the M uniform random variables on [0, 1], and the randomness in (H.)) should be understood as sampling a categorical distribution and updating the state accordingly.
Algorithm 2: Uniformization Algorithm for Discrete Diffusion Model Inference
Input: Jo go. time discretization scheme (s.)bE)o,N] with so and 8 T 6, intensity upper bound process X., intensity function Nº defined in Proposition H.I. and neural Hetwork-basedd score function estimation S.-
Output: A sample Ian qtn-
for b = to B 1 do
M ~ P ( (ab+1 - sb)). om ~ Unif([O, 1]) for m E [M];
for m = 1 to M do
with prob. +o (z)/Tomm for y E X, with prob. - Evex Po tn (2) R
y.
(4.3)
Vea.
end
end
The main idea is to simulate the backward process by a Poisson random measure with a piecewise constant intensity upper bound process and then sample the behavior of each jump according the

---

Published as a conference paper at ICLR 2025
intensity (v) at time s. The uniformization algorithm also admits stochastic integral formulation, as shown in the following proposition.
Proposition 4.2 (Stochastic Integral Formulation of Uniformization), Under the block discretization scheme ($))bE(0,B) with so O and sB = T 6, and for any 8 E (Sb, 8b+11, we define the piecewise constant intensity upper bound process by X = suPse(s,.oo-1 Sx (U) Then the uniformization algorithm (Algorithm D) is equivalent to solving the following stochastic integral equation in the augmented measure space (X x AI. 1 & B(O0, A)). v @ m):
Us yo + L J
| (y (y- V.- (+--))oses Josssssssss A2 (a)u)dy) N p (dr, dy..d))
(4.4)
where the evolving intensity 7. (v) is given by (v) = (0- v (0+ .y)
Based on Proposition 1.2. can show that the uniformization algorithm simulates the backward process in discrete diffusion models accurately (ef. Theorem A.I.) and the proofs of the claims above will be provided in Appendix A4
4.2 ASSUMPTIONS
We need the following assumptions to ensure the well-definedness of discrete diffusion models. For simplicity, we assume the rate matrix Q, is homogeneouu and symmetric. i.e. Q: = Q for any 2 0. In fact, the results can be easily extended to the mmmm-inhomogenouu case of the family Q 3.Q with rescaling factor Br, and asymmetric cases will be left for future works.
Assumption 4.3 (Regularity of the Rate Matrix). The rate matrix Q satisfies:
(i) For any æ. y X, Q(x, C and D -Q(x, x) D) for some constants D,
(ii) The modified log-Sobolev constant p(Q) of the rate matrix Q (cf. Definition B.G is lower bounded by p O.
Statement (i) assumes the regularity of the rate matrix, which is often trivially satisfied in many applications, while Statement (ii) ensures the exponential convergence of the forward process in discrete diffusion models. In general, p(Q) may depend on the connectivity and other structures of the corresponding graph G (Q) (ef. Definition B.I.). Such lower bound has been obtained for specific graphs (e.g. Example I. and DD. and general results are in active research (Salofi-Coste 1997 Babkov & Tetali 2006). We refer readers to Appendix [B] for further discussions on the literature of the modified log- log-Sobolev constant, as well as its relation to the spectral gap, the mixing time, etc..
Assumption 4.4 (Bounded Score). The true score function satisfies St s1 v) S 11v t-,, while the learned score function satisfies (x. v) E (0, M), for any x, E X.
The first part the asymptotic behavior of the true score corresponds to the estimation [[[[| ||=] E|||x; - |13 //2//?]] ~ V 1 in the continuous case (Chen et all 20RKE, Assumption 1) and further justification provided in Remark B.3. The bound the estimated score can be easily satisfied by adding truncation in post-processing in the implementation of the NN-based score estimator.
Assumption 4.5 (Continuity of Score Function). For any t 0 and y X such that QIr ,9) > 0,
Met (v) (z ((().)) - < 1 ivt f for some exponent 7 E [0. 1].
we have
(v()) px [x() .9)
Assumption corresponds the Lipschitz continuity of the score function (cf. (Chen all 2I2a
Assumption 1). (Chen 202E, Assumption 3)) for continuous diffusion models, and is in light of the postulation that adjacent vertices should have close score function and intensity values. In
the worse case, assume Q( y) ((), then naive bound would be (x)
< [s(( x,-) S
(x(
1 v with 7 1. However, when the initial distribution is both upper and lower bounded, y may be as small as 0, and we plan to investigate how this (local) continuity of the score function affects the overall performance of discrete diffusion models.
Assumption 4.6 (e-accurate Score Estimation). The score function sı (z:) is estimated by the neural network 8 (x.) with e-accuracy, i.c.
N
Σ (snt1 s,,
{ K
Fan (3--0)
(T (..,(F... ()((v) ())((()))))))))))))))))))) Sc.
Ban (5
8

---

Published as a conference paper at ICLR 2025
This assumption assumes the expressive power and sufficient training of the NN-based score esti- mator and is standard in diffusion model-related theories (Chen et all 2022 2023;; Benton et all, 2023::
Chen et all 2024c).
4.3
ERROR ANALYSIS
Our main results are presented below for each algorithm introduced in Section !
4.3.1 T-LEAPING
Theorem 4.7 (Error Analysis of r-Leaping). Suppose the time discretization scheme (81))E(0.N)
with 8o =0 0 and 8x =T - satisfies for k E [0: N 1}, Sk+1 Sk S (1 (T (++1)1+7-9)
where the exponent y satisfies y < S 1 T when 7, < 1, and 1j 1 when 7 1. With Assumptions B.3.
and B.G place, we have the following error bound with probability
1 ((e)
log X + +c+DDDK and under the following choice of the order of parameters:
(RI.Ps (n) S
log(e
1 log 121) )
7 1, 1 vT),
[0,
T ==
O
(4.5)
''loe log log(x))
7=1 1,
we have DKL (PollTr-)))) S with N = =K= D2pp² log" (e (0000o0"(e" log xI) total steps.
The conclusions and detailed proof (as provided in Appendix Q whose sketch is given in Ap- pendix Cal, are analogous to the error bound for continuous diffusion models (cf. Theorem ID as a summation of the truncation, approximation, and discretization errors as outlined in Section P We would like to point out the main differences between continuous and discrete diffusion models:
Maaeeinn-Uheebeckk process converges exponentially fast in the continuous diffusion models, the exponential convergence of the forward process in discrete dif- fusion models is non-trivial for general graphs (Q)), for which the lower bound on the modified log-Sobolev constant is one of the sufficient conditions. In practice, the exponential convergence of the forward process should be verified for the specific problem at hand;
Truncation Error: While the
Discretization Error: In continuous diffusion models, the analysis of the discretization error is based on the Itō integral and Girsanov's theorem, while for discrete diffusion models, the stochas- tic integral framework, including the Poisson random measure with evolving intensity (cf. Defini- tion I. and change of measure (cf. Theorem B.3) that developed above, is employed instead.
Remark 4.8 (Remark on Early Stopping). As in Assumption H.A. the true score function may exhibit singular behavior as s + T, due to possible vacancy in the target distribution Pv- To handle this singularity, two different regimes are considered for the time discretization scheme depending on the continuity parameter of the score function (Assumption H.5)). The main intuition is that (a) in the worse case 7 1, early stopping time T 8 is necessary; (b) if the larget distribution po is such well-posed (e.g. both upper and lower bounded) and the rate matrix Q is constructed in way that the score exhibits certain (local) continuity reflected by & one may choose an appropriate shrinkage 1,, with which fiite discretization error can be achieved with finite steps.
In Theorem T. the coefficient roughly translates to the dimension d when the discrete diffusion model is applied to X [S] where S is the number of states along each dimension. For example, when each state connected to those at a Manhattan distance of 1 with unit weight, we have = 1, D 2d, log X d log S hold in Assumption P.l. Plugging D log X O(d) into the results, we obtain that the total number of steps = (dd), where Õ denotes the order up to logarithmic factors. This recovers the dependency described in (Campbell et all, 2022, Theorem 1) for r-leaping with a completely different set of techniques, and importantly, our results do not rely on strong assumptions such as uniform bound on the true score. We also reduce assumption stringency by relating our assumption on the estimation error (Assumption L more closely to the practical training loss rather than requiring an - score estimation error. Most notably, we provide the first convergence guarantees for r-leaping in KL divergence, which is stronger than the total variation distance, for discrete diffusion models.

---

Published as a conference paper at ICLR 2025
4.3.2 UNIFORMIZATION
The error analysis the uniformization algorithm requires the following modified assumption on the accuracy of the learned score function 5% (zz):
Assumption 4.6" (e-accurate Learned Score). The score function st(xe) is estimated by the neural network &y (z1) with e-accuracy, i.e.
E
K
sc.
Theorem 4.9 (Error Analysis of Uniformization). Suppose the block discretization scheme (8))) with so and sN R s(1 (T sk+1)) Under Assumptions E.3. R. and H.1 we have the following error bound
satisfies for k [0 N 1]. sk+1 8% S
(RL(pol(ur-6) S exp(-pl pT) log + +c.
Then with O log(c - log (x1)
and the early stopping scheme (e (Te-"), we have
(KI(pollAT-D S with B[N] O log(( log (x))
steps.
The proof of Theorem is deferred to Appendix Q where corresponding sketch provided in Appendix CT Following similar argument for Theorem ! the dimensionality dependency of the uniformization scheme is (d), confirming the result for the special case {0, 1)d in (Chen & Ying. 20224) and X = [$] in (Zhang et all 2024).. Theorem y and 4 offer direct comparison of the efficiency of the r-leaping and uniformization implementations for discrete diffusion mod- els. Our proof reveals that the less favorable quadratic dependency in the r-leaping scheme arises from the truncation error, which is not present the uniformization scheme, illustrating a possible advantage of the latter in reducing computational complexity.
Recalling the current state-of-the- art result for continuous diffusion models (Theorem 1. is Ö(d),
conjecture that (d) is also the optimal rate in the discrete case. In the continuous case, the lincar dependency does not depend on the accurate simulation of the approximate backward process (2.10) (or (B.22) and is achievable with Euler- Maruyama schemes. The proof was via an intricate stochas- tic localization argument (Benton et all 2023a), with which the bound on E[[[" log (= is improved by ((d)-facto from (dd). The corresponding argument for the r-leaping scheme of discrete diffusion models would be possible refinement Proposition en which we believe is of independent interest and will be explored future work.
5 CONCLUSION
In this paper, we have developed a comprehensive framework for the error analysis of discrete dif- fusion models. We rigorously introduced the Poisson random measure with evolving intensity and established the Lévy-type stochastic integral alongside change of measure arguments. These ad- vancements not only hold mathematical significance but also facilitate clear-cut analysis of dis- crete diffusion models. Moreover, we demonstrated that the inference process can be formulated stochastic integral using the Poisson random measure with evolving intensity, allowing the er- ror to be systematically decomposed and optimized by algorithmic design, mirroring the theoretical framework for continuous diffusion models. Our framework unifies the error analysis of discrete diffusion models and provides the first error bounds for the r-leaping scheme in KI. divergence.
Our results lay theoretical groundwork for the design and analysis of discrete diffusion models, adaptable to broader contexts, such time-inhomogeneous and non-symmetric rate matrices. Fu- ture research directions include exploring the continuum limit of discrete diffusion models in state spaces and time (Winkler et all 2024) Zhao et all (024) and how accelerate the implementation via parallel sampling (Chung et all 2023 Shih et all 20222, Tang et all 2024; Cao et all 2024 Selvam et all p024;; Chen et all 20244: Gupta all, (022). We hope work will inspire further research on both the theoretical analysis and practical applications of discrete diffusion models in various fields.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Lexing Ying acknowledges the support of the National Science Foundation under Award No. DMS- 2208163.
REFERENCES
Amira Alakhdar, Barnabas Poczos, and Newell Washburn. Diffusion models in de novo drug design. Journal of Chemical Information and Modeling, 2024.
Sarah Alamdari, Nitya Thakkar, Rianne den Berg, Alex Lu, Nicolo Fusi, Ava P Amini, and Kevin K Yang. Protein generation with evolutionary diffusion: sequence is all you need. BioRxiv, pp. 2023-09 0223-09.22 2023.
Michael S Albergo and Eric Vanden-Eijnden. Building normalizing flows with stochastic inter- polants. arXiv preprini vrXiv:2209.1557/, 2022.
Michael Albergo, Nicholas M Boffi, and Eric Vanden-Eijnden. Stochastic interpolants: A unifying framework for flows and diffusions. arXiv preprini urXiv:2303.08797, 2023.
David F Anderson, Arnab Ganguly, and Thomas G Kurtz. Error analysis of tau-leap simulation methods. The Annals of Applied Probubility, 21(6):222-2222,, 2011.
David Applebaum. Lévy processes and stochastic calculus. Cambridge university press, 2009.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing 2021.
Systems, 34:1
Pavel Avdeyev, Chenlai Shi, Yuhao Tan, Kseniia Dudnyk, and Jian Zhou. Dirichlet diffusion score model for biological sequence generation. In International Conference Machine Learning, pp- 1276-1301. PMLR, 2023.
Joe Benton, Yuyang Shi, Valentin De Bortoli, George Deligiannidis, and Amnad Doucet. From denoising diffusions to denoising markov models. arXiv preprint (tfi:22110035990 2022.
Joe Benton, Valentin De Bortoli, Amnad Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. arXiv preprint wrXiv:2308.03668 2023a.
Joe Benton, George Deligiannidis, and Amaud Doucet. Error bounds for flow matching methods. arXiv preprint 2.X.x::305..686/ 2023b.
Joe Benton, Yuyang Shi, Valentin De Bortoli, George Deligiannidis, and Arnau Doucet. From denoising diffusions to denoising markov models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(2):86-301, 2024.
Adam Block, Youssef Mrouch, and Alexander Rakhlin. Generative modeling with denoising auto- encoders and langevin sampling. arXiv preprini urXiv:2002.00107, 2020.
Sergey G Bobkov and Michel Ledoux. On modified logarithmic sobolev inequalities for bernoulli and poisson measures. Journal of functional analysis, 156(2):347-365, 1998.
Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings. Journal of Theoretical Probability, 99:289-3366 2006.
Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 55:28266-28279, 2022.
Andrew Campbell, Jason Yim, Regina Barzilay, Tom Rainforth, and Tommi Jaakkola. Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design. arXiv preprint 2rXiv:2402.049977 2024.
11

---

Published as a conference paper at ICLR 2025
Jiezhang Cao, Yue Shi, Kai Zhang, Yulun Zhang, Radu Timofte, and Luc Van Gool. Deep equilib- rium diffusion restoration with parallel sampling. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 2824-2823322 2024.
Luke Causer, Grant M Rotskoff, and Juan P Garrahan. Discrete generative diffusion models without stochastic differential equations: a tensor network approach. arXiv preprint arXiv:2407.11133,
2024.
Stanley H Chan. Tutorial diffusion models for imaging and vision. arXiv:2403. 18103, 2024.
arXiv preprint
Haoxuan Chen, Yinuo Ren, Lexing Ying, and Grant Rotskoff. Accelerating diffusion models with parallel sampling: Inference sub-linear time complexity. arXiv preprint arXiv:2405 2024a.
Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffusion model: Exact imple- mentation through uniformization. arXiv preprint arXiv:2402.08095, 2024.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendll bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pp. 4735-4763, PMLR, 2023a.
Minshuo Chen, Song Mei, Jianqing Fan, and Mengdi Wang- An overview of diffusion models: Ap- plications, guided generation, statistical rates and optimization. arXiv preprint arXiv:2404.0777,, 2024b.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint 1rXiv:2209.11215: 2022.
Sitan Chen, Giannis Daras, and Alex Dimakis. Restorationnddggraaaiinn beyond linear diffusions: A non-asymptotic analysis for ddim-type samplers. In International Conference on Machine Learning. pp. 4462-4484. PMLR, 2023b.
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast. Advances in Neural Information Processing Systems, 36, 2024c.
Seunggeun Chi, Hyung-gun Chi, Hengbo Ma, Nakul Agarwal, Faizan Siddiqui, Karthik Ramani, and Kwonjoon Lee. M2d2m: Multi-motion generation from text with discrete diffusion models. arXiv preprint arXiv:2407. 14502, 2024.
Hyungjin Chung, Jeongsol Kim, Sehui Kim, and Jong Chul Ye. Parallel diffusion models of operator and image for blind inverse problems. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6059-6069, 2023.
David R Cox. Some statistical methods connected with series of events. Journal of the Royal Statistical Society: Series (Methodological), 1722):129-157, 1955.
Do Huu Dat, Do Duc Anh, Anh Tuan Luu, and Wray Buntine. Discrete diffusion language model for long text summarization. arXiv preprint arXiv:2407.10999, 2024.
Oscar Davis, Samuel Kessler, Mircea Petrache, Avishek Joey Bose, et al. Fisher flow matching for generative modeling over discrete data. arXiv preprint arXiv:2405. 2024.
Persi Diaconis and Laurent Saloff-Coste, Logarithmic sobolev inequalities for finite markov chains.
The Annals of Applied Probability, 6(3):695-750, 1996.
Andreas Eberle. Markov processes. Lecture Notes at University of Bonn, 2009.
Andreas Eberle. Stochastic analysis.
http:// wwwp//wwwww.. mi. Ltn.kooll.dd//tochanae pdd, 2015.
wSl 611 617/EBa wwwereeeettcaaaeeeeeeeee
cAna 1 cána
Patrick Emami, Aidan Perreault, Jeffrey Law, David Biagioni, and Peter St John. Plug & play directed evolution of proteins with gradient- based discrete meme. Machine Learning: Science and Technology, 4(2):025014, 2023.
12

---

Published as a conference paper at ICLR 2025
Jiahao Fan, Ziyao Li, Eric Alcaide, Guolin Ke, Huaqing Huang, and E Weinan. Accurate conforma- tion sampling via protein structural diffusion. bioRxiv, pp. 2024 0224-05,22 2024.
Griffin Floto, Thorsteinn Jonsson, Mihai Nica, Scott Sanner, and Eric Zhengyu Zhu. Diffusion on the probability simplex. arXiv preprini arXiv:2309.02555 025300 2023.
Nathan C Frey, Daniel Berenberg, Karina Zadorozhny, Joseph Kleinhenz, Julien Lafrance- Isidro Hotzel, Yan Wu, Stephen Ra, Richard Bonneau, Kyunghyun Cho, al. Protein discovery with discrete walk-jump sampling. arXiv preprint arXiv:2306.123360 2023.
Xuefeng Gao and Lingjiong Zhu. Convergence analysis for general probability flow odes of diffu- sion models in wasserstein distances. arXiv preprint arXiv:2401.17953. 2024.
Daniel T Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of chemical physics, 111(4):176--1333, 2001.
Paul Glasserman and Nicolas Merener. Convergence of a discretization scheme for jump-diffusion processes with state-dependent intensities. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 460(2041):111-227) 2004.
Sharad Goel. Modified logarithmic sobolev inequalities for some models of random walk. Stochastic processes and their applications, 1 114(1):51-77 2004.
Shansan Gong, Mukai Li, Jiangtao Feng. Zhiyong Wu, and Lingpeng Kong. Diffuseq-v2: Bridging discrete and continuous text spaces for accelerated seq2seq diffusion models. arXiv preprint arXiv:2310.05793, 2023.
Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4):1061- 1083, 1975.
Nate Gruver, Samuel Stanton, Nathan Frey, Tim GJ Rudner, Isidro Hotzel, Julien Lafrance- Arvind Rajpal, Kyunghyun Cho, and Andrew G Wilson. Protein design with guided discrete diffusion, Advances neural information processing systems, 36, 2024.
Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to- image synthesis. In Proceedings of the JEEF/CVF conference on Computer Vision and Pattern Recognition, pp. 10696-10706, 2022.
Zhiye Guo, Jian Liu, Yanli Wang, Mengrui Chen, Duolin Wang, Dong Xu, and Jianlin Cheng. Diffusion models in bioinformaties and computational biology. Nature reviews bioengineering. (2):136-154, 2024.
Shivam Gupta, Linda Cai, and Sitan Chen. Faster diffusion-baasd sampling with randomized mid- points: Sequential and parallel. arXiv preprint arXiv:2406.009) 2024.
Zhengfu He, Tianxiang Sun, Kuanning Wang, Xuanjing Huang. and Xipeng Qiu. Diffusion- bert: Improving generative masked language models with diffusion models. arXiv preprint arXiv:2211.15022 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-663 0851, 2020.
Emiel Hoogeboom, Alexey Gritsenko, Jasmijn Bastings. Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. arXiv preprint arXiv:2110.02037, 2021a.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows
and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454-12465, 2021b.
Minghui Hu, Yujie Wang, Tat-Jen Cham, Jianfei Yang. and Ponnuthurai N Suganthan. Global context with discrete diffusion in vector quantised modelling for image generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1 11502-11511, 2022.
13

---

Published as a conference paper at ICLR 2025
Daniel Zhengyu Huang, Jiaoyang Huang, and Zhengjiang Lin. Convergence analysis of probability flow ode for score-based generative models. arXiv preprint arXivv2404.09730, 2024.
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score match-
ing. Journal of Machine Learning Research, 6(4), 2005.
Ilia Igashov, Amee Schneuing, Marwin Segler, Michael Bronstein, and Bruno Correia. Retrobridge: Modeling retrosynthesis with markov bridges. arXiv preprint arXiv:2308. /62/2, 2023.
Naoto Inoue, Kotaro Kikuchi, Edgar Simo-Serra, Mayu Otani, and Kota Yamaguchi. Layoutdm: Discrete diffusion model for controllable layout generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10167-10176, 2023.
Jean Jacod and Albert Shiryaev. Limit theorems for stochastic processes, volume 288. Springer Science & Business Media, 2013.
Frank P Kelly, Reversibility and stochastic networks. Cambridge University Press, 2011.
Thomas J Kerby and Kevin R Moon. Training-frre guidance for discrete diffusion models for molec- ular generation. arXiv preprint arXiv:2409.073: 07359, 2024.
Steven P Lalley. Continuous time markov chains. Lecture Notes, University of Chicago, pp. 34, 2012.
Günter Last and Mathew Penrose. Lectures on the Poisson process, volume 7. Cambridge University Press, 2017.
Michel Ledoux. Concentration of measure and logarithmic sobolev inequalities. In Seminaire de probabilites XXXIII, pp. 120-216. Springer, 2006.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 35:22870-22882, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pp- 946-985. PMLR, 2023.
Tzong-Yor Yow Lee and Horng- Tzer Yau. Logarithmic sobolev inequality for some models of random walks. The Annals of Probability, 26(4): 1998.
Jose Lezama, Tim Salimans, Lu Jiang, Huiwen Chang, Jonathan Ho, and Irfan Essa. Discrete predietor-corrector diffusion models for image synthesis. In The Eleventh International Confer- ence on Learning Representationss 2022.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non-asymptotic convergence for diffusion-based generative models. arXiv preprint arXiv:2306.09251, 2023.
Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejie Chi, and Yuxin Chen. Accelerating conver- gence of basre-based diffusion models, provably. arXiv preprint arXiv:2403.03852. 2024a.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards non-asymptotic convergence for diffusion-based generative models. In The Twelfth International Conference on Learning Rep- resentations, 2024b.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. sharp convergence theory for the probability flow odes of diffusion models. arXiv preprint arXiv:2408.02320. 2024c.
Tiejun Li. Analysis of explicit tau-leaping schemes for simulating chemically reacting systems. Multiscale Modeling Simulation, 6(2):417-436, 2007.
Xiner Li, Yulai Zhao, Chenyu Wang, Gabriele Scalia, Gokcen Eraslan, Surag Nair, Tommaso Bian- calani, Aviv Regev, Sergey Levine, and Masatoshi Uchara. Derivative-fre free guidance in continuous and discrete diffusion models with soft value-base based decoding. arXiv preprint arXiv:2408 2r8.0:2408.08252, 2024d.
14

---

Published as a conference paper at ICLR 2025
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024c.
Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Non-asymptotic convergence of discrete-time diffusion models: New approach and improved rate. arXiv:2402.13901 2024.
arXiv preprint
Yaron Lipman, Ricky TQ Chen, Heli for generative modeling. arXiv preprint arXiv:2210.02747, 2022.
Maximilian Nickel, and Matt Le. Flow matching
Xingchao Liu, Chengyue Gong, and Qiang Liu. Flow straight and fast: Learning generate and transfer data with rectified flow. arXiv preprint arXiv:2209.0300 2022.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Forty-first International Conference on Machine Learning, 2024.
Yunhong Lou, Linchao Zhu, Yaxiong Wang, Xiaohan Wang, and Yi Yang. Diversemotion: Towards diverse human motion generation via discrete diffusion. arXiv preprint arXiv:2309.01332. 2023.
Sokhna Diarra Mbacke and Omar Rivasplata. A note on the convergence of denoising diffusion probabilisticc models. arXiv preprint arXiv:2312.05989 2023.
Chenlin Meng, Kristy Choi, Jiaming Song, and Stefano Ermon. Concrete score matching: General- ized score matching for discrete data. Advances in Neural Information Processing Systems, 35: 34532-34545, 2022.
Hunter Nisonoff, Junhao Xiong. Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete state-space diffusion and flow models. arXiv preprint arXiv:2406.01572, 2024.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. In International Con- ference on Artificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020.
Bernt Øksendal. Stochastic differential equations. Springer, 2003.
Francesco Pedrotti, Jan Maas, and Marco Mondelli. Improved convergence of score-based diffusion models via prediction-correctoon arXiv preprint arXhv:2305.14164, 2023.
Philip Protter. Point process differentials with evolving intensities. In Nonlinear stochastic problems, pp. 467-472. Springer, 1983.
Yiming Qin, Clement Vignac, and Pascal Frossard. Sparse training of discrete diffusion models for graph generation. arXiv preprint arXiv:231 1.02142, 2023.
Yinuo Ren, Haoxuan Chen, Yuchen Zhu, Wei Guo, Yongxin Chen, Grant M Rotskoff, Molei Tao, and Lexing Ying. Fast solvers for discrete diffusion models: Theory and applications of high- order algorithms. arXiv preprint arXiv:2502.0023: 2025a.
Yinuo Ren, Grant M Rotskoff, and Lexing Ying. unified approach to analysis and design of denoising markov models. arXiv preprint arXiv:2504.011 2025b.
Pierre H Richemond, Sander Dieleman, and Arnaud Doucet. Categorical sdes with simplex diffu- sion. arXiv preprint 10..::220..1488.. 2022.
Eric A Riesel, Tsach Mackey, Hamed Nilforoshan, Minkai Xu, Catherine K Badding, Alison Altman, Jure Leskovec, and Danna E Freedman. Crystal structure determination from powder diffraction patterns with generative machine learning. Journal of the American Chemical Society, 2024.
Severi Rissanen, Markus Heinonen, and Arno Solin. Improving discrete diffusion models via struc- tured preferential generation. arXiv preprint arXiv:2405. /7889, 2024.
15

---

Published as a conference paper at ICLR 2025
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. arXiv preprint arXiv:2406.07524, 2024.
Laurent Saloff-Coste. Lectures on finite markov chains. lectures probability theory and statistics (saint-flour, 1996). 301 301-413. Lecture Notes in Math, 1665, 1997.
Javier E Santos, Zachary R Fox, Nicholas Lubbers, and Yen Ting Lin. Blackout diffusion: generative diffusion models discrete-state spaces, In International Conference on Machine Learning, pp. 9034-9059. PMLR, 2023.
Ari Seff, Wenda Zhou, Farhan Damani, Abigail Doyle, and Ryan P Adams. Discrete object gener- ation with reversible inductive construction. Advances in neural information processing systems, 32, 2019.
Nikil Roashan Selvam, Amil Merchant, and Stefano Ermon. Self-refining diffusion samplers: En- abling parallelization via parareal iterations. arXiv preprint arXiv:2412.08292 2024.
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. arXiv preprint McXiv:2001.09382 2020.
Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis K Titsias. Simplified and gener- alized masked diffusion for discrete data. arXiv preprint arXiv:2406.0432, 2024.
Andy Shih, Suneel Belkhale, Stefano Ermon, Dorsa Sadigh, and Nima Anari. Parallel sampling of diffusion models. Advances Neural Information Processing Systems, 36, 2024.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learn- ing, pp. 2256-2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song. Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13455 2020.
Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon. Maximum likelihood training of score-based diffusion models. Advances neural information processing systems, 34:1415- 1428, 2021.
Hannes Stark, Bowen Jing. Chenyu Wang, Gabriele Corso, Bonnie Berger, Regina Barzilay, and Tommi Jaakkola. Dirichlet flow matching with applications to dna sequence design. arXiv preprint arXiv:2402.0584/1 2024.
Daniel W Stroock. Logarithmic sobolev inequalities for gibbs states. In Dirichlet forms. 1993.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous-timg discrete diffusion models. arXiv preprint arXiv:2211.1677 2022.
Zhiwei Tang, Jiasheng Tang, Hao Luo, Fan Wang, and Tsung-Hui Chang. Accelerating parallel sampling of diffusion models. In Forty-first International Conference on Machine Learning, 2024.
Belinda Tzen and Maxim Raginsky. Theoretical guarantees for sampling and inference in generative models with latent diffusions. In Conference Learning Theory, pp. 3084-3114, PMLR, 2019.
Nico M Van Dijk. Uniformization for nonhomogeneous markov chains. Operations research letters, 12(5):283-291 1992.
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
16

---

Published as a conference paper at ICLR 2025
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural compu- tation, 23(7):1661-1674, 2011.
Lingxiao Wang, Gert Aarts, and Kai Zhou. Generative diffusion models for lattice field theory. arXiv preprint arXiv:231..03578 2023.
Joseph L Watson, David Juergens, Nathaniel R Bennett, Brian L Trippe, Jason Yim, Helen E Eise- nach, Woody Ahern, Andrew J Borst, Robert J Ragotte, Lukas F Milles, et al. De novo design of 2023.
protein structure and function with rfdiffusion. Nature, 620(7976):1089-111
Ludwig Winkler, Lorenz Richter, and Manfred Opper. Bridging discrete and continuous state spaces: Exploring the chrenfest process in time-continuous diffusion models. arXiv preprint (rXiv:2405.03549 2024.
Tong Wu, Zhihao Fan, Xiao Liu, Hai-Tao Zheng, Yeyun Gong, Jian Jiao, Juntao Li, Jian Guo, Nan Duan, Weizhu Chen, al. Ar-diffusion: Auto-regressive diffusion model for text generation. Advances in Neural Information Processing Systems, 36:39957-39974 2023.
Zhichao Wu, Qiulin Li, Sixing Liu, and Qun Yang. Detts: Discrete diffusion model with contrastive learning for text-to-speech generation. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 11336-11340 IEEE, 2024.
Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geo- metric diffusion model for molecular conformation generation. arXiv preprint urXiv:2033002223, 2022.
Donghha Yang, Jianwei Yu, Helin Wang, Wen Wang, Chao Weng, Yuexian Zou, and Dong Yu. Diffsound: Discrete diffusion model for text-to-sound generation. JEEE/ACM Transactions Audio, Speech, and Language Processing, 31:1720-1733, 2023a.
John Yang, Jason Yim, Regina Barzilay, and Tommi Jaakkola. Fast non-autoregressive inverse folding with discrete diffusion. arXiv preprint arXiv:2312.02447,, 2023b.
Ling Yang, Zhilong Zhang, Yang Song. Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. ACM Computing Surveys, 36(4):1-39, 2023c.
Kai Yi. Bingxin Zhou, Yiqing Shen, Pietro Liò, and Yuguang Wang. Graph denoising diffusion for inverse protein folding. Advances in Neural Information Processing Systems, 36, 2024.
Junyi Zhang, Jiaqi Guo, Shizhao Sun, Jian Maa-Guang Lou, and Dongmei Zhang. Layoutdiffusion: Improving graphic layout generation by discrete diffusion probabilistic models. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pp. 7226-7236, 2023.
Linfeng Zhang, Weinan E, and Lei Wang. Monge-ampère flow for generative modeling. arXiv preprint arXiv:1809 10188
10188, 2018
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. arXiv preprint arXiv:2204. 00044.3990 33002, 2022.
Zikun Zhang, Zixiang Chen, and Quanquan Gu. Convergence of score-based discrete diffusion
models: A discrete-time analysis. arXiv preprint 1rXiv:2410.02322,, 2024.
Lingxiao Zhao, Xueying Ding, Lijun Yu, and Leman Akoglu. Improving and unifying diiscetee&coottnuuus-tttt discrete denoising diffusion. arXiv preprint arXiv=2402.03771, 2024.
Lin Zheng, Jianbo Yuan, Lei Yu. and Lingpeng Kong. A reparameterized discrete diffusion model for text generation. arXiv preprint arXiv:2302.05
2023.
Kun Zhou, Yifan Li, Wayne Xin Zhao, and Ji-Rong Wen. Diffusion-nat: Self- prompiro discrete diffusion for non-autoregressivve text generation. arXiv preprint arXiv:2305.0400 2023.
Ye Zhu, Yu Wu, Kyle Olszewski. Jian Ren, Sergey Tulyakov, and Yan Yan. Discrete contrastive diffusion for cross-modal music and image generation. arXiv preprint 20X1: 2022.
Yuchen Zhu, Tianrong Chen, Evangelos A Theodorou, Xie Chen, and Molei Tao. Quantum state generation with structure diffusion model. arXiv preprint orXiv:2404.06335 2024.
17

---

Published as a conference paper at ICLR 2025
A MATHEMATICAL FRAMEWORK OF POISSON RANDOM MEASURE
In this section, we provide a mathematical framework for Poisson random measure with evolving intensity, which crucial for the error analysis of discrete diffusion models in the main text.
A.1 PRELIMINARIES
We first provide the definition of the ordinary Poisson random measure.
Definition A.1 (Poisson Random Measure). Let F2 P) be a probability space and (X, B, v) be measure space satisfying that
IV LVM < x0,
The random measure N (dt, dy) on RR x X is called Poisson random measure w.r.t. measure v if is a random counting measure satisfying the following properties:
(i) For any B E B and 0 < N((s, x B) (v(B)( s));
(ii) For any 2 O and pairwise disjoint sets {Bi) C (N.(B.) (((0, x B:)) are independent stochastic processes.
The following definition of predictability will be frequently used for the well-definedness of stochas- tic integrals w.r.t. Poisson random measure, and thus the extension from ordinary Poisson random measure Poisson random measure with evolving intensity.
Definition A.2 (Predictabilityy. The predictable o-algebra on IR+ x X is defined as the a-algebra generated by all sets of the form (s,t) x B for 0 S < and E B. process X₃ is called predictable if and only X, is predictable w.r.t. the predictable o-algebra above.
In the following, we will define the Poisson random measure with evolving intensity, which is special case of random measures (Jacod & Shiryavv, 2013, Definition 1.3).
Definition A.3 (Poisson Random Measure with Evolving Intensity). Let (D, be probability space and (%, B, v) be a measure space. Suppose ) is non-negative predictable process on R x X x Ω2 satisfying that for any 0 <T<? T,
J J IV lul (o < <0, a.s.
The random measure [[d] dy) on TR+ x % is called Poisson random measure with evolving intensity >e(y) w.r.t measure if it random counting measure satisfying the following proper- ties:
N[A]((s, 1 B) (I. C So (r()))(dy)dr))
(i) For any B B and
(ii) For any 2 0 and pairwise disjoint sets (Bi)iEjn) CB
[N+A)((B:) = N[A]((0, x B.)
are independent stochastic processes.
Theorem A.4 -Well-definedness of Poisson Random Measure with Evolving Intensity). The Poisson random measure N [A)(dt, dyy) with evolving intensity >e(y) is well-defined under the conditions in the definition above.
Proof. We first augment the (X, B, 1/) measure space to a product space (X x 1, X X m), where is the Lebesgue measure on IR, and B(R) is the Borel o-aleebra on IR. The Poisson random measure with evolving intensity >e(y) can be defined in the augmented measure space as
N[A]((s, x B) = J.
1 N dE),
(A.1)
J
18

---

Published as a conference paper at ICLR 2025
where (dr, dy, dg) is the Poisson random measure on R X x R w.L.. measure r r(dy)df.
Then it is straightforward to verify the two conditions in the definition of Poisson random measure with evolving intensity by noticing that for pairwise disjoint sets [Bi)ie[m) B, {B, x R) C B x (IR)) are also pairwise disjoint.
The Poisson random process [dd) dy) with evolving intensity Ax(1) is well-defined up to an eventual explosion time
{ 1/" (v(w)((d))dd 0o, a.s.
T inf
We refer the readers Protten. 1983) for more rigorous detailed version of the proof.
Remark A.5 (Relations to the classical Poisson random measure and that with tateedeeendennt den- sity). The classical Poisson random measure is well-studied by the theory of Lévy processes (Ap- plebaum, 2009), and the extension the state-dependent intensity is proposed and analyzed in (lasssrmmm & Merener 2004). Notably, Li (2002)) establishes the stochastic integral formu- lation for the chemical master equation with the Poisson random measure with state-dependent intensity, which is a special case of the evolving intensity, and subsequently shows the weak and strong convergence of the T-leaping scheme.
Remark A.6 (Relation to the Cox process). The Poisson random measure with evolving intensity shares multiple similarities with the Cox process (Cax) 1955: Last Penrose, 20T7)), including being point process and with the intensity being random measure. The main difference is that the Cox process is defined on a general measure space, while the Poisson random measure with evolving intensity is defined the product space (X x B, x (BR), v m) and the intensity function is required to be predictable to ensure the well-definenness of its stochastic integral.
A.2 STOCHASTIC INTEGRAL W.R.T. POISSON RANDOM MEASURE
The following theorems provide the properties of stochastic integrals w.r.t. Poisson random measure with evolving intensity. The proofs are based on the observation that with the augmentation of the measure space argument I)..), the stochastic integral w.r.t. Poisson random measure with evolving intensity in (X, B, v) can be reduced to the stochastic integral w.r.t. homogeneous Poisson random measure in (X R, B x ((R), v m). and under certain conditions on the measure space (X, B3 v), to the well-known Lévy-type stochastic integral (Applebaum, 2009). For simplicity, we will work on the interval E [o, 2] with T < T and the following regularity conditions of the Poisson random measure:
ess inf (x I
ess sup {² < +oG.
+E
=E(o,T],uEx
One can easily generalize the following results to their local versions on [0, T) by considering its compact subsets.
Theorem A.7 (Stochastic Integrals w.rtt. Poisson Random Measure with Evolving Density), For any predictable process Ky(y) on R+ x X x Ω the stochastic integral w.r.t. Poisson random measure with evolving intensity (
Tt ===
K. K.())
(A.2)
has unique solution, for which the following properties hold:
(1) (Expectation) For any O, we have
J. J K- K-(w)\-+))((dd)d) L [ K-(W) dm) =J""
(2) (Martingale) For any 2 O, we have
S 3x K-(W)N S/' ( (K((W)NNN((drddd)) 1 Kr (=())))(v)>((dy)d) is local Fe-martingale;
19

---

Published as a conference paper at ICLR 2025
(3) (Itó Isometry) For any t O, have
[ (=
E
Proof.
We first write the integral (A.2) in the augmented measure space (X R. B B(RR. m)
as
Tt = 1o + 1.' / Kr (oses)) dy, dE),
(A.3)
and since K2 (o))Ssss)))r is predictable process, the desired properties can be derived from the corresponding properties of the stochastic integral w.r.t. Poisson random measure augmented measure space.
The subsequent proof will follow similar argument as the proof of the stochastic integral w.r.. Brownian motion (e.g. in (Ksendaa 2003)) by starting from proving the properties for elementary processes, which in our case refer to working with the elementary predictable processes of the following form:
7- 1 m
(e(y
Σ
Zo (w) Iee(tatnl AEE
where to
in T partition of [0, T). Bj for [m] are parti- tion of X with r(B)) < 0o, and Cj E B(R) for k E [1] are a partition of the time interval [0, ess si. >>(y) with m(C)) < oo, and Kig, is bounded and measuuraa,, on which the stochastic integral is defined as
S. 2r (V dE)
n-1 m
ΣΣ> Σ
((tattee) Bj x Ck).
Then, it is straightforward to verify the properties of the stochastic integral for the elementary pre- dictable process Z, (y. E). using the definition of Poisson random measure (Definition A.I.. For general predictable processes (y, {), we write Ze(y, {) Z (y. E) 2, (y E), where Z, (y E and Zr (y. E) are positive and negative parts of Zy E), and apply the results to Z (y, E) and Z, (y. {) separately.
Finally, we take Ze(y, <) = (o(e)) to derive the properties of the stochastic integral w.r.. Poisson random measure with evolving intensity.
We refer readers to (Eberle, 20TS, Section 2.2) for detailed arguments. For the uniqueness of the solution to the stochastic integral, also refer to (Protter, 1983, Theorem 3.1).
Proposition A.8. Define the list of jump times (nn)eN recursively as
to = 0, tn+1 = inf tn An # 0}, n 0,
the Poisson random measure (dt, dy) with evolving intensity Xe(y) can be written as
N[A](dt, dy) >> Se. (df)oy, (dy))
(A.4)
n=1
and the stochastic integral A is càdläg and can be rewritten as a sum of jumps:
Σ Ari
20 Σ Ke (Yn),
(A.5)
where N a random variable satisfying iN S IN+1, and Art., are the jumps Aw., Ft,, -I,
with Tzz lim s-2 Fs..
20

---

Published as a conference paper at ICLR 2025
Proof. To see the solution is cådläg, we notice the following right limit at time t:
lim (re-e xze) = c00
[1,++]/xx Ke(t) dy) - 0,
and the left limit at time t:
/ ((())NNA(((t.d)))
J (((W)N( x dy), (A.6)
Dr. lim (ar Ie-e) c-0
(e-cxt/x
where the notation (ft x dy) should be understood ([A]((+)) x dy) = 0 if & [tx or otherwise Y, = .N [A]((tn) x dy) is a random variable on X.
Since the Poisson random measure N (dt dy) with evolving intensity A (v) is a random counting measure, it can be represented as a countable sum of Dirac measures as in (A.4)) and thus we have
It + [ (())N dy)
=Do S///// Ki(V)
NV
Σ 5rn (dt)oy, (dy) Fo
K2, (Yn).
n=1
By the definition of Poisson random measure, (tx)ne[N] are also the jump times of the homo- geneous Poisson random measure (dtt, dy. in the augmented measure space (X R, B x B(R), D x m) w.r.t. measure vddy)dg. Therefore, with a slight abuse of notations, we will assume (ln, Yn, EnNNENN are i.i.d. random variables with probability measure proportional dlv(dy) for each of which En S Ae, (Yn) holds because otherwise the jump would not occur.
Then the distribution of Yn can be derived as a conditional probability of the jump location Y, given the jump time t, and E, Xe, (Yn)):
P(Y, = v)v(dy) = Sa uddy) sx. (o)
den (v)u(dy)
(A.7)
J v(dy) 1E, Sen (w) dg
Jx de,, (w)))dy)
and the proof is complete.
The following theorem gives the martingale characterization of Poisson random measure with evolv- ing intensity, which will be crucial for the proof of the change of measure arguments:
Theorem A.9 (Martingale Characterization of Poisson Random Measure with Evolving Density). Let N (di,, dy) be a Fr-adapted process in the probability space (R, Then N [N](dd,, dy)) is a Poisson random measure with evolving intensity >e(y) if and only if the complex-valued process
Mifi= = exp (: (. [ (+(0)NTA((rrdd)) dy) + f.' J (1-01h(0)) > (x))((dy)drr)
(A.8)
is a local martingale for any predictable process [+ satisfying that f+(1)= E L* as..
Proof. By Proposition
A.S. we rewrite the stochastic integral as a sum of jumps:
S J ( dy) = Σ Sca (Yn),
where (In, Yn, En, are i.i.d. random variables with probability measure proportional to dtv(dy)dC, for each of which E, I Ae, (Y,,) holds, following a similar argument as in the proof of Proposition A.E.
Then, it is straightforward to derive the following probability of the jump time t, =
Sx PPYY = y, t, = T)u(dy)dr =
Jx (w))((ddd
Pttn = =T)d=
1/ 1/ P(Y.. = -,, = =d)ddd
(v)
21

---

Published as a conference paper at ICLR 2025
and by the definition of the Poisson random measure, we have the following probability of the total number of jumps . = 72:
1 P(N n) Te!
(-f A+())(la))rr) JT (( "
exp
Without loss of generality, we only verify [f]] as follows, and general cases are similar by Markov property:
i (15% /
x fea (1)
E
exp
|n s den (Yn), Vn e [M]]
E
exp
feo (Kw))
N
(Xn)) S de, [Yw)
E
E
N
X=
im [-
E
(x)(())
{ (1 (
exp (-fo L (n(evvlaydrr)
n
= exp (%, L (655100) - dr (
which immediately yields the desired result [[] = 1. On the other hand, for any 0 S and B E B, set
Zv( u () WER,
where u E R, and by assumption, we have
E [M, E [exp exp (., 2-0)) + S.'
elh-(o)) d (t--et)))))) (w)(dd))d)
iu S." / N(N + 1.¹ [ (1 (1-e" edd)) (1- X=(w)((do))tt)
-E exp
=F exp iuNTN)((ss,) B) + -ee")(( (t- / (=(0))((a)) =1,
i.e. the following holds for any u E R:
E (exp (iuN (s) 8] x B))) = (t) / dn (r(
which by Lévy's continuity theorem implies that
N[A]((s, Q x B) B)> / Ar(w))(du))
and thus [[A] dyy is a Poisson random measure with evolving intensity (v) by Definition A.
Theorem A.10 (Itò's Formula for Poisson Random Measure with Evolving Density). Let N [[t dg) be Poisson random measure with evolving intensity Xe(g) in the probability space (2,F,P) IP) and K2(y) be a predictable process on R+ St. Suppose a process I, satisfies the stochastic integral
Fo + 1/
K-(G)NTA((rrdd))
(A.9)
22

---

Published as a conference paper at ICLR 2025
then for any f(()) C(R* x X) with probability 1, have
s((x)) fo( + ( (, + S'' S (Jr(e,- + K,(1) - (x+-)) (N((dr))
Proof. By Proposition wc again rewrite the stochastic integral as a sum of jumps:
N
To
Σ
Ken (Yn),
n=1
where (NN] the jump times with to and In S t tN+1, and (Yn)ne are the jump locations. Consequently, it is easy to see that ,,,,, = = Zin-1 for E (fz-1, fnl and n E [N].
Then we have the following decomposition:
fe(xr)) - fo(wo)
N
=fe(ar) SeN (xex))
+
Σ
(It.)) Scn, (x + fen (x ) ( (Dem..))
n=1
=f"
1/10 0, (e
Jex O. +
Σ
Σ
(Fta + Ken (Yn)) - St, (Ztn-.))
n=1
n=1
and for the last term in the above equation, we have
Σ (fen (#tm.1 KK,,
-K,, (Ya)) fca (Ito- Σ (fa + (X,))) fen (3(=))
- -f, I (St(0r + K+(())) - ft )) N(A((drr
Combining the above results, we have the desired result.
Denote the trajectory obtained by simulating the master equation (2. of the forward process of the discrete diffusion model as Iı. then the time interval At, tn+1 tn is distributed according to the following distribution:
Lemma A.11.
( QT. It )d,
P(At, > -
(A.10)
and the jump location Tea distributed according to the following distribution:
P( v) Qenti (3,, It,,)
(A.11)
Quaen (It, Ita.)
Proof. The results can be found in (Eberld, 2009 Section 1.2). While fully rigorous proof can be conducted by discretizing the time-inhomogeneous continuous-time Markov chain into 2" uniform steps and taking the limit more intuitive proof here for completeness.
co, following the approach in (Lalley, 2012). will provide
Pt.. = ex.. where by is the y-th unit vector R| then the Jt,, entry of (2.) yields
d
P(#z = v...)
dt
di
BEX
which, by the assumed continuity of the rate matrix Qr, implies
IP(At, > 7) Paxx, +r zt..) Q+,, (I It.,) ( + O(T),
23

---

Published as a conference paper at ICLR 2025
and thus
d
log P(Ann > T) lim Qt, (st,,, Ft,.) o(1) Qt, ttm:
log , 7) lim r-
5-
integrating the above equation yields the desired result.
Similarly, by setting P = Cri,"" we have for all y E X for,):
P( = y) = Ptnt1 (1)
Pt. P1.11-1(0 (1) + Qt. 1-- 21, o(T)
lim
7 Evex)(Ern) } (Pim.12-(()) Q Q 1- (1, Ii JT O(T))
Plats (3), Izn))
Qbzps (y. Ftm))
Σ EyEx)(Ren Qenti (1/, Frt.)
Qta (Dia Dtt
and the result follows.
A.3 PROOFS OF CHANGE OF MEASURE RELATED ARGUMENTS
Proof of Theorem P. In the following, will denote the expectation under the measure IP by Ep and the expectation under the measure Q by Eq-
By Theorem A verify that the Poisson random measure [dt] dy) with evolving intensity (B) is a Poisson random measure with evolving intensity he())he()) under the measure Q, suffices show that for any L' (X, the complex-valued process
Mc[]] = exp (. Je [SW)NNNa + +f6 (1- X (x)
a local martingale under the measure Q
To this end, we perform the following calculation:
Ec
[MII]]
Er [M] ((NN()((rr + [/ (1-o((w) > (
exp $ (/// [
= Er
exp (L, S (ogg dyy) (/' ((ooc))
=Ep exp ( S/" f (f(v) + (v)) N()((dr,y))) dy)+ + S/" ((1111111101 (1-2310))e(w) s(prr(aa)
EEr [M]f + log h]],
and by assumption, + L L'(X,)), a.s., which implies that M, [foflooo h] is local martingale under the measure P again by Theorem A.J. Consequently, Mr[f] is local martingale under the measure Q and the result follows.
Remark A.12. One may verify that the exponential process 7, in (G.1)) is local Fe-martingale by Applebaum (200%, Corollary 5.2.2) under mild assumptions on the function hy(y) (ef. Novikov 's condition in the Girsanov's theorem for Itô integrals).
Proof of Corollary 34 With a similar argument in the proof of Proposition 6.2 following stochastic integral representation of the approximate backward process with the learned neural network score function Sy:
we have the
yo + 1-" [ (w- uo-ya- y-- -------N (N (ds, dy), with pl(2) 50 (.. (v.- :1) = (A.12)
By the datc-proesssing inequality and the chain rule of KL divergence, we have
DRL(#Tllm ((r)) DRL. (Po.rllgor)) DxCt. (Po (l)) + (Po. Yo =y]]-
24

---

Published as a conference paper at ICLR 2025
Then notice that conditioning the alignment of the initial state To 3/0 for any y X, the second term in the above equation can be expressed as
do:T
7
DKL (Po.r 110 Fo yo y) E
log
Fo yo y log Z
dqu:r
where the last equality is by the change of measure in Theorem B. from the stochastic integral formulation (6.2) of the backward process (2.8) with the true score function ă to the stochastic integral formulation (A..2) the approximate backward process with the learned score function 8
Plug in the expression of Zr in (3.33) and notice that
70 8. (v, (v.-
8. U1s
ys By (1s- (Vs-.1)
8. (Vo= y)
we have
11
E
log ZT
20
[[a(dds x dy) + /'' /
30 (2. 12)
$g 9 (3
=E
log
Holv)u(dy)ds
x
8g 2y(s5, (y--,8)
B3 1
E
8. (yo- .1)
log
58 8, Uv- 9)
3 (M.
x
F. .1)
5, (3/s y)
20 (y- (ous--))(dyddss (y v) 5. (yss 9) 5 y) log 3 (y)= 41
=E
rearranging the terms in the above equation yields the desired result.
A.4 PROOFS OF STOCHASTIC INTEGRAL FORMULATIONS
Proof of Proposition 1 In the following, we will denote the trajectory obtained by simulating the
master equation (2.77) of the forward process of the discrete diffusion model as Σ, and the trajectory obtained by the stochastic integral (B.II) 24, with zo To. We will also use the notation - to denote the quantities associated with the trajectory Tt. The goal is to show that ia and Te are identically distributed for any E [0,7] 7).
We prove this claim by induction. We assume that for any E [0, fnl. where n E N and t, is the n-th jump time with to = O, the two trajectories x, and T. are identically distributed. For simplicity, we realign the two processes x, and T. at time L by setting It., It,,
We first consider the process 3. generated by the discrete diffusion model (2.7). Recall the definition (e) = Qu, ), we have that
(c())(dd)) Eily, -Q.(-) = -
(Tr Tc.,;; for (ons bn+1).
BEX
By Lemma the time interval AFn = En+1 - En is distributed according to (A I0), i.e.
P(A > r) = exp ( Qr (Te, Jt, )ar)) exp (-o / (+())rldyddr)
Similarly, the jump location Teass is distributed according to (I. iee.
Qiaar (y, It.,.
Nenis (v)
P( = = Qtip (Tt,,: Ft..)
Ix Xent (y)v(dy)
Now we turn to the stochastic integral (G. By definition of the Poisson random measure, we have
(xr(e)v(aa)arr) (A.13) P(At, > 7) (PN[[)](( tu + + x x) = 0) = exp (-),,M. pfr
25

---

Published as a conference paper at ICLR 2025
and the jump location is distributed according to 12..2) i.e.
Nenui (v)
P = v) Ix Aents (V)
(A.14)
Comparing the arguments above, we conclude that the two processes and Ty are identically dis- tributed for any / E [0, 1x+1), and the induction is complete.
The proof of the equivalence between the backward process of the discrete diffusion model governed by (2.8)) and the corresponding stochastic integral (3.22 can be conducted similarly, and the result follows.
A.4.1 T-LEAPING
Proof of Proposition 7 Without loss of generality, we give the proof for = SN. and the general case can proved similarly.
The stochastic integral (4 can be partitioned by the time discretization (S:)kE(o.N] into N intervals along which the evolving intensity is constant, i.e.
DaN = yo + 10¹ [ [w
- DU-Baa-)N((PLy((la dy)
N
81
[ (y) -Do )
- -0 +
Σ
To;,) [ún I(ds, dy)
1=1
84-1
00 + Σ
(v- D ((5-111) dy),
[
i=1
which given X is finite, can be further decomposed into the following sum of jumps:
N
(y - U., Dex = 1o +
2=1
x
+
Uzg J. {4})
i=1
MEX
N
~0 +
(v D,,,) )P((s
81-1) (V)),
MEX
which is exactly (1 in the T-leaping algorithm (Algorithm M..
Remark A.13. In Algorithm and Proposition I we have implicitly assumed certain underlying additive group structure on the state space X such that the difference - in (B and ((s)- (H and their multiples are well-defined and can be summed up with states. certain spaces with apparent ordering, e.g. [8]s, this assumption can be easily satisfied by resolving violations at the boundary of the state space with clipping operations. In practice, these discrepancies only happen with a small probability given a sufficiently small stepsize, as will show in the following proposition.
In order to quantify the issue in Remark A.T and apply the change of measure argument in Theo- rem B. to the r-leaping algorithm, we provide the following alternative stochastic integral formu- lation of the r-leaping algorithm.
Proposition A.14 (Alternative Stochastic Integral Formulation of r-Leaping). Under the assump- tion on the time discretization scheme and the choice of parameters in Theorem E.A with probability
1 1 (KDDTT), the r-leaping algorithm (Algorithm [ is equivalent to solving the the following stochas- tic integral equation:
Te No + 1 { (1-1y--- NN..
(A.15)
where the evolving intensity P. (v) is given by Di (v) b (Tt (-)
26

---

Published as a conference paper at ICLR 2025
within the time interval (Sns Sn+1] and assume that y is left-continuous at time 8n which happens with probability 1.
Proof. For simplicity, first consider the stochastic integral (4W))
Notice that (A. only differs from (9 in that the integrand is evaluated at each time instead of the starting time of the interval [$] Sn.- Consequently, V. coincides with y = ys. before the first jump within the interval. Therefore, both the first jump time (AA.T) and the first jump location 44) are distributed identically for the two stochastic integral formulations, and if no further jump occurs within the interval, the two formulations are equivalent within the interval.
We bound the probability of the scenario where the two formulations differ, i.e. at least two jumps occur within the interval (sn; 8n+1]. We will denote this event as An. By the equivalence between Algorithm II and the stochastic integral (9.2), we have that
P(A.)) P
Σ VEX
P (i (v) -aa)
= -1-P P
Σ yEX
Ma (V) (m)
1 - exp
Σ
Th (8)(1 -8a)
-8)))188)) 8n)
Σ
pe (8)(1 8n)
VEX
VEX
[
2
pe. (g)
which, with a similar argument as in IA), further bounded by
P(An) (1 (T snt1) (s
and thus
P An
(IV (T -2 D³ D3($n11 =,,)²
n=
(IV 88+1) 114-))) D³ D2n($at1 8n)
SKD
T
- S SDDTT
where the last inequality is by following the same argument in the proof of Proposition C and the choice of the early stopping time ő in Theorem 47 The result follows.
A.4.2 UNIFORMIZATION
Theorem A.15 (Accurate Simulation by Uniformization). The uniformization algorithm (Algo- rithm Ø with its stochastic integral formulation in (8.4) is equivalent to the approximate backward process with its stochastic integral formulation in
Proof of Proposition 2.2 and Theorem A.I. For simplicity, we only consider the stochastic inte- gral 4) within the time interval (sp, 1b+1]-
We rewrite the stochastic integral
sum of jumps:
N ysu+1 Yss (Ya - V Lus., Peng, (vurddy)
where by Proposition (sb.n)neIN) are the jump times and (Yn, En)nENI are the jump locations that are distributed according to
P (2)
po (v)
P(Y, = y. E, = =)
(A.16)
Jx ph (y)r(dy) So dg
Ixx Pe (y)u(dy))
27

---

Published as a conference paper at ICLR 2025
Therefore, the n-th jump is not performed if P (V))(dy) <En X, which is of probability
P(En > Per.. (Uor.))) )) = Ix 1 (w)x(dy)
X- 1-Ix P. (v)v(dy)
Ix P (v)u(dy)
A
Ix 12P% (y)(dd
and is to the state with probability
P Yn v. S / ( (w)((a)))
Dea (v)
Sx Me (v)v(dy)
De (v)
Ix Pe.... (v))(dy)
which coincides with in the uniformization algorithm (Algorithm D) By conditioning on the occurrence of each jump, i.e. 0 S En S Sx n2 (v))(dy), with slight abuse of notation, we have that
Yu = / oSE, S ( (w)((a))
Men (v)
Ix P (v))(dy)'
which again by Proposition A implies that ys also satisfies the stochastic integral (A sponding to the approximate backward process, and vice versa, and the result follows.
B RESULTS FOR CONTINUOUS- TIME MARKOV CHAIN
In this section, we will provide some results for the continuous-timg time Markov chain (CTMC), includ- ing the mixing time, the spectral gap, the modified log-Sobolev constant, etc.. Definition B.1 (Graph Corresponding to Rate Matrix). We denote G(Q) as the graph corresponding the rate matrix Q. i.e.
((Q) (X, F(G(Q)), Q), where F(G(Q)) (1,,y) EX X/x # y. (x,,)( 0) and the weight of the directed edge (x. v) E E(G(Q)) is Q(r, v)-
We will assume that the continuous time Markov chain is irreducible and reversible on the state space X, and the corresponding stationary distribution is
B.1 SPECTRAL GAP
Definition B.2 (Spectral Gap). Let L = -Q be the graph Laplacian matrix with D = diag L,
corresponding to the graph (QQ). with
0 )=>(L) X2(L) .... 5 max D(x, =D,
zEX
the spectral gap X(Q) of the rate matrix Q is defined the second smallest eigenvalue of the graph Laplacian L, i.. (Q) = (L))
Remark B.3 (Asymptotic Behavior of the score function st). Assume Q is symmetric with the following orthogonal eigendecomposition::
Q = -UAAA.
where = (2 U2...., Uix is an orthogonal matrix, and the distribution pt has the following decomposition w.r.l. the eigenvectors of the graph Laplaciann L:
X
p: Σ
=
28

---

Published as a conference paper at ICLR 2025
then the solution to the master equation (2.7) is given by
X
Pt exp(1())p U exp( Po U exp((11))a)
U exp( -11)) (j),
i.e. a, - exp(-tA))eer and thus for any i E [|x]].
Pe(1) Po())
Σ E0,00000))20000
j=1
321
Therefore, we have
vx (v( po(y) - 160)00010000
(x) Po(x) - ()()))0(0000000000 IV (Ft)
given that the following condition is satisfied
F
min #EX
Σ ())()))o()))
>0,
which only depends on the initial distribution po and the rate matrix Q. Especially, the bound se(z, v) S 1 for any x E X s.t. po(x) and st 4) S t- for those
Po(x) =0. O.
Definition B.4 (Conductance). The conductance (99) of a graph g is defined as
ExESyyS Q(x,1)
((
min SCX min [EEES D(x, x), Enes D(v
Theorem B.5 (Cheeger's Inequality). Denote the normalized graph Laplacian matrix by İ D LD-111 with eigenvalues
5 (I 5e) S... \/x [L) 2,
then the conductance of the graph G(Q) can be bounded by
1 No L < (G(()) S (1)
B.2 LOG-SOBOLEV INEQUALITIES
Definition B.6 (Modified Log-Sobolev Constant (Bobkkov Tetali 2006))
For any function f.g
X - R, we denote the entropy functional Ent, (ff of f as
Entz( [ log f] E [x] log F. [s]:
and the Dirichlet form (x as
Ex(f.g) = = In = Σ (W) = Σ f(z) v))())(()))
yEX
Z.yEX
where the Laplacian L = Q. Then the modified log-Sobolev constant the as
the rate matrix Q is defined
E (o, Ent (f)
f R, Ent (f) > =0)
p(Q) inf
Theorem B.7 (Theorem 2.4, (Bobkov Tctali 2016).. For any initial distribution po, we have for any 2 0.
(pilpi I DRL (pu(pol exp (-p(Q)t)
i.e. the KL. divergence converges exponentially fast with rate p(Q).
29

---

Published as a conference paper at ICLR 2025
Proof. Noticing that Ent ( ( obtain that
DKL (pill differentiate DKL |T)) with respect to t to
d (Pol(T
d
(z(
log
(c(
[T()=
(T2) = Σ
log Pc(x) ग (2)
+ T
d (x(x)
di
di.
(xx)
T(())
di (σ)
TEX
TEX
pe(x) x(x)
d
Pt(x)
log
+
Pr(x)= =- Σ
log
L(x, y)(())
dt
ZEX
S.EEX
(B.1)
Pr(v)
L(z, y) log Pc(x))
Σ
π(x) T(2)
(y)
VEX
ZEX
Pt
log ( - ((()) (p.lTt
En
and the result follows by applying Grönwall's inequality to both sides above.
Then, the following proposition connects the modified log-Sobolev constant with the spectral gap. Proposition B.8 (Bokkko & Ictafi 2008, Proposition 3.5)). The modified log-Sobolev constant p(Q) of the rate matrix Q is bounded by the spectral gap X(Q), i.e. p(Q) S XQ))
Proof. Below we provide sketch of the informal proof of the proposition above for the sake of completeness. Let f : X - IR be an arbitrary function and Ç > be any positive number. From the definition of the modified log-Sobolev constant, we have
Ex(e ,Cf 2 p(Q) (et,,
(B.2)
Under the limit < + 0+, we may apply Taylor expansion to the two terms on the LHS and RHS, which implies
Ex (e51, .ff)
+ (1 (f
[E> E [
Ent (efs)
Fn [1+C(++((()) - B (J + 0(53)) log E (65))
(B.3)
((+( log (1 [[+
[[E + ( + (1+ (E= + O((3)) (<E+)))0((²))
= c²
O
Substituting (B. into (B22) and taking the limit Ç - 0+ then yield the following inequality
(x,
p()) E+ Ex
for any non-constant function f: + R. Taking infimum both sides above with respect all then indicates
ff
Ex(f.f) [
p(Q)= inf [ 15
inf f=E=1/]=0
A2(D) X(Q)
(B.4)
where the last two equalities above follows from the definition of spectral gap, desired.
In general, the lower bound of the modified log-Sobolev constant p(Q) and the spectral gap X(Q) depends on the connectivity and other specific structures of the graph G (Q), and the related research
is still an active area on a graph-by-grape basis (Bobkov & Tetali 2006).
The properties of the spectral gap X(Q) are better known in the literature, as it closely related the conductance of the graph g ((Q) via Cheeger's 's inequality (Theorem B. and thus when D DI, the spectral gap X(Q) satisfies
1 M S ((g(2)) < 222 = 21(Q) 2D -
(QQ
D
30

---

Published as a conference paper at ICLR 2025
However, shown in Proposition BX the lower bound the modified Log-Sobolev constant Q
hard to obtain, as the KL divergence, the exponential convergence which is controlled by p( Q), stronger than the total variation distance, the exponential convergence of which is controlled by (Q)), via Pinsker's inequality. The following theorem gives a rough lower bound on d-regular graphs.
Theorem B.9 (Bobkov & Tetali, 2006, Proposition 5.4)). Suppose G is d-regular graph on X
with unit weights and Q the corresponding rate matrix such that ((Q) 9, then the modified log-Sobolev constant pl (Q) of the rate matrix Q satisfies
((Q)
8d log X
S p(Q S
log X
diam
where diam(() the diameter of the graph G.
For some specific graphs, the modified log-Sobolev constant p(Q) and the spectral gap X(Q) can be explicitly calculated, such as the following examples:
Example B.10 (Hypercube (Crross, (1755). Let X {0, 1 and Q be the rate matrix for which the graph (QQ) is a hypercube, and for any two states x, y E X, the rate Q(r,8) y) = 1 if and differ in exactly one coordinate. Then the modified log-Sobolev constant ((Q) and the spectral gap (Q))
are given by
=
which is dimensionless.
Example B.11 (Asymmetric Hypercube (Dracomis Coste 1996)) Let X {0, 1] and Q be the rate matrix for which the graph (Q)) is a hypercube, and for any two states æ, y E X. the rate Qxx, y) = if x and differ in exactly one coordinate and x is the state with 0 in that coordinate, and (z q 1 p if with in that coordinate. Then the modified oo--ooolev constant p(Q)
and the spectral gap X(Q) are given by
2(p q)
p(Q) po(logp log 4)
and x(Q)
pq
Further results on log-Sobolev inequalities related to finite-state Markov chains are beyond the scope of this paper, and we refer the readers to (Stroock, 1993 Saloff-Coste, [199; Bobkov & Ledoux. 1998: Lee Yau. 1998: Goel 2004:
Ledoux. 2006) for more detail.
B.3 MIXING TIME
Definition B.12 (Mixing Time). We define the mixing time bmizz(e) of the continuous-time Markov chain with rate matrix Q as the smallest time t such that starting from any initial distribution po. the KL divergence DKL (PellTt) is less than i.e.
(E) = inf {+ B.
E DKL DKL(E - Se..
Similarly, we define the mixing time Luix,T((e) as the smallest time such that starting from any initial distribution po, the total variation distance TV(pt, π)) is less than i.c
(vix,Tv(e) = inf EE E TV
(eV(p,.T)) T) = TV(e (V(e-190 '9 T se
With a slight abuse of notation, we will also denote the e -mixing time as fmix = ki (e-)e) and Lmix,TV Lmix,T((e"
Proposition B.13. The mixing time teise()) of the continuous-time Markov chain with rate matrix Q is bounded by the modified log-Sobolev constant p(QQ) i.e.
(mix(() S p(Q) (loge + log log n.
And the mixing time Tvix,TV(e (e) is bounded by the spectral gap X(Q), i.c.
Imix (c() ((Q) (loge-> log log 11
31

---

Published as a conference paper at ICLR 2025
Proof. Define n, min IT (2)),
first bound DKL (PullT) follows:
DKI(PolPass S log (a
log n.
(B.5)
x (x)
DEX
and thus by Theorem B.7. we have
(pI(P) S (po((pol=T) exp expp)))xppppppppppp (-p(Q)1) S log ,, exp((xp(Q))
(B.6)
Therefore, by setting the right-hand side of (B.6) to be e, we have the desired result for the mixing time
tmix (E) S p(Q) (loge + log log म.
For the mixing time mixx (e).. use the Pinsker's inequality to obtain:
1
TV(p,, T) S DKr (pelTT) s V
log m exp(-p(Q)1)
and therefore,
Tvix,TV(c) 2 p(Q)
1
log ( V 2 p(Q)
1 (loge
log log n.
Corollary B.14. The E -mixing time tnix and tmix, TV of the continuous-time Markov chain with rate matrix Q satisfy
mii p(Q)) -1 log log n. and fmix,TV E p(Q)) (Q0))"log log log π._
and thus tmix 2 mi..
C PROOFS OF ERROR ANALYSIS IN SECTION
In this section, we provide the proof of the primary results in the main text and their sketches.
C.1 PROOF SKETCH
A general pipeline of the proofs of Theorem 7 and g is to decompose the KL divergence between the target distribution and the distribution of generated sample as summation of the truncation, approximation, and discretization errors, and then bound each term separately, echoing that for the continuous case in Section
As in the continuous case, the truncation enror is caused by the finite time horizon of the forward process (2.77) and is thus bounded by the convergence rate of the con- structed forward process. In our work, use the modified log-Sobolev constant p(Q) to bound the truncation етror (cf. Definition B.)). As discussed in Appendix H. lower bound on the modified log-Sobolev constant p(Q) guarantees the exponential convergence of the forward pro- cess (cf. Theorem B.), which then implies the upper bound on the truncation error presented in Proposition CT
Truncation Error:
In the r-leaping algorithm, the discretization error is caused by the ap- proximation of the backward process with piecewise constant function, and should decrease as the time step K decreases. We first analyze the discretization error within one step (ef. Propo- sition (X4 and then provide the overall discretization enror in Proposition 055, taking different discretization scheme into consideration and deriving early stopping criteria. In the uniformiza- tion algorithm, due its exactness, the discretization error is zero.
Discretization Error:
Approximation Error: The approximation error is caused by the estimation error of the score function, and is bounded by certain error assumptions (cf. Assumption BXG for 7-leaping and Assumption P.6 for uniformization) on the score function estimation in the training process.
Then in Appendix Cz) we first invoke the change of measure theorem 6 and obtain KL diver- gence bounds for both algorithms (Theorem C and C.), and then provide the overall error bounds thereafter.
32

---

Published as a conference paper at ICLR 2025
C.2 TRUNCATION ERROR
Theorem C.I (Truncation Error). The forward process (2.2) converges to the uniform distribution Pco 1/|x| exponentially fast in terms of the KL divergence, i.e.
DKL (pL(pil DKL
Pt
[X]
e 1e log [
where [X] is the size of the state space, and tmix is the mixing time of the contimuous-time Markov chain corresponding to the rate matrix Q defined in Definition B.72
Proof. Since is symmetrie, we have the stationary distribution π 1/ and thus (pel = DRL. ()) and IT. = 1/12] By Assumption A.3 and Theorem B.Z. we have
(pL(Pel T) p(Q)) DEL (po |T)) S - log मं S e- log [X],
where the last inequality is by (ES))
C.3
DISCRETIZATION ERROR
Denote the shorthand notation G(r;;) y) = x(log logy) ax; it is easy to check that G' log z log y.
Proposition C.2. For any y X. we have
(0 (1)) S (log C + log (1 (T oo) + log M) (1V
Proof. By the chain rule, we have
O.G(uo P.... (w)) Pl
(log (v) - log 1 ((s.,(())) Pa
We first compute (,(1a(()
Po(U)
(v) = (0), (
=Q(ī,-,0) .8)
1
OoFo(y)
(I jz 100 (xo
(o(
Po(
Σ Po((')
Quu 1/) + (o(
Σ Do(1))
-Q(Fa-
2x ,0/)
Po (To-)
Po
(v)
Do (xa-))
Po (aroa))
e/ex
(v)
Σ vc(u.v/)(u..'))+
+ Σ
No (E [/
VEEX
WEX
by which we have
1o. (oHH(()1 (v)1
(w)l (2(
Σ
(T ()) (1V
S so (==3)((=0-,'''11 (LVV)((L
D'Ex
and thus
0, O,G((H Pla.. (v)) < log (1log Q(To- y)1 log For (To .1) + log Q(5 o5 y)1 + log 8on (T.,,,)) wl) (0
log log 06 (w) (2)
Spa(V) (log log (1 v (T- -)- -1 log M) D (1 (T o)-
33

---

Published as a conference paper at ICLR 2025
Proposition C.3. For any 0 < <ts T, we have
S: [ Ho ~ (I D(t s).
Proof.
- J. p f/ 3d
(1V (T S. / Uly, Olu,
(C.1)
((I - -)-1) /: 1Q( Fo )ddo $ (T D(t - s).
Proposition C.4. For any y E X. we have
E 1 Me.. (V)) G(us, M4 (1)) [w)] x (log C + log (1 V (T snt1) + log M) no (v) sn) (1 (1 8xt2)-1-9)
Proof.
Applying Theorem A.10 to the backward process (3.2) we have
Glus(w):M(e..) (1)) -Guu, (w): + [ G.G(Ho (v))do
+ +f
Nn / (v):
G(H (e..) (w)) N Niul(do, dy)),
where we adopt the notation M4+ (y) as the right limit of the càglàd process po(y), iee Hot (v) (Fa,,)))(( ()a((r)))))))
For the first term, we have by Proposition C that
If a, (1): dn
x {( [l, (w)) do
sn
2A
(log C+ log (1 v (T- - 1) + log M) pe (1) (1 (T - (T- 3) do
$ (log C + log (1 v -n+1 + log M) no (() - sn) (1 V (T s1)
For the second term, we have
(v)= (em))))))) - G(uo (v): (2))
G'(E: ...] (2)) (y) no (v)) = (log & log ( (3)) (v) - mo(2))
|log por (v)l + log Ho (v)l + log (w)))
Mo+ (y)
(1)(1)
(o(
S (log C + log (1 v (T 1) + log M) (1 v - -T) -7) ( (y);
where the first equality follows from the mean value theorem and the last inequality is by Assump- tion 9.5l
34

---

Published as a conference paper at ICLR 2025
Therefore,
G(usi (s..)()).))))) - G(meni i( (1))
<B
a (v): (o))do))
[." / G(por (o)) (v): ((,)) dlul(d
+
2 (log + log (1 V (T 8nt1) 1) + log M) no D(s - s.)) (1 v VT 80+1)
/
(log C + log (1 (T - /) + log po (1 (T - -) po (u)dddd
Nn x
2 (log C' + log (1 V (T' Sn+1) + log M) no (v) -
s, (1 (T' - so+1)
(log C' + log (1 V (T 5n+1) + log M) (1) V (T mn+1) 1--1)-1-3) Sn)
(log C. + log (1 (T' -8++1) + log M) p (y) s..) (T- 80+1) (1
where the second to last inequality is by Proposition ok
Proposition C.5 (Discretization Error). The following bound holds
1 T-6
/ [(P.(W):F(.., G(Ho.. [,0 (v)) v(dy)ds
D' KT,
9<1,
D²x K (T log 1og2 9=1,
T.. IT + log 8 8-1); 7 1= steps, by taking y < T when y < 1, and 1) when 7 In particular, in the former case, early stopping at time T 8 is not necessary, i.c. 5 = 0.
7 <<1
with N
Proof. We have by Proposition C4 that
(an)))))))))))) (v)) G(uon (V) (v)) v(dy)ds
x
[ (o(y))(dy)
(log C log (1 v (T Sp+1) + log M) D(s s.) (1 (T sx+1) -1-7) ds
S (log C log (1 v (T' 11) + log M) D³ (3(2511 - sn)² (1 (T sn+1) -117).
Case 1: < 1-7--
The following bound holds
Bn+1 ( (alual)): Po..) (v)) - G(us, (v): (1): (wi) uddydds
$ (1 + log (TV(T-
- sn+1)
D² ( - 8n) (1 (T -8+1)) -1-
35

---

Published as a conference paper at ICLR 2025
and thus, the following error
/ G(uu(W):P(o. (v)) - G(psn (0): (z): (4)) u(dy)ds
(t))
0
(1+ log (1V -T snt1) (1 D k(Sn+1 spp (1V (T snt1) 1
<D'R T t- 1-1-1- log 1 S D' (T+ 8-1 (1-(1-1) log tdt
6
<Dx (T + 8 log 0- D'IT,
KT, a +0,
is achievable with finite number steps N, i.e.
N J (1A dt Sx x 'T + k 11
1]
t dt 2 -1
T+ ( S TT
8
where we take 1 E 1-T
Case 2: 7=
We have the following bound
/ G(u G(us, (v): (1); (v)) p(dy)ds
3 5(1+ + log (IV - (T--TT+))--) D' k(8n+1
D'k(s4( - sn) (1V (T - s1+2)-t).
and similarly
8nll /
G(ass)): G(uen (v): (x)) u(dy)ds
n=0
N-1
Σ
log (I 1)) D k((n+1 8n) (1 V (T snt1)
8-1 t-' log ldt
<D'
2 T
s DD (T log² 8-1).
K
However, the number of steps N is now bounded by
N S { m(IA() dt S (T log 8 1)
C.4 OVERALL ERROR BOUND
Theorem C.6. Let poer and qu.T be the path measures of the backward process with the stochas- tie integral formulation (5.22 and the interpolating process (A.3)) of r-leaping algorithm (Algo- rithm (l)), then it holds that
[[ log log
(1110)
moly)
DKL (oorlloo S DKL +E
(x(3) P(a)(()) p(dy)dt
(C.2)
where the expectation taken w.r.t. paths generated by the backward process
Proof. The result directly follows by the arguments in the proof of Corollary 14 in Appendix
and invoking the change of measure formula (Theorem (3) w.r.t. the true intensity μ4 as in (52
and the approximated intensity p in (8.2), Proposition I.
36

---

Published as a conference paper at ICLR 2025
Now, ready present the proof of Theorem A7
Proof of Theorem A
We first rewrite the integral in (C.3))
Bnt1 { (e(3) log
Ms(y)
Mo(y) + P(,)(u)) u(dy)ds
M.a (v)
pdnt1 {{ Mon (V) log
Ma (v)
[ (v) Mon (v) +A(s] M(()(()) (v)
G(ualy)) (w)) - G(us,, (1): (u) (,, p(dy)ds.
Therefore, the overall error is bounded by (KL(Po-T-lll) -olorr--oloo-)
(F (1ool + +E
10- T
/
Mss. (v)) (v) log
Msn (v)
Men (v) Mon (w) o(dy)dt
plon.] (3)
G(Me, (1): 01);)(1111 (v)) v(dy)ds
(PT-PTTAll) (PT-lpo)))
(snt1 - sm)
3an (F am v) (F
log
Sx, (F,,,)) v) 50 (F,,.0) ((3.,.,)((0))
30
An v4) km
N
+
(log C' + log M) D' k(sn+) 8n)
n=
exp(-pZ')) log X + + D²x2 kT,
<<1, 7 7=1,
2A
exp(-pz') log x + D² k (T log (-228-1). 8-1),
where the last inequality we used results for the first term (Truncation error, cf. Theorem M.). the second term (Approximation error, cf. Assumption (.G) and the third term (Discretization error, of Proposition
By taking
(0(Log) log (e- log (x]) ): = O
T-
cp
D² log (E- log xx)
deploying the time discretization scheme with 7 < S 1, and performing early stopping as
T when 7 1, and 7 when
0, {0
<<1,
0 expppl (exp((-VTT)
7=
have DKL ( & DKL P
sllāurr-6) S with
D log" (E- (E- log [X])
N K =
cp2
steps with probability
1- o (ND'TT =1 1-0(mD')=11- -
The proof is complete.
37

---

Published as a conference paper at ICLR 2025
Theorem C.7. Let Po:r and qu:T be the path measures of the backward process with the stochas- tic integral formulation ((3.2) and the approximated backward process 49 of the uniformization algorithm (Algorithm (2)), then it holds that
DKL (PoTT111)))))) S (Poloo))))) E
Jo (Mo(t)
log
(e(y) (7
u + pL(v)) u(dy)dt
(C.3)
where the expectation is taken w.r.t paths generated by the backward process (3
Proof. The result directly follows by the arguments in the proof of Corollary + in Appendix
and invoking the change of measure formula (Theorem 3 w.r.t the true intensity Ms as in and the approximated intensity T7. in (9.4), Proposition
Proof of Theorem g
Due to the equivalence of the stochastic integral formulation 44 of the
uniformization scheme and the approximate backward process (A..22 established in Proposition H.2) the error for the uniformization scheme is directly bounded by the error (C.33) in Corollary 6.4 i.e.
( alloorrslllo:aa))
J/ T- / (Hs(v) log pa(y) px(() n2((v) uddy)at
(PL((oll00) + E
(1)
(PT((PT))
+E
(x(Fa-1 log ( .9)
(o 1)
(F 33, @(F.-
x
S exp(-pT) +c.
The expectation of the number of steps N is bounded by
B-1
B-1
E = E
Σ
P
(Toup2 ($6+1 - -bo))
Σ
Janes (86+1 - 8b)
6=
6=0
D(V (T -T--))))))))--444 (041))-((66+1 -sb)
T ilde) DDT +log8-1)
SD
By taking
log (E log (xl)
8= Ω (exp((T)
=
P
we have (KI (1 S DKI. -olfo--ssll0o---- S with
D Dlog (E log (x])
E[N] = o
steps.
38


Reviews:
[{"review_id": "GmDDrCPKSk", "reviewer": "Reviewer_XLAW", "summary": "This paper addresses the challenge of error analysis in discrete diffusion\nmodels. To bridge the gap between discrete and continuous diffusion models\n(for which the error analysis is better understood), the authors propose a\nframework based on Levy-type stochastic integrals, by generalizing Poisson\nrandom measures to support state-dependent and time-varying intensities\nunder assumptions of regularity of rate matrix, and bounded and continuous\nscore function. This framework allows for error decomposition into\ncomponents such as truncation, approximation, and discretization errors,\nproviding clearer insight into error sources.  The analysis is performed\nfor tau-leaping and uniformization methods, two methods to simulate the\nbackward process. They establish stronger error bounds compared to previous\nwork using KL divergence.", "questions": "Questions inserted in weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Pros:\n- Very non-trivial theoretical work.", "weaknesses": "Cons:\n- Positioning of the work is not clear. It is not compared clearly with\n  previous work.\n- Motivation and implications for practical usage not provided.\n- Very dense writing. Hard to understand.\n\nDetails:\nThe main results are two theorems, one for tau-leaping and the other for\nuniformization. No attempt is made to provide outlines of the proofs. What\nis the basic motivation for this research? How does it contribute to the\nfield (reduce algorithmic complexity, improve guarantees, etc.)?\nThe reader could greatly benefit from proof outlines.\n\nThe paper is very hard to understand. For a reader who is not deeply\nimmersed in this topic, it is almost impossible to understand the\nimplications, general approaches, and the proofs themselves.\n\nThe third bullet in contributions says that the work unifies and fortifies\nexisting research on discrete diffusion models. The reviewer did not come\nacross any statement in support of this or elaborating this point.\n\nRelated works does not cover any theoretical work on discrete diffusion\nmodels. The introduction does mention several papers in this regard.\nOrganization can be made better.\n\nThe paper starting at Preliminaries is very dense. That said, the authors\nhave put effort to state the assumptions clearly and provided discussions\non differences between continuous and discrete diffusion models w.r.t. the\nvarious errors considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PyWL2xwd4J", "reviewer": "Reviewer_Se7m", "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.\nBy 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.", "questions": "see above Weaknesses section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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.\n2.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.\n3.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:\n1. 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? \n2. Could the authors provide runtime or memory complexity comparisons for τ-leaping versus uniformization under varying parameters?\n3. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PU5x84BCob", "reviewer": "Reviewer_5nb2", "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.", "questions": "How important is the request \"Q symmetric\" for assumptions 4.3--4.6?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hqKXXALwj8", "reviewer": "Reviewer_5uy7", "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.", "questions": "Please refer to the weakness part.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n2. Well-designed examples are presented for better illustration.\n\n3. 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.\n\n2. This paper is mathematic-heavy. Some insights, intuitions, or illustrations are suggested to provide for better comprehension.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)