Breaking AR’s Sampling Bottleneck: Provable Acceleration via Diffusion Language Models
Authors: Gen Li
Changxiao Cai
Venue: NeurIPS 2025 poster ()
Keywords: diffusion model
large language model (LLM)
iteration complexity
mutual information
Primary area: theory

Abstract: Diffusion models have emerged as a powerful paradigm for modern generative modeling, demonstrating strong potential for large language models (LLMs). Unlike conventional autoregressive (AR) models that generate tokens sequentially, diffusion models allow for parallel sampling, offering a promising path to accelerate generation and eliminate the left-to-right generation constraints. Despite their empirical success, theoretical understandings of diffusion language models remain underdeveloped. In this work, we develop convergence guarantees for diffusion language models from an information-theoretic perspective. Our analysis demonstrates that the sampling error, measured by the Kullback-Leibler (KL) divergence, decays inversely with the number of iterations $T$ and scales linearly with the mutual information between tokens in the target text sequence. Crucially, our theory covers the regime $T<L$, where $L$ is the text sequence length. This justifies that high-quality samples can be generated with fewer iterations than $L$, thereby breaking the fundamental sampling bottleneck of $L$ steps required by AR models. We further establish matching upper and lower bounds, up to some constant factor, that shows the tightness of our convergence analysis. These results offer novel theoretical insights into the practical effectiveness of diffusion language models.

Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models
Gen Li" Chinese University of Hong Kong genli@cuhk. edu .kk
Changxiao Cai University of Michigan cxcai @umich edu
Abstract
Diffusion models have emerged powerful paradigm for modern generative modeling, demonstrating strong potential for large language models (LLMs). Un- like conventional autoregressive (AR) models that generate tokens sequentially, diffusion models allow for parallel sampling, offering a promising path to accel- erate generation and eliminate the left-to-right generation constraints. Despite their empirical success, theoretical understandings of diffusion language models remain underdeveloped. In this work, we develop convergence guarantees for perspective. Our analysis
diffusion language models from information-theonm demonstrates that the sampling error, measured by the Kullback-L.eible (KI.) di- vergence, decays inversely with the number of iterations T and scales linearly with the mutual information between tokens in the target text sequence. Crucially, our theory covers the regime 7 L, where L is the sequence length. This justifies that high-quality samples can be generated with fewer iterations than L, thereby breaking the fundamental sampling bottleneck of steps required by AR models. We further establish matching upper and lower bounds, to some constant factor, that shows the tightness of our convergence analysis. These results offer novel theoretical insights into the practical effectiveness of diffusion language models.
Introduction
Large language models (LLMs) fall within the domain of generative modeling, which aim to learn the unknown probability distribution of natural language from training data. The state-of-ther LLMs are typically trained using an autoregressive (AR) modeling paradigm. For a text sequence of tokens (x(1), (T.),, an AR model factorizes the joint distribution
p(z) p(x()))))
II p(x(() x
(i-1))
(I)
and generate tokens sequentially from left to right. Despite its remarkable success (Radford et al. 2018 2019; Brown et al. 22200) the AR approach suffers from several notable drawbacks. First, token generation is constrained by rigid left-to-right order, prohibiting the model from reasoning earlier tokens based on later context. Second, the one-by-one generation is inherently slow, as tokens are produced one at time, limiting the efficiency of sampling.
Motivated by the above limitations and the extraordinary performance of diffusion models in various generative modeling tasks (Sohl-Dickstein et al., (2015) (Song and Ermon 2019 Ho et al.) 20200 Song al. 2020), recent research has begun exploring diffusion models alternative approach to
"The authors contribute equally.
1 Cooresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

language modeling (Dieleman et al. 2022 Han et al. 2022 Gulrajani and Hashimoto 2023 He
al. 2022). Unlike the AR paradigm, diffusion language models allow parallel sampling of tokens through an iterative denoising process, thereby eliminating left-to-right constraints and potentially accelerating text generation. Discrete diffusion models have emerged as promising framework for
LLMs in this vein (Austin et al. 2021] Campbell et al. 2022 Lou et al. 2023), which is tailored to generate discrete-structtuee samples.
Among the discrete diffusion models, one notable class is the masked diffusion model (Asttin al., 202T; Shi et al., 2024, Sahoo et al. 2024). It introduces an absorbing state called mask and achieves the best empirical performance. Identical to its continuous counterpart, the masked diffusion model consists two complementary processes: forward process that progressively corrupts a text sequence Xo Pdata drawn from the data distribution by masking out tokens:
Xa
mask
X1
mask
mask
mask
XTi
a reverse process that learns to reconstruct the original sequence by iteratively predicting the masked tokens:
Yo
unmask
Yi fo Y2 unmask
unmask
Yr-
The mask predictors- distributions that take partially masked sequences input and predict masked tokens a role analogous to the score estimators in continuous diffusion models, guiding the reverse process recover the text.
Compared to the AR paradigm, diffusion modeling offers several key advantages for language generation:
Sampling acceleration. By generating multiple tokens in parallel at each iteration, diffusion models can reduce the number of sampling iterations and speed up the overall sampling process compared to one-token-at-a-tine AR generation'.
Reversal reasoning. Without unidirectional order, diffusion language models can perform reverse generation tasks (for example, inferring earlier tokens from later ones) that are impossible for standard AR models constrained a forward-only generation.
Controllable generation. Because diffusion models do not follow a strictly left-to-right generation order, they more easily incorporate global constraints or planning for long- range dependencies, enabling more flexible control over the generated text (Li et al. 2022).
These benefits have spurred a surge of interest in diffusion language models. A flurry of recent works has demonstrated the viability of diffusion models for language models, showing that they can achieve comparable performance to AR approaches in certain settings (Lou et al. 2023 [ahoo et al., 2024. Gong al.) 2024 Campbell et al. 2024 Nie al. 2025 Ye al. 2023). Moreover, diffusion language models have been shown to handle generation tasks beyond the reach of AR methods, such
reversal reasoning, which standard AR models cannot perform (Nie et al. (025).
However, despite their empirical promise, rigorous theory for diffusion language models remains in its infancy. In particular, there is limited insights into how the quality of the generated text relates to the sampling procedure or to the statistical structure of the underlying language distribution. Only until very recently have researchers begun to explore its sampling guarantees. The work (Chen and Ying 2024) examines convergence guarantees of discrete diffusion models terms of total variation (TV) distance and Kullback-Leibler (KI.) divergence. However, their analysis is restricted to regimes where, on average, less than one token is masked per step. This assumption does not align with practical diffusion language models that mask a large fraction of tokens at each iteration (Yu et al. 2025). Such a gap between practice and theory motivates the central question of our study:
Given accurate mask predictors, can we establish the convergence guarantees of diffusion language models for general sampling procedures and data distribution?
'While diffusion language models enable parallel sampling, current practical implementations are typically slower than highly optimized AR models with KV caching (Pope et al. 2023). Recent work demonstrates that distillation can close part of this gap (Deschenaux and Gulcehre 2024 Hayakawa et al. 2024); see Sahoo et al. 22044 Fig. 2) for comparison of text generation speed.

---

Main contributions. In light of the above gap, this paper takes an initial step towards convergence perspective. We seek rigorously
theory for diffusion language models from an characterize the quality of the generated samples (i.e., sampling error) as a function of the number of iterations steps and the statistical structure of target text distribution.
To make the analysis tractable, we adopt a standard decoupling approach in prior theoretical analyses of diffusion models (Block al., 22000] De Bortoli et al.
Li et al.) 2024 Li and Yan 2024] Li and Cai. [0224] Li et al. 2025), which separates the training stage (how to learn the mask predictors) and the sampling phase (how to generate samples). Our work focuses on
2021 Chen et al. 2022a 2023a
the latter, assuming access to given mask predictor and analyzing the sampling procedure.
Under this setup, we establish the first convergence guarantees of diffusion language models for general sampling schemes and data distributions. In particular, our analysis shows that after T iterations, the KL. divergence between the output distribution and the true data distribution decays on the order of 1 /T, with a coefficient governed by the information coupling among tokens. Specifically, we prove an upper bound on the sampling error (measured by the KL divergence) of the form:
( Σ T(X(0 x(10)
+ Strain:
where ((x (xx ) denotes the mutual information between the i-th token X (1) and the remaining tokens X under the data distribution X ~ Pdatt. and êrain captures the training error due to imperfect mask predictors (see Section 2 for a formal definition). Notably, our theory accommodates the regime where the number of iterations T is smaller than the sequence length L, which provides a formal justification for the sampling acceleration of diffusion language models over their AR counterparts. Further, complement this upper bound with a matching lower bound (up to constant factors), showing that our convergence analysis is tight. In other words, the 1/T decay of error and its linear dependence on the sequence's 's mutual information cannot be substantially improved in general.
Our theoretical findings, grounded in information theory, provide new insights into why diffusion language models can be so effective in practice. The above guarantee holds for a broad class of data distributions, suggesting that diffusion language models have robust performance across diverse language data. Moreover, by linking convergence to the mutual information among tokens, our results highlight how the statistical dependencies in language data influence the efficiency of parallel diffusion sampling.
1.1 Other related work
Discrete diffusion models. While diffusion models were initially introduced for both discrete and continuous state spaces in the seminal work (Soht-Dickstein et al. 2015)), subsequent studies have predominantly focused Gaussian diffusion processes in continuous domains. Applying diffusion models to intrinsically discrete settings is challenging because Gaussian noise cannot be directly applied corrupt discrete-valued data. Prior works on discrete diffusion models can be broadly categorized into two classes. The first class embeds discrete structures into a continuous space and applies continuous diffusion (Chen et al. [002bb] Dieleman et al. 2022 Gulrajani and Hashimoto 2023 Han et al. 2022 Li et al. 2022 Lovelace et al.) 2023) Strudel et al.) 2022). The second class directly defines the forward process on discrete structures using various categorical Markov transition matrices (Hoogeboom et al. [021] Austin et al. 2021 Sahoo et al.) (022), often under the
continuous-time Markov chain (CTMC) framework. This perspective has further led to methods for
adapting score matching (Song and Ermon 2019) to discrete settings (Meng et al. 2022 Sun et al.)
2022
Lou et al. 2023).
Theory for diffusion models. Our work is closely related to the convergence theories for continuous diffusion models in d field that is considerably more mature than its discrete counterpart. These studies address a fundamental question: given imperfect score estimates, how many iterations are required to sample accurately from the target distribution? Under the assumption of a---ucurate score estimates and a log- Nog-Sobolev inequality for the target distribution, [eabuutioon,ee@daaa et al. (2022) established the first polynomial iteration complexity bounds. Later works relaxed these assumptions by either imposing Lipschitz continuity the scores (Chen et al. [022aa] Lee et al. 2023) or by requiring bounded support/moment conditions for the target distribution (Chen et al. 2023a). The current state-of-th -hhe art results, derived in Benton et al. (2023) and Li and Yan (2024). achieve convergence rate of
3

---

((/d/T) in KL divergence and (d/T) in total variation distance, respectively. In addition to the convergence analysis, recent work has established end-to-end statistical guarantees by characterizing the errors in the score estimation and sampling stage. These analyses yield rigorous bounds on the
sampling error in diverse distributional settings, such as smooth densities (Oko et al. 2023 Chen
et al., 2023b; Wibisono et al., [2024] /hang et al. [024 Dou et al. 2024 Cai and Li 2025 and
Gaussian mixture models (Gatmiry et al. 2024
Chen et al. 2024).
1.2 Notation
For integer n. > O, we denote [m]] == {1. 2........ For I > O, we use [æ] to denote the smallest
n).
integer greater than or equal to x and [x] denote the largest integer less than or equal to æ. Let X denote the (discrete) vocabulary of texts. We use M to denote the mask and extend the vocabulary X
by including a single point [M] to obtain X = X U [M). For vector I E X4, we use x(() to represent
its i-th entry for i [4]. Moreover, for any set M C [4], we use o M (xi)ieM denote the
vector in || that consists of the entries of indexed by the set M. In addition, let PM : X" denote the projection defined as
Dig E M, (M) = M, i i M.
For a random variable X, we use Px to denote its distribution and probability density function interchangeably for simplicity of notation. For random vectors (X,Y) Px.y with marginal distributions px and py, let (L ll py) == pxx(() log (2
px(x) dx denote the Kulback-Leible
divergence between px and py. The mutual information between X and Y is defined as I(;;Y) = (L(xx,y Pxpy). For random vectors (X, Y. 2) ~ Px,Y2. the conditional mutual information between X and Y given Z is defined as T(X;Y Y 2) = (L(pxyizpz PxIzPy 2P2).
For two functions (n), (n)) 0, we use f(n) & g(n) f(m) (g(n)) to mean f(n) I Cg(n) for some absolute constant > 0. Similarly, we write f(n) 2 g(n) or f(n) ((g(n)) when f(n) 2 (m) for some absolute constant C" > O. We denote f(n) x g(() or f(n) (g(n))
when Cf()) S g(n) S (n)) for some absolute constants C" > C > 0.
2 Preliminaries
In this section, we provide a brief introduction to diffusion language models.
Forward process. Consider a text sequence Xo X of length L drawn from the data distribution Pdata- The forward process gradually corrupts Xo by masking its tokens step by step until reaching a fully masked sequence (M, (M...., M) E X² In more detail, let { be a sequence of positive integers such that ΣT= St = L. We call it mask size schedule since it defines how many tokens to mask each step. We then construct sequence of increasing mask index sets
Mo S M, S ... C Mr = [T.]. where each M, is obtained by adding new indices chosen uniformly at random from the previously unmasked positions M Formally, each step / E [7). we select subset M. \ M of s, token positions from Mf_, uniformly at random and mask those positions, and let Mr denote the set of all masked positions at step f. We denote by X, the partially masked sequence at step f, obtained from the original Xo by replacing tokens at the masked positions M, with the mask symbol M. Using the projection operator PMς defined in ( we can write the sequence at step as
X, = Pase (Xo),
(3)
meaning X, retains the original tokens in positions not in M, and has M in positions Mt. After T steps, Xy (M...., M) E x" is the fully masked sequence.
Training. The reverse process aims to invert the forward masking: starting from the fully masked sequence, it iteratively unmasks tokens to recover a sample from Pdata- The core of the diffusion language model is a mask predictor p(- X,) that represents the conditional distribution of the masked tokens given the partially observed sequence X,. To learn the mark predictor, we fit the

---

generative model to the data distribution by minimizing a variational upper bound on the negative log-likelihood.
As directly modeling the joint distribution of all masked tokens can be intractable in high dimensions, practitioners typically parametrize the mask predictor using factorized form:
p X2)
II (((( Xx),
(4)
i.e. each token is predicted independently given X₁. We then seek product distribution that solves the following minimization problem:
-1
min -E Mo 1
Σ iEM,
log lxg 1x+)
(5)
[M
where the expectation is taken over a random time T E [7] with P(T = = s for t E [T], a training sample Xo Pdata draw from the data distribution, and random mask set of size [M,] chosen uniformly at random from [... Notice that the loss in (5) is computed over masked tokens. In
practice the objective in (5) is approximated by its empirical average
the finite training samples.
As remark, let II_ pj denote the optimal predictor (i.e., the minimizer of (5)). Then one verify that for each E [L] ( X,) coincides with the true conditional distribution P Px ( (X)
of the i-token x given the partially masked sequence X².
Sampling procedure. Once the mask predictor p is trained, we generate new text by simulating the reverse process. Initializing at step T with Mr [L] and Yr (M, ......,,. M) X we iterate for t= - 1,..., as follows. We first choose a subset of 8; masked positions to reveal, consistent with the forward schedule. Formally, we sample mask set M,-1 S M2 such that M, \ M,-1 consists of indices chosen uniformly at random from M, (the currently masked positions). Next, we sample placeholder values for the tokens in Mc \ M using the learned mask predictor p and current iterate Y;:
Y1- = Page (Yi) + PMAMM,,,, with X, ~ p- Yi).
(6)
Equivalently, sample each masked position E M, MM-1 from P- Y2) and leave the already unmasked positions i & M, as they are in Y,. We then fill in those sampled tokens to obtain the next sequence Y,-1, while keeping other positions fixed. After repeating this procedure down to we output fully unmasked sequence Y, E XL.
Main results
In this section, we present the convergence guarantees for the sampling procedure of diffusion language models (see (6)).
To begin with, we introduce the following definition to characterize the quality of the mask predictor P used in the sampling process.
Definition 1. For mask predictor estimator 5 = I1 Pr. define its training error as
[ L
L
Etrain Er.X..M.
Σ FEM.
log pt (X
x+) No.
Σ VeM,
log IX [
[
[
where p* is the minimizer of the objective 5
In essence, the training error Strain measures the likelihood gap caused by imperfect training of the mask predictor.
5

---

3.1 Sampling error upper bound
With the above definition, we now state our main results. We first present the sampling error upper bound. The proof is deferred to Section 4
Theorem 1.
For any mask size schedule {st)E=1 let 8max == max 8t be the maximum mask
size. Also, let M- (M1....,M denote the sequence of mask sets. Then the output Yo of the
sampling procedure (6 satisfies
2 floga Smanl
I Σ
E [L I| PYojas]] &
1(xx
(xx=))x6-)))
+ Etrain
(8)
L
Here, the expectation is taken over the randomness in the mask sets M1
Mr-
Our result demonstrates that the sampling error- mroo--eeaurred by the KL divergence between the output distribution Py, and the data distribution Pdata consists of two components: an information-theoredd term depending on the data distribution Pdata and an estimation term train arising from imperfect mask predictions. It is noteworthy that the result holds for arbitrary mask size schedules (sx) which covers parallel sampling schemes where multiple tokens are unmasked per step (st > 1), and thus the number of iterations 7 can be less than the sequence length L.
The first term captures the difficulty of modeling the token dependencies: is the sum of mutual information between each token and the rest of the sequence Σ I(X!"; x(-1)) scaled by a factor that depends on the mask size schedule { The dependence on the mutual information quantifies how the intrinsic coupling of tokens in the data affects the difficulty of sampling while the second term Stainn reflects the training error of the mask predictor.
Notably, if the mask predictor is optimal (i.e., train = 0), then the sampling error is governed purely by the information structure of the data distribution. In general, the bound indicates that the more statistically dependent the sequence tokens are (higher mutual information), the larger the potential sampling error, unless more refined mask size schedules are used to compensate.
Furthermore, under balanced mask size schedule where the mask sizes are set roughly uniform across iterations (i.e., 8t x L/T for all e [T] and thus Smax x L/T),, the leading term in Theorem simplifies to O1/TT) and we obtain a cleaner bound:
Corollary 1. Suppose ΣT= 8,
Smax- Then the output Yo of the sampling procedure 66 satisfies
Es [L(xxx, PYoIM)] S
Ci
Σ xx Etrain T
where C1 = T Ei=1 St x is an absolute constant. Here, the expectation is taken over the randomness in the mask sets ,
In this regime, after T iterations the sampling error becomes O(1/T), with a prefactor given by the total mutual information El= I(X: ( xx-+)) of the sequence. In the idealized case Strain 0. to achieve a target error level E in KL divergence, one needs on the order of (11/z) iterations (up to a maximum of order J., since we cannot iterate more times than the sequence length without saturating the improvement). Meanwhile, Striin is nonzero, the final sampling error will decrease to a floor on the order of train- In other words, the sampling error increases proportionally to the training error, underscoring the importance of accurate mask prediction.
Comparison with prior work. The recent work by Feng et al. 2025) examines the efficiency of masked diffusion models for n- d-gram language model, where each token is generated based on its preceding n tokens (Brown et al. 1992). To quantify token-level accuracy, they introduce token error rate (TER), defined via perplexity:"
Definition 2. Given a data distribution Px. and an output distribution PY: the TER is defined as
log2 TER(PE:: == - Ex. [log (Xo)].
(10)
'They also analyze the inefficiency of masked diffusion models via sequence error rate (SER), which falls beyond the scope of this paper.

---

When n is fixed constant (independent of the sequence length L), Feng et al. (2025) shows that masked diffusion model can achieve a small TER using a few iterations, which is independent of sequence length L. However, their bound on TER scales as ((n 1)/T) 1/n log |X], which is suboptimal for any n > 1 and becomes increasingly loose as n grows. Indeed, consider a trivial baseline that samples Yo Po uniformly at random from all length-L sequences, L..,, Po Unif (X)). For this baseline, one can verify that log, TER(pp Pn: - log, TER(px, : S log [X]. To beat this when 2 log T., the result of Feng et al. (2025) requires T 2 (n 1)4hh > I., which is substantially larger than the sequence length L. Consequently, their guarantee can be vacuous for realistic values of n.
In contrast, our results offer a sharper guarantee, which covers arbitrary data distribution. Indeed, by Corollary |
we immediately obtain
log2 TER(Py;:xx, log2 TER(PX;:PX.)
KL Il pxa) } ENs [KL(px. L
Ci TL Σ 1 1 Xx xx)
1 I Strain (11)
PYbIM)]
L
where the first inequality makes use of the convexity of x + log and Pva EM [P Since ((X,); x² ) < Hxx))) I log X KL convergence bound implies a TER bound that decays as O(log (X) in the worst case. This means the token-level error in our framework drops on the order of 1/",, regardless of n. Therefore, unlike Feng et al. (2055)whichh which is confined specific n-gram distributions and degrades for high-order 7-oour bound improves the prior convergence guarantees and holds for arbitrary distributions.
3.2 Sampling error lower bound
Given the upper bound in Theorem | natural question is whether this convergence rate can be improved. In other words, are there fundamental limits that prevent diffusion language models from converging faster than O(1TT)?
We proceed answer this by establishing matching lower bound. In fact, prove that the dependence on the number of iterations T and the mutual information in Theorem iis tight. In particular, Theorem 2 below provides refined expression for the error and shows that substantially faster rate is achievable in general. The proof can be found in Section[4 4
For simplicity of presentation, we assume log2 Smax and L/smax are integers without loss of general- ity. Otherwise, the same bounds hold up to some constant factors.
Theorem 2. Consider an arbitrary mask size schedule {st LT with Smax == [ 8t > For each token index [L] and integer 0 S log2 Smax, let W(- [L.] be a random set such that i w(-0) and [W(- L. Smax 2-3, Then the output Yo of the sampling procedure 4 satisfies
EM [L |l PY][M]]
8max
ΣΣ 2- w [((X)'
(1), Xo xo w/(
+ Strain
(12)
2L
120
Moreover, there exist some mask size schedule {st [s with 9t x Smax for all E [T] such that
Ex [KL || PYG]A)]]
Smax
E F [1x]') Xo w! + Strain
(13)
16L
120
In summary, Theorem 2 demonstrates the sharpness of our analytic framework by refining the mu-
(0) ; Xo tual information term from ((x)) ((x(('xx; x(=")) in Theorem to Σ Σ,z0 2 2E [(x))
)] which is tight up to constant factors. The somewhat complex double sum can be understood as finer-grained decomposition of the mutual information between token x(() and the rest of the sequence, split across different "scales" of conditioning (the sets W((-)) represent randomly chosen subsets of other tokens whose size increases j grows).
7

---

Crucially, the lower bound 13 guarantees the existence of a particular choice of {st (satisfying Smax/ L x 1/T) for which the sampling error does not decay faster than on the order of 1/T with the same linear mutual-information dependence. In other words, it is impossible, in the worst case, to achieve a substantially smaller error than our upper bound-the O(1/T) convergence rate and its linear dependence on the mutual information are fundamental limits. This matching lower bound highlights the optimality of diffusion language models' convergence analysis: we establish the best possible order of error decay for the parallel diffusion sampling scheme given the information- theoretic complexity of the text data distribution.
It is worth emphasizing that the lower bound in does not hold universally for every mask size schedule. For example, if we set 81 = Smax and choose 8, = for all > 1. the resulting sampling еπтог becomes negligibly small. In this regime, a lower bound of the form (13) no longer applies. particular, the number of iterations is T = I 1 8max, meaning the average mask size T-1 St is much smaller than Smax. We conjecture that when the schedule is balanced-i.. Se X 5max. in all practical teatings-maachine
upper and lower bounds of order 1/TT should still be attainable. Establishing this general result is an interesting direction for future work. Remark Our theory provides insights into the entropy-based unmasking strategy. Specifically, (12) reveals that the per-step contribution to the total sampling error is the conditional mutual information between a newly revealed token and the remaining masked tokens. This suggests prioritizing the unmasking of tokens whose conditional dependence on the rest of the sequence is weakest. A simple heuristic to implement this strategy is to rank tokens by their conditional entropy at each step t: use the learned mask predictor (e Y.) to estimate the conditional entropy H (x (+) Yy) for each masked position i, and unmask the positions with the lowest conditional entropy. This approach exploits the inequality [(;; Y Z) < H(X) Z) for any random variables X, Y. Z, allowing us to approximate the mutual-infi inntuuliiffoomtiionn criterion without requiring additional training external estimates. Unmasking positions with lower conditional entropy thus provides a principled way to minimize the error contribution at each iteration.
4 Analysis
In this section, we provide the proof strategy for Theorem auxiliary lemmas are deferred to the appendix.
I
The detailed proof for Theorem 2 and
Preparation. We find it helpful to introduce an auxiliary sequence (Yz")=o using the optimal mask predictor p" =I Pf (the minimizer of 5p). Specifically, we initialize Y = (M...., . M) and for each t E [T. define
Y == PMy (Y²) + +PP+PPMA PMAYM. (X;) with Xi p"( Yr),
(14)
where we use the same mask schedule (M4)?= as in the true sampling procedure 66
Next, let us define W, == MM and D. = W,-1 W, for each t E [T]. By construction, (D,)_ forms a partition of [Z] and [D. = 8, for all E [T]. Similar to M == (M, Mr), we denote
W = (W1.... Wr) and D = (Di...., Dr.) for brevity.
It is worth noting that by the construction of (Y₂*) in (4), given mask schedule (mi,...,,T)) we can use the chain rule to express the distribution of Yo as
T p" (zo o di xo wx), p=
Pyg IM (zo m) PAg My.... (To m1 mT)
II t=1
(15)
where we recall for any set w E [T]] x o w denotes the vector in X|w| with entries a0() for i E w. Similarly, the distribution of the output Yo of the sampling procedure (6) given a mask schedule m can be written as
T
Pro m) := Pro|M.... (zo my...., mT)
II
p (zo o d, 20 w.).
(16)
'Here and throughout this paper, we slightly abuse the notation: in 15 we write p' (No o di I 2o o wx) in a way that it accepts an input of length lux). while p², detined in (5), takes masked sequence of length L. It is not hard to that the two equivalent since the remaining tokens are replaced by the mask M.
8

---

With the above preparation complete, we now begin to prove Theorem
Step 1: Decoupling training error. We hegin by separating the training error from the fundamental sampling difficulty. For any mask schedule m, we can write:
KL (L (.) |1 PYojas( m)) - KL (-) PrgIM( Im)
J PXo (2o) log
Pyg (10 m)
T
pr(ro o de
To wi)
dro
Px (xo log
dro
PYolas (20
m)
t= xx
p f o de 30 o we)
p² (=
(8)
2u wi)
Pxo (20)
log
dro
(10
(8)
20 wi)
iEd,
(X Xoo
(ii)
Er,No
log
M = m
VED, Px o W)
Here, (i) follows from P% m) II P (ro de | zo wx) and Pygluul (2o m)
p"= o | zo wy) as shown in (16) and 115 respectively; (ii) is true as p* and p are product distributions; (iii) holds because P((T = St Since each set D, of size 9; represents the
positions newly unmasked at step f, which are chosen uniformly at random from the previously masked positions Mj- = Wr,, taking expectations over all mask realizations yields:
L M
(x Xo o WW,) log
EM [KL(px. || PYoI)) KL(px. PYslar]] = Er,,xo,M
Erain
((X) Xx W+)
iEM,
(17)
where the last step follows from the definition of Etrain in 77
This decomposition shows that in order to control the KL divergence EM KL(xx, |l PY.JM) [M)] between the distributions of the output Yo and data Xo. it suffices to focus on the KL divergence EM [KL PY;[M)] between the distributions of the auxiliary output Y and data Xy.
Step 2: Parameterizing by maximum mask size. Our strategy is to establish a recursive inequality that relates the sampling performance with maximum mask size smax to those with smaller mask sizes. Towards this, recall that the sizes of the mask sets { (Mr are determined by the mask size schedule {s To establish our recursive bound, we parameterize the sampling difficulty by the maximum mask size. Concretely, we define
max <(5max) ( maXie(r) 6m=mx
<({st))
(18a)
where for any mask size schedule {s define
e({xt)) == EM [KL ll PYg M)];
(18b)
We now present the following key lemma that controls e (Smaxx; with proof deferred to Appendix A
Lemma 1. For any Smax > one has
E( 6(8max) S E([ 8m[[max// (2) + Smax
Σ 1(x(";; x(-x)
(19)
2T.
Given Lemma we can apply the inequality (99 recursively obtain
[loga
1-1
2
L
Dlgg Smavl 1
E(8max) <e(1)= +
Σ
(1) x ((=))) e(1) +
Σ
1(x x x x(-i))
T.
L
J=
i=1
(20)
Finally, note that when the maximum mask size equal to 1, we have |M, \ M,-1l = for all
e [T",, i.c., the sampling process unmasks tokens one by one. In this case, it is not hard to use the
construction of Y in (14) and the fact that p X,) Px (: Xx) to deduce that e(1) =
The claim (8) then immediately follows from
and 20

---

ww Pape))
EaleLU (PPall
210:2-001 mutual information
T: number Iteration
(a)
(b)
Figure I: (a) sampling error vs. number of iterations T where = 2: (b) sampling error vs, mutual information where T 10.
Numerical Experiments
In this section, present numerical experiments to validate convergence theory developed in Section For the data distribution Pdata of text X (x ...., .4)), we consider K'state Potts chain of length L with coupling parameter J. Specifically, X ~ Uni(([K]) and for i 2 2,
exp 1fx =t) Va,y E [K].
P(X y (+-11) =x] exp(J) K K-
This construction allows us to compute explicitly the mutual information / (xx(); X(-)), ) the optimal mask predictor p" (- X2), and the distributions of both the data Px, and the generated sample PY We implement the sampling process using the optimal mask predictor p" (- X₂) and a balanced mask schedule where the number of unmasked tokens the same at each iteration. Given the explicit distributions of PX, and PYoIM, the expectation in the KL divergence, taken over both the mask schedule M and the data distribution px. approximated via Monte Carlo simulations.
Set K = 10 and L = 100. Figure (a) presents the sampling error (in KL divergence) vs. the number of iterations T. As shown, slope in the log-log plot very close to demonstrating that the sampling eтror scales proportionally to 1 1/T. In addition, Figure (b) plots the KL sampling eтror vs. the mutual information (controlled by J). One can see that the sampling error increases approximately linearly with the mutual information. Collectively, these numerical studies confirm our main theoretical findings: the KI. sampling error decays as (1/TT) with the number of iterations and grows linearly with mutual information.
Discussion
In this work, have made progress towards understanding the sampling process in diffusion language models. Our results provide tight convergence guarantees, revealing that the sampling emor--quantifedd by the KI. ddiverence-deecee decreases the order of 1 T/ with the number of iterations and increases linearly with the mutual information among tokens.
Looking ahead, our analysis suggests that the sampling error primarily stems from the discrepancy between the true data distribution and the modeled product distribution. This observation motivates future studies to explore low-dimensional structures low-order Markov properties in the text data, which may help reduce this discrepancy and thereby decrease the sampling error. Moreover, establishing comprehensive end-to-end performance guarantees that account for both the mask training phase and the sampling phase represents an important direction for further research. Finally, while current focus is masked diffusion models, extending these insights to other types of discrete diffusion models for language modeling is compelling avenue for future investigation.
Acknowledgments and Disclosure of Funding
G. Li is supported in part by the Chinese University of Hong Kong Direct Grant for Research and the Hong Kong Research Grants Council ECS 2191363. C. Cai is supported in part by the NSF grant DMS-255 251-33.
10

---

References
Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and Van Den Berg, R. (2021). Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17993.
Benton, J., De Bortoli, V., Doucet, A., and Deligiannidis, G. (2023). Nearly d-linear convergence bounds for diffusion models via stochastic localization. arXiv preprint arXiv:2308. 03686.
Block, A., Mrouch, Y., and Rakhlin, A. (2020). Generative modeling with denoising auto-encoders and langevin sampling. arXiv preprint arXiv:2002.00107.
Brown, P. F., Della Pietra, J., Desouza, P. V., Lai, J. C., and Mercer, R. L. (1992). Class-based n-gram models of natural language. Computational linguistics, 18(4):467-40..
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P. Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
Cai, C. and Li, G. (2025). Minimax optimality of the probability flow ode for diffusion models. arXiv preprint wrXiv:2503.09580
Campbell, A., Benton, J., De Bortoli, V., Rainforth, T., Deligiannidis, G., and Doucet, A. (2022). A continuous time framework for discrete denoising models. Advances Neural Information Processing Systems, 35:28266-28279.
Campbell, A., Yim, J., Barzilay, R., Rainforth, T., and Jaakkola, T. (2024). Generative flows discrete state-spaces: Enabling multimodal flows with applications to protein co-design. arXiv preprint ar 2xIv:2402.044997
Chen, H., Lee, H., and Lu, (2023a). Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pages
PMLR.
Chen, H. and Ying, I. (2024). Convergence analysis of discrete diffusion model: Exact implementa- tion through uniformization. arXiv preprint 0rXiv:2402.08095.
Chen, M., Huang, K., Zhao, T. and Wang, M. (2023b). Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning, pages 4672-4712 PMIR.
Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang. A. R. (2022a). Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209.11 11215.
Chen, S., Kontonis, V., and Shah, K. (2024). Learning general gaussian mixtures with efficient score matching. arXiv preprint 0rXiv:2404.1889)
Chen, T., Zhang, R., and Hinton, G. (2022b). Analog bits: Generating discrete data using diffusion models with self-conditioning. arXiv preprint arXiv:2208.04200
De Bortoli, V., Thornton, J., Heng, J., and Doucet, A. (2021). Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34:1 14:17695-177
Deschenaux, and Gulcehre, C. (2024). Beyond autoregression: Fast 1lms via self-distillation through time. arXiv preprint arXiv:2410.21035
Dieleman, S., Sartran, I.., Roshannai, A., Savinov, N., Ganin, Y., Richemond, P. H., Doucet, A., Strudel, R., Dyer, C., Durkan, C., et al. (2022), Continuous diffusion for categorical data, arXiv preprint arXiv:2211.1508:
Dou, Z.,, Kotekal, S., Xu, 7.,, and Zhou, H. (2024). From optimal score matching to optimal sampling. arXiv preprint arXiv:2409.07033

---

Feng, G., Geng, Y. Guan, J., Wu, W. Wang, L., and He, D. (2025). Theoretical benefit and limitation of diffusion language model. arXiv preprint arX1v:2502.09622.
Gatmiry, K., Kelner, J., and Lee, H. (2024). Learning mixtures gaussians using diffusion models. arXiv preprini arXiv:2404. 18869.
Gong, S., Agarwal, S., Zhang, Y. Ye, J., Zheng, L., Li, M., An, C., Zhao, P., Bi, W. Han, J., et al. (2024). Scaling diffusion language models via adaptation from autoregressive models. arXiv preprint arXiv:2410. 17891.
Guirajani, I. and Hashimoto, T. B. (2023). Likelihood-based diffusion language models. Advances in Neural Information Processing Systems, 36: 16933-6616
Han, X., Kumar, S., and Tsvetkov, Y. (2022). Ssd-Im: Semi-autoregressive simplex-based diffusion language model for text generation and modular control. arXiv preprint arXiv:2210.17432.
Hayakawa, S., Takida, Y.. Imaizumi, M., Wakaki, H., and Mitsufuji, Y. (2024). Distillation of discrete diffusion through dimensional correlations. arXiv preprint arXiv:2410.08709,
He, Z., Sun, T., Wang, K., Huang, X., and Qiu, X. (2022). Diffusionbert: Improving generative masked language models with diffusion models. arXiv preprint arXiv:2211.15029.
Ho, J., Jain, A., and Abbeel, P. (2020). Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-688 6851.
Hoogeboom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. (2021). Argmax flows and multino-
mial diffusion: Towards aoneautoreeressvve language models. arXiv preprint arXiv:2102.05379
Lee, H., Lu, J., and Tan, (2022). Convergence for score- based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 15:22870-228822
Lee, H., Lu, J., and Tan, Y. (2023). Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946-985. PMLR.
Li, G. and Cai, C. (2024). Provable acceleration for diffusion models under minimal assumptions. arXiv preprint arXiv:2410.23285.
Li, G., Cai, C., and Wei, Y. (2025). Dimension-free convergence of diffusion models for approximate gaussian mixtures. arXiv preprint arXiv:2504.05300
Li, G., Wei, Y., Chi, Y., and Chen, Y. (2024). A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprint arXiv:2408.023320
Li, G. and Yan, Y. (2024). (d/T)) convergence theory for diffusion probabilistic models under minimal assumptions. arXiv preprint arX.v:2409.18959.
Li, X., Thickstun, J., Gulrajani, I., Liang, P. S., and Hashimoto, T. B. (2022). Diffusion-Im Im improves controllable text generation. Advances in neural information processing systems, 35:4328 43443,
Lou, A., Meng, C., and Ermon, S. (2023). Discrete diffusion modeling by estimating the ratios of the data distribution. arXiv preprint arXiv:2310. 16..34431..6634.
Lovelace, J., Kishore, V., Wan, C., Shekhtman, E.,, and Weinberger, K. Q. (2023). Latent diffusion for language generation. Advances in Neural Information Processing Systems, 36:56998-5707 57025.
Meng, C., Choi, K., Song, J., and Ermon, S. (2022). Concrete score matching: Generalized score matching for discrete data. Advances Neural Information Processing Systems, 35:34532-3455
Nie, S., Zhu, F., You, 2., Zhang, X., Ou, J., Hu, J., Zhou, J., Lin, Y., Wen, J.-R., and Li, C. (2025). Large language diffusion models. arXiv preprint 299999......
Oko, K., Akiyama, S., and Suzuki, T. (2023). Diffusion models are minimax optimal distribution estimators. In International Conference Machine Learning, pages 26517-26588 PMLR
12

---

Pope, R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J.. Heek, J., Xiao, K., Agrawal, S., and Dean, J. (2023). Efficiently scaling transformer inference. Proceedings of machine learning and systems, 5:606-624.
Radford, A., Narasimhan, K., Salimans, T., Sutskever, I,, et al. (2018). Improving language under- standing by generative pre-training
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. (2019). Language models unsupervised multitask learners. OpenAl blog, 1(8):9.
Sahoo. S., Arriola, M.. Schiff, Y., Gokaslan, A., Marroquin, E., Chiu, J., Rush, A., and Kuleshov, (2024). Simple and effective masked diffusion language models. Advances in Neural Information Processing Systems, 37:130136-13018
Shi, J., Han, K., Wang, Z., Doucet, A., and Titsias, M. (2024). Simplified and generalized masked diffusion for discrete data. Advances in neural information processing systems, 37: 17:100331-103167
Sohl- Sohh-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015). Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256-2265, pmlr.
Song, J., Meng, C., and Ermon, S. (2020). Denoising diffusion implicit models. arXivv preprini arXiv:2010.02502.
Song, Y. and Ermon, S. (2019). Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32.
Strudel, R., Tallec, C., Altché, F., Du, Y., Ganin, Y., Mensch, A., Grathwohl, W., Savinov, N., Dieleman, S., Sifre, L.,, et al. (2022). Self-conditioned embedding diffusion for text generation. arXiv preprint arXiv:221..04236
Sun, H., Yu, L., Dai, B., Schuurmans, D., and Dai, H. (2022). Score-based continuous-timg time discrete diffusion models. arXiv preprint arXiv:
Wibisono, A., Wu, Y., and Yang, K. Y. (2024). Optimal score estimation via empirical bayes smoothing. arXiv preprint 240
Ye, J., Zheng, Z., Bao, Y., Qian, L., and Gu, Q. (2023). Diffusion language models can perform many tasks with scaling and instruction-finetun finetuning. arXiv preprint arXiv:2308.1222
Yu, R., Li, Q., and Wang, X. (2025). Discrete diffusion in large language and multimodal models: survey, arXiv preprint arXiv:2506.135: 13759.
Zhang. K., Yin, H., Liang. F., and Liu, J. (2024). Minimax optimality of score-based diffusion models: Beyond the density lower bound assumptions. arXiv preprint 15X0v.2402.15602.
13

---

[7], let A Proof of Lemmal 1
Before proving the inequality observations.
19 we first introduce some notation and make few preliminary
Recall that X o W E
|X| denote the sub-vector of X indexed by set W. For simplicity of presentation, for any W C [7]. denote by
p(- X o W) = PXol (. Xo o W)
the conditional distribution of Xo given the partial tokens Xoo W. Moreover, we define the associated product distribution over X as
(. KooW = II ps( X) with pe(- XooW)= = P [xoo XooW), i i [4].
In word, P.(.] Xy W) denotes the conditional distribution the i-th coordinate given the partial tokens Xg W and the product distribution p Xo W) treats all coordinates as conditionally independent.
Next, recall that for any mask schedule M = (M,...., Mr), we denote W. == Mf and Dr = W,-1 W,. Since (D,) forms a partition of [T.], we know from the chain rule that given a mask schedule M, the distribution of Xo can be factorized as
T
PX.IM (Xo M) = IX D. X W.).
(21)
1=1
Meanwhile, recall that the "ideal" sampling procedure yields that Py | m)
IT (an de so o wx) and that the minimizer pt of coincides with ps(: X W). Thus, given the mask sequence M, the distribution of the auxiliary output Y of (14) can be expressed as
T
Pvg (X M) = II 8 (Xo D, Xo W.).
(22)
t=1
Putting the above observations together implies given mask sequence M, the KL divergence between the data Xo and the auxiliary output Yú can be decomposed as sum of KL divergences between the true conditionals and their product-form counterparts at each sampling step:
T
Eys [KL(px. PYG]N)]]
Σ
EM KL(p(Xo D₁ Xo Wt) p o D. Xo o Wi))
(23)
With the above preparation in place, we are now ready to prove the inequality (9)). In light of the definitions of E( (smmax) and e e({s;)) in (18). it suffices study the KL divergence term the right-hand side of (23 for each E [T].
To this end, let us fix an arbitrary mask size schedule {st]T with max = Smax and consider a mask set sequence M = (M1...., My)) such that [M, \ M,-1l = 8t. We construct an intermediate mask schedule whose maximum mask size equals [smax/2]] 27. Specifically. for each
Wr-1/2 be a random set such that We S W,-1/2 S. Wi-1 and W,-1/2 \ We is a random subset of Dj = W W. with size [s./]]. For notional convenience, we define the following two sets:
D,,- Wi-1/2 \ W.
(first set, size [st/2])
Dr.+ W.1 (W-1122
(second set, size [sr/2])
The key insight that revealing D, Dr,- - U Dr,+ in two stages creates dependency structure that can exploit. Conditioned on M m. express each KL divergence the hight-hand-side
14

---

of 23 as follows:
kL(p(Xo o o wy) | (Xo d Xo o w.))
KL(p(Xo o d Xo wilp o de, Xo 1/21
|| p 1Xo - Xo o wilp (Xo o 1o oow)
(
(L((ooo d Xo o wi) || P 0 (Xo o de Xo w()
Bxood,,- (KL d.+ Xo o 1
p (Xo a de,t Xo wx)) X wi]
(m1)
KL (L o de, Xo wi)
p (Xo o d,,
X6 o
Exoode. (p o d,,t
Xo o 1
(Xo o de,t Xo u, w2-1/2)) Xo wi
Σ 1(x!"; No d 1x o w,).
(24)
+
Here, (i) holds as D, Dt.- Dr.+ and W,-1/2 W. Dr,-; (ii) applies the chain rule of the KL divergence; (iii) makes use of the following identity:
/ p(Xo d Xo o wi) p(Xo o de,+ Xo o 1/21 log
(Xo o d,,t
| o w1-122
po o dr,+
Xo o w))
i
Σ
p(Xo o No wx) Xo 11-1/2) log /
pa (X
Xo o w2-1122
De (X1))
(3)
Xo we)
+
(iI
Σ
p(Xo o de. X w)) (x! Xo o w. 1/2)
p (X
Xo w01122
pdd (x (1)
No a wx)
Xo o dr,,, w;) log pd (x Xo o d Xo wy)
(iii
Σ
p(Xo o de,- (x
px
(i)
| o w.)
iEde,
Σ
1 Xo de, o))
iEds,
where (i) follows from our construction of the product distribution p0; (ii) is true as the marginal distributions of p(X, o d Xo 12-1/2) and p (Xo o de,t Xo o 1/21122 are identical; (iii) holds because W. n Dr,- Ø and W, U Dr,- = W,
Notice that in (44,, the last term captures the dependency between the sets of tokens while the first two terms correspond to a sampling process with maximum mask size f2ax
Putting and
24 together with the definition of {(5max) in (18). we can derive
6(8mmxx S em[[mmax/2)
(2) Ew
Σ
Σ
I(X!0; Xoo Dr,- 10-1Xp
X Wo)W))
WT)
(25)
t=1
iED..
15

---

For the mutual information term, taking the expectation with respect to W = (W1.... Wr) (or equivalently M (M....., Mr)) and summing over l...... yields
T
Ew
Σ
Σ
T(X Xo Dr.- Xo ()oW)))
1=1
(
81
Ewa Ew..
[T([] Xo Dr,- 1X W.)
Ew, W. [1XX0'; Dr.- Xo W:) l 1/-1/2]
T,
2m1
max
Ew
xo Dr,- Xoo 1 liglliige i W1/2
2L
(ii)
$ mmax
1xx1";x(""))
(26)
2L
where (i) is true because Dr,t is a random subset W t-1/2 with De.+1= = 1 (ii) arises from the following bound:
Ew
Σ t=1
1(x (1) Xo Dt,- Xo WT) i W1/3 s 1(x :x! xx--)
due Wi-1 W, = D. Dr,- D..t and the chain rule of mutual information that 1(X; Y 2) + [Xx; 2) = ((;YY 2) for any X,Y, 2 px,Y.z.
Combining 25 and (26 establishes the recursive inequality 19)) thereby completing the proof of Theorem
B Proof of Theorem 2
In this section, we prove Theorem Our strategy is to establish the lower bound (13) first, then sharpen the factor the upper bound
to obtain the refined upper bound [12).
B.1 Lower bound analysis
We begin by reminding the readers the sampling process introduced in Section Recall that Mj denotes the set of masked positions step and that define W, [Z.] M, the set of unmasked positions. Equivalently, the sampling process creates decreasing sequence of random sets [L] Wo 2 Wi 2 newly revealed positions. The sampler starts with a fully masked sequence Yr = (M...., M) and iteratively reveals tokens by going backwards through time / T, T I,..., 1. At each step the sampler predicts 8t tokens located in the unmask set W.- W.
Wr Ø, where each W, is obtained from W,-1 by removing s
Step 1: Auxiliary sampling process. To establish the lower bound, let consider specific mask size schedule { For some smax > L, each s; is independently chosen from {smax Smax/22 /2 uniformly at random. Without loss of generality, we assume that L = E St, which implies that 2L
T = (1 o(1)) 38max
To analyze the sampling process with the chosen mask size schedule, we reorganize the original T-step sampling process into a K-step process where K := 2L/Smax- Smax- Let [L] = Wo Wi 2 2 Wx = Ø be a decreasing unmask sets where each We is a random subset of W such that [Wa-1 \ Wil mmax/2 In this reorganized view, each "super-step" in the K-step process corresponds to revealing 8max/ positions. The correspondence between original steps and super- steps as follows:
When 8; 8max/2 /2 in the original process: the auxiliary sampler takes one super-step (k + k- - 1).
16

---

When = Smax in the original process: the auxiliary sampler takes two super-steps at once (k k 2).
Since each st is chosen uniformly from (Smax, 15mmx/2),, each type of transition occurs with proba- bility 1/2.
The key insight comes from analyzing two-super-step transitions (k - k - 2), which occur when
8, = Smax. Consider the case where the sampling process transitions from &s to k 2, which happens with probability at least 1/4. For such transitions, define:
D& Wk-2 \ WK.
(all newly revealed positions)
DR,- = WK-1 WA.
(first batch, size 8max/ (2) (second batch, size Smax/
D Wk-2 WK-1-
Using the non-negativity of the KL divergence and repeating the argument for (26). we obtain the following lower bound:
EM [px,,x, || PY][M]]
Strain = Ea
[pL
PYg pY)(M))
R
Σ
1(x)0; Xoo DR.- 1 Wis)
VEDE.+
8max
[(x(") Xo DR,- Wkk 1 W1
E
8L
Smax
E :o0 W1) ( i Wi].
(27)
8L
Step 2: Hierarchical decomposition. In what follows, we will develop a stronger lower bound through a more sophisticated recursive analysis, which leads to the desired result ([3). To this end, for any super-step l with two-step transition, applying the decomposition in (44) and the non -egaaiivv of the KI. divergence, we can derive: conditioned on W w.
(L( d Xo o wK) |l 1d (Xo ds X, wk))
Σ 1(x)"); Xo dr,- | Xo wk)
iEdx.+
+ EXoods. (pL de,+ Xo wx-1) || 1 (Xo dx,+ Xo wx-
(28)
Consider the case where the sampler uses W2 and Wo consecutively. The above inequality (88 tells us that
Ew [KL D2 Xo W2) 10 (Xo D2 Xo W2))]
Σ I(x! (t) Xo D2,- Xo W2)
Ew
De
+ EW.,xoD,,- [KL D2.+ Xo c W1) (Xo o D2.t Xo Wi))]-
By construction, one has [W2] I, Smax Wil Smax 2, and DD.-1 = ID2,+1 = Smaxx/ 2.
To leverage this structure, we define a hierarchical family of random sets: for any E [L]. let W!--) .... C (((1)) .... C [7.] be sequence of increasing random sets such that i & W and ( I. 8max 2- for all 0 < j S log, 8max. Consequently, find that
Ew [KL (p(Xo o D2 Xo W2) || 8 (Xo D2
Xo a W2))]
Smax
W! [[X (1) Xo w((-)) X₂ o W
2
+
[KL(p(Xo D2.+ Xo o W1) || 1 D2.t Xo o W1))
17

---

where the inequality holds as W c W and (W
1 - 122
Smax/2. Applying the above relationship recursively across all hicrarchical levels and invoking the decomposition 23 yields
loga 8max
EM [KL PY; m)] 2
mmax
2 2- W W [T(X]]
Xx W Xo W W/-1)
(29)
Now we simplify the hierarchical sum on the right-hand side of (29). Recall that for any E [L] and
j 2 O, we define w. (:(-)) S [L] to be a random set such that i & W and [ 1 || L - smax 2
Combining {W 1j21 with {W) i) 1221. we can derive
logg Smax
2 2 W W ((x)
B
10) Xo W w/ Xo Wo
long Smas
2 2 W w [(x)0) Xo :) 1(x0 (1) Xu w/
==1
log Seawor
loga #max
(
2 2E
E w
[[(x()) Xo o wr(-1)
2 2-6-1) 1) w [I(x] Xo w/-
logg
2 E (r(-0)
[[(x()) Xo o w/-0)}]
= E
ww--
[T(x(0;; Xo w
2
2
[[(x!0) :o w/ smase]]
E
((-9
Smax
1o02 Amau
logg Smax
2 EE
[[(x6') Xo lo )
Bwg-o [I(x)() No wy
where (i) uses the chain rule of the mutual information; (ii) holds as (-1)) and ( have the same marginal distribution. Substituting the above bound into 29 we obtain
loga 9max
EM [KL(xx PYg M)] 2
Smax
2 B [I(X)"; Xo w/ :oo
-Ewg-o [I(X]";
w6-3)]]
(30)
Step 3: Combining bounds.
Finally, it is not hard to deduce from the basic bound 27 that
EM [KL(px. PYg1a))
Smax Ew [ Xo w)-"))].
(31)
Therefore, combining 300 and 31 with the training error bound 17 yields the desired lower bound (33)
B.2 Upper bound analysis
For the refined upper bound (12 we will use the introduced random sets {w Jo2ı to improve the analysis in step (ii) of (6). Since Wi-1 \ W, = D. = Dr,- Dr,t, one can use the chain rule of the mutual information to derive
T
Ew
Σ
Σ IED
1xx Xo D._ Xo Wi) Wi)
<
8max Σ
E w!
[(xx(")
Xo o W/ w)
2L
(32)
18

---

where we recall W/ S [L. to be a random set such that i W( and | = L. max Hence, applying the same recursive argument as for (29). this improvement allows us to obtain the refined inductive relationship (9) follows. For any 0 S j < log2 Smaxi
E(Smax2 S (smaxx ()+ + 8max 2
E Xo
Xo
(33)
21
Applying this inequality recursively gives
loga Smax
(Smax) =1( +
Smax
2
Σ
(34)
2L
Therefore, the desired refined upper bound 12 immediately follows from the fact that e(1) 0.
19

---

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: Main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
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 or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work and future directions are discussed properly.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Justification:
All assumptions and complete (and correct) proof are provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
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 of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the information needed to reproduce the main experimental results disclosed.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer 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 is a specific model and empirical evaluation, it may be necessary to either make 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 can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
21

---

Answer: [Yes]
Justification:
The synthetic data generation is described the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.cc/pullc//uuuii wwwticccguie//eeeeeeeeeii CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All the details necessary to understand the results are specified.
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 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: [Yes]
Justification: The results are accompanied by error bars suitably and correctly defined.
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, statistical significance tests, at least for the experiments that support 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, 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.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
22

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful 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 in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The numerical experiments on the synthetic data are not computationally intensive.
Guidelines:
The answer NA means that the paper does not 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 as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:/::///eups/eeeeeeeeeeer http:///..c.c...cccciceccceeeeea Eittes/
Answer: [Yes]
Justification:
This paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations 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:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does 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.
23

---

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 of 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 paper poses such risks.
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
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?
Question:
Answer: [NA]
Justification: This paper does not 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.

---

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: This 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: This 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: This 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
25

---

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 in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
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.
26


Reviews:
[{"review_id": "Z3pHr25Cpl", "reviewer": "Reviewer_2wt9", "summary": "The paper sets out to prove an upper and lower bound on the error of the sampling distribution of a trained masked diffusion model relative to the true sequence distribution it is trained on. The authors bound the expected KL divergence (over choices of mask sets at sampling) above by the training error as well as the mutual information of each token and the rest of the sequence with a 1/L prefactor, where L is the length of the sequence. The authors then refine the bound and show that this 1/L prefactor holds in both the upper and lower bounds with a similar weighted mutual information sum of each token and chunks of the remaining sequence, showing the sampling error bound is tight.", "questions": "- Are there insights from your theoretical analysis that could illuminate if it is possible to deliberately choose masking sets (or an unmasking ordering based on mutual information) at sampling time to reduce the sampling error from the true distribution?", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The authors examine a very fundamental theoretical question regarding how far the sampling distribution of masked diffusion models is from the true sequence distribution, and offer a comprehensive answer.\n\n- The authors identify that beyond training error, there is a fundamental error stemming from the product posterior assumption.\n\n- The exposition is extremely well done.\n\nWeaknesses:\n- The proofs in the appendix could be made even more clear with a simple \"English\" summary of some of the equations. For example, in (22), some brief sentence right after like \"We break down the the KL divergence between the \"ideal\" sampling distribution and the sequence distribution into a sum of expected KL divergences between the true and productized marginals at one \"unmasking\" sampling step\" (or something along these lines). Essentially reminding the reader how $D_t$ and similar variables are defined w.r.t. the unmasking sampling process.", "was_revised": true, "final_justification": "- The paper is strong and insightful towards understanding theoretical limitations of sampling with masked diffusion models. Responses from the authors during rebuttals confirm the original positive impression.", "rebuttal": "We thank the reviewer for the careful reading and the constructive feedback.\n\n**Weakness:**\n- Thank you for the suggestions. We will add plain-language explanations in the proofs. For instance, we will add the suggested summary for the KL divergence in (22); we will discuss the intuition for the KL divergence decomposition in (23); we will include an explanation for the conditional mutual information in (24).  \nTo aid navigation, we will also (i) restate the sampling update (6) and the factorized predictor (4), and (ii) remind readers of the masking sets $W_t$ and $D_t$ throughout the proof.\n\n**Questions:**\n- We appreciate this thoughtful point. A practical implication of our theory is to unmask, at each iteration, the tokens whose conditional dependence on the rest of the sequence is weakest. Concretely, (24) shows that the per-step contribution to the total sampling error is the conditional mutual information between a newly revealed token and the remaining tokens. Hence, selecting positions with smaller conditional mutual information minimizes that contribution. Moreover, because $I(X;Y|Z)\\leq H(X|Z)$ for any random variables $X,Y,Z$, we can implement this strategy by ranking tokens by conditional entropy: at step $t$, use the learned mask predictor $\\hat{p}_i(\\cdot | Y_t)$ to estimate the conditional entropy of the token at position $i$. Unmasking the positions with the lowest conditional entropy provides a simple heuristic that approximates the mutual-information criterion without additional training or external estimates. We will add a remark on this point in the revised manuscript."}, {"review_id": "o4Qak36z3u", "reviewer": "Reviewer_hh8p", "summary": "Masked diffusion language models (DLMs) generate text by iteratively unmasking subsets of tokens in parallel, potentially sampling much faster than autoregressive transformers. Despite strong empirical results, there has been little theory quantifying how many unmasking iterations $T$ are needed to approach the true data distribution. This paper fills that gap by analyzing the sampling phase—assuming an already-trained, sufficiently accurate mask-prediction network—and derives information-theoretic bounds on the KL divergence between model output and data. \n\nIn the main theorems, the authors proved an explicit upper bound on the KL divergence between the model output and the data distribution that decays as $O(1/T)$ with the number of unmasking iterations $T$ (for balanced schedules) and depends linearly on a sequence-level mutual-information term. This bound is also shown to be unimprovable under the paper’s oracle-predictor assumption.", "questions": "Please refer to the Weaknesses Section above.", "limitations": "There is no negative societal impact of their work,", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper makes a compelling theoretical contribution by establishing the first rigorous relationship between the number of unmasking iterations and generation quality for masked-diffusion language models.  It offers a tight information-theoretic analysis with matching upper- and lower-bound rates, while scaling gracefully to schedules that update many tokens in parallel.  A particularly valuable aspect is its identification of sequence-level mutual information as the key statistic governing convergence, which provides an intuitive bridge between linguistic dependence and iteration complexity.  The authors further separate sampling-phase error from training-phase error, clarifying where future architectural or data improvements are most beneficial.  Beyond its theory, the manuscript is clearly written, logically structured, and supported by a thorough discussion of prior work, making the results accessible to a broad audience.\n\nWeaknesses and Questions:\n1. For the oracle predictor assumption, the main bound becomes vacuous when $\\varepsilon_{\\text{train}}$ dominates; no scaling law links this term to model capacity or data. It would be better to add some discussions on the $\\varepsilon_{\\text{train}}$ term as well as its connection with model capacity. \n2. Is there any synthetic or real experiments that the authors can provide to confirm the predicted inverse-linear curve or the practical relevance of the mutual-information coefficient? \n3. For the potential gap in KL decomposition, I wonder whether there is a $\\varepsilon_{\\text{train}}$ term omitted at every step when the predictors are imperfect, which will loosen the final bound in this case. I think the authors should add a remark after Lemma 1, or make the Lemma 1 more robust. \n4. I wonder if the self-conditioning breaks the independence assumption used in Lemma 1, and how would that affect the bound?", "was_revised": true, "final_justification": "The authors added a synthetic numerical experiment in the updated manuscript to validate their theory, which also answered most of my questions on experiments.", "rebuttal": "We appreciate the reviewer’s thoughtful comments and careful evaluation.\n\n- Thank you for the suggestion. We agree that it would be beneficial to add an explicit remark on $\\varepsilon_{train}$, which reads as follows. Our theory shows that the overall error in KL divergence exhibits a two-stage behavior: when the number of iterations $T<C_1\\sum_i I(X^{(i)};X^{(-i)})/\\varepsilon_{train}$ where $C_1$ is the constant from Corollary 1, the sampling error term dominates and the overall error decays proportionally to $1/T$; once $T$ exceeds this threshold, the error plateaus and becomes almost insensitive to further increases in $T$.\nDeriving a sharp scaling law for $\\varepsilon_{\\text{train}}$ itself would require new techniques to analyze the model capacity of transformers and the sample complexity of their nonconvex training, which is currently unavailable and beyond the scope of the present work.\n\n- Thank you for the suggestion. We add a synthetic numerical experiment in the revised manuscript to validate our theory. \n  - *Model.* we use a $K$-state Potts chain of length $L$ with coupling $J$ to model the distribution of text $X=(X^{(1)},\\dots,X^{(L)})$. Concretely, $X^{(1)}\\sim\\text{Unif}([K])$ and $$\\mathbb P\\\\{X^{(i)}=y|X^{(i-1)}=x\\\\}=\\exp(J1\\\\{x=y\\\\})/(\\exp(J)+K-1), \\quad \\forall x,y\\in[K].$$ This construction allows us to compute explicitly the mutual information, the optimal mask predictor $p^\\star(\\cdot | X_t)$, and the densities of $p_{X_0}$ and $p_{Y_0|M}$. \n  - *Mask predictor.* We use the explicitly computable optimal mask predictor $p^\\star(\\cdot | X_t)$ to run the sampling process.\n  - *Sampling error.* Given the explicit densities of $p_{X_0}$ and $p_{Y_0|M}$, the expectation in the KL divergence, taken over both the mask schedule $M$ and the data distribution $p_{X_0}$, is approximated using Monte Carlo simulations. \n\n  - *KL divergence vs. mutual information.* For fixed $T=10$, $K=10$ and $L=100$, KL divergence vs. mutual information is summarized in the following table:\n\n    |   J   | Mutual Information |   KL   |\n    |:-----:|:------------------:|-------:|\n    | 0.000 |     4.80e-13       | 0.000  |\n    | 0.333 |     1.18e+00       | 0.051  |\n    | 0.667 |     5.53e+00       | 0.309  |\n    | 1.000 |     1.43e+01       | 0.748  |\n    | 1.333 |     2.86e+01       | 1.302  |\n  \n    One can verify that the KL divergence error increases linearly with the mutual information. \n\n  - *KL divergence vs. number of iterations $T$.* With a balanced mask schedule, $K=10$, $L=100$ and $J=2$, $\\log KL$ vs. $\\log T$ is summarized in the following table. \n \n    | $T$ |   KL   | $\\log$ KL | $\\log T$ |\n    |-----|--------|-----------|-----------|\n    | 2   | 18.70  | 2.928     | 0.693     |\n    | 4   | 8.85   | 2.180     | 1.386     |\n    | 5   | 7.24   | 1.980     | 1.609     |\n    | 10  | 3.10   | 1.130     | 2.303     |\n    | 20  | 1.49   | 0.395     | 2.996     |\n    | 25  | 1.16   | 0.151     | 3.219     |\n    | 50  | 0.44   | –0.818    | 3.912     |\n\n    One can verify that the slope is very close to -1, demonstrating that the KL divergence error scales proportionally to $1/T$.\n\n  - *Conclusions.* Therefore, these two results validate our established sampling convergence theory.\n\n  In addition, because the true data distribution is unknown in the real-world datasets, it is infeasible to compute the token-level mutual information or the KL divergence between the output and the data distribution. Hence, we restrict our numerical experiments to the synthetic data.\n\n- We appreciate this careful point. Lemma 1 is **not** ``missing” $\\varepsilon_{train}$: the term $\\varepsilon_{train}$ is fundamentally absent in Lemma 1 because this lemma analyzes the sampling error when the optimal mark predictor $p^\\star$ is used. Error due to imperfect training is aggregated into $\\varepsilon_{train}$ and handled in (17), which relates the distribution induced by the learned predictor $\\hat{p}$ to that induced by $p^\\star$. This separation decouples training from sampling, which allows Lemma 1 to focus on  $KL(p_{X_0}\\|p_{Y_0^\\star|M})$. We will add a remark after Lemma 1 to make this point clearer.\n\n- In the training stage, the mask predictor is parametrized such that tokens in the unmask set are predicted independently given the current context (see (4) and (5)). Therefore, the proof of Lemma 1 reflects this design: the gap between the factorized predictor and the true joint conditional over a block of tokens is controlled by conditional mutual information terms that precisely measure the statistical dependence among those tokens after conditioning on the revealed ones. This is why conditional mutual information naturally appears in the per-step error decomposition."}, {"review_id": "tsLFWJm9Be", "reviewer": "Reviewer_DvD9", "summary": "This paper analyzes both the upper and lower bounds of the sampling error in diffusion language models from an information-theoretic perspective. It demonstrates that, under the assumption of linear dependence on the mutual information, the fundamental limit for the convergence rate of the sampling error is $O(1/T)$.", "questions": "Q1: What is the rationale for assuming that the sampling error has a linear dependence on the mutual information? Could the authors provide further justification or discussion for this assumption?\n\nQ2: While the paper presents an analysis of sampling error convergence, could the authors offer any constructive suggestions on how to effectively reduce the sampling error or accelerate convergence for parallel sampling in diffusion language models?\n\nMinor 1: The description in the Abstract (Line 6) is inaccurate: it should state “theoretical understandings of discrete diffusion language models” instead of “diffusion models”.\n\nMinor 2: Why is reversal reasoning emphasized? This does not seem consistent with the nature of language generation, and I do not consider it an advantage.\n\nMinor 3: The claim at Line 68 “This assumption does not align with practical diffusion language models that mask a large fraction of tokens at each iteration” needs supporting citations.", "limitations": "See Weaknesses and Questions.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\nCompared with previous results on diffusion models under n-gram distributions (e.g., Feng et al., 2025), this work is more general and rigorous, as it applies to arbitrary data distributions and token dependencies. The theoretical guarantees remain valid even for higher-order structures with long-range dependencies, unlike prior methods whose guarantees become loose or invalid as n increases.\n\n## Weaknesses\nWhile the paper provides a rigorous theoretical analysis, all derivations assume that the mask predictor can be trained to near-optimality, but no experimental results are provided to support the theoretical conclusions. In addition, the theoretical lower bound may not hold under certain extreme mask schedules (see Lines 283–290).", "was_revised": true, "final_justification": "According to the rebuttal reply, I increased my rating by one point.", "rebuttal": "We appreciate the reviewer’s time and effort in providing helpful feedback.\n\n**Weakness:**\n- This is certainly a valuable point that needs more clarification. We do **not** assume a near-optimal mask predictor. Our analysis only requires access to a pre-trained mask predictor (of arbitrary quality) and provides an off-the-shelf framework for assessing the text generation quality of diffusion language models. We decouple the mask predictor training phase from the sample generation stage, showing that the final error in KL divergence can be decomposed into (i) a training error term $\\varepsilon_{train}$ that captures how far the learned predictor is from the optimal one, and (ii) a sampling error term incurred during the sample generation phase. The central contribution of this paper is to characterize the sampling error in terms of the iteration number and the statistical structure of the text distribution. Crucially, this sampling term is **independent** of the quality of the mask predictor. To make this point more precise and avoid misunderstanding, we will revise our statement about the pre-trained mask predictor from “We assume access to sufficiently accurate mask predictors” to “We assume access to some mask predictors”.\n- We add a synthetic numerical experiment in the revised manuscript to validate our theory. \n  - *Model.* we use a $K$-state Potts chain of length $L$ with coupling $J$ to model the distribution of text $X=(X^{(1)},\\dots,X^{(L)})$. Concretely, $X^{(1)}\\sim\\text{Unif}([K])$ and $$\\mathbb P\\\\{X^{(i)}=y|X^{(i-1)}=x\\\\}=\\exp(J1\\\\{x=y\\\\})/(\\exp(J)+K-1), \\quad \\forall x,y\\in[K].$$ This construction allows us to compute explicitly the mutual information, the optimal mask predictor $p^\\star(\\cdot | X_t)$, and the densities of $p_{X_0}$ and $p_{Y_0|M}$. \n  - *Mask predictor.* We use the explicitly computable optimal mask predictor $p^\\star(\\cdot | X_t)$ to run the sampling process.\n  - *Sampling error.* Given the explicit densities of $p_{X_0}$ and $p_{Y_0|M}$, the expectation in the KL divergence, taken over both the mask schedule $M$ and the data distribution $p_{X_0}$, is approximated using Monte Carlo simulations. \n\n  - *KL divergence vs. mutual information.* For fixed $T=10$, $K=10$ and $L=100$, KL divergence vs. mutual information is summarized in the following table:\n\n    |   J   | Mutual Information |   KL   |\n    |:-----:|:------------------:|-------:|\n    | 0.000 |     4.80e-13       | 0.000  |\n    | 0.333 |     1.18e+00       | 0.051  |\n    | 0.667 |     5.53e+00       | 0.309  |\n    | 1.000 |     1.43e+01       | 0.748  |\n    | 1.333 |     2.86e+01       | 1.302  |\n  \n    One can verify that the KL divergence error increases linearly with the mutual information. \n\n  - *KL divergence vs. number of iterations $T$.* With a balanced mask schedule, $K=10$, $L=100$ and $J=2$, $\\log KL$ vs. $\\log T$ is summarized in the following table. \n \n    | $T$ |   KL   | $\\log$ KL | $\\log T$ |\n    |-----|--------|-----------|-----------|\n    | 2   | 18.70  | 2.928     | 0.693     |\n    | 4   | 8.85   | 2.180     | 1.386     |\n    | 5   | 7.24   | 1.980     | 1.609     |\n    | 10  | 3.10   | 1.130     | 2.303     |\n    | 20  | 1.49   | 0.395     | 2.996     |\n    | 25  | 1.16   | 0.151     | 3.219     |\n    | 50  | 0.44   | –0.818    | 3.912     |\n\n    One can verify that the slope is very close to -1, demonstrating that the KL divergence error scales proportionally to $1/T$.\n\n  - *Conclusions.* Therefore, these two results validate our established sampling convergence theory.\n\n  In addition, because the true data distribution is unknown in the real-world datasets, it is infeasible to compute the token-level mutual information or the KL divergence between the output and the data distribution. Hence, we restrict our numerical experiments to the synthetic data.\n- Our lower bound targets the balanced mask schedules used in practice, where the number of unmasked tokens per iteration is of the same order. Admittedly, the bound can fail for deliberately unbalanced mask schedules---for instance, unmasking half the sequence in the first iteration and then proceeding token-by-token in the rest of iterations. Because balanced mask schedules are much more commonly employed in practice, we believe this exclusion does not compromise the practical insights of our results.\n\n**Questions:**\n- “The sampling error has a linear dependence on the mutual information” is the main result of this paper (upper bounds in Theorem 1 and Corollary 1, and lower bounds in Theorem 2), rather than an assumption.\n- Thank you for the suggestion. A practical implication of our theory is to unmask, at each iteration, the tokens whose conditional dependence on the rest of the sequence is weakest. Concretely, Eq. (24) shows that the per-step contribution to the total sampling error is the conditional mutual information between a newly revealed token and the remaining tokens. Hence, selecting positions with smaller conditional mutual information minimizes that contribution. Moreover, because $I(X;Y|Z)\\leq H(X|Z)$ for any random variables $X,Y,Z$, we can implement this strategy by ranking tokens by conditional entropy: at step $t$, use the learned mask predictor $\\hat{p}_i(\\cdot | Y_t)$ to estimate the conditional entropy of the token at position $i$. Unmasking the positions with the lowest conditional entropy provides a simple heuristic that approximates the mutual-information criterion without additional training or external estimates. We will add a remark on this point in the revised manuscript.\n- The original “diffusion model approaches” means using diffusion models for language models. We have changed it to “diffusion language models” to avoid this potential misunderstanding.\n- Reversal reasoning is one key practical motivation of diffusion language models (see e.g., [1]). This task spans many real-world scenarios, including cloze/fill-in-the-blank problems, and span infilling. For example, literature examples often ask students to recover the first half of a poem from the second half; language exams routinely require predicting a verb given its object.\n- Thank you for the suggestion. We have added the reference [2] to show that practical diffusion language models indeed mask more than one token in average at each iteration.\n\n[1] Nie, S., Zhu, F., You, Z., Zhang, X., Ou, J., Hu, J., Zhou, J., Lin, Y., Wen, J.-R., and Li, C. (2025).\nLarge language diffusion models. arXiv preprint arXiv:2502.09992.\n\n[2] Yu, R., Li, Q., & Wang, X. (2025). Discrete Diffusion in Large Language and Multimodal Models: A Survey. arXiv preprint arXiv:2506.13759."}, {"review_id": "lf1Yp3bT7o", "reviewer": "Reviewer_zPJj", "summary": "This paper investigates the theoretical understanding of generative *diffusion language models*. Unlike conventional autoregressive models, diffusion models allow parallel token sampling, which leads to faster generation and eliminates left-to-right generation constraints. The main results of the paper are convergences guarantees from an information-theoretic perspective: the sampling error, measured by KL divergence, decays inversely with the number of iterations and scales linearly with the mutual information between tokens in the target text sequence.  The paper establishes matching upper and lower bounds, which provides the tightness of their convergence analysis. These findings offer interesting theoretical insights into the practical effectiveness and robustness of diffusion language models, highlighting how the statistical dependencies in language data influence the efficiency of parallel diffusion sampling.", "questions": "My only question is about the generality of this statement:\n\n*\"Given accurate mask predictors, can we establish the convergence guarantees of diffusion language models\nfor general sampling procedures and data distribution?\"*\n\nIn particular regarding the  *general sampling procedures and data distributions.*\n\nMinor typos:\n\n  - l6: diffusion models --> diffusion language models\n  - l42: serves --> serve", "limitations": "Limitations are correctly discussed.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n - **Interesting theoretical contributions**: (As far as I know) the paper offers significant theoretical contributions by developing convergence guarantees for diffusion language models using KL divergence and IT tools. It quantifies the sampling error using KL divergence, showing an inverse decay with the number of steps  and a linear relationship with the mutual information between tokens in the target text sequence.\n\n- **Tight Bounds**: The establishment of matching upper and lower bounds (up to constant factors) demonstrates the tightness and optimality of te convergence analysis, suggesting that the $1/T$ decay and mutual information dependence are fundamental limits.\n\n- **Practical insights / intuition**: The results offer new insights into why diffusion language models are effective in practice.\n\n- **Comparison with other relevant work:** The paper contrasts its findings with existing work, such as  the very recent work by Feng et al. 2025, showing a sharper and more general guarantee for arbitrary distributions, overcoming limitations of previous bounds that degrade for high-order n-gram models.\n\n**Weaknesses:**\n\nI don't see any major weakness in this work, though I recognize that I'm not able to correctly asses the technical proofs since this work is out of my domain of expertise. One point that could may be better discussed is the statement:\n\n*\"Given accurate mask predictors, can we establish the convergence guarantees of diffusion language models\nfor general sampling procedures and data distribution?\"*\n\n**General sampling procedures and data distributions.** The paper (as always) does make some assumptions about the sampling procedure and the data distribution, maybe this should be contextualized in the introduction. It would be nice to connect the assumptions to what we may observe on real data (there's some discussion about this at the very end).", "was_revised": true, "final_justification": "This paper presents an interesting theoretical contribution by establishing convergence guarantees for diffusion language models using KL divergence and information-theoretic tools. The authors demonstrate the tightness and optimality of their analysis by providing matching upper and lower bounds, which reveal a fundamental relationship between sampling error, the number of diffusion steps, and the mutual information between tokens. While the theoretical proofs are complex, the work appears to be solid with no major weaknesses. The authors could, however, improve clarity by contextualizing the assumptions about general sampling procedures and data distributions earlier in the paper. Given its strong theoretical foundation and valuable contributions, in my opinion, the paper is a strong candidate for acceptance.", "rebuttal": "We are thankful for the reviewer’s valuable feedback and close attention to the manuscript.\n\n- For the question regarding generality, this indeed requires more clarification. First, our theory applies to any target text distributions---we impose no distributional assumptions whatsoever---so we refer to ``general data distributions.’’ Second, we analyze the **standard** sampling procedure of diffusion language models without introducing additional constraints or restrictions for analysis (e.g., we allow arbitrary mask sizes per iteration). Hence, we describe our results as covering “general sampling procedures” of diffusion language models. \n\n- Thank you for catching the typos. We have fixed them."}, {"review_id": "ondnJwP4b1", "reviewer": "Reviewer_v9hs", "summary": "This manuscript proves convergence guarantees for sampling from discrete diffusion language models.  The authors prove that (i) the error decays as O(1/T) after T denoising steps and (ii) that the constant factor depends on the mutual information between tokens in the target sequence. Finally, a matching lower bound shows that this rate is tight. The results assume access to accurate mask predictors, consistent with prior work that theoretically analyze the sampling process of continuous diffusion models.", "questions": "1. Can the bound be tightened further for language distributions with known structure (e.g., low-order Markov texts)? Have the authors thought about interesting such distributions?\n2. Have the authors studied the impact of changing the sampling algorithm to the bound? For example, what would be the impact of entropy-based sampling, where positions with low uncertainty (as predicted by the denoiser), are more likely to be sampled first?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- **Well-written**: in general, the paper is well organized and written. The exposition in section 4 is well organized and relatively easy to follow. I appreciate that not all proofs are relegated to the appendix. Additionally, the notation preliminaries are complete and consistent with my expectations.\n- **Novel theoretical contribution**: Theorem 1 (Eq. 8) provides an O(1/T) upper bound on the KL error that depends on the average mutual information between a token and the rest of the sequence. Importantly, the authors prove a matching lower bound, showing that their result is tight.\n- **Significant improvements over prior work**: authors discuss the prior work of Feng et al. [6], and rightfully argue that their bound is more aligned with realistic values of L (sequence length) and n (vocabulary size).\n- **Well-structured preliminaries**: section 1.2 carefully sets notation and clarifies the training objective, lowering the barrier to entry for readers outside the discrete diffusion community.\n- **Sampling algorithm is accurate**: While some prior theoretical work might make unrealistic assumptions, this work assumes the true sampling algorithm of recent masked diffusion models such as MDLM [4].\n\n---\n## Weaknesses\n**No empirical validation**: While the work is theoretical, a small-scale simulation on a synthetic distribution would strengthen the submission.\n\n**Potentially large hidden constants**: Theorems quote unspecified \"absolute constants\" (C_1,C_2,C_3). The manuscript could be improved by including more details on what typical constants should be expected.\n\n**Contextualization**: To better contextualize this work, the authors should consider citing a few recent works, which would make some claims in the introduction more precise. Specifically, by default, contrary to what is stated on lines 46-48, **sampling from masked diffusion models is generally slower than AR models**, despite parallel generation quality. Indeed, KV caching [1] accelerates AR models significantly, but is not available for models with bidirectional attention. However, diffusion language models can be accelerated through distillation [2,3]. For a comparison of the speed of text diffusion models with AR models, see Figure 2 of the appendix of [4]. Additionally, regarding the capabilities of diffusion language models, citing [5] would be relevant.\n\n\n[1] Efficiently Scaling Transformer Inference, Pope et al.\n\n[2] Beyond Autoregression: Fast LLMs via Self-Distillation Through Time, Deschenaux and Gulcehre\n\n[3] Distillation of Discrete Diffusion through Dimensional Correlations, Hayakawa et al.\n\n[4] Simple and Effective Masked Diffusion Language Models, Sahoo et al.\n\n[5] Diffusion Language Models Can Perform Many Tasks with Scaling and Instruction-Finetuning, Ye et al.\n\n[6] Theoretical Benefit and Limitation of Diffusion Language Model, Feng et al.", "was_revised": true, "final_justification": "The authors have addressed my questions and even included small-scale experiments, despite being primarily a theoretical contribution. I think this paper makes a valuable contribution to the literature, by analyzing a realistic model of discrete diffusion models. Hence, I think the paper should be accepted", "rebuttal": "We thank the reviewer for the insightful comments and thorough assessment of our work.\n\n**Weakness:**\n- Thank you for the suggestion. We add a synthetic numerical experiment in the revised manuscript to validate our theory. \n  - *Model.* we use a 1-D $K$-state Potts chain of length $L$ with coupling $J$ to model the distribution of text $X=(X^{(1)},\\dots,X^{(L)})$. Concretely, $X^{(1)}\\sim\\text{Unif}([K])$ and $$\\mathbb P\\\\{X^{(i)}=y|X^{(i-1)}=x\\\\}=\\exp(J1\\\\{x=y\\\\})/(\\exp(J)+K-1), \\quad \\forall x,y\\in[K].$$ This construction allows us to compute explicitly the mutual information, the optimal mask predictor $p^\\star(\\cdot | X_t)$, and the densities of $p_{X_0}$ and $p_{Y_0|M}$. \n  - *Mask predictor.* We use the explicitly computable optimal mask predictor $p^\\star(\\cdot | X_t)$ to run the sampling process.\n  - *Sampling error.* Given the explicit densities of $p_{X_0}$ and $p_{Y_0|M}$, the expectation in the KL divergence, taken over both the mask schedule $M$ and the data distribution $p_{X_0}$, is approximated using Monte Carlo simulations. \n\n  - *KL divergence vs. mutual information.* For fixed $T=10$, $K=10$ and $L=100$, KL divergence vs. mutual information is summarized in the following table:\n\n    |   J   | Mutual Information |   KL   |\n    |:-----:|:------------------:|-------:|\n    | 0.000 |     4.80e-13       | 0.000  |\n    | 0.333 |     1.18e+00       | 0.051  |\n    | 0.667 |     5.53e+00       | 0.309  |\n    | 1.000 |     1.43e+01       | 0.748  |\n    | 1.333 |     2.86e+01       | 1.302  |\n  \n    One can verify that the KL divergence error increases linearly with the mutual information. \n\n  - *KL divergence vs. number of iterations $T$.* With a balanced mask schedule, $K=10$, $L=100$ and $J=2$, $\\log KL$ vs. $\\log T$ is summarized in the following table. \n \n    | $T$ |   KL   | $\\log$ KL | $\\log T$ |\n    |-----|--------|-----------|-----------|\n    | 2   | 18.70  | 2.928     | 0.693     |\n    | 4   | 8.85   | 2.180     | 1.386     |\n    | 5   | 7.24   | 1.980     | 1.609     |\n    | 10  | 3.10   | 1.130     | 2.303     |\n    | 20  | 1.49   | 0.395     | 2.996     |\n    | 25  | 1.16   | 0.151     | 3.219     |\n    | 50  | 0.44   | –0.818    | 3.912     |\n\n    One can verify that the slope is very close to -1, demonstrating that the KL divergence error scales proportionally to $1/T$.\n\n  - *Conclusions.* Therefore, these two results validate our established sampling convergence theory.\n\n\n- Thank you for the suggestion.\nAccording to Theorem 1, one can see that $C_1 = T s_{\\max}/\\sum s_t \\asymp 1$. In addition, a direct inspection of the proof of Theorem 2 shows that we may take $C_2 = \\frac{1}{2}$ and $C_3 = \\frac{1}{16}$. We will state these explicit constants in the revised manuscript.\n\n- Thank you for bringing these references to our attention and for the detailed description, which is very helpful for improving this paper. We’ll incorporate them in the revised manuscript to make the introduction more accurate.\n\n**Questions:**\n- This is certainly a valuable point! Classical results from information theory show that when the text distribution has a Markov structure, the mutual information between any token with the rest of the sequence is substantially smaller than that in the full dependent scenario. For instance, when $(X^{(1)}, X^{(2)}, \\dots, X^{(L)})$ forms a first-order Markov chain, then $I(X^{(1)}; X^{(-1)})=I(X^{(1)}; X^{(2)})$, which is typically far less than that in the general case. \nBecause our sampling bound depends on the same mutual-information terms, it automatically tightens for such structured data. Investigating diffusion language models under explicit structural assumptions (e.g., Markov, low-order dependencies) is therefore a promising avenue, and we will add a brief discussion of this point in Section 5.\n\n- Thank you for the suggestion. Our ongoing studies suggests that it is possible to extend our results to the entropy-based sampling and show its performance improvement over the random sampling. Specifically, in each iteration, we can rank the still-masked positions by their conditional entropy (which can be estimated using the learned mask predictor). Unmasking the lowest-entropy positions first reduces the per-step conditional mutual information (because mutual information is always upper bounded by entropy),  thereby leading to a smaller final error bound. Our conjecture is that when the entropy-based sampling procedure is used, the conditional mutual information terms in our current error bounds can be replaced by these smaller conditional entropy terms, which yields improved sampling accuracy. Providing a rigorous theoretical proof for this adaptive strategy is an interesting direction for future work."}]

Author rebuttal:

Meta-review: This paper establishes theoretical convergence guarantees for discrete diffusion language models, proving that sampling error (measured by KL divergence) decays as O(1/T) with the number of denoising iterations T, where the constant factor depends linearly on mutual information between tokens in the target sequence. The authors provide matching upper and lower bounds, demonstrating the tightness of their analysis. Strengths include the novel theoretical contribution addressing a fundamental gap in understanding diffusion language models, rigorous information-theoretic analysis with tight bounds, excellent exposition and clarity, and significant improvements over prior work that was limited to n-gram distributions. Weaknesses center on the lack of empirical validation, assumptions about mask predictor quality that may not reflect practice, and potential concerns about hidden constants in the bounds. 

The author rebuttal successfully addressed most reviewer concerns, leading to improved scores from multiple reviewers. Key additions included synthetic numerical experiments validating the theoretical predictions (addressing concerns from 2wt9, hh8p, DvD9, and v9hs), clarification that the analysis doesn't assume near-optimal mask predictors but works with arbitrary quality predictors (addressing DvD9's confusion), and explicit constants for the bounds (addressing v9hs's concern). Reviewer hh8p upgraded from "borderline accept" to accept after seeing the synthetic experiments, while DvD9 increased their rating by one point. However, DvD9 maintained a remaining concern about the proposed optimization heuristic (unmasking tokens with lowest conditional entropy) lacking experimental validation, noting this as a continuing weakness despite the overall positive theoretical contribution. The synthetic experiments and clarifications were sufficient to demonstrate the paper's theoretical validity and practical relevance, with the remaining empirical gap being acceptable.
Decision: Accept (poster)