Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models
Authors: Yuchen Liang
Renxiang Huang
Lifeng Lai
Ness Shroff
Yingbin Liang
Venue: NeurIPS 2025 poster ()
Keywords: Discrete diffusion models
absorbing rate
tau-leaping
uniformization
Primary area: theory

Abstract: Discrete state space diffusion models have shown significant advantages in applications involving discrete data, such as text and image generation. It has also been observed that their performance is highly sensitive to the choice of rate matrices, particularly between uniform and absorbing rate matrices. While empirical results suggest that absorbing rate matrices often yield better generation quality compared to uniform rate matrices, existing theoretical works have largely focused on the uniform rate matrices case. Notably, convergence guarantees and error analyses for absorbing diffusion models are still missing. In this work, we provide the first finite-time error bounds and convergence rate analysis for discrete diffusion models using absorbing rate matrices. We begin by deriving an upper bound on the KL divergence of the forward process, introducing a surrogate initialization distribution to address the challenge posed by the absorbing stationary distribution, which is a singleton and causes the KL divergence to be ill-defined. We then establish the first convergence guarantees for both the $\tau$-leaping and uniformization samplers under absorbing rate matrices, demonstrating improved rates over their counterparts using uniform rate matrices. Furthermore, under suitable assumptions, we provide convergence guarantees without early stopping. Our analysis introduces several new technical tools to address challenges unique to absorbing rate matrices. These include a Jensen-type argument for bounding forward process convergence, novel techniques for bounding absorbing score functions, and a non-divergent upper bound on the score near initialization that removes the need of early-stopping.

Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models
Yuchen Liang", The Ohio State University
Renxiang Huang"",
Lifeng Lai', Ness Shrofft, Yingbin Liang? University of California, Davis
Abstract
Discrete state space diffusion models have shown significant advantages in applica- tions involving discrete data, such text and image generation. It has also been observed that their performance highly sensitive to the choice rate matrices, particularly between uniform and absorbing rate matrices. While empirical results suggest that absorbing rate matrices often yield better generation quality compared uniform matrices, existing theoretical works have largely focused the uniform rate matrices case. Notably, convergence guarantees and error analyses for absorbing diffusion models are still missing. In this work, we provide the first finite-time error bounds and convergence rate analysis for discrete diffusion models using absorbing rate matrices. We begin by deriving an upper bound on the KL divergence of the forward process, introducing a surrogate initialization distribution address the challenge posed by the absorbing stationary distribution, which is a singleton and causes the KL divergence to be ill-defined. We then establish the first convergence guarantees for both the r-leaping and uniformization samplers under absorbing rate matrices, demonstrating improved rates over their counterparts using uniform rate matrices. Furthermore, under suitable assumptions, we provide convergence guarantees without early stopping. Our analysis introduces several new technical tools to address challenges unique to absorbing rate matrices. These include a Jensen-type argument for bounding forward process convergence, novel techniques for bounding absorbing score functions, and a non-divergent upper bound the score near initialization that removes the need of early stoppig..
Introduction
The diffusion model is one of the key branches of generative models. Inspired by non-equilibrium statistical physies, it first introduced in M and was subsequently refined and extended by (2) In recent years, the diffusion model has achieved many breakthroughs in the generation tasks under both continuous state spaces that for discrete data such as natural language and graphs, discrete diffusion models offer greater advantages and more flexibility than their continuous counterparts 7
and discrete state spaces 6). growing body of work suggests
Diffusion models typically include a forward noising diffusion process and backward denoising process. Under the continuous-time formulation of discrete diffusion models, the forward process can be characterized by continuous-tima Markov chains (CTMCs), with some specially designed rate matrix. Commonly used rate matrices include the uniform rate matrix, which leads to uniform stationary distribution; and the absorbing rate matrix, which results in singleton (absorbing) stationary distribution. The generation quality typically highly sensitive to the choice of the CTMC rate matrix. It was first reported by [5] that using the absorbing rate yields better performance than using the uniform rate in terms of both perplexity and negative likelikeld (NLL) for text
generation tasks. This empirical ad advantage was further confirmed subsequently by [ 10 I. where
consistent improvement was observed using the absorbing rate matrix. Moreover, [ established
These authors contributed equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Sampling algorithm
Early- stopping?
Uniform Rate [5
Absorbing Rate (this paper)
Yes
O /s)
O(d/s)
7-leaping
No
(1d4/e)
Pois (dlog((d/))
Pois lo log(d/E)
Yes
Uniformization
+dlogo-1)
+dlogo-1)
Pois (Od log(d/e)
No
N/A
+dy-1)
Comparison of convergence results in terms of number of steps. Here we list only comparable references with the uniform rate (under the same algorithm and sample space). Note that 15 assumes symmetric rate matrix, which does not include the absorbing rate matrix studied in this paper. Here d is the data dimension, 8 is the amount of perturbation due early-stopping. E the target accuracy in KL-divergence, and ?y describes the minimum relative likelihood of the mask state in the data distribution (see Assumption 4). Here Pois(A) refers a Poisson random variable with mean The sample space for all the results here [S]d.
Table 1:
close relationships between the absorbing discrete diffusion models and other popular language modeling approaches, including BERT [12 and the conditional masked language model (CMLM) 13]
The superior performance of discrete diffusion models has sparked considerable theoretical interest in understanding their convergence properties. However, existing convergence guarantees have primarily focused on the uniform rate matrix, with various sampling approaches analyzed in this setting. These include the uniformization method [4 [5], sampling via piccewise solutions of the Kolmogorov equation at each discretized step [16 17. and the r-leaping sampler [6] [1). Among those studies, the uniform rate matrix explicitly assumed [6 [7], and a symmetric rate matrix considered in [15]. Notably, these studies do not address the setting involving absorbing rate matrix.
In contrast, although discrete diffusion models with absorbing rate matrix have demonstrated superior empirical performance [5] 9). there has been no theoretical analysis to characterize their convergence behavior date. This gap in the literature motivates present study.
1.1
Our Contributions
Our overall contribution in this paper is to provide the first theoretical convergence guarantee for discrete diffusion models under the absorbing rate matrix. This is further described in the following four parts:
Convergence of the forward process: To address the challenge of irregular KL-divergence under the absorbing stationary distribution (i.e., singleton), we design a smooth surrogate distribution which both close to this singleton and easy to sample from. We further show that the data distribution in the forward process converges exponentially fast to this surrogate distribution in terms of KI. divergence. Different from previous approaches using log-Sobolev incqualities, absorbing rate matrix is used. Our approach enables a well-controlled initialization error and prepares for further convergence analysis for the reverse process.
employ lensen-based technique which is applicable when the
2. Convergence guarantee under the absorbing rate matrix: we establish an upper bound on the KI. divergence between the generated and target distributions, showing that E KL-divergence accuracy can be achieved with ((d/c) steps. Notably. our convergence rate under the absorbing rate matrix linear in the data dimension d. which improves upon the quadratic dependency in d established for the uniform rate matrix with relppin in [15]. This result implies that, for the same number of sampling steps, the absorbing rate matrix yields smaller KL-ddivergence, which aligns well with empirical results found in (9 T0 M.]. Moreover, for the uniformization sampler, we show that e KL-divergence accuracy is achievable in expected Odd(og log(d, d/=)) + +log 8-1)) steps.
For the r-leaping sampler,

---

This also improves the expected O(d(log(d/E) + 1og&=")) steps previously required under the uniform rate matrix, further showing advantages of absorbing discrete diffusion models.
3. Convergence guarantee without early-stopping: Furthermore, we provide an interesting case which removes the need for early-stopping for both the r-leaping and the uniformization samplers. Intuitively speaking, this can be satisfied when the [MASK] token is selected one of the likely tokens in the given vocabulary. Compared [14] [15, we show that early-stopping might not be necessary even when using the uniformization sampler.
4. New techniques for bounding absorbing scores: One key component in our study is to investigate the properties of the score function under the absorbing rate matrix. Upon obtaining the exact expression of the score, provide upper and lower bounds both with and without early-stopping. We show that the absorbing score is more well-controlled than for the uniform case for large diffusion time, which enables smaller expected steps using uniformization. We also show a non-diverging score upper bound for quite relaxed data distributions, which removes the need of early-stopping. These score properties might have independent interest for future studies on absorbing diffusion models.
1.2 Related Works on Absorbing Discrete Diffusion Models
The superiority of absorbing discrete diffusion models have been confirmed in many empirical experiments, including text [5] 10 [ 18), image [5] [0], music [19], DNA sequence and
chemical molecule [8] 20]. Meanwhile, there have been many empirical studies investigating an
improved training objective particularly for absorbing discrete diffusion models. For example. [I]]
reparameterized the concrete score training objective to achieve efficient training and sampling, [1]
investigated and improved the training objective as weighted integral of cross-entropy loss, and [18] derived Bao-Blackwellize
objective to tighten the Evidence Lower- Bound (ELBO) and to reduce
training variances. Note that all of these works, while impressive, include only empirical results. A theoretical understanding of the superiority of absorbing diffusion models is still lacking. We have provided more detailed literature review in Appendix
Preliminaries of Discrete Diffusion Models
Discrete diffusion models consist of forward and a reverse process over the discrete data space.
The forward process is commonly modeled as a continuous-ting time Markov chain (CTMC) over a discrete state space [6]. We consider the state space [S] representing d-dimensional token space where each token is drawn from vocabulary of size S. Accordingly, the training data xo E [S] consists of d tokens, with an associated probability mass function denoted by 9o- Let Qr E RR be the rate matrix governing the forward process, where (z y) specifies the rate of transition from state x to state y, for all x, E [S]d. Then, given the previous state x, the transition probability from t At t given by: 4 ())=) (v = + Qx y) o(A))
Here, 1fy x} is the indicator function which equals if y and 0 otherwise. Clearly, the non-diagonal entries Qr(2, Z for x + y, and the diagonal entries Q( x)) < 0. We further have that Qx x) ΣEDter (x) Equivalently, the marginal distribution g: satisfies the Kolmogorov forward equation as follows:
di (v()
Σ Qr(z,))a = Qi LE[S
Given state x E [S]d, we denote x' E [S] as the i-th token of x. To simplify computation, it often assumed that each token propagates independently in the forward process 6 9 [6] This implies that the forward conditional distribution can be factorized as Zro (xy (mn) I gf (x) (of)). We define the rate matrix for each token Qt 5x8 It is shown in (6) that under such a forward process,
Qtok (xt, w²) 0
if only of + w²: otherwise.
Qx v)
We assume that Qe is time- tine-homogencous, and thus Q: Q and Qt = Qlok
3

---

