State Size Independent Statistical Error Bound for Discrete Diffusion Models
Authors: Shintaro Wakasugi
Taiji Suzuki
Venue: NeurIPS 2025 poster ()
Keywords: discrete diffusion models
score estimation
distribution estimation
approximation theory
Primary area: deep_learning

Abstract: Diffusion models operating in discrete state spaces have emerged as powerful approaches, demonstrating remarkable efficacy across diverse domains, including reasoning tasks and molecular design. Despite their promising applications, the theoretical foundations of these models remain substantially underdeveloped, with the existing literature predominantly focusing on continuous-state diffusion models.
A critical gap persists in the theoretical understanding of discrete diffusion modeling: the absence of a rigorous framework for quantifying estimation error with finite data. Consequently, the fundamental question of how precisely one can reconstruct the true underlying distribution from a limited training set remains unresolved. 
In this work, we analyze the estimation error induced by a score estimation of the discrete diffusion models. One of the main difficulties in the analysis stems from the fact that the cardinality of the state space can be exponentially large with respect to its dimension, which results in an intractable error bound by a naive approach. 
To overcome this difficulty, we make use of a property that the state space can be smoothly embedded in a continuous Euclidean space that enables us to derive a cardinality independent bound, which is more practical in real applications. 
In particular, we consider a setting where the state space is structured as a hypercube graph, and another where the induced graph Laplacian can be asymptotically well approximated by the ordinary Laplacian defined on the continuous space, and then derive state space size independent bounds.

State Size Independent Statistical Error Bound for Discrete Diffusion Models
Shintaro Wakasugi', Taiji Suzuki!
'The University of Tokyo, 'RIKEN AIP
vakasugi-shiinarro8822 ecc. u.t..uutooo u-tokyo. ac.jp, taijiemist.i faajimmist.i.uttok.... u-tokyo. jc.
Abstract
Diffusion models operating in discrete state spaces have emerged as powerful approaches, demonstrating remarkable efficacy across diverse domains, including reasoning tasks and molecular design. Despite their promising applications, the the- oretical foundations of these models remain substantially underdeveloped, with the existing literature predominantly focusing on continuous-state diffusion models. A critical gap persists in the theoretical understanding of discrete diffusion modeling: the absence rigorous framework for quantifying estimation error with finite data. Consequently, the fundamental question of how precisely one can reconstruct the true underlying distribution from limited training set remains unresolved. In this work, we analyze the estimation error induced by a score estimation of the discrete diffusion models. One of the main difficulties in the analysis stems from the fact that the cardinality the state space can be exponentially large with respect to its dimension, which results in an intractable eπтоr bound by naive approach. To overcome this difficulty, we make use of a property that the state space can be smoothly embedded in continuous Euclidean space that enables us to derive a cardinality independent bound, which more practical in real applications. particular, we consider setting where the state space is structured as a hypercube graph, and another where the induced graph Laplacian can be asymptotically well approximated by the ordinary Laplacian defined on the continuous space, and then derive state space size independent bounds.
Introduction
Diffusion modeling has demonstrated state-of-the-ane performance in learning problems such as creating images (Song et al., [22T Dhariwal and Nichol, 202T), videos (Ho et al.) 2002), and audios (Chen et al. 2020 Kong et al. 2020). drawing significant attention to their applications.
Theoretical studies diffusion modeling in continuous state spaces have been conducted within the framework of score-based generative modeling iSohl-Dickstein et al., 2015 Song and Ermon 2019 Song et al. 2021 Ho et al. 20200 Vahdat al. 2021). One of the most important characterizations of dillusion model lin is the Tormulation using stochastic differential equations (SDEs) proposed by
Song et al. (2021)
With the advent of SDE formulation, significant efforts have been made to analyze the estimation error between the true distribution and the generated distribution. [ee et al. (2022b) showed that the total variation distance between the two distributions can be bounded by the polynomial order of the score estimation error and the step size with the time discretization of the reverse process. Lee et al.] (2022b) assumed the smoothness of the score function and the validity of the log-Sobolev inequality (LSI) for the true distribution, while et al. (2023)) and et al. (2022a) derived error bounds without the LSI condition, Chen et al. (2023a) further relaxed the smoothness assumption. Moreover, Song et al. (2021) Pidstrigach 2022 evaluated error rates under the manifold hypothesis,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

