Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis
Authors: Zikun Zhang
Zixiang Chen
Quanquan Gu
Venue: ICLR 2025 Poster (2025)
Keywords: Discrete diffusion model
Convergence analysis
Time-discretization
Discrete score function
Primary area: generative models

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

Published as a conference paper at ICLR 2025
CONVERGENCE OF SCORE-BASED DISCRETE DIFFU- SION MODELS: A DISCRETE-TIME ANALYSIS
Zikun Zhang
Zixiang Chen
School of Mathematical Sciences Fudan University
Department of Computer Science University of California, Los Angeles chenzx1 90 98cs. ucla a allla.dda edu
zk zkzhang21 @m. fudan. auudaneed... edu. en
Quanquan Gu
Department of Computer Science University of California, Los Angeles qgußcs uul a edu
ABSTRACT
Diffusion models have achieved great success in generating high-dimensional samples across various applications. While the theoretical guarantees for continuous-state diffusion models have been extensively studied, the convergence analysis of the discrete-state counterparts remains under-explored. In this paper. we study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete- time sampling algorithm in the general state space [s] that utilizes score estima- tors at predefined time points. We derive convergence bounds for the Kullback- Leibler (KL) divergence and total variation (TV) distance between the generated sample distribution and the data distribution, considering both scenarios with and without early stopping under reasonable assumptions. Notably, KL diver- gence bounds are nearly linear in the dimension d, aligning with state-of-the-arr results for diffusion models. Our convergence analysis employs Girsanov- method and establishes key properties of the discrete score function, which are essential for characterizing the discrete-time sampling process.
INTRODUCTION
Diffusion models (Sohi-Dickseii et al. 2015 Song & Ermon 2019 Ho et al.) 2020) have achieved
great empirical success in various generative tasks including audio (Kong et al. 202T] Schneider
2023}. video (Ho et al. 2022b Yang et al. 2023). and image (Batzolis et al. [021 Ho et al. 2022a) generation, and have demonstrated potential across a wide range domains like computer visions (Baranchuk al.) 2022 Whang et al., 2022 medical image reconstruction (Chung & Ye 2022
Cao et af.) 2024), , and bioinformatics (Trippe et al.] 2023 Guo et al.) 2024). The main goal of diffusion models is to generate novel samples from an unknown and unstructured data distribution. In general, the framework of score-based diffusion models consists of two stochastic processes: a predefined forward noising process that gradually corrupts data into some easy-to-sample noise distribution (e.g., standard Gaussian), and a reverse generative process generating new samples that almost obeys the real data distribution from the pure noise by learning the logarithmie gradient of the forward marginal distributions known as the (Stein) score.
Previous works on diffusion models primarily focus on continuous state spaces, particularly Fu- clidean space Rdd In this setting, studied by [Song et al. (2021b). the forward process can be constructed as continuous-time process characterized by a stochastic differential equation (SDE). The associated reverse process is also described by an SDE, which incorporates the drift and diffu- sion coefficients of the forward SDE along with the score function. Hence, an approximate reverse process be constructed by estimating the score functions, which is the core principle of the bcsre diffusion models. However, many problems require us to deal with discrete data, which
arise in fields like text generation (Austin al. 2021: Hoogeboom al. 2021
Li al. 2022

---

Published as a conference paper at ICLR 2025
Zheng et al.
) protein design (Gruver et al. 2024 Campbell et al. 2024). and segmentation
maps (Zbinden et al. 2023 Courdier et al. (024). Therefore, modeling probability distributions and constructing diffusion processes in discrete space is of great importance.
To tackle the discrete data, analogous to the state-of-the-ee art Denoising Diffusion Probabilistic Mod- els (DDPMs) (Ho et al. 2020) in continuous state space, (Asstn et al. (202T) proposed structured discrete diffusion models in discrete time, which was referred to as Discrete Denoising Diffusion Probabilistic Models (D3PMs). Campbell et al. (0022) introduced a continuous-time framework for discrete diffusion models, in which the forward noising process is formulated as CTMC. Similar to the continuous SDE setting, the reversal of a forward CTMC can be characterized by the for- ward rate matrix and the forward marginal probability ratios known as the discrete score function. Lou et al.] (2024) proposed methods for estimating the discrete score by minimizing discrete score matching objectives. Thus, we can refer to the discrete diffusion models by estimating the score function within the CTMC framework as the score-based discrete diffusion models. Interestingly, Benton et al. (2024b) demonstrated that score-based continuous space SDE diffusion and discrete space CTMC diffusion can be regarded as a more general unity, which well illustrates the many similarities between discrete and continuous diffusion.
In light of the significant empirical advances, extensive theoretical works for understanding the effi- ciency and acceleration of score-based diffusion models in the SDE framework (Chen et al. 2023b
Lee et al.] 2022] Yang & Wibisono| 2022 Chen et al. 2023a Benton et al. 2024a Li et al. 2023]
2024a Cheng et al.) 2024 Li al. 2024b] Chen al. 2024 Gupta et al. (024) have arisen.
Nevertheless, the theoretical foundation remains largely absent for discrete diffusion models, both
in discrete-time and continuous-time settings. The recent work[Chen & Ying (2024) first studied the
theory of score-based discrete diffusion models. This paper proposed a sampling algorithm in the hypercube setting {0, 1]a utilizing the uniformization technique of CTMC, proved its efficiency by deriving convergence bounds and sampling complexities, and applied the elementary properties of the discrete score function to promote the algorithm design. Inspired by these prior works, we study the theoretical analysis of based discrete diffusion models within the CTMC framework, as this framework allows us to leverage the score error and its properties in a manner similar to the convergence analysis of continuous diffusion models. The discrete-time sampling algorithm and analysis in our paper are closely related to the previous works on the theory of continuous diffusion models (Chen al. 2023b Benton al. 2024a b) and discrete diffusion models (Campbell et al., 2022
Chen & Ying 2024). Our contributions are summarized as follows.
1. Analogous to the exponential integrator (Zhang & Chen 2022 De Bortoli 2022 Yang & Wibisono 2022; Chen et al.] 2023a) within the SDE framework, which discretizes the true re- verse SDE, we propose discrete-time sampling algorithm for high-dimensional discrete diffu- sion tasks with theoretical guarantee within the CTMC framework. Under reasonable assump- tions, we derive convergence bounds for scenarios with and without early stopping. When the data distribution is balanced, the bound without early stopping is tighter than the bound with early stopping. Our main KI. divergence bounds for convergence consist of three components: score estimation error, discretization error, and truncation error due to insufficient mixing of the forward process, which are analogous to the typical convergence bounds found in continuous diffusion models (Chen et al. 2023a b Yang & Wibisono 2022 Benton et al. 2024a).
Technically, we use a Girsanov- method to analyze the proposed discrete-time sampling algorithm. We study the theoretical properties of discrete score functions such as the movement bound to facilitate our analysis. The discretization error terms in our main bounds are novel in the literature score-based discrete diffusion models. Also, we derive the exponential convergence of the forward process with uniform mixing in the general state space [s] Our KL divergence bounds are nearly linear in the dimension d. matching the best result for continuous diffusion models (Benton et al. 2024a) and discrete diffusion models (Chen & Ying 2024).
Notation. We use lowercase letters to denote scalars and boldface lowercase letters to represent vectors. All vectors are considered as column vectors. The i-th entry of a vector x is denoted by x', or simply zf when the context is clear. We use x to refer to all dimensions of x except the i-th, and x 1 @ a² to denote a vector whose i-th dimension takes the value á², while the other dimensions remain V_ For positive integer n, we denote [n]] the set 21, ......... n.. 1, RR as the vector of ones, and In E " as the identity matrix. The notation e; refers to a one-hot vector with a 1 in the i-th position. .(:-)) denotes the Kronecker delta, and 1(.) is the indicator function. The
2

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of convergence results for score-based discrete diffusion models with and without early stopping. The true reverse CTMC is discretized in our algorithm, leading to step size h in our bound. For early stopping, a terminal time of T' ô is used, where qs is a 8-uniform perturbation of the data distribution, and pr-ó is the law of output from the diffusion model after K steps with law of output from the diffusion model with time horizon I' after K iterations with 7 Kh. is score error, S' the size of discrete state space, C₁ depends on and ö, and C2 and x² depend on the properties of data distribution. To keep comparison consistent, present all bounds with e, though in Chen & Ying 2024) the actual bound is éT due to their time-averaged score error assumption.
hh. Without early stopping. qu = Pdata the data distribution, and pr the
Space
Time-discretized?
Early stopping?
Assumption
Convergence result
Reference
continuous
Chen Ying, 2024 Theurem
(0. 11
No
Yes
Dia.(uiller-a) de de +
bounded score estimator
Dxlaalerr 6) S, de 8++ 8 CAS 01894ATT Offe
[s
Yes
Yes
discretized score error
Theorem D This work)
continuous score error
Chen Ying 2024
(0, 1)*
No
No
bounded score estimator bounded score of Plats
Dxc(oullrr) $ de-P 4
Theorem
discretized bounded score of
Daa (pr) & do log O2S213 Cße
[s]e
Yes
No
Theorem 2 This work)
Hamming distance between two vectors x and is denoted by Ham(x, y) = E, 1f22 y'). We adopt f S g to mean that there is a universal constant C 0 such that f < Cg. Additionally, we denote the generalized I-divergence (Amari 2012) as D = E,(='' + + x' log((') /v²)), which is the Bregman divergence with respect to the negative entropy function (xx) = E, x² log x².
RELATED WORK
Discrete Diffusion Models. The diffusion model was first introduced by SSoh--Dickstein et al. (205)). Many previous works construct discrete diffusion processes as discrete-time Markov chains, and thus train and sample the model discrete time (Austin et al.) 202T Chen al., 2024c). In par- ticular, D3PM (Austin et al.) (021) and the Discrete -ar-Morkov Diffusion Model (DNDM) (Chen cct al. 2024c) serve as the discrete diffusion counterparts to DDPM (Ho et al. 2020) and Denoising Diffusion Implicit Model (DDIM) (Song et al. 202 in continuous diffusion, respectively. These works offer various practical sampling algorithms but lack theoretical guarantees. Given the limi- tations and inflexibility of the discrete-time formulation, Comulation,,Campbell et al. (2022) proposed CTMC framework for discrete diffusion models, which offers much greater flexibility in defining the reverse sampling scheme. Due to the particular nature of the discrete space, this paper sensibly proposed to assume the factorization of the forward process for high-dimensional tasks, a strategy that has been widely adopted, and introduced a tau-lcaping method to simulate the continuous-ting reverse process. Lou et al. (2024) provided a practical sampling algorithm using Euler discretization and the discrete Tweedie's theorem.
Inspiringly, the CTMC framework for discrete diffusion models makes estimating the discrete score function important for simulating the reverse process. Meng et al. (2022) proposed concrete score matching objective, but the 1,2 distance there cannot fully capture the characteristics of the score and is thus unsatisfactory. [Sun et al. (202) derived the score matching objective from the marginal probabilities of each dimension with maximum likelihood training. Lou et al. (2024) proposed score entropy losses by deriving the KL divergence path measure between the true and approximate reverse processes, which are analogous the score matching objectives in continuous diffusion models (Hyvärinen & Dayan| 2005 Vincent 2011). Benton et al. (2024b) provided a general framework for these score matching objectives in both discrete and continuous spaces.
Convergence Analysis of Discrete Diffuusio Models. There is a lack of convergence analysis of discrete diffusion models in the existing literature. Campbell et al. (022) derived error bound
3

---

Published as a conference paper at ICLR 2025
for the tau-leaping sampling algorithm with TV distance metric, under strong assumptions such as bounded forward probability ratios and L error for the approximate rate matrix, since the forward process can be quite general. The error bound grows at least quadratically in the dimension d. Chen & Ying (2024) first introduced a sampling algorithm for score- discrete diffusion models that exactly simulates the reverse process through the uniformization of CTMC in the hypercube set- ting with independent flips as the forward process. They also provided corresponding convergence bounds and algorithm complexities that are nearly linear in the dimension d, matching the best result achieved for continuous diffusion models (Benton et al. 2024a). The results of & Ying (2024) and ours are summarized in Table
BACKGROUNDS ON SCORE-BASED DISCRETE DIFFUSION MODEL
We will be handling discrete data 2g X [M] A probability distribution on X' can be represented by a probability mass vector E RR,, where the entries of p are non-negative and sum to 1. Assume that z0 PPlata for some discrete data distribution Pdata- The forward noising process is defined as a CTMC on X, evolving from / = 0 to / = T, with a rate matrix (or generator matrix) Q₁ E TR- X and an initial distribution go Rate matrix Qr defines the infinitesimal transition probability for the continuous-timg process between the two time points and t + At:
(++as)+()22)) = 6( y) + Qi v) + o(At),
where Qr(2, y) is the (ar, v) element of the rate matrix Qt and aet (y/zr denotes the infinitesimal transition probability of being in state y at time ( + Al given state x at time From we know
Qx v) 2 0 for x + v. Qc(z,z) x) S 0, and Qr(2,z)
Σ (z
ufr
Moreover, the forward marginal distribution a satisfies Kolmogorov forward equation (see, e.g., Campbell et al. (2022): Chewi (023)) ):
dg:
Q. g: 9o Pdltt
dt
Generally, Qe is chosen as a simple matrix such that the forward process mixes quickly towards noise distribution Pref which is easy sample. For example, if setting 3()) time-dependent scalar, the uniform rate matrix Q = ((t) - N- IN) results in Pret = } 1N. the uniform distribution on X; Q B(t)(1x eMASK- IN) yields Pref eMASK. the one-hot probability encoding of the MASK absorbing state (Austin et al. 2021 Campbell et al. 2022 Lou et al. 2024).
Notably, the forward process has an exact time reversal (Kelly) 2011 is also a CTMC that evolves from = 0 to = with rate matrix Qi given by
Campbell et al. 2022 which
Q (ar, v) = Qr Qu- QT (v)
for x + v. and Q (f,a))=- QF
96 (x))())
Therefore, we know that the access to probability ratio 9:(2) is important to simulate the reversal. (z)
Specifically, the collective ratios (z) ==
(g(())
N-N are known as the discrete score
(x(x))
function (Meng et al. 2022). which generalizes the Stein score function V, log (ar) (Song & Er- mon 2019) in the continuous setting. As pointed out by previous works concerning score matching in discrete space (Lou et al. 2024. [Benton et al. 2024b). we learn discrete score estimator & to St
for E [0, 7] by minimizing the score entropy
L" Exe-g:
CSE(S) =
D(( dt.
Note that the score entropy loss characterized by the Bregman divergence, different from the L distance loss in the continuous counterpart. We defer the details on the Bregman divergence to
Appendix E The score entropy is exactly the path measure KL divergence (Lou et al., 2024| Chen & Ying 2024 Benton et al. 2024bb. Although the score entropy can not be directly estimated, there are equivalent objectives such as implicit score entropy and denoising score entropy (Lou et al.
2024 Benton et al. 2024b) which can be optimized practically.
4

---

Published as a conference paper at ICLR 2025
4 PROBLEM SETTING
In practice, the discrete state space typically factorizes as X = [S] representing sequences x = x1a .'. (e.g., token sequences (Lou et al. 2024 image pixel values (Campbell al. 2022). or protein sequences (Campbell et al. 2024)).
Forward Process. The forward process X (Xt):20 is defined by CTMC X with rate matrix Qt starting from Xo ~ Qo Pdata which is the data distribution. Let == Law(X;), which follows the Kolmogorov forward equation
As general Qs R would be of exponential size, we assume that the forward process can be factorized such that each dimen- sion propagates independently with rate Qtok IRSxS Namely, the forward transition ker- nel Gtjs (x:( = PXX, = Xx Xx = xx) factorizes as (x(x(x) = II Ti. (x]la²)) where 2/j. (1(lor)) P(X; x xrt)) is the transition probability for the i-th dimensional CTMC
X" = (X)) with forward rate Qtok. This is common assumption in literature considering high dimension tasks in the CTMC setting (Campbell et al. [2022] Lou al. [024] Campbell al. 2024]
Chen & Ying 2024). According to Campbell et al. (2022, Proposition 3). the non-zero off-diagonal
entries of Q: are given by
Q1(x, O +00 = Qa ....''......
Qi (x* .²)
for x X' and x² + E' [S]. We see that the non-zero off-diagonal entries Q: can only oceur between sequences with Hamming distance of 1, leading rather sparse structure. As for the perturbation each dimension, we take the homogeoooge uniform rate
1 = 11s1 -s.
Q. = Qlok
This rate matrix is common in applications (Austin al. 2021 Campbell et al. 2022 Lou et al.
2024 Campbell et al. 2024). and also analyzed by Chen Ying 2024) where 2 is taken. Then Q: is of the form
Ham 5 1)d, x
Q(x,y)
0,
otherwise.
We can then obtain the expression of forward transition probabilities and marginals as stated in the following proposition, showing that the marginal converges uniform distribution X' [S] which we denote 7d as increases. The proof of Proposition is deferred to Appendix A.1
Proposition 1. Let P SxS be the transition probability matrix of the i-th dimensional forward CTMC X from time 8 to time I, iee, Ps,( y) 4%jo (vlx)) for all x, y E [S] and E [d]. Then for all i E [d], Pi = Po, where
p0 a.1 5 (1- 111 te -t-
Let Ps,t @RS be the transition probability matrix of the forward process from time s to time for > ie., Px)(x,y) (x x) for all x, E X, then
(Po) 3d
Pa
where (-)8d denotes performing the matrix Kronecker product d times. In particular, the marginal distribution the forward process at time can be expressed
[ -1 +
od
4:
Pdatas
and when +00, qi approaches the uniform distribution nd.
Reverse Process and Score Model. Suppose that the forward process until time T 0, ending at 9r. We can convert the noise back into samples if we reverse the forward CTMC dynamic X in time. According to Campbell et al. (2022) Proposition 3), the reverse process Y (Yt)eeo,.)

---

Published as a conference paper at ICLR 2025
can be achieved by CTMC starting from Yo Qr with Law(Yi) = Law Law(Xr-1) 9r -t, and the
reverse rate Q E TR55x xs* is of the form
(x-
Qi (x,
Σ or (x 1x(x)
(3)
(T-+(x)
From (3) we know that the non-zero off-diagonal entries of Q; can only occur between sequences with Hamming distance of 1. Therefore, care about the forward marginal ratios between these sequences and denote the collective ratios St X + pd( defined by
8t (x),, == 2e 2x
@ it)
for X E, ie E [d], x² # E (S).
qi
Then the sparse structure of Q can be expressed as
o (x, / o  Q and the reverse marginal or- satisfies the Kolmogorov equation
bok (+* ( (x) = $ (
for i [d], x' + 4 E [S],
d Qi TiTTTTT 9r-1-
dt
However, in practice, we do not have access to qr, the initial distribution of the reverse process, so we start the reverse process at the noise =², the target distribution of the forward process, and simulate with score estimators. The score estimator 8, X pd(S-1) that estimates 8, for I E [0, T] is learned by minimizing the score entropy loss
(SE(S) = S'' Exing Σ
d
Σ
(xx) dt Qe(x)
i=1 =i
1 T S
/ Bxing (x(ss(x)))(((xx
(5)
Algorithm. Since the reverse process is iime-inhomoeencous, we can discretize the time simulate it. Let h > () be the step size, and T be the time horizon. We consider applying early stopping with a terminal time of T 8, because the score function can blow up as
for data distributions without full support on X. As shown in Section 5 early stopping can be removed when Paata has full support on X. The time horizon set to T = Kh + ō, where 2 is a small value and E N is assumed. Suppose we have access to the score estimators -T for k = 0,1 K 1. We then construct a continuous time sampling process = (Z, (Z))reoo.T- starting from Zo ~ x and let Pt = Law (Zz). For & [kh, (k- 1)h), by freezing the value of the rate matrix in the ODEs (4) at time kh and replacing the true score with the score estimator, (Ze)te (k++k) [h] is constructed
as a hime-homogeneous CTMC with rate matrix Q E S where the non-zero off-diagonal entries of Qt, are given by
(x, x o 8²) 8 for [d], x² + 5 E [8].
Hence, in each step from time kh to (k 1)h, the distribution follows the Kolmogorov equation d
Pkb I/AA (xxn+1 (xs) = QE. PhΛ++ an (Xsh+e|xkR)
h].
(6)
dt
For A: = 0, 1.1.... K 1, theoretically we update the solution of the ODEs (6) as
26+1 ~ exp (1QTTT (ex) @ ... 2 ezy), Zo ~ T
After K iterations, we get a sample zς with law Pr-5- Unlike the exponential integrator in the continuous setting, where the closed-form solution for the iteration formula of sampling random variables can be obtained by solving the linear discretized SDE within each time interval, the dis- crete setting requires deriving the categorical probability from the Kolmogorov equation and then sampling from this distribution. In practice for sampling, can run 7 with Poisson point process utilizing the uniformization of CTMC (Chen Ying 2024) instead exactly calculating the matrix exponential exp(hQ, 7) which is intractable for reasonably sized S and d. For completeness, we formalize the practical sampling procedure in Algorithm presented in Appendix D

---

Published as a conference paper at ICLR 2025
5
MAIN RESULTS
Our main results are the convergence analyses for the theoretical iterative algorithm 7 We use an analogous Girsanov-based method in the continuous SDE settings (Chen et al., 2023a Benton et al. 2024a) by bounding the KL divergence between the path measures of the true reverse process and the sampling process.
The score estimation error measures the quality of the learned score estimator. Since we discretize the true reverse CTMC in our algorithm, we make the following score error assumption. Assumption (Score estimation error). The score estimator satisfies
K-1
(k+1))++
1
Excag Dr(s((+))++s(xx))) ((4T)))))))))))))))))() dt S Escore
5
k= kh+6
Assumption 1 which we introduce for the first time, can be viewed as time-discretization of the score entropy loss (5) establishing a discretized version of score error assumptions for our CTMC framework. This assumption is analogous to those widely used in diffusion models (Lee al. 2022 Chen et al. 2023a Li et al., 2023 2024a b Benton et al. 2024a; Chen & Ying 2024), but with two key distinctions. First, we use Bregman distance instead of the L distance, aligning with
the discrete nature of the CTMC framework. Second, in contrast to Chen & Ying (2024), we only require a small error over pre-defined discretization points, rather than a continuous error bound.
Theorem 1. Suppose Assumption I holds. By choosing small 8 = Ö(S 3) > 0, the KL diver- gence between qs and -8 is bounded by
DK (lrssllpr6))))))) E de -T log + 8 C, S h C2 + Cf cfccooe
(8)
where C1 = max {1 {1+ 5 5.
K (1((++1)+++ and the TV distance between
Paata and pr-6 bounded by
(Piata s) S dde Tlo S +
+ 8 + C,Sh + Cfesore + (1-e d5(S-1)/S).
The proof of Theorem I is deferred to Appendix A.3 We interpret the KL divergence bound (8) as follows. The first term de log S arises from the initialization error of the algorithm. Recall that the true reverse process should begin from ęr, but the algorithm starts from the noise xd The second term 8
2 reflects the discretization error, which scales with the step size and is linear in d, vanishing h - 0. The third term CfEscore corresponds to the score estimation error, which is non-vanishing We remark that the appearance of the quantity C1 in the bound (8), which is absent in the continuous SDE counterpart, stems from the lack of the triangle inequality for the Bregman divergence. Specifically, C1 is the uniform bound of the involved score and score estimators (see Lemma 2 in Appendix for details). As discussed in Appendix [A.4 if applying the score clipping technique, we can ensure that C₁ S S/8. The nearly linear dependence on d of the KL bound (8) matches the best result for the continuous diffusion model (Benton et al.) 2024a).
The last term in (9) provides an upper bound on the TV distance between Pdata and ga- There is trade-off involving d in this bound: to reduce Drv (s), we opt for a rather small 8 O, especially when d is large. However, this causes the square root term to grow rapidly, at a rate of 5-2 As a result, the square root term dominates the bound, leading us to focus on the KL divergence bound 8 for a small 8.
The data distribution characteristics are closely related to the properties of the score function when >>> 0 is small. We perform early stopping because the score of the data distribution can be positive infinity for some data points with a probability of zero. However, if the score of Paata uniformly bounded, early stopping is no longer necessary.
Assumption 2. depending on S but not on such that for all x E X, E [d], and x & 4¹ e [8).
The data distribution Pasta has full support on X, and there exists uniform L > 0
Pdata(x') ② 2
so so(x)i.
< L.
Pdata (x)
7

---

Published as a conference paper at ICLR 2025
Assumption 2 holds in many cases, e.g., when the data distribution is the product of i..d. com- ponents. each with a marginal distribution fully supported on [S]. It is similar to Assumption 3 in Chen & Ying (2024), both aimed to remove early stopping. Our Assumption 2 is stronger since assume that 7. does not depend on d. Camphell et al. (022) also applied similar assumptions, as presented in Assumptions and 2 in their paper. As they noted, the uniform boundness for the data distribution follows trivially from the strict positiveness of Pdata if we allow L to depend on d. We adopt the assumption from Campbell et al. (2022), which enables us to derive bound that can be nearly linear in d, as stated in the following theorem.
Theorem 2. Suppose Assumptions
[ and 2 hold. Let ô = Denote Paata I as the marginal (pista Jmax for i E [d] and n² Ei= R2t distribution of the i-th dimension of the data, and let Ki: (assaamin then it holds that
DKL. (paatallPT)) S de de- log S C2 S2 + C2 Escores
(10)
where C2 = max (L, maxxe,
1) || (()+1)(())ll))
The proof of Theorem 2 is deferred to Appendix A.4, K; is well-defined since the strict positiveness Aateppsiiiiaall of Pdata in Assumption ensures the strict positiveness of marginal distribution Plata- In the bound (TO), the term 52 is the discretization error, where x² and C2 related the property of the data distribution. Specifically, x² is characterized by the ratio of the largest to the smallest entry in the marginal data distribution, and large value of x² indicates that the probability values for certain data points are either very high or very low. x² is nearly linear in d and equals d when Pdata is uniform distribution. When Pdata is relatively balanced, meaning that the probabilities across data points are fairly similar, x² x²/d and C2 are reasonably small, and thus the bound (TO) is tighter than (8) as it eliminates the term involving 8 The quantity C2 arises similarly to C1, and applying score clipping can make C2 S L as shown in Appendix A.4 where L is proven to be the uniform bound of the score along the forward process.
With the early stopping criterion, Theorem 1 results in the following iteration complexity.
Corollary 1. Suppose Assumption 7 holds. By choosing small ó = (OS-0SS2200 2/3) > 0, for any e >> 0,
{o 8 (caSee)
1/3
1/2)
if choosing T x log [dlog and h x min
(cLESH))
then the discrete diffu-
S.
sion model requires at most Ô maxx { (C.Sed) 1/3
(Crsed) 1/2)
)
steps to reach a distribution
Pr-6 with DKL. (gs (PT 8) = Ö(e + Cftscore).
By Corollary
I to have DKL (s) = Ö(e), it suffices to choose Escore = (e)(C)) Similarly,
Theorem leads to the following iteration complexity without early stopping.
Corollary 2. Suppose Assumptions
1 and 2 hold. Let d = O. For any e > 0. if choosing T x
GLSEZ. then the discrete diffusion model requires at most è (V CaSpee
log
dloog
s and
steps to reach a distribution pr with DKL (passallpr) < Ō(E+ + C2ecore).
By Corollary 2 to have DKL (Paatallpr = Ō(e), it suffices to have (score = Oc//C2).
Comparison with Chen & Ying (0224). Both Chen & Ying 2024 and our paper utilize uniform rate matrix for its structural simplicity. [Chen & Ying (2024) applied the uniformization technique of CTMC develop a sampling algorithm for discrete diffusion models, enabling the exact simulation of approximate reverse CTMC dynamics. In contrast, our algorithm discretizes the time to simulate the reverse process and calls the score estimator at fixed discretization points (kh + 6 ke[[]] instead of at randomly sampled times, introducing an additional discretization error term in our bounds. As - 0. our sampling procedure covers the exact simulation, at which point our bound (8) degrades to the bound in terms of score error and the mixing of the forward noising process. See Table for a comparison of the quantitative KL divergence bounds. Moreover, although we do not explicilly make additional assumptions on the score estimator, we note that the score clipping approach dis- cussed in Appendices A.4 and D aligns with Assumption 2 in Chen & Ying 2024), which assumes bounded score estimator to implement their sampling algorithm. Furthermore, our convergence analysis is conducted in the more general [S]d setting, as opposed to the (0. 1)dd hypercube frame- work used in their work, making our state space setting and algorithm more broadly applicable.
8

---

Published as a conference paper at ICLR 2025
SKh+8
Truc Reverse Process
Y (gu)
Yy- (9))
Yy-oh-a (Gor-e)
Yo (97)
xf (9
S
8gi+5
True Sampling Process
Tx-o (Pr-a)
Z 5 (Pr-sh-e)
(pt)
86
8kh+5
Analyzed Sampling Process
7
7--
7o (gr)
Illustration of the processes Y. Z and Ż. the true reverse process, Z is the sampling process starting from the noise n", and Ž is the same as except for the initialization. Both and Z start from Ør. The random variables (e.g., Y,, Ze) are shown with their corresponding probability laws in parentheses (e.g.. Pt)
Figure I:
OVERVIEW OF KEY PROOF TECHNIQUES
We present key proof techniques for the main results given in Section [|] which characterize the discrete-time sampling process in the discrete diffusion model. Theorems andd] provide bounds for both the KL divergence and the TV distance. In this section, we focus on proving the KL bound (8), as the TV distance bound 9 follows from this KL bound via Pinsker's inequality, plus the additional term (1 ---(-- 1)/S). The proof of the KI. bound
TO follows similarly.
Let Q the path measure of the reverse process Y = (Y+) starting from Yo ~ gr, and pr* be the path measure of the sampling process Z = (Zi)<e(0,T-)) starting from Zo ~ nd. Recall that q: Law((r--) and Pt Law(Zz). Additionally, let the process Ž (Zi)ce(o,T-a) be the same as except for its initialization yr, and per be the path measure Ż. We visualize these three processes in Figure [ Then by the data processing inequality and the chain rule of KL divergence, we have
(gs DKL(Q) = DKL(erlTT)) + DKL (K((((
(11)
Therefore, suffices to bound the two KI. divergence terms
Forward Process with General S States. The term DKL (gr (( represents the prior loss due to the initial distribution mismatch between @r and πd. This can be bounded using the convergence properties of the forward process. [ shows that the forward process qr converges to x as T + CC. We now characterize this convergence rate for general S states.
Proposition 2. For the forward process marginal targeting the uniform distribution d we have
(xi(aell=*) e (Paaaaaas m ed S.
The proof of Proposition is deferred Appendix A.2
Proposition 2 demonssratesss that the forward
marginal converges exponentially to the uniform distribution ud. Since DRL, (Pdttal I can be upper bounded by log S, which is the maximum possible KL divergence between any discrete distribution and the uniform distribution over states in dimensions, this result holds irrespective
of the complexity of the data distribution Pdata-
Girsanov-Bare -Baed Method. The term DKL (Q]( is the discretization eπror that calculates the path measure KL divergence between the true reverse process and discretized reverse sampling process. We employ Girsanov's theorem to explicitly express the discretization error as follows (detailed in Lemma T Appendix)
K K-1
(k+1)448
1
DKL(Q|
dé,
S
k=0
kh+5
where (x) (1) (xx)) ) is the Bregman divergence characterizing the distance between s; and 1(++1)445 for E [kh 8, (k 1)h 6). Since Assumption [ is made the discrete points

---

Published as a conference paper at ICLR 2025
{kh + kE][K] further decompose the Bregman divergence into two parts:
K
(K+1)488
PRL
2
E x (1x)()))))))))))))){{))))) 1(++1)++6 (x:))
S
k=0
kh46
Score Movement
C7
K-1
(k+1)
Ex D (1( 1a (xx)) dt,
(12)
S
k=0 kh+5
Score Error
where the inequality holds due to the boundness of score and the property of Bregman divergence (detailed in Lemma 2 and Proposition] in Appendix). The score movement term in (12 represents
the squared norm of the score difference (x)x))((++1)++) (x))))++xxx))1 over the time interval khh+ (k++
1)h + 8). and the score error term in [12 is naturally bounded by Ea due to Assumption |
Score Movement Bound. We derive the score movement bound to quantify the change in the score function over time (detailed in Lemma 3 in Appendix). For all k E {0,1, KK 1},
t te [kh + 6, (k + 1)h 5], and x, E N, we establish the following inequality:
e (kb-55
S chh
[11s((xx)) (0+1))+0(xx)13
+1
dsa
(1 (kh+5)y2
which leads to the score movement term in 12 being bounded by c= C hPT (detailed in Lemma 2 and the proof of Theorem Appendix), vanishing approaches zero
In summary, we established proof techniques for bounding [T]. We demonstrated exponential convergence of the forward process to the uniform distribution, bounding the prior loss term. The Girsanov- method was employed to analyze the discretization error, decomposing it into score movement and score eгrоr components. The derived score movement bound revealed dependencies on step size h, dimension d, and state space size S. Collectively, these techniques provide a final bound on DEL. ( offering a rigorous framework for analyzing discrete diffusion models under various parameter regimes.
7 CONCLUSION AND FUTURE WORK
We introduce a discrete-time sampling algorithm for the high-dimensional score-based discrete diffusion models within the CTMC framework and corresponding convergence analyses using Girsanov-based method, similar to that the continuous SDE setting. We study the properties of the discrete score function and incorporate them into our discretization error analysis. The conver- gence bounds for the sampling algorithm are nearly linear in the dimension d, both with and without early stopping. The bound without early stopping is related to the property of the data distribution.
The primary limitation of this work is that the discretization error the convergence bounds of the proposed sampling algorithm becomes significant when ő is sufficiently small when the data distribution contains extreme probability values. Hence, future work can be focused on developing refined techniques to treat the discretization eтror. Another important future direction will be devel- oping accelerated algorithms with theoretical guarantees for score-based discrete diffusion models and applying method to some more general rate matrices obtain tight convergence bounds.
ACKNOWLEDGEMENTS
We thank the anonymous reviewers and area chair for their helpful comments. ZC and QG are sup- ported in part by the NSF grant IIS 2008981 and Sloan Research Fellowship. ZC is also supported by UCLA Dissertation Year Fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Shun-ichi Amari.
onfferential-eommetiiee methods in statistics, volume 28. Business Media, 2012.
Springer Science &
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 Systems, 1es11998-179999 2021.
Dmitry Baranchuk, Andrey Voynov, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Label- efficient semantic segmentation with diffusion models. In International Conference on Learning Representations, 2022.
Georgios Batzolis, Jan Stanczuk, Garola-Bibians Schönlieb, and Christian Etmann. Conditional image generation with score-based diffusion models. arXiv preprint 0rXiv:2111.13600 2021.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear con- vergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024a.
Joe Benton, Yuyang Shi, Valentin De Bortoli, George Deligiannidis, and Amaud Doucet. From denoising diffusions to denoising markov models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(2):286-30, 2024b.
Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19:289-336 2006.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford University Press, Oxford, UK February 2013.
Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. Advances Neural Information Processing Systems, 35:28266-2888 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. In Forty-first International Conference on Machine Learning, 2024.
Chentao Cao, Zhuo-Xu Cui, Yue Wang, Shaonan Liu, Taijin Chen, Hairong Zheng, Dong Liang, and Yanjie Zhu. feghffrey space diffusion model for accelerated mri. IEEE Transactions on Medical Imaging, 2024.
Haoxuan Chen, Yinuo Ren, Lexing Ying, and Grant M Rotskoff. Accelerating diffusion models with parallel sampling: Inference at sub-linear time complexity. arXiv preprint arXiv:2405. 15986, 2024a.
Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffuusion model: Exact imple- mentation through uniformization. arXiv preprint 20Xiv:2402.08095,.00 2024.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pp. 7733. PMLR, 2023a.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li. Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference Learning Representations, 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, 2024b.
Zixiang Chen, Huizhuo Yuan, Yongqian Li. Yiwen Kou, Junkai Zhang, and Quanquan Gu. Fast sampling via discrete non-markov diffusion models with predetermined transition time. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024c.

---

Published as a conference paper at ICLR 2025
Xiuyuan Cheng, Jianfeng Lu, Yixin Tan, and Yao Xie. Convergence of flow-based generative models via proximal gradient descent in wasserstein space. IEEE Transactions on Information Theory, 2024.
Sinho Chewi. Log-concave sampling, 2023. Book draft available https:://cewiiinhoo github. io.
Hyungjin Chung and Jong Chul Ye. Score-based diffusion models for accelerated mri. Medical Image Analysis, 80: 102479, 2022.
Evann Courdier, Angelos Katharopoulos, and François Fleuret. Segmenting the unknown: Discrete
diffusion models for non non-dttemiinistic segmentation, 2024. URL hattps::/openzevier
net/ d d= 4XeFOAY
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022.
Rui Dong. Feller processes and semigroups, 2003.
URL https: hestps::/www.ee www.wwtw....ttttttttt.ttttwtwwtt stat www.:ssttt..erlleeee.. berkeley.. Lecture notes, UC Berkeley.
hedp:/potccaa///25550//eeetttt2 pdf
Nate Gruver, Samuel Stanton, Nathan Frey, Tim GJ Rudner, Isidro Hotzel, Julien Lafrance- Vanasse, Arvind Rajpal, Kyunghyun Cho, and Andrew G Wilson. Protein design with guided discrete diffusion. Advances in Neural Information Processing Systems, 36, 2024.
Zhiye Guo, Jian Liu, Yanli Wang, Mengrui Chen, Duolin Wang. Dong Xu, and Jianlin Cheng. Diffusion models in bioinformatics and computational biology. Nature reviews bioengineering, (2):136-154, 2024.
Shivam Gupta, Linda Cai, and Sitan Chen. Faster Iittusion-basedd sampling with randomized mid- points: Sequential and parallel. arXiv preprint arXiv:2406. 00924,, 2024.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 6851, 2020.
Jonathan Ho, Chitwan Saharia, William Chan, David Fleet, Mohammad Norouzi, and Tim Sali- mans. Cascaded diffusion models for high fidelity image generation. Journal of Machine Learning Research, 23(4)) 2022a.
Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet. Video diffusion models. Advances Neural Information Processing Systems, 35:8633- 8646, 2022b.
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 2021.
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score match- ing. Journal of Machine Learning Research, 6(4), 2005.
Frank P Kelly. Reversibility and Stochastic Networks. Cambridge University Press, 2011.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference Learning Representationss 2021.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 15:22870-22882 2022.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejic Chi. Towards faster non-asymptotic convergence for diffusion-based generative models. arXiv preprint arXiv:2306.092. 2023.
Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejie Chi, and Yuxin Chen. Accelerating vergence of scsre-based diffusion models, provably. In Forty-first International Conference on Machine Learning, 2024a.
12

---

Published as a conference paper at ICLR 2025
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprint arXiv:2408.023200 2024b.
Xiang Li, John Thickstun, Ishaan Guirajani, Percy S Liang, and Tatsunori B Hashimoto. Diffusion- Im improves controllable text generation. Advances in Neural Information Processing Systems, 35:4328-4343, 2022.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. In International Conference on Machine Learning. 2024.
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.
Flavio Schneider. Archisound: Audio generation with diffusion. arXiv preprint arXiv:2301.13267, 2023.
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.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Interna- tional Conference on Learning Representations, 2021a.
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 P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021b.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous-time discrete diffusion models. In The Eleventh International Conference on Learning Representa- fions, 2023.
Brian Trippe, Jason Yim, Doug Tischer, David Baker, Tamara Broderick, Regina Barzilay, and Tommi S Jaakkola. Diffusion probabilistic modeling of protein backbones in 3d for the motif- scaffolding problem. The Eleventh International Conference on Learning Representations, 2023.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural Compu- tation, 23(7).1661-167, 2011.
Jay Whang, Mauricio Delbracio, Hossein Talebi, Chitwan Saharia, Alexandros G Dimakis, and Pey- man Milanfar. Deblurring via stochastic refinement. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16293-16303, 2022.
Kaylee Yingxi Yang and Andre Wibisono. Convergence of the inexact langevin algorithm and score- based generative models in divergence. arXiv preprint arXiv:2211.0151/ 2022.
Ruihan Yang, Prakhar Srivastava, and Stephan Mandt. Diffusion probabilistic modeling for video
generation. Entropy, 14619)1146, 2023.
Lukas Zbinden, Lars Doorenbos, Theodoros Pissas, Adrian Thomas Huber, Raphael Sznitman, and Pablo Márquez-Neila. Stochastic segmentation with conditional categorical diffusion models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1119-1129, 2023.
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. In NeurIPS 2022 Workshop on Score-Based Methods, 2022.
Lin Zheng, Jianbo Yuan, Lei Yu, and Lingpeng Kong. A reparameterized discrete diffusion model for text generation. arXiv preprint orXiv:2302.05733, 2023.
13

---

Published as a conference paper at ICLR 2025
A MAIN PROOFS
A.1 PROOF OF PROPOSITION
Proof of Proposition Consider the Kolmogorov forward equation
& pi P Q we obtain 8t
that P., exp ((t $ Qtok) for the CTMC X Let Qrok = PAP- be the eigendeconposition of Qtok with
S --1
0
0
1
1
1 P
1
P =
-1
-1
$
--1
-1
-1
S-1
1
1
1
and A diag (1,,.. -1,00. Then it can be easily verified that
pu a. = exp ((t - x) = Pexp ((1 8)A) p- = S [1 (1-e-(t-)))1
1
1sl + Se (e--e--aa (t-8) 15)
Also, the Kolmogorov forward equation 0 pa, = Ps yields p.,: exp((t s)Q). Furthermore, note that Q has Kronecker tronecckr-producct structure
d
Q
+ 1=1
Q
tok
@k--1)
@ tok 1 @dd-k)
where (i denotes the Kronecker sum, and this structure can be verified by direct calculation:
+ A=1
lok
(x, (x,x11 o 8²)
s(k-1) 2 grok
2 1
(((d))) k) (x, x), o s²)
g (i)-)
Qua @ 1 (dd-1)
(x, @ 2t)
II
Is (x. x²) (z)
3/1
and
Qtok
(x,x)
1s
3(k-1)
2 Q
x 1s k) (x,x)
k=
k=1
Σ
II
Is (x) x²)) Qiok
k= 1=
Σ
1 - xx(xxxxxx
Q(x,x)
for all x E X,, i E [d]. and x² + E [S]. Then
d D k=1
(t-ttQQtot (exp ((t ))Q(o)) ood = =(p0) 0d
P.. = exx=(((((ts)))) -
= exp
Thus, by the Kolmogorov forward equation
de TT a: have
3d
a: exp(()( Pdata = (exp (1Q)oo)) ad
Pdata (1- e
Pdata
As +00, 9t [1 sod
Pdata 5 I gal 1
Pdata 3/2 1g d
14

---

Published as a conference paper at ICLR 2025
A.2 PROOF OF PROPOSITION 2
For the first inequality, we prove that the forward CTMC with generator matrix Q and stationary distribution x" satisfies modified log-Sobolev inequality (MLSI) with constant CL.S 2:
Proof of Proposition 2
CLSI fo for all function f - R+. 2
Ent
[
(13)
where the entropy
Ent [f] = E If log fl E log( ( [/]) for function f: + R4, and the associated Dirichlet form is
E(f.g) - - f(x) Σ Q(x (x)
yEX
1
Σ (f(x)
f(y))(((x) - (xx)))((xx))7()))
2
x.yεX'
for two functions fig: + R. With the sparse structure of Q, we can further write out that
Els, f)
E ExNTT
Σ Σ(((x) f(x) o a' (log) f(x) log f(x V о E'))
25
for some function X R. We now use the subadditivity of entropy and tensorization property of log-Sobolev constants to prove (13), and we will see that it is sufficient to show that the CTMC on [$] with generator matrix Qrok and stationary distribution
1/2 1g satisfies MLSI with constant CL.st = 2. First, Boucheron et al. (2013 Theorem 4.10) implies the subadditivity of entropy that
Ent [f] Exlinre
Ent (0) [f],
where [5) W. Egww Iflog Pa [f] log Rx [.] Hence, suffices to show that for all i E [d].
CLSI Egg
s Σ ( S(xV (lo) s(x) log f(x @ t*)).
Emt (1)
[ʃ]
(14)
#1=1
Given any fixed realization of x f(x) can take different values with equal probability J. and call these values 01, , 0. Then the desired inequality (14 is of the form
S log a;
Σ a s
log
CLSI 4
Σ (a. (aa-a,)le a;) a; loga,).
Thus, it remains to prove that this elementary inequality holds for all a..... as 0, which can be easily verified by plugging CL.tT = 2 and the concavity logarithmic function.
To conclude, the MLSI [13 implies the exponential mixing of the forward process in KL divergence
(see, e.g., Bobkov & Tetali (2066] Theorem 2.4). Chewi 2023 Theorem 1.2.25)):
(- (-Cust
2t
(xi. S exp
(ptaa ( e - ''DI.. (DIit(aattall*
CL.s
The second inequality is because
DELL (pdata ) = Σ
(x) log
Pdata(x) S-d
Σ
Paata log (x)ta(x) + dlog S S d d S.
XEX
XEX
15

---

Published as a conference paper at ICLR 2025
A.3 PROOF OF THEOREM 1
To prove Theorem D we state the following lemmas. Their proofs are provided in Appendix B
Lemma The KL divergence between the true and approximate path measures of the reverse process both starting from 9r is
K-1 Σ k=0
(k+1))+6
DKL. PQI((QIPPTT)
E
(oa dt.
kh+6
Lemma iss the key lemma to our analysis, allowing us to explicitly express the path measure KL divergence. Lemma 2 (Score bound). Let 8 > O. For all t E 16, x E X, i [d] and i' + xt E (S), we have
S
S
8x(x) S +1+
S +
et
5 -
Lemma 3 (Score movement bound). For all le E (0,1, K - 11. L E [kh + 6, (k. + 1)h + 8). X and X' * x² [S). we have
e- (Mh+8)
(8)(x) - (()+1))40((((aa)
Sh.
e1----Mahe (kh+6))2
ehh+0
Proof of Theorem 1 Recall that Q is the path measure of the true reverse process (Yi).e(o,7)
starting from Yo QT, and pa* is the path measure of the sampling process Z (Zi)
starting from Zo ~ n.. is a CTMC with rate matrix Q where the non-zero off-diagonal entries
defined by
(x,xx o - $1-1(1(()) for X' + x²
Then Ż (0, is CTMC with rate matrix Q starting from Zo or with path measure per. By the data processing inequality, we have the estimate
dQ (Y)
dler
DkL(gslPr-s) DKL (QII""""" Ey Ex log
dl (Y)
dPvr
dQ
dqr
Ey log
(Y)
drd (Yo)
dlPrr
DKL (KL((Q[PPF)) + DKL (frl((=)
(15)
where the second last equality holds since the only difference between the two path measures IPrr and [p* is the initial distribution for a path Y. We respectively bound the two terms (T5). The
second term is bounded by Proposition 2 We next combine Lemmas
2 and 3 Assumption and
Proposition to bound the first term in (15). By choosing
C max {1 1+ 11-1'
S 11'x6
|| (()))))
max
MEX K-1)
we have
D
K-1 1
(k+1)4+8
Exing D[(s(/xs/18/e/en)aaa dt
6h+5
C1
(k+1)4+88
Ex Ex S(R+1)445 (xx)
S
kh+t
C
K-1
(1-1))+5
Exing. DI
dt
S
kh+t5
K=0
16

---

Published as a conference paper at ICLR 2025
K
(kh+d)
S
2A
+ +1
dS + +c scooe
5
e (bh+8))2
chi -1
2(h++o)
s
)
+1 h + CfEcore
11
(kh+6)34
ckh+o
2x
S C
dx + C1dsah + C7 Coooe
2)
C² -
[[ee - 1) + (6 - log(e 1 Cids Cids" + Cids Ci Exonre
(6 S cdd + Cids Cfecoore
8²) CidS C1dS + Cf Cscore
(16)
The first equality follows from Lemma 1 The first inequality is consequence of Lemma - and
Proposition 3 Lemma and Assumption I lead to the second inequality. The third inequality stems
from (a (a++6 c) 3(a² 02 + )²) The second last inequality utilizes the fact that e - 2 x.
For the final inequality, we employ 6-0+ Lastly, combining (5). 16. and Proposition 2 yields the KL divergence bound (8)
Ō(S-i) and note that 5 + log(1/8)5² = 0(8-3) as
As for the TV distance bound 2 it is a similar proof that of Theorem 6(2) in Chen & Ying (2024). By the definition of TV distance and the uniformization of CTMC (Chen & Ying 2024
Proposition 1), we have
Dry (Pdatas 98) S P(X. # X8)
P(A Poisson(d(S - 1)5/5) random variable is non-zero')
(17)
d(s 1)8-1)
Then by the triangle inequality, Pinsker's inequality and inequality 8 we have
Drv (Pdata, PT -6) Drv pr- + DTV (Pdata, 46)
V DKL(gs)lpr-s) - -((S-1))//)
V de- do- log 53 + Cfescoe (1 1----d15110 -dd(-1/11))//)
We conclude the proof of Theorem
A.4 PROOF OF THEOREM 2
Proof of Theorem The proof of Theorem similar to that of Theorem Note that the decom-
position 15) and the equation for path measure KL divergence in Lemmal I still hold for d 0. It
suffices to bound the first term of 15
We need the following lemmas. Proofs Lemmas and
provided in Appendix B
Lemma 4 (Score bound). Suppose Assumption holds. Let 8 = O. Then for all t E [0, x E X, i [d] and 4² f x² [S], we have
s((x) S
Lemma 5 (Score movement bound). Suppose Assumption 2 holds. Let 5 = 0. Then for all h
(0, 1, ... K 1}, & E [kh, (k: + 1)4), x E X. i [d], and xt + x² E [S], we have
(sx(x) S(K+1)) (x) 5 e- + + nigh
We then combine Lemmas 5
Assumption D and Proposition 3 with 5 By choosing
C2 = max
L,
max
K- (1)(0+11 (x)=10
17

---

Published as a conference paper at ICLR 2025
have
DKL. (Q))
K-
1k+
Exira Dr(s((x))l@@ de
K=D
kh
(A+1)A
Ex Sxangills((x2 1(4+1)) (x))2
S
kh
((++1)
+
Exing (
11++
Ex ruge
Σ Σ
- 1))+)) -
+ Cscore
1= stttttt
S
(K++JA
Exiry
Σ
12h² dt + C2 1 c- (K+1)A +
kh
1=1 ='
C2
(-(++1)A + +
n2?10 + C2Esorr
A=0
C2n
e- (k+1)hzz 13 C2 Escore
S 22
(1 (1---z)2 dæ + C2x 2 + C2 Escore
h
< 11
T - log(e" h - 1) + -b
+ C2n S2 + Esenro
②
1
h2
T - log +
C2Ax² 52 + ChESCore
h
1 h
$ 13
T
+ C2 Cscore
2A3 3
[h- 22
S2
+ C2escore Escore
h2222222T + Cscoore
(18)
The first equality follows from Lemma 1 Lemma Proposition lead to the first inequality. As- sumption [ gives rise to the second inequality, while Lemma JemmaB5yyelee yiellss the third. The fourth inequality stems from the fact that (a + b)2 < 2(n² + b2). Inequality is a consequence of ex 1 2 x, and (ii) results from the assumption that h < $2.
Then Theorem
2 follows from 15
and Proposition 2
Discussion on C₁ and C2. Since we have access to uniform bounds for the true score functions from Lemmas 2 and 4 which depend on either and S. or L, we can apply score clipping during training to ensure that the learned score functions are reliable. Specifically, we enforce the following conditions:
3 1+ 2
35 5
(161441)++6x))l6 I XEX, ME K-11
max
-1
<
for a small 6.
and
K 1-) || (x)x+1)(()1ll S 3 L. 2
max xEX, KE (O......
As result, we choose that Ci and C2 3 L..
38 3
18

---

Published as a conference paper at ICLR 2025
B OMITTED PROOFS IN APPENDIX A
B.I PROOF OF LEMMA
To prove Lemma T we need the following generalized Girsanov's s theorem and Dynkin's formula, as stated below. For related definitions and details regarding the notations used in Theorem 3 and Lemma 6 we refer readers to the work of Benton et al. (2024b).
Theorem (Girsanov, (Benton et al. 2024b, Theorem 6)). Ler Y = =Y,, t)20 and Z = (Ze, t)
be Feller processes on S with generators L, and path measures Q, P respectively, such that Yo and Zo have the same law, Suppose that there exists a bounded, measurable function 8 (0, +20) such that a La is bounded, and such that
aMs = f(fa)-
(19)
for all proper functions f (assume that all the involved functions well-defined). Then we have
dP d
awrr, T)
exp {-f" La(ws,
(w) alwo, 0)
ds
a(Wers)
Lemma 6 (Dynkin's formula, (Dong 2003 Theorem 27.20)). 1fY =Yy, l)12 is Feller process on S with generator f. and a proper junction on (assume that all the involved functions are well-defined), then
Mf = - f CJ(Y,,
is a martingale with respect to the natural filtration of Y
Proof of Lemma ! Recall that Y (Yo) is the true time reversal CTMC with generator Q and Z = (Ze (2))) is the sampling CTMC with generator Q both initiating from @r: the rate matrices are of the forms
O (x, o )*) = ST and Q x 2 8²) = 5 8T (x)) for x² + 8².
Since the processes Y and 2 on X' are time-inhomogenecous, inspired by Benton et al. (2024b), we consider Feller processes Y, Z defined on the extended space structed by setting Y; = Yr and Z, Zr for t 2 T and letting Y = (Y, t) and Z = (Z,, t) which are honogeoomgsssuss.... For more related details on the Feller process and stochastic analysis, we refer readers to the work of Benton et al. (2024b).
X' [0, +00) which are
We can now apply Theorem 3 with L = O, + å and M =0 Ō + M. where 2 and M are the generators of the CTMCs Y and Z respectively, the condition 119 has the form
aMs- = =L(fa) fLa,
and it follows that
axxxt) t) Σ (x, Σ 2
f(x) Σ Qi (x, t))
for all x E X. By taking y x 3² (+* + )²)
and f(z) 1(z = y.. we have
a(xx, () [g (x* acyy
for all i E [d] and st *'
Thus, in order for 19 to hold, is required that
a(x, t)
8T (x)
a(x' 2 2 8 (1) for all i E [d] and 4' # x!.
(20)
also can be easily verified that this is sufficient for 19 to hold for given a. Let and IP be the path measures of Y and Z respectively. Then with function a(x, satisfying 20 Theorem yields that
d (Y) = a(Yr -,, T
dP
T-8 8) ((a()))) s))
exp
(21)
a(Yo,0) 0)
19

---

Published as a conference paper at ICLR 2025
By taking f = log in Lemma 6 we know that
Mf log a(Y,,t) t) a<Yo; 0) C Clog a aY,: ss ds
is Q-martingale. Then by taking logarithms in 21 it follows that
dP
log
(Y)
dQ
T-6
Cloga(Y.. 5) 8)
ds + Mf
T
[oa(Ys:s) La(Ye:))
O₂ aogoa(Ys loo (()g(())s))))
s(Y +
ds Mf
a(Y,:
6
aloga(Y., La(Ys; 8()..
do M4-8
Taking expectation above yields that
dQ
DRL(Q[ = DKL (QIIP) = Eg log
dP
BQ
Cloga ds + B
a(Y..))
La(xi,t) a(x,,t)
log (loga(xe:)) di
ExINOT
Ot (x4,8) aly.1)
(x:, a(y,
} dc
Exp
Σ
((xx,t))
a(xi,t)
yEN
T-
Qi (x), + Σ Qi (x.,)) aly,t)
of (xx,) log a(x,,t)
Exi~gr-
Σ
tly,t) dt
a(xi,t)
yxx:
yxx
1
T-h
d Σ
ExINOT
-x)-( + (0n-(()(xxx)ss0
S J
(=1 s/znj
ST (
ST [2 (xx (xe)i.ag + +xT=1(x))i.0 log
dt
1
T-6
3
3
ExINer
Di (x00--100)))01/77-114
1=1 #ita
K-1
(k+1)A
1
-3
Exingr
(x) (x:)e.a)) dt
K-1
(R+1)A
- dt
S
(k+1)++8
1
Exiag D(((s(xx)l((xx+)))==xxx)) dt,
3
kh+8
where we used E,M4,,, EgMo = since {M/ Jazo is a Q-martingale by Lemma Thus we finish the proof of Lemma
0
20

---

Published as a conference paper at ICLR 2025
B.2
PROOF OF LEMMA
Proof o Lemma
2 Note that for all 0 - 1' +
8x(x),,
(x(x)) V @ 4*)
1
Σ qu (Xx Majer (x 2 29 (xx)
(x(x)
(x(x)
X.E
qe (x,r) II Aye (o latt )a (8" (6'12z))
(x)
ligtt
d II
Tep (2%
qu (xxr)
Tbe (a (2 Tee (20%
(x(x)
X.EE
k=1
qu (x< Jepe (x(
Bie (2%))))))
qt (x(x)
Gej (1²* (22e.)
x,
Lijo (
E ae 1e( xx) Gep (ar (xr].)
(22)
In particular, by taking 1' = 0 in we have
4/10 (af (((())) 4/10 (orf (m)))
(x()),, Exorgg (xbb))
1 e
S
S
Exp ((1x)
<
+
(23)
(-14-
et
B.3
PROOF OF LEMMA 3
To prove Lemma 3 we need the following lemmas. Proofs of Lemmas 7 8 and 9 are provided in Appendix C
Lemma 7. Denote of as the marginals of the i-th dimensional forward CTMC x and the cor-
responding score function for X si(r), d(()) for y E [S]. Then for all i [d].
gi(x)
k E 10,1,..... K 1}. tttEE E 1kh + 8, (k + 1)h + 6). and x # [S]. we have
She (kcb+)))
$)(r), I 1 chb 1 and s((x), s( s (1 e (6h++66))2
Lemma 8. There exists some large enough t' such that for all t e kk + 6, (k + 1)h + 6), x F (S), and xe E [S]. we have
[d], k 10,1,...,
(xr()) (01 o (xv(x) (((++))4((0ell)) (xel=)
Leplsv (y)
8Sh, and
2.
L)((Fe12))
Lemma 9. There exists some large enough t' such that for all E 10.1.... , K - 1}. t E [kh+ 5, (k + 1)h + 8] and X, it holds that
2 Dr Drv(geje(-1z) (e(e)))))))))000))))) < h.
Proof of Lemma 3
We can bound the high-dimensional score movement as follows:
(x(()) - 5(k- 1(k-1)++ 6))++(x)sxxx) (x)
L (a (at.))
(1x+1)++0j0 (#* (ozz)) Ex, - aar gi 1)4+1)644-1 176 (xr (xr{.)
Ex x)
L (2 (xt.)
a (o (af.))
11411445 ef (i (att)art)))
< E Exp (11b)) el)bx)
B (1 (ot)))
4441)n4t (xt) (o()))
21

---

Published as a conference paper at ICLR 2025
Pa+ + (2'laz)))
Fx Px F 13 eper (6 (2
+ E Exingra
1)++0 (xt1xr)))
F + (x* [x
L (2)
((4+1)+0(1"))) (1 + (zfz (a*)
Ex sx(x")a
Po (arg
To (app lar))
sup 0,25,20 22 2
DDrv(arje (0(0-+))45((
(24)
To (2t (x:))
where the first equality is by (22) the first inequality is due to the triangle inequality, and the last rule.
inequality is due to the Bayes
Then by utilizing the inequality |0102 b, < (0
bj l2 + bı bala2 bal (a1, 02 b1. b2 2 0) for 7 and for some large enough we have that
the first term in (24). and then using Lemmas
9
2.he (6h++)
S
(xx,)) 8(4+1)4+8 (x))
(1
)88h
+ 2h
(1 e (k++8))2
@kh+
(kh+5)
s
V2
+ Sh.
11 e (sh++6))
ekh+ -
B.4 PROOF OF LEMMA
Proof of Lemma kernel function
f
This is similar proof that of Lemma in Chen & Ying (0224). Define the
gw (1)
[ [++
1( =0 (mod S)}] for w E 2 t 1 0.
Sa i=1
By Proposition can express the transition probability of the forward process
d
d
(x(x(x)(x,) = II
ghj (x/1=²))) = II
Po. (2
i=1
2=1
1 + (t-s)(-1 S. (x),-\1) for all <> 0.
St d=1
Then we have (y x) = By x for 1 0. Thus, it follows that for all / E (0, x X [d]
and x² * x' E [S].
Se (x (xxx) @ a+)
(x)
9i(x (#' x² )c:)
(x())
Eyex (oly))cjf( x + (it - x² y
q (x)
Eyex qu(v))x+( (aciaia-aaa a0)
(t))
T (x)
Eyex lo (+'
x²
(x(x)
90(x))e)(x(1))
go(y + (x' - xt)e
ge
go(y)
yex
By (-1x) go + (i* x² )eee))
< L,
yo(y)
where the last inequality is by Assumption and y + (# - x x')e; should be understood in modulo S sense.
22

---

Published as a conference paper at ICLR 2025
B.5 PROOF OF LEMMA 5
Lemma 10. Suppose Assumption 2 holds. Let ó 0, then for all E [d]. k E {0,1, ... K 1}.
t te [kh, (k + 1)h], and x # y E [S), we have
(x)y) S Kis
and (((x), s (2 (z)u Ski 1 (2+1)6
The proof of Lemma 10 provided Appendix C
Proof of Lemma]
5 Similar to the proof of Lemma by utilizing the inequality Ja1æς - bybيl
|a: bi a2 + bj 02
by (a), d2, b1, b2 2 0) for the first term in (24) and then combining Lemma
Lemma 9 and Lemma 10 with 8 O, we obtain
(x(()) - S(k+1)A (x) S K4
e (k+1) h h 8Sh + 2h
e (k+1)6 + k,h.
OMITTED PROOFS IN APPENDIX B
C.I PROOF OF LEMMA 7
Proof of Lemmal Proposition
D Iimplies that
4 = Po.. Paata = =p-'aa + (1 (1--
Thus, we have
gi(y)
Paata (V) + (e" - 1)
<1(x),
(25)
qi (x)
Paana (x) + (et - 1)
and
(v)
f2-11840 (v)
st(2), - -((+1))+662))
(xr
11++ (x)
IPanta (x) Panta())) (pasta (x) + (e(++1)) (S (y) + (et-1) 1))
(e (e+11)) -e)
(26)
We can derive from
25 and 26 that if retain the dependence on 6, we obtain
S I 11 ehh++ -1*
$1)),, <1+ e --1
and
Se(k+1) (1 (((++1))0+8-1)
(x()) - s(et1)+6(0)g) 5 (elk+1)/+t 1)(e" -1)
Sh
e- ((++))++)) (chhit (cht++ 1)
She -(kh+6)
e- (1h++))2
23

---

Published as a conference paper at ICLR 2025
C.2
PROOF OF LEMMA g
Proof of Lemma 8 First, we have
( (v) - 1001) (2vvll))
5 1-1+8 8 of (1' - -0- -
$ ((++))+++)) (1-ttt1011-00000000000-- ((++1))6666))) S h
-
and
qe (xxl))
1 (1 + (t'-0) (-1+ 8f2, 2z 11) 2 5
e (((-)))) 2 22
g
L (2r (x) - 5 (1ee (1' D) - 1])
g
for some large enough l' (for example, 1' T 2 log 5 Hence, we have the estimate
( (v)
z 10 (xely)
Le (0++244 (3xr
(zee 1u) 13a+o (Ie (x) of 13 t (wrl)
2h
8Sh.
1 (ate (or (x)a (x (ze (2e)
252
For the other statement, it holds that
(xvl()))))) 1te (1' - 8f2r.81
S
( lx) 1te -te-(000(-1)) )xr, $ 11
et - 2
for some large t' (for example, t' 2 T log
C.3 PROOF OF LEMMA 9
Proof of Lemma 9 By taking large enough (for example, 2 T d S + log d), we have
2 Dry Dry(ge (x),, 1010 1)x+6(11x))) = Σ
X EX
Σ
II (o II qe 10004)44000001 (x*)
X l==1
< (S -c' -('- ((N-(((1)++00)) h.
where the second last inequality comes from the inequality
T
12
II 0: II
(ax=
bk) II mix(a;,bb) bi} ip
where mix mix(a;, b.} denotes taking a value from a₂ and b;-
C.4 PROOF OF LEMMA I0
Proof of Lemma 10 We retain the dependence on Pasta in equations (5 and 26 with 8 0. and
derive that
<t(x)y S max
(Páata dmax (P'sta) Jmin
1
Kis
and
()()), s()+ 5 (Phata) )max h
(Panta)min
1 (K+1JA
Ni 1 1 (k+1)h
24

---

Published as a conference paper at ICLR 2025
Algorithm 1 Generative Reverse Process Simulation through Uniformization
Input: Learned discrete score function -hh (k 0, 1. K - 1), total time T, discretization T Kh 2 0
step h > O, and
1: Draw Zg ~ Td
2: for k 0, 1....... K - do
3:
Set A = maxxEx (
4:
Draw M ~ Poisson(Ax.h (x.
5:
Set yo = Z4k
6:
for j 0, ...
M do
yj 11
åT un(ssii' 1 "i 5 E [S]
w.p.
7:
y5+1
w.p. 1 - Σi= Egi
AT (Ns))
Yjs
Ap.
8:
end for
9:
Set Z YM
end for
Output: A sample zk from PT-6
D PRACTICAL ALGORITHM
Inspired by Chen & Ying 2024, Algorithm 1), we provide a practical generative sampling algorithm
in Algorithm The uniformization of CTMC guarantees the algorithm (Chen & Ying 2024 Propo-
sition 1). For convenience, we define (x)xxx == Σ Ex $e(x) for t [0, T". yielding that
(x, = - OT (x, -
Σ Σ Q -z S 2'
1 Σ
Σ ST (
y/x
1
5 5 (1))
Note that we run a Poisson point process to sample based on the transition probability matrix exp (1QT)) in each iteration. Running Algorithm requires M Poisson(A) steps with
A = 2k= dyh EO maxxEx (a (x)x)),,, which characterizes the sampling complex- ity.
Discussion on 0 in Algorithm We set A = ( in Algorithm where the maximum is taken over the discrete set X' [s] When |.X' = S is so large that it impractical to obtain this exact maximum, by the uniformization of CTMC (Chen & Ying 2024 Proposition 1), we can instead set Ås as an upper bound for maxxex m (sT-Nx
Since we
know that E Σ fz (x) < dS(1 + ) for all k E {0,
K 1} and
X by Lemma we can apply score elipping ensure that ST (x)x S 2 ds(1 + )
for all x X. Therefore, we can set A ds (1 - which is tractable given any k, T, h, d, and S, thereby avoiding the need to calculate the maximum over the set X.
Discussion on X. By applying score clipping with šT =x)xx(x dd + -- ) we have
K-1
Σ ds (1
S
_ h dST 2
(1+
-h
-1
ch+ -
k=0
k=1
I"
1
S dST + dS²
dt S ds(T + log 11(h + 8))).
148 e -
By choosing and h in Corollary I we have
X S dS
log
dlog S
min {
{ (CiSsd))
} llgg(1/))
1/ (c,55T)
E
s
25

---

Published as a conference paper at ICLR 2025
dlog S + (G)
à sid oz 1og(1/6);
< log
(27)
where we used the inequality min(a, b3 I vab for a, b 2 0; by choosing T and Corollary we have
log d dlog S
Sh +h (og((111))) x ds log d doog S c
O2S
A ds
log
(28)
C2k²
which depends the property of data distribution. When score clipping is applied discussed in Appendix A.4 we can specify C1 = 39 and C2 = L and further obtain from (27) that
dlog S + ta t o log(1/8) - log dlog (6 0+)
S ds log
(29)
with early stopping, and from 28 that
log d dogg S
2
S ds log dog S
x ds
log
+ 1
log S
(30)
T
V
Txx2
without early stopping. Note that the last term of (30) can be rather small for some large L and x² leading the first term to be the dominant term in the bound (30), which matches the bound 29 for the sampling complexity with sufficient small 8 > O.
E BREGMAN DIVERGENCE
Definition 1 (Bregman divergence). Let & be a strictly convex function defined on a convex set C IR (n E N4) and ó is differentiable. The Bregman divergence Do(Illy) : S x S - R4 is defined as
Da(xlly) -(x))(((1))) <(v) ( (x -y).
(o(v))((
In particular, the generalized I-divergence
Dr(xly) Σ
- x + 3² +
x² log
y¹
is generated by the negative entropy function I(x) Ei_ x' log x. When restricted on the sim- plex, the generalized I-divergence becomes KL divergence.
The Bregman divergence does not satisfy the triangle inequality. However, for the negative entropy restricted to closed box contained in R2g we have the following proposition, which provides an analogous form of triangle inequality.
Proposition 3. Let the negative entropy function 1(x) = Ei= x² log x defined on 1 C1Th (C
0). Then for all x,y, [t. Cln, we have
SC- 2112 +02 (z(y))))
Proof of Proposition 3 By (2] diag "..... ... + x CIa for all 1t, CJn, there exists
some 0 [0, such that for all x, y, E 12, C1n, it holds that
1
(x(x
2 (x -y-
T>> + -))xxx(xxx-----))) y)
C
|x -y11
S C (||x 2 + ||z - y1
S C. ||x - 2112 + +0 DD(zlly);
where the last inequality is by the strongly-convexity of I on [g C1nh since V²[(x)
diag + _ 2 JL..
26


Reviews:
[{"review_id": "ulhLqwm79I", "reviewer": "Reviewer_Gwu3", "summary": "The paper presents a discrete-time sampling method using score estimators at fixed points in a multidimensional state space. It provides bounds on how closely the sample matches the data distribution, with KL divergence bounds nearly linear in dimension, comparable to top diffusion models. The analysis uses a Girsanov-based approach to define key properties of the discrete score function for effective sampling.", "questions": "- *Equation on line 723*. Why is $Q$ equal to the Kronecker sum $Q^{tok}$?   \n - *line 296* Why is the reverse process time-inhomogeneous? \n - *line 3 of the Algorithm*: How easy is it to find the maximum of the estimated score function? Is there any concavity assumption to make this problem solvable in theory/real-time? Is this assumption satisfied for practically relevant examples?\n - *line 361* Why is there a uniform upper bound on all the scores and their estimators? On line 371 the authors mention that the score function may be as large as infinity for some data points. This means, that when $\\delta$ is small, this uniform upper bound $C_1$ becomes larger, thus, it is dependent on $\\delta$. Can this dependence be quantified? \n - *Equation (4)*. Why is this true? Is there a reference or a proof for this statement?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper tackles an interesting theoretical problem. Theoretical analysis of diffusion models with finite state spaces with discrete time space is of great importance. The authors have made the effort to push further the existing methods for the current setting.", "weaknesses": "The notation is confusing and important details are often omitted.  The assumptions seem to be rather stringent. The paper lacks mathematical clarity. See the below sections for details.\n \n### Mathematical comments \n \n- *Proposition 1*. The formula for $q_t$ depends on the initial data distribution $p_{data}$. When $t \\rightarrow \\infty$, the term on the right side  $\\frac{1}{S} \\left(1 - e^{-t}\\right) \\mathbf{1}_S \\mathbf{1}_S^\\top + e^{-t} I_S \\rightarrow \\frac{1}{S} \\mathbf{1}_S \\mathbf{1}_S^\\top$ . The latter is a fixed matrix and thus $q_t \\rightarrow \\frac{1}{S} \\mathbf{1}_S \\mathbf{1}_S^\\top \\cdot p_{data}$. This is not necessarily the uniform distribution. \n- *Proposition 1* What does approaching mean here? In what sense do you have the convergence?\n-  *line 280* . The sentence `With rate $Q^{\\leftarrow}_t$, it holds that...` is not clear. Is there a reference or proof for this statement? \n- *Assumption 2* It does not seem to be easy to verify this assumption. Is there a general class of distributions that are known to satisfy it?\n- *Theorem 2* The number $\\kappa_i$ is not always well-defined, as we deal with discrete distributions, where some of the probabilities may be equal to zero. \n\n#### typos\n- *line 187* if setting β(t) as a time-dependent scala\n- *line 206* Nota -> Note\n- *line 323* For completeness, We -> For completeness, we", "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": "93nceAvkmT", "reviewer": "Reviewer_qT9k", "summary": "The paper  examines theoretical aspects of score-based discrete diffusion models within a Continuous Time Markov Chain (CTMC) framework. The authors aim to address the underexplored convergence properties of these models, especially in discrete state spaces, compared to their continuous counterparts which have been widely studied. Key contributions of the paper include: 1. The authors propose a discrete-time sampling algorithm designed for high-dimensional discrete diffusion tasks. This algorithm leverages score estimators at specific time points to approximate the reverse process of the diffusion model. 2. They provide convergence bounds for the KL divergence and TV distance between the generated sample distribution and the target data distribution. The bounds are derived for cases both with and without early stopping, depending on assumptions about the data distribution's properties. 3.The convergence analysis is performed using a Girsanov-based method, which enables the authors to assess the score estimation error, discretization error, and mixing properties of the forward process. This method is adapted from techniques in continuous diffusion models and tailored to the discrete setting. 4. The paper establishes that their convergence bounds scale nearly linearly with the data dimension, aligning with the best results for continuous models. Additionally, they discuss practical considerations, such as the need for score clipping and early stopping under certain conditions to handle potential score function divergences. 5. The authors compare their method with prior approaches, particularly highlighting differences in sampling efficiency and the elimination of certain assumptions on score estimators, thus broadening the algorithm's applicability in discrete settings.", "questions": "1. Have the authors considered adaptive step sizes as a way to minimize discretization error? If so, could author's share insights on how this might affect the overall convergence bound?\n2. The paper proposes a CTMC-based discrete diffusion model, but certain continuous diffusion approaches are also adaptable to discrete data. Could the authors elaborate on specific scenarios or types of tasks where their CTMC-based model would be preferred over these alternative approaches?\n3. Also see weaknesses part above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overrall I think this work is clear and studies a clean problem which is relevant to the theoretical understanding of diffusion models.. Theorems 1 and 2 derive rigorous convergence bounds for score-based discrete diffusion models using KL divergence (Theorem 1 with early stopping, Theorem 2 without early stopping). This provides a critical theoretical foundation for discrete diffusion modeling, aligning nearly linearly with the dimension $d$, a promising result compared to continuous models. And the use of a Girsanov-based approach to analyze the sampling algorithm in a discrete setting is particularly noteworthy (Sections 5 and 6). This method adapts well-established techniques from continuous diffusion models and is a creative application in the discrete domain, enabling a novel convergence analysis.\nThe work also proposes a time-discretized approach (Section 4 and Algorithm 1), which involves sampling at discrete time steps rather than simulating the continuous CTMC path. This approach allows for more efficient sampling, as it does not require continuous access to the reverse CTMC. Additionally, to ensure bounded score estimates, the authors introduce score clipping as a practical solution for handling extreme values (discussed in Section 5).", "weaknesses": "I don't see major weaknesses of this work, but I do have some comments:\n1. Since the authors claim improved sampling efficiency (e.g., fewer function evaluations), would compare actual runtime or convergence speed with other discrete sampling methods (such as the uniformization technique in Chen & Ying) substantiate these claims?\n2. Assumption 2 requires the data distribution to have full support and uniform bounds. This may restrict the model.\n3. Although the work mentions similarities with continuous diffusion models, there is limited discussion on when to use their discrete CTMC approach versus discretized continuous models for discrete data. \n4. Generalizability to Other State Spaces: The works' algorithm assumes a general state space $[S]^d$, but would it be insightful to discuss how it might extend to more complex or structured discrete spaces, such as graph-based or hierarchical state spaces, which are common in discrete data applications?", "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": "ktILs21QSc", "reviewer": "Reviewer_nnaP", "summary": "This paper provides the convergence rate of the discrete diffusion models introduced by Lou and Ermon. The authors consider the finite state space $S^d$, extending early analysis by Chen and Ying in the continuous time.", "questions": "Please see the weakness section.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a timely convergence analysis of the discrete diffusion models, which is important in understanding this new class of models (with applications to LMM). I checked most proofs, and they are scientifically correct.", "weaknesses": "The weaknesses are:\n\n(1) The main idea of proofs are very similar to Chen and Yin, with the key to the proof the representation given by Proposition 1. The differences are: (1) the paper extends the previous results from $\\{0,1\\}^d$ to $S^d$; (2) the paper considers the issue of discretization. I agree that (2) is important, while (1) seems to me incremental. \n\n(2) The authors made Assumption 2, which requires the ratio constant $L$ is independent of $d$. I am dubious on this assumption, since the main application of the discrete diffusion models is on the LLM. I would encourage the authors to provide a numerical analysis to show indeed this assumption is valid.\n\n(3) Regarding early stopping: Chen and Yin considers early stopping since they are concerned with the continuous dynamics. It is known that the score matching has large errors near time $0$, and even the continuous dynamics may not be well-defined at $0$. Since the paper studies the discrete scheme, I wonder if there is a particular reason why the authors also consider early stopping. \n\n(4) Except the error for the initialization, which uses log-Sobolev inequality (more or less expected), the other ingredients in the proof are very similar to the existing approaches to the SDE-based diffusion models. Of course, the authors dealt with CDMC, which is slightly different.", "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": "18gDG57QyV", "reviewer": "Reviewer_k765", "summary": "This work develops an algorithm for score-based diffusion models over a discrete state space. Their new algorithm relies on the uniformization of the CTMC developed by Chen and Ying and discretization in time. The main innovation of the work is theoretical. Using this new algorithm, the authors can derive bounds on the generated samples under less restrictive assumptions than in previous work. The main assumption is an approximate score function, where analogous to the results on continuous denoising diffusion models, the authors are able to develop a bound with early stopping. Under the further assumption of bounded scores for the data distribution, the authors show that early stopping is no longer needed and can derive bounds at $t=0$.", "questions": "Can the authors provide more explanation comparing their result to the Chen and Ying result? \n\nAlso, can they provide a comparison between their guarantees and the guarantees for continuous models? I am curious if they are analogous or what the fundamental differences are.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well-written and represents a strong contribution to the generative model literature. The assumptions are weaker than those for existing algorithms. There is a strong case for accepting this paper due to its novel theoretical analysis of an important problem. The theoretical framework given may be useful in analyzing more general settings and motivating further algorithmic improvements.", "weaknesses": "First, It is unclear how tight these bounds are. Can the authors compare these to bounds in the continuous setting? Second, I don’t understand everything in the table, and it would be better to flesh out the comparison with Chen and Ying. In particular, their assumptions are different, can you tell us what they are? Finally, there are no tests of the algorithm in practice. While the theoretical contribution is nice, it remains to be seen if it will have an impact on practice.", "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)