In this work, we focus on the absorbing rate matrix, which results in singleton state towards the end of the forward process. Specifically, we let [MASK] [S] denote the mask state in the vocabulary. Write m(x) (s d) for the number of [MASK] in vector z. We define the absorbing rate matrix as
Qtak 1se MASK]] Is:
where 1s an all-1 vector of length S, and e; is a unit vector where only the i-th element is 1. In other words, there are only two cases where Qook (a. b) * O. First, the diagonal elements Qlok(a, a) = 1 Va E [S] a * [MASK], which corresponds to the case where no change occurs when the token is not yet in the mask state. Second, for the column corresponding to [MASK]. Qiok [MASK]]
1, Va E [S] + [MASK]. This corresponds to the transition from non-mask to the mask state.
The reverse process can be designed to be the exact time-reversal process of the above forward process with an initial distribution ?o = qr [ [21. In particular, [6] shows that the time-reversal process (ē.) } is also CTMC from ( = 0 to T with the reverse rate matrix given by
(1. v) = Qr- Tr (v-
Vz, y E [S]d such that x + y.
(1)
(x))
Then, the marginal distribution satisfies that i7 = Qr Similarly, for the diagonal elements in the reverse matrix, (2, = - - voree (x,
For continuous-space diffusion models, one generally defines the score function as Vz log q: (x)) Unfortunately, this is not applicable for discrete-space diffusion models where the gradient is not defined. Alternatively, the discrete score function is defined as 8 sz x)) = (.(v) In order to prevent
(x)))
the score function from blowing up around t = O, one common approach is to employ early stopping in the time-reversal process by setting the terminal time be Otherwise, if early-stopping is not applied, we simply set 8 = 0. To estimate the score function s, x)), can parameterize it via neural network and learn an approximation S, 8t. One popular training loss is the score entropy Lse (9] which is given by
T 5 with a small constant d.
Eulu 21)) (Bl().a)) - (v) - se x4) log
(v,
(SE( = Exgrogg
(2)
st s1 x1)
In practice, for tractable training, the denoising score entropy is usually used, which is variant of the score entropy 9
In this work, we analyze two sampling methods commonly studied in the literature: the r-leaping method 66] [1] [2] and the uniformization method [14] 16 23). To explain these two methods, since it is hard to directly sample from continuous-time reversal process, we divide the total time horizon [0, T 8] into N small intervals, such that to = and IN
ô. Given the estimated score 8
we define the estimated reverse rate matrix as
Q,, (x, v) QT (U, 8T (y, .)).
In the r-leaping sampling method 6 22), for given Fzy the next state is given by T2z41 =
EE (s ) Pr.ce where P.e is Poisson random variable with mean Q (#e, Fea + (s vi, (tx((+111111 - tx). Intuitively, this method can approximate the sampling process by simultaneously applying all transitions in the time interval [4x, (x))). Equivalently, on each interval [4x, (k+1), T- leaping approximates the piecewise constant Q (z. y) with a proxy (z. y) such that Qr(Ta,.)) Q v) (6)
The uniformization sampling method 2 has been proven to be able to exactly simulate the time-inhomogeneous CTMC by constructing a Poisson process with piecewise constant inten- sity {>=)==o...,B-1 (thus comes the name uniformization). Here it is required that X 2 sup=e[s) (- (x) At each time interval [4x, (x+1), the number of transition times M2 is first sampled from a Poisson random variable with mean As (ts+1 - t.). Then, each transition
In practice, an additional clipping step is necessary avoid boundary crossing behaviors. As shown in [5 such step does not affect the convergence rate given sufficiently small step-sizes (cf. [15 Remark A.13)).

---

time is drawn uniformly over [tx, tx+1) which forms set (or {o:):= Finally, for each of these transition times o,, each dimension of the current state x is transitioned to (# x²) with probability Ax Qo (I, + - x²) )..)
3
Main Results
In this section, we provide the convergence results for discrete diffusion models with the absorbing rate matrix.
3.1 Initialization through Surrogate Distribution
The initialization error of the sampling process closely depends on the convergence rate of the forward process under the absorbing rate matrix. To this end, we first characterize the evolution of the conditional and marginal distributions in the forward process in the following lemma. The proof is deferred to Appendix C
Proposition 1. Fix any time > and dimension i E [d]. Define the token transition probability for a, E [5). Then,
mairis of q as Po such that (a, b)
P (1 (1===(-E MASK] + T Accordingly, if we similarly define the overall transition probability matrix of qejo as Po.t, then
Po, [11 ss +e"
where & represents the tensor product. Also, the marginal distribution qu satisfies
qf = 2b (1 (1-c-")1seTuaa)) + e II' Rd
Intuitively, with the absorbing rate matrix, Proposition I shows that the probability for each non-mask token to still remain in its original state at time is If the state of the token changes, the only possibility transition [MASK] (i.e., with probability 1 et) Once the token enters the mask state, it stays there forever. Thus, with sufficient large terminal time T, the marginal distribution gr converges to the stationary distribution, which is (fMAsKK) )8d
One main challenge in the analysis under the absorbing rate is that if we select the stationary distribution (6]MASK]) ) for initialization, the initialization error will diverge in KL-divergence because of the log 0 term introduced for any x E [S] such that 3i x² * f[MASK] and that (r(x) > Such a problem does not exist for the previous studies of the uniform-rate case where the stationary distribution is the uniform distribution over the state space. To address such an issue, we design surrogate initial distribution to avoid the singleton distribution:
Rd
Pinst
(1 - (1-E)))OAAS +
S-1
GT
Σ
8j
57
where er > 0 is a small positive constant that vanishes T co. Here, instead of the stationary distribution, the above surrogate initialization distribution is asymptotically a singleton that located at (6 MASK)) @dd as T + co. For any finite é7, small mass is distributed equally across all non-mask states on each dimension. With such an initialization, the Kl.-divergence is bounded away from infinity as long as ET is finite. We then characterize its initialization ertor in the following theorem.
The proof is given in Appendix [
Theorem 1. Consider the surrogate initialization distribution Then we have
in Equation 3 and let eg =T
(L(grllpinde de de-T.
New analysis approach: Our analysis is different from the existing approaches using log-Sobolev inequalities [1 15 16). Specifically, it has been shown that if the rate matrix of the CTMC satisfies modified lobolee inequality 24 25 then the initialization emorr (i.e., the mixing time) can be well controlled (i.e., having exponential decay). Verifying such modified log-Sobolev constant typically requires that the rate matrix is symmetric. This is not the case, however, for the absorbing
5

---

rate matrix, which is highly asymmetric. Instead, we use a censen-based approach similar to the case of continuous diffusion models in [26]. Specifically, the key is to decompose the KL divergence into the difference of the (negative) entropy of the forward conditional distribution and the (negative) cross-entropy between the conditional and the initialization distribution. Then, we immediately obtain an upper bound for the initialization error given the analytical form of the conditional distribution under the absorbing transition kernel (from Proposition []. Notably, no extra assumption is required of the rate matrix. Our approach is not only more direct but also can be more generally applied to wider class of rate matrices, including non-symmetric ones and those without known log-Sobolev constants. Meanwhile, our result might have independent interest for investigating the mixing properties of general CTMCs.
3.2 Convergence Guarantees with Carly-Stopping
With the initialization distribution in (3), are now ready provide the convergence guarantees for both the r-leaping and uniformization methods. In this subsection, we focus on the setting with early-stopping. and will study that without early-stopping in Section 3.3
For the 7-leaping sampler, we adopt the following two assumptions, which have been commonly taken in the previous analyses under the uniform rate matrix [I5 16 17.
Assumption (Score Estimation Error). The estimated score function $1-4, satisfies
N-1
(l++1 - (S) S Escore.
k=U
Assumption 2 (Bounded Score Estimate). There exists M O such that Vz, y E [S] with Qr (y, x) > 0, the estimated score St, satisfies log 8T (v, a] S log M, 4k: = 1, I.
Assumption 2 is commonly adopted in the previous studies for uniform-rate discrete diffusion models (e.g.. 15 16). In practice, this can be satisfied with score-clipping during training [T6]. Indeed, the convergence error bounds in our main results only at most depend on log M.
The following theorem characterizes the convergence rate of rleappin under absorbing rate matrix. Theorem 2. Suppose that Po = Pinit in (3) and fx+1 t cmin
{1. T tx}. Also suppose that m(xa) S mo- = -(1) almost surely. Then, under Assumptions 1 and using the r-leaping sumpler yields, we have, as e, 6 +00 0,
(T, (PT-) S de + Escore + d(T + log( (T + log 8 1)2
N
where TQ 98) S d8. Thus, KT.(gs (e.ggsllr-A (pT if we choose T = log(d/s) and N = (ddee).
Theorem 2 provides the first convergence guarantee for absorbing discrete diffusion models using the r-leaping algorithm. Here, the target distribution qs is slightly perturbed from the true data distribution go due early-stopping Theorem indicates that (ddfe) steps are sufficient reach this slightly-perturbed target distribution Qs within an e-error in KI--iivrgence. Compared with the otate-of-the-art result of (d2) under the uniform rate in [15) our Theorem 2 shows improved dependency in d by a factor of (d) under the absorbing rate matrix. Indeed, such an improvement consistent with the empirical studies in [5] 9 II]. which shows an improved generation quality under the absorbing rate matrix compared to the uniform one. The complete proof is provided in
Appendix E
The key difference between our analysis and that under the uniform rate is on how to obtain upper and lower bounds for the score functions. As example, if one naively applies the same technique in the uniform rate case, one would only obtain an upper bound for (x, 2)) that is exponential in Our key insight here is that instead of uniform upper bound over all possible # y such that ad F y (cf. [66] Lemma 2] and [1] Assumption 4.4]), we only need an upper bound over those x and y such that Q2y, x) O, which, given the particular design of the absorbing rate matrix, small for all t > O. We have provided more details about the novelty of our approach in Section 4
Next, we conduct the convergence analysis for the uniformization sampler. We adopt the following slightly modified estimation assumption, which is typically required in the previous analysis of the uniformization sampler [14 15].
Indeed, as shown in Lemma the score function must blow up for certain cases when t -+ 0. For these cases, small perturbation around is necessary.

---

be avoided for Assumption 3 (Uniform Score Estimation Error), The estimated score function śr-t satisfies
Jo L S Escore
Theorem 3. Suppose that (y, x 81 2) when (y- (y. Ak S (ettee)sssrtttttta.a)) Kl(gsllpr-o) S de-T E
0. t tx c and Then, under Assumption as c, 8 + O, we have
where (go: ga) dō. Thus, KL(gs (1TT S by choosing T log(d/e), for which case E[N] = (d(log log(d/s) log ()).
Theorem B is the first convergence guarantee for absorbing discrete diffusion models under the uniformization sampler. For small enough ö, in order to reach s-level KL-divergence accuracy, Theorem shows that the expected number of steps grows as (log log e-1 This improves that
under the uniform rate, where Ollo e steps on average is required 14 15I. The underlying reason lies in the score function St when becomes large. For uniform CTMC, since the stationary distribution is uniform, & is close to a constant for which a constant-level uniformization intensity required. In comparison, for absorbing CTMC, since the stationary distribution is singleton, 8 decays as 1 for large l's (see Lemma D. which enables a much lower uniformization intensity and reduces the total expected number of steps. The proof of Theorem 3 is given in Appendix F
3.3 Convergence Guarantees without Early-Stopping
While the carly-stopping technique ensures theoretical guarantees, it comes at a cost of degraded sample quality. Indeed, even a small perturbation around = O might introduce a large difference show that the early-stopping in the overall woglliiklhhood. In the following, absorbing discrete diffusion models with the following assumption.
Assumption 4. Suppose that for all i [d] and x- [S]d-1,
(MASK]] ' max [ (MAASK] 26 (a(a((=-1 27>0.
Here, Assumption is made only on the initial data. This assumption can be justified as nearly necessary for the validity of the diffusion algorithm, as follows. By the second part of Lemma 2 Assumption is not satisfied, the score function will (nearly) diverge around / = Since the
algorithm relies on the score function to make progress at each step, such divergence at / = 0 would render the algorithm itself invalid in that regime. To satisfy Assumption a sufficient condition is that qo has full support over [S]d (albeit without explicit y), i.c., when [MAK] corresponds to one of the existing tokens in the training data. Also note that Assumption larger y when this chosen token becomes more likely.
can be satisfied with a
Comparison with other assumptions in the literature: We compare Assumption with two other assumptions in the existing literature under which the early stopping can be removed. Particularly, 16 Assumption 2] assumes that go has full support and that the score 8o(y, 2) can be upper-bounded by uniform constant for all and where only one component differs, and [15] Assumption 4.5] assumes some Lipschitz continuity condition for the score function when R O. Our Assumption relaxes [16, Assumption 2] and only requires that qo to have full support. While Assumption 4 does not have a direct comparison with (15) Assumption 4.5], as justified above, it is (nearly) necessary to ensure the validity of the diffusion algorithm.
In the following, we provide the convergence guarantee for r-lepping sampler without early stopping.
Theorem 4. Take J = O. Suppose that Assumptions 7 2 and hold. Also suppose that m(#n) S mo ((1) almost surely. Then, choosing tx+1 ty have
T KT(golleT) S de- + Excore 7 - + log(My N
Thus, KL(gol(pT) & by choosing T log(d/E) and N = ō (dy-1/E)
Therefore, when Assumption is satisfied, Theorem 4 shows that we can exactly recover the data distribution without carly-stopping, by taking constant step-sizes for O(d/s) steps. Also note that
7

---

the number of required steps decreases increases. Intuitively speaking, the generation becomes faster when the chosen [MASK] token already occurs likely the original data.
Novel analysis approach: The proof is given in Appendix G One key component in the proof is to provide non-diverging upper-bound on the score when s To this end, we first invoke the exact expression of s; (see (21)). Then, our key insight is that given an initial mask state. it will stay there for any t O, which guarantees that the denominator of (y, (which corresponds to q (x) with at least one mask state in 2)) does not vanish for small & (Lemma 66. Indeed, to strengthen this, we also show an almos converse result to this: Suppose that [MASK] does not occur at all in the initial data, the score function must blow up when t = 0 (see second part of Lemma
For the uniformization sampler, we also establish the convergence guarantee without early-stopping. whose proof is give in Appendix H
Theorem 5. Take 8 Suppose that Assumptions and 4 hold. Then, choosing S ( x 8T 8T- x) when QT- xr) > 0, 4++1 - 1x = C. and Ak S SuPPE[S] (= (-Q x)), and letting 0, we have
KL (IT)) S de- + E'score'
Thus, (L(qullpr) S by choosing T = log(d/e) and [E[N] = O (og(/e) +7
Theorem is the first con-early-stopping result for the uniformization sampler. Note that for uniform CTMC, early-stopping typically required use the uniformization algorithm [1 15]. The proof
of Theorem 5 is straightforward by combining elements from Theorems and
4 Overview of Key Proof Techniques
In this section, we highlight the major novel elements in our proofs. We first focus on the case with early-stopping, and we identify any differences towards the end of this section. Given > 0, the TV distance under absorbing rate matrix has an upper bound similar the uniform-rate case (see Lemma 4) Thus, as follows, we focus on deriving the KI. error bound for both the uniformization and the r-leaping samplers.
Following 15 Corollary 3.4), the error in the KL-divergence can be decomposed as
(ir-slllrr-)) z (L(oollPa) + f Cs
For the uniformization method, if we assume uniform score estimation error in Assumption 3 and since we can sample exactly from the time-inhomogeneous process induced by & using the uniformization method, then (T. (|PT-s) KL (Ipo) + e'ccrre Meanwhile, the total number of steps is a Poisson r.v., whose mean satisfies that
EIN S EB kmo Je(l,, EEwnya 8 -u, ((,,)) (tx+1 - 4x).
For the case with r-leaping, an error corresponding to time-discretization will be introduced. Under Assumption I and following straight-forward error decomposition, the total error has an upper bound given by (where we have combined Equations (14) to (16))
KL S KT(Ãoolpo Eocore +
N-1 fla12 km
ST (y, Itt)) š
log
(v, Itte 1sT ( xl, 31- Zr. QQ,, )dt
(5)
Thus, for both the uniformization method and the r-leaping algorithm, the results Theorem 2 Theorem 5 can be established as long (i) have sxponentially-decayin upper bound for the initialization eтror under the absorbing rate matrix, and (ii) the score functions sy (y, x) have nice upper and lower bounds for t E [8, T). Here lower bound is necessary because of the log operator. As follows, we provide the details of all these missing pieces.
Convergence of Forward Process (Theorem I)
In establishing the exponentially-decayin ini- tialization error bound, we cannot directly invoke the log-Sobolce inequalities for the mixing time
"This becomes an exact converse when we further assume homogeneity in the data across each dimension. ie.. when (a) = (a) for all E [d] and E [S].

---

of a Markov chain (as in [14 15 [6]] because the absorbing rate matrix does not have a known log-Sod Bog-Sobolev constant. Instead, we decompose the KL-divergence as (Equations and
(L(grlIPssst)
S Baj gb 1o [log o (z)) - log pl (xt)))
where the last line follows from Jensen's 's inequality since l'(u) = u log u is convex and the fact that the forward process is conditionally independent across the dimensions. Also, since have the analytical form of o:jo from Proposition (cf. Equation (9) and the initialization distribution from
Equation (3). the result is straight- forward. In particular, the exponential decay in T is due to the fact that 4/o0 (MASSK]a²) = e for all zó & [MASK]. Note that our approach is also applicable the case with uniform rate matrix or more generally to any CTMC with conditionally independent rate. This highlights the generality of our approach.
General Score Upper Bound (Lemma I] The upper bound on (y,, is essential to further providing an upper bound for the number of steps using uniformization (see Equation (4) and that for the discretization error using the 7-leaping sampler (see Equation (5). To this end, we simply
follow the technique for uniform rate (cf. [16] Lemma 2)), we would get (cf. Equation (20)
( [=g) % (w/ [x]]
sr(y, x) = Ee (11z)
< I-e" for all x and y s.t. only x' + yy.
This is problematic because the bound is exponential in T for t E [8, [8. Our key insight in the analysis is that instead of uniform upper bound over all possible x * y such that x * y², from Equations (4) and 5 we only need an upper bound over those and such that Q x) > 0. Given the absorbing rate matrix, this is equivalent to the case where x [MASK] while y & [MASK].
Now, given that Quv, a) > O, the upper bound for (e x) can be significantly improved
$t (y. .) = 1-e-r Lo (0011))) & t-,, for all x and y s.t. Quy. x) > O.
e-
Note that this upper bound decays as 1-1 for large I, which is much faster than under the uniform rate matrix (where the score is asymptotically a constant). This enables us to design much lower intensity for the uniformization algorithm for large I's, thus significantly reducing the total expected number of steps. Also, for r-leaping, this score upper bound is also essential to control the rate of change in the score and thus the term [ Tt, -T (y, xxt)) in (5) (see Lemma 3).
General Score Lower Bound (Lemma 2): The upper bound by itself is not sufficient for the analysis using leaping because of the log operator in Equation (5). For this reason, we also need to provide a score lower bound when Q 22 > O, especially for the region where is small. From the expression of st, one key element is (dje((l())) which by Bayes' rule is equal to
En seispd co(u ",9r) Vejola and o UM C (x) = Eate(s E. seisid go(a s,a2) vejo 2uM ممر ".a)""
(6)
Here we explicitly decompose into three different parts: (i) UM which the unmasked compo- nents x, (ii) ممA which is the masked components except the j-th one, and (ii) x², which is equal to [MASK] since Q(y,2) z) > 0. Here, for each fixed xg = (u a²), only the conditional probability at the j-th element would differ for different a², which indicates that the lower bound in- dependent of d. Also, intuitively, in terms of f, this lower bound should decay no faster than the worst rate of the conditional probability, which is e e' Interestingly, for the case where x/ * [MASK] a.s. for all i E [d], our approach would result in an improved lower bound, which diverges as t + 0 at rate that matches that of the upper bound (i.e., 11). This not only highlights the tightness of our bounds but also contributes to the general understanding of the score function, which might potentially be useful during training.
Non-dived Non-diverging Score Upper Bound (Lemma 6) Now we consider the case where carly-stopping can be removed. For both analyses using the uniformization and the -lleaping algorithms. the goal is to provide a non-diverging upper bound on st (y x) when Q x) > 0 (see Equations (4) and (5) Now, from the exact expression of 9o (3² (x) in (6) suppose that Assumption holds, then the
go qo(u- [MASK]) terms in the denominator would introduce a constant lower bound independent of t when t is small. This would result in an upper bound of (v. æ), which also does not depend on t.

---

Conclusion
In this paper, we have provided the first convergence rate analysis for discrete diffusion models under the absorbing rate matrix. We have first introduced surrogate initialization distribution to address the challenge due to the ill-defined KL. divergence. We have then established the first convergence guarantees for both the r-leaping and uniformization samplers, demonstrating improved rates over their counterparts using uniform rate matrices. Furthermore, under suitable assumptions, we have provided convergence guarantees without early-stopping. One future direction is to provide guarantees for the conditional generation of discrete diffusion models, where the absorbing rates would depend on the particular form of conditioning.
Acknowledgments and Disclosure of Funding
The work of Y. Liang, N. Shroff and Y. Liang was supported in part by the U.S. National Science Foundation under the grants: NSF AI Institute (AI-EDGE) 21 2112471, MMMS-213415,, CNS-2312836, CNS-2223452, CNS-2225561, and was sponsored by the Army Research Laboratory under Coopera- tive Agreement Number W91 INF-23-2-0225. The work of R. Huang and L. Lai was supported in part by the U.S. National Science Foundation under the grants: CCF-2232907 and ECCS-2448200 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Jascha Sohl- Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 2256-2265, 2015.
[2] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840-6851, 2020.
[3] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8794, 2021.
[4] Rongjie Huang, Jiawei Huang, Dongchao Yang. Yi Ren, Luping Liu, Mingze Li, Zhenhui Ye, Jinglin Liu, Xiang Yin, and Zhou Zhao. Make-an-audio: Text-oo-audio generation with prompt-enhanced diffusion models. In International Conference on Machine Learning, pages 13916-13932. PMLR, 2023.
[5] Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In A. Beygelzimer, Y. Dauphin, Liang, Jnd J. Wortman Vaughan, editors, Advances Neural Information Processing Systems, 2021.
[6] Andrew Camphell, Joe Benton, Valentin De Bortoli, Tom Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems, 2022.
[7] Chengyi Liu, Wenqi Fan, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: methods and applications. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023.
[8] Amira Alakhdar, Barnabas Poezos, and Newell Washburn. Diffusion models in de novo drug design. Journal of Chemical Information and Modeling, (4(119)7238-7255) 10 2024.
[9] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 32819-32848 2024.
[10] Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis Titsias. Simplified and generalized masked diffusion for discrete data. Advances in neural information processing systems, 37:103131-1033 2024.
10

---

[11] Jingyang Ou, Shen Nie, Kaiwen Xue, Fengqi Zhu, Jiacheng Sun, Zhenguo Li, and Chongxuan Li. Your absorbing discrete diffusion secretly models the conditional distributions of clean data. arXiv preprini arXiv:2406.00373, 2024.
[12] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Pupers), 2019.
[13] Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predieh Parallel decoding conditional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNIP)), 2019.
[14] Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffusion model: Exact implementation through uniformization. arXiv preprint arXiv:2402.0809. 2024.
[15] Yinuo Ren, Haoxuan Chen, Grant M. Rotskoff, and Lexing Ying. How discrete and continuous diffusion meet: Comprehensive analysis of discrete diffusion models via stochastic integral framework. In The Thirteenth International Conference on Learning Representations, 2025.
[16] Zikun Zhang, Zixiang Chen, and Quanquan Gu. Convergence of score-based discrete diffusion models: A discrete-ting timeetteeemeeeeeeee analysis. In The Thirteenth International Conference on Learning Representations, 2025.
[17] Le- Tuyet-t-NNi Pham, Dario Shariatian, Antonio Ocello, Giovanni Conforti, and Alain Durmus. Discrete markov probabilistic models. arXiv preprint arXiv:2502.07939 2025.
[18] Subham Sekhar Sahoo, Marianne Arriola, Aaron Gokaslan, Edgar Mariano Marroquin, Alexan- der M Rush, Yair Schiff, Justin Chiu, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[19] Matthias Plasser, Silvan Peter, and Gerhard Widmer. Discrete diffusion probabilistic models for symbolic music generation. Edith Elkind, editor, Proceedings of the Thirty-Second Interna- tional Joint Conference Artificial Intelligence. IJCAI-23, pages Joint Conferences on Artificial Intelligence Organization, 8 2023. Al and Arts.
International
[20] Seul Lee, Karsten Kreis, Srimukh Prasad Veccham, Meng Liu, Danny Reidenbach, Yuxing Peng. Saee Paliwal, Weili Nie, and Arash Vahdat. Genmol: A drug discovery generalist with discrete diffusion. arXiv preprint arXiv:2501.061: 2025.
[21] Frank P. Kelly. Reversibility and Stochastic Nenworks. Cambridge University Press, 2011.
[22] Daniel T. Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of Chemical Physics, 11164))776-1133,, 07 2001.
[23] Nico M Van Dijk. Uniformization for nonhomogeneous markov chains. Operations research letters, 1265):283-291, 1992.
[24] Persi Diaconis and Laurent Saloff-Coste. Logarithmic sobolev incqualities for finite markov chains. The Annals of Applied Probability, 6(3):695-750, 1996.
[25] Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev incqualities in discrete settings. Journal of Theoretical Probability, 19:289-336, 2006.
[26] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: user-friendly bounds under minimal smoothness assumptions. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[27] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances neural 2021.
information processing systems,

---

[28] Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous timmeemuuu--eeeeeee discrete diffusion models. In The Eleventh International Conference on Learning Representa- lions, 2023.
[29] Chenlin Meng, Kristy Choi, Jiaming Song, and Stefano Ermon. Concrete score matching: Generalized score matching for discrete data. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[30] Yair Schiff, Subham Sekhar Sahoo, Hao Phung, Guanghan Wang. Sam Boshar, Hugo Dalla- torre, Bernardo P de Almeida, Alexander M Rush, Thomas PIERROT, and Volodymyr Kuleshov. Simple guidance mechanisms for discrete diffusion models. In The Thirteenth International Conference Learning Representations, 2025.
[31] Chenyu Wang, Masatoshi Uehara, Yichun He, Amy Wang, Avantika Lal, Tommi Jaakkola, Sergey Levine, Aviv Regev, Hanchen, and Tommaso Biancalani. Fine-tuning discrete diffusion models via reward optimization with applications to DNA and protein design. The Thirleenth International Conference on Learning Representations, 2025.
[32] Nate Gruver, Samuel Don Stanton, Nathan C. Frey, Tim G. J. Rudner, Isidro Hotzel, Julien Lafrance- Vanasse, Arvind Rajpal, Kyunghyun Cho, and Andrew Gordon Wilson. Protein design with guided discrete diffusion. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023.
[33] Ye Zhu, Yu Wu, Kyle Olszewski, Jian Ren, Sergey Tulyakov, and Yan Yan. Discrete contrastive diffusion for cross-modal music and image generation. In The Eleventh International Conference on Learning Representations, 2023.
[34] Lin Zheng, Jianbo Yuan, Lei Yu, and Lingpeng Kong. A reparameterized discrete diffusion model for text generation. In First Conference on Language Modeling, 2024.
[35] Kun Zhou, Yifan Li, Xin Zhao, and Ji-Rong Wen. Diffusion-NAT: Self self-prompting discrete diffusion for con-autoregressive text generation. In Yvette Graham and Matthew Purver, editors, Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 1438-1451, St. Julian's s, Malta, March 2024. Association for Computational Linguistics.
[36] Yongxing Zhang, Donglin Yang, and Renjie Liao. Symmetricdiffuser: Learning discrete diffusion models finite symmetric groups. In The Thirteenth International Conference Learning Representations, 2025.
[37] Yixiu Zhao, Jiaxin Shi, Feng Chen, Shaul Druckmann, Lester Mackey, and Scott Linderman. Informed correctors for discrete diffusion models. arXiv preprint arXiv:2407.21243. 2025.
[38] Jarrid Rector-Brooke Mohsin Hasan, Zhangzhi Peng, Cheng-Hao Liu, Sarthak Mittal, Nouha Dziri, Michael M. Bronstein, Pranam Chatterjee, Alexander Tong, and Joey Bose. Steering masked discrete diffusion models via discrete denoising posterior prediction. The Thirteenth International Conference Learning Representations, 2025.
[39] Shen Nie, Fenggi Zhu, Chao Du Tianyu Pang, Qian Liu, Guangtao Zeng, Min Lin, and Chongxuan Li. Scaling up masked diffusion models on text, In The Thirteenth International Conference Learning Representations, 2025.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We indicate our contributions and scope in the abstract, and we have dedicated subsections in the introduction that separately discuss our contributions and other related works.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We clearly state each assumption in the main results, discuss their applicability, and further compare them with assumptions from related work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide our assumptions in Assumptions to and a complete proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
14

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/ wwwggdee/oeeeuusiieeeeeeeeeoeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https)
/ haaigp.ccc//bbli/g/uuuddd////eed htw.:iddeee/ooeSuunnissiiioooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp/////..aeeeeccoopp//////aa/
16

---

Answer: [Yes]
Justification:
The research conducted in this paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses the theoretical analysis of the diffusion model and does not involve any societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper does not pose any risk related to data or models.
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
LLM is only used for paper editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standaaddard components.
Please refer LLM (https: hhtppp:///euriss.coo http:///arrrraeeeoooooo/a//////a for what should or should not be described.
19

---

Appendix
Related Works
20
List of Notations
21
Proof of Proposition
21
D Proof of Theorem |
22
E Proof of Theorem 2
24
Proof of Theorem 3
28
Proof of Theorem
28
Proof of Theorem
29
Proofs of SSupoorting Lemmas
30
Proof of Lemmal
30
Proof of Lemmal
30
Proof of Lemma
32
Proof of Lemma
33
1.5 Proof of Lemma
34
1.6
Proof of Lemma
34
Proof of Lemmal
35
A
Related Works
Discrete diffusion model
There have been plenty of empirical works discrete diffusion models. [ first proposed the concepts of the diffusion model with a non-equilibrium statistical physics framework, laying the theoretical foundations of the diffusion model. In addition to the continuous space diffusion, they also discussed the modeling and denoising of a binomial discrete diffusion process. Later, [27] proposed the Multinomial Diffusion model defined categorical variables through uniform transition kernel, pioneering the structure of directly modeling the discrete data. [5] introduced the Discrete Denoising Diffusion Probabilistic Model (D3PM) with the structured transition matrices generalize the Multinomial Diffusion. It is also (5) that first proposed the absorbing discrete diffusion models. 66] embedded the discrete diffusion model into the Continuous-Time Markov Chain framework, modeling the forward and reverse processes as CTMCs and naturally deriving the continuous-time ELBO. They also adopted the r-leaping algorithm instead of the exact simulation to sample the reverse process, which reduced the computational cost in the nigh-dimensional setting. To learn the discrete diffusion model, 5 and [6] directly approximated the reverse kernel. 22 and 29 proposed ratio matching and concrete score matching, respectively. Subsequently. 9 constructed the Score Entropy Discrete Diffusion models (SEDDs) by introducing the score entropy as a score matching counterpart to continuous diffusion, to extend the score matching to the discrete field.
Discrete diffusion models have demonstrated comparable or better performance than continuous diffusion models. D3PM 5 outperformed continuous DDPM on the CIFAR-10 10 dataset regarding log- likelihood. SEDD 9 achieved lower perplexity than existing diffusion models in language modeling. Moreover, extensive empirical studies demonstrated the advantages of the discrete diffusion model
20

---

in tasks such as genomic sequence and protein design 30 31 32 image 6
T0
33
music
6
33
NLP TO
18] and finite symmetric groups [6).
A Absorbing discrete diffusion model
Beyond general discrete diffusion models, there have been several empirical studies that are partic- ularly focused on the absorbing discrete diffusion models. [10] simplified the variational training objective a weighted integral of cross-entropy. They also proposed a state-dependent masking schedule, which allows rate adjustment dynamically with states for better generation quality. [ reparameterized the concrete score as the product of time-dependent scalar and lime-independent conditional distribution. Through this reparameterization, they built a Reparameterized Absorbing Discrete Diffusion (RADD) model without time to achieve efficient training and sampling. Similar to I0, g parameterized the reverse posterior based on the structures of the absorbing state and derived tighter continuous-
ELBO through noo-Blackwellization They also proposed a semi- autoregressive decoding method that allows sampling sequences of arbitrary length. (37] proposed an informed corrector for the absorbing diffusion models, for which they showed better performance than using the regular (uninformed) predictor-corteet
scheme for masked models. Building upon [8), (38] investigated the problem of fine-tuning an absorbing diffusion model by casting it as a Bayesian posterior sampling problem. They introduced the Discrete Denoising Posterior Prediction (DDPP) objective for efficient training and sampling from fine-tuned models. More recently, [39] further validated the better scalability of absorbing diffusion models than traditional autogressive models in language understanding tasks.
Convergence analyses on discrete diffusion model
14 applied the sampling algorithm based uniformization in the state space {0, 1)d Under the assumptions of score-entropy error and bounded score, they achieved a nearly linear dependence of the expected number of iterations on the dimension d. [16] performed analysis of discrete-time sampling scheme in the state space [S]d via the Girsanov theorem. The work of [14] and [16] are focused on the uniform discrete diffusion models. Under the assumption of the symmetric rate matrix, [15] introduced a stochastic integral framework and first provided the error bound of KL divergence for the r-leaping algorithm. Note that all of the works above are not applicable to the absorbing discrete diffusion model, which is the main focus in this paper.
B List of Notations
We write [xx = y} as a function of x and which equals I only if = y. For i = 1....,d, we write e is a vector where only the i-th element distribution of singleton whose p.m.f. is ej. For positive integer S. [S] == [I....,S}. Write 1s as a vector length that contains all I's, and Is as an identity matrix of size S. Write m(x) to denote the number of [MASK] states in the vector
and other elements are 0's, and we write 8, as the
C Proof of Proposition
Recall that we have Qtok the last token in the vocabulary. First, we perform the eigen-decomposittion of Qlok as
1se MASK] Is. Without loss of generality assume [MASK] = S. i...
Qtak PAP-1
I 0
0
I
0
0
1
0
1
0
:
diag( (0gg--120
(1,,..
0 0
0
I
0
0
1
Note that
exp [-]]
0
exp [-t]
0
exp [At]
0
21

---

Thus, solving the Kolmogorov forward equation, the transition probability matrix of the i-th token x² can be expressed as
Po. = exp
Q
tok
ds
= Pexp [At] p-1
Texp [-1
0
0
exp
exp
[-t]
0
1 exp
-t]
exp
|-1]
exp
[-
0
1
8x8
1
[MASK] [M[MASK]
Ig.
Since each token propagates independently in each dimension, then (00(()/ -II (1 and
Po. [ @d
()se te-1ls Ed
Hence, the marginal distribution Ør at time is
qf = o0 (1- ")se +e te' Rd
D Proof of Theorem
The proof idea is adapted from that for the continuous diffusion model first in [26). To start, we have
KL(gT[lPinst) = Σ (T())) log (r(TT)
Pinit(A7)
2
( log (p()
Σ
(r(oT) log (eni)(TT).
erE(s)4
Term;
Terma
We first focus on the first term in 77 Since
(π(T)) = Browgo [er)((<)(<о)]]
we have
Term
Σ Exorgoo [grlo(1r|za) log Exo [9r]o[01(20]]
Exgnngo ( log 9r ( (xT(20))
E
Σ
urjo(ar (20) log (ri
E Eggo o
Σ a+E|ss
( (26) log of (at
(8)
where (i) follows by Jensen's 's inequality since f(u) u log is convex, and (ti) follows because the negative entropy can be decomposed into a sum across each dimension when the transition kernel is independent. To proceed, need express the analytical solution for 4jp- From Proposition
(=/a) = [(1 - -e
[ASK]] +e [
(TTT(a((a2))
22

---

e
a = 2 + [MAKK]
1
e
if a + 2 = [MASK]
(9)
1
if = 2 [ASS
0
otherwise
Thus, using the convention that 0 Oog 0- = 0, we have
e loge -
afa== [ASKK]
(rio(2|a) [ log (t)o(2/a)= =
(1 - (1-c
log (1-
[AAK]]
0
otherwise
Then, when un a # [MASK], the negative entropy is
Σ
(r)o(=1/a) (a) log (1)
es.E|s]
Σ
( log 0r10(=1a) + (foo((MASK]])) log ((MAA
MASK]
(riolala) log o (ala) O
log log ([0AS))))))
=e- loge T + (1- e - - T.
Here (iii) follows because of the absorbing rate matrix. Otherwise, when 26 = [MASK].
Σ (ro(++||MAKK] log E).
= o (MASK)][ASKK) log 1 (MASK]](MASS))
0.
This yields that
d
Term
E - [1(26 + [MASK]J (6- loge (11 -1--"" "))=o)) E 7)
((((MS))])) ) (e-T(-T)-e-7 + (()-2T)
Σ aá (MASK])) e 1)
(10)
where (ir) follows, by Taylor expansion, that (1 x)) log(1 x) x 0xx²) when is small.
Now, let us turn to the second term in 7.. As follows we write c = cr for which we omit the T dependency. Note that the specified Pinst has independent components, and
[ 11-6, if x' [MASK] T
Pimix (x')
af 4 [MASK]
Here, 8, denotes a point mass distribution centered at state Thus,
Termy =
Σ
(xr) log (x)))
Σ
Σ
(010(27(20900(z0)
log (XT)
ETE[S|"
(v)
Egg Exr S Pogaa
(vi)
E Eno En [lo Plmse (xf))
23

---

d
(vit)
1 unj mo Busy 10 (1bb) [log Pénis (x/1))
1 (ar * [MASK]] (1-e=))log(1 - c) + e- log
B Baigugh
8 8-
Bag
[1 [1)) [MASK]]] log(1 -))
d (vi()
11x6 + [MASK]] (1-T-
Beeg ~6
1)e 1)e+ - -- -oog
$
2d (MAAK]] + O(de
(MASK]))))
(1-5-11c+e- log 5-1
d
- (MAAK))))) 6 de + O(de)
(11)
where (v) follows by changing the order of summation, (vi) follows because Pinit is independent across the dimensions, (ui) follows because the forward process is conditionally independent, and (viit) follows because by Taylor expansion, log(1 x) = - + O(x²) when x is small.
Now, combining 100 and together, have
Σ ([MASK)))
KL(grl Pinit) S de
T' 1-T-1)-(6 -1)c - c (s 6
s s-1 -c)
S de -T (1-T- 1) - c-log ( E
5-1 )
Now, we can choose = -T Thuss
e -
KL(qrlIPinat) S de-F T + -T -1- -e -log
5-1
S -T
E Proof of Theorem 2
First, using the Girsanov change-of-measure technique similar to
15
Corollary 3.4], get
- S ([((oor--/lprrr-)))
-KL(Tollpo)+
-1) ST sT + sT- log 8T (1, 2z.) 8T 8T xxe)
Σ
Quy xz)dt
-KL(Eullpu)+
N-1
8T (1) sT- ST ST b0u, log 8T (y,1
Exinit
Σ
Q Q(u,sr)) xx)
di
8T to (v. xxa)
KLoolllpo)+

---

N-11
fe+1
Σ
(U,
- ( xx)) dl
where we have defined that
G(æ;y) == 2: log x
x.
(12)
Note that Qr Q due to homogeneity, From Theorem the initialization error term has an upper bound as
Linat KL lpo) $ de
Also note that the estimation error satisfies
N-1
Lest ==
Σ (t++1 -tx)
k=
Esy, mie
Σ
(sT-1e (1, +
8r (1, Q(v, )t,) S Escore (13)
Thus, find the discretization error to be
N
Ldisc
Σ
di Lest
k=0
N-1
dt.
k=0
senele Σ Cilc (4n D10 x(.)
S4y with ytz!
dt-
E simli soy with yosrre
Σ (1 (v, (,, vt.)
+ Bezyy with
Σ yEur
xt,, (r,,::/0,.-.a.-.-...----------,, Q m.,)
(14)
Here, for (i), note that 87 (g. 81-11 21 QQ( (ly,, for the r-leaping algo- rithm.
We first focus on the first term in the discretization error, which is
dt ai
Σ (o
K=D
AN
zey mit
dt Exenit (lorr-ddo--)))rrr--0000000010111
Σ 4T Ar- (1t)
m4 4
yosu
dt Ex Σ
Q(21, Ite)
Σ ((s
F4 E(S)d
25

---

N-1 Met1
dt (t - tx)d Euryat mite
Σ
((sT=:(,,aa)isTT- (y, )Q [3,, I(e.
(181) N-1
N-1
(1+11 - 11) dLest + d
Σ
di(l (4)
km0
km0
Euree wi
Σ
(G(ST- 88 (y, (t,)) - G( & (v, (i))
(10) o(R (Escore Ldisc))
(15)
where (2) follows because by definition of CTMC -eje-ar (u)=))(y(x) S 6ø. + Q(r,)) (ti) follows because there are (dd) non-zero terms in (0 st,,) and because (x(r) Tt, (x) = O(t 4x) for each [S] (izi) follows because of (13) and that -r, (v. 3t, (Q Ft,)) > 0 when y * Nea and (tv) follows as long as
Σ yF
(G (1, Ita)) G (g) Ita
Quy. xv.) O t&).
Hence, this term does not contribute to the overall upper bound in (14 Thus, it remains to upper- bound the second term (I4) for all t [ts, 1x+1), which the key is to upper-bound its integrand given by
Σ
(G(sT-o(y, Ft, 81 (v.) G(sr-ta T.. (v. (v. xı, xI.)
8T 81 :tee) log
S Eryg Ti
(8T, ST ST (u+ It, Q(y,
(16)
8T (y, xtt)
y
where the inequality comes from the fact that G(aa;)) y) is continuous and dz G( y) log う
To proceed, we need to investigate 8t under the absorbing rate. The following lemmas investigate some properties of st. Their proofs are in Appendix Lemma 1 (Score Upper Bound). Fix > and æ + y such that Qely, x) > O. Let j be the only index such that x² + y². Then, xd [MASK], and we have
e
sely,2)) 1 1 e-t (1)
Lemma 2 (Score Lower Bound), Fix 0 and x, E [S]a. Given that Q(y,z) > and that 4:(v) > 0, we have
sr(y,x) Z et
Further, suppose that dt (MMAS]) for all E [d], then a tighter lower bound can be applied:
1
se x
Here note that sx(y,2) x) diverges at the same rate as does the upper bound as I + Lemma 3 (Score Derivative Upper Bound), Suppose that the number of masks in the data satisfies m(xa) S mg = Ô(1) almost surely. Given that Q(y, x.) > O, we have
i
e¹
se 2)) Ot
S -e'- 5
Let now continue upper-bound the second term in Lemmas and 2 direct implication that, when Q x)) > 0 and qi (y) > O,
14 With the score upper and lower bounds
loog (v. x) S max{[logt
'I, log(e log S T - log d log S.
(17)
26

---

Without loss of generality assume that -r-44 (v) 0 Now. continuing (16). note that
G(sT-c x); -1 (v, x)) G (v, ST - (y.z))
x log 8 (v,
1ST ( x) -T (1, 2)
8T 14 (y,
S (T + log + log M) ( (v, x) - 8T t4 (y,
(18)
where the last line follows from and because log šy ( x) - log M when Qv,, > 0 from Assumption 2
Recall that & E [4x, (R+1). Thus, an upper bound for the second term in 14 is
Bay, 1
Σ
(G(ST- Di,)) &T (y, It,) G(ST-ta (2), Iz, ST en (V, x(, Quv x.,))
(T + log 8'1 + +lgg MM M) with
Σ
|ST (1V,
ST (3) Fz Q v11)
yd
$ (t- (T' + log 8-1 log M Mlx Nop
Σ
sup ME(T to 1 1. tx)
de se (y, x4)
2) 21
(8) S (t- + log 8-1 logo- + log MT tx+11 2d
where (i) follows from (88 and (ii) follows from Lemma
Combining all results for the discretization error, we arrive at
N
Laise
dt
km0
Bisg Titk
Σ
(1,
(y. x+,)) - (1, 6r
(y, x4,) Q(y, si.))
N-1 (1x+1 - 42) max (1, (T - -2
$ (T + log 0 +- log d
Σ
Finally, to determine the parameter dependency in the summation, we can directly employ 26 Lemma 18] and get that when 1++1 14 emin {1,T T (x), have
(T log 8 12
Lasec S (T log 8-1 + log M)d
N
Furthermore, taking t4+1 4 emin {1, - tx). the number of steps satisfies that N S 1T 1og8-1). With this, we arrive that
KLL S de + Escore + d(T + log (og(M--1)) (T + log 8-1)2
N
as desired.
Finally, the following lemma, whose proof Appendix | provides an upper bound in TV distance between go and qs- The proof is similar to the uniform-rate case as in [14 Theorem 6).
Lemma 4. Under the absorbing rate function, we have
(go. q8) S d5, as 8 + O.
The proof of Theorem is now complete.
"Indeed, if (v( > 0, then by the absorbing rate property, we have gi(y) > for all t > s. This implies that if (v) = 0, then (r)) 0 for all t E (tx, t. For this case, trivially we have G(sr- (0,, x); = 0 for all E [ta, [1]... where the difference is simply 0.
27

---

Proof of Theorem 3
is shown in [15] that uniformization can exactly simulate the reverse process without discretization emoor Thus, from [15 Corollary 3.4], we have
KL(ūT-ollpe 6) S (L(Tollpo)
T-
ST SV- vit) - + s7-1 log
Exoo i-
Quy. xz
dt
B7 3 xx)
S -T E'corre
where the last line follows from Theorem and Assumption 3 note that we still have TV (4o, Qs) X dó due to the early-stopping.
Similarly to the proof of Theorem 2
now remains to determine the number of steps, which is usually a Poisson random variable due to simulating the CTMC process. Now, for each interval [tx, t&+1). uniformization requires that
A 2 s (E((s)))))) (x, As follows, we first provide an upper bound for 2 using the following lemma.
Lemma 5. Fix >> 0 and such that [MASK] E Recall that m(x) (S d) is the number of [MASK] in x. Then,
Σ sely, wozf
I-e-t S m(xx)(
Thus, under the assumption that ST ST-1(y, ST-c(U, x)) when Qr- 2)) 0, we have
-((1x))= = Σ Q.(z.))= = Σ ( S d(T - -)
Note that different from the case under uniform rate, this upper bound is vanishing for large (T - -t'ss. Thus, since the sum of independent Pois(A&) n.vs is distributed Pois( E Ax). the expectation of the total number of steps is given by
B-1
B[N]
Σ
A (1++1 - -44)
k=
B-1
2 d(T - +x+11) - - tx).
k=0
Now, since choose constant step-sizes as 1x+1 1g C,
E[N] S d
(bx+1 tx)
T
1x41
k==
B 3-1
(IT (x) (T (+1))
tx+1
k=
1
S d
7
d(log T + log 8 8-1)
Plugging in T log(d/e) completes the proof.
G Proof of Theorem
In order to provide convergence guarantees without-early stopping, we need to provide a tighter upper bound for the score function 8, (y.x)) .)) (given Q(y, .r) > 0), which does not diverge for small L's. Thus, the following lemmas provide improved upper-bounds when Assumption 4 holds. The proof is in Appendix[
28

---

Lemma 6. Suppose that Assumption 4 holld.. Fixt 2 0 and x # y such that Qv( > 0. We have the following improved upper bound for syi
ST {
se S min I1--
In particular, this bound does not diverge as - O. Lemma 7. Suppose that Assumption / holds. Suppose that the number of masks in the data satisfies
m(xo)= S mg = (1) almost surely. Given that Q(y, x) > O, we have
① 0t
e²
$t
(v, x)
S min
(et - 1)2: ST
Also, note that the general lower bound in Lemma still holds regardless of Assumption !
still
The rest of the proof is similar as Theorem 2 for which we provide outline below. Now from Lemma 6 we have
llog (v) x T logy vt [].
Also, from Lemma
7 we have
- -s > (t s), vs <t
Thus,
Exg -
Σ
G(ST tu (3), Tx, - to (v, xr, 1)) Quy, Tww)
$ (T + log(My 1)
Exy with
Σ
(1,- 8T - (v, Q4v x1.)
$ (t - (T + My ddy
Continuing from 14p, we further have
Mk1 (fm (t
Ldisc
ta)dt) tt-tx)d
(T -log(M>>1)))0
N-1 Σ (1++1 - 14 k=0
x - + log( (og(M>1)))
Now, given fx+1 4 = c. (or equivalently. == k), we can derive that the total error is given by, without early-stopping,
(L(gull S de- + Eecore + +y + log(My-11) T N
H Proof of Theorem
The proof is straightforward by applying the modified score upper bound in Lemma 6 to the proof of Theorem 3 First, the upper bound for the total error the same as in Theorem 3 From Lemma when Assumption 4 holds, we have (B. x) I -- and thus
Σ Q((2.v)=
Σ Qr-((ux)3r--(u.t) S (T -f ".. BorF
Therefore, the expectation of the number of steps satisfies that
N-1
N-1
E[N]
A - (x) -
Σ
d (T (x+1) -1, .7 --,--11((641 (x)
Σ
d(T - (4+11 (1a+1 (x) Σ - (x))
k:T 1
kTT-4
S d(log T 1
Plugging in T = log(d/E) yields the desired result.
29

---

I Proofs of Supporting Lemmas
L.1 Proof of Lemma Following similar analysis as the proof of [16 Lemma 2] (and note that t >> 0), we have
Ae (v' (m))
2)) = Rx (-1z)
(19)
F (x)) (mn))
Let us now focus on this likelihood ratio. Recall the analytical expression for 4ho in ( In light of the expectation operator in (19), follows we only consider those 2n and x's such that (x)o(2)))))) > O. Then.
T (
if =f + [MASK]
oho (v' (xrg)
(1)
L (20)) (20g))
if * x² [MASK]
Gájo (11d (m)))
a/ x² = [MASK]
if of = x + [MASK] and '² [MASK]
(2))
if y = =b & x MASK]
(20)
otherwise
Here in (i) we only have three cases because if œ + [MASK] and 20 + x² (whether or not zg
MASK] itself), we have (x)(() 0 = 40jo (x) 0. Also for (ii) in order that
Lo (y w > O, we must have either yd = zg or y² = [MASK]. Meanwhile, we need to ensure that 3' * x!.
Now, note that if we naively provide an upper bound (indeed, as with the uniform rate), we would get (,,, x) S e - - c - 1. This is problematic and is due the highly asymmetric design in the rate matrix.
Instead, let now consider the condition that Quy, x) > O. By definition of the absorbing rate, since Qv(,x)) = Qtok (x²) > 0, x must be [MAKK]. Thus, it is impossible to have x² * [MASK] yet y [MASK] (since by definition the state will stay at [MASK] after reaching there, making such @v 0). This implies that only the second non-zero case in (00) is applicable when
Q x) O. Plugging back into 19 we have, when Q 2) >
(v) (x(x))
(x,,
Sale (N (1')x)), such that xf |MAKK.
Therefore, we have
1
st st
et st
1 1- e-
I,2 Proof of Lemma
From Lemma when Q(y. > 0, we have
-
(v, = 1-e-t 1z)()
Here j is the only index such that yd + x².
As follows we explicitly express 40g (y/ (z). To this end, we use the following notations. Given I, we write n and y. U for the masked and unmasked tokens in v, respectively. Since x [MASK] (from Lemma 1/. denote the masked tokens except x MV, For an arbitrary vector u E [S] write - E [s]-11 its j-th element excluded. Also write aM UM and M' as the tokens in that corresponding respectively to x: M UUM, and MV, Also, denote the number of masked tokens in as m(x), and m(x) [1, d]. We also slightly abuse the notation and write (r)o(("(>)) [z) = & (v (x)).
Using Bayes' rule, we have
Goje (o)e(y2(2)) [z) 90,021, w²)
(0. M. UUM y²)
96(x)) 9e (a xUMM
30

---

En-se[spa1 qo(u ( ,0) We1olie zUM lu-
EVeE Eu- qu(uu,, (2)) oltb (. wi Iyd
n 10) (0)
"s , x JUMMe und m(x)) (1 a -olaa M (ommem))
(M)ie(S)mm()
Mis a, LUM oid s(d- - "ee00( (1 al al [MASK] N (0)
Σ
Σ
Mu [MASK], JUMe 1(d (x)) 4 (aaea (
Here the last line follows by the definition of the forward absorbing-rate process, which is con- ditionally independent and using the absorbing-rate probabilities. Note that y² [MASK] and xd = [MASK]. Thus, using Lemmal we have an analytical expression for the score:
87 (v)
Σ
ao y2, .UMM ( v(d-m(x)) e- (0 (aaaaaaaas
Σ
qulu as LUM -ede-<<(dm=))) "e1 (1)
at ad [MASK] (i)
Mow MV [MAS]], UMM) (e-Me--udd- (dd-m(())) (2 (aar))))
(21)
We first provide a general lower bound. Observe that in both the numerator and the denominator above, the dependent components and the a² ov-vrrying components can be separated. Also, those time-dependent components are the same as long as a + [MASK]. Thus, continuing from (2T) and noting that 1 - - < 1, we have
(V,
ze
Mo M,M,,,,, UU)e t(d ((d-m(a)) (2) Mo (1ppa110)
20( ,0, JMM) tid m(x)) -1lla (I: M v/ (olueii )
Σ
('E(S) m(()-
2 el
Co MuuN,,,AC N,,UUM xUM) uld uldm wo
S max d'E[S]
MV M,a',, a², DUM) (()))-
Σ
( ild tld-m(x) gelo gljo
(
S
The last line is explained as follows. Note that the numerator is strictly positive because ge (v) > and thus s(y, O. Then, for set of non-negative numbers, any positive cą satisfies maxe Ck
min mine now co m 0. This yields the first result in the statement.
Ck
Next, we show an improved lower bound when de (MMAS)) = 0 for all i E [d]. Then, an implication that
(o Myi [MASK], x UM) 0, vj E [d].
Thus, from 21 following similar analysis.
31

---

Mo(u ,,y, suAM)e ((d) 1o 20 (ow /
(
E
go(u aad MMMM ((d_m(s)) gorrb 2i1o
al [[MASK] /
e
Σ
2o(un , auMMe -tddee--------e v(d-maa)) 2o Mo (ooloossss
1 6-
u
a E[S] (MASK]EW'y
Σ
E
yo a. U.M Me t(d (()-)(()) 20jo( v ppclrrss
o7 [|MASK]
u EE E|s [MASK]εu
28-1 c-
as claimed.
1.3 Proof of Lemma 3
Throughout we employ the same set of notations as in Lemma Given we write xM and UM for the masked and unmasked tokens in æ, respectively. Since x [MASK] (from Lemma I denote the masked tokens except x as MVj For an arbitrary vector its j-th element excluded, Also write wM, UMM, and MM as the tokens in u that corresponding respectively to x.M _UM, and v'V, Also, denote the number of masked tokens in m(r)) and m(r) E [1, d].
[S] write u [s| as
We consider the following two cases. First, suppose that x A [MASK] almost surely for all i E [d]. From [1] Theorem 1], we have
e- -- ad(lrru
se (y.
Here note that qú is time-independent "clean-data" distribution. Thus, the time-derivative of the score function is equal
8 0t
8 Ot
e
e² UMM)
st
x)
1-e
(e' 1)3 1C--1196611 (NU
which implies that
dy se (v. x)) S ( 1)2 2
sup ('(s.()]
Next, we consider the case where [MASK] is possibly in the data. We first recall the analytical expression of sr (),, in (21):
s((,,x)
Σ
MV M. ( -et--ty- (tyd-m(())) .t .( (1- e -1
- MV a², u. (e (m)) ) - E mm(
a tal [MASK] An (()
Σ
Mo [MASK], (e - -1
32

---

E
My yy, wllM) e (1 e) m mimui)) 
Σ
E
go(u a x uuM) ([ e ) -- -m
a3 * a (
Σ
vo(u [MASK] x GMM(( )1 e -) -m(((rr))
By assumption, here go [MASK], (
UM) > 0 for some whV,, Also, m(( S mo 0(1).
0 Observe that (V..x) is continuous in t. Taking the derivative of this ratio, we get क7 ( x) =
Ti - T2, where
vo(u M.y, .. JUMMe-t (1- (1-e-t)m(u W1 m(
+ -
Ti
el -1
Σ
Mo a² UMM (1 E f) -m mm
ah:at + MASK] m=)
vo(u>r [MASK], OMM) (-)-mm(utr))) (Mr
E
and
vo(u "auno,ypaaa (UM) . e (1 e-t)- m
T2 =
Σ
Vo a UUM (mm( - 1)e - -
-m(u
al:ad (MAAK) A (e(S)m())-)
[MASK], x UM mWu 7- (1 = --- -mpuuru
Σ
--e-t
Σ
Σ
MowuMs a², 2UM e -----m(w
[MASK] a (
Σ
Mo(uM [MASK], x. UM (1 - -) ---))-m(uhh))
Note the similarities in-between and with the expression of (y,, Since m(u S mg. we have
T S mg + e²
se(y,2)
et - 1
T2 (mo- 1)e
et (1),
+ 1-e-r)
e
Since mo = Ō(1) by assumption, using Lemma 1 we obtain that
i
se
x))
x (e' 1e² St t-
Note that this bound independent of d. The proof now complete.
L.4 Proof of Lemma
Write Il(go, 98) is the set of all joint probability measures with marginal distributions go and qs- Then,
(go. 98)
min
Ex.. 1(xs * 2o}
33

---

I Beoongo [asio (fas # øot [20]]
2030 (1a3 # 26) (zti
E [d]
(40)
Σ
dd(=))a500 (MASK]|=))
E d] m [MASK]
S (1 e 9
x d6
where (i) follows from the union bound, and (ii) follows from the conditional probabilities under the absorbing rate.
1.5 Proof of Lemma
From Lemma when Q(v.x) > O, we have
6-
(y(, 1-e-t 2 (1))),
where j is the only index such that y² & x [MASK]. Thus,
Σ ((U..))(u.z)=
= Σ
scly, QV).
v:Q(yx)>0
$t(v, x)
jun [ASKK] goos' [[MASK]
(8)
Σ
% (1' (x)
[MAS]] [MASK
m(x).
Here (i) follows because the only positive entry in Q x)) is 1, which corresponds to the case where Ham (y. 1, yd * [MASK], and zí = [MAS]], and (ii) follows by Lemma | thus established.
The claim is
I.6 Proof of Lemma
From Lemma
we already have upper bound for (yyy x)) when / is bounded away from O, which
is
s(y, = 1t
In the following, focus the case where becomes small.
We start from the exact analytical expression for (y. in Equation 21 given that Quy, xx) > which is
St (1,, x))
Σ
Ms M, UMM )e (ld-m(x)) - an (2 M (ullrrs)
20 a² UM ) un m(=))) - "4 -
o (are (ornoot
adia a MASK] w m(s
Σ
Ms [MASK], x UM je t(d-m()) gooo M M Mi (
Co MuA,,,, je -(dd- g00l
M (a (ann(ss)
34

---

go(un [MASK], LDM) t/d ((d))(x)) (1) A wo (alM)s)
E
1o .UM yoo .uAiee ild ((d-m(=)) 00:f (2.0))0))))) // ((nneee /
6([MAS]] J MW UM "0 DUMM uld =ld_m(x)) go10 (I (o (actrs))
Σ
ild ml()) (0 Mis Salilllly (ellrs) 20 (o goo Mi Je --t
(0
1o u -((d-((x)) (1000//0ua
max [M) a3 [MASK]
(22)
where (i) follows by Assumption 4 Note that this bound is uniform in t.
I.7 Proof of Lemma
When not small, we can invoke Lemma and get (1,, S কলー S 1. Thus, it suffices to get a non-diverging upper bound when / becomes small.
Recall the proof of Lemma in which we defined Ti and T2 such that dr sc x) Ti T2. For small E's, have (1 ") x and e x 1. Also note that m(xo) mo- Thus, for all such t's, we can further simplify both terms as
No G. UMM) 1t (1 e e (0-))mm(aa))) M13 Mi c¹ -
Σ
T
Σ
No a xx (UM) e -
at : + [IMASK]
a (()
Mu [MASK], UM - e) mm(aM())
WM (
MV 3/, UMMD )) mim ii m( e -1)
Σ
a M
Mo [MASK], I UM MMM(1 eー m
Mo y UUMM - c - mo + 6s
)---1)
6 61
Mammuu =mo
Σ
Mi, [MASK]. x. UM - oml-
WM (m((ur)))mmm
mo + el -1
En Mi, 3² _UM)
e1
Eudr 20 Mi [MASK], x UMM
and
T2 =
Σ (MsSsmm
go( V.y. 3², ZUM). -t
e (1 - (1---)--mle -
35

---

go(u ad 2MM)(m( (mm( Mis) - 110-0(1 - - -m(u(rrs) +
Σ
E
ah:al + a (()
- - m )
go(uM,, [MASK], - mi ( (1- -
Σ
1 - -
_
-
go Co Muu
" J - 1 - و ml uu (
Σ
Σ
c ( 
ahe [MAAK] MV ME(
co(u [MASK], 2UM)(1 
Σ
u u
vo(u 15, JMM) et (1 ( Son
E
MASK], a Tnl (
-
(1
-
[MASK), UM [1 (1-- - - -
/
E
co(u>
vo ,,, sLCM) e . (1 e) - m
M Won (w (w/r)))) =mo
Ny [MASK], UMM my- c (1 e =t) - mmo)
MASK] X 21 - - ) 2
Σ
WM M )=ma
E Eumusmamus=m Do Ms y2, ..UM
c EudNem(w Mo [MASK], ZUM)
Therefore, when & small,
8 01
86 (y, x))
= -ii -Tal
mo + - +1--1)
En EaMMsm(uM))=m (0 y8, xUM
mo
Eud(ssm(MM))=m (o [MASK], aee
E¹ c'
E MuM)emmaMM)==m Mo y², UUM)
E EuMVsm(uM))mm 2o Ms, [MASK], x UM)
---1
where the last inequality follows similarly as in (22) when Assumption 4 holds. The proof is now complete.
36


Reviews:
[{"review_id": "41Lk72oUDt", "reviewer": "Reviewer_gMRL", "summary": "This paper provides convergence rate analysis for discrete diffusion models using absorbing rate matrices.  The authors came up with a new way to handle the singleton distribution caused by the absorbing state. They also show that two popular sampling methods—τ-leaping and uniformization—work faster and better with absorbing rates than with uniform rates. They also find conditions where early stopping isn’t needed. Overall, this work shows that using the absorbing rate matrix can achieve convergence with fewer sampling steps—scaling linearly with the data dimension instead of quadratically", "questions": "There are some divergences which remain well-defined when the underlying distribution is a singleton or non a.c., e.g. the spread KL divergence [1].Do you think it is possible to use such divergence to get rid of the surrogate distribution?\n\n\n[1] [Spread Divegrence](https://arxiv.org/abs/1811.08968)", "limitations": "While the theoretical contributions are strong, the paper currently lacks empirical verification or practical demonstrations showing how the proposed convergence bounds translate to real-world implementations. For instance, it would be valuable to see whether the improved convergence rates under absorbing rate matrices indeed yield faster or higher-quality sampling in practice. Some plots would be useful to support the theoretical argument.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I’m not an expert in theoretical analysis of convergence rate for the discrete diffusion model. Here’s how I understand it:\n\n1. Quality and Clarity\nThe paper seems very solid and well-structured. The background is easy to understand, and the analysis is rigorous.  It would help if the authors explained more of the intuition behind their ideas, especially the surrogate initialisation method and what happens if you skip early stopping.\n\n3. Significance:\nThe paper is important because absorbing discrete diffusion models are becoming more common in areas like language and molecule generation. The authors provide the first convergence guarantee to explain why these models work so well in practice, and this could guide future research and the practical use of these models.\n\n4. Originality \nThe paper is novel since it focuses on absorbing rate matrices, which other papers haven’t analyzed in depth. The authors also come up with new ways to handle the unique challenges that come with these models, some of the techniques like  smooth surrogate distribution are intuitive and natural.\n\nLimitation:\nThe paper lacks of empirical evidence which supports the derived theory.", "was_revised": true, "final_justification": "I  am not an expert in the discrete diffusion theory and I do not have concerns left.", "rebuttal": "We thank the reviewer for carefully reading our work and providing encouraging and insightful feedback.\n\n**Q1:** Limitation: The paper lacks empirical evidence which supports the derived theory.\n\n**A1:** Please see our response in A3.\n\n**Q2:** There are some divergences which remain well-defined when the underlying distribution is a singleton or non a.c., e.g. the spread KL divergence. Do you think it is possible to use such divergence to get rid of the surrogate distribution?\n\n**A2:** We agree that spread-type divergences present a promising direction for potentially bypassing the surrogate initialization. It is worth noting, however, that applying spread-type divergences introduces its own challenges, as their rate-of-change w.r.t. time becomes hard to capture in the reverse CTMC process. Yet, we view this as an intriguing avenue for future work and thank the reviewer for highlighting it.\n\n**Q3:** While the theoretical contributions are strong, the paper currently lacks empirical verification or practical demonstrations showing how the proposed convergence bounds translate to real-world implementations. For instance, it would be valuable to see whether the improved convergence rates under absorbing rate matrices indeed yield faster or higher-quality sampling in practice. Some plots would be useful to support the theoretical argument.\n\n**A3:** We appreciate the reviewer’s interest in empirical validation. To clarify, this submission is focused on closing a theoretical gap by providing the first non-asymptotic convergence guarantees for discrete diffusion samplers with absorbing rate matrices, which previously lacked such analysis. That said, prior works — including [1] and [2] — have empirically demonstrated that absorbing rate matrices often yield better performance than uniform ones. Our theoretical findings thus offer formal justification for this empirically observed advantage. \n\nWe thank the reviewer again for your comments. We hope that our responses resolved your concerns. Certainly, we are more than happy to answer your further questions if any.\n\n[1] Austin, Jacob et al. “Structured denoising diffusion models in discrete state-spaces.”\n\n[2] Lou, Aaron, et al. “Discrete diffusion modeling by estimating the ratios of the data distribution.”"}, {"review_id": "mVjUz9VWGe", "reviewer": "Reviewer_rP18", "summary": "This paper presents the first provable convergence guarantees and error analysis for discrete diffusion models utilizing absorbing rate matrices. It addresses a critical gap, as prior theoretical work mostly focused on uniform rate matrices despite absorbing models showing superior empirical performance. The authors derive finite-time error bounds and analyze convergence rates for $\\tau$-leaping and uniformization samplers, demonstrating improved rates. Notably, they achieve convergence without early-stopping under certain conditions and introduce novel technical tools for bounding absorbing score functions. The theoretical insights reinforce the observed advantages of absorbing discrete diffusion models.", "questions": "1. Regarding Assumption 4 (for convergence without early-stopping), could you further elaborate on its practical implications and the types of data distributions for which it is most likely to hold? Specifically, how might practitioners determine if their specific setup satisfies this assumption, or what might be the consequences if it does not?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "- Strengths\n\n1. Good Writing: The paper is well-written and structured, making the complex theoretical arguments as accessible as possible. The authors adeptly highlight their key proof techniques, which significantly aids in understanding the methodological contributions.\n\n2. Theoretical Contributions: This paper delivers the first rigorous theoretical analysis of sampling convergence for discrete diffusion models that employ absorbing rate matrices. This fills a significant gap in the literature and provides a foundational understanding for models whose empirical performance has often surpassed those using uniform rate matrices.\n\n3. Explanation on Empirical Results: The authors provide a clear theoretical explanation for why absorbing rate matrices offer advantages over uniform rate matrices in practice. Their analysis includes improved convergence rates for common samplers, such as $\\tau$-leaping, aligning theory with observed empirical benefits.\n\n- Weaknesses\n\n1. Practical Concern on Assumption 4: My primary concern lies with Assumption 4, used to establish convergence without early-stopping. While the paper acknowledges that previous works might make stronger assumptions, this particular condition still appears quite strict for practical distributions. It also seems that current absorbing discrete diffusion models do not typically rely on such an assumption when determining mask tokens, which might limit its immediate practical applicability.", "was_revised": true, "final_justification": "This is a very nice work on the fundamental theory of discrete diffusion model. I will keep my rate to accpet this work.", "rebuttal": "We thank the reviewer for carefully reading our work and providing encouraging and insightful feedback. \n\n**Q1:** Practical Concern on Assumption 4: My primary concern lies with Assumption 4, used to establish convergence without early-stopping. While the paper acknowledges that previous works might make stronger assumptions, this particular condition still appears quite strict for practical distributions. It also seems that current absorbing discrete diffusion models do not typically rely on such an assumption when determining mask tokens, which might limit its immediate practical applicability.\n\n**A1:** Even though it seems strict, Assumption 4 can be justified as nearly necessary for the validity of **the diffusion algorithm itself** (without early stopping), as follows. By the second part of Lemma 2, if Assumption 4 is violated, the score function will (nearly) diverge around $t = 0$. Since the diffusion algorithm relies on the score function to make progress at each step, such divergence at $t = 0$ would render the algorithm itself invalid in that regime. We have made this point clear after Assumption 4 in our revised draft.\n\n**Q2:** Regarding Assumption 4 (for convergence without early-stopping), could you further elaborate on its practical implications and the types of data distributions for which it is most likely to hold? Specifically, how might practitioners determine if their specific setup satisfies this assumption, or what might be the consequences if it does not?\n\n**A2:** Excellent question. Note  that our main theoretical guarantees with early-stopping (i.e., Theorems 2–3) do not rely on Assumption 4 and thus remain broadly applicable. Thus, practitioners can always rely on early stopping for a small enough initial time $\\delta$, which would make the approach practical. Specifically for Assumption 4, it can be satisfied when the probability of [MASK] is non-zero in the data. Also, as argued above, given that Assumption 4 is nearly necessary for the diffusion algorithm to be valid, the violation of it stops one from pushing too much towards $t=0$.\n\nWe thank the reviewer again for your comments. We hope that our responses resolved your concerns. Certainly, we are more than happy to answer your further questions if any."}, {"review_id": "EVdpvpMEoX", "reviewer": "Reviewer_vZMc", "summary": "This paper studies the discrere diffusion models with absorbing rate matrices. The authors establish the first convergence guarantees for both the τ-leaping and uniformization samplers under absorbing rate matrices, which are better or same for uniform rate matrix. Thses results are based on several new techniques.", "questions": "A more detailed discussion of the dependence on M, along with a comparison to existing literature, would be appreciated.", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength:\n\nThis paper delivers the first rigorous convergence analysis for absorbing discrete diffusion models and introduces several technically significant innovations. By proposing a surrogate initialization distribution, it effectively overcomes the challenge of ill-defined KL divergence caused by a singleton stationary state. The authors further employ novel Jensen-type arguments and refined score-control techniques, thereby eliminating reliance on log-Sobolev inequalities. Importantly, the work establishes convergence guarantees under both early-stopping and non-early-stopping regimes, offering a comprehensive theoretical foundation.\n\n\nWeakness:\n\nThe assumption of bounded score estimate seems too strong. Could you give more justification?", "was_revised": true, "final_justification": "My concerns and questions have been addressed, and although I am not an expert in discrete diffusion models, I believe this work is worthy of acceptance.", "rebuttal": "We thank the reviewer for carefully reading our work and providing encouraging and insightful feedback.\n\n**Q1:** The assumption of the bounded score estimate seems too strong. Could you give more justification?\n\n**A1:** Definitely! Assumption 2 is commonly adopted in the previous studies for uniform-rate discrete diffusion models (e.g., [15] and [16]). In practice, this can be satisfied with score-clipping during training [16]. Indeed, the convergence error bounds in our main results only at most depend on $\\log M$. In the revision, we will add these sentences after introducing Assumption 2.\n\n**Q2:** A more detailed discussion of the dependence on M, along with a comparison to existing literature, would be appreciated.\n\n**A2:** We thank the reviewer for raising this. As follows we divide the existing literature according to two types of sampling algorithms. First, for random-stepsize samplers, the uniformization algorithm in our paper does not depend on $M$ under the absorbing rate (with or without early-stopping). This result aligns with that under the uniform rate in [15]. For deterministic-stepsize samplers, the dependence on $M$ was initially shown to be $O(\\sqrt{M})$ in [16] and was later improved to be $O(\\log M)$ [15], both under the uniform rate. In comparison, our result has shown the same $O(\\log M)$ dependence under the absorbing rate.\n\nWe sincerely appreciate the reviewer’s continued engagement. We hope our responses have fully addressed the concerns. We are also happy to provide further clarification if needed."}, {"review_id": "6OFrlaOIri", "reviewer": "Reviewer_j85T", "summary": "This paper studies the non-asymptotic convergence guarantees of absorbing discrete diffusion models, and establishes the algorithmic complexity of the $\\tau$-leaping and uniformization samplers to obtain $\\varepsilon$-accurate samples in KL divergence assuming $\\varepsilon$-accurate score estimation. The paper also provides convergence guarantees without early-stopping under specific conditions on the target distribution.", "questions": "1. In Sec. 2, the score entropy loss is given in the form that includes the ground truth score $s _ t(y,x _ t)$, which is typically not available during training. As introduced in [Lou et al, ICML 2024], the form of the loss typically used in practice is the *denoising* score entropy, and I think the authors should clarify this point. Of course, in presenting the convergence bounds it is fine to use the score entropy loss there, but you should not say this is the \"training objective\".\n2. The implementation of the $\\tau$-leaping discussed in Sec. 2 lacks the **clipping** step. If many jumps happen in a certain position, then summing up the difference may make the value out of the domain $[S]$. In practical implementations one typically truncates the value to the domain $[S]$ or just rejects the jump if there are more than one jump in a certain position (which happens w.p. $o(h)$ where $h$ is the step size). See [Ren et al, ICLR 2025, Rmk. A.13] for a discussion of this issue. I have not seen how the authors handle this issue in the paper, and a brief clarification would be helpful.\n3. Assump. 4 is non-standard. As far as I know, in almost all of the real-world implementations, the mask token is different from any of the tokens appearing in the dataset, i.e., the mask token is not in the support of the data distribution $q _ 0$. But in Assump. 4, the authors assume the mask token is one of the existing tokens in the dataset and takes a conditional probability of at least $\\gamma$, which, though not impossible, is not the common case, and $\\gamma$ would be extremely small in high-dimensional distributions with large vocabulary size.\n4. Lem. 2 seems to be strange. From Lem. 1 and [Ou et al., ICLR 2025], we know the score is just a time-dependent scalar (here $\\frac{\\mathrm{e}^{-t}}{1-\\mathrm{e}^{-t}}$) times the conditional probability of $y^j$ given all the unmasked positions in $x$ in the data distribution $q _ 0$. But why can the conditional probability be lower bounded in general? Is there any hidden assumption or am I missing something?\n5. To the best of my knowledge, the first use of the \"Jensen approach\" for continuous diffusion models is in [Chen et al, ICML 2023, Lemma C.4] (reference [40] in this paper), not the reference given in the paper.", "limitations": "I do not see clear discussion of limitations in the paper though the authors claimed having done so in the checklist. See the weakness part above for my opinions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\nThe paper provides the first (to the best of my knowledge) non-asymptotic analysis of the convergence guarantees for the absorbing discrete diffusion models, complementing the theoretical understanding of discrete diffusion models that have been mainly studied in the uniform setting. The paper is clearly written and all the main results are well presented.\n\n**Weaknesses:**\n\nI have the following concerns about the motivation of the paper, and they impact my willingness to recommend acceptance of this work.\n\nThe paper studies two algorithms for sampling from absorbing discrete diffusion models: $\\tau$-leaping and uniformization. While these are useful samplers for uniform discrete diffusion models, they are typically not used very often in the setting of absorbing discrete diffusion models. As studied in [Ou et al., ICLR 2025] and several other works such as [Sahoo et al., NeurIPS 2024], the absorbing discrete diffusion models can be *exactly* sampled via random-order autoregressive sampling in *exactly* $d$ steps. Exact sampling means that there is no discretization error (like in the $\\tau$-leaping method) and no initialization error as discussed in Thm. 1 of your paper, and the KL divergence from the target distribution to the sampled distribution is bounded above by the score learning error. This is a significant advantage over the $\\tau$-leaping and uniformization methods that are studied in this paper, which require more than $d$ steps to sample from as indicated by your bounds.\n\nIn light of this, I feel it is not of high value and significance to the community (both theoretical and applicational) to study the convergence guarantee of these sampling algorithms that may contain numerical error and require significantly more steps, unless there is a strong motivation to do so, such as being able to sample in $\\widetilde{O}(\\sqrt{d})$ steps (see, e.g., [Ren et al., 2025](https://arxiv.org/abs/2502.00234)), or to prove some other theoretical results for inexact sampling with better generation quality.\n\nBesides, there are also some issues regarding the special structure of the absorbing discrete diffusion models that can be used to make the analysis easier. For instance, as the time parameter is redundant in the absorbing discrete diffusion models (proved in [Ou et al., ICLR 2025] and several other papers), Thm. 1 is totally unnecessary with a different noise schedule: one can choose a function $\\sigma(t)$ and write $Q _ t=\\sigma(t)Q^\\mathrm{base}$. If $\\int _ 0^T\\sigma(t)\\mathrm{d}t=\\infty$, then the distribution at the final time $T$ is exactly $(\\delta _ {[\\mathrm{MASK}]})^{\\otimes d}$. Also, in Lem. 1, $q^j _ {0|t}$ can be written as $q^j _ 0(y^j|x^\\mathrm{unmasked})$, which is a more natural way to write the conditional distribution of the unmasked variables given the masked variables.", "was_revised": true, "final_justification": "During rebuttal, the authors have addressed most of my concerns, especially for the motivation of this research (which we had a long discussion). I thus raise the rating to 4 to reflect the authors' commitment of improving the paper and effort in better clarifying the value.", "rebuttal": "We thank the reviewer for carefully reading our work and providing insightful feedback. \n\n**Q1:** Weakness and question on the value and significance of studying $\\tau$-leaping and uniformization algorithms in the setting of absorbing discrete diffusion models.\n\n**A1:** We respectfully disagree with the reviewer. The references cited by the reviewer do not appear to support the claim that the algorithms studied in our paper are not used very often in the setting of absorbing discrete diffusion models. In practice, $\\tau$-leaping-like samplers—such as the Euler method and Tweedie $\\tau$-leaping—have been employed in various works under absorbing settings (e.g., [3–4]), including the references [1] and [2] provided by the reviewer. Our reading of [1] and [2] suggests that sampling in those works is not performed in exactly $d$ steps, as asserted. In both papers’ discrete diffusion models, during each sampling step, there is a non-zero probability for a mask state to remain as mask, yielding the total number of steps (much) greater than $d$ (i.e., not “exact”). Such non-“exact-step” sampling is also indicated by their empirical experiments as well. For example, in [1, Table 3], the number of sampling steps reaches up to 4096, exceeding the window length of $d = 1024$. Similarly, in [2, Table 6], with a window size of $d = 1024$ tokens, the number of steps can go up to 10,000.\n\n**Comparison between exact samplers and $\\tau$-leaping-like samplers:** Since exact samplers are often in autoregressive-type masked language models, we refer to it as **MLM** in our following discussion, and use **DDM** to denote the discrete diffusion model with $\\tau$-leaping type samplers. While MLMs offer certain advantages such as no discretization and initialization errors and a deterministic number of sampling steps (e.g., $d$ steps), there are several fundamental reasons why they may still underperform compared to DDMs in certain settings. (1) DDMs sample tokens iteratively based on a learned reverse process that models dependencies across all tokens and time steps. In contrast, MLMs often rely on shallow, single-step predictions for each masked token, limiting their ability to model long-range or high-order dependencies in a globally consistent manner. For example, [11] shows that DDMs can model structured sequences more effectively than autoregressive or MLM-type methods, due to the ability to revise and refine generations. (2) The deterministic $d$-step schedule in MLMs may not optimally align with the complexity of the generation task. DDMs allow adaptive generation paths, e.g., more steps for difficult tokens, enabling finer-grained control and potentially better outputs. [12] reveals that MLMs allocate separate representational dimensions to [MASK] tokens, limiting downstream expressiveness and overall performance.\n\nOverall, the current literature continues to actively explore and compare exact samplers in MLMs and $\\tau$-leaping-like samplers in DDMs. As far as we can tell, there is no conclusive evidence that one method consistently outperforms the other (e.g., [10, Table 3]). Therefore, we believe both sampling techniques offer valuable and complementary perspectives, and hence both warrant continued theoretical and empirical investigation.\n\n**Our another motivation:** We further note that another motivation for us is to theoretically understand and justify the benefits of using absorbing rate over uniform rate, as empirically observed in [3]. To this end, we choose the same set of samplers ($\\tau$-leaping and uniformization) as those typically used for the uniform rate. Overall, we show improved rates of these samplers on absorbing rates over uniform-rate counterparts. \n\n**A side note regarding [6]:** [6] does not seem to have an explicit result that characterizes the dependence of $d$. It is unclear whether the sampling is in terms of $\\tilde{O}(\\sqrt{d})$ steps.\n\n**Q2.1:** Question on the noise schedule.\n\n**A2.1:** In our study, we follow many prior works (under the uniform rate) in assuming time-homogeneity (e.g., [7-9], which study uniform discrete diffusion models). This allows for a more direct comparison on the rate matrices by controlling for other parameter differences, such as the noise schedule. While it might be helpful to introduce a non-homogeneous noise schedule to tackle the initialization error, both the discretization error and the estimation error will be affected, which may possibly worsen the overall convergence rate.\n\n**Q2.2:** Question on notation in Lem. 1.\n\n**A2.2:** To clarify, our $q_{0|t}^j(y^j|x)$ in Lemma 1 is **different** from the “clean-data distribution” as in [1, Theorem 1]. While their “clean-data distribution” does not depend on $t$, ours is the **posterior** distribution of $x_0^j=y^j$ given that $x_t = x$ (notably, at time $t$), which obviously depends on $t$. \n\nNow we argue that $q_{0|t}^j(y^j|x)$ must depend on $t$ in general in the following example. Suppose that the score function is well-defined at $t=0$ (i.e., finite for every pair of x and y having Hamming distance 1). (Necessarily, this implies that [MASK] exists in the training data.) Then, since the time-dependent coefficient $e^{-t}/(1-e^{-t})$ blows up as $t \\to 0$, the other term in the multiplication must also depend on $t$ so that the overall product remains a finite quantity. \n\n**Q3:** Question on score entropy loss.\n\n**A3:** We will clarify this point in the revised draft. In particular, we will change the previous one to “training loss” and add the following sentence: “In practice, for tractable training, the denoising score entropy is usually used, which is a variant of the score entropy [9].”\n\n**Q4:** Question on the lacking of clipping step in $\\tau$-leaping discussed in Sec. 2.\n\n**A4:** Indeed, in practice, an additional clipping step is necessary to avoid boundary crossing behaviors. As shown in [7], such a step does not affect the convergence rate given sufficiently small step-sizes (cf. [7, Remark A.13]). We will add this piece of clarification in the footnote when introducing the sampler.\n\n**Q5:** Question on Assump. 4.\n\n**A5:** To clarify, our main theoretical guarantees with early-stopping (i.e., Theorems 2–3) do not rely on Assumption 4 and thus remain broadly applicable. Early-stopping is often used in theoretical analysis to deal with practical difficulty. Thus, in practice, one can always rely on early-stopping for a small enough initial time $\\delta$. \n\nOur dependence on Assump. 4 comes only if we aim to obtain stronger theoretical guarantees to remove early stopping (which is generally regarded as very difficult and has been very rarely established in the literature). In fact, Assumption 4 can be justified as nearly necessary for the validity of **the diffusion algorithm itself**, as follows. By the second part of Lemma 2, if Assumption 4 is violated, the score function will (nearly) diverge around $t = 0$. Since the diffusion algorithm relies on the score function to make progress at each step, such divergence at $t = 0$ would render the algorithm itself invalid in that regime. We will make this point clear in our revised version.\n\n**Q6:** Question on Lem. 2.\n\n**A6:** As we pointed out in A2.2, our $q_{0|t}^j(y^j|x)$ in our Lemma 1 is not the “clean-data” distribution but the posterior distribution which depends on $t$. Meanwhile, our Lemma 1 is more general than [1, Theorem 1] by taking into account the possibility of masks in the data.\n\nIn Lemma 2, instead of providing a lower bound for this posterior distribution, we provide the bound **directly for the score function** through Bayes’ rule. Intuitively, if $q_t$ has full support for all $t > 0$ (necessarily, this also holds for $q_0$ due to continuity of measure), all possible states (including the mask) would have finite probability under $q_0$, which implies a finite lower bound for the score function. Otherwise, the score function will diverge, at the same rate of the time-dependent coefficient. \n\n**Q7:** Reference related to \"Jensen approach\".\n\n**A7:** Thank you for pointing this out! We will change the reference and further clarify this in the proof in Appendix D.\n\nWe thank the reviewer once again for your thoughtful comments. We hope our responses have addressed your concerns. In particular, we hope the reviewer could kindly consider the value of exploring absorbing diffusion models with stochastic sampling, which is still a meaningful and timely direction of study. If so, we would greatly appreciate it if you could kindly reconsider your evaluation and consider raising the score. We would be happy to address any further questions or clarifications you may have.\n\n[1] Ou, Jingyang, et al. “Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data.”\n\n[2] Sahoo, Subham Sekhar et al. “Simple and Effective Masked Diffusion Language Models.”\n\n[3] Lou, Aaron, et al. “Discrete diffusion modeling by estimating the ratios of the data distribution.” \n\n[4] Nisonoff, Hunter, et al. “Unlocking Guidance for Discrete State-Space Diffusion and Flow Models.”\n\n[5] Ghazvininejad, Marjan et al. “Mask-Predict: Parallel Decoding of Conditional Masked Language Models.”\n\n[6] Ren, Yinuo, et al. \"Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms.\"\n\n[7] Ren, Yinuo, et al. “How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework.”\n\n[8] Zhang, Zikun, et al. “Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis.”\n\n[9] Chen, Hongrui and Ying, Lexing. “Convergence analysis of discrete diffusion model: Exact\nimplementation through uniformization.”\n\n[10] Shi, Jiaxin, et al. “Simplified and Generalized Masked Diffusion for Discrete Data.”\n\n[11] Austin et al. “Structured denoising diffusion models in discrete state-spaces”\n\n[12] Meng et al. “Representation deficiency in masked language modeling”"}]

Author rebuttal:

Meta-review: This work is a theoretical study of the discrete diffusion models with absorbing rate matrices. It establishes the first non-asymptotic convergence result in this setting. All reviewers agree the paper is well written and technically sound. There are two major concerns raised by the reviewers, one on assumption 4 and one on the significance of the results. The authors manage to convince the reviewers with an intense and comprehensive rebuttal. Overall, this work represents an interesting contribution in the area of discrete diffusion models.
Decision: Accept (poster)