Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees
Authors: Yuchen Liang
Yingbin Liang
Lifeng Lai
Ness Shroff
Venue: NeurIPS 2025 poster ()
Keywords: Discrete diffusion models
convergence analysis
tau-leaping
Euler method
Tweedie tau-leaping
Primary area: theory

Abstract: Discrete diffusion models have recently gained significant prominence in applications involving natural language and graph data. A key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, $\tau$-leaping samplers have become particularly popular due to their theoretical and empirical success. However, existing theoretical analyses of $\tau$-leaping often rely on somewhat restrictive and difficult-to-verify regularity assumptions, and their convergence bounds contain quadratic dependence on the vocabulary size. In this work, we introduce a new analytical approach for discrete diffusion models that removes the need for such assumptions. For the standard $\tau$-leaping method, we establish convergence guarantees in KL divergence that scale linearly with vocabulary size, improving upon prior results with quadratic dependence. Our approach is also more broadly applicable: it provides the first convergence guarantees for other widely used samplers, including the Euler method and Tweedie $\tau$-leaping. Central to our approach is a novel technique based on differential inequalities, offering a more flexible alternative to the traditional Girsanov change-of-measure methods. This technique may also be of independent interest for the analysis of other stochastic processes.

Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees
Yuchen Liang', Yingbin Liang', Lifeng Lai', Ness Shrofft
The Ohio State University Univeesitty of California, Davis
Abstract
Discrete diffusion models have recently gained significant prominence in appli- cations involving natural language and graph data. key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, r-leaping samplers have become particularly popular due their theoretical and empini cal success. However, existing theoretical analyses of r-leaping often rely on somewhat restrictive and difficult-to-verify regularity assumptions, and their con- vergence bounds contain quadratic dependence on the vocabulary size. In this work, we introduce a new analytical approach for discrete diffuusio models that removes the need for such assumptions. For the standard 7-leaping method, establish convergence guarantees KL divergence that scale linearly with vocabulary size, improving upon prior results with quadratic dependence. Our approach is also broadly applicable: it provides the first convergence guarantees for other widely used samplers, including the Euler method and Tweedie r-leaping. Central approach is a novel technique based on differential inequalities, offering a more flexible alternative the traditional Girsanov change-of-measure methods. This technique may also be of independent interest for the analysis of other stochastic processes.
1 Introduction
Generative modeling a core component of deep learning, aiming generate samples that closely approximate distributions of training data. Recently, diffusion models 2 3 have gained significant attention. These models really work well in various generative tasks, particularly in image and video generation [4] [5. Their effectiveness has been extensively documented in several comprehensive surveys 77.
Discrete (i.e., discrete sample space) diffusion models form specialized subclass within the broader family of diffusion models and have gained increasing prominence in generative modeling. Similar to their continuous (i.e., continuous sample space) counterparts, they adopt the standard diffusion framework comprising
forward and reverse process. Differently, by operating over discrete sample spaces, both processes formulated as discrete-state Markov chains, first under discrete-ting (3] and later under continuous time [9]. Since the seminal work [3, discrete diffusion models have been remarkably useful for variety of discrete-data applications, achieving excellent performance in natural language processing (NLP) 10], graph generation [2], and drug design [13]. Recent advances, such SEDD and RADD, have further demonstrated language generation capabilities that rival those of traditional autoregressive models such as GPTss [10 14]. [4].
Despite their empirical success, the theoretical understanding discrete diffusion models remains limited. Existing theoretical studies on discrete-state state diffusion models have mainly focused on various sampling methods. One focus has been the aando-step-ssiz samplers, which sample both the next-state and the transition-times in the reverse process. This includes the Gillespie's 's algorithm [[5] and the uniformization algorithm [16]. Specifically, the uniformization algorithm has been analyzed in [17 [8]. While these algorithms are able to simulate the reverse process exactly, their convergence
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

guarantee is characterized only in a stochastic manner. In other words, there is no guarantee of fixed and finite number of iterations to achieve a target accuracy due to the algorithm's 's inherent randomness in the number of iterations, which, in the worst case, can be unbounded.
Another theoretical focus is on deterministiic-ttppsiii samplers, which enjoy finite-iteration guarantee for achieving a target accuracy. One type of such samplers is what we call as Kolmogorov sampler, which directly solves the piece-wise Kolmogorov equation at each discretized step, for which convergence guarantees were provided in [9 20 Such an approach may not be practically feasible, because it involves high computational costs in practice. At each step, the Kolmogorov sampler needs to solve a matrix exponential, which typically requires eigen-decompooition and multiplication of the reverse rate matrices (of size 5d x 5", where 5 is the vocabulary size and dl is the data dimension). This renders the per-step computational complexity to be exponential in d.
more practical deterministic-stepe size sampler is T-leaping (2T], which has drawn lot of attention 10 [8] Rather than solving for the matrix exponential exactly, the algorithm applies all transitions within a single step simultaneously for each next-state and dimension. The existing theoretical studies (9, [8] on r-leaping have some fundamental limitations that need to be resolved. (1) (Strong or hard-to-check assumptions) Existing results require either strong assumptions on the estimation error or somewhat hard-to-check assumptions due to the analysis technique. Specifically, [9] assumes that the reverse rate matrix is well estimated under the 1 error for each data sample and for each diffusion time, which is stronger compared to that only in expectation. [18] requires additional regularity assumptions on the diffusion path in order to invoke the Girsanov change-of-measure measure framework, which are usually hard to check in practice. (2) (High dependence on vocabulary size) Existing error bounds have high dependence on the vocabulary size S. In particular, the iteration complexity grows in fourth-power in both d and S for [9], and it grows quadratically in S for [18] 0 This might be unsatisfactory in practice where S is large (e.g.. S = 50257 for GPT-2 tasks [10] To this end, it is important to obtain a tighter bound on S. Thus, these open challenges can be summarized into the following intriguing question:
Question 1:
Can establish convergence guarantees for T T-leaping under more relaxed assumptions? Meanwhile, can we achieve a better dependency on S?
While r-leaping is practical sampler, it also has several weaknesses. For each step, the sampler requires sampling from a Poisson random variable each dimension and each token, which becomes per-step sampling heavy especially when the vocabulary size S is large. Also, especially for non- ordinal or categorical data, there could occur unmeaningful jumps such as multiple jumps within the same dimension out-of-range jumps. For practical implementations, one usually needs additional constraints to restrict only one change to only one target location [9], which might further increase the sampling complexity. In comparison, empirical studies usually employ the Euler method Tweedie r-leaping [10] 22], which are more sampling efficient than vanilla r-leaping. However, existing analytical tools are not directly applicable these samplers.
Question 2: Can we provide convergence guarantees for practically more efficient samplers having deterministic step-sizes, such as the Euler method and Tweedie 7 r-leaping?
This paper will provide affirmative answers to both of the above questions.
1.1 Our Contributions
Our main contribution in this paper lies in developing a novel analysis framework to analyze discrete diffusion models to improve/advance the current theory. Our detailed contributions are as follows.
Novel Analysis Technique: We develop a novel framework for analyzing discrete diffusion models. In particular, we directly analyze the rate-of-change of the KL-divergence between the true posterior and the sampling distribution, for which we provide an upper bound in terms of the respective rate matrices in the two processes by directly invoking the Kolmogorov equations. Our analysis (i) provides convergence guarantee without any regularity conditions, i.c., without requiring that the likelihood function on the sampling path is a local martingale, which is typically required for the Girsanov change-of-men -f-easurr technique; (ii) enables to analyze a broader class of practical samplers, such as the Euler method and Tweedie r-leaping 110. for which it is challenging to apply the analysis based on the Girsanov saange-ff-mesuree framework.
'The error bound in 18 does not explicitly characterize the dependence on S. However, it is straightiorward to derive the quadratic dependence on S from their proof steps.

---

Comp
Sample
Results:
Sampler
Space
Assump
Reference
per-step
per-step
Num of steps
Uniform-
[0
int-path
((d)
(ld)
Pois (O (d)
17
Thm 6]
ization
S
int-path
((dd)
O(d)
Pois (O (dS))
18
Thm 4.9]
Kolmogo-
[s]
int-path
O
((d)
VdMS VF
19
Cor 1]
rov
DMPM
{0, 1]ad
disc-max
(ld)
((1)
2
20
Cor 2.7]
[s]a
cont-max
((Sd)
O(Sd)
o
a
+Cd
9
Thm 1]
T- leaping
VF
[s]]
disc-sum
((Sd)
(Sd))*
d
18
Thm 4.7]
[s]]
disc-sum
(Sdd)
O(Sd)
Thm
(here)
Euler
[s]
disc-sum
(Sdd)
((d)
d's
Thm
(here)
Tweedie
[S]a
disc-sum
(SSd)
(dd)
Thm (here)
Table 1: Summary of results for discrete diffusion samplers terms of the nunber of steps needed
achieve e-accuracy in KL(qa||Pr-A and the per-step computation and sampling complexity. Note that all log- dependencies are not shown. Here d is the dimension (window-length, for generative tasks). S is the vocabulary size, M is the upper bound of the score estimates (which grows in (S)). Pois(N (X) is a Poisson Ev. with rate X. and qs is such that [g(gu, q6) S dō. Comparison of results: (i) Uniformization samplers suffer from random number of steps guarantee, whose actual iterations to convergence might grow unbounded. (ti) Kolmogorov samplers enjoy fixed finite step guarantee, but suffer from exponential in d per-step computational complexity, making it generally not practical. (iit) DMPM is an Euder-type method that differs from the standard Euler schemes [10] [2] studied in this paper. In particular, at most one coordinate is updated at each step, whereas the standard Euler sampler [10 [2] first constructs sampling probabilities for all coordinates and then performs simultaneous categorical draw across all of them. After our initial submission of the paper. 1200 provided an updated result, which is O(d/e"), ). (iv) The result on T T-leaping in (9) has high dependence on and S (note that C = (2S")) ) is an implicit function of S), although is more efficient in c. The number of steps in (9) is calculated in order to reach VE total-variation error, which is weaker than the Kl-divergence ervor considered in other guarantees the table. The "cont-max" assumption strong, which requires an upper bound for each time on each sample. The result on r-leaping in [18 has dependence on S². Note that quite large for many NLP tasks. (v) Our result on T-leaping improves that of (18) by a factor of S. Our analysis also removes the regularity assumptions required in [18]. (vi) Our result on the Euler method and Tweedie r-leaping enjoys the same convergence as vanilla r-leaping, but these two samplers have smaller per-step sampling complexity than T-leaping by a factor of S.
Improved Result for r-leaping: Based our analysis tools, we show that r-leaping generates a sample distribution that is close to the target distribution within an s-KL accuracy with (d iteration steps. In particular, the iteration guarantee is linear in S under the fully discrete score- entropy estimation loss, which improves the quadratic dependency on S in [18]. This order-level improvement has important practical implications, especially because S is often very large in NLP tasks (e.g., S = 50257 in 10))
New Convergence on Euler method, and Tweedie r-leaping: Our analysis framework further provides convergence guarantees for practically efficient samplers: the Euler method and Tweedie r-leaping. The existing analysis tools do not seem to be applicable directly for lack of a path- wise measure defined for both samplers. Our result shows that these two samplers enjoy the same performance guarantee as r-lcaping even with smaller sampling complexity at each step. Our approach involves constructing an approximate sampler which is asymptotically equivalent both samplers, and then establishing the convergence guarantees for the constructed sampler. This constructed sampler might be of independent interest to future theoretical investigations of these two samplers.
1.2 Related Works
We have provided more prior works in Appendix A
Empirical Studies on Discrete Diffusion Models:
Unlike continuous-space diffusion models, discrete-space diffusion models are emerging as a strong contender in generative modeling, particu-
larly for tasks involving discrete data [9] (see some surveys in [12 [3). The continuous-time discrete diffusion formulation was first developed in [9]. Recently, [10 first proposed the score-
3

---

entropy estimation error and achieved empirical success in text generation tasks, They also proposed a new discrete diffusion sampler by approximately solving the Tweedie's 's formula, which they call Tweedie 7- r-leaping. For per-step sampling, note that most of these works use categorical sampling algorithms, yielding good empirical performances.
While there are numerous results for continuous-space diffusion models, the theoretical understanding of discrete diffusion models remains limited. Among them, 9 provided an early convergence analysis under the TV metric using 7-leaping. However, the estimation error is quite strong, and the parameter dependencies are also high. More recently, under the score-entropy estimation errors, [17] provided the convergence result using the uniformization sampler on d-dimensional hypercube, which was subsequently extended to general [S] space in samplers, [1] performed analyses by assuming the accessibility of a perfect per-step sampler via solving the Kolmogorov equation, and [18] investigated the more practical r-leaping sampler. Among these works, [19 required the score-entropy loss to be evaluated on the continuous sampling path, whereas [8] 20 only required it to be on the discrete sampling grid. Notably, all of these works [8 19 20) employed the Girsanov lrange-of-measune framework, which requires such regularity conditions (that the likelihood function is a path-wise local martingale) that are hard to check in practice.
Theory on Discrete Diffusion Models:
[1]. For determiiistiicsttp--aa
2
Preliminaries of Discrete Diffusion Samplers
In this section, we provide the background of continuous-time discrete-space diffusion sampler.
2.1 The Forward Process
Let the initial (discrete) data xo = {-d. = consist of tokens, where each token x1 E [S] with S being the cardinality of the token space. Hence, To E [S]d Let % be the probability mass function (p.m.f.) of wh. which is the probability simplex over [0, ll We further let go [0, _js" be entire p.m.f. of the initial data To-
The forward process can be characterized by a Continuous- Time Markov Chain (CTMC) from t= 0 to = T. which is defined by an initial distribution do and a transition rate matrix R2 x* Intuitively, each entry Ra (I, y) in the rate matrix R₂ characterizes how fast state x transitions to state y at time I, where x. y E [$]d. Thus, for sufficiently small time duration At, the conditional probability (=-a)((y)=) of state at time + A given state x at time i. is given by
ltti r (y)lz)
{v = x) [x A) + o(Al), Va, [S]
(1)
Here 1 {4} is the indicator function of an event A. Equivalently, d satisfies the Kolmogorov forward d equation: di (v) = Exe[s| qe (x))).)) [z, v).
We now discuss several properties for the rate matrix R. For a valid CTMC, Rd needs to satisfy that: 1) for all v, E [S] (x y) 0f x + y; 2) Rg (3r, S O; and 3) Eye[sp Re 0. Also, to make the computation tractable for large S and d, common practice is to make each token propagate independently and homogeneously (i.e., over the dimension) [0] Then, RS necessarily satisfies that, for all + y. 19 Prop. 3]
Riok (x+ v²)
if Ham (z, 1,
(x,,))
(2)
0
otherwise.
Here Rook E Sx8 is the token transition rate matrix (corresponding to g)), and Ham (x. y) denotes the number of unequal tokens between x and y. We follow [9] and let R Rome for some noise schedule 3, > O. In this paper, we are primarily interested in the constant noise schedule (i.e., 3, 1) in the previous studies (e.g.. [18 19). With such R,, can obtain analytical solution for 4ro useful for training. Further, we primarily focus on the case where
Roase 1111] Is:
which is common in many applications
An immediate implication is that for all x E [S]] Rx(2, x) Eyer Re y) S-1 d. Note that qr Uniform([S]d) for the chosen Roase-
9 10
Most of our results can be extended for general Ri's that satisfy [18 Assumption 4.3).

---

2.2 The Reverse Process
The forward process has a corresponding reverse process whose marginal distribution matches that of the forward process [3] By 99 Prop. 11, such a reverse process is CTMC with initial distribution
To qr and transition rate RG, where RG satisfies
(x,,)) == RT (v,
9r 9r-1(y)
Vx # and (x(x,))=
Σ R, w-z
(3)
GT (x))
We let the reverse process stop at T å with some small constant 8. This technique called early-stopping to prevent irregularities in the score when / + 0+. One immediate consequence
is that with the R in (2 whenever Ham (z, v) 2, (x y) = O. Note that qt == qr for all
t E -0.
2.3
The Sampling Process
In order implement the reverse process, several approximations need to be made for sampling. Let Pe be the marginal p.m.f. at time t E [0, T 5] in the sampling process. First, since qr is unavailable, we start the sampling process with Po == Uniform([S])) which is the stationary distribution of the
CTMC. Second, when * we estimate the intractable ratio 2c(v] with se 2), which is known
q(()) as the concrete score function. Here adopt the score-entropy (SE) loss [10] to train the score function, which defined as
Σ Roly, (sc(u. yo
4e(y)
(x) log
se(v. sc(u.3t))
LSE(1; (1; 81) = Reg rige
ge (xx,)
2e (x()))
2e (u())/q
Third, the continuous path needs to be discretized for practical algorithms. discretization points on which St is accessible, where to 0 and ty estimated rate on the sampling grid as
Let ftx NE be the T 8. Define the
Re (Ic, y) == RT- ()) ().
(5)
r-leaping: A popular approximate sampler is called r-leaping, which has a deterministic number of sampling steps with polynomial per-step computation S and d. Given It. the next state is obtained as
(6) where e² unit (one-hot) vector on token [d]. Pois(A) is Poisson random variable with rate X, and e1 @D is a vector that replaces the i-th element of as E [S]. Intuitively, the sampler applies all transitions within [t,: fx+1) to single component simultaneously. where the transition rate comes from the estimated reverse rate at the initial time. As shown in [9, Appendix B.5], the r-leaping process is equivalent to a CTMC with a piece-wise constant rate matrix given by
1t = Ize + +E e' E'Evess (w' - Poiss (Ree (Ei tn o y (12+1 tt)) ((())111))))
(7) While r-leaping is popular in theoretical studies 18] its sampling complexity is quite high because it requires drawing ((Sd) Poisson e.v. at each sampling step. Rather, many empirical samplers, such as the Euler method and Tweedie r-lcaping, draw only ((d) categorical r.v.s [10 14 22).
1e (xx y) Re, (Ir -- x Ita);; Va + y, Vt [FA, 1x+1).
Euler method: The Euler method is given by, for each k- = O....,N- 11
w.p. R (at, a)(41 (e), Va f str
O oie
(8)
w.p. 1 + Rr (z) ot (tx+1 tx)
where (2, a) is the token-wiss rate defined as (2, Re, (Ita : ,,, @ a) [== Va # st..
(9)
Tweedie r-leaping: The Tweedie r-leaping sampler is given by, for each = NG....N..
w.p. (le (fe-(tx-1-taRRR
8T (o tb ;,,(.)))
[e [e(fu+r 1apt----oae Muse ant
Wa # xi
(10)
otherwise
Note that neither sampler has such an RG defined on the continuous-path (4x, la+ 1)+1) 1). This renders the theoretical analysis for these two samplers be still lacking, since existing analytical tools require the path-wise measure of the sampling process to be well-defined (for all E [0, T 6)).
5

---

2.4 Key Notations
Let x1l I S d) denote the i-th element a vector X E [S] and x- E [S]d-] denote the i-th element removed. Define Ham (z. y) as the Hamming distance between two vectors z and y. For positive integer n, [n] := {1..... n.. Write 1g as a vector of length that contains all 1 I's, and Iy as
an identity matrix of size S x S. See full list of notations in Appendix B
3 Main Convergence Results
The r-leaping sampler has been analyzed in 9 18 with convergence guarantees. However, the convergence rate in [9] has high dependence on S and d (which grows in fourth-power in both d and [ assumes that the reverse rate matrix is well estimated under - error. The study in 18 relaxed such an assumption to be in expectation, and the convergence rate in [8] grows only quadratically in S. However, the study in [88] requires additional difficult-t-cheeck assumptions on the diffusion path in order to invoke the Girsanov thaang-off-mastien framework.
S). Further,
In this section, we develop a new analytical framework, which removes the need for the regularity assumptions used in [18), and to further improve their convergence rate with a lower-order dependence on S.
3.1 Convergence Guarantees for General Sampling Processes
We first propose the following KL-divergence decomposition for general reverse rates, without any regularity assumptions for the sampling path. Indeed, the result is applicable any CTMC with general forward rate R, as long as the reverse rate RG is well-defined [23] Chapter 1]. Theorem 1. Recall the true reverse process with rate defined in 43. Suppose thut pt also follows CTMC, with initial distribution Po and rate Rg. Then,
N-1
KL(Ār-ollPr slpp--)))))))-- 6) S (T.(Follpo)
+
Ex ~0
(T.(Te-alte (1 ) IlPe (t (12()))]
A==
N-1
Re(xes v) + Re(x v) log Re(xes de.
< (K(ToolPo) +
Eniwt
Re(wer Mr
Σ
R. v)
k=
(11)
Theorem [ indicates that, without any regularity condition, the final KL-divergence between the marginal distributions of the true and the mismatched process be upper- bounde by the sum of (1) the divergence between the initial distribution and (2) that accumulated along the sampling path due to mismatched rate matrices. Also, different from continuous diffusion models (24), the rate of accumulation at each time is characterized not by Fisher divergence but by Bregman divergence generated by the negative entropy function.
The proof is provided in Appendix Our proof of Theorem I takes a differential inequality argument, which is different from the approaches used in existing works. After invoking the chain-rule of the KL. divergence (cf. (24)), the key is to provide an upper bound for the rate-of-change of the KL-divergence between the true posterior and the sampling distribution. We then convert it into the rate-of-change the respective probabilities themselves, which can be further characterized by the corresponding CTMC rate matrices by invoking the Kolmogorov equation. Rearranging the terms, we finally obtain an upper bound in terms of only the rate matrices.
While our idea comes from 24 Lemma 6 and Proposition 8] (which studied continuous diffusion models), there are several key differences: (1) In contrast to the continuous diffusion studied in 244, there is no Fokker-Plan Planck equation defined for discrete diffusion (since the space is discrete). Instead, we need to use the Kolmogorov equation specifically tailored to a CTMC, which is related to the special CTMC rate matrix. (2) Because of this, we need to characterize the reverse rate of CTMC not in terms of the marginal probabilities (as [9] but ones that are conditioned on future observations. This is non-trivial extension, whose proof is given in Lemma 9
Comparison with Girsanov-based approaches: Our cnfferenttialinequaaiit based approach for proving Theorem Tis is more advantageous than previous Girsanov- approaches (see [8 Corol- lary 3.4], [19 Lemma I], and (20) Theorem F.3)), two ways. (1) First, we do not require the regularities conditions necessary to apply the Girsanov ohange-of-measunee (see [18 Remark A.12),

---

19 Theorem 3], and [20] Theorem F.3]). (2) [8 19 20 assume a particular parameterization of the sampling rate as (z) = R ( x). whereas our analysis allows (x y) to be generic. This might be useful, for example, when the rate is not obtained through minimizing the score-entropy,
when there is general score mismatch that arises from mismatched target [25] Nonetheless, Theorem | can be applied directly to the aforementioned particular parameteri- zation (z, y) to obtain the following Corollary | where the score-entropy is used. The proof is straightforward, which is provided for completeness in Appendix FF
Corollary 1. Under the parameterization that Rx y) Ry- ())= we have
(L(rr-a|lrr-o) S KL(Tollpo)) (o) +
Σ
LSE(T t;
(12)
k=
Here LSE is the score-entropy defined in
3.2 Improved Parameter Dependence for rleapping
In this subsection, we characterize the convergence rate of r-leaping with explicit dependencies on d and S. To this end, we employ the following standard assumptions. Assumption 1 (Score Estimation Error). Recall LSE as defined in (4). The score estimation satisfies
(tu+1 ts) tki (1-1TT-11) S Escore
(13)
Note that Assumption captures the error that St, incurs for estimating the score function in terms of the loss value at T 4 ss We have provided a table to compare different assumptions for score estimation in Table [ In particular, for those works using score-entropy estimation errors, [17 Assumption 1] and [9] Assumption IJ require that 8t (or st.) is well-estimated along the integral- path of the sampling process. This assumption is typically hard to verify practice because of the continuity of the sampling path. (20] Cor 2.7] requires that the maximum eπтor over the discrete sampling grid is well-controlled. which is stronger than our Assumption [ Our Assumption i the same as [18, Assumption 4.6], which assumes that the sum-averaged error over the discrete grid is well-controlled, which can be practically verified.
Assumption 2 (Bounded Score Estimates). The score estimates st, 's satisfy st, (x. E [M-1, [M] for all x; y E [S]d and = 0, O,...,
Assumption 2 is commonly adopted in the previous studies such as in 18 19 In practice, this can be satisfied with score-clipping during training [19]. Indeed, shown in Theorem the convergence error bounds depend only on log M.
We are now ready to present our main result below. Theorem 2. Suppose that Assumptions and?2 holld. Using the r-leaping sampler, and choosing 4-11 1 S. mim {1,T T t ). we have
KL(gsller-bb -) S d(log S)e -T Ewore + kdd S(T + log(M
(14)
where 9s satisfies TV( 98) $ dō.
Furthermore, by letting tx+1 tx = k min {1.T tx and choosing T = log(d S)/E), we have that KT< (p))) achieves E error with N = Ô (d2 sampling steps.
Theorem indicates that it takes at most Sdd))E iterations to approximate a ò 6-perturbed distribution of go e-accuracy in KL-divergence. The linear dependence on S improves upon the best previously known result for r-leaping in (18) by a factor of OSS) | This order-level improvement has important
practical implications, because
often very large for many NLP tasks (e.g., S = 50257 [TO). We
have performed a numerical study to validate such linear dependence in Figure [ in Appendix D The
full proof of Theorem 2 is in Appendix G and we have provided a proof sketch in Section
'The error bound in 18 does not explicitly characterize the dependence on S. However, it is straightiorward derive the quadratic dependence on S from their proof steps.
7

---

3.3 Convergence Guarantees for Euler Method and Tweedie 7-leaping
significant obstacle establishing the guarantees for the Euler method and Tweedie T-leaping is that both samplers are defined directly the discrete sampling grids and thus lack an intermediate rate function. Our approach to tackle this challenge includes the following steps. (i) First, we construct non-trivial approximate sampler with explicit intermediate rate that allows for categorical per-step sampling. (ii) We then show that our construction is asymptotically equivalent (in the categorical sampling probabilities) establish convergence guarantees for these samplers, we show that asymptotically equivalent samplers would also result in the same asymptotic rate in KL-divergence. In particular, this step is based on our step-wise KL-divergence decomposition in (26). In comparison, the Girsanov change-of-measine technique cannot be applied here directly due the lack of path-wise measure defined for both samplers. (iv) Finally, we show that our constructed approximate sampler enjoys the same rate as vanilla r-leaping does. The full proof is in Appendix H
both the Euler method and Tweedie 7-leaping. (iii) Then, in order to
Theorem 3. Suppose that Assumptions [ and
2 hold. For both the Euler method and Tweedie T-leaping, choosing tx+1 to I K min {I.T T tkh. we have
KL (1))l) E d(log S)e-T + Excore + S(T + 10ggMMM8811
(15)
Here (4( 96) I d8. Similarly, if we take tx+1 -t, = min {1,T tx). it suffices that log(d(log 5) and N = Ô (d (/e) to reach & Kl-divergence ermor.
Notably, this is the first theoretical convergence guarantee characterized for the Euler method and Tweedie r-leaping. Compared with vanilla r-leaping, since both samplers require the same number of iterations but a decreased number of samples per-step (by a factor of (SS)), our Theorem 3 shows that the Euler method and Tweedie r-leaping enjoy less overall sampling complexity for given target accuracy e. This benefit becomes more significant when S is large, as in many practical tasks [0].
We have also numerically compared these samplers in Figure 2 in Appendix [
Proof Sketch of Theorem
In this section, we provide a proof sketch of Theorem 2 to describe the main idea of our analysis approach. The full proof is in Appendix G Upon invoking the KL-divergence decomposition in Theorem I we can decompose the total error into three different errors, where the discretization error is the rateddetrmining term. For the two terms of the discretization error, we further identify one of the dominant term and provide an error upper bound directly in expectation.
Comparison with the approach of [8]] Our proof is different from [8] in the following ways. (i) In Step 1, we do the need for any regularity conditions, which restrict path-wise integrability and are typically hard check in practice (see 118 Corollary 3.4 and Remark 1.)) Rather, our Theorem provides more general starting point for which no such regularity conditions are needed. (ii) In Step 2, for determining parameter dependency, we do not construct stochastic-interral framework where Ito's Lemma is needed for the amalysis of discretization eтror (see [18] Theorem A. 10 and Proposition C.4]). Instead, we directly identify the dominant error term by invoking the Kolmogorov equation, thus eliminating the need of such stochastic- stochastic-integral formulation in the analysis. (iii) In Step 3, we do not employ uniform upper bound (in x and y) for the score difference to control the discretization error as in [18 Proposition C.2]. Differently, our upper bound is only in expectation of 2,, which enables us to reduce the quadratic dependency on to linear dependency.
the Girsanov change-of-measine
framework start with, thus eliminating
In the following, we divide the proof into three steps.
Step 1: Decomposing total error (Theorem I. Following Theorem I we can decompose the total error as
(L(āTllPT) < KL(oollpo)
(to+1 - (x) )x,, th Lgce (Ier )1 +
initialization ervor
estimation error
N
E ze-ee Ds mit
(g)( gel + Er,, wi. (gc( - gre (zw) (16)
discretization erroe
8

---

(x4, (e v) Re (1x, y) log Rx(2..9) Indeed Si is
where we have defined
R. (z.21)
a Bregman divergence generated by the negative entropy function. Here from
[19] Proposition 2) and
[8 Theorem C.I], the initialization error satisfies KL(Tollpo) S (dlog S)e Also, the estimation
error satisfies N
(1++1-tu tk Bu ~in Iot, (Itt,
Σ (tx+1 (t) tk2 Sta
Excure-
(17)
It remains to provide an upper-bound for the two terms, which constitute the discretization error.
Step 2: Identifying dominant term for discretization error (Lemma) 1 As shown above, the discretization eπror consists of two terms: one for the time-difference in the argument gr (in expected value), and the other for the difference in St itself. For the former term, the expected difference in the argument can be rate properties. Indeed, further implies that it does not contribute to the total error:
bounded using the Kolmogorov forward equation and the show that the former term is decaying faster than the other, which
T
E varile (ac( 9e(Fee)) = K @score f/m0 Re Nice (ge( Itn (3ree )] dt
T-
= =(())
(18)
Step 3: Bounding dominant term for discretization error (Lemmas and Equation 29
Now, we control the latter term in the discretization error, which is also the dominant-rate error term. We first upper-bound this term an expected difference of the reverse CTMC rate matrix (Lemma) and Equation (29))
Ti Eozzy 1i (ge( ghn (2te )) S + log(M88 B ~ux
Σ
Ri ( Re, (1er v
QT- (v)
QT (v)
S (1 log( The
E
PT- (11
(19)
Cr (Dta))
GT (x
Ham (M.Pig
Thus, is essential deal with the time difference of the likelihood ratios (i.e., concrete scores). One common way is to exploit the continuity of this ratio and to upper-bound its derivative for every fixed x and such that Ham (x, y) = Indeed, this is the approach taken by [I8] Prop. C.2], which will result in O(S²) dependency, approach here directly provides an upper bound expectation, which enables us to reduce a factor of (SS (see Lemma 5). With this improved bound, the discretization error Wane satisfies that
show in Lemma
purpose of comparison). Instead, our
Wdisc
2A
L max (T (T- tx+1) (tte-)))) tx)
(20)
k=
Note that this results in a tighter upper bound with linear S dependency.
Finally, combining the steps above, and invoking 224 Lemma 18], we can determine the overall parameter dependencies the above summation, which shows that
max (1, (T (241) ()41))")((+++) 1x)² S + log8-1)
(21)
Also, from the last part of [1 Theorem 6], the perturbation due to early-stopping satisfies that (Voo qa) dō,
(22)
5 Conclusion
In this paper, we have introduced a new analytical approach for discrete diffusion models that removes the need for any regularity assumptions required in the previous Girsanov change-of- measure techniques. For the standard 7-leaping sampler, we have established convergence guarantees that scale linearly with the vocabulary size, improving upon prior results with quadratie dependence. We have also provided the first convergence guarantees for other widely used samplers, including the Fuler method and Tweedie relappn the future, might be interesting investigate acceleration techniques that further reduce the order of d and S dependence.

---

Acknowledgments and Disclosure of Funding
The work of Y. Liang. Y. Liang and N. Shroff was supported in part by the U.S. National Science Foundation under the grants: NSF AI Institute (AI-EDGE) 2112471, ECCS-241353 CNS-23 12836, CNS-2223452, CNS-2225561, and was sponsored by the Army Research Laboratory under Coop- erative Agreement Number W91 INF-23-2-0225.. The work of L. Lai was supported in part by the U.S. National Science Foundation under the grants: CCF-2232907 and CCCS-2448268 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-Dickstee 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 2256,,265, 2015.
[2] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840-68488 2020.
[3] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[4] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06/25, 2022.
[5] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björ Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684-10695, June 2022.
[6] Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. ACM Computing Surveys, 56(4), Nov 2023.
[7] Croitoru, V. Hondru, Ioneseu, and M. Shah. Diffusion models in vision: A survey. IEEE Transactions on Pattern Analysis & Machine Intelligence, 45(9): 18800-0080 Sep 2023.
[8] Amirhossein Kazerouni, Ehsan Khodapanah Aghdam. Moein Heidari, Reza Azad, Mohsen Fayyaz, liker Hacihaliloglu, and Dorit Merhof. Diffusion models in medical imaging: comprehensive survey. Medical Image Analysis, 88, August 2023.
[9] Andrew Campbell, Joe Benton, Valentin De Bortoli, Tom Rainforth, George Deligiannidis, and Arnaud Doucet. continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 2022.
[10] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 32819-3284 2024.
[11] Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, 2023.
[12] 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.
[13) Amira Alakhdar, Barnabas Poezos, and Newell Washburn. Diffusion models in de novo drug design. Journal of Chemical Information and Modeling, 64(199)7238-7255 10 2024.
10

---

[14] 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. In The Thirteenth International Conference on Learning Representations, 2025.
[15] Daniel T Gillespie. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. Journal of Computational Physies, 22(():403-- 434, 1976.
[16] Nico M. van Dijk. Uniformization for nonhomogeneous markov chains. Operations Research Letters, 12(5):283-29) 1992.
[17] Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffusion model: Exact implementation through uniformization. arXiv preprint arXiv:2402.08095, 2024.
[18] 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. The Thirteenth International Conference on Learning Representations, 2025.
[19] Zikun Zhang, Zixiang Chen, and Quanquan Gu. Convergence of score-based discrete diffusion models: A discrete- time analysis. In The Thirteenth International Conference on Learning Representations, 2025.
[20] Le-Tuyet-Nhi Pham, Dario Shariatian, Antonio Ocello, Giovanni Conforti, and Alain Durmus. Discrete markov probabilistic models. arXiv preprint arXiv:2500.079.39 2025.
[21] Daniel T. Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of Chemical Physics, 1114))1716-1173,, 07 2001.
[22] Hunter Nisonoff, Junhao Xiong, Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete state-space diffusion and flow models. In The Thirteenth International Conference on Leurning Representations, 2025.
[23] Frank P. Kelly. Reversibility and Stochastic Networks. Cambridge University Press, 2011.
[24] 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.
[25] Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Theory on score- core-mismatched diffusion models and zero-shot conditional samplers. In The Thirteenth International Conference on Learning Representations, 2025.
[26] Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. In Advances in Neural Information Processing Systems, volume 34, pages 17695-17709, 2021.
[27] Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022.
(28) Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, 2022.
[29] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023.
[30] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-basee generative modeling for general data distributions. In Proceedings of The 34th International Conference Algorithmic Learning Theory, volume 201, pages 946-985, 2023.
[31] Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear convergence bounds for difffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024.
[32] Giovanni Conforti, Alain Durmus, and Marta Gentiloni Silveri. Score diffusion models without carly stopping: finite fisher information is all you need. arXiv preprint arXiv:2308.122: 2023,
11

---

[33] Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non -on-asymiioiic convergence for diffusion- based generative models. In The Tweifth International Conference on Learning Representations, 2024.
[34] Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejie Chi, and Yuxin Chen. Accelerating convergence of score-based diffusion models, provably. arXiv preprint arXiv:2403.0388 2024.
[35] Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Non-asymptotic conver- gence of discrete-time time diffusion models: New approach and improved rate. arXiv preprint arXiv:2402. 13901, 2024.
[36] Sitan Chen, Giannis Daras, and Alexandros G. Dimakis. Restoration-degraaattin beyond linear diffusions: non-asymptotic analysis for ddim-type samplers. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[37] Daniel Zhengyu Huang, Jiaoyang Huang, and Zhengjiang Lin. Convergence analysis of probability flow ode for score-based generative models. arXiv preprint arXiv:2404.0977 2024.
[38] Runjia Li, Qiwei Di, and Quanquan Gu. Unified convergence analysis for score-based diffusion models with deterministic samplers. In The Thirteenth International Conference on Learning Representations, 2025.
[39] Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprini arXiv:2408.023320 2024.
[40] Stefano Bruno, Ying Zhang, Dong-Young Lim, Ömer Deniz Akyildiz, and Sotirios Sabanis. On diffusion-basee generative models and their error bounds: The log-concave case with full convergence estimates. arXiv preprint arXiv:2311.13588 2023.
[41] Xuefeng Gao, Hoang M. Nguyen, and Lingjiong Zhu. Wasserstein convergence guarantees for a general class of score-based generative models. arXiv preprint arXiv:2311.1100: 2023.
[42] Francesco Pedrotti, Jan Maas, and Marco Mondelli. Improved convergence of score-based diffusion models via prediction-correctinn arXiv preprint arXiv:2305. 14164, 2023.
[43] Xumpeng Huang, Difan Zou, Hanze Dong, Yi Zhang, Yi-An Ma, and Tong Zhang. Reverse transition kernel: A flexible framework to accelerate diffusion inference. 2405.16387, 2024.
[44] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. In Advances in Neural Information Processing Systems, 2021.
[45] 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 on Learning Representations, 2025.
[46] Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky T. Q. Chen, Gabriel Synnaeve, Yossi Adi and Yaron Lipman. Discrete flow matching. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[47] Andrew Camphell, Jason Yim, Regina Barzilay, Tom Rainforth, and Tommi S. Jaakkola. Generative flows discrete state-spaces: Enabling multimodal flows with applications to protein co-design. In Proceedings of the 41st International Conference on Machine Learning, 2024.
[48] Zixiang Chen, Huizhuo Yuan, Yongqian Li, Yiwen Kou, Junkai Zhang, and Quanquan Gu. Fast sampling via discrete mon-markov diffusion models with predetermined transition time. In The Tight Annual Conference on Neural Information Processing Systems, 2024.
[49] 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. In The Thirteenth International Conference on Learning Representations, 2025.
12

---

[50] Yinuo Ren, Haoxuan Chen, Yuchen Zhu, Wei Guo, Yongxin Chen, Grant M. Rotskoff, Molei Tao, and Lexing Ying. Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms. arXiv preprint arXiv:2502.00224, 2025.
[51] Xunpeng Huang, Yingyu Lin, Nikki Lijing Kuang, Hanze Dong, Difan Zou, Yian Ma, and Tong Zhang. Almost linear convergence under minimal score assumptions: Quantized transition diffusion. arXiv preprint 2rX11 2025.
[52] J. R. Norris, Markov Chains. Cambridge University Press, 1997.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have highlighted our contribution and scope in the abstract, and have provided separate subsections for our contributions and relationship to previous works.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize 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 the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the achievability and the limitations of all our assumptions right after proposed them in the paper. We have also explicitly captured the dependency on both the computation and sampling complexity (see Table Tb, which is typically ignored in previous investigations.
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 their paper.
The paper should point out 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails 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 faimess.
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
14

---

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: The assumptions are highlighted Assumptions and and all proofs are given 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:
The paper does not contain 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 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.
15

---

(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:
The paper does not contain experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/ www.gdee/ooeeuusiseeeeeeeeeeeeee
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) haaipps.cc//ubll///uuuddd////eed htw.:iddeee/ooeeuuunissiiioooooo
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:
The paper does not contain experimental results.
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.
16

---

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: The paper does not contain experimental results.
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:
The paper does not contain experimental results.
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 in the paper conform, in every respect, with the NeurlPS Code of Ethics https http://nuuiuia http://wwwppppppppoo/c/cccccccta
17

---

Answer:
[Yes]
Justification:
The result in this paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a 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 is part foundational research that aims understand generic class of diffusion process, which is not tied to any particular application.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not 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 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 as 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe 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)?
Question:
Answer: [NA]
Justification: This paper does not pose risks regarding data models.
Guidelines:
The answer NA means that the paper poses such risks.
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
18

---

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 challenging, and many papers do not 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 (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not any 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 is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com ddtasets 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 it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset'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:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of 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 was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

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:
The LLM is only used during writing and editing of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non stansaaddard components.
Please refer LLM policy http:///eerrrrsscc///ooeeeeeeeee for what should or should not be described.
20

---

Appendix
Related Works
21
B Full List of Notations
22
Implementations of Discrete Diffusion Samplers
23
Numerical Simulations
23
Proof of Theorem
23
Proof of Corollary |
26
Proof of Theorem
27
G.1 Step 1: Decomposing total error
27
G.2 Step Identifying dominant term for discretization error
28
G.3 Step 3: Bounding dominant term for discretization error
28
Proof of Theorem
30
Step 1:
Constructing an approximate sampler
30
H.2
Step 2:
Establishing asymptotic equivalency
30
Step
Examining the error induced by asymptotically equivalent samplers
Step 4: Examining the rate of truncated 7-leaping
31
Proofs Auxiliary Lemmas
31
Proof of Lemma
31
Proof of Lemma
32
Proof of Lemma
Proof of Lemmal
33
Proof of Lemma
34
1.6
Proof of Lemma
36
Proof of Lemmal
36
L.8
Lemma 8 and proof
37
1.9
Lemma 9 and its proof
37
A
Related Works
Theory on Continuous Diffusion Models: There have been many works that have explored the performance guarantees of continuous-space diffusion models. While initial studies focused on
L score estimation eтror and exponential eтror bounds [26] 27 subsequent studies developed
polynomial error bounds under L score estimation error (e.g., 128
30
BI 32)). In particular,
29 first employed the Girsanov change-of measure framework for continuous diffusion models and obtained guarantees for Lipschitz-score distributions. This result was later improved under differential-ineque inequality- analysis in [24], which removed all regularity conditions and enlarged the distributional set to enforce the Lipschitz condition only for target and include all finite- variance targets. Their idea inspired analysis investigate differential differentiallinequulii based analysis
21

---

also for the discrete diffusion models. Apart from the works mentioned above, there are other works
that provide convergence guarantees on the discrete-time formulation directly [3
34 35 on the
deterministic sampler [3 37
38
39 on the Wasserstein distance 40 41 and on the modified
predictor-corrector sampling method 42 Recently, 43 provided unified eyvers-trrnsitionn
framework that include these stochastic samplers for continuous-space diffusion models.
Different from continuous-space diffusion models, discrete-space diffusion models are rising as strong candidate in generative modeling, especially for those tasks involving discrete data such as texts [0], images [2], and graphs [2]. having applications
Empirical Works on Discrete Difflusion Models:
even in the biochemical field [3]. Early ideas of discrete diffusion models can be traced back to [.. which was subsequently extended in [4 31 The continuous-
counterpart using CTMC was trained according to a variational inference objective, which maximizes an Evidence Lower-Bowee
developed in 19). In particular, all models in 44 3 9
(ELBO). While empirically effective, is hard for one to characterize the estimation error, which is implicit in the Jensen bound. Recently, (TO) first proposed the score-entropy estimation error which is easy to train, and they achieved empirical success compared autogressive models in text generation tasks. They also proposed a new discrete diffusion sampler by approximately solving the Tweedie's 's formula, which they call the Tweedic r-leaping sampler. Other than an improved training objective, there are other works that are focused on the conditional guidance in discrete diffusion models [ 22 45
on the discrete flow models 46 47). on the Mon-Markovian sampling process (48), on tin-tunnig [49], to name a few. For per-step sampling methods, note that the majority of these works (only except 9 use categorical sampling methods. yielding good empirical performances.
Theory on Discrete Diffusion Models: While there have been flourishing results for continuous- space diffusion models, the theoretical understanding of discrete diffusion models remains limited. All convergence results are given in Table Among them, [9] provided an early convergence analysis under the TV metric using the r-leaping sampler. However, the estimation error is quite strong, and the parameter dependencies are also high. More recently, under the score-entropy estimation errors, [17] provided the convergence result using the uniformization sampler on d-dimensional hypercube, samplers, 19 performed analyses by assuming the accessibility of a perfect per-step sampler via solving the Kolmogorov equation, 20 analyzed Euler-type method which differs from the standard Euler schemes 10 22 and 18] investigated the more practical r-leaping sampler. Among these works, required that the score-entropy loss is evaluated the continuous sampling path, whereas
which was subsequently extended to general [S] space in [8). For deterministic-step
19
20 only required such loss to be evaluated on the discrete sampling grid. Notably, all of these works [17
18
19 20 employed the Girsanov change-of -ffeauurr framework, which requires such regularity conditions (that the likelihood function is a path-wise local martingale) that are hard to check in practice. Recently, (50) investigated possible acceleration schemes in discrete diffusion models, and [51] used discrete diffusion techniques to solve for continuous diffusion problems under quantization.
18
B Full List of Notations
For any two functions fdd, 6, E) and g(d, 6, E), we write f(d, 5) S q(d,6, (resp. f(d,8,E) 2 g(d, 5, E)) for some universal constant (not depending on 8, d or T) L < (resp. L 0) if lim sunsup. [fd, // g(d,8,e) < L (resp. lim inf (d, a, s) ) 2 L). We write f(d, = 8, when both f(d, S 8,) and 8,e) 2 g(d, d,)) hold. Unless otherwise specified, we write z' (1 < S d) as the i-th element of vector r E {S] and [A]Ø as the (ih element of a matrix A. Also, write x E [S]
the i-th element removed. Define Ham (x, 3) as the Hamming distance between two vectors x and y (which is equal to the number of non-equal elements). We also write Hain (I) = Hain (I, 0) for brevity. For matrices A, B. Tr(A) is the trace of A, and A < B means that B- - A is positive semi semi-definite. For a positive integer n, [n] : .1,....77. n). Write 1, as vector of length S that contains all I' and Is as identity matrix of size S x S. Write 1 {.A} as the indicator function of an event A.
*In the DMPM algorithm 20 most one coordinate is updated at each step, whereas the standard Euler sampler 100 22) first constructs sampling probabilities for all coordinates and then performs a simultaneous categorical draw across all of them. Consequently, the number of flips at each step is random variable taking values in O to d (where is the dimension).
22

---

C Implementations of Discrete Diffusion Samplers
In this section, we provide the implementation of two practical sampling algorithms typically used in empirical studies, namely the Euler method and Tweedie 7-leaping [O]. We also provide our
construction of an approximate discrete sampler for the proof of Theorem 3 which we name as Truncated r-leaping.
Algorithm 1: Euler method (c.g.. [10,22)
Input: initial sample It, ~ Po, discretization points {(x] (with to = and i = - 8), estimated score these discretized points 8T -t-
for k = to N 1 do
Re, (z, + - (1 (V.
for do
Recall (2, a) from 9 Draw winss as follows:
a (+ st
w.p. P2g (ar a)((x=111111 - -4)
1241
w.p. + Ry. (ate : (tx+1 tx)
end end
Return: Ztn
Algorithm 2: Tweedie r-leaping (10)
Input:
initial sample It, Po. discretization points (4x [4 (with to 0 and IN = T 6),
estimated score on these discretized points 8T -T-fy
for k = to N do
for 1 do
Draw air., follows:
(# afe);
w.p. (lo (0-(0r- Br -n Moee
8T- (x
Bi Bi ,00))
[ - Br 1 Rro a
otherwise
end
end
Return: Ftw
D Numerical Simulations
In this section, we provide some numerical simulations to validate our theoretical results. The target distribution is synthetic autoregressive model with given coefficients.
E Proof of Theorem 1
Write X' == [S]d. To begin, we note the chain-rule of KL divergence as Theorem 1))
35 Theorem 1] (cf. 24
N-1
KL S KL(āollpo) +
Σ
Exa wāt [L (.1 ) pllPees Iee (Fr.
(24)
k=0
where, for each Nta, X,
KL (.1z Il (o ((2)) KL (.Ize,))l (+1xw)))
23

---

Algorithm 3: Truncated r-lcaping (used in Appendix H)
Input: initial sample Et, ~ Po. discretization points {tx] (with to 0 and t T 8),
estimated score on these discretized points $y s1-4,
for k= = to N do
R1, (z, y) Rt- (y, (8, sT (y.
for i = to d do
For each E [S], recall that the token-wise rate ftj. E RXS is defined in 9
R (2,20) = Re, (212 F7 ax {= f== m Va + x
with R2 (c), ==
== -=--nels Cee(s] (x), :)); axtil
Draw Tbe follows:
Ralei, (1- exp (Rtg (1u+1 (6x)))-x)))
a (f x
w.p. -Ry (eig
(n))
Zle
w.p. exp RR ( tx))
(23)
end
end
Return: TiN
0.035
0.030
Estiamted Ki-divergence
0.020
0.015
0.010
0.005
0.000
2
Vocabulary size
Figure 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here We use Euler method to obtain 2000000 samples to estimate the KI. divergence.
cl+1
(Teje (-121, Mlpej,, ((..)))
at
By Lemma 8 we can take the limit l which yields
KL 1lt, (-I Mlpp, 1lt, (l(x()))
KL (-1z4, MPpaa (- (dtt.
(25)
Ot
suffices to provide an upper bound for the partial derivative of the KI. divergence. Below, for notation brevity, omit the conditional dependence Iz, in notation and write Teje. (z)

---

3x10
Euler method
Vanilla rllaping Tweedie r-leaping
Final Accuracy (in TV]
xx
10a
Number of Steps
Estimated total variation distance between the target and sampling distribution of different sampling methods. Here d d= and S = 8. We use 30000 samples to estimate the TV distance.
Figure 2:
Tejes (3r(ar))) (resp. Petee (x:)). We have
KL (Tr (-12a, MlPeje (+12t,))
Öt
0
Tejec (x) Pelce (x)
Tojer (x))
log
Ot
TEX
Teiia (xx)
23 Teje (x)
9
Dele (x) Pejez (x)
8
Σ sed
Telee (2r)
log
+
Σ
Teles (x)
0t
Peica (Ir)
Te (x)
DEN
2 Tejea (xr)
Teesa (x:)
85 BrPa en (ar) Pejee (x)
log
Teler (x)
Pelee (xr)
=:Ti
=
Using the Kolmogorov forward equation (see
(T) and reversing x and y, we have
Tejee (x)
Tele. (v) Pejea (v)
T = Σ
Σ
Relu. x Viee (v)
log
Σ Z.DEX
Re v) (x) log
Pelea (x)
ZEX
BEX
Telta (v)
T2
Σ
x) = Σ
Ro(a, ())
Pejta (x)
Pejez (v)
ZEX
BEX
Z.EEX
In order show the desired result, need relate the ratio of densities with that of the rate matrices. Recall the definition of R, in We have
Telt. (2)/ (x)
Telt (x) Peicy (x)
Ti Σ Re(x, Topa (x: log X
+
Σ xex
Tejea (x) log
Σ Re(
Pijta (v) Petty (x)
HEX
Jote, (v) Teles (z)
Σ (a v) log
Petaa (w) Peje, (x)
Re w) - u (v.
Σ
Ra x)) Σ
Ra(a,, T) (2) log
Petea (V)/Pejcs (x)
ZEX
E.VEX
x
25

---

where (i) follows because Evex Re(a, y) = O, and (di) follows by Lemma 9 (2 x
(where the conditioned
Fte omitted for brevity) and note that R (y.
RT (y,, z). Thus.
or T- 22 1
T - T2
Σ
(2( - 2z) Telce (x:)
ZEA'
V) Re(s, ( Pelta (1)/ Prlca (z)
- (y,
Tepez (v) Tele (x) Pelen (t)/Pele. (x)
Σ
Telea (x)
Ree (2., v)
a.ee zzy
Σ Re(x, v) log Re(
Σ
Re(2,2) - 2)) +
(x)
Re(x,,)
ZEN
yEX vサ=
Tap (x) (Ralor)) log Re /) RT- 1T (y,x)
Tele. (V)/ (x) Re(a,w) Pejez //jeee///ee// (t)
Σ
b2 (V) Pelee (1:)
EYEX z7y
Now, since log 2 2 for all we have
(x( (R( u)/ RT-11 -1 (U, -1)
Tejen (V)/ (x)
R s Σ Tejee (x)
Re (e(x,))
Palta (1)/ (V)/Ptjc. (x)
Pelea (3) (x))
xyEX wzy
Pe (v) Pt/e,, (x) -1)
Tr (u))v))/eee (x)
Telea (V)/ūalea (x) Re 8)
(156)
Σ
Pelea (B)/Ptjt, (x)
XEEX
wzy
Tejec (w)/Tetea
Tspes (V) (2x) Patta (8) /Ptep (x)
(1)
Tepee (x) Rx +
Σ
Ter (e)
Pelc, (v) PP/
2NEX azy
0
where (iii) is again by Lemma (2, & 0. Therefore,
(iv) follows because EpEx (x, y) = 0, and (v) follows because
Exsr -ā
(L (-1222)) Mleee (112))))
Relai, v) log (x( v) Rs (xe. v)
E
21x Tup aeru (-128y))
Re(se, (in)))-(((xaaa (1 + Σ
VEN
R 5) Ri (21, 4)
Σ Ra(a,.u) - R.(x..)) + Re (2x, v) log
VEN
The proof is now complete by combining this with and 25
F Proof of Corollary I
The proof is straight-forward by noting that
Re v)
Bxe
Σ
Re( v) (x,, 4) + Ra v) log
R, v)
26

---

xz) RT- 2 x2)) 9T (1)
Bx rife
Σ 1ト21
RT
-r- (2ie)
9T (x))
RT- (y, (yT 1T ((
+ RT Rly
x1)
log
RT (y,, (e) - Zoz)
Eggnge
Σ
RT ((y,
qr qr-((y)
+ Cr (r-
log
Pr--(u)/qr -x)))
()-)(
9T (2x)
ST 8T- xz)
LT 8T-))
where the last line follows from the definition of score-entropy in
G Proof of Theorem 2
In this section, provide the proof of Theorem Before start, the following assumption characterizes those general approximate deterministic-step-aae samplers (i.c., approximation to the Kolmogorov samplers) that sample efficiently.
Definition 1 (Approximate Sampling Method). The sampling rate RG is piecewise constant, i.e.,
constant within E [ta, fx+1). Also, given It, e [s] we have ( Rr, (z)
Definition D is especially useful for discrete diffusion models where the exact solution of the Kol- mogorov equation of the sampling CTMC is computationally hard to obtain. In particular, Definition satisfied for the rate r-leaping (see 77. It will also be satisfied for the truncated r-leaping method later (see 30
G.1
Step 1: Decomposing total error
To begin, we can employ the general result of Theorem and get that
KL )
N
< KKLTollpo (Po) +
Σ
E Eng ~u
[KL(ūtaralee
(1]x)))]
k=
N
tk+1
Rolar, Re( + Re v) log Re(xe, v) Re v)
< <KL(TollPo) +
Σ
Expiie
Σ yo
dl.
Amm 0
(we)
(26)
Note that is Bregman divergence (generated by the negative entropy function) for each and thus (x(x) 2 for all [S]a. To see this, we fix I, and consider two vectors p and such that Py := (x y) and qy := (2x, y) such that y * Fy. Also, let <(p) : Ey Py log (i.e., the negative entropy function, which is convex), and the corresponding Bregman divergence is Dolp.g) = Φ(p) <(g) (y Φ(v)) = Eyzta Py log dy log fy (p, 9gy( + log q,)
E Eyse, Py Log(py/gg 9g) Py gy, which is exactly gr. We further decompose 9i into three different terms:
KL(ārllPT) < KL(Tollpo)
Σ
Bxi (g dt
KL
(1x+1 - lu Ex ten Iore (Irew)
iniiializaion errrr
estimation error
E ze (gr(x)) g((2))) Exr, mic (g(()))) It. (Ir d dt.
(27)
Dzy ritt
discretization erroe
27

---

From 19 Proposition 2] and [8] Theorem C.1]. the initialization error satisfies that
KL(Tullpo) x lolog S)e
Recall and
Note that the estimation error term can be upper-boundee as
(tx+1 th Bo,, wice
lot (I
N-1
Rei (J
(1++1 1s.) Base wer 1k
Σ Vr
Rey (Fen: - Ray (Stt v) + Row (Fte, v) log
Re, (Des v)
k=
N-1
= (4x+1 - 1x. Bes, -er-
Σ -r (1,, Ttx)x
k=0
Q1-11(0) (1)
9r 91--1 (v)
log 9r- (w)/er -ee (1r 8T- tt (V. Drn
8T tu (y, (1y)
+
GT -T-44, to (3rte)
9r- (1ta)
N-1
(1x+1-4)) - (L) L2i 81-
k=
I Exoore:
where the last line follows from Assumption T As follows, the goal is to provide an upper bound for the discretization error.
G.2 Step 2: Identifying dominant term for discretization error
As shown in (27). the discretization error can be decomposed into two terms, one for the time- difference in the argument of dt (in expected value), and the other for the difference in di itself. In the following lemma, we show that the former term decays faster than the other, which further implies that the latter term is the dominant error term for the discretization error. Lemma 1. For each k O, O....,N-- and E [tx, 1x+1). We have
E a (ar( - (.( )] S (1 dd Expnj (gc (a:))
Proof. See Appendix I.I
As result of Lemmal
suppose that tx+1 - tt S K, we further have
E x (oc(x)) ga (x(x)a)) S k 0 (L, T-6
Br (ec( dt
Zec -8
1T--0 Es, ~e,, (g)()))) 94a (Iee
T
K O Escore +
(28)
Here the last line follows from the decomposition of 9r as in 27 Thus, this term (corresponding to the difference in Z3 in expectation) does not contribute to the overall rate as long as 0.
G.3
Step 3: Bounding dominant term for discretization error
Now, control the second term in the discretization error in (27), which is also the dominant error term as shown in Step 2. We also explicitly express its parameter dependencies. The following lemma provides useful score bound for further analysis, which is similar (18 Remark B.3] and [19 Lemma 2] and provided here for completeness.
Lemma 2. Fix > 0 and x f y such that Ham (x,v) v) Given the forward process in T with rate given in 2 we have
(
S max(1,t-1].
(x)
28

---

Proof. See Appendix I.2
Now, we can upper-bound the error due to difference in gt as a difference in the likelihood ratio, as shown in the following lemma.
Lemma 3. Fixt E [tt, 11+)). Under Assumption and Definition
we have
Bar uun (ge()))) - 9o2 (Iw)) & (1 + log(MS8 (og w0t
Re(F v) - Roz (oe.. v)
Proof. See Appendix 1.3
Now, for any Sts E [S]0, the sum difference in the reverse rate can be further calculated using (3) as
Ex u
Σ
Rey (Iee, v) Ro (Jiz v)
9r 9r-44 (V)
RT -e- (1, - 9T- 91-1(3) Rr c I(x)
Been ~i
qa (Iite)
QT (
9r -r (v)
(r-
Beey Tth
Rr (V,
Qr -1 (Dex)
(r-((
yofrr Ham y.eey) ==1
(29)
where the last line follows because (V = (1, whenever + It, since 3r = 1.
Due continuity of this ratio (i.e., the concrete score), one common way to upper bound its derivative uniformly for every fixed and such that Ham (æ, y) 1. Indeed, this is the approach taken by 18 Proposition C.2] (cf. [9 Proposition 6)). For reasons of comparison, the following upper-bound adopts the derivative-basse
method as in [18] Proposition C.2].
Lemma 4 (Following the idea (18). Fix s < such that s is small. Fix x and such that
Ham (z, 3) 1. Given the forward process in I with rate given in (2). have
(x(v) (x(x)
(x())
X ds² max - (t 8)-
(x)
This further implies that
9T (1) (8)
Bey Bek
Σ of Ham (y. ==1
RT (v.
91 -1 (Ite)
(
S S² max {1, (T - -2 (t ts).
Proof. See Appendix
1.4
Then, we present our novel approach below that directly provides an upper bound in expectation. This will finally result in tighter upper bound with linear S dependency. Lemma 5. Fix < such that f. s is small. Given the forward process in with a rate given in
have
(v))
(x)
E Eggrage
Σ yy Ham(y.z;)=
Re(y,
(x())
go (xx)
dS maaxf11 -²](( 5) d max[1,s-1]] -s)
$ d max(lx -22 -2] 8).
Proof. See Appendix 1.5
29

---

Thus, considering the two terms in 29 we have the following bound for the expected difference in the reverse rate matrix:
Σ
Rez (F y) Re(xre w) 2 df max (T' t(+11 - tx).
Collecting the results from Steps 1-3, we would arrive KT. )
5 d(log S)e= - + Escore + df log log(M
Σ max (T ( tx)².
Finally, to determine the overall parameter dependencies in the above summation, we can consider the particular step-size: 1x+1 l K: min {1,7 T [ and invoke (24 Lemma 18), which shows that
N-1 m1 (T (2+1) 1 [(u++ - (x)² x <(T + 8).
Also, from the last part of Theorem 6], the perturbation due to early-stopping TV(4: 9s) E d6, as d + 0.
The proof for Theorem is complete.
H Proof of Theorem
The proof of Theorem S consists of three parts. First, construct non-trivial approximate discrete sampler, the truncated r-leaping algorithm, with explicit intermediate rate that allows for categorical per-step sampling. Then, show that our truncated r-leaping asymptotically equivalent both the Euler method and Tweedie r-leaping in terms of the categorical sampling probabilities. Finally, we show that our proof of Theorem is applicable even for such asymptotically equivalent samplers, which is further evidence of the generality of our approach.
H.1 Step I: Constructing an approximate sampler
To start, we propose an approximate discrete sampler that modifies the vanilla r-leaping algorithm and enables categorical sampling. We call this sampler the truncated r-leaping algorithm (see Appendix C). The intuition is that we only allow the first state change (a.k.a. truncated) for each dimension according to (7). This intuition is made solid by the following proposition, which shows explicitly the rate of truncated releaping.
Lemma 6. Fix k E {o...... N 1) and Ft, E (SS]d The truncated r-leaping algorithm corresponds to the following rate matrix: Vt E [tx. tk+1) and V(x, y) I # y.
RXILL (x, u) == Re, (Ir, V x x1,)1 {nzind(y - x) E zeros(r - It2 where uzind(y- x) is the only index i* such that x² # v² and zeros(v) = {i : v 0} is the set of indices having zeros in a vector u E [S]
(30)
Proof. See Appendix L6
H.2 Step 2: Establishing asymptotic equivalency
Then, we show that both the Euler method and Tweedie r-leaping are (first-order) asymptotically equivalent to truncated r-leaping. This is summarized in the following proposition.
Lemma 7. Fix ty [0,T 5), Ite E [S] and i E [d]. With some abuse of notation, write Piruncated (a). Piveedie (a), and Pirter (a) for the conditional probability of I a given It, for these three algorithms, respectively. Then, as tx+1 - tx + 0,
pi Prancuted( (a) = Pi (aider(a)) (a) + o(1) = p Pireedie (a -00(1+o(1)) o()), Va E [S].
Proof. See Appendix L.7
In the context of Theorem note that 1++1 4 < K. Thus, Lemma shows that the constructed truncated r-leaping is asymptotically equivalent to both the Fuler method and Tweedie r-leaping when K 0 (or equivalently, when N + oo).
30

---

H.3 Step 3: Examining the error induced by asymptotically equivalent samplers
Let P4z denote the (exact) conditional probability from truncated r-leaping, and let Pl l84 be any conditional probability such that P lty (-(are))) - Pe lt (-Jare)) + +(1) for fixed It, [S]4 as k > O. Previously, from Lemma 7 we have shown that both Euler method and Tweedie --leaping are special cases of such Piztslte"
useful property for such Pls is that, for fixed 25e. [S] as tx+1 tx - O.
KL alt (-1202 MlPt (-121x))
Dea+slle lee (T/
Σ
Tteeslte (T) log
Pest llc (3) (T())
2E|S/
Tea alte (8/
= Σ
Stufalty (2) log
Σ #E(S]
Tt It ( log 1+ o(1)
Pent lee (T)(Te))
=E[
Tee+ Ilee (f)
= Σ
Teu 1lx (#)
log
Σ
T I& (i/
Peut 1 ltc (2)
=E[S)
$E(S]a
Ith alle ( (2)2)))
=
sta 16, (z) log
Pet (7) Ttt,)
+ o(1)
(31)
2E|S|
Now we consider the decomposition in 26 We have
(ātx I
KL
Bus wis
KL KKL(Tunzate (f MP (1 })]
k=0
S (L
Buy Wit
[KL(Tee us
(-122t,)) )]]
k=0
where the last line follows from (31). Thus we have recovered the result in (26).
H.4 Step 4: Examining the rate of truncated r-leaping
Now, we can verify that the rate matrix in (30) satisfies Definition just as vanilla r-leaping. Thus, the rate of Theorem 2 still holds if we substitute r-leaping with truncated r-leaping. The proof of Theorem is now complete.
Proofs of Auxiliary Lemmas
I.1 Proof of Lemma
With the forward process in ( we have
-i-ui (gc(xe) - go (x+1))
Zet ~ie
Eggrqe
(o(xz)
Σ
GT - (2))
me E(S]"
go(xe)
Σ
(1 (ate = xx + Re 2ee (t tx)) gr( to tx)
Bey E[S]
(t 1xk) 1xx) Eurs
Σ
Re(xe, Ney (o(()(e))
+ olt - 1x)
De, E(S]"
to tx)Barrn I(- xx) + oft tx)
31

---

(t (x) S-1 d. B.rr (gx()))) + o(t - tx)
5
where (i) follows because (x) 2 0 and Re( y) 2 if # Also, for the last line, note that
(x, = Ey yz (2, y) S-1 when 3r = 1. The proof is now complete.
5
1.2 Proof of Lemma
Let j be the only index such that x² + y². First, we note that
gr (v)
go (1o)) u(l
26 (z)
(x
20 E0E[S)
i
II ic(d)
To (00)
(c(a:)
RuE|S|
L (e") (3)) (gt 2ejo (2) (mz) )
(xxo
II iE|d
ohjo (ze (ejo(("())))
4 (
Z0E[S
(x (20
HooCor (an)) T/ (ars)
18
(x(x))
To (SS
(o (=()
E Zo
(32)
61 (=)))=1))) (z%)
where both (1) and (w) follow because with the chosen Rg in (2) each dimension propagates inde- pendently in the forward process (ef. [9] Prop. 3J). Note that the reverse process does not propagate independently.
To obtain an analytical solution for the conditional probability, we can solve the Kolmogorov forward equation for the i-th dimension (vi E [d] (cf. [19] Proposition I]):
d dt (ho(2la)=
Σ SE[S]
R. (2,2),
whose solution is
(hj((1aa== - exp (f" regakdss) ]
(a, 2) -lexp (t. (a. = Pexp (a,
(S- (1- (1+ 1)
if 2 + a
(33)
if 2 =
where we recall that Ryck Rease when Br = 1 and we denote the eigendecompossiion of Roase
s 1s1] Is as Roase PAP-1, Thus, plugging back into 32 we have
if # x and Dd + x af = 2 but y¹ + 1/
( (a() Th (20 (ar)
(34)
1= (5 lje
if + 2ef but n¹ J/
Among the three cases above, since - > O, the second case satisfies that the third case satisfies that
I+(5-1)e S 1. Also,
1-
1 + (S 1)e-
1
SS1 2 otherwise
1
1-6-1
et
SS S max
Therefore, the bound is desired.
32

---

I.3 Proof of Lemma 3
By definition of Jt, we have
Be wite (gc(
Dc, (1isa)
Been ~0th
E
(e((x))))
Ree (o1). - (Re 3) Roz (2
(2 y) log Re Re( W)
Rei (ven Rea (Dez. v)
Re,, (oee log
Re (312. 1)
(
Res (Dte log Re, (Fees v) Res (Zess y)
Eus, with
Re( v) log
Res (ors))) y)
(Re(Iee.))
Roz (ITL.
< Eas ~0
Σ UF
(r(e v) Rei (wen w) (1 + loog Re, (Rre wi
+ RelEte y) log Re 4) - Ro (Du ÿ) log Res (Fee 20
(1 + log( (MS8
Ba Ti
Ri((en Rei (2)t): v)
where (i) follows by Definition We explain (it) as follows. First, from (5. if x + y.
Be (x, u) Rr (v, x) (u. x) E [M- "MM''-
under Assumption which further implies that log Rr. (x, v) < log(MS), Also,
(I 8) log Rr (I0z. v) Reg (Iez y) log Re, (Fee 8)
(111) (1 + log RT-)) (are v) - Re, (dre) w)
(10) 3 (1 (1gg0((8811) (e v) - Rei (Fezs v)
where (iii) follows from the internediate-value theorem for f(z) = = log = and it" is a num- ber between Ry (Ite y) and (I y). and (iv) follows because, by Lemma 2 (x,
RT- x) gr-((v) S max [1, (T 1)- S 8-1 for all / > if + y. Meanwhile, by sym- (()
metry, R₂ (I. 3) 2 5 mmxx( 2J 2 5 The proof is now complete.
1.4 Proof of Lemma
The idea comes from [18
Proposition C.2]. When t - is small, we note that the derivative of the
likelihood ratio w.r.t. t is equal to
i
Je (v)
at (v)
0
(0))) (x)
S [9((
(x(x) + g0(3) a [x)
Øt
q6 (z)
qe (z)
(x)2
q((x))
Now, by Kolmogorov forward equation,
dt (x)
(e(v') Ra(l
2e (x)
W'ELS q((x)
(v)
Σ
ge(v))
+ d
5 1 (1)
5 (x)
(v)
S go (T)
y' "
Ham (v.// Ham(y.s/)
33

---

ds² max (1, (1, + ds max
x ds max
where (i) follows from Lemma similar argument, we have
2 and note that the summation has d(S 1) terms in total. With
(x)
qe(o') (x(x)
+ d S 1-1 S dS max(1,
Σ
Ør (z)
S
d'Els Ham (1,0 ==
Therefore,
θ qe(U))
S ds² max(1,
Öt
(x(x))
and thus
Ye (v)
go (v)
(e())
(t- 8) S dse max 11x 8),
(x)
Is xx)
Öt
(x(x)
as claimed. Especially note the quadratic dependency on
1.5
Proof of Lemma 5
First, fix xe and y and let i be the index such that æi
+ y². From 32 we have.
ge(()
ge(())
Lo (=))
210 (o (1))
Exo 2ole
Eso (11aa)
4o (1re)
2s (3+x)
S4o (1((1))))))
1 (xr) (ang)
(oo(("))a)) (zt) Lo (2t)
(1)())))))))
E E
2ejo (x21())))))))
( (xb)
+
E to (111))) Za (-12e)
(35)
(a
1 (x1())))))
For the first term in (35 we note the expression of likelihood ratio in 34 and thus, for any fixed To. Te, and y.
if x * z and y # x/
2
(a8))
l-e-t I+1s- 115-1Dp 1)e-
1-e- I+(S-1Je-1
if ot =/ but y² + xb
(5 1)e-
1+
if xt + vb but y² z
1-
1-e-
Now, since
1 -
Set S + el 1)2 S
01
1 (S 1)6-1
0
(1 (S 1)e
Se:
s
S
0t
1- --
el 1)2
min {1,1)
have
(1000)))))) (2b)
S
(1 - ss.
C a (or (ar6))
L (oe (mn))
min {1,
Note that this term does not depend on d. Thus,
(1(6))))))))))))))
(1))))))))))
Eg ruge
Σ
E Eno (12z) F (xt))))
By Ham(g.zx)=1
S dS max {1,t-2} (t s).
34

---

Now we turn to the second term in (35 Write f(=) == (v'
for brevity (recall that 2a and are
% [2)
fixed and thus omitted in this expression). Note that from 33 upper bound f(z) is
(v'l3
sup 9¹ [[[S]
f(2)
sup y = 4 (<)|z) S max(1, '3.
Thus, the second term in 35 can be upper-
upper-bounded bounded (for each y²) as
(egrrgore((las) 2g (1
[S(x)) [(tb]]
Σ
(1001)) (000(100
RoE|S)4
S S ma
Σ
(20pr() - (20 [x) (36)
moE(s]
Using Bayes' rule, we have
(.10(1e/200)
Σ (xollz)) - (0)o(=0|21)]==
Σ (u()))
(xx))
gx(xe)
no E0E
(o (vo) | (200 (sjo(=e (ocellrodee (2 lyo)
(x())) a (x4)
< (e(x))) qa (xx)))
Exp 30000 [000(10 (=)0 (=)0(=))3)))
+ (9.10(=1lu0) -ejo (=10(<>
E Rizorgo [0 - (=)
(e(x)) Fyongo [_)0())))0)) (c)((e))0o)
q: (24))
2
B Beoongo (=) - [=)o(=2/<zo)--
(37)
q (x2e
Now, this term (without the constant factor 2) can be upper-bounded
(x())) E Exongo |u10(1)))20)) (=)0(=))(00)
i (0
(c())) (t - 30
at
(x(ere) (1 -88) Ezo
Σ
2nj (Tr (uro) Ra (R, vt))
RIELS
(x())) (1 8) B
Σ
(n (5t,
1.E[S)
(it)
(1 8)
(T,,
(38)
where (i) follows from Kolmogorov forward equation. Thus, combining these intermediate results, have
E
E Bno (- 50 (mmr))
[f(xt) - f(8b)] Re(y.z))
M Hamm (g.ur)
dS mmx{1,s511 Enrng
E Exangs (q10(2)/20) - (010(21000))
ge(xx)
35

---

(:(Tt)
(1 s)dS max (1, " "BBrraa
[ [a)(
2111 at (x()))
(t - s)dS max{1, s
1 1
Σ
[Re 24)1
my E||a
(t s)d mmax ( s1)
where (ii) follows from (36) and (37). (iii follows from (38). and (iv) follows because - -Rc(2,
Eyn Ra y)
--1 g d for all v, [S]a. The proof is now complete.
I.6 Proof of Lemma
Note that (x, v) 0 whenever Ham (x, 2 2 by definition of Ri,- Also recall the definition
of the token-wise rate R in (9) Note that R is valid rate matrix since Eeels) R2 a) = for
all E [S] and [ a) 2 0 if Fa.
Fix and such that Ham (x, v) = 1. Let E [d] be the (only) index such that y" * xt We now divide into the following three cases:
1. Case 1: R (="(.""")))
Ftg. Then, zeros(æ Ita) [S]. and (2, (o v)
2. Case 2: x # Fee but xf = she Thus, i E zeros(x - xt,), and (x, =
Re, (Ien vin 0r (-)5') fty v1")
3. Case 3: x" # xf. (and also x + Tte). Then, i" & zeros(x - Ita)), and RT. (s, y) = O.
Thus, the overall CTMC is equivalent to S CTMC's, one for each dimension. The transition rate matrix on the i-th dimension is (2, a) { = zi, }. Notably, at most one state transition can happen during E [fx, 1x+1) (where the CTMC stops after its first transition). We can also calculate the corresponding state transition probability by solving the Kolmogorov forward equation, which is equal to (for example, see [52) Chap. 2J)
cxp (Ri (tx+1 - tx))
ifa= a/e
Pi Pie { =a/z }
Ascei, a))
(1 (1- exp (it ( (ta)) tn))
if a s/c
-RC )
This is the same as the transition in (3). The proof is now complete.
I.7 Proof of Lemma
Recall the conditional probabilities from 23 8 and (00.. Also there we have defined Rt such that
(1 a) fie (Fez Th @ a); Ya + #
As follows, we only consider all E [S] such that + ri. since all probability vectors need to sum
up as 1.
We first focus on the Euler method. From 23
(xh,,)))))
pr Piuncated (a)
(1-ea) exp (R (lx+1 tk))
R (
(r a)
[ (2/ 2 ((t+41 - tx) + o(te+1 +4))
-R, (+t , (
-Ri ()((k+11 - (1) o(1))
Pinter (1) + o(1)..
Also, for Tweedie r-leppigg, from 10 we have
pi
P (a)
36

---

((e (Br-ry ( - Mo M ai 81- (27e" Bss xtee [ - M) 1.
= 16u- - (Br-ue -r-1 -2t1 Risse (a, :) 11 Bi: (3r - - R (a 211 o(1))
-T (Fry @b (,11)((111
Br- 16-1 ) Rlase (a, 2/, (1 d(1)
-T- (#te @bs u, st, (1++1 - 11))3r-1 Reaee (a, Fz (1))
-T-- (Ite (Ds a, Ft. -1 (1 aBs a, Fz, (1x+1 4x)(1 + o(1)
(x (t(++ (1 o(1))
Patter (a) o(1))
where 6g is such that Ham (6,, 0) and [6,] 1. The proof is complete.
1.8 Lemma 8 its proof
Lemma 8. Fix E [S].. We have
lim (Ha)lllaa (-la) = 0. 8i8
Proof of Lemma
First, we have
lim KL (1a)] (11aa))))))) 2/%k
Talea (3r (a)
lim
Σ
Topre (x(aa) log
88%
Patea (Ilaa
TEN
Jalex (ar(a) Palca (I(aa
lim slix
Tstte (xxaa) log
xEX
Tstes (x/aa)
lim Toten (xla) silt
lim log
Pale, (2
TE
Here (+) follows because, different from the case where X' Rd and summation because has finite cardinality. Now, by definition the CTMC process (see (T).
safely interchange the limit
lim To (xla) = lim Patta (x/a) (x = =a
804g
sit
which implies the desired result.
I,9 Lemma and its proof
Lemma 9, Fix L (thus T - -T - and [5]
We have
(ula(
R. v) (x(a) R R Vz + y.
Here RT- is defined as the rate matrix for the forward CTMC at time T t conditioned on the future observation at time T being Indeed, further have
( RT (v. (0).
- 9T (
Proof of Lemma
Fix x + y. First, by Bayes' rule, ví (8, 1) (and thus - T T 1),
(uko, a) = -r- a) = - (xly, 0T-IT-s
For the left-hand side, by the Markov property of the reverse process, have that
i
lim E- 01
Tee. (y/ a) = lim
T)(() Ra v)-
iut
37

---

For the right-hand side, we note that
9T - (8/la
lim
4r (
2-+ Ot
8r - (x)
r
0
- (y)aa)
8e - -
lim
lim Qr -1------ (xly, a)
[-f
01
1r-ir- (
(-+
-- (1) ())
i
fr 17- (y/a)
lim
6-
00
0r-1r-- (x
0r-1r- (v(a)
= lim - (xly,, a)
E+s Ot
(T-
where (i) follows because lim; 9r- -, (x y. a) = for # y. Also, by Kolmogorov backward equation,
0 Ot 9T HT -.T = 0(T t) 47 - -1T (
8
4T 11-
#E[S]
where o -la) is the rate matrix for the forward CTMC at time T conditioned the future event that the observation at time T - is a. Then, combining both sides, we would get
(y-(a(a) RT RT- 2/a). (z|aa
Rx(x,
Lastly, we ensure that the conditioned rate is well-defined. Fix s' < t' < T'. Note that
Reir (y, xla) = lim s' or T (x) a).
Thus, we obviously have Ryprr (v, 0 for all + if (alp 0. Otherwise, we have
Repp (y,
0
lim 20 (x)u,
0y
1
lim
(aly))
s'-t' 4 (a y) ot
1
-lim
s' 4r (aly) y) du (a
lim
1
Σ #E(S]*
Re( 8)T (alā) + (a(o(
Σ
We (aly) (8,
s'-2' qr (a
$E(S]4
(a(z) 4r (aly)
Rs (y.x)
which is finite and non-negative when x + y. The proof is now complete.
38


Reviews:
[{"review_id": "EdE4v5CoPV", "reviewer": "Reviewer_ieBG", "summary": "This paper extends the theoretical guarantee if discrete diffusion samplers with a novel framework. Specifically, the quadratic dependency on vocabulary size in the iteration guarantee is improved to linear and new convergence on two practically efficient samplers are further provided.", "questions": "I don't have further questions.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well-structured and well-written with thorough proof. Assumptions are properly discussed. Detailed discussion and a comprehensive comparison with related works are included, which is very helpful.\n- The theoretical contribution is clear and strong. The convergence guarantee is proved without regularity conditions. The iteration guarantee of $\\tau$-leaping is improved and new convergence results on practical samplers are provided.\n\nI am satisfied with this paper and I don't find any significant issues. I am familiar with diffusion models but not particularly familiar with this specific field. I will continue to refer to the opinions of other reviewers for a more comprehensive evaluation.", "was_revised": true, "final_justification": "After reading the other valuable reviews, I believe that the quality and potential impact of this paper are worthy of recognition. I keep my current rating.", "rebuttal": "We sincerely thank the reviewer for providing valuable feedback, for the positive comments,  and for recognizing our contributions. We greatly appreciate your time and effort in reviewing our paper."}, {"review_id": "yqRDElsUHz", "reviewer": "Reviewer_qy7m", "summary": "The paper introduces a novel analytical framework for discrete diffusion models based on differential inequalities. This new technique circumvents the need for restrictive regularity assumptions previously required by methods relying on the Girsanov change-of-measure framework. The primary contributions are: (1) The development of a more flexible analysis tool for discrete diffusion models. (2) An improved convergence guarantee for the popular $\\tau$-leaping sampler, as well as the first-ever convergence guarantees for the empirically efficient Euler method and Tweedie $\\tau$-leaping samplers.", "questions": "- Your results in Theorems 2 and 3 show that the Euler and Tweedie $\\tau$-leaping samplers have the same asympotic convergence rate as $\\tau$-leaping, but with a significantly lower per-step sampling complexity. Does it suggest that there are larger hidden constants in the convergence bounds for these samplers that may impact their practical performance?\n- Can your analysis extend to the high-order samplers as in [1]?\n\n[1] Ren, Yinuo, et al. \"Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms.\" arXiv preprint arXiv:2502.00234 (2025).", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength\n- The novel differential inequality analysis removes restrictive Girsanov-based regularity assumptions, a significant theoretical advance.\n- The improved linear dependency on vocabulary size S for $\\tau$-leaping is a key result with practical importance.\n- This paper provides the first-ever convergence guarantees for the efficient Euler and Tweedie $\\tau$-leaping samplers.\n- The paper is clear and well-organized, and the included comparison table is very helpful for context.\n\n### Weaknesses\n- The work is entirely theoretical and lacks any empirical validation to support its findings.\n- The convergence rates maintain a quadratic dependence on data dimension $d$, which remains a practical limitation.", "was_revised": true, "final_justification": "I am keeping my rating (4, Borderline Accept), as this paper is well-written and provides improved results based on previous works.", "rebuttal": "We sincerely thank the reviewer for providing valuable feedback and greatly appreciate your time and effort in reviewing our paper.\n\n**Q1:** The work is entirely theoretical and lacks any empirical validation to support its findings.\n\n**A1:** We appreciate the reviewer’s concern. We have included two tables to provide empirical support for our theoretical results. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical characterization of linear dependence on $S$. Table 2 compares the performance of the Euler method and Tweedie $\\tau$-leaping against the standard $\\tau$-leaping algorithm (in terms of the estimated TV distance between the target and the sampling distribution), highlighting their superior efficiency and practical advantage.\n\n| Vocabulary Size ($S$) |Estimated KL Divergence |\n| - | - |\n| 3 | 5.93$\\times$$10^{-3}$ |\n| 4 | 1.32$\\times$$10^{-2}$ |\n| 5 | 2.10$\\times$$10^{-2}$ |\n| 6 | 3.38$\\times$$10^{-2}$ |\n| 7 | 3.77$\\times$$10^{-2}$ |\n\n\nTable 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.\n\n| Number of steps | 16 | 32 | 64 | 128 |\n| - | - | - | - | - |\n| Vanilla $\\tau$-leaping | 0.290 | 0.215 | 0.179 | 0.161 |\n| Euler method | 0.193 | 0.165 | 0.152 | 0.151 |\n| Tweedie $\\tau$-leaping | 0.176 | 0.158 | 0.155 | 0.153 |\n\nTable 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.\n\nPlease note that the empirical performance of these practical samplers like $\\tau$-leaping, Euler, and Tweedie $\\tau$-leaping have also been widely studied in many existing experimental works, e.g., [1-3].\n\n**Q2:** The convergence rates maintain a quadratic dependence on data dimension $d$, which remains a practical limitation.\n\n**A2:** We thank the reviewer for this thoughtful observation. Indeed, our convergence bounds scale quadratically in $d$, which is consistent with the prior work of [4]. While reducing this dependency remains an important open direction, our main contribution is the **reduction of the dependence on vocabulary size $S$** from quadratic to linear — a critical improvement in NLP and sequence modeling where $S \\gg d$. For example, in [1-2], $S$ is as high as 50257 while $d$ is only 1024.\n\n**Q3:** Your results in Theorems 2 and 3 show that the Euler and Tweedie $\\tau$-leaping samplers have the same asymptotic convergence rate as $\\tau$-leaping, but with a significantly lower per-step sampling complexity. Does it suggest that there are larger hidden constants in the convergence bounds for these samplers that may impact their practical performance?\n\n**A3:** In general, our results suggest $\\tau$-leaping has the same convergence rate (in terms of **number of iterations**) as the Euler and Tweedie $\\tau$-leaping samplers. Hence, with respect to the number of iterations, our results do not suggest large hidden constants in the convergence bounds. In particular, Lemma 7 establishes the asymptotic equivalency between Euler, Tweedie $\\tau$-leaping, and the truncated $\\tau$-leaping algorithms, where the last one is itself a rate-truncated version of the standard $\\tau$-leaping algorithm. Thus, the convergence rate of Euler and Tweedie $\\tau$-leaping samplers should be the same as vanilla $\\tau$-leaping, without any hidden constants.\n\nHowever, in practice, performance often corresponds more closely to the **total number of samples taken**—that is, the product of the number of samples per step and the total number of iterations. In this context, the Euler and Tweedie $\\tau$-leaping samplers offer advantages over the vanilla $\\tau$-leaping method due to their lower per-step sampling cost. In particular, new experimental result seems to suggest that these samplers differ in their constant-level performance, with the Euler method and Tweedie $\\tau$-leaping exhibiting **consistently smaller** constants than vanilla $\\tau$-leaping, likely due to their more efficient sampling in each iteration step.\n\n**Q4:** Can your analysis extend to the high-order samplers as in [5]?\n\n**A4:** The core idea of [5] is to better approximate the “middle” rate through a Runge-Kutta-like method designed for CTMC. With such a “middle” rate, [5] shows an accelerated convergence result (in terms of $\\epsilon$) for the $\\tau$-leaping algorithm. At a high level, it appears that our proof framework can be extended to [5] to investigate the “middle” rate for the truncated version of the vanilla $\\tau$-leaping reverse rate and obtain an accelerated convergence result for Euler and Tweedie $\\tau$-leaping samplers. However, this extension will involve the careful development of some detailed technical steps and would require a rigorous analysis.\n\nWe sincerely thank the reviewer again for the thoughtful comments. We hope that our responses have resolved your concerns. Certainly, we are more than happy to answer your further questions if any.\n\n[1] Lou, Aaron, et al. “Discrete diffusion modeling by estimating the ratios of the data distribution.”\n\n[2] Ou, Jingyang, et al. “Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data.”\n\n[3] Nisonoff, Hunter, et al. “Unlocking Guidance for Discrete State-Space Diffusion and Flow Models.”\n\n[4] Ren, Yinuo, et al. “How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework.”\n\n[5] Ren, Yinuo, et al. \"Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms.\""}, {"review_id": "0LRRnt8Hez", "reviewer": "Reviewer_ZqTY", "summary": "This paper presents a novel theoretical tool for convergence analysis of discrete diffusion models. \nThe approach is based on differential-inequality, which circumvents the need for the regularity assumptions required by Girsanov theorem.\n\nTheoretically, this new framework provides an improved convergence guarantee for $\\tau$-leaping sampler.\nThe linear dependence on the vocabulary size $S$ improves upon the previously\nresults $\\mathcal{O}(S^2)$ complexity.\nMoreover, the authors provides the convergence order for the Euler method and Tweedie $\\tau$-leaping samplers.\nThese two sampling schemes are shown to have the same convergence rate in terms of the number of steps, but with a lower per-step sampling complexity.", "questions": "Please see the Weaknesses section.", "limitations": "The main text lacks a discussion of the limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strength\n- The paper's contribution is clear: it provides an improved convergence bound for the $\\tau$-leaping sampler using a novel analytical technique.  Notably, this approach also weakens standard regularity assumptions in Girsanov theorem without introducing any new ones.\n- The paper is well-written and provides a dedicated section for its key notations (Section 2.4).\n\n\n### Weaknesses\nThe theoretical analysis is strong. One question for the authors is whether they considered numerical validation for the convergence rate with respect to vocabulary size $S$.", "was_revised": true, "final_justification": "After reviewing the authors' response to my question, I am now convinced of the manuscript's contribution and recommend its acceptance.", "rebuttal": "We sincerely thank the reviewer for providing valuable feedback and greatly appreciate your time and effort in reviewing our paper.\n\n**Q1:** One question for the authors is whether they considered numerical validation for the convergence rate with respect to vocabulary size $S$.\n\n**A1:** Thank you for raising this point! We have included two tables to provide empirical support for our theoretical results. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical prediction of linear dependence on $S$. Table 2 compares the performance of the Euler method and Tweedie $\\tau$-leaping against the standard $\\tau$-leaping algorithm, highlighting their superior efficiency and practical advantage. \n\n| Vocabulary Size ($S$) |Estimated KL Divergence |\n| - | - |\n| 3 | 5.93$\\times$$10^{-3}$ |\n| 4 | 1.32$\\times$$10^{-2}$ |\n| 5 | 2.10$\\times$$10^{-2}$ |\n| 6 | 3.38$\\times$$10^{-2}$ |\n| 7 | 3.77$\\times$$10^{-2}$ |\n\n\nTable 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.\n\n| Number of steps | 16 | 32 | 64 | 128 |\n| - | - | - | - | - |\n| Vanilla $\\tau$-leaping | 0.290 | 0.215 | 0.179 | 0.161 |\n| Euler method | 0.193 | 0.165 | 0.152 | 0.151 |\n| Tweedie $\\tau$-leaping | 0.176 | 0.158 | 0.155 | 0.153 |\n\nTable 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.\n\nWe sincerely thank the reviewer again for the thoughtful comments. We hope that our responses have resolved your concerns. Certainly, we are more than happy to answer your further questions if any."}, {"review_id": "ywfoB5NiwO", "reviewer": "Reviewer_EBtu", "summary": "Thanks to suthors for submitting to NeuRIPs 2025. Their work addresses theoretical aspects of discrete diffusion models and derives novels framework for convergence bounds. Paper addresses two challenges present in current convergence bounds for $\\tau$-leaping sampler and its variants: 1. hard-to-verify assumptions (l 53-59) and 2. Better scaling - in terms of vocabulary size as well as for $\\tau$-leaping variants with deterministic step size, i.e., Euler and Tweedie, used in practise.\nBy carefully treating the discrete nature of the problem, the Kolmogorov forward eq. is used and upper bounded by bounding the leading term to replace a need of It\\^o calculus and Girsanov change of measure technique. Insuch doing, for specific parameterisation (5) the main result (Theorem 2) proves the linearly scaling bound in vocabulary size for $\\tau$-leaping sampler and its variants, improving existing quadratic bounds for $\\tau$-leaping and introducing novel results for Euler  and Tweedie.", "questions": "Q1: Wider discussion or experiments concerning limitations/ablation study/asymptotics along the lines of Weakness W1 is suggested.\n\nQ2: See weakness W2.\n\nQ3: Could authors elaborate why $g_t$ is a Bregman divergence, whose non-negativity was used in proof (Appendix F)? Bregman div. is defined by $\\phi(y) - \\phi(x) - \\langle y-x, \\nabla\\phi(y)\\rangle$, where $\\phi$ is strictly convex function (here negative entropy), if I am not mistaken. Could authors rewrite presented relation to this form (or show it otherwise please?)", "limitations": "See W1", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Well motivated and timely topic. Introduction is well versed and provide context to problem addressed by the paper.\n\nThe paper is theoretical in nature and provides a rigorous treatment of the topic, referencing existing results and sources of inspiration (e.g., l 223) while emphasising the non-trivial novelties introduced by authors. So despite quite technical topic, the approach and assumptions needed are relatively straightforward to follow.\n\nContributions are both theoretical (novel theoretical results) as well as practical (new guarantess for popular algorithms) and thus paper is well suited for wider ML community.\n\nOn the improvemnt side:\nW1: Limitations: Presented limitations and wider discussion is very limited and perhaps too slim. For instance, the main results are derived for special CTMC rate matrix (5). To what extend is this limiting? If it is, it should be emphasized. Can it be extended? The same goes for Assumtions 1 and 2. One of the claims of the paper is it alleviates difficulties with hard-to-check assumptions. It would be worth discussing or ortherwise showing (experiments?) the new assumtions are easier to verify/meet.\n\nW2: Experiments/Ablation study. Despite its theoretical nature supporting experiment(s) could increase accessability and appeal fo the paper. For instance, Main result (Th 2) is an asymptotic result (in T) in its nature. Could authors show in the experiment (or otherwise) for what ranges of T asymptotic behaviour prevails? Is it data/task dependent?\n\nMinor:\n- numbering of equations is missing as of Section 3, included.\n- (l.140) define $\\mathbb{1}{y=x}$ and other symbiolics used", "was_revised": true, "final_justification": "Thanks to Authors for carefully addressing questions raised, especially Q1-Q2. I do not have any further comments and find paper to be novel and valuable for ML community and recommend it to be accepted (keep my current 'Accept' score).", "rebuttal": "We sincerely thank the reviewer for providing valuable feedback and greatly appreciate your time and effort in reviewing our paper.\n\n**Q1:** Presented limitations and wider discussion is very limited and perhaps too slim. For instance, the main results are derived for a special CTMC rate matrix (5). To what extent is this limiting? If it is, it should be emphasized. Can it be extended?\n\n**A1:** We thank the reviewer for pointing this out. We agree that our latter theoretical results (namely Theorems 2 and 3) are derived under the commonly used rate estimator in (5), which ensures analytical tractability and aligns with prior work (e.g., [1-3]). However, our analytical framework — particularly Theorem 1 — is **not limited to this specific reverse rate parameterization** and applies to any CTMC as long as the reverse rate matrix is well-defined. Meanwhile, although we assume a particular parameterization for the reverse rate in Theorems 2 and 3, they can be easily extended for general reverse rates with slightly modified Assumptions 1 and 2 (which are then made on the estimated rates instead of the scores). We will discuss our current limitation on the uniform rate matrix under time-homogeneity and potential extensions to other rate matrices and under non-homogeneous noise levels in the revision. We will further discuss another limitation on using Bergman divergence to characterize the estimation error. It might be interesting to investigate other forms of estimation error, such as in $L_1$ or $L_2$.\n\n**Q2:** The same goes for Assumptions 1 and 2. One of the claims of the paper is it alleviates difficulties with hard-to-check assumptions. It would be worth discussing or otherwise showing (experiments?) the new assumptions are easier to verify/meet.\n\n**A2:** We appreciate the reviewer’s thoughtful comment. Both Assumptions 1 and 2 are easy to check/enforce. Assumption 2 can be easily enforced through score-clipping. In particular, during training we can clip those scores that are too small or large with a constant $M$ [4]. Also, note that our convergence result only depends on $\\log M$. Assumption 1 requires bounding the score-entropy loss evaluated on the discretized grid, which is easy to check. In particular, we can take the average loss (up to some constant) on the selected grid. This is in contrast to those integrated loss functions [4, 5], where taking an integral is needed to evaluate the loss.\n\nJust to clarify as a side note, both Assumptions 1 and 2 also occur in prior works (e.g., [3-4]).\n\n**Q3:** Experiments/Ablation study. Despite its theoretical nature, supporting experiment(s) could increase accessibility and appeal for the paper. For instance, Main result (Th 2) is an asymptotic result (in T) in its nature. Could authors show in the experiment (or otherwise) for what ranges of T asymptotic behaviour prevails? Is it data/task dependent?\n\n**A3:** To clarify, the asymptotic results are in terms of the final error $\\epsilon$, which is affected, for example, by the number of steps chosen. We have included two tables to provide empirical support for our theoretical results. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical prediction of linear dependence on $S$, even for moderate number of steps (instead of asymptotically large ones). Please see our response to reviewer 1 for more details.\n\nTable 2 compares the performance of the Euler method and Tweedie $\\tau$-leaping against the standard $\\tau$-leaping algorithm, highlighting their superior efficiency and practical advantage.\n\n\n| Vocabulary Size ($S$) |Estimated KL Divergence |\n| - | - |\n| 3 | 5.93$\\times$$10^{-3}$ |\n| 4 | 1.32$\\times$$10^{-2}$ |\n| 5 | 2.10$\\times$$10^{-2}$ |\n| 6 | 3.38$\\times$$10^{-2}$ |\n| 7 | 3.77$\\times$$10^{-2}$ |\n\n\nTable 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.\n\n| Number of steps | 16 | 32 | 64 | 128 |\n| - | - | - | - | - |\n| Vanilla $\\tau$-leaping | 0.290 | 0.215 | 0.179 | 0.161 |\n| Euler method | 0.193 | 0.165 | 0.152 | 0.151 |\n| Tweedie $\\tau$-leaping | 0.176 | 0.158 | 0.155 | 0.153 |\n\nTable 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.\n\nIn general, asymptotic results usually have a vanishing constant, which depends on other system parameters such as the data dimension, yielding the tightness of these theoretical bounds data/task dependent. Yet, our experiment above shows that such asymptotic behavior might occur very early (i.e., when the number of steps are still moderate). Also, our main result in Theorem 3 further shows the advantage of Euler and Tweedie $\\tau$-leaping samplers, both of which are commonly used in practice.\n\n**Q4:** Minor and typos\n\n**A4:** We thank the reviewer for pointing these out. We will add the corresponding definitions and line numbers, and correct typos in the revised paper.\n\n**Q5:** Could authors elaborate why $g_t$ is a Bregman divergence, whose non-negativity was used in proof (Appendix F)? Bregman div. is defined by $\\phi(y)-\\phi(x)-<y-x,\\phi(y)>$, where $\\phi$ is a strictly convex function (here negative entropy), if I am not mistaken. Could authors rewrite the presented relation to this form (or show it otherwise please?)\n\n**A5:** Definitely. In our case, for each fixed $x_t$ and $y \\neq x_t$, let $$p_y := R_t(x_t,y), q_y := \\\\hat{R}_t(x_t,y).$$\n\nAlso, let $\\phi(p) := \\sum_{y \\neq x_t} p_y \\log p_y$ (i.e., the negative entropy function, which is convex), and the corresponding Bregman divergence is $D_\\phi (p, q) = \\phi(p) - \\phi(q) - \\langle y-x,\\phi(y) \\rangle = \\sum_{y \\neq x_t} p_y \\log p_y - q_y \\log q_y - (p_y - q_y) (1 + \\log q_y) = \\sum_{y \\neq x_t} p_y \\log(p_y / q_y) - p_y + q_y,$ which is exactly $g_t$. We will add this part in Appendix F for clarification.\n\nWe sincerely thank the reviewer again for the thoughtful comments. We hope that our responses have resolved your concerns.  Certainly, we are more than happy to answer your further questions if any.\n\n[1] Campbell, Andrew, et al. “A Continuous Time Framework for Discrete Denoising Models.”\n\n[2] Lou, Aaron, et al. “Discrete diffusion modeling by estimating the ratios of the data distribution.”\n\n[3] Ren, Yinuo, et al. “How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework.”\n\n[4] Zhang, Zikun, et al. “Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis.”\n\n[5] Chen, Hongrui and Ying, Lexing. “Convergence analysis of discrete diffusion model: Exact implementation through uniformization.”\n\n[6] Pham, Le-Tuyet-Nhi et al. “Discrete markov probabilistic models.”"}, {"review_id": "XKhUE2opwO", "reviewer": "Reviewer_Hz15", "summary": "This paper introduces a new analytical approach to analyze samplers for the backward process in discrete-state continuous-time diffusion models. With this new approach, the authors report convergence guarantees for the tau-leaping sampler in KL divergence that scale linearly with the state space size per dimension, in contrast to previous results that showed a quadratic dependence. \nAdditionally their method can be applied to the euler and tweedie tau leaping sampler, which are defined on a discrete sampling grid, \nproviding first convergence guarantees.", "questions": "Can these results point researchers in the right direction when choosing a sampler for their diffusion model?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This paper is an important theoretical contribution to the field of discrete diffusion models in continuous-time, providing valuable convergence guarantees that are valuable for the community.\n\nThe paper is well written, providing a good overview over the deterministic-step-size samplers used within the discrete diffusion models and the prior theoretical work on the convergence of the tau-leaping sampler.\n\nThe main strength of the paper is the proposed novel analysis based on the rate-of-change of the KL between posterior and sampling distribution as an alternative to the analysis based on the Girsanov change-of-measure framework. This brings two benefits: First, it allows application to samplers such as the Euler and tweedie tau-leaping for which the posterior rates are not defined on the whole continuous-time path. Second, the new method does not require regularity conditions.\n\nAnother strength of the paper are the convergence results, which either improve prior results or provide new guarantees.\n\nOne weakness of the paper is a missing discussion how this new results can be interpreted for practitioners, when choosing the sampler for their diffusion model.\n\nTypo\nLine 76 practivally", "was_revised": true, "final_justification": "I appreciate the author’s responses to my questions. Based on the clarifications provided, I will raise my score.", "rebuttal": "We sincerely thank the reviewer for providing the highly valuable feedback. We greatly appreciate your time and effort in reviewing our paper.\n\n\n**Q1:** One weakness of the paper is a missing discussion of how these new results can be interpreted for practitioners, when choosing the sampler for their diffusion model.\n\n**A1:** We thank the reviewer for pointing out this important issue. Yes — one key motivation for our work is to inform the design and selection of samplers for discrete diffusion models based on theoretical guarantees. Our results suggest that Euler and Tweedie $\\tau$-leaping samplers offer the same convergence rate in KL-divergence as vanilla $\\tau$-leaping (Theorem 3), while requiring **lower per-step sampling complexity** by a factor of $O(S)$, where $S$ is the vocabulary size. This makes the former two samplers more scalable for large-vocabulary tasks. Overall, our findings indicate that Euler or Tweedie $\\tau$-leaping may be preferable in practice — especially in settings where sampling efficiency is critical and the vocabulary size $S$ is large.\n\nWe also provided numerical experiments to validate our theoretical results and to support their practical implications discussed above. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical prediction of linear dependence on $S$. Table 2 compares the performance of the Euler method and Tweedie $\\tau$-leaping against the standard $\\tau$-leaping algorithm, highlighting their superior efficiency and practical advantage.\n\n\n\n| Vocabulary Size ($S$) |Estimated KL Divergence |\n| - | - |\n| 3 | 5.93$\\times$$10^{-3}$ |\n| 4 | 1.32$\\times$$10^{-2}$ |\n| 5 | 2.10$\\times$$10^{-2}$ |\n| 6 | 3.38$\\times$$10^{-2}$ |\n| 7 | 3.77$\\times$$10^{-2}$ |\n\n\nTable 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.\n\n| Number of steps | 16 | 32 | 64 | 128 |\n| - | - | - | - | - |\n| Vanilla $\\tau$-leaping | 0.290 | 0.215 | 0.179 | 0.161 |\n| Euler method | 0.193 | 0.165 | 0.152 | 0.151 |\n| Tweedie $\\tau$-leaping | 0.176 | 0.158 | 0.155 | 0.153 |\n\nTable 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.\n\n**Q2:** Typo Line 76 practically\n\n**A2:** Thank you for catching this typo! We will correct it in the revision.\n\n**Q3:** Can these results point researchers in the right direction when choosing a sampler for their diffusion model?\n\n**A3:** Please see our detailed response in A1. We believe our results suggest that Euler or Tweedie $\\tau$-leaping may be more favorable in practice, particularly in scenarios where sampling efficiency is crucial and the vocabulary size $S$ is large.\n\nWe sincerely thank the reviewer again for the thoughtful comments. We hope that our responses have resolved your concerns. Certainly, we are more than happy to answer any further questions you may have."}]

Author rebuttal:

Meta-review: This work studies the sample complexity of discrete diffusion models (for popular sampling algorithms such as $\tau$-leaping, Euler method, and Tweedie $\tau$-leaping algorithm) and improves the dependence of vocabulary size $S$ under weaker assumptions compared with previous works. To achieve the guarantee under the KL divergence, this work adopts the Kolmogorov equation instead of the Girsanov change-of-measure framework. Finally, they do a detailed analysis on the CTMC rate matrix to remove the dependence of $S$.

All reviewers keep a positive score for this work and view this work as a solid step in the analysis of discrete diffusion models. In the rebuttal phase, this work provide the additional simulation experiments to support the theoretical results to address the concerns of the reviewers, and the concerns of reviewers are addressed. Hence, we make a accept recommendation.
Decision: Accept (poster)