which assumes that the true distribution is concentrated on low-dimensional manifold. De Bortoli et al. (202T) and De Bortoli (2022) derived error bounds under the assumptions of score estimation error bounds at each time step and each point, considering dissipative structures and the manifold hypothesis, respectively.
While the above studies assumed the accuracy for score approximation, Oko et al. (003) developed a theoretical framework that derives the approximation error of the score function when the true density belongs to a Besov space. Their work combined function approximation theory from deep learning with the approximation theory of diffusion modeling and employed concentration inequalities to establish score estimation error bounds. Building upon this seminal work, several refined theoretical analyses have been proposed, including relaxation of the lower bound condition for the density (Zhang et al.] (2024), analyses under the manifold assumption on the support of the data distribution (Azangulov et al. 2024), statistical guarantees for reflected diffusion models (Holk et al. 2024). and minimax optimality of the probability flow ODE (Cai and Li 2025
Recently, diffusion modeling for discrete states has also gained attention (Hoogeboom al. 202 1 2023
Austin et al. [202]] Richemond et al. [022)] Meng et al. 2022 Sun et al. 2023 Santos et al.
Lou et al. 2024). Notable advancements have been made in learning problems with discrete structures,
such as natural language processing (Austin et al. 202 He et al. 2023 Wu et al. (2023) molecular
design (Zhang et al.
2023 Gruver al. 2023 Campbell
al., 2024] Lee et al. (022), graph 2020 Shi et al. 2020; Vignac et al. (222)) , and segmentation (Zbinden et al.
generation (Niu et al.
2023). In addition, areas where continuous diffusion modeling performs well, such as image (Hu et al. 2022 Zhu et al. 2023) and audio generation (Yang et al.) 2023), discrete diffusion models have been shown to efficiently infer multimodal generation problems conditioned on discrete structures
like text.
As for the theoretical analysis of discrete diffusion modeling, Campbell et al. (2022) analyzed total variation distance based on Markov chains, and Chen and Ying (2024) reduced the error under the condition that the discrete state space is restricted the vertices of hypercube. |enn et al. (2025)
proposed a more general approximation theory for discrete diffusion characterized by Poisson random measure with evolving intensity, allowing discrete diffusion modeling be formulated as stochastic integrals similar to the theory of continuous diffusion modeling.
However, the theoretical analysis of score estimation error in discrete diffusion modeling remains unexplored. In this study, we derive score estimation error bounds for discrete diffusion models by applying the function approximation theory of neural networks and concentration inequalities, which were previously used in the score estimation theory of continuous diffusion modeling (Oko et al., 2023
Our main contributions are summarized as follows:
First, we develop a theoretical framework for bounding the score estimation error in discrete diffusion models. Unlike continuous diffusion models that rely on L loss in score matching, our analysis handles the Bregman divergence loss that naturally arises in discrete diffusion, and we rigorously control the estimation error using the Hellinger distance.
Second, introduce novel approach to achieve state-size independent error bounds by embedding the discrete space X into Ed and approximating the eigenvectors of the graph Laplacian by functions in an anisotropic Besov space. This enables the use of advanced function approximation results for deep ReLU networks. Under mild regularity assumptions, we show that the error bound depends only polylogarithmically on the number of discrete states M, which nearly achieves the optimal rate conjectured in Ren et al. (2025).
Third, demonstrate that this framework can be instantiated in concrete settings such the hypercube [o, 1j2 and graph-based diffusion processes on smooth manifolds. In both examples, we show that the eigenvectors of the transition matrix admit efficient approximations.
2 Preliminary
Here, we introduce discrete diffusion models and prepare some technical matters for our theoretical analysis. Before introducing the discrete diffusion models, we briefly review the continuous state diffusion models. The continuous diffusion models consist of two stochastic processes, the forward process and the reverse process, so that the model can generate data whose distribution sufficiently close to the true distribution po on Rdd The forward process (X, h20 on B is formulated as the
2

---

following Ornttein-Ullenbeck (OU) process:
Xo Po. dX, = -x,dt + v2dB,,
where [22 represents a d-dimensional standard Brownian motion. Under certain assumptions on the initial distribution Po (Haussmann and Pardoux 1986 Cattiaux et al. 2023). the distribution of X,, denoted by Pt, converges exponentially to the standard normal distribution as - cc. The reverse process (YioSIsT (I' 2 0) defined by the following stochastic process trace-backs the forward process:
Yo PT: dY, (V 2V loggrr((()))d + VdBB
That is, the distribution of Yr- coincides with pt for S T, and thus we can generate samples from the target distribution pu by sampling Y7 via the reverse process. However, do not know the initial distribution of the reverse process pr and the score function V log Pt because both of them are dependent on the unknown true distribution po. Here, the initial distribution pr can be replaced by the standard normal distribution for sufficiently large T since converges to the standard normal exponentially fast, and the score function V log (Y,) can be estimated by least squares score matching using finite-size training data. These approximations, along with the time discretization of the process, induce errors in the resulting distribution generated by the model. Chen al. (2023a) obtained an upper bound on this error in terms of Kullback-eeibler divergence (KL-divergence). Their result implies that the main part of the error is the estimation error of the score function V log Pt- Based on this observation, Oko et al. (023) derived the following bound on the score estimation error.
Proposition 1 (Oko et al. (2023), informal). Under some smoothness assumptions Po- score matching estimator St obtained on a deep neural network model with an appropriate network size, can achieve
Exo,
[ BT (o ((( at) S inn=a
(.ー log n.
Here, s represents the smoothness parameter of the Besov space which po belongs, and i sufficiently small end-point time.
This theorem implies that diffusion models with an appropriately designed score-function estimator can achieve the minimax optimal rate n गीड to estimate the target distribution with smoothness s. In this work, establish analogue of this result for discrete diffusion models.
2.1 Discrete diffusion modeling
Discrete diffusion modeling is defined over finite set X instead of Rd.. Let M = [ and consider estimating the probability mass vector Po E A where A = {p P(Ex = 1, p E R%)0 We assume that each æ E X has vector representation ((x) E R.D. We identify this vector representation with x and use the same notation x for both meanings. A typical situation X
{0. 1) where ((x) (II....,II)) E IR RR,, and another example is one- one-hot- vot-v representation X = far (0, 1)M -=
Forward process: In the forward process of discrete diffusion modeling, the distribution {pe at each time step follows the master equation of the following Markov process:
dp
QiPes
(2)
dt
where Q E MRM is the transition rate matrix satisfying ()=,,)==--)) Q((y,)) (Va E X)
and (z, > 0 (Vz + y X). If π denotes the stationary distribution of the Markov process (2)
the following equation analogous to the continuous diffusion model holds (Bobkov and Tetali 2006):
KT(p:ll=) < cxp(-p((Q)))TT.xxlll))
Here, p(Q) is the modified log- Sobole constant Bobkov and Tetali 2006) defined as
p(Q)= = inf
(f Ent.
x - R, Ent, (1) > 03.
where Ent,, (f) = EE,, If log fl - E, [f] log Ex [f] and E,, (f.g) Ex gl.
3

---

Reverse process: The reverse process {9 UEKK = (pr-closest can be formulated by using another transition rate matrix Q, as follows (Kelly 2011
dg:
Qr (0SLST),
= pr. df
pi(z) Qz v) and xz) = - 2v) Then, it is known that Qe Pr-r (0 S S 1). Although this reverse process only gives the ODE of the probability mass function gt. its particle implementation can be given by the T-leaping algorithm (Campbell et al., 2022 Ren et al. 2025). This algorithm expresses the reverse process stochastic integral and applies the Suuler-Maryaee scheme, similar to the continuous case. The transformation into a stochastic integral performed using Poisson random measure with evolving intensity (Protter (983). For simplicity, we consider the case where Q₁ is time-homogeneous (Q: Q holds for all 2 0).
where 2v(,,)) = p((2)
Proposition Ren et al. (2025). The reverse process 4 can be expressed as the following stochastic integral defined by Poisson process [ui with respect to intensity function (see Definition 2
Appendix B for its definition):
V/ Yu (y (onu-yn)NNllle dy), mcly) = 90)
where Xt- denotes the left limit of Xx and Q denotes the matrix Q with the diagonal elements set to 0.
Score estimation: However, to implement the r-leaping algorithm, we need to know the score function (t v) == p=fv), We approximate it using score network x² R I ((r, y, f) + se sx(x,,)) y)) in deep neural network model F. The score network 8 can be estimated via score matching analogous to the continuous state diffusion models, but we need to account for the non-negativity constraint of the score function. For that purpose, the denoising score entropy is employed instead of L loss (ouu et al. 2024):
p=(=)'
8 E arg min sEFF
Exepp
Σ ypk
BR (s((2, (((x,))(z,, dt
arg min xEF
Exaruo
Exwpi (1120)
E
Σ
BR (s mx)) if (z. y ao)
dt.
Here (x, y [00)
p=(u) Pe zo)
and BR denotes the Bregman divergence defined by
(s f(s)) f(s) (s(sss**
for a strictly convex function f, where we employ particular choice K(x) := log for the convex function f. In training the neural network, analogous to continuous diffusion models, we approximate the expectation over 2o Po by empirical distribution defined by the training data iid.
Dr = {= (x; ~ po) with size n, and we seek & E F that minimizes this empirical loss. We define the loss function f as
Σ BR (R (1ls za)) si (Ft. xo) w) dr. Moki
l, (x0)) = Exrop(iko))
Then, the empirical loss L(s) can be written as Σ(s) = 4 (x;)). As we have stated above, we find the empirical risk minimizer @ in the set of deep neural networks that is defined as
(L, W) ((A(4)))) ((()) +(())
(2) + b(1)
1 E RR 100 E RW (1 lo + I1)) & S, max, | V |1 S B},
where L. represents the depth, = (Wi)f represents the width with W = 1, B represents the sparsity, and B is bound on the norm of parameters. Here, the activation function 17(-) ) given by m(x)= Re)U(x) = max(æ, 0). The function class to which the score network belongs is defined

---

Algorithm Implementation of discrete diffusion modeling by r-leaping
Input: Do π, time discretization [to]kelo.K] (to 0, k - 6), intensity function pr.
score networks;
2: Output: sample from Dtk ~ Qr-6
3: for π = 0 K 1 do
4:
It--1 Eye (,,)) (( (v)(ta+1 tn));
5:
end for
as E&E L W.S,W, st (1/R, (Vt, x. x. with hyper-parameter R 2 (see Assumption 310
We denote the expectation of measurable function with respect vn -o Pf. and its empirical distribution as Pn/, i.e., Pʃ == Brooro [f] and P.ʃ = J Ei= f(x)). Accordingly, the expected
loss [(s) and empirical loss [(s) can be expressed
(()) = ( P((.),
(x(s)) = Pr(lo),
Then, the empirical risk minimizer on the deep neural network model F is given by
$ arg min Pr SEF
Once we have obtained an estimator 8, we can define the corresponding intensity function 7h with time discretization (tx (t with 0 and f T
(u)(() êт [4] ( v) -
where [4] = lx for / E [4:, (14). Moreover, due to Eq. 33) the initial distribution of the reverse process qo can be replaced by (1= pr). Then, the r-leaping algorithm with our estimate can be implemented as in Algorithm]]
2.2 Technical assumptions and theoretical tools for the error analysis
To derive the discrepancy between the generated distribution and the true target distribution for the estimated discrete diffusion model implemented by 7-leaping algorithm (Alg. [.. we prepare some technical tools.
The transition rate matrix Q symmetric, and there exist positive constants C, D, and such that Q y) < C, D < (x x) < D.
Assumption 1.
Assumption 2. There exists lower bound p > 0 for the modified log- Sogg-oo constant p(Q).
Assumption There exists R 2 such that the true score function and our model satisfy 8i (zz y) [1/R, R] and & (z. 3) E [1/R, R).
Assumption 4. There exists E [0, such that for any y X. satisfying Q > 0, the 1(
following holds: px(2.0((=--))
1V
Assumption iis natural condition for discrete diffusion models which ensures the regularity of the rate matrix (Ren et al., 2025). Assumption 2 guarantees the exponential convergence of the forward process in discrete diffusion models, serving role analogous to functional inequalities in the continuous case (Bakry et al. 2014). Assumption Sattiiioniimmeee Bimposes boundedness on the score function, which mirrors common assumptions made in continuous-state diffusion processes (Chen et al. 2023a). Assumption corresponds to the Lipschitz continuity of the score function continuous diffusion models (Chen et al. 2023b a). ensuring sufficient regularity for the analysis. Under these assumptions, the following result holds.
'The function value restriction can be practically implemented as 4' max(min R). R where min and max be realized by ReLU activation.
5

---

Proposition 3 (Ren et al. (2025) )
In the r-leaping algorithm, suppose the time discretization + f some t and assume that
(el satisfies 1x+1 ts S x2
K-1 (tn+1 -x)
E y
BR (ST ta (I1z y (o (80--- - (0)
Esc:
k=
for the score network 5c v). Here, suppose that y 17 T for y < 1, and 17 1 for
7 = 1, and it holds that
(
log (log(= log [x1) k. =0
0
(7< < 1), (7= 1).
T=
Esc
8
(
TD
log Cuo log
[x]
Then, under Assumption 7 1o the following error bound holds
KL(psllēr-al S (xp(-pT)log M
D'RT
Esc
(6xi)
Similar to continuous diffusion modeling. the upper bound on the error consists of three terms. (i) corresponds to the егтоr from the convergence rate of the forward process, as shown in Eq. (3). (ii)
arises from time discretization. (iii) represents the estimation error of the score network. Although the Girsanov's theorem cannot be applied to discrete diffusion models, another similar proposition can be derived from the characterization of Poisson random measure with evolving intensity (Ren et al. (025), which allows for the evaluation of the estimation error. However, unlike continuous diffusion models, the sample size or neural network parameter size required to satisfy the estimation error assumption has not been examined. Hence, the aim of this paper is to show upper bound of Esc analogous to Eq.
Naive estimation error bound of discrete diffusion models
Here, we derive an estimation error bound of the score estimation network in rather naive way. In our analysis, the key step is to derive an upper bound on the Hellinger distance between the empirical risk minimizer á and the true score function s", defined by
1/2
(Be, 81) = (Ereppi
Engtar (Vi((E)))) - ( vi) Q(22.
First, we give bound on this Hellinger distance under naive setting.
Theorem 1. Under Assumption 7 to and the same parameter settings Proposition 3 if the network size is set I, = Ollog (mM)). W ((M), S = Ö(M), B Ó(M) and T (log(M V n)), then with probability at least - 2e for 2 1, holds that
(2,, s = o ( Mt [
log (M (m).
The formal proof of Theorem D provided in Appendix C. By Proposition and Theorem 1 obtain the following result showing an estimation error bound for the estimated distribution.
Theorem 2. Suppose that the same condition as that of Theorem holds. Then, the following estimation error bound holds with probubility 1 -2 ''forr 1:
MI 1ogo(M) V n).
(T(psllrr-s)
One of the biggest difficulties in deriving this bound is the requirement to carefully treat the Bregman divergence in contrast to the continuous diffusion models where we could directly deal with the Ln-norm. The difficulty can be overcome by noticing that the Bregman divergence can be lower bounded by the Hellinger distance. By combining this notion with the so-called peeling device
'it was later pointed out that the r-leaping update can become ill-defined for non non-ordinal data when multiple- jumps appear in a single windew.d which we were not aware of at the time of writing. Our theoretical results do not rely on this aspect and therefore remain valid.

---

van de Geer (2000,, we achieve (1/nn) rate of convergence with respect to the sample size n. which significantly improves upon the standard Rademacher complexity bound that only provides an 0(1/ vn) bound. An additional technical contribution is to show how ReLU neural networks can effectively approximate the score function 8t-
This bound holds under minimal assumptions. On the other hand, if the state space is product space such as X = {0, _ (which often happens in real applications), then M can be exponentially large with respect to the dimension D. To overcome this difficulty, we consider a situation where the discrete state space X can be embedded into a Euclidean space IR and the eigenvectors corresponding to the Markov transition operator Q can be well approximated by smooth function on R By doing so, we obtain a significantly improved bound seen in the next section.
4 State size independent error analysis with continuous space embedding
As we mentioned above, we aim to improve the estimation error by explicitly considering an embedding from the discrete space into a Euclidean space TRD Through the embedding, we may approximate the eigenvectors of Q by functions defined on RDD enabling the application of function approximation theory for smooth functions defined on Euclidean spaces. Especially, the anisotropic Besov space is useful function class that covers wide range of functions with smoothness.
Anisotropic Besov space. Here, we begin by defining anisotropic Besov spaces. Let = [0, 1]s. For function f: : . + R. we define its ---norm as
Il = [ = ( (0< p < oo), Ssupzen [f()) (p=0))
For B R. let |8| = Σ 18yl. The r-th order finite difference in the direction h E R is
defined as: (z) =
(f)( + - - (f)(() and ())))(x) = f(x), for x + rh E Q
otherwise, define (f()(() =
Definition 1 (Anisotropic Besov Space). Let p.q S xo, (Br..... .B) E R R r =
max; + 1. Then the Besov semi-norm is defined as
If IflBg.. = 22 (ʃ, k/3 ..... 100/:/__....2//8__]]]1 {/2))]]) 1/2 supE2o 2t o (f, (2 k/8, .................... 2-..,,-k//84))
(q < 00);
(q (q=
where Wrp is the r-th order modulus of smoothness defined by wra (f,t) = SuPhERt/nelSt:
|| The anisotropic Besov space ( is defined as B (9) = If (P())) [If Bg. = IIfllp + Ifl < co). The unit ball of the anisotropic Besov space is denoted by U( p.g)
(E)= 1/3,)-1, plays an The harmonic mean of the components of B, which is given by 3 3= important role in evaluating the approximation error by ReLU deep neural networks. known that the Hölder class and the Sobolev class with = 2 are special cases of anisotropic Besov spaces Triebel [1983 2011). In the following, we consider a situation where the eigenvectors of Q can be well approximated by a function in a Besov space on the continuous space.
4.1 Assumpitons
We now summarize the additional assumptions required for the analysis.
Assumption 5. Let 0 < 5 1. Suppose the orthonormal eigenvectors U = (u1...., uM) of the graph Laplacian L Q satisfy u, uz(x) ((1/MM)) for all x E X and the initial distribution po can be expanded as:
po(x)= = E (z)((a) (Va E X).
Assume that for each j= 1,..,, M, there exists a function VMu; X - [0, 1] satisfying (2z u,(x)) S e/ VM and representable (z)(x) = (Px)), where hy E 91 (BB))) with 7 0 and
P E gdxD are projection matrices for all j. Moreover, assume P| O(1) and 3 1/p.
7

---

and the Assumption 6. For each = -l...., Besov norms of b satisfy 7731 2 5" where and y
.......MMM....... M, the expansion coefficient satisfies cyyl E |cil j=
Assumption 5 is technical condition that enables the application of function approximation theories in the anisotropic Besov space (Suzuki and Nitandal 202T) (see also (Suzuki (2019)). The factor (11 M)) in u. stems from the normalization of orthonormal eigenvectors, i.e., Erex Ml (2)(2)) Assumption 6 imposes a polynomial decay condition on Cj. which is a standard regularity assumption in nonparametric statistics, particularly in the analysis of kernel methods (Caponnetto and De Vito 2007; Ying and Pontil, 2008) Dieuleveut and Bach, (016). The condition on "/ reflects the increasing complexity of the basis functions hy. Similar assumptions are common in the analysis of eigenfunctions of the Laplacian operator in continuous settings.
4.2 State space size independent error bound
Theorem 3. Assume that A and as well as Assumption 7 to hold, and if the network size is set as L = (log (M)), W = (M)) S = Ô(M). B = ((M) and T Ollg(( VMMMV vn)).
the following estimation error bound holds with probability 2e :
(1+28)(
28
11+3
n
(1+28)0--1)+
28G
2
+
log 00g (MV))) (s-721),
(01
201
2
M
1428
1+28
M
e Aa
log (M (M vn)
(s<1).
S (2, oj)dl
2n(a-1)
o
A₂
(1+21)
()-1)))))
a 1112
131 (1 to 2)1
+
12
(11-6-1
0(1
(1 (1-25X Dia (x lox (arva)
(otherwise).
2nll
The proof of Theorem 3 is given in Appendix D The estimation error bound in Theorem shows that for 2 1, the dependence on M is only polylogarithmic, successfully removing any polynomial dependence on M. This aligns with the optimal rate conjectured in Ren al.] (2025) for discrete diffusion models. Even when 7 + 1/2 < 8 < 1, the exponent on M remains below 1, yielding an
improved convergence rate over Theorem 1
As for the dependence on the sample size n, the bound does not explicitly depend on the embedded di- mension d, which is desirable. Moreover, when < 1, the rate recovers the optimal rate (28 (22)) derived by (Suzuii and Nitanda (202T), but can be dependent on M polynomially. This is because estimation errors for (aM)s functions affect the final results when the decrease of coefficients is slow. On the other hand, when s is large, we may "cut-off" redundant basis functions so that we mitigate the dependency M to poly-log order while the rate with respect becomes bit slower instead.
Finally, combining Proposition 3 and theorem 3 yields an upper bound on the distribution estimation error. Here, we let the right hand side of the bound in Theorem 3 be denoted by E,,t-
Theorem 4. Suppose that the same condition that of Theorem 3 holds. Then, the following error bound holds with probability -t:
S E
Example 1: Hypercube f0, P. As an example, we consider the hypercube setting = (0, P similar to Chen and Ying (2024) This setting is natural in practice, the general discrete space S which is commonly assumed in many works such as Campbell et al. (2022); Lou et al.
2024 Zhang et al. 2025) can be encoded as a hypercube structure {0, 1] D [S] We let the eigenvalues of L Q2 be ordered as 0 0= A A2 S < AaM-
Assumption 7. Let the discrete state space be X = P0 For any pair of distinct states x + y. assume the rate matrix Q(z, y) satisfies:
(d(x, y) = =1); (otherwise), where d(x, y) denotes the Hamming distance between and y.
Q(x,v)=
8

---

Under Assumption since the diagonal term satisfies -Q(xz = D, we obtain D = O()). Moreover, the following spectral property holds.
Lemma 4. Under Assumption 7 for every w E X, hao( cos(TT" ( VM is eigenvector corresponding to the eigenvalue 2 2/w], where [w] is the number of ones in w. In particular, X2 = 2, which is independent of the dimension D.
Based on this lemma, we can derive the convergence of the discrete diffusion model as follows.
Corollary 1. Under the assumptions of Proposition 3 and Assumption 5 5
7 for arbitrary 69 >
the following error bound holds with probability
2e-
[n (2(s-1) 10)-1))))-0//-- 60)/ + t/n) log vn)
(s 1), (s < 1).
(L(psller-s) 5) -
Mit1 log (M VM))) n)
The proof can be found in Appendix We observe that when 2 1, the convergence rate is essentially ((=-226-1)/((--1)) which is independent of the state space size M. This rate could be achieved by showing that the eigenvectors in this setting can be represented by cosine functions on the continuous space, and that such trigonometric functions can be efficiently approximated by deep neural networks. On the other hand, when & < 1, the convergence rate is (MM/n), matching the error bound of the naive estimator in Theorem [ In this case, accurately approximating the score function requires aggregating contributions across the entire state space, which leads to higher estimation complexity.
Discrete graph diffusion process. Finally, we consider a diffusion process defined on graph. In this setting, each point of X is randomly generated on a d-dimensional, smooth, closed and connected Riemannian manifold M C TR. isometrically embedded in Rd through e: . - R.D. where each point x obeys the uniform distribution p on M independently. On this point cloud X, we can define the transition rate matrix as the ordinary graph Laplacian: First, let the affinity matrix be W(x; v) = ko (x..)
Example 2:
po (x) where ( v) exp (- (-1--11) |-=="
and pa (xx== hio v), second, 20
using a diagonal matrix D E =x* defined as D(I,z)= ΣyEx W(x, 3). let the normalized weight matrix as A = D- and finally we define the normalized Graph Laplacian as the transition matrix Q 2 7). The stochastic process corresponding to Q is known as diffusion process on the graph with the normalized weight matrix A. In this setting, the graph Laplacian Q can be considered as discrete approximation of the Baolace-BBlttami operator A defined on MM, and thus the eigenfunctions and cigenvalues of the Laplace-Beltrami operator provide a good approximation of those of Q (i.e., bounding in Assumption 5) (Dunson al. 2021), Since the eigenfunctions of AM are included in the Sobolev space W (M) with arbitrary B3 we can apply our theorem to derive the following bound. The proof is given in Appendix F
Corollary 2. Suppose that the same assumptions as Theorem 3 and Assumption 5 and 6 hold,
mase 1-10/4.8/2 1/244//5/54
and >> 1. Then, if M is sufficiently large that M I(n
(d/21210 1911
and
[og(M)) sat13 then there exists event with high probubility on the realization of X such that, for arbitrary B such that 8- 23/d id= > 1, the following error bound holds with probability 1 - -e=
(L(psllur-s) S n 17
+
Angg (ng(M)
t
log (M V n2).
A3
Therefore, distribution point cloud X on smooth manifold M can be well approximated by the discrete diffusion models that utilize the graph diffusion process induced by the graph Laplacian as the forward process.
5 Numerical experiment
To complement our theoretical analysis, conducted score-matching experiment that exactly instantiates Example 1 on the hypercube {0, 1)2h with M = 2D. For each D = 6,8, 10 we constructed two distributions using the Hadamard basis H E {+ (1MM-//3MXM,
((x) = (He)a, p(x) = cl(a)
y= c((r))

---

Prediction Error (DSE)
0.00440
0.00300
DSE
0.00200
0.00010
0.00000
0,00000
6-low
6-high
B-oow
8-high
10-low
10-high
Figure 1: Score matching results hypercube toy examples. Each bar shows the mean denoising score entropy (DSE) over 10 trials; error bars are 1 standard deviation ( 0.4-0.7 x 10-1).
The coefficient vector c E IRM was chosen in two regimes:
Low-frequency: 00,--.; Ca (0, 1), Ck for 5.
High-frequency: Gg ~ (0, 1) for all & 2 2 (DC and first harmonic set to zero). Activating only the first few modes yields smooth distribution, whereas using the whole spectrum (minus the DC term) creates a highly oscillatory one. Each distribution was evolved for / = under the rate matrix Q shown in Assumption 7 We then train one-hidden-layer score network sø (ır, y) (input 2D, 256 ReLU units, Softplus output) using the denoising score entropy (DSE) loss. Training used 5000 random Hamming- I pairs, ADAM (lr = 10 10) and 20 epochs. Performance was evaluated as the mean DSE over all Hamming- pairs. Each setting was repeated 10 times.
The mild increase from D predicted by Theorem and corollary 1 while the higher errors for high-frequency mixtures reflect the bounds' sensitivity the smoothness parameter. These observations provide concrete evidence that the theoretical guarantees translate directly to practice without any hyper-parameter tuning or architectural changes.
D 10 matches the logarithmic dependence M 2
6 Conclusion
In this study, we established the first theoretical framework for estimating score functions in discrete diffusion models. We proved that directly approximating the score function for each discrete state using neural network yields an estimation error rate Ö(M/n) under naive analysis and further improved this bound to Ö(n ()/(= 1+255-8)) independent of the state space size M by assuming a polynomial decay condition on the spectral decomposition of target distribution. Our analysis made use of decomposition of the target distribution by eigenvectors of the transition matrix Q. Then, we utilized the fact that the eigenfunctions can be well approximated by smooth functions (i.e., Besov spaces) also demonstrated concrete bounds for the hypercube settings and the graph diffusion processes.
embedded continuous space in order to reduce the model complexity. We
One of the main drawbacks of our analysis is that we assumed a mild condition on the score function of such that is bounded above by and below by 1/R. This condition inherits the same condition assumed in the continuous space (Oko et al. (223).. Relaxing this condition to the case where there is no uniform lower bound on the density as performed in Zhhng et al.) (2024) is important direction for future work.
Acknowledgment
SW was partially supported by JST CREST (IPMJCR2115), TS was partially supported by JSPS KAKENHI (24K02905) and JST CREST (JPMICR2015), This research is supported by the National Research Foundation, Singapore, Infocomm Media Development Authority under its Trust Tech Funding Initiative, and the Ministry of Digital Development and Information under the AI Visiting Professorship Programme (award number AIVP-2024-004), Any opinions, findings and conclusions recommendations expressed in this material those of the author(s) and do not reflect the views
10

---

of National Research Foundation, Singapore, Infocomm Media Development Authority, and the Ministry of Digital Development and Information.
The authors are grateful to Satoshi Hayakawa for insightful comments, particularly for drawing our attention to the potential ill-definedness of the 7-leaping scheme in the SDE form.
References
Austin, D. Johnson, J. Ho, D. Tarlow, and R. van den Berg. Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems, volume 34, pages 17981-17993 2021.
I. Azangulov, G. Deligiannidis, and Rousseau, Convergence of diffusion models under the manifold hypothesis in high-dimensions. arXiv:2409.18804 2024.
D. Bakry, I. Gentil, and M. Ledoux. Analysis and Geometry of Markov Diffussio Operators. Springer, 2014.
Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. The Annals of Statistics, 33: 13:1157-1 2005.
S. Bobkov and P. Tetali. Modified logarithmic Sobolev inequalities in discrete settings. Journal of Theoretical Probubility, 19:289-336, 2006.
O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical process. Comptes Rendus de l'Académie des Sciences Paris, Series 1 Mathematics, 334:495-500, 2002.
C. Cai and G. Li. Minimax optimality of the probability flow ODE for diffusion models. Sttl:25033.0583,, 2025.
A. Campbell, Benton, Bortoli, T. Rainforth, Deligiannidis, and Doucet. continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems, volume 35, pages 28266-28279, Curran Associates, Inc., 2022.
A. Campbell, Yim, R. Barzilay, T. Rainforth, and T. Jaakkola. Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 5453-5512. PMLR, 2024.
A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
Cattiaux, G. Conforti, Gentil, and C. Léonard. Time reversal of diffusion processes under finite entropy condition. Annales de I' l'Institut Henri Poincaré, Probabilités et Statistiques, 59(4): 1881, 2023.
H. Chen and I.. Ying. Convergence analysis of discrete diffusion model: Exact implementation through uniformization. arXiv:2402.08095. 2024.
H. Chen, Lee, and J. Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference Machine Learning, pages 4735-4763. PMLR, 2023a.
N. Chen, Y. Zhang, H. Zen, J. J. Weiss, M. Norouzi, and W. Chan. Wavegrad: Estimating gradients for waveform generation. In International Conference on Learning Representations, 2020.
S. Chen, Chewi, Li, Y. Li, A. Salim, and A. 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, 2023b.
V. De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Trans- actions on Machine Learning Research, 2022. ISSN 2835-8856. URL. https:::tt// pesttss:/oopereviiie het//forum/id--/MBaao.oo

---

V. De Bortoli, J. Thornton, J. Heng, and A. Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34: 17695-17709, 2021.
Dhariwal and A. Nichol. Diffusion models beat gans image synthesis. Advances in Neural Information Processing Systems, 34:8780-8994, 2021.
A. Dieuleveut and F. Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4): 1363-19999 2016.
D. B. Dunson, H.-T. Wu, and N. Wu. Spectral convergence of graph Laplacian and heat kernel reconstruction in L from random samples. Applied and Computational Harmonic Analysis, 55: 2021.
N. Gruver, S. D. Stanton, N. C. Frey, G. Rudner, I. Hotzel, J. Lafrance-Vanasse, Vanasse, A. Rajpal, K. Cho, and A. G. Wilson. Protein design with guided discrete diffusion. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL htttp:://opeetiie httpps///oenrrevie net/ CorumPid-Mf1669Ges
A. Hassannezhad, G. Kokarev, and I. Polterovich. Eigenvalue inequalities on riemannian manifolds with a lower ricci curvature bound. Journal of Spectral Theory, 6(4):807-835, 2016.
U. G. Haussmann and E. Pardoux. Time reversal of diffusions. The Annals of Probability, 14(4): 1188 1188-1205, 1986.
Z. He, T. Sun, Q. Tang, K. Wang. X. Huang, and X. Qiu. DiffusionBERT: Improving generative masked language models with diffusion models. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Pupers), pages 4521-4534, Toronto, Canada, 2023. Association for Computational Linguistics.
J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840-6851, 2020.
J. Ho, T. Salimans, A. Gritsenko, W. Chan, M. Norouzi, and D. Fleet. Video diffusion models. arXiv:2204.03455, 2022.
A. Holk, C. Strauch, and L. Trottner. Statistical guarantees for denoising reflected diffusion models. arXiv:2411.01563, 2024.
E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. In Advances Neural Information Processing Systems, volume 34, pages 12454-12465, 2021.
M. Hu, Y. Wang, T.-J. Cham, Yang, and Suganthan. Global context with discrete diffusion in vector quantised modelling for image generation. In 2022 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 11492-15501, 2022.
P. Kelly. Reversibility and Stochastic Networks. Cambridge University Press, USA, 2011.
V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34:2593-2656, 2006.
Z. Kong, W. Ping, J. Huang, K. Zhao, and B. Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations, 2020.
H. Lee, J. Lu, and Y. Tan. Convergence of score-based generative modeling for general data distributions. In NewrIPS 2022 Workshop on Score-Based Methods, 2022a.
H. Lee, J. Lu, and Y. Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, 2022b.
S. Lee, K. Kreis, S. P. Veccham, M. Liu, Reidenbach, Y. Peng. S. Paliwal, W. Nie, and A. Vahdat. GenMol: A drug discovery generalist with discrete diffusion. arX11:2501.06158, 2025.
12

---

A. Lou, C. Meng, and S. Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 32819-32848, PMLR, 2024.
C. Meng, K. Choi, Song, and S. Ermon. Concrete score matching: Generalized score matching for discrete data. In Advances in Neural Information Processing Systems, volume 35, pages 34532-34545. Curran Associates, Inc., 2022.
R. Nakada and M. Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(174):1-38, 2020.
C. Niu, Y. Song, J. Song, S. Zhao, A. Grover, and S. Ermon. Permutation invariant graph generation via score- score-based gencrative modeling. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings Machine Learning Research, pages 4474-4484. PMLR, 2020.
K. Oko, S. Akiyama, and T. Suzuki. Diffusion models minimax optimal distribution estima- tors. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26517-26582. PMLR, 2023.
Pidstrigach. Score-based generative models detect manifolds. In Advances in Neural Information Processing Systems, volume 35, pages 15852-35866 Curran Associates, Inc., 2022.
Protter. Point Process Differentials with Evolving Intensities, pages 467-472. Springer Netherlands, Dordrecht, 1983.
Y. Ren, H. Chen, G. M. Rotskoff, and L. Ying. How discrete and continuous diffusion meet: Comprehensive analysis of discrete diffusion models via stochastic integral framework. In The Thirteenth International Conference on Learning Representations, 2025.
P. H. Richemond, S. Dieleman, and A. Doucet. arXiv:2210. 14784, 2022.
Categorical sdes with simplex diffusion.
J. E. Santos, Z. R. Fox, N. Lubbers, and Y. T. Lin. Blackout diffusion: Generative diffusion models in discrete-state spaces. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 9034-9059. PMLR, 2023.
J. Schmidt-Hieber. Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 1914)1191, 2020.
C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, and J. Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. In International Conference Learning Representations, 2020. jtt/sttss: http://///opparooooooooooororaar
Sohl-Dickstein, Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256-2265. PMLR, 2015.
Y. Song and S. Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Y. Song, J. bock-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
H. Sun, L. Yu, B. Dai, Schuurmans, and Dai. Score-based continuous-time discrete diffusion models. In The Eleventh International Conference on Learning Representations, 2023. URL https: //op://///eeeeiieeee weciiiew.eeeeeeeeee htte//oouumm.d-BBBWsss
T. Suzuki. Adaptivity of deep reI.U network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2019. httpppse//ppenreviee.... new. http://wwww.......oooooorrieeaaa
13

---

T. Suzuki and A. Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. In Advances in Neural Information Processing Systems, volume 34, pages 3609-3621. Curran Associates, Inc., 2021.
M. Talagrand. New concentration inequalities in product spaces. Inventiones Mathematicae, 126: 505-563, 1996.
H. Tricbel. Theory of Function Spaces. Monographs in Mathematics. Birkhäuser Verlag, 1983.
H. Triebel. Entropy numbers in function spaces with mixed integrability. Revista matemática complutense, 24(1):169-18) 2011.
A. Vahdat, K. Kreis, and J. Kautz. Score-based generative modeling in latent space. In Advances in Neural Information Processing Systems, volume 34, pages 11287-11300 Curran Associates, Inc., 2021.
S. van de Geer. Empirical Processes in M-Estimation. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2000.
C. Vignac, I. Krawczuk, A. Siraudin, B. Wang. V. Cevher, and Frossard. DiGress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, 2023. /eLLiatttps//ppeeeeeee.eeee wttp:/iiwwwnn/.ffnniieee SateuuumdddUUU--DDDD-- NuBGNN
M. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
T. Wu, Z. Fan, X. Liu, H.-T. Zheng, Y. Gong, y. shen, J. Jiao, J. Li, z. wei, J. Guo, N. Duan, and W. Chen. AR-Diffusio: Auto-regressive diffusion model for text generation. In Advances in Neural Information Processing Systems, volume 36, pages 39957-39974. Curran Associates, Inc., 2023.
D. Yang. J. Yu, H. Wang, W. Wang, C. Weng, Y. Zou, and D. Yu. Diffsound: Discrete diffusion model for text-to-sound generation. IEEF/ACM Transactions on Audio, Speech, and Language Processing. 31:1720-177 1733, 2023.
Y. Ying and M. Pontil. Online gradient descent learning algorithms. Foundations of Computational Mathematics, 8:561-596, 01 2008.
L. Zbinden, L. Doorenbos, T. Pissas, A. T. Huber, R. Sznitman, and P. Marquez-Neila, Stochastic segmentation with conditional categorical diffusion models. JEEE/CVF International Conference Computer Vision (ICCV), pages 1119-1122 Los Alamitos, CA, USA, 2023. IEEE Computer Society.
K. Zhang, H. Yin, Liang, and J. Liu. Minimax optimality of score-based diffusion models: Beyond the density lower bound assumptions. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 60134- 60178, PMLR, 2024.
W. Zhang, X. Wang. Smith, Eaton, Rees, and Q. Gu. DiffMol: structured molecule generation with discrete denoising diffusion probabilistic models. In ICML 2023 Workshop on Structured Probabilistic Inference Generative Modeling, 2023.
Z. Zhang, Z. Chen, and Q. Gu. Convergence of score-based discrete diffusion models: A discrete-time analysis. In The Thirleenth International Conference on Learning Representations, 2025. URL https://openrevier wtt.iiiwwww..eeeemmee formm waarrmmmd==qqqlWeeed d=pq1Weegkzz
Y. Zhu, Y. Wu, K. Olszewski, J. Ren. S. Tulyakov, and Y. Yan. Discrete contrastive diffusion for cross-modall music and image generation. The Eleventh International Conference on Learning Representations, 2023, URL httpss//opperreeiieee wtt.://www....eeeo.rri.--e. 1-MB.JssZ-S
14

---

A Construction of Neural Networks
This section collects fundamental tools on function approximation using neural networks. These results play central role in our approximation error analysis. Many of the lemmas below are based on Oko et (2023).
A.1 Composition and Combination Lemmas
We begin with lemmas that describe how to combine multiple neural networks. These lemmas are essential realize large neural network that approximates complicated functions.
Lemma 5 (Nakada and Imaizumi (0200). For any neural networks d'..... .6. with o² Rdd.
Rd and Ø' E L11, ,, B'),") there exists a network & E (I,,, W,S, B) such that 6(x) = Sb of o (u) Rdi with
L Σ L 1=1
S S W S 2 > 1|
2 B s max B
Isisk
1=1
Lemma 6 (Oko et al.
(023 ). For any networks t² ,t..... .²t with Ø² Rd + Rd and
d' @ W St, B²)
there exists network
(L,, W S, B) such that o(x)
[6] (x1) ,..., 6² (xx) TTT Rd 4dy >R t.4 for (x) xg with
& | 2 22>
L = max L' isisk
Σ |
k
2 (St + LW),, B max max B¹, 1}.
Isick
Lemma (Oko et al. 2023)). For any networks .'...., &f with øi Rd. + Rd and øi
(T, W S", )²), there exists a network & E (LL, S,T,W,S, S, B) such that Φ(x) = Σx= (1(;;)
Rd +d + Rd for x = [a] ...I with
L max L' 1, | <4 1sisk
Σ
| | bo,
1=1
S LWE) + 2W,, S S 4
S max max B¹, 1).
1sisk
Lemma 8 Oko et al. (2023)). For 4 < la < ti < l2 and f(r, 1) Rd R - R. assume
that (x, 1) approximates [(x, 1) up to E > within L, L]] (i = 1,2). There exist networks
Sswit (t: t2 t1), oz (t:t. 22. (1) (3, (1,2,111) 8, max(ti, (11 tt) (1)) with
1 (t: t2 J1) (x, t) + oz tg. & o (x. f(x,t)) (t (t,(t,)))
A.2 Approximations of rational functions
The following lemmas describe how to approximate elementary operations such multiplication and reciprocal using neural networks. These are particularly important because the score function in discrete diffusion models involves the ratio of probabilities between two discrete states, which can be approximated by neural networks designed to emulate rational functions.
Lemma 9 Oko et al. (2023)). For 2, C 1, Eerror S and 0, there exists a network
Smuit ( (ZI, T& E LLL, W, S, B) with L = Ollog k(loge-1 + k klog C)), || 48k, S
Oollog + l log C)), B = O such that (x)) < C² Omult ( (21,..., IKk = 0 if at least one of x; equal zero, and
Pmatt (41, 22 ..... x6))
Se kO* Cerror: Vx EE || 211100 S Eorror-
15

---

Lemma 10 (Oko et al. (202))). For constant R > and any 0 < < R there exists
network Prec 1..
Tk) E $ W,S, S, B) with = Ollog ) = Ollog" 5 =
Olog ). = 2) such that
(re)lze) 1 I
S x/s
Vx E [R R|, x' E R.
B Poisson Random Measures with evolving intensity
this section, we introduce the formal definition of Poisson random measures with evolving intensity, which is a foundational concept required for implementing the r-leaping algorithm. Although this concept is not central to the main theoretical results of this paper, we include the definition here for completeness and reference.
Definition 2 (Protter (183)); Ren et al. (2025) ). Consider a probubility spuce (2, F,I) and measure space (X,B, B, v). A non-negative predictable process dely) on R& x x Q is assumed to satisfy for any T > 0:
Sf J
< <0 a.s.
where v is the counting measure. probability measure [[A](d,, dy) on R2 x X called a Poisson random measure with evolving intensity >e(y) if:
1. For any B E B and 0 S < [[)]((s 4 B) P represents a Poisson distribution with the given expectation.
(fe St (d))u(dg)) where P(.)
2. For any t 2 0, B and disjoint Be.s( the processes {N.[A](B.) = N[A]((0, x
B:) } t independent.
C Proof of Theorem 1
To prove Theorem 1, decompose the total estimation eтror into approximation and generalization components.. We begin by analyzing the score approximation error with neural network. This part captures the model bias, and the resulting bound depends the smoothness of the score function and the expressive power of the network class. The subsequent subsection will then address the generalization error using tools from statistical learning theory. Together, these analyses yield the desired estimation error bound.
C.1 Approximation error analysis
In this subsection, we construct neural network that approximates the score function sf (zx y) in compositional manner by separately approximating Pr (z) and its reciprocal 1/Pe(z), and then combining them multiplicative way.
Lemma 11. For any E there exists neural network o! (x, e &(L, W,S, B) such that
(0' - Mp.(z)) SE Vt
The parameters of o¹ (x, t) are bounded as follows:
L = Olog² MET
|| llo O(M log Me 1)
S O(M log Mei )
B ( v log MaT').
Proof. We begin by approximating the function e >,t using neural network. Define A = log 3e
16

---

For j = O, we set 0, = 1 so that e e is approximated without an error. For j >> 0, using the Taylor
expansion, we obtain
(-\a)² i!
(1= + (-X,)a+1 (0(1 s)))att) (I: + 1)!
e Ape -
(1 (1-8)
where 0 E [0, Setting k max 12e² D1, [log 38
$1.. ,. we obtain the bound
e Aya (-),)
(->;) k+1 (k 1)!
1
(6+ 1)! (0(1 - (0(1-5))*t)
3 le k+1 S
<
((E: + 1)/2eD)
Here, we used (n/e)" < n! in the second inequality. By Lemma 9 for each (-> (1 8), there
exists neural network @(t; i) that approximates it within error of e/3(k 1) over the interval 8 S I S 8 2/2g- The network parameters satisfy:
Olog' =
W xc Ollo E 1
S Olog e
B ((1).
Similarly, by lemmal 7 there exists neural network (1) that approximates e within error of e/3 over I t < + 2/Ag, with the following parameter bounds:
L Olog 8 =
W | Ollog E 1
S Ollog* E-1),
B O()).
Note that (x)u)(x)] < 1. Indeed,
9j = Σ (x)
Σ Epo(a)s po(x)) LEX
E2)())3
Σ po(x)2 < Epo(s) = 1.
ZEX
ZEX
ZEX
Thus, we can construct neural network (2, t) that approximates ej (x)( -hy as follows:
(1 1) Pmmut Sowi (t;
-1]-1
Σ
dmult
(t: (s 1)/Aj; (s 2)/Ag), Sewi (t; s/Aj, (s 1)/2,), (,1 (6 Om
Using Lemma the approximation eтror from each Omalt is bounded by 8/ loge-1 We set the parameters of Pmult to L. (log e -1), | = 0(1,, 5 O(loge the input t of (z, t) to the range [0, we define (x, t) = (e f) 6) A)) (z, A). This ensures that (x, approximates e - with an error at most for all 2 0. For t < A, the following inequality holds: (0, - (zy( Ast| & c/3 + e/3 < E. For (x, dy (z) + (z, A) ( A
= 0(1). To restrict
t> A, we have (x, (z), -aytee--s11=0 A
(x) Ayt -e ->,4)] 0 + 22/3 + e/3 = e. Thus, the parameters of o(x, t) are evaluated as follows:
Olog? 1
W |o
Ollog =11);
S O g -!),
B O(log -1).
17

---

Finally, setting E = E1/M² and summing By (z. t) over all j ,,..., M,, we construct neural network o² (2x, 1) that approximates Mpr(x)) within an emror of e1. By Lemmas and the parameter bounds given by
I = O(log M
W < O(M log Me
S O(M log" MeT
B = OM2 V log ME
Building on this result,
construct neural network that approximates the reciprocal (/p((x))
Lemma 12. For any 0 < S t and $1 there exists neural network (xx 1) E (LL W,S, B) satisfying the following inequality:
(x, Mp((a) Se + R2
A1 O.
with the parameters of d² are bounded as follows:
= Ollog Eo v log MET!), ))
| O(log" 3 Eo v M Mlog McT ) S O(log* 4 ED Mlog MEi ),
B O(M 6 log Ma
Proof. From Lemmas and 10
there exists of² (2x t) Dree of (xx t) satisfying
(x,
I Eu + R2E1.
Mp((F)
Here, the network parameters coincide with those stated above. Regarding pt, the boundedness of the MMp((r) score function ensures that Mpr(x)) E.cxPe(M Excr of Lemma
M
which satisfies the conditions
10
Combining the approximations of (x) and its reciprocal, network that directly approximates the score function si (z, y) pt (v)/pt The following lemma formalizes this construction and provides the approximation error bound.
now ready to construct neural
Lemma 13. For any 0 en t and 82 0, there exists network Pscore (x, y. 1) F such that
Docore (x, v,t) (z. v)1 S + R& + Vt 0.
Here, the parameters of @score are evaluated as:
Olog कp log² MeT v logez
| lc = Olog Eo v M log Me
S = Oloog v M log Mej Vloge
B = O v log 1.
In particular, the following holds:
T
Eg-op
Σ
BR (dxcard (I, y, (f) (x) (((,)))( di S Rlog
18

---

Proof. Consider the neural network & (z) 16' (y.
t)] (x,
which parallelizes the esti-
mation of (b)) and (z), The function Oscoro y. == munl o x² (a, y, t) is neural network
that estimates si (2, v) pdfvl and its error is evaluated as follows:
(=(
@score (I. v. - 2s (x, vx) - mu (0' (v. t), (x, t)) - (v, (z, t)l + (1. (x,
o (v.
8 (y.
6 s (v, 10 (x,
(( v)
(x)
Mp.
1 E2 (y, 8 (x, Mpr(2) t)
+ Mp((
10 (v. -pr(v))
Eu (R² R)E1 E2.
From Lemmas 5
and 12 the parameters are bounded showed in above:
L Ollog* sp v log Mej V log E2
| >c = Ollog 6o M log MeT
= O(log" co v M log MET v log loge5
B = O v log ).
Considering (score v, t) which restricts the output of Øscore y. 1) [1 RR, RJ. Assumption ensures that this restriction does not increase the error, and the order of the parameters remains unchanged. Thus, we can conclude Éscore E
Since 1/R S Øscore: 8 < R and 0 S x - -lo((z) - I 4 (lo - 1)2 for E 1-1/12,, we
have that
@scooro (0 log @scoro (2,, (2, y1,
BR (&score (x, y. (1,,)
(x,
(x,,))
S (l)o(()((Qocord)) (,t,,t//(((z..)) - -
Therefore, we obtain that
Buwps
Σ
BR (Oscoro f)ss v)) (x, df
Enppi
Σ (2, 1),, di
u
Epppe
Σ
log (2,cor)( - (x 83) -0 v) dt
uイ
4R 4Rllog()(Es)) (R² MR)er + E2)2 / Ddl =
S Rlog(R) + R²
which achieves the assertion.
C.2
Generalization Error Analysis
This subsection focuses on bounding the generalization error. The analysis proceeds in three steps:
First, relate the score estimation enror conditional form via denoising representation. Second, define loss class and control its generalization error using local Rademacher complexity and Peeling device.
Third, we derive explicit complexity bounds using covering number estimates for neural networks.
19

---

We begin by expressing the explicit score matching entropy as the denoising score entropy. This representation justifies interpreting the score entropy as the empirical loss.
Lemma 14 (Lou et al. (0044).. For any se(se, v) and i 0, the following holds:
Σ Σ
BR 1) (rr, u)) si v)p (ax))
ΣΣΣ
BR (sr 9))ss mo)) si (Zt, y so)pe(are 20)po(=0))(21 2) + C,
Zt VFΣ.
where C a constant independent of 8t-
Proof.
Σ
Σ
BR (s (Rx(s((2,)))66(( v)) si (1x((
St yola
Σ
log (e(
(x w)
+ 1 pe Q)())Q((ee))))
oi (FT.
Σ
log oi (xt1 x0)
of (Tr, xo) + 1) (1 xo)po(Z0) (x),, 8)
sc( v)
Σ
(log di (z,,, v)) pr(y)
E
log oi (Zi, 3/ xo)
Σ
(s vills æo)) (f y mo) pe(a, (0)p)( + C,
where C' is a constant depending only pr, Q.
Next, We relate the Hellinger distance to the expected excess risk.
Lemma 15. For any g E G {g =- ls la 1 E F}, we have that f li, sf)dl S Pg.
Proof. From Lemma 14 we have:
Pg L(Ge) L(se)
Erypp
Σ
BR (Fees, v)ll v)) (1,, (0) v) di
(1
(1 +1) (xe. (2) dt sf v)
Ez pup
Σ
log
si (Ee, v)
3e (2r, v) (2t, y) -1)
(e 8) $7 (Ir: v)
+1
2
Ex Baperpss
2
8 (x v) Q v) dt
usfure
Exeoe
Σ
(-2 3 (2,,, 8) v) + ie (2r, v) + 3, v))Q((re v) dt
utz
=f/" 1(Be, dd
which concludes the assertion.
Here, we aim bound the generalization error using the local Rademacher complexity R2 (G.). We define G, {g = b, - lo 1 G, Pg r)
20

---

Lemma 16. For any E G == {g 6. -6 E0 S F}, it holds that llgllc X TRD which also indicates that Pg & TRDPg.
Proof. Define (z, zu, t) = (x) zo)) (2 v/ zo). Then, for any F, 2, y E X, it holds that
c. U. Tu, t) fo y, vo.t)
(t y) - (0 v)
loog st(2, v)
si (a,, y zo)
(I. zo)
$t (z, y)
8z (x v)
(se(2r, y) - (x( log
(2r, mo)
(x v)
s1 y)
- (s((,, y) 5 (z. y) +
log
8 (z., y mn)
sx y)
S 2R + 2 log(H)s
xo))
Therefore, we arrive at
(l,(z)) lo- S
{/' Expepi(1
Σ
(Z, v0, fa To, (1 8) dt
< T Egeepell)za)
Σ
[2 + 2 log( (x,
mn)] de
2 - RD +
E Eyr-ma(-1ao)
dt Σ llo
S 4(T - RD
where we used the symmetricity of Q and in the last equality. Therefore, we have Pg² lggloooPg & TRDPg.
We introduce two classical tools for controlling the supremum of the empirical loss. Proposition 17 (Peeling device (van de Geer 2000 Bartlett et al. 2005 Koltchinskil 2006 )
Suppose there exists a function Φ [0, 00) + [0, oc) and r* > 0 such that Vr r",
@(4r) 20(r), (G,) S Φ(r).
Then, Vr 8", the following holds:
1 E
o.g(z.)
40(r)
E
(x.)(or))
sup LGEG
Pg
Proposition 18 (Talagrand's concentration inequality). (aalagrand 1996 Bousquet 2002 Let G
be a separable set of measurable functions on the probability space (X, A, P), and suppose that dg E G.
E[g = O, Elg² = v, 11 SC
Then, Vt
Pr sup GE n
n g g(x)) 2 2E
n sup LoEa n
Σg gaas)
+
21u
21C
Se-t
n
n
By using these theorems, the prediction error can decomposed into the approximation error (model bias term) and the generalization error (variance term).
21

---

Lemma 19. Define 8 = arg min fEF L(f), 3 = arg L(f), g = ls fse, and
r" L(s") ). For the function @(r) defined Proposition 17
there exists f 2
max {, r", tTD such that the following holds with probability 1 2e 2e=
TRDt
P +0
n
Proof. By Lemma 16
Pg - TRDPg, 1lel S TRD.
Define G = {g
Pg- Patr
G
Then, the following holds:
Pg- Pg 0,
Pg +T
Pg 9
9
TRD
1 l0 =
+1
Pg +r 00
|P - 21l2, (Pg r)²
Pg²
(Pg)²
Pg²
TRDPg TRD
2 12
2
(Pg+r)
Pr
rPg
Using Proposition 17
to bound the term (x,) sup gea 1 -
in Proposition 18 have
E
sup (P- Pn]ğl
s 22n((G)
Gee
1
n
Pg g( Pg +r r
2B (m.)(())
sup
9EG 71
n
g(x,)
sup
0i
gEG n
Pg tr
86(r)
The first inequality follows from a standard property of the Rademacher complexity, and the final bound is derived using Proposition Therefore, from Proposition [8. it follows that with probability at least 1 - -e-t.
160(r)
21RD
21
(P Pn)
sup gEG n
Σ
g(x.) x
(r).
Pğ+r +r
r
nr
nr
Let us define g" = lost
10 St. Then, we get
Pğ [(xe) ((8t)
= L((e) - [((() + [.().) [((st) + [(st) L(s)) + L(st) - I(se) + [((st) [(s+)
(P Pa)g + (Pn P)g" Pg
< (Pğ + -r) (r) + (P,, -P)g* +
Since pg* < TRDP' , the second term can be bounded via Bernstein's 's inequality Wainwright 2019 Proposition 2.14) as
rtt
TRDI
TRDI
(Pr - Pig. 50
< 50
TRD
with probability 1-e- for l > 0. We now choose F 2 max (()),r,, ITRD
If necessary, we
can scale so that (,) < 1/2. Under this condition, the following inequality holds:
()) F 1 1/TRDD r" + +0 TRDt
Pÿ E 1 (T)
1- (F(
TRID
Sf+r" 0
22

---

To evaluate the complexity function ((r), we use known bounds on the covering number of ReLU neural networks.
Lemma 20 (Schmidt-Hieber 2020 For S c + W, the covering number log N (E, 8,
(loo) satisfies
log (N, S, 11x0) & Log 1)W=-!)
Combining Lemma 20 with the Dudley integral gives the following bound the local Rademacher complexity.
Lemma 21. For Ø(r) defined in Proposition
(v
SLr log(L(B 1)]lW]
<(r)
By combining these local Rademacher complexity controls, we obtain the proof of Theorem D
Proof of Theorem I. From Lemmas inequality holds:
15 and 19
with probability at least 1 2e- the following
L.
TRDt (P S o (+tr--
According to Lemma
13 the model bias term r* can be bounded as
T RRD c e1 + E2),
Furthermore, from Lemma 21 the generalization error is bounded as
F= ST. So [(Bv
The network parameters satisfy the following upper bounds:L Ollgg Eu log Mej log e "), || (log² so v log Ms
Olog" Eo v-v log M&-1 Vlog 8 12
O(M V Ve log MeT1). To balance the size of each term, we set En A R- n nD
M
M¹ V M
nD
M RD'
Given that D = O(M), the desired bound follows.
D Proof of Theorem 3
In this section, we provide the proof Theorem 3 While the subsequent analysis closely parallels the arguments in Appendix([] the key distinction here lies in the use of function approximation theory in anisotropic Besov spaces.
D.1 Approximation thoery in anisotropic Besov spaces
Here, give the function approximation method in anisotropic Besov class by deep neural networks. We define the affine composition model, which composes affine transformations with functions in anisotropic Besov space:
Hal (h(Ax + b) h e U(B (1O, 1) A E RxD be Rd s.t. Ar + [0, 1]d (vr e 2)).
Under this model, the following bound the approximation error is known.
Proposition 22 (Suzuki and Nitanda (202I)). Suppose follows the uniform distribution on Ω [0, 1]. and define = Ax + R. which is assumed to have a bounded density supported on 1]. Suppose there exists a constant C such that ||A]] [|b]]sc C. Then for < p. q: r S co , the following approximation error bound holds:
and B E IR__ satisfying 3 >
R,(*(L, Wi ((BB))))))((()))))(())))
(d)), Han) S NN"
23

---

fEF Ilf fll denotes the worst-case approximation enror. Here, the network parameters are set as
where (F, == eu jn
3dvm
(d) = + 2 log2
+5
[loge(d V mm]]
(C(d.m)
W1(d)= = NW.
(idd) = ((Li(d) 1)W3 + 1|N,
(d = ((vd(++ ((
where c N- No (oog(N)~ and C(d.m) is constant depending only on and m.
D.2
Approximation error bound
Under Assumptions Assumption to we construct a neural network that approximates the score function (x)
Lemma 23, For every k E [I,...;.. MI, there exists a neural network Prome (z, 1) E & W,L, such that
1 (2, Mpr(x)) (N Ve ( Ve 122 S2(k) V 0,
The network parameters satisfy:
L = Ollog (M V N)),
|| = Ollog M V kN),
S Ollog M KN log N),
B = (O"y"M V N)),
where the functions $1 (k) and f2()) defined as:
(1-()-))
(s 7 < 1), (s y = 1),
M
(s < 1),
f1()) <
log
f2(1)) 2
log M
(s = 1),
- 7 1),
k
(>>> 1),
for 1 S k S M and f2(M) =.
Proof. We aim to approximate the function Mp,(x) ME E=j (r) using neural network by truncating the sum fixed number of terms. Specifically, we consider (x) Σ (z)e where each u² E Hat By Proposition & E (TT,(d), (idd), Y, B1 (d)) such that
22 there exists a neural network
|ug 2f ( & N-
Following the same strategy as in Lemma I1 we can construct neural network to approximate the exponential decay ett,, We define (t() follows:
+3 (1) Hmmutt ( (1; 1/A, 2/Ay), (1))+
[A] Σ
Smatt ( (t; (s + 1)/A,, (s 2)/Ag), Levi (t; s/A,, (s 0./a,())
The product uz (e) th can be approximated using (t) and of. and by summing over 1,...
and multiplying by M, we can construct the neural network &oom E &(L, W, B) satisfying ||o - Mpill < N Σ jj=1 * Here, we set the approximation error of ()) and @mult to
E = - According to Lemmas 7 and 9 the parameters of &o can be bounded as follows: L Olog? (M v N)),
|| 0c Ologg M kN),
S O(log M &N log N),
B = OlyaPoly(M V N)).
24

---

Now, the total enror in approximating Pa( is given by
M
k 1A
[x) - dcont (I, t)
N
Y5ō " + M Σ
cuy(x)e
13g
jml
5ml
k
M
N
j (--7) + Me Σ
c1j c
12 + M
Σ
uu (x)e (x))e-
j=l
==1
b=k+1
For the sum Σド (-0-)) and Σ 2z=b+1 j_ we have
k2-
(s 7 < 1),
(a-2) s1+ ' g-(0-
logk k
(s - 7 = 1).
i=1
(8 > 1),
M
{.a dj S
M
MI-s
(s 1),
Σ jmk+1
J S
log M
(s 1),
kl-a
(s > 1).
Since C =1/MM, we can achieve the desired upper bound.
Lemma 24. For any 0 Eo S R-1 there exists a neural network &com( (2,1) &(L, S, B) such that
2oont (z,t) t)
S +
4> 0,
(p((x)
with network parameters bounded as:
L Ollog" Eo v log V N)),
||]] 0. Ologg* (M V V
= O(log M V log' to v &N log N),
= O vxpoly(A V N)).
Here, fk) and f2(k) are defined Lemma 23
Proof. As in Lemma 12 we can construct &oont (x, 1) = Dree Doom (x, 1) to achieve the desired approximation.
Lemma 25. Let 0 80 R-1 and N N. Then, there exists a neural network Dcone (x, y, F such that
1dcont (I, t) 8 (x, vll S Co + R²((N-- ve
(222)) - e -h2 f2)))())) -
V1 > 0.
The parameters of Deou. are bounded as follows:
L = (logg EN v log M V N)),
|| Ologg" (M V V KN),
Olog' M V log En v AN log N),
= O(5 2 Vapoly V N)).
Here, fikk) and f2(k) are defined in Lemma
23 Moreover, the following bound holds:
{ Exrpp
Σ wok
BR (Dcent (2. y, (1))))))())))))) -3 (x, y) dt
Rlog(R) +
V f2(k)) RºN (k)))
25

---

We construct a network dont (2. y, == (y, t), oe (z. t)] by combining the neural networks that approximate Mpr(y) and 1/Mp:(r)in parallel. Then, define the overall network as Oeont (2, 1) = Qmllt p=lv) and the error can be bounded as p.)))
Proof. The proof proceeds in similar manner to Lemma 13
(x, ys t). This network estimates the true score (i v)
follows:
décnn (I, v,t) - si 8)1 - munlt (o [V, t), o (), 2 (v. (z, 10 (v, (x, (x,)))
o' d'(y,t) o' (v.
I 61 + Φ (v,
Mp((x) +
Mp((a)
S + (v. 1) 2 (x,1) Mp((x)
+ (px
10'(v,)) MPr(u))
$ + +1t (2N ve (() td2 f2(K)).
Setting E1 Eo gives the desired approximation rate. By the same argument as Lemma [3 we can bound the divergence as
Eawp
BR (dcone (2, v. u, v)) (x,,,)((z,,)) dt yf
Eappi
Σ
lolog(R) (o) - ((((,))) dt
< (R)og(R)
ve RR &ve -et Ve 1hs -ha f2(k)))
t/ (e (e (2())) R². S( (N- ( ((-))(()))TTA))))
< RR)
TD RA RAI
x R log( (eloggy)DD(e,, + 1² (Ef((()) V fa(k)) + A (k))))
where we define to = min A, (ōlog N + log ( f1(k)) }
f2(M)
D.3 Proof of the statement
By combining the results from Appendices C.2 and D.2
we are now ready prove Theorem 3
Proof of Theorem 3. By applying Lemmas 15 and 19
we obtain
L
TRDi
(2 s dt S o f+r*
with probability 1 2t By Lemmas 21 and 25 the model bias term r" and the generalization error F can be bounded as:
r" S TRlog( (R) + R X₂ (k) fe(k)) + R2N + ( AA))?
8 = o (L v W)| n)
By setting N O - (k)()) 2s and co = O (n 1/22), we have
rイン (m (m R (A)) + +,, 2 [2:)² + 2 logo v N).
We consider balancing the first and second terms as follows:
1. When S 1 (and thus 7 - 1): By setting l M. obtain
y* + + n 1+23
23
20 (1-
1428
+ X 2 202 =22
log*(M (M v N).
26

---

2. When < 8 and 8 - S 1: By setting ht = (2 n that
we have
201 (0-((--)+3)
28(e-1)
r² + S
12
2510 Dia 1)133 (a-1)(1
23 (--1-()-)))
+8a \2
[[--1](1+3)++i)) -t (--
log (M N).
8 and < 7.. By setting & (n (n- 1n-B21 212 1-8--1 we have
3. When 1
28
28(4-11
+
A2
+ 25= log log V N).
E Proof of Corollary 1
E.1 Proof of Lemma
Before proceeding to the main proof, we present a preparatory result on the spectral properties of the graph Laplacian in Lemma 4 Since (xr) (-1)a' for every w f0, 1) the function hw {0, 1] + / 11 an eigenfunction of the adjacency matrix A defined on {0, 11P. Let the state 2; (0. 1} l satisfy d(e;, x) = in terms of the Hamming distance, where the index i indicates
the coordinate at which v; and x differ. Then, we obtain
D (w,) = -D -Iwl) - hm (x) = -0(w2]] hh.w)) (I), E
which implies h:w is an eigenfunction of A with the eigenvalue D - 2/wl. Since L = DI A, where I denotes the identity matrix, it follows that hn is also an eigenfunction of L with eigenvalue 2 w/) and in particular, A2 =
E.2 Main proof
First, we show (z) cos(Tw" Tx)), x)) v M belongs to the Sobolev class ( 1) for any constant B E N. Sobolev spaces are defined by
1/2
aaa
1*( = f (EL
Iff =
Σ |a SB
D
fl?
< <00
D =
Jan
Here (a)....a0 .an.....))))). E No. Using the chain rule, we obtain
hm = M (cos(TTW) T 2), sin(ww") (Tw))
27

---

The term Pa is finite linear combination of trigonometric functions and |a. = (1). In particular, we have the bound | hw x O(1 la /VM). Thus, the Sobolev norm of ft is bounded as
Σ
hm
lalsp
Σ
Dhhlld
[0.1]
la|s
Σ
O(1w|3aa///) /M)
sa
Olwo|3aa| MM)
k= la|=k
= -(D3s//M
0(1).
This implies that hw E ([0,
1JD) and, in particular, h. lies in the scaled Sobolev unit ball: there exists constant Tw 0 such that hw (11 where (H))) denotes the unit ball in /1 (RR.. Since H =B in the sense of Besov spaces, Thcorem can be applied directly. Specifically, for the function uj (z) = cos(Tw) z), Assumptions and 6 with parameters & = 0, 7 O and O. Moreover, Lemma Lemma@ennurree that A2 (1). By choosing / sufficiently large, the desired bound follows from Theorem 4
F Proof of Corollary 2
Here, let (x) be the eigenfunctions of the Laplace-Beltern Beltrami operator - - normalized in (M2, and their corresponding cigenvalues are denoted by μ4 < U2 I ...., that is, -Amo, = Pyoj. and let (m-A)) == { be the set of eigenvalues, For vector (u(x))=Ex, we define
S
u(x)²
[ =
N(w)
ZEX
where ((x) = {y E X
|| vll S o).
Then, the following result known:
Proposition 26 Dunson (2021)
Suppose that M is sufficiently large such that
L2 + 1
4/2+5
8d+266
M max
. + 1i
(5d47)/4,8d 8d+26
(5)
mT.
where L2, W3 are constants depending on and the volume, the radius, the curvature and the second fundamental form of the manifold M, and l'x minigisk dist(ug of AM) Muz3). Let
[oog M) M1
Then for 1 $ K, it holds that
Uy (r(r)
(log(M)
52y10
(5)()) s C2
(6)
[1, (1]](
M
Since -AMO; = po the Sobolev norm of os for 3 E N can be evaluated as
[ - C(1 |4 (6 C(1 C(1+ HG)
Moreover, since it known that [4 = (j2/d)
Hassannezhad et al. 2016), we obtain that
| (e)lww(()) $ $.28 22//
This implies that we may choose = 28/d. Now suppose that 3 is chosen so that -- > 1. More precisely, approximate o, by composite function Φ, the where v/M D - Rd
28

---

represents smooth function giving the local coordinate of MM and oj is function on this local coordinate that corresponds Øj. Then, we may think Φ5 is function in Besov space B2g compact domain of IR", and thus Φj UM can be approximated by ReLU deep neural networks with an error O
Since p is the uniform distribution, measure concentration inequality (Wainwright, 2019) implies
1d-110" 10dd
((x)
M
uniformly over x E X, with high probability, provided that 2 see that ||ulee<))) @(IluI/VMM @(I/VM). Then, by Eq. (z(x) = (,) = ()(r)/ / v M with the approximation error
In this event, we 6 Assumption is satisfied for
[o
13
log((M) (M) M
SUFTO
To achieve the assertion in Theorem with 3 B/d, we choose k in its proof as
k = (n 8/d 2 1
= WirFalo--- DFFT
which yields μt (5447)/448d-2)) On 0734900-197
O 11734220 14+ Hence, (44 ( On (173420 D11 ) and
2/d
(1=10/)1104420)
(5/24 4/ax04420
(pi
). We assume that M is sufficiently large to satisfy Eq. (5) with this choice of k, which ensures the approximation error bound above holds.
Based on these arguments, Theorem with 3 = 3/d and = 2, gives that
(T. S n 20-111
Bio +
log(AM) M
b+42
- log (M Vn).
which yields the assertion.
29

---

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:
The target of the analysis (discrete diffusion models) is detailed in Section
The convergence analysis is given in Sections and Proof details are provided throughout the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the conclusion section (Sec.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiattinn 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 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 be 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best 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 complete (and correct) proof?
30

---

Answer:
[Yes]
Justification: The assumptions of the theoretical analyses are given in Sections 2.2 and Section
4 before we state results. All complete proofs are provided throughout the appendix.
Guidelines:
The answer NA means that the paper does 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 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 of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
There is numerical experiment in the paper.
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 be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
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) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a 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 or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe 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 (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
31

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
There is no numerical experiment conducted in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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
/ "pipsscc/puullc//uuu /tto://uuuddeeoooouuuubmmiibia ssionPolicy) 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. only subset of experiments are reproducible, they should state which ones 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 to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: 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 to understand the results?
Answer: [NA]
Justification: This is purely theoretical paper. There no numerical experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
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: There is no numerical experiment.
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, at 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 to a library function, bootstrap, etc.)
32

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: There is no numerical experiment.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 or 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 NeurIPS Code of Ethics httppp/s//.aaatp...ccpppp/////aa
Answer: [Yes]
Justification: The authors have checked that the research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is purely theoretical paper and no immediate societal impact is expected.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is purely theoretical paper.
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 that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses 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 use existing assets.
Guidelines:
The answer NA means that the paper does 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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
34

---

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/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
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 details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 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
Question:
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?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 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
35

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development and theoretical analyses in this research do not involve LLMs.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
36


Reviews:
[{"review_id": "E4mEj0hdP6", "reviewer": "Reviewer_zn3k", "summary": "This paper presents a theoretical framework for analyzing the estimation error of discrete diffusion models, addressing a gap in existing studies which has focused primarily on continuous diffusion models. The authors derive score estimation error bounds employing Hellinger distance and such bounds depend only polylogarithmically on the size of the discrete state space. Overall, the paper deepens the theoretical understanding of discrete diffusion models, enabling the development of more accurate and efficient algorithms for practical applications involving discrete data.", "questions": "Refer to the above section.", "limitations": "The paper provided limitations in Section 5 (conclusion).", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "*Disclaimer: I must state that this paper does not fall into my field of expertise.*\n\n**Strengths**:\n\n- The paper covers an appropriate amount of previous works, and states the clear contribution compared to the previous work of (Ren et al., 2025). \n- Overall, the paper is well-structured.\n\n**Weaknesses**:\n\nTo my understanding, there is no major weaknesses, yet there are few questions:\n- While I acknowledge that this paper primarily focuses on developing a rigorous mathematical framework regarding the statistical bounds for discrete diffusion models, planning at least a toy example to validate the practical implications would greatly enhance the paper.\n- Is there a particular reason to choose the \\tau-leaping algorithm for simulating the backward process? To my knowledge, there exists other algorithms as well such as the uniformization scheme.", "was_revised": true, "final_justification": "I raise my score from 3 to 4. However, I must say that I am not an expert in this field.", "rebuttal": "Thank you for your helpful suggestions!\nPlease find our responses to your points below.\n\n**Q1:While I acknowledge that this paper primarily focuses on developing a rigorous mathematical framework regarding the statistical bounds for discrete diffusion models, planning at least a toy example to validate the practical implications would greatly enhance the paper.**\n\nWe performed an **additional score-matching experiment** that exactly instantiates *Example 1* (hypercube $\\{0,1\\}^{D},\\  M := 2^{D}$).  \nFor each $D\\in\\{6,8,10\\}$ we generate two distributions using the Hadamard basis:\n$$H\\in \\{ \\pm M^{-1/2} \\}^{M \\times M},$$\n\n$$\\ell(x) = (Hc)_x, $$\n\n$$p(x)=\\frac{e^{\\ell(x)}}{\\sum_{y=0}^{M-1}e^{\\ell(y)}}$$\n\nThe coefficient vector $c\\in\\mathbb{R}^{M}$ is chosen as \n* **low-frequency**: $c_{0},\\dots,c_{4}\\sim\\mathcal{N}(0,1)$, $c_{k}=0$ for $k\\ge 5$; \n* **high-frequency**: $c_{k}\\sim\\mathcal{N}(0,1)$ for all $k\\ge 2$ (DC and first harmonic set to 0). \n\nActivating only the first few modes yields a smooth distribution, whereas using the whole spectrum (minus the DC term) creates a highly oscillatory one.  Each $p$ is evolved for time $t=1$ with the rate matrix $Q$ shown in Assumption 7.  We then train a single-hidden-layer score network $s_{\\theta}(x,y)$ (input $2D$, 256 ReLU units, Softplus output) using the denoising score entropy loss. Training uses 5000 random Hamming-1 pairs, ADAM (lr $=10^{-3}$), and 20 epochs; performance is the mean DSE over all Hamming-1 pairs.  Each setting is repeated ten times.\n\n| $D$ | spectrum | mean DSE × 10⁻⁴ | std × 10⁻⁴ |\n|:---:|:---:|:---:|:---:|\n| 6  | low  | **2.30** | 0.69 |\n| 6  | high | **2.84** | 0.57 |\n| 8  | low  | **2.64** | 0.43 |\n| 8  | high | **3.04** | 0.58 |\n| 10 | low  | **2.89** | 0.49 |\n| 10 | high | **3.37** | 0.45 |\n\nThe mild increase from $D=6$ to $D=10$ (≈ +47 %) matches the logarithmic dependence on $M=2^{D}$ predicted by Theorem 4 and Corollary 1, while the higher errors for high-frequency mixtures reflect the bounds sensitivity to the smoothness parameter.  These observations provide concrete evidence that the theoretical guarantees translate directly to practice without any hyper-parameter tuning or architectural changes.\n\n\n**Q2:Is there a particular reason to choose the \\tau-leaping algorithm for simulating the backward process? To my knowledge, there exists other algorithms as well such as the uniformization scheme.**\n\n\nAs noted in [Ren et al., 2025 ; Chen & Ying, 2024], both the τ-leaping and uniformization schemes can be formulated as stochastic integrals using Poisson random measures with evolving intensity, and each allows a rigorous analysis of the backward process in discrete diffusion models.\nThe core contributions of our paper lie in deriving statistical error bounds via concentration inequalities and neural network approximation theory. These analytical tools apply uniformly across both $τ$-leaping and uniformization schemes, as both share the same underlying stochastic integral formulation [Ren et al., 2025, Theorem 3.2]. Therefore, the choice of algorithm does not affect the main flow of our proof or the validity of our theoretical results.\n\n### References:\n\n- Ren, Y., Chen, H., Rotskoff, G. M., & Ying, L. (2025). *How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework*. ICLR.\n- Chen, H., & Ying, L. (2024). *Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization*. arXiv:2402.08095."}, {"review_id": "mDM0uxexwJ", "reviewer": "Reviewer_YSng", "summary": "This work introduces state size-independent score estimation error bound for discrete diffusion models. The paper is an extension of such theoretical analysis in continuous scenarios. The authors address a critical challenge that the error became intractable when the state size grows exponentially with the dimension size in discrete scenario, by embedding the discrete space onto R^d Euclidean space and approximating the eigenvectors.", "questions": "I have no further questions.", "limitations": "No", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths and Weaknesses\nThe paper is well written and demonstrated. The authors provide concrete analysis within its scope. I would like to especially highlight the authors’ good introduction of sufficient previous materials, which make its contribution clear and specific. The idea is original and the result is useful empirically since changing the dimension of language models by using sub-tokens or super tokens is a common practice in pre-LLM era in many domains including language and molecular modeling. This result might be helpful for people to understand the consistency of model performance when changing the tokenization. The weakness is that the paper has no experimental analysis. The paper will be more persuasive even with a small sanity-checking experiment. However, I think this is not a must for this paper to be published, as its current contribution is already meaningful to the community.", "was_revised": true, "final_justification": "It is a nice paper with enough theory and good results. The authors have addressed my all concern.", "rebuttal": "Thank you for your positive assessment of our contributions! Regarding the numerical evaluations, we have conducted a numerical experiment and confirmed that the dimensionality does not impact the accuracy very strongly while the amplitudes of high frequency components affect more. See the rebuttal to zn3k for more details."}, {"review_id": "JGBvETHer7", "reviewer": "Reviewer_nWBC", "summary": "The method proposes a theoretical framework with a error bound by mapping discrete variables to continuous space and approximating the error bound with the theory tools from Gausian diffusion.", "questions": "Q1. Why the bound in Euclian space is still hold for discrete space? since some assumption like 2, 3, 4 are adopted from continous diffusion.\n\nQ2. Is there any practical applications benefited from the theorical bound? Empirical evidence is needed.\n\nQ3. Could the authors provide concrete practical examples where Assumptions 3 and 5 are satisfied? These assumptions appear quite restrictive.\n\nQ4. Is the bound also true for large model?", "limitations": "Yes, the authors acknowledge adopting the same bounded score function assumption used in continuous diffusion models, but this assumption may not be appropriate or may be loose for discrete settings. Another important limitation is the lack of empirical results to validate the theoretical findings, so it is impossible to assess the usefulness of the bounds.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Deriving the bounds by embedding to continuous Eucliean spaces is clever and technically sound.\n- Proofs seems correct and solid unless there is any issue raised by other reviewers. \n\nWeaknesses:\n- The paper is quite dense in the technicality, making it hard to get intuition. \n- No empirical validation of the theoretical bounds, make it less connected from practical applications.\n- The bound involves many restrictive assumption, raising a concern its validity in practice.", "was_revised": true, "final_justification": "Thank you to the authors for the detailed responses and the additional empirical results! I am satisfied with the rebuttal and believe the theoretical framework proposed is very solid and provable, providing an analytical tool to further understand and improve existing discrete diffusion models. Thus, I increased my score.", "rebuttal": "Thank you for your valuable and constructive feedback! We provide our responses below.\n\n**Q1:Why the bound in Euclian space is still hold for discrete space? since some assumption like 2, 3, 4 are adopted from continous diffusion.**\n\nIf the concern is specifically about the validity of Proposition 3 under discrete settings despite assumptions borrowed from continuous diffusion models (e.g., Assumptions 2, 3, and 4), we would like to clarify that our theoretical framework is rigorously grounded in the discrete setting. In particular:\n\n- Proposition 3 is not derived by naively applying continuous space assumptions. Instead, it is based on a discrete stochastic integral formulation established by [Ren et al., 2025], where the reverse process in discrete diffusion models is expressed as a Poisson random measure with evolving intensity. This approach enables us to bypass the need for tools such as Girsanov's theorem, which are only valid in continuous spaces, and still allows us to quantify the error propagation caused by score estimation in a principled manner.\n\n- More concretely, as shown in [Ren et al., 2025], the reverse process admits a stochastic integral formulation:\n\n  $$\n  y_t = y_0 + \\int_0^t \\int_{\\mathcal{X}} (y - y_{s-}) \\, N{[\\mu]}(ds, dy),\n  $$\n\n  where $N{[\\mu]}$ is a Poisson random measure with intensity \n  $\\mu_t(y) = s_{T-t}(y_{t-}, y) \\cdot \\widetilde{Q}(y_{t-}, y)$. \n  This is the discrete analogue of the Itô integral and supports a change-of-measure theorem analogous to Girsanov’s theorem in the continuous case.\n\n- Therefore, the theoretical bound in Proposition 3 in our paper is derived within the discrete probability space, using a well-defined stochastic process and score entropy-based loss under assumptions suitable for the discrete setting.\n\n**Q2:Is there any practical applications benefited from the theorical bound? Empirical evidence is needed.**\n\nWe highlighted two concrete application scenarios that directly benefit from our bounds in the paper:\n\n- **Example 1: Hypercube** — As discussed in Section 4.3, our theoretical results apply to state spaces structured as a hypercube $\\{0,1\\}^D$, which are relevant to binary discrete modeling tasks such as molecular generation and certain language modeling applications. In this setting, we rigorously show that the estimation error bound becomes independent of the cardinality of the state space when $s \\geq 1$, aligning with the optimal rates predicted by Ren et al. (2025).\nWe have also conducted additional numerical experiments in this setting, which empirically confirm that the estimation error is not significantly affected by the dimensionality $D$, whereas the amplitude of high-frequency components has a larger impact. See our response to reviewer zn3k for details.\nThese results connect to the practical use of discrete diffusion models in domains such as molecular graph generation [Shi et al., 2020] and graph-based modeling [Niu et al., 2020].\n\n- **Example 2: Discrete Graph Diffusion** — In Section 4.4, we consider a graph diffusion process defined over a point cloud on a Riemannian manifold. This corresponds to practical settings such as protein design or 3D point cloud generation, where the underlying geometry enables efficient approximation of eigenfunctions. Our theory provides guarantees even in this more complex non-Euclidean scenario. This connects to prior results on manifold learning and Laplacian approximation [Dunson et al., 2021; Fefferman et al., 2016].\n\nWhile we agree that empirical validation is important, our main goal in this submission is to establish a rigorous foundation that can support and guide such practical deployments. We believe future empirical studies, particularly in the above settings, will benefit from the insights and guarantees provided by our theoretical framework.\n\n**Q3:Could the authors provide concrete practical examples where Assumptions 3 and 5 are satisfied? These assumptions appear quite restrictive.**\n\nRegarding Assumption 3, we note that in our setup the transition rate matrix $Q$ is taken to be symmetric , which implies that the stationary distribution $\\pi$ becomes uniform over the discrete space $\\mathcal{X}$. In such a case, the forward process $\\{p_t\\}$ converges exponentially fast to the uniform distribution as $t \\to \\infty$. Consequently, for sufficiently large $t$, the score $s_t^\\circ(x, y) = \\frac{p_t(y)}{p_t(x)}$ becomes close to 1 for any $x, y \\in \\mathcal{X}$, thereby naturally satisfying the boundedness condition $s_t^\\circ(x, y) \\in [1/R, R]$. This setting is reasonable and widely applicable in practice.\n\nFor Assumption 5, while it is indeed more technical, we emphasize that our paper provides two examples where it holds as we mentioned above.\n\n**Q4:Is the bound also true for large model?**\n\nIf the term \"large model\" refers to complex architectures such as LLMs, then our theory remains applicable in principle, provided that appropriate function approximation guarantees can be established.\n\nOur theory is designed to be general. It relates the total generative error to the score estimation error, without depending on a specific model architecture. This means that if the score function can be well approximated by a complex model like Transformer-based model, then the same theoretical bound can be applied. complex models. The key requirement is not the size of the model, but whether the approximation error of the score function can be controlled in a suitable way.\n\nAs noted in Assumption 3, structural properties such as symmetry of the rate matrix $Q$ play a key role in ensuring stable behavior of the score ratio $s_t^\\circ(x, y)$. This assumption is still desirable in large models, as it enables uniform control of the statistical error. However, it does not preclude the use of large-scale expressive networks.\n\nIn summary, our theory provides a flexible and broadly applicable analytical framework. While we instantiate it with specific neural network classes in this paper, its applicability extends to any model architecture for which a suitable approximation theory can be established.\n\n### References:\n\n- Ren, Y., Chen, H., Rotskoff, G. M., & Ying, L. (2025). *How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework*. ICLR.\n\n- Shi, C., Xu, M., Zhu, Z., Zhang, W., Zhang, M., & Tang, J. (2020). *GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation*. arXiv:2001.09382.\n\n- Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., & Ermon, S. (2020). *Permutation Invariant Graph Generation via Score-Based Generative Modeling*. arXiv:2003.00638.\n\n- Dunson, D. B., Wu, H.-T., & Wu, N. (2021). *Spectral convergence of graph Laplacian and heat kernel reconstruction in \\(L^\\infty\\) from random samples*. Applied and Computational Harmonic Analysis, 55, 282–336.\n\n- Fefferman, C., Mitter, S., & Narayanan, H. (2016). *Testing the manifold hypothesis*. Journal of the American Mathematical Society, 29(4), 983–1049."}, {"review_id": "pHf1tHTwzi", "reviewer": "Reviewer_fq8A", "summary": "The paper touches on an important topic of present interest, namely convergence of discrete diffusion models. It closely follows the recent paper:\nY. Ren, H. Chen, G. M. Rotskoff, and L. Ying. How discrete and continuous diffusion meet: comprehensive analysis of discrete diffusion models via a stochastic integral framework, 2025.\nand analyzed the score error convergence rate. The discussion about how embedding discrete symbol space into vector space improves complexity (section 3) is interesting.", "questions": "The paper is quite similar to [Ren et al. 2025]. Can you clarify the differences?\n\nDoes the proposed algorithm achieve any kind of theoretical minimax optimality, analogous to the nonparametric optimality in [Oko et al. 2023]?\n\nI don't quite understand the Poisson integral representation in Proposition 2: how are y_t and \\mu here related to the reverse process (4). In particular, in (4) the random variable is in a general discrete space, whereas in Proposition you need y_t to be in a vector space. Are you using a specific embedding?\n\nIt is mentioned that a substitute of Girsanov is used to control the error. Can you give an intuitive explanation of the idea and comment on whether it is a tight bound?", "limitations": "So far, the assumptions seem to be restrictive, and the error bound (corollary 2) seems ugly and not optimal in any sense.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Occasional typos (e.g. capitalize probability measure in Definition 2)\n\nSection 3 shows that a naive estimator has complexity growing in D exponentially, which can be improved using vector embedding. Perhaps this can shed light on better algorithm and practices in real world applications?", "was_revised": true, "final_justification": "Thanks for the response and I will keep the rating.", "rebuttal": "Thank you for your thoughtful comments! Our responses are as follows.\n\n**Q1:The paper is quite similar to [Ren et al. 2025]. Can you clarify the differences?**\n\nWhile our work builds on the foundational stochastic integral formulation of discrete diffusion models developed by [Ren et al. 2025], the core novelty and contribution of our paper lies in addressing a key limitation of their assumption of a fixed score estimation error (Assumption 4.6 in their work).\n\nSpecifically, [Ren et al. 2025] analyze the $τ$-leaping scheme under the assumption that the estimation error of the score function is bounded by some constant $ε$. However, they do not investigate how this ε can be achieved in practice, nor how it scales with the state space size $M$. In contrast, our work focuses precisely on verifying and quantifying this assumption, by developing a statistical learning theory that relates the score estimation error $ε$ to the sample size  $n$, the neural network class, and the number of discrete states $M$.\n\nTo overcome the curse of dimensionality inherent in discrete spaces (where $M$ can be exponentially large in the dimension), we leverage the continuous embedding approach and the approximation theory of deep neural networks developed in [Oko et al. (2023)]. This enables us to show that, under mild regularity assumptions, the score estimation error $ε$ can be bounded polylogarithmically in $M$. Our approach thus turns the previously assumed constant $ε$ into a rigorously derived bound, making the overall theoretical error bound explicitly dependent on the state size in a provably mild way.\n\nIn summary:\n\n- **[Ren et al. 2025]**: Introduce the stochastic integral framework and analyze error propagation under a constant $ε$-assumption for score estimation.\n- **This work**: Provides a statistical learning-theoretic justification for that $ε$-assumption by constructing neural score estimators whose error scales only polylogarithmically with $M$, thereby achieving state size–independent error bounds under practical conditions.\n\n**Q2:Does the proposed algorithm achieve any kind of theoretical minimax optimality, analogous to the nonparametric optimality in [Oko et al. 2023]?** \n\nOur work does not explicitly claim minimax optimality in the strictest sense. However, we strongly believe that our bound achieves the minimax optimal rate at least in a smooth density setting ($s-\\gamma > 1$ in Theorem 3 and $s \\geq 1$ in Corollary 1).\n\nMore precisely, when $s \\ge 1$, the error bound established in Corollary 1 becomes\n$$\n\\mathrm{KL}(p_\\delta \\| \\hat{q}_{T-\\delta}) \\lesssim n^{- \\frac{2(s - 1)}{2s - 1}} \\log^8(M \\vee n),\n$$\nwhich matches the known minimax optimal rate for function estimation under source and capacity conditions in kernel methods [Caponnetto & De Vito, 2007; Ying & Pontil, 2008]. This indicates that, when the number of basis functions \\(M\\) is sufficiently large, our bound achieves the minimax rate in such settings.\n\nMoreover, in the general case analyzed in Theorem 3, we obtain an error bound of the form\n$(\\text{number of active basis functions}) \\cdot n^{-2 \\tilde{\\beta}/(1 + 2 \\tilde{\\beta})}$\nwhere $\\tilde{\\beta}$. This rate aligns with the known minimax optimal rate for approximating functions in anisotropic Besov spaces [Suzuki & Nitanda, 2019]. Thus, even without an explicit minimax claim, our theoretical analysis captures regimes where minimax optimality is plausibly achieved.\n\nTo summarize, while the formal proof of minimax optimality remains an open and challenging direction due to the combinatorial nature of the discrete state space, our error bounds already exhibit minimax-optimal behavior in representative regimes. We hope this provides a useful foundation for future work in formally establishing such optimality guarantees.\n\n\n**Q3:I don't quite understand the Poisson integral representation in Proposition 2: how are y_t and \\mu here related to the reverse process (4). In particular, in (4) the random variable is in a general discrete space, whereas in Proposition you need y_t to be in a vector space. Are you using a specific embedding?**\n\nIn our analysis, we assume that each discrete state can be embedded into a Euclidean space using a fixed representation such as one-hot encoding, as discussed in Section 2.1 of our paper. This allows us to treat the discrete variable $y_t \\in \\mathbb{X}$ as a vector in $\\mathbb{R}^M$, where $M = |\\mathbb{X}|$, thereby enabling the formulation of the reverse process as a stochastic integral in Proposition 2.\n\nImportantly, this formulation is not limited to one-hot encoding. For instance, in the hypercube setting $\\mathbb{X} = \\{0,1\\}^D \\subset \\mathbb{R}^D$, the natural embedding $\\iota: \\mathbb{X} \\hookrightarrow \\mathbb{R}^D$ can be directly used. The Poisson integral formulation still holds since the stochastic process evolves via discrete jumps across the embedded support of $\\mathbb{X}$, and the vector representation is used only to define the direction and magnitude of each jump.\n\nThe idea of expressing discrete diffusion models via Poisson-type integrals with evolving intensity is adapted from [Ren et al., 2025]. As the intensity function $\\mu_t(y)$ in Proposition 2 is defined in terms of the reverse process rate matrix and the score function, and the trajectory evolves in jumps from one discrete state to another, this representation naturally respects the discrete nature of the process despite using a vector-valued notation. The rigorous construction of such stochastic integrals over discrete spaces requires care, particularly in defining the evolving intensity $\\mu_t$ and ensuring well-definedness, as detailed in [Ren et al., 2025].\n\n**Q4:It is mentioned that a substitute of Girsanov is used to control the error. Can you give an intuitive explanation of the idea and comment on whether it is a tight bound?**\n\nIn continuous diffusion models, Girsanov's theorem provides a justification for replacing the drift term in an SDE when the score function is perturbed, which in turn allows us to bound the KL divergence between the true and the approximate distributions using the score estimation error (see, e.g., [Chen et al., 2023]).\n\nIn the discrete case, [Ren et al., 2025] proposed a stochastic integral formulation of discrete diffusion models based on Poisson random measures with evolving intensity. Within this framework, they derived a change-of-measure formula (Theorem 3.3 in their paper), which can be seen as a discrete analogue of Girsanov’s theorem. Specifically, the change of measure characterizes how the likelihood of a trajectory changes under a perturbed intensity function, and connects the score entropy loss used in training to the KL divergence between path measures (see also Corollary 3.4 in [Ren et al., 2025]).\n\nIn our paper, we build upon this formulation: the change-of-measure result guarantees the validity of Proposition 3, which relates the score estimation error to the total error in the generated distribution via the τ-leaping algorithm. However, we do not directly use this change-of-measure formula in deriving the statistical error bound itself. Rather, it serves as a theoretical foundation for validating the link between the loss function and the KL divergence.\n\nAs for the tightness of the bound, we kindly refer to our response to Q2.\n\n---\n\n### References:\n\n- Ren, Y., Chen, H., Rotskoff, G. M., & Ying, L. (2025). *How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework*. ICLR.\n- Oko, K., Akiyama, S., & Suzuki, T. (2023). *Diffusion Models are Minimax Optimal Distribution Estimators*. ICML.\n- Suzuki, T., & Nitanda, A. (2021). *Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space*. NeurIPS.\n- Caponnetto, A., & De Vito, E. (2007). *Optimal Rates for the Regularized Least-Squares Algorithm*. FoCM, 7(3), 331–368.\n- Ying, Y., & Pontil, M. (2008). *Online Gradient Descent Learning Algorithms*. FoCM, 8(5), 561–596.\n- Chen, H., Lee, H., & Lu, J. (2023). *Improved Analysis of Score-Based Generative Modeling*. ICML."}]

Author rebuttal:

Meta-review: This paper provides a framework that gives rise to more meaningful theoretical results for discrete diffusion models. The authors shows how spectral smoothness of the state space can lead to error rates that scale only polylogarithmically with the number of states. Their work helps elucidate the theory behind discrete diffusion models and their good empirical performance. Their work is nontrivial and a contribution to an important area of research.
Decision: Accept (poster)