Theoretical Benefit and Limitation of Diffusion Language Model
Authors: Guhao Feng
Yihan Geng
Jian Guan
Wei Wu
Liwei Wang
Di He
Venue: NeurIPS 2025 poster ()
Keywords: Discrete Diffusion Model
Efficiency
Masked Diffusion Model
Language Modeling
Metrics for NLP
Primary area: deep_learning
TL;DR: Masked Diffusion Models can generate low-perplexity text efficiently, but can not handle tasks requiring high accuracy efficiently.

Abstract: Diffusion language models have emerged as a new approach for text generation. By enabling the parallel sampling of multiple tokens in each diffusion step, they appear to offer a more efficient alternative to auto-regressive models. However, our observations show that current open-sourced diffusion language models require more sampling steps to achieve comparable accuracy on representative tasks--resulting in even higher inference costs than their auto-regressive counterparts. To investigate whether this is an inherent limitation, we conduct a rigorous theoretical analysis of a widely adopted variant: the Masked Diffusion Model (MDM). Surprisingly, our analysis reveals that the conclusion is highly sensitive to the choice of evaluation metric. Under mild conditions, we prove that when the target is near-optimal perplexity, MDMs can achieve this goal in a constant number of sampling steps, independent of sequence length. This result demonstrates that efficiency can, in principle, be attained without compromising generation quality. However, when targeting low sequence error rate--which is important for assessing the ``correctness" of a generated sequence, such as a reasoning chain--we show that in the worst case, the required sampling steps must scale linearly with sequence length, thereby eliminating the efficiency advantage. Our analysis establishes the first theoretical foundation for understanding the comparative strengths and limitations of MDMs, offering practical guidance on when to favor MDMs over the auto-regressive models and vice versa.

Theoretical Benefit and Limitation of Diffusion Language Model
Guhao Feng
Yihan Geng
Jian Guan
Wei Wu
Liwei Wang Di Helt
State Key Laboratory of General Artificial Intelligence, Peking University
2 School of Mathematical Sciences, Peking University
3 Ant Group
Center for Machine Learning Research, Peking University
{f tneguuao,, gengy pku. edu. en
{j (jianguanthu, 1us1e10553111111mmmmmmll com hinggl,,iih)@pkkpi hwtp:pppkuuuuu..... edu. cn
Abstract
Diffusion language models have emerged as a new approach for text genera- tion. By enabling the parallel sampling of multiple tokens in each diffusion step, they appear to offer a more efficient alternative to auto-regressive models. How- ever, our observations show that current open-soureed diffusion language models require more sampling steps to achieve comparable accuracy on representative tasks-resulting even higher inference costs than their auto-regressive counter- parts. To investigate whether this is an inherent limitation, we conduct rigorous theoretical analysis of widely adopted variant: the Masked Diffusion Model (MDM). Surprisingly, our analysis reveals that the conclusion is highly sensitive to the choice evaluation metric. Under mild conditions, we prove that when the target is near-optimal perplexity, MDMs can achieve this goal in constant number sampling steps, independent of sequence length. This result demon- strates that efficiency can, in principle, be attained without compromising genera- tion quality. However, when targeting low sequence error rate- rate-which important for assessing the "correctness" of generated sequence, such reasoning chain- we show that in the worst case, the required sampling steps must scale lincarly with sequence length, thereby eliminating the efficiency advantage. Our analy- sis establishes the first theoretical foundation for understanding the comparative strengths and limitations of MDMs, offering practical guidance when to favor MDMs over auto-regressive models and vice versa.
Introduction
Diffusion models (Ho 2021: Song et al] (0211) have emerged powerful paradigm in gen- erative modeling, establishing state-of-the-ar performance in image synthesis (Karras el all RDZ2: Song et al,, ()) Their extension discrete domains has opened new possibilities for generating sequences, such as natural language (Campbell et al, R022; Dieleman et all 2022: Zheng et all 2023; Lou all, 2024k Campbell all, 2024; Lovelace et atall 20244 and biological sequences (Kase logi et all, 2022 Vignac et al], 2022: Sun & Yang, 2023; Avdeyev et all, 2022). Among various discrete diffusion architectures, masked diffusion models (MDMs), which generate sequences by
"Equal Contribution Conresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

iteratively converting masks to tokens, have demonstrated competitive performance across language generation tasks (Shi all 2024; Sahoo et all. 2023: Ou et all, 2024).
While auto-regressive models generate sequences token-by-token, discrete diffusion models can gen- erate multiple tokens simultaneously during each step, offering the potential for greater efficiency. However, efficiency and quality are often two sides of the same coin, and the key lies in identifying the trade-off points of different approaches. Unfortunately, as shown in Figure M1 we observed that for two recent open-sourced large MDMs, achieving performance comparable to that of left-to-right generative models incurs higher computational costs, as more sampling steps are required. This leads us to ask: do discrete diffusion models really offer a better trade-off than auto-regressive mod- els, achieving superior efficiency while maintaining high-quality generated content? The answer may vary. If MDMs require fewer steps (i.e., neural network executions) without compromising quality, they could offer a more favorable trade-off than auto-regressive models. However, the number of executions needed to maintain quality is similar to or exceeds that of auto-regressive models, then MDMs may not present a clear advantage.
To address the above question, we present the first theoretical analysis of the efficiency of Masked Diffusion Models (MDMs) and find that the seficieney-accurace trade-off is highly sensitive the choice of evaluation metric. We adopt two complementary metrics to assess the efficiency of MDMs in language modeling. The first metric, token error rate (TER), quantifies leven-level accuracy, which correlates with the fluency of the generated text. In practice, perplexity is a widely used metric for measuring loken-level errors of language models (Uelinek et all. 1977: Deyhn all. 2019): thus, we define the metric of TER by perplexity in this paper. The second metric, sequence error rate (SER), evaluates the correctness of an entire sequence, which crucial for reasoning tasks requiring logically correct sequences. We provide natural definition of SER that reflects the correctness of the whole sequence. Together, these metrics enable a comprehensive evaluation of MDMs at both the token and sequence levels.
We first provide a positive theoretical result regarding TER. We prove that under mild conditions, MDMs can achieve near-optimal TER with sampling steps regardless of the sequence length L. Compared to the auto-regressive model, which must be executed L times generate the sequence. MDMs demonstrate substantial efficiency gains, especially when the generation length is long. How- ever, we show that this efficiency advantage diminishes when SER is considered. We theoretically prove that to achieve low SER, in the worst case, the number of required sampling steps for MDMs must scale at least linearly with sequence length. Intuitively, this limitation arises from the fact that SER, a metric for the entire sequence, requires the generated sequence to be free of any error in the whole sequence, which forces MDMs to sample only a small number of tokens per step to mitigate such inconsistencies. As a result, the number of required sampling steps can be signifi- cant. It notable that each MDM sampling step usually incurs a higher computational cost than an regr-segre step under the same architecture, thus MDMs offer efficiency advantage.
To fully validate our theoretical findings, we conduct synthetic experiments and examine MDMs trained on formal languages, including n-gram languages and Hidden Markov Models (HMMs), systematically analyzing the relationship between performance and efficiency under both TER and SER metrics. All empirical results align with our theoretical predictions: For MDMs, achieving low SER requires a significant number of sampling steps, and this requirement increases as sequence length grows. In contrast, obtaining a satisfactory TER demands fewer sampling steps, with this number remaining relatively constant regardless of sequence length. These findings offer practical guidance for selecting when to deploy diffusion language models based on specific application needs and requirements.
2 Related Work
Discrete Diffusion Models. The auto-regressive paradigm has achieved significant success in language modeling (Dai, 2019 Elondi & Chiriatii, 2020; Achiam atll 2023). However, its left- to-right, token-by-token generation approach is not without limitations. Notably, it faces challenges such as restricted controllability (Zhang et al, 20223) and inefficiencies in inference speed (Leviathan atl 2023). To overcome these drawbacks, inspired by the success of diffusion models in image generation (Sohl-Dickstein et all, 2015: [Song et all, 2021a; Karras et all 2022)) researchers have
adapted these techniques for NLP tasks (Austii el all 202LE He et all 2I2 Chen et all 202

---

Meng et all 0022: et all 2025: Gulrajami & Hashimoto, 2023 Zhang et all 2022). Discrete diffusion models, in particular. have shown promising results, achieving comparable performance with auto-regressive models across range of NLP benchmarks.
Discrete diffusion models can be categorized based the initialization strategy of the reverse process: (I) reverse processes that begin with masked sequences and (2) reverse processes that start with sequences of tokens sampled randomly from the vocabulary. The first category, termed masked diffission models (MDMs), includes models such as SEDD Absorb (Lou et all 2024) and its streamlined variants in subsequent works (Sahoo et all 2024, Zhao et all, 2024: Shi all 2024: Ot all 2024; Zheng et all, (004)). The second category encompasses models like SEDD Uniform (Lou all 2024), as well extensions introduced follow-up studies (Campbell et al, 2024). Notably, Gat et all (2024); Davis et all (2024) and Campbell et al. (2024) further extend flow-matching to the discrete domain, with differing initialization strategies: the former employs masked sequences, while the latter utilizes customized distribution for the reverse process.
Masked Diffusion Models. Among the two primary classes of discrete diffusion models, MDMs have consistently demonstrated superior performance and scalability (Lou et all 2024; Campbell etall 2023). For instance, in Lou all (2023), the masked variant of SEDD significantly outper- forms its uniform counterpart across a range of benchmarks. Similarly, Campbell et al. (2022) report that the masked variant achieves better results in most language tasks. Based on MDMs, some sam- pling strategies have been proposed to enhance efficiency or generation quality (Sahoo all, 2024; Ou st 2024: Wang et all 20255 Kim et all 2025). Furthermore, recent advancements have suc- cessfully scaled MDMs to 8 billion parameters (Gat all 2024; Nie all, 2024: [ong et all 2024 Shi 2023; Nie all 2025; etll 2025), underscoring their robustness and adaptability to large-scale NLP models. In this paper, we focus MDMs, and our theoretical contributions can be applicd to all MDMs, including the masked variant of discrete flow matching. Notably, concurrent with our theoretical analysis of MDMs, Lr all (2022) also conduct in-depth theoretical and empirical study on another class of MDMs. While their work primarily investigates the statistical complexity of learning these models, our analysis concentrates on the efficiency-accural trade-off of MDMs during inference.
3 Masked Diffusion Language Model
Without loss of generality, we study the sequence generation task where the sequence length is upper bounded by T.. Let V denote the vocabulary. The MDM (Louetall, 2024, Shierall 2024 Gong et all
2024; IShoo et all (0224) extends the vocabulary V by introducing a special mask token [m] The forward diffusion process progressively transforms an initial sequence 2n (xr]- 22. x VL
into fully masked sequence Φ ([m), , [m],.. [m]) ) by independently masking each token according a predefined schedule. Conversely, the reverse process defines a generative model that reconstructs a sequence by iteratively modifying a fully/partially masked sequence. Below, we formally define both the forward and reverse processes.
Forward process. Given a sequence Do and a masking schedule a,, the distribution of the sequence 2, at time t E [0, 1] is expressed as:
L-1
C (D)) II
where 4t (eo()11z))
at:
5t = xhj x [m].
az
The masking schedule 0e is designed such that 0gg 1, ensuring that the sequence remains masked at the start of the process. Similar to the continuous diffusion methods (Ho all, 2020; Song et all 2027; Karras et all 20222. we set a (or a value approaching zero), ensuring the sequence is fully masked at the end of the forward process.
Reverse process. The reverse process reconstructs sequence from masked version by reversing the forward dynamics. Given the sequence at time t and the original sequence Eg. the conditional distribution of the sequence at time I, is defined as:
- Ot 5 (xt) +
O₂ - -at 5n (xz),
( xo) = 1 at
1 a
3

---

Rolative Efficiency Accuracy MDMs against AutionstAuto-Feee Auto-Regressive Model on GSMBK (8 shote)
Relative Efficiency Accuracy of MDMs
with Different Sampling Strategies on GSMBK (8 shots)
14
Robalive Accumacy
Fularive Accuniyy
Lower Efficiency Higher Accuracy stop 250
Higher Efficiency Higher Accuracy
Lower Efficiency Higher Acturacy
Higher Efficiency Higher Accuracy
1.2
1.0
Relatve Etigenay
Relative Emiclency
eln 258
soop 258
step
Higher Efficiency Accuracy
Lawer Efficiency Lower Accuracy
5top
stcp 128
stop 128
step
slop
Dream- Sa-ae---- TB)
[D Buse 78) relaove [Drasm-to-Baae (at-b--rggnt
stop
rikehs to 10wen2 3-73
Stats--ttdtaaaa readuve
stop 64
0.00125 0.0625 0.126
2.0
18.0
0:125
0.25
Figure 1: Efficiency and accuracy of MDMs on GSM8K (8-shot): The left figure uses Qwen2.5-7B as the evaluation baseline and plots the relative accuracy and efficiency of Dream-vO-Basee -LaDA-8B-Bass across different sampling steps. The origin can be considered as the baseline result. The first quadrant demonstrates models that can simultancously achieve higher efficiency and accu- racy. From the figure, we can see that the MDMs all fall into the third quadrant, indicating lower efficiency and lower performance. The right figure uses baseline in which the MDMs are con- strained to generate the left- most masked token at each step, effectively mimicking auto-regressive decoding using the same model. Still, even under this setting, none of the configurations fall into the first quadrant.
and
where 85 (v) is the Kronecker delta function. Marginalizing over x, yields the true reverse process qxx, x.):
L-1 Lo (xt axee,
(2.(221/10))) = II
where
1=0
1,
x
+
[m]
x
Zt
(2)
2
2
[m]
2stt (2 xx)
=
a at 1-ar
20 (x))
o [m]]
x
7 [m]
0,
otherwise.
In MDM, a parameterized reverse model pa is often employed to approximate the distribution ( x2). This model is trained by minimizing the evidence lower bound (ELBO) (Lou ot all 2024: Shi all 2024: Gong et all 2024; Sahoo et all 2022) on the negative log-likelihood of the data distribution qu-
Inference within the MDM framework entails discretizing the reverse process to itera- tively reconstruct sequences from a fully masked sequence. Let T denote the number of sampling steps. Starting with a fully masked sequence, the denoising process proceeds via Vaje(a,, ax)), where s = T tion Pa x.),, followed by masking specific tokens according q(x, | 2z, 2o).
Inference.
i+1 At each step, the model first samples zn from the conditional distribu- i and t = T
In practice the reverse model is parameterized using a factorized denoising model, where the condi- tional distribution po(#0 ax,) is expressed as:
1. po p= xx)) = II po (=0 w.).
Here, each token is predicted independently using P=(2) xz). allowing for efficient parallel sam- pling. However, this factorized approach imposes a significant limitation: it disregards interdepen- dencies between tokens within the sequence. As result, the factorized model po (x | x;) cannot exactly match the true reverse distribution q(za) xx) (Xu all 2024). In this work, we analyze the conditions under which this sampling method achieves favorable balance between efficiency and the quality of the generated sequences. Motivated by these observations, this paper begins by re-examining the theoretical upper bounds the performance and efficiency of MDMs.
afccury trade-off of open-sourced MDMs. The afficiency-accuracy trade-off is cru- cial for understanding the strengths of different generative models. In Lou al (20224);; Nie et al

---

(2022), researchers demonstrate that MDMs offer more favorable trade-off than auto ruge-segressive models in terms of perplexity-that is, the learned MDMs can achieve competitive perplexity with higher token throughput. However, to the best of our knowledge, there has been limited empirical investigation of this trade-off in realistic tasks such as reasoning.
To address this gap, we conducted experiments on the GSM8K, MBPP, and HvaanEval benchmarks (Cobbe atall 202T; Austin et al, P0 Chen et all IO2T,, using two recently released large-scale MDMs in 2025, Dream-vO-Base 7B and LLaDA-SB-BRL -Bee (Ye et all 2025: Nie et all (025).. We directly evaluate these checkpoints using different numbers of decoding steps, and compare the ac- curacy and efficiency against similar- size auto-regressive baseline Qwen2.5-7B (Team, 2024). The results on GSM8K are presented in Figure the results on MBPP and HumanEval are presented in Appendix A. and Appendix A4 Notably, across all configurations (sampling steps), the perfor- mance and efficiency of MDMs are significantly worse than that of auto-regressive models.
key contributing factor to this gap is that the model checkpoints were trained on different private datasets, which inherently introduces bias into the comparison. To ensure fairesss, we also construct a baseline by running the MDMs in an auto-regressive manner: at each diffusion step, the model is constrained generate the left-most masked token, thereby producing the full sequence L steps. However, even compared to this naive baseline, none of the configurations fall into the first quadrant of the plot in Figure M- Dnddiicct that, compared auto-regressive decoding, MDMs may not be able to simultancously achieve superior efficiency and improved performance. Full details are given in Appendix
Theoretical Analysis
Motivated by the observations above, this paper begins by re-examining the theoretical trade-off between the accuracy and efficiency of MDMs. In image generation, the primary goal is typically to produce visually appealing and scamless images (Heusel et all 2017). Language generation is more task-specific. Depending on the application, the users may prefer fluent outputs, as in article writing, or precise and accurate reasoning, as in problcm-solving tasks. In this section, we explore the sampling efficiency of MDMs in addressing various language tasks with respect to different evaluation metrics.
4.1 Notations and Problem Setting
Our investigation employs the hidden Markov model (HMM) framework to analyze natural lan- guage generation. This section establishes the formal notation and problem setting that underlie our subsequent analysis.
HMMs (Eddy, (19%) provide a probabilistic foundation for modeling sequential data with latent structures, where observed sequences are generated by an underlying sequence of unobservable hidden states. Formally, an HMM H. VS V. A, B) characterized by the following components: a finite set of hidden states S = $2,, SN)) )N). an observable vocabulary V. state transition probability matrix A E N an emission probability matrix B E N VI, and an initial state distribution π e N Given a sequence of observations
(I1, T2, T2...... 22) E y and a sequence of hidden states = ($1, $2....,. $L) ) E S", the generative process of an HMM is governed by the following probabilistic relations:
Pr(s1) Tea Pr(z, st) B
Pr(s: $1:-11 = Pr(s; (1-1) As; 1.81
This formulation enables HMMs to capture both the sequential dependencies among hidden states and their probabilistic relationships with observed data. In the field of NLP, HMMS serve as the fundamental statistical tools to model natural language (Eddy, [996 Marh & Bunke 2001). A notable special case of HMM is the r-gram language model (Brown et all 1992), which estimates the probability a token given its preceding n - tokens. Despite their simplicity, n-gram models foundational tools in NLP tasks (Brown et all 1992: De Novais et all 2010). Moreover, Lm et all (2022) suggests that scaling up n- n-gram models can also achieve performance comparable to modern large language models.
Formally, we aim to address the following question: If MDMs have the capability to approximate target HMM model, what are the computational costs, and do MDMs offer advantages over auto-
5

---

regressive models? To evaluate the approximation quality of MDMs, we adopt two widely used metries: TER and SER, which quantify different aspects of model's performance.
Token Error Rate. In practice, perplexity is one of the most widely used metrics for evaluating token-level errors in language models. It quantifies the uncertainty of model in predicting the next token in a sequence and serves as a standard measure for assessing the quality of text generation. In this paper, we define the TER by perplexity. Models with lower TER are generally considered more effective at generating fluent and coherent text. Formally, given a ground-truth language model and an evaluated model p. the TER computed as:
TER(p) - 2Ba los(p(m))
(4)
Sequence Error Rate. The SER evaluates the correctness of an entire sequence rather than individ- ual tokens. Let q represent target language defined over vocabulary V, and let L, {or V ((x)) >> 0} denote the support set of distribution q. For a generative model p. the SER is defined as: SER(p) = 1 Σ p(x)).
(5)
EcC,
This metric quantifies the probability that the model generates sequences falling outside the support set of the ground-truth distribution.
Compared to TER, SER imposes a stricter evaluation criterion by requiring the correctness of entire sequences. This makes SER particularly well-suited for tasks that demand logical consistency or reasoning, where the correctness of the complete reasoning chain is crucial.
4.2 MDMs Can Generate Low-TER Sentences Efficiently
In this subsection, we rigorously examine the efficiency of sampling in MDMs, demonstrating that MDMs are capable of efficiently generating sentences with near-optimal TER. To establish the main theoretical results, we assume that the MDMs have enough expressive power and begin with the following assumption:
Assumption 4.1 (Learning with Small Error). Let & denote the target language model with vocabu- lary V, and let Pg represent the reverse model trained to approximate the reverse process generating the target language under masking schedule o,, Assume there exists fleaming > 0 such that the KL divergence between pa and the reverse process distribution generating the language q bounded by
éleaming, i.c.,
DKL (goje [x))lpoozr ax)))
Oleaming:
A and Ct.-
It is worth noting that (a xz:) gojo xx)) represents the optimal solution to the ELBO loss during training. Assumption I. implies that the MDM model is rell-trained and approximates the ground-truth distribution with only a small error.
During MDM inference, the time interval [0, 1] is discretized into N steps, where 4; v. i [N], and iteratively reconstruct sequences from a fully masked sequence. The following theorem shows that the sequence distribution generated by the reverse process, even with small number of sampling steps, can achieve npar-optimal TER. Consequently, MDMs exhibit high efficiency in generating n-gram language.
Theorem 4.2 (TER Bounds for n- n-Gram Language Generation). For any n- n-gram language q and any O, let po denote the reverse model and L denote the sequence length. The distribution over sequences generated by is denoted as p. For any >> O (= under Assumption E.A. there exists a masking schedule a such that, with N = -("m-) (==1) sampling steps, the TER of the MDM is upper-bounded by:
log TER(p) S log TER(q) + Ctearning + 4c log VI.
(6)
The proof of this theorem is presented in Appendix ID. Theorem efficiently generate sentences with high fidelity. is notable that for a given data distribution the TER of a language model p achieves its global minimum when q. To ensure a gap of at most e with the optimal TER during sampling, the number of required sampling steps is bounded by
2y demonstrates that MDMs can
The above results suggest that to achieve near-optimal TER, MDMs require only a number of sam- pling steps that is independent of the sequence length L. In each sampling step, the neural network

---

model, i.e., a Transformer, is executed once. Therefore, informally, the neural network execution count is constant for MDM. This offers substantial efficiency gains over auto-regressive models, where the model must be executed I. times, once for each token in the sequence. Such efficiency enables MDMs to handle long- sequeeeeeene generation tasks effectively while maintaining high-quality outputs.
4.3 MDMs Cannot Generate Low-SER Sentences with A Low Cost
In this subsection, we examine the SER of sampling in MDMs and highlight fundamental lim- itation of MDMs in generating logically rigorous language. We begin by establishing that, with sufficient sampling steps, the MDMs are able to approximate a target HMM model with perfect SER.
Theorem 4.3 (Accurate Generation of HMM with Sufficient Steps). Let q denote any HMM, and let pe represent the reverse model under an arbitrary masking schedule, where L is the sequence length. Let p denote the distribution over sequences generated by pa- Under Assumption I with learning ervor Elearning O(4). and given sufficient number of reverse steps, the sequence error rate (pR(p) of the generated text satisfies SER(p) S 5.
The complete proof of Theorem + is detailed in Appendix
While this result establishes the theoretical capability of MDMs to achieve low SER, we still need to estimate the computational cost to achieve it. The following theorem provides a negative result for this problem.
Theorem 4.4 (SER Bound for HMM Generation). There exists an HMM q over vocabulary of size 16 that satisfies the following conditions: for any reverse model pe under Assumption H. with élearning < 128 and any masking schedule os, let denote the distribution over sequences generated by po. There exists a constant C such that the number of sampling steps satisfies N CL. where L is the sequence length, the SER of the generated text is lower- bounded by: SER(p) > 2'
The proof of Theorem 4 is presented in Appendix [xp Theorem
! shows that to generate se- quences with low SER, the number of sampling steps in MDMs must scale at least linearly with the sequence length L, indicating that the number of neural network exccutions is comparable be- tween MDMs and autoregressive models. However, this scaling law of MDMs typically leads to much higher computational costs compared to autoregressive models. For instance, in the case of Transformer-basee architectures, each execution step in MDMs involves quadratic computational complexity in terms of L, as opposed to the linear complexity of auto-regressive Transformer models in each generation step (through reusing the stored KV caches). Consequently, in accuracy- critical applications, MDMs offer no computational efficiency advantage over auto-regressive models.
Extended analysis of Theorem 1e Since the high SER partly arises from irreducible errors intro- duced by parallel sampling, it is natural to ask whether this issue can be mitigated by allowing tokens to be remasked. In Appendix S examine the remasking strategy recently proposed by (Wang allll 2025), and demonstrate that Theorem 4 continues to hold. Furthermore, some prior works (Sahoo et all, 2024; Ou et all 2024) have proposed efficient sampling strategies that reuse cached outputs without requiring additional forward passes through the network when no token is modified from [m] at given step. Nevertheless, our theoretical results remain applicable to these sampling strategies, which is discussed in Appendix BK
Discussion regarding theory and GSM8k result. SER is closely related to the accuracy of MDMs in solving mathematical problems, as an incorrect chain of thoughts typically leads to an erroneous answer (Wer et all, 2022|; Yu et all, 2024; Zhu all 2024). Our theory reveals that MDMs incur higher computational costs when evaluating generations by SER. This finding is consistent with re- sults presented in Figure M1 Both our theoretical insights and these prior experiments demonstrate that when MDMs are applied to math problems, their able than that of AR models. For further discussion, please refer to Appendix [3)))
performance trade-off is less favor-
Practical guideline of ARs v.s. MDMs. Based on the theoretical results, conclusions regarding when to favor MDMs depend heavily on the evaluation metric employed. Specifically, MDMs excel in applications where fluency is prioritized. In contrast, for reasoning-intensse tasks that demand highly accurate trajectories, MDMs may fail to offer significant efficiency advantage over auto- regressive models. As result, MDMs are better suited for fluent generation tasks, while ARs remain the preferred choice for tasks that require precise, step-by-step reasoning.
7

---

SER with Different Sampling Steps
N-gram
Length
128
256
512
1024
2048
AR
512
36.2 + 4.2
24.5 3.2
14.4 + 2.9
7.4 + 2.2
5.4 1.2
0.2 0.1
2-gram
1024
59.5 + 4.9
40.3 + 4.6
23.2 + 3.2
14.6 + 3.0
9.4 1.5
0.3 = 0.2
2048
88.70 +: 2.8
71.5 3.7
50.2 + 4.4
40.2 3.9
26.9 + 3.3
0.3 + 0.1
512
37.3 + 3.6
21.6 + 3.3
16.4 + 2.7
11.6 + 3.0
7.9 = 2.1
0.2 + 0.1
3-gram
1024
64.8 + 4.7
39.4 + 5.3
26.6 + 3.0
19.3 + 3.2
13.9 2.7
0.3 0.3
2048
86.0 + 3.9
66.1 5.3
48.2 + 5.2
48.2 5.6
37.8 + 5.2
0.2 0.2
512
51.8 + 4.4
39.2 + 3.2
34.0 + 3.5
30.0 + 2.7
25.7 2.6
0.5 0.1
4-gram
1024
67.9 + 5.6
52.9 + 5.1
41.8 + 2.7
36.1 + 5.8
35.4 5.1
0.4 + 0.2
2048
80.0 + 4.1
68.1 + 5.5
62.0 + 5.4
62.0 + 4.3
60.1 + 3.8
0.5 + 0.4
512
19.1 + 2.1
16.7 + 2.3
12.8 + 2.6
9.1 2.6
2.2
0.4 + 0.1
HMM
1024
40.1 + 2.5
32.8 3.1
29.9 2.6
30.5 + 3.0
0.4 0.2
2048
68.5 + 5.6
63.4 4.2
62.9
5.5
62.9 + 4.7
61.8
0.3 0.1
TER with Different Sampling Steps
N-gram
Length
128
256
512
1024
2048
AR
512
3.71 .03
3.68 .02
3.67
3.67 + .01
3.67 =00
3.67 .01
2-gram
1024
3.72 + .05
3.70 .03
3.68 .01
3.68 + .02
3.67 = .01
3.67 .01
2048
3.71 + .05
3.69 + .03
3.67 +: .02
3.66 + .01
3.66 = .01
3.66 + .02
512
3.13 + .05
3.10 + .03
3.07 + .01
3.07 + .01
3.07 = .01
3.07 + .01
3-gram
1024
3.14 +: .06
3.10 .03
3.09 .02
3.08 + .01
3.08 .01
3.08 + .02
2048
3.15 .06
3.11 .03
3.10 .02
3.09 + .01
3.08 .02
3.08 .02
512
3.27 .08
3.23 .04
3.20 .02
3.20 + .01
3.19 = .01
3.19 .01
4-gram
1024
3.21 + .08
3.16 + .03
3.16 + .02
3.14 .01
3.14 .01
3.14 + .01
2048
3.20 + .06
3.16 + .03
3.14 + .02
3.13 + .02
3.12 .01
3.12 + .02
512
4.04 + .03
4.01 + .03
4.00 .01
3.99 .01
3.99 .01
3.99 + .01
HMM
1024
4.03 .04
4.01 .02
4.00
3.99 + .02
3.98 .02
3.98 .02
2048
4.03 .02
4.02 .01
4.01 .01
4.00 + .01
4.00 = .01
4.00 .01
Table 1: SER and TER results for MDMs (n-grams, E {2, 4): HMMs) vs. AR baseline across varying sequence lengths (512, 1024, 2048) and sampling steps. The 'AR' column (underlined) pro- vides the baseline for comparison. In the TER table, blue highlighting indicates MDM performance statistically similar to the AR baseline according to T-Test. MDMs approach AR TER with 512 sampling steps, irrespective of sequence length. Accuracy, however, requires more steps for longer sequences and generally lags behind AR models with large margin.
5 Experiments
As discussed in the previous section, our theory aligns with observations in natural language tasks. However, for comprehensive validation and completeness, we also conducted experiments to empir- ically support our theoretical results. More precisely, these experiments the relationship between sampling steps, sequence length, the SER, and the TER. We will first intro- duce experimental setup, followed by presentation of the results.
designed to investigate
5.1 Experimental Setup
Tasks and Datasets. We evaluated MDMs on several formal languages: n-gram languages (with E (2 4)) and HMMs. For each language type, parameters (c.g., transition matrices,

---

observation matrices, initial distributions) were randomly sampled. A detailed description of this generation process and examples of resulting sequences are available in Appendix E.I. These formal languages were used to generate datasets of 1,000,000 samples each, with 990,000 for training and 10,000 for validation. Datasets were generated with sequence lengths I. E (512, 1024, 20483.
Model Training. Transformer-based architectures served as the backbone for our MDMs, chosen for their scalability and expressiveness in sequence modeling. Detailed architectural specifications, including layer counts, hidden dimensions, and positional encoding schemes, are provided in Table ! (Appendix E2).. The training procedure largely followed the framework of Sahoo et all (2024), with specific training configurations detailed in Table &. Models were trained for 20 epochs, with conver- gence monitored on the validation set using perplexity. The trained models successfully achieved perplexity values consistent with the ground-truth language models generating the datasets.
Evaluation Metrics. To evaluate the quality of generated sequences in line with theoretical framework, we used TER and SER as primary metrics. Generative perplexity, computed using the ground-truth model, served the TER metric. SER was calculated directly via Equation (5) (where accuracy reported in tables is 1 - SER), also utilizing the ground-truth models. For sequence generation, we employed the ddpm_cache cache sampler from Sahoo et (2022); its influence under varying sampling steps is further discussed in Appendix B.S. We report the inference time per sequence of MDMs with 512 sampling steps and AR models in Table D across different sequence length (detailed inference settings in Appendix E22) For robust evaluation, all reported TER and SER values are averages over 2000 generated sequences for each experimental setting.
Auto- Nutt-Regressive Baseline. We also trained AR models with identical architectures and model sizes on the same datasets generated by the formal languages for comparison. These AR models were evaluated using the same metrics. Training configurations for the AR models are detailed in Table g.
5.2 Experiment Results
The experiment results are presented in Section EL This table presents the generative perplexity and accuracy on n-gram languages E {2, 3, 4}) and HMM. The results are detailed for sequence lengths of 5 512, 1024, and 2048, across a varying number of sampling steps (128, 256, 512, 1024, and 2048). The final AR'' column shows the performance of the auto-regressive baseline.
As Section E shows, under the metric of TER, MDMs achieve near-optimal generative perplexity, closely matching the AR baseline, with approximately 512 sampling steps. Crucially, this required number of sampling steps remains relatively constant across the tested sequence lengths (512, 1024, 2048). This empirically supports our theoretical finding that TER is primarily dependent the number of sampling steps, rather than sequence length.
In contrast, achieving low SER with MDMs necessitates substantially larger number of sampling steps. This requirement becomes more pronounced as sequence length increases. For instance, for 2-gram models generating sequences of length 2048, even 2048 sampling steps yield only 73.1 % accuracy, whereas AR models achieve near 100%. This aligns with our theory that SER is more sensitive to both the number of sampling steps and the sequence length.
Furthermore, even with high number of sampling steps (e.g.. 2048), a significant gap in SER persists between MDMs and AR models. This is particularly evident for more complex languages like 4-grams and HMMs across all sequence lengths. For example, with 4-gram language of length 512, MDMs with 2048 steps achieve 74.3% accuracy, while the AR bascline reaches 99.5%. AR models, due to their token-by-token generation mechanism, consistently achieve near- wear-perfect SER on these tasks. This result further validate our theoretical result that MDMs Cannot generate low- SER sentences with a low cost.
Sequence Length
512
1024
2048
MDMs (512 steps)
3.1s
4.2s
4.7s
AR
1.7s
3.3s
7.0s
Table 2:
The inference time per sequence of MDMs with 512 sampling steps and AR models.
Despite the challenges achieving low SER, MDMs demonstrate considerable efficiency in gener- ating fluent sequences with a fixed number of sampling steps (e.g., 512 steps), especially for longer sequences. The inference time per sequence, detailed in Table El quantifies this advantage, showing MDMs to be highly efficient for generating fluent long sequences.

---

These empirical findings underscores the trade-off between generation efficiency and performace for MDMs. While MDMs excel producing fluent outputs efficiently, they require considerably more sampling iterations to achieve low SER. This characteristic is particularly salient for reasoning- intensive tasks that demand high sequence- correctness. Collectively, these experimental results provide strong empirical corroboration for our theoretical analyses.
Conclusion and Limitations
This paper provides a rigorous theoretical analysis of the efficiency of MDMs under various metrics. We demonstrate that MDMs can achieve near-optimal TER with fixed number of sampling steps, regardless of sequence length, making them highly efficient for tasks emphasizing fluency. However, when evaluated using SER, MDMs require sampling steps that scale linearly with sequence length, negating their efficiency advantage over auto-regressive models. Our study focuses on formal lan- guages modeled using HMM, which, while foundational, still differs from modern language models. Extending this analysis to more advanced language models remains an important direction for fu- ture work. Additionally, we primarily analyze Masked Diffusion Models, but broader family of diffusion-based language models, including variants like SEDD-unform (Lou et all 2024). Further exploration is needed to generalize our findings to real-world settings and to systematically analyze other diffusion approaches.
Acknowledgement
This work is supported in part by the State Key Laboratory of General Artificial Intelligence. DH is supported by National Science Foundation of China (NSFC62376007) and Beijing Natural Science Foundation (7250001).
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Al- tenschmidt, J. Altman, S., Anadkat, S., al. Gpt-4 technical report. arXiv preprint arXiv:2303.08874. 2023.
Austin, J., Johnson, D. D., Ho, Tarlow, D., and van den Berg, R. Structured denoising diffusion models in discrete state- spacess In Advances in Neural Information Processing Systems, 2021a
Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., and Sutton, C. Program synthesis with large language models, 2021b. URL https: //arxiv.org abs/2108.07733:
Avdeyev, Shi, C., Tan, Y., Dudnyk, K., and Zhou, Dirichlet diffusion score model for biological sequence generation. In International Conference Machine Learning, pp. 1276-1301. PMLR, 2023.
Bahdanau, D. Neural machine translation by jointly learning align and translate. arXiv preprint arXiv:1409.0473 2014.
Brown, P. F., Della Pietra, V. J., Desouza, P. V., Lai, J. C., and Mercer, R. L. Class-based n-gram models of natural language. Computational linguistics, 18(4):467-480, 1992.
Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T.,
Li, Y., Lundberg, S., et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv: 120..1222, 2023.
12712,
Campbell, A., Benton, J., Bortoli, V. D., Rainforth, T., Deligiannidis, G., and Doucet, A. A continu- time framework for discrete denoising models. In Advances in Neural Information Processing Systems, 2022.
Campbell, A., Yim, J., Barzilay, R., Rainforth, T., and Jaakkola, T. Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design. In Forty-firsl In- ternational Conference on Machine Learning, 2024. URL https://openreviee net/forum? htt.enrrviiieeeeeforuuum ad=RywSbyUBRA
10

---

Chen, M., Tworek, J. Jun, H., Yuan, Q. de Oliveira Pinto. H. P., Kaplan, J., Edwards, H., Burda, Y. Joseph, N., Brockman, G., Ray, A.. Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G. Míshkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, I.., Bavarian, M., Winter, C., Tillet, P., Such, P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E.,, Herbert- Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saunders, W. Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford,
A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I,, and Zaremba, W. Evaluating large language models trained on code. 2021.
Chen, T., Zhang, R., and Hinton, G. Analog bits: Generating discrete data using diffusion models with self-conditioning. arXiv preprint arXiv:2208.0422) 2022.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, l.., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers solve math word problems. arXiv preprint arXiv:2110.1 10. 14168, 2021.
Dai, Z. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:I901. 02860. 2019.
Davis, O., Kessler, S., Petrache, M., Ceylan, I. I., Bronstein, M., and Bose, A. J. Fisher flow matching for generative modeling over discrete data, arXiv preprint arXiv:2405. 146644 2024.
De Novais, E. M., Dias Tadeu, T., and Paraboni, I. Improved text generation using n-gram statistics. In Advances in Artificial BeeligeenceIBEERAA 2010: 12th Ibero-American Conference on AI, Bahía Blanca, Argentina, November 1-5, 2010. Proceedings 12, pp. 316-325, Springer, 2010.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technolo- gies, Volume (Long and Short Papers). Association for Computational Linguistics, 2019.
Dieleman, S., Sartran, I.., Roshannai, A., Savinov, N., Ganin, Y., Richemond, P. H., Doucet, A., Strudel, R., Dyer, C., Durkan, C., Hawthorne, C., Leblond, R., Grathwohl, W., and Adler, J. Continuous diffusion for categorical data. ArXiv, 0os/2211.15088 2022.
Eddy, S. R. Hidden markov models. Current opinion in structural biology, 6(3):361-365. 1996.
Floridi, L. and Chiriatti, M. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 30:681 196881994,200 2020.
Gat, I., Remez, T., Shaul, N., Kreuk, F., Chen, T., Synnaeve, G., Adi, Y., and Lipman, Discrete flow matching. arXiv preprint arXiv:2407. 15595, 2024.
Gong, S., Agarwal, S., Zhang, Y., Ye, J., Zheng, I., Li, M., An, C., Zhao, P., Bi, W., Han, J., et al. Scaling diffusion language models via adaptation from autoregressive models. arXiv preprint MIXiv:2410.1781 2024.
Gulrajani, I. and Hashimoto, T. Likelihood-basse diffusion language models. In Advances in Neural Information Processing Systems, 2023.
He, Z., Sun, T., Wang, K., Huang, X., and Qiu, X. Diffusionbert: Improving generative masked language models with diffusion models. In Annual Meeting of the Association for Computational Linguistics, 2022.
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. Gans trained by a two time-scale update rule converge local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, 2020.
Hu, Y., Huang, Q., Tao, M., Zhang, C., and Feng. Y. Can perplexity reflect large language model's ability in long text understanding?, 2024. URL https://arxiv.orzz http://axxvv...g/bbbeeee// wargg/bs//40g/ 06105.

---

Huang, F., Tao, T., Zhou, H., Li, L., and Huang, M. On the learning of non- bon-autoreggressive transform- ers. ArXiv, abs/2206.05975, 2022. URL sttps://apl..mmmniiccccllooo
249626413
Jelinek, F., Mercer, R. L., Bahl, L. R., and Baker, J. K. Perplexitya measure of the difficulty of speech recognition tasks. The Journal of the Acoustical Society of America, 62(S1):S63 S63, 1977.
Karras, T., Aittala, M., Aila, T., and Laine, S. Elucidating the design space of diffusion- based generative models. Advances in Neural Information Processing Systems, 2022.
Kim, J., Shah, K., Kontonis, V., Kakade, S., and Chen, S. Train for the worst, plan for the best: Understanding token ordering in masked diffusions, 2025. URL https://arxiv org/ abs/ 2662.06/68L
Leviathan, Y., Kalman, M., and Matias, Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023.
Li, Y., Kirchmeyer, A., Mehta, A.. Qin, Y., Dadachev, B., Papineni, K., Kumar, S., and Risteski, A. Promises and pitfalls generative masked language modeling: Theoretical framework and practical guidelines, 2024. URL https: www.ooggg///oooeoooeoo..oo..eeat /20///0////0......//// 21046.
Lin, C.-Y. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 81, 2004.
Liu, J., Min, S., Zettlemoyer, I.., Choi, Y., and Hajishirzi, H. Infini-gram: Scaling unbounded n-gram language models to trillion tokens. arXiv preprint arXiv:2401. 2024.
Lou, A., Meng, C., and Ermon, S. Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41st International Conference on Machine Learning, pp. 32819-3288 32848. PMLR, 2024.
Lovelace, J., Kishore, V., Chen, Y., and Weinberger, K. Q. Diffusion guided language modeling. arXiv preprint arXiv:2408.0427 2024.
Luden, I., Giulianelli, M., and Fernández, R. Beyond perplexity: Examining temporal generalization in large language models via definition generation. Computational Linguistics in the Netherlands Journal, 13:205-232, 2024.
Marti, U.-V and Bunke, H. Using a statistical language model improve the performance of an hmmm-baeed cursive handwriting recognition system. International journal of Pattern Recognition and Artificial intelligence, 15(01):65 90, 2001.
Meng, C., Choi, K., Song, J., and Ermon, S. Concrete score matching: Generalized score matching for discrete data. In Advances in Neural Information Processing Systems, 2022.
Nie, S., Zhu, F., Du, C., Pang, T., Liu, Q., Zeng, G., Lin, M., and Li, C. Scaling up masked diffusion models on text. arXiv preprint 11X::24400.1814. 2024.
Nie, S., Zhu, F., You, Z., Zhang, X., Ou, J., Hu, J., Zhou, J., Lin, Y., Wen, J.-R., and Li, C. Large language diffusion models. arXiv preprint arXiv:2502.09999, 2025.
Ou, J., Nie, S., Xue, K., Zhu, F., Sun, J., Li, Z., and Li, C. Your absorbing discrete diffusion secretly models the conditional distributions of clean data. arXiv preprint arXiv:2406.037355 2024.
Ouyang, S., Zhang, J. M., Harman, M., and Wang, M. Llm is like a box of chocolates: the non- determinism of chatgpt in code generation. arXiv preprint arXiv:2308, 02828, 2023.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.J. Bleu: a method for automatic evaluation of ma- chine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311 311-318, 2002.
Rastogi, R., Schiff, Y., Hacohen, A., Li, Z., Lee, I., Deng, Y., Sabuncu, M. R., and Kuleshov, V. eemi-parametric inducing point networks and neural processes. arXiv preprint arXiv:2205. 17188 2022.
12

---

Roziere, B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I,, Ellen. X.. Adi, Y., Liu, J., Sauvestre, R.,
Remez, T., Code llaaa: Open foundation models for code. arXiv preprint arXiv:2308. 12950. 2023.
Sahoo, S. S., Arriola, M., Schiff, Y., Gokaslan, A., Marroquin, E., Chiu, J. T., Rush, A., and
Kuleshov, V. Simple and effective masked diffusion language models, 2024.
Schaeffer, R., Miranda, B., and Koyejo, S. Are emergent abilities of large language models a mirage?
Advances in Neural Information Processing Systems, 36, 2024.
Shi, J.. Han, K., Wang, Z., Doucet, A., and Titsias, M. K. Simplified and generalized masked diffuuson for discrete data, arXiv preprint arXiv:2406. 244.02990 2024.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models. In International Con- ference on Learning Representations, 2021a. URL hctps://openreveev.ntsts www.:rrrviiinneefoouu/uu. StIgiarCHLP,
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021b. URL https://openrevies: wttp://ww....oooooooaooo111111..
Sun, and Yang, Difusco: Graph-based diffusion solvers for combinatorial optimization. Ad-
vances in Neural Information Processing Systems, 07137666371,, 2023.
Sutskever, I. Sequence to sequence learning with neural networks. arXiv preprint arXiv:1409.3213 2014.
Team, Q. Qwen2.5: A party of foundation models, Septemher 2024. URL https://quen.n. btchub.io/blgg/// http//lo//weee.555/
Vignac, C., Krawezuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
Wang, G., Schiff, Y., Sahoo, S. S., and Kuleshov, V. Remasking discrete diffusion models with inference-time scaling, 2025. URL https: wwwpaaawww.rogaaaa/aaaaaaaaa http/aab/2503.000000
Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., al. Emergent abilities of large language models. Transactions Machine Learning Research, 2022a.
Wei, J. Wang, X. Schuurmans, D., Bosma, M., ichter, b., Xia, F. Chi. Le, Q. V., and Zhou, D. Chain-of-thought prompting elicits reasoning large language models. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 24824 24837. Curran Associates. Inc., 2022b. URL
www.iis...r....... wwt.riisscccpppppppeeeeeeepp ccppaper files/ /tlle//aaper/222//1110 adt5r066ss222044111107777000020 Paaeraaaaaraa-aaaeeeeaeaeeeeeeee Conference.. pdi
Wei. J., Wang. X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain- of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837,, 2022c.
Wu, Y., Schuster, M., Chen, 2., Le, Q. V., Norouzi, M., Macherey, W., Krikun, M., Cao, Y., Gao, Q., Macherey, K., et al. Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144 2016.
Xu, M., Geffinr, T., Kreis, K., Nic, W., Xu, Y., Leskovec, J., Ermon, S., and Vahdat, A. Energy- based diffusion language models for text generation. arXiv preprint arXiv:2410.21355 2024.
Ye, J., Zheng, 7.,, Bao, Y., Qian, I.., and Gu, Q. Diffusion language models can perform many tasks with scaling and instruction-finetie
arXiv preprint 1211:2338..1221, 2023.
13

---

Ye, J., Xie, Z. Zheng, L., Gao. J., Wu, Z., Jiang. X., Li, Z., and Kong, L. Dream 7b, 2025. URL https://hkum www.p..gt..biii..pp http:///oo/gg/////rraraaaaa
Yu, J., He, R., and Ying, R. Thought propagation: An analogical approach to complex reasoning with large language models, 2024. URL https://arxiv. http://rgggab/aaeeeee 03965
Zhang, H., Dang, M., Peng, N., and Van den Broeck, G. Tractable control for autoregressive lan- guage generation. International Conference on Machine Learning, pp. 09992240945.. PMLR, 2023.
Zhang, S., Wu, L.. Gong, C., and Liu, X. Language rectified flow: Advancing diffusion language generation with probabilistic flows. arXiv preprint arXiv:2403. 16995,, 2024.
Zhao, L., Ding, X., Yu. L., and Akoglu, L. Improving and unifying discrete&<coninuuuus -imee discrete denoising diffusion. arXiv preprint arXiv:2402.0370), 2024.
Zheng, K., Chen, Y., Mao, H., Liu, M.-Y., Zhu, J., and Zhang, Q. Masked diffusion models are
secretly time-agnostic masked models and exploit inaccurate categorical sampling. arXiv preprint arXiv:2409.02908, 2024.
Zheng, L., Yuan, J., Yu, L., and Kong, L. A reparameterized discrete diffusion model for text generation. ArXiv, abs/2302.05737, 2023.
Zhu, T., Zhang, K., Xie, J., and Su, Y. Deductive beam search: Decoding deducible rationale for chain-of-thought reasoning, 2024, URL https: //tp///aavvv/////// org/ aba/2401 17686,
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction (Section M 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.
fine to include aspirational goals as motivation as long as it 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 paper discuss the limitations in Section f
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors 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, c.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 ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and fairnsss.
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 it acknowledged in the paper. The authors should use their best 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.
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]
15

---

Justification:
For each theoretical result, the paper provides the full set of assumptions in Section B and a complete proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or 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 comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The training and testing details are presented in Appendices A and IB.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a 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 re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We will open the code base and data when the paper is published.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:)
/ paips.cc//ubliccguiddes (CodeSSub ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended 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: The training and testing details are presented in Appendices and B.
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 appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We run experiments for times and report standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It OK report I-sgmaa error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computer resources are listed in Appendix E
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpss///oorrrsccccoo//////aaaae
Answer: [Yes]
Justification: The research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work aims for understanding diffusion language models, has no potential malicious or unintended use.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
18

---

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 as 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 mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We only use open source data and synthetic data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. 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: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the cense 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.
19

---

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 documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl 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 pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing 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 contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, 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 deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) 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 as the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM 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: [Yes]
Justification:
We use LLM help with paper writing.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
cc//Comferrecccs//255/11
Appendix
A Details of Preliminary Experiments
A.1 Models and Sampling Strategies Compared
We follow aa (2025) and NNee et (2025) setup experiments GSM8K, MBPP and
HumanEval benchmarks. For each benchmark, we compare the following sampling strategies of different models suggested:
Entropy-based sampling (Ye 2025) applied to Dream-vO-Base -0-Baas--B.. with different sampling steps.
Low-confidence-based sampling (Nie all 2025) applied to LLaDA-80 --A-A----Bae also with different sampling steps.
Left-to-right (AR-style) sampling strategy for Sream-vO-Basee 7B and LLaDA-88 -B--BBassc where one token is generated per step in sequential, left-to-right manner.
Standard auto-regressive generation for Qwen2.5-7B with default settings.
Here, the entropy-based sampling strategy and the low-confidence-base sampling strategy are the recommended sampling strategies for MDMs (Ye et all 2025: INie all 2025). Qwen2.5-7B serves as the standard AR baseline, while the left-to-right sampling strategy of MDMs serves as a naive baseline for the MDMs, aiming to climinate the influence of other contributing factors, including different training datasets training methods.
we manually implemented the left-to-right sampling process. In the case of LLaDA-8PB -BB Base, setting block length-1 during generation naturally obtains the same behavior. This configuration does not stop generation after encountering EOS, which may cause an increased time cost, but our results indicate that this behavior does not affect the overall conclusions.
For
A.2 Settings for GSM8k Experiments
Following Ye all (2025) and etal (2025), we use the widely-adopted im-evaluation-hamaen framework evaluate the performance. For the GSMSK benchmark, we follow prior work and set number of few-shot examples to and the maximum length of answer to 256. assess
GSM8K Accuracy and model efficiency of different models, where efficiency is defined by the in- verse of the execution time measured on 8 Nvidia RTX 4090 GPUs with Huggingface' s transformers library
21

---

In the figure, report the relative accuracy and efficiency of MDMs compared to the baselines. These relative values are computed by dividing the actual accuracy and efficiency by those of the respective baselines Qwen and the MDMs using the left-to-right strategy.
We list the detailed testing configurations for GSM8K in Appendix A.
Dream w/ entropy
Dream w/ left-to-right
LLaDA w/ low-confidence
LLaDA w/ left-to-right
Models
Qwen2.5
Max new tokens
256
256
256
256
256
Block length
N/A Entropy
N/A Sequential N/A
256
1
N/A
Sampling algorithm
Low-confidence (64,128,256)
Sequential
N/A
Sampling steps
(64,128,256)
256
N/A
Temperature
0
0
0
0
0
Table 3: Testing Configurations for GSM8K
A.3 Settings and Results for MBPP Experiments
For the MBPP experiment, the evaluation settings are similar to the GSMSK experiment. Specifi- cally, use 3 few-shot examples and set the maximum answer length to 512, as suggested, to evaluate the MBPP Accuracy and efficiency. The definition of efficiency and the method for computing rela- tive accuracy and efficiency values - by normalizing against the respective baselines are identical those used in the GSM8K evaluation.
The results are presented in Figure EL and the detailed testing configurations for MBPP are listed in Appendix A
Dream w/ entropy
Dream w/ left-to-right
LLaDA w/ low-confidence
LLaDA w/ left-to-right
Models
Qwen2.5
Max new tokens
512
512
512
512
512
Block length
N/A
N/A
512
N/A
Sampling algorithm
Entropy
Sequential N/A
Low-confidence (128,256.512)
Sequential 512
N/A
Sampling steps
[128,256.512]
N/A
Temperature
0.2
0.2
0
0
0
Top P
0.95
0.95
N/A
N/A
N/A
Table 4: Testing Configurations MBPP
A.4 Settings and Results for HumanEval Experiments
For the HumanEval experiment, uate the HumanEval Accuracy and efficiency. The evaluation methods and definitions are identical previous experiments.
zero-shot and set the maximum answer length to 512 to eval-
The results are presented in Figure El and the detailed testing configurations for MBPP are listed in the table below.
22

---

Relative Efficiency & Accuracy MDMs against Auto-RRerresivve Model on MBPP (3 shots)
Relative Efficiency Accuracy of MDMs
with Different Sampling Stralegiee on MBPP (3 shots)
10
Relative Acouracy
Relative Accuracy
14
Lower Efficiency Higher Acouracy
Higher Elliciency
Lower Efficiency Highor Accuracy
Higher Efficiency Higher Accuracy
Higher Accuracy
12
step 512
1.0
stop
atae Efiilencc
1.0
Helative Efficenncy
Higher Efficiency
Lower Efficiency Lower Accuracy
0.5
xtop Jlop 258
Lower Accuracy
step 258
0.6
[Drear -DBaae 75
0.0
[D Base 78) relrove (Drasms-t-Baae Base- att-l--rggnt
step 128
Joane' 5-77g
readuve
128
0031250 0.125
2.0
0.25
80
Figure 2: Efficiency and aceuracy of MDMs on MBPP (3-shot): Similar to the GSM8K experiment, the left figure uses Qwen2.5-7B as the evaluation baseline and compares the MBPP relative accuracy and efficiency Dream-v0-Base-77 and LLaDA-8B-Base across different sampling steps. The origin can be considered the baseline result. The first quadrant demonstrates models that can simultaneously achieve higher efficiency and accuracy. From the figure, we can see that the MDMs all fall into the third quadrant, indicating lower efficiency and lower performance. The right figure uses baseline in which the MDMs are constrained to generate the left-most masked token at each step, effectively mimicking auto-regressive decoding. Still, even under this setting, none of the configurations fall into the first quadrant.
Dream w/ entropy
Dream w/ left-to-right
LLaDA w/ low-confidence
LLaDA w/ left-to-right
Models
Qwen2.5
Max new tokens
512
512
512
512
512
Block length
N/A
N/A
512
I
N/A
Sampling algorithm
Entropy
Sequential
Low-confidence (128,256.512)
Sequential
N/A
Sampling steps
(256,512)
N/A
512
N/A
Temperature
0.2
0.2
0
0
0
Top P
0.95
0.95
N/A
N/A
N/A
Table 5: Testing Configurations for HumanEval
B Further Discussion
B.1 Various Metrics in NLP Tasks.
Evaluation metrics in NLP tasks are inherently tied to the specific objectives and requirements of their respective domains. For general language modeling tasks, perplexity (Jelinek et all 1977: Devim all 2019) remains the metric of choice due its ability to capture model's predictive performance effectively. However, domain-specific tasks often demand more specialized evaluation criteria. For instance, in machine translation (Bahdanaul 2014; Wu all 2016), the BLEU score is widely regarded as a standard measure of translation quality (Papmen et all 2002), while text gen- eration tasks (Sutskever. 20T2) frequently rely on metries such as ROUGE assess output fidelity (Li 2004). Similarly. tasks requiring reasoning (Wer all (022c)) such as mathematics (Bubeck allll 200%)) code generation (Rozıere etall 2023; Ouyang all 2023), commonly adopt accuracy as an intuitive and straightforward measure of success.
B.2 Discussion Regarding the Empirical Observations.
The above results reveal that MDMs can efficiently generate low-TER sentences but may incur higher costs when evaluating the generation under SER. One might think these results are contra- dictory. Note that several previous works have already shown that TER (a.k.a perplexity) may not reflect model's true performance in solving several meg-seeuence understanding tasks (Huang
X

---

Relative Efficiency & Accuracy of MDMs against Ruto-Regressive Model on HumanEval
Relative Efficiency Accuracy of MDMs with Different Sampling Strategies on HumanEval
16-
Reletive Acouracy
Relative Accuracy
14
Lower Efficiency Higher Accuracy
Higher Efficiency
Lower Efficiency Higher Accuracy
Higher Efficiency
Higher Accuracy
Higher Accuracy
12
stop 012
1.0
seep 512
Reatire Elficency
1.0
512
Reaaive Effitency
Higher Efficiency
Lower Efficiency Lower Accuracy
0.5
Lower Accuracy
[h readive fare lif
R.Lab--s ap Blad) sistive to E LLDDA ds Bass left tig
0.6
stop Srittop 206
[Drean -DBaae 75
0.0
stop 200
[Laata-dttflaae Joane' 5.77g
ship 125
0031250 0.12
2.5
32.0
0:125
0.25
8.0
Figure 3: Efficiency and accuracy of MDMs on HumanEval: Similar to above, the left figure uses Qwen2.5-7B the evaluation baseline and compares the HumanEval relative accuracy and effi- ciency of Dream-vO-Base-77 and LLaDA-8B-Bas across different sampling steps. The origin can be considered as the baseline result. The first quadrant demonstrates models that can simultaneously accieve higher efficiency and accuracy. From the figure, we can see that the MDMs all fall into the third quadrant, indicating lower efficiency and lower performance. The right figure uses baseline in which the MDMs are constrained to generate the left-most masked token at each step, effectively mimicking auto-regressive decoding. Still, even under this setting, none of the configurations fall into the first quadrant.
atall 2022: Hu of all 2024 et 2024). Thus, it is natural to arrive at different conclusions depending the metric used. Moreover, many practical scenarios have shown that the choice of evaluation metric significantly influences the conclusion of other problems (see Appendix [В for various metrics NLP tasks). For instance, while the community has previously focused on the emergence phenomenon, recent works by all (2122)) and Schacfter al (2024) demonstrate that this phenomenon may stem from the use of non-smooth evaluation metrics.
B.3 Extend to Efficient Sampling Strategies
In Sahoo all (MU24) and Oullta (2112)), an efficient sampling strategy ddpm_ cache is proposed, which can reduce the sampling time by a constant order of magnitude. Specifically, this sampler is approximately 3-4 times faster than previously used samplers when the number of sampling steps is large. In this section, we discuss the influence of ddpm_ccccte cache on our conclusions under different sampling steps.
First, we briefly introduce the principles of ddpm_cachal cache. It utilizes the observation that if no loca- tions are sampled at given step, the sequence remains unchanged. Consequently, when the reverse model is not conditioned on time, the cached value computed during the first time this sequence went through the reverse model can be reused, instead of going through the reverse model again.
This sampling strategy does not affect our main theorems, they are based solely on the sampled locations at each step, while unsampled locations are not considered. As for the evaluation metrics for computational efficiency in our experiments, we break it down into the following two cases:
1. When the number of sampling steps is much smaller than the sequence length, which the primary scenario we focus on, the expectation of steps where no new locations are sampled is relatively low, resulting in a computational cost that is nearly linear with respect to the number of sampling steps.
2. As the number of sampling steps becomes larger, the computational cost is mainly depen- dent on the number of valid steps where at least one location is sampled. As a matter of fact, the expectation of the number of valid steps increases the number of sampling steps increases, and the maximum number of valid steps is equal to the number of sampling steps. In this case, the MDMs offer computational advantage over auto-regressive models.
Based on the above conclusions, we can find that for tasks requiring a low TER, using ddpm cache can further accelerate the generation of MDMs, suggesting high efficiency. Conversely, for tasks that
24

---

demand a low SER, we have shown that the number of sampling steps need to be large enough, such that MDMs can not generate with low cost even when using ddpm_cache. Therefore, we extend our findings to MDMs with efficient sampling strategies.
C Auxiliary Lemma
In this section, we present some technical lemmas the proof of our main results.
Lemma C.1 (Upper Bound for Multi-tokens Sampling). Let X X2...2..... Xx) [N] be random vector following the distribution 9, where each component X; follows the marginal distri- bution 9, Define X X2........ .x)) ~ p as another random vector, where the components X; sampled independently according ps- Let 6 between and satisfies the inequality:
then, the KL divergence
DKL(gl S (k- 1) log N + kg.
Proof. Using the chain rule for probabilities, the KI. divergence can be written as:
&
g:(2 xx))
DKL(all)) = Eg
log
pi(x;)
where X<i (01....,33-11 For i 1, there no preceding variables,
Ey log (x1)) ]
DKi(ailli)).
pi (zr1)
For i 1, we bound:
Ey log (x; xx(s)
Eng log (xx)))
px()))
Decomposing E.g [log(1 //px(ar))) we get:
q: (2xz)
Eg
log
Eyg
log
+ Eg
log
Ps (x.))
P. (.r;)
(2.
The first term is DKL (4x [p:), and the second term is - EEg llog ge (2:)), which represents the entropy of ds- Since the entropy of any distribution over [N] is at most log N, we have:
-B, [log qi (x::)] S log
Thus:
Ci xxi)
By log
S DKI.(ullps)) + log N.
Pi(#z))
Summing over all I,.... ....., hi, we obtain:
Eg log (x x<<s) )}
DKL (gllp)
< (gi(ellpr)) Σ (DKL(allP)) + log N).
pi(x;)
Reorganizing, we have:
DRi(alle) Σ (Ku((ilpp)) (k: 1) log N.
Since DKL (q: (Ip:) S 8 for all i, the total sum of marginal KL divergences is bounded by kō. There- fore:
DKL(gll)) S k8 + (k 1) log N.
This completes the proof.
25

---

Lemma C.2 (Chernoff Bound). Let XI...., Xn be independent random variables taking values in (0, 13. Define X Ei=1 X; as the sum of these independent random variables, and let μt [[[] denote the expected value of X. Then, the following probabilistic bounds hold:
Pr(X 2 (1 6))) 5 243
for 5 2 O,
for 0 < 5 < 1. Lemma C.3 (Pinsker's Inequality). Let p and q be two probability distributions. Then, the total variation distance between these distributions satisfies:
Pr(X S (1 8)₂) S S
Drv(p, 4) S <V V Via
Specifically, since Drv (p. q) = [p gll the following inequality holds:
1|p- r|lو S 22DrI,
D Proof for Theorem
This section provides the complete proof of Theorem + We first outline the proof strategy, then present the detailed arguments with supporting lemmas and definitions.
Our proof rests on reformulating TER bounds through KL divergence and carefully analyzing de- pendencies in the f--ram setting. The key steps are:
We establish a connection between the perplexity of the discrete diffusion model and the KL divergence between generated and data distributions. This involves deriving an upper bound on KL divergence using expected divergence over reverse processes (Lemma D and decomposing this divergence into per-step conditional KL terms (Lemma D.
We analyze n-gram model dependencies through rigorous characterization of reverse pro- cesses (Definition D.I)) and separators(11 1) continuous sampled tokens that create inde- pendent intervals (Definition D.4). This leads to precise formulation of per-step depen- dencies using these separators (Definition D.S)
We derive an upper bound for the KL divergence between generated and data distributions based on the number of per-step dependencies (Lemmas DX and D
We employ probabilistic bounds to analyze and bound the number of per-step dependencies (Lemmas C.ll D and II
Finally, we demonstrate the existence of a schedule achieving small KL divergence with O 0(n-²) steps by constructing efficient sampling schedule using the preceding lemmas (Lemma D.I2).
To begin the formal proof, we introduce key definitions for analyzing the discrete diffusion process. Consider a masking schedule ar and sequence of sampling time steps 4 N For a sequence of length L, we define an instance of the discretization of the reverse process as follows:
Definition D.1 (An Instance of Reverse Process). Let = (M1, M2..... M, represent a reverse process, where M; {45} } denotes the set of locations sampled step i. For sequence of length L, the sets M, satisfy the following conditions:
U KE[N]
= and
n [E[N]
M, = 0.
Specifically, we denote Mes as the union of all locations sampled prior to step 4;
Me M,
J<1
Under a given instance of the reverse process т, at each time step 4; = Nyi the set locations M; (4,j) is sampled. Let Φ;; denote the tokens associated with the locations sampled at time step 1,. Given the masking schedule ar, there exist multiple possible instances of the reverse process. We denote the distribution over these instances by REVR((a, (a,, N, L).
26

---

Lemma D.2 (KL Divergence Upper Bound for the Masking Schedule). Let denote the data dis- tribution over sequences of length and let p denote the distribution over sequences of length 1. generated by the reverse model po with masking schedule and N sampling steps. The KI. divergence between q and p satisfies the following upper bound:
DKL(gll)) S EE.-REVROo,,N DKL (gllp(-17)).
where the expectation is taken over the distribution of reverse processes T induced by REVR(a,, L).
Proof. Let X' denote the set of all possible generated sequences. Then, the KL divergence between q and p given by:
((x) log ((x)) p(x)
(xl(a
Σ
Let denote the distribution over reverse processes REVR(( N, L). Due to the convexity of log 1. z. by applying Jensen's 's inequality, we can obtain:
log p(æ)
log Σ. ((T) p(alT) S
Σ ((T)) log p(æ) r)
Since data distribution q is independent of reverse process T:
g(x))= g(xlT), Vr.
Therefore, have:
((x)
Σ h(()) log g(x:TT)
log p(x)
p(x]T)
Substituting this back, we can get the final result:
DRI(allp) < ΣV E ((T)(()) log (x
p(x)T)
Σ ((()) g(<l|) log ((<]TT)
p(x]TT
*EA
EEV. DKL (g (g( (1)
E. DKL (xlllp((+7))
We next establish upper bound for the KL divergence between the distribution of sequenees sampled under an instance of the reverse process and the ground-truth distribution in the n- n-gram setting. To achieve this, leverage the chain rule for KL divergence, which allows decomposi- tion of the KL. divergence of the entire sequence into a summation of the KI. divergences at each individual step of the process.
Lemma D.3 (KL Divergence Decomposition for the Reverse Process). Consider an instance of (M.,, Mx) REVR(a,, N, L). Let ă; denote the set of tokens corresponding to the locations sampled at time step tú and सςi denote the set of tokens sampled all steps prior step The KL divergence between the ground-truth distribution q and the distribution Pr generated by the reverse process T and reverse model satisfies the following decomposition:
reverse process
DRL(Ulle>) Σ F.. Ex DKL (gl 1p (c)))
Proof. Given the reverse process т, the reverse model samples ã; sequentially from i = to N, and the probability of sampling ã; at step i; depends only on the previously sampled tokens E<;- Therefore, the distribution p(x:) can be factorized as:
(x) =
Pr (0. E2).
27

---

On the other hand, since the data distribution is independent of the reverse process т, it can similarly be decomposed as:
((x) II (
Applying the chain rule for KL divergence, we obtain:
DKL(allp=) Σ Es,,
Next, derive upper bound for the KI. divergence each step of the reverse process. In the n-gram setting, it is important to note that, at step 4, the tokens Fiy and Fi,y are conditionally independent if there are at least n consecutive tokens between the positions liy and ley that have already been sampled prior to step Under this condition, sampling these two tokens simultaneously incurs no sampling error, as the distributions of Fig and Fi are independent.
To formalize this concept, we introduce measure of dependencies among the tokens sampled in M; during the reverse process, For the i-th reverse step in the n-gram setting, the number of dependencies, denoted DEP,, (,M,, Mes). determined by the structure of Mei. Specifically, depends on the number of separators in Mei denoted as SEP, (Mei), as described in the following definition.
Definition D.4 (Number of Separators in Reverse Step). Consider reverse process (M, MM,,,,,...,MN' where Mes = Ujci-M, represents the union of all previously sampled location sets. The set Mec can be partitioned into several contiguous segments. Let 5,, S2. Ss denote the segments containing at least - 1 consecutive tokens fie../S)) 2 1) with the max- imum k. We refer these segments as separators, and denote the number of separators in the set Mes as:
SF.,( max k
8.l. S 1- Sj CMes, Aj E
S 0. Vj
Note that if contiguous segment S in Mai contains least d(n 1) consecutive tokens, where d an integer, then S consists of at least d separators.
Definition D.5 (Number of Dependencies in a Reverse Step). Consider a reverse process T (M,, MM,,MM The separators of Mcs divide the sequence into at most SEP,,MM. + disjoint intervals In, I2...... Ig. Under the n-gram setting. the sampling within each interval is in- dependent of the sampling in other intervals. The number of dependencies of step t; is defined as the number of intervals Ip (for p 1,...,
......,)) 1)) that contain at least one location in M,:
DEP n (Mi, (M., MMl
II
where Il is the indicator function.
To illustrate this definition, we provide the following example:
Example D.6 (Computing Dependencies in the n-gram Setting). Consider a token sequence of length 10, denoted as x (21, 22, Iiu), with n Let the previously sampled location set be M = (2,3, 4, 6, 7} and the current location set be M2 = 5,9].
Identify contiguous segments in Mes containing at least n - = 3 consecutive tokens: The set Mei [2, 3, 6) forms the following contiguous segments:
(2,3,4} and {6.7].
Only the segment {2, 3, 4} contains at least n
consecutive tokens. Thus, we have
S = (2, 3, 4). The sequence is then divided into the following disjoint intervals:
Iι (1), I {5, 6, 8,8,9.94. 10).
28

---

2. Determine which intervals overlap with M, = (1, 5) Token belongs to interval Z1. and tokens and belong to interval Iz.
3. Compute the number of dependencies: The number of dependencies is:
DMP,, Mei) = w
II n M, -
(2.3. 4]
{6. 7)
210
T1
Z2
(1)
(2,3, 4)
(5, 7,8,9,
Figure 4: Illustration of the example for computing dependencies the n-gram setting. Tokens T2, 33, T4, x7 (blue) represent the previously sampled location Mci, forming two contigu- ous segments: {2.3, 3, } and {6, 7) The current sampled locations #1, 45, Dg (red) overlap with disjoint intervals Zi (1} and IN (5, 6, 7, 7,8,9 9, 10). The number of dependencies is computed
as DEP,, (M, [M,] (number of overlapping intervals) = 3 - 2 = 1.
This example demonstrates how dependencies are computed, highlighting the interaction between previously sampled locations and the current reverse step. Such formalization is critical for under- standing the efficiency and accuracy of discrete diffusion processes.
Finally, we extend this concept to define the total number of dependencies across an entire reverse process:
Definition D.7 (Number of Dependencies in Reverse Process). Consider reverse process M2.,M Under the n-gram setting, the total number of dependencies in the process is defined as the of the dependencies across all steps:
N
DEP DEP,. = Σ
DEP D Mci
Using the definition of DEP, (T), we can bound the KL divergence between the distribution of sequences sampled under an instance of the reverse process and the ground-truth distribution the n-gram setting.
Lemma D.8 (KL Divergence Upper Bound for the Instance of Reverse Process). Let q denote the data distribution for sequences of length L, and let p denote the distribution of sequences of length L generated by reverse model pa via the reverse process T. Under Assumption 1 the following
upper bound holds:
D s DEP,. log [V] + Leqearinng
where V denote the vocabulary.
Proof. Using Lemma D.3. we have:
DRL(ulle>) Σ
Ex, D Dx..((( (e)))
For each time step 4;
Egc: ( (0 = Re Σ
((x:(0te log
æ.eV Mil
29

---

Given M; and Mei the tokens ã; at step t2 can be partitioned into independently sampled token sets a. (1) x. (m) with Ky denoting the size of each token set:
k | j [m]] m M,l DEP, (M,,
Using the independence, for each Øes, we can decompose the sum into:
q (c<))
log g( ( (<cs)
Σ
g( <1)) log
( (1) [2t)
Pr ( Eei)
p+ ( (8<1)
(1)
@,EViM
EV"
m
Σ
DKL (g
Tes (es) Tci).
Under Assumption 11 the KL divergence between 9 and po is bounded by:
DEL (1ooo (=))) ax:))
éleamingg
Ao L and Ft.
By Lemma we know that:
(1)
(1) (i)))) S (kj 1) log D1 + ky kéeleannngg
Substituting back:
q +c)
Σ ga log
(k) - 1) log [ + ky Elearning
Dr (
B,EV M,l
==1
Using the fact that
E - 1)= MM m m (M;
Σ k2 = M.M )=1
we can obtain:
Ex DKL (akL(q(())) (<<(//<<)))) ( S DEP, (M,, log [V] + [M,[Eeernnigg
Thus, combined with the definition of DEP, (T) and Pt = p(-TT), we can draw the final conclusion:
(xl(ell((1F)) -
(DEP,, (M; Mes) | M//Agnnnnig))
1=1
= DDP log |V]
Lejearning
The above Lemma directly leads to the bound for the KL divergence between the distribution of sequences generated by the reverse model with a given masking schedule and the ground-truth dis- tribution in the n-gram setting.
Lemma D.9 (KL Divergence Upper Bound for Masking Schedule). Let denote the data dis- tribution over sequences of length L, and let denote the distribution over sequences of length L generated by the reverse model pe with masking schedule o4 and N reverse steps. Under Assump- tion 1. the KL divergence between and satisfies the following upper bound:
DKL(gllp) < log M
E, B. (M, + Lejeernigg
Proof. By Lemma D.2. can obtain:
(kl(g & E,, DEL (xl((lp((11)))
Applying Lemma D.S to the instances of reverse process, conclude that:
DKl(g) & E.
DEP, n (M, (M,) V + Letearning
=log Σ E REVR (M,, + Lejerning.
30

---

For the final estimation, we need to derive upper bound for the expected number of dependencies each reverse step. First, we use Chernoff Bound to control the number of separators and new locations at each reverse step for a given masking schedule.
Lemma D.10 (Bounds on Separator and New Location Count at Each Reverse Step). Given a se- quence of length L. masking schedule at, and N reverse steps. Assume that L is divisible by NN' let NEW denote the number of locations sampled at step t, and sEP,, n denote the number of separators in the previously sampled locations. Under the n n-gram setting, the following bounds hold for NEW and SEP.:
1. Given the time step t, N
Pr SEP, I Tpp
Ly S 8(n-1),
2(n
LA,
Pr 2 2T.,)) $
where Pi - and 6; Clt. -
Proof. Given a masking schedule or, using the expression true reverse process in Equation (2) and a1 = 0, we can compute the probability p(*) of a token being sampled at time step t to be:
Cltz
Oite-1
oit
az: a4, 84.
Octy-1
O11-1
Therefore, 8; is the probability of location being sampled at time step 4, Summing up 6; we can know that p. Σド= ōg is the probability of a location being sampled prior time step t,.
+ intervals, each of length n 1. To derive bound for SEP,, we partition the sequence into n-1 For given interval, the probability that all locations within the interval have been sampled prior to step & is p. 2-11_ Define X, if the locations in the j-th interval have been sampled prior t, and Xj 0 otherwise. The random variables X1, X2, X are independent and satisfy the following expectation:
Lp
B REVE
Xj
11
==1
By the definition of SEP,,, n. we know that:
SEP
Xj.
Applying Lemma 2 to the sum of Xj, we derive:
Lp n-1 2(n 1)
Lp 2(n - 1)
Lp 5
Pr SEP,
< Pr
Xj
Next, we consider the bound for NEW. Given that the sequence contains L, locations and the probability of sampling any specific location step & is 8,, the expected number of new locations sampled at f; is given by:
E E, NEW LS,,
Since the sampling of each location occurs independently. applying Lemma we have:
Pr (NEW 2Lo,) -
Using the above lemma, we can divide the estimation for the number of dependencies into three cases, and derive the bound case by case. This is achieved by using a variety of means and careful estimations.
31

---

Lemma D.11 (Upper Bound for the Expectation of Dependencies at Each Reverse Step). Given a sequence of length L, masking schedule at, and N reverse steps. Assume Lô; then the expected number of dependencies at time step 1 N N satisfies:
9
C(n 1))83
3+ Lo,
where p; -it--1 8, ar, - and C is a constant.
Proof. By Lemma D.O. at step tús the following bounds hold:
Lp:
Pr SEP, S
2(n S BLH-17
Ld
(NEW 2 2L8.) S
Since DEP, (M, Mae 2 0, its expectation can be decomposed into three components:
(r.-REVR(L.O..) DEP, (M,, Mei) Pr (NEW 2Ld,) NEW22L4,
REVRR.((, DEP, DE (M, (Case 1)
Pr SEP, S Lp
NEW < <2L6,)
2(n
E, N) DEP,, (M;
(Case 2)
SEP S by 1)-1)
<2W
Lpp-11
+ Pr SEP, n 2(n 2 1)
NEW < 2L..)
EF REVR(( DEP, (M;
(Case 3)
SEP,> > 2x-1
<218
We estimate these three cases separately.
Case 1: NEW 2 2Ld;
By the definitions of (EP,(M,, Mcx) and NEW, we have:
(M,, S [M, = NEW.
Substituting this into the estimation, we obtain:
Pr (NEW 2 Pr (NEW 2 2L.,) (LO,)-E,-me BE-REV((L.O,., DEP, (M; P NEW22L6;
2, -EVRR NEW
NEW 22L6,
Since DEP,, nn (M;, 2 0, the expectation can be expressed an integral of the tail probability:
1 too
REVRLL.... NEW NEW22L6;
Pr(NEW 2 x NEW 2 2L8)) da.
2L6
directly follows that:
( +00
Pr (NEW 2 2LX,) E, RE NY NEW = (NEW 2 2L5))
PN 2 & NEW 2 2L5,) dr
NEW22L8,
226..
Pr Pr(NEW 2 x NEW PT Pr PN 2 2T.5,) da
2L0
Pr (NEW 2 x) dx.
2L8;
Using the same trick as Lemma D.10 applying Lemma CN Pr (NEW x)
we can derive the bound for probability
(x-16,)) #4L6,
PN(NEW 2 x) Se
32

---

Note that NEW Σ L, we only need to consider 26, S 1. In this case, we have:
1"
L
(a-La)2
Pr (NEW 2 x) dx -
e ooting
dx
216.
2L5.
Let x- L5; E [L,, L(1 - -,)], the integral can be rewritten as:
+00
((1-81)
(N 2 x) dr S
v-225 dy-
21.6.
Observe that y + 2L5, S 3y, we can obtain:
1(1-6))
Pr 2 x)dx V
e by = (e-
14
111-611
3e
14
3
(1 (1-e*
111-261
218,
Lb;
Using the fact that e -
1
for x 2 O, we have the upper bound:
1+
(1 (1- Li2 ((1-26))
L6;
3e
S 3e
S
3 Ld;
Combining the above results, we know that:
9
Pr (NEW 2 2LO,) E, REVRE. DEP ne (M;, NEW22L8;
3 Lò;
Lp Case 2: SEP, 2[n-T] and NEW < 2L0,
Similar to Case 1, we have:
DEP DEP (M; S NEW < 2L,,
so the expectation also follows:
E, DEP, (M, < 2L5,.
SEP Lp T[
NEW<2L6,
Using the probability bound, it follows that:
Pr SEP S Lp n-1 2(n - 1)'
Lp n-
Lp Lp 8(m
NEW < 2L5;
S Pr SEP, V
Se
2 -
Since e < I+x for x 2 0:
Lo B[n
8(n - 1) Lp 1 + 8(n 1)
Combining these results, we obtain:
Lpp-1 NEW < 2L0; E. BE-REEV(LL., DEP, DEP,(M, (M, 5 SEP 1.
16(n 1)L5; Lp, 8(n 1)
Pr SEP,, < 2(n 11'
NEW <2L6.
Case 3: SEP,,
Lp. 2[ and NEW < 2L0.
Apparently, we have:
Pr SEP, > Lp
2(n 1)' NEW < 2L0,)
-1.
Given a, b, let En,D DEP, in (M,, Mez)) denote the expectation DEP,, i (Mi dition of SEP,, and NEW b. In other words:
under the con-
E.D DEP, (M.
E REVR(L. DEP, (M, SEP =0
NEW=b
33

---

Since all the locations are sampled independently, and DEP,, DE,,.MM,.MMa depends only on the relative positions of separators in MMs and the new locations in MM, the expectation Ba,b DEP,, (M; Mex) only depends on the ordering of separators and new locations.
b positions (not locations) in order. We regard the process of ordering separators and new locations as the process of choosing b positions randomly from zj. For 1 S. j S a+ b define Xj 1 if æ and 4j+1 are both new locations, and Xj 0 otherwise. By the definition of DEP, (M; Mex), we can obtain:
Assume "1,"' Fb
a++h-1
(M, = Σ Xj.
J=1
Since the b new locations are chosen randomly, the probability of Xj can be calculated as:
c a+bb2-
b(b 1)
Pr(X; =1
a+b
(a + b)(a + b-1) 1)
Therefore, the expectation of X, is:
b(b 1)
EX,
(a + () + b b-1)
Summing up. have:
a+
b(b 1)
Ea, DEP n Mc, = E
Σ (a 1)EX;
a +
Lp, n-1 1) and b < 2Lo; we can derive the upper bound for any a, b:
Since
b(b 1)
b(b - 1)
2L5,(2L0; -
8(n L)
a
Lp" 2[n +
Lp" + 2Ld
P. + 4(n 1)6
1[n
Since this holds for all a and b, we can obtain:
Lp
Pr SEP,
2(n 1) NEW < <2L0:)
E REVRI( DEP, (Mi.,.MMMMM) SEP, 2n"
2(--T) NEW-2L6,
DEP, DEP,(M, (MM,,
SEP,> T. N2W-
Σ
Pr(SEP, NEW b) Ea, DEP, (M;
Lr 2(-1)) b<2Ld,
8 LO?
P.
n- 4(n 1)6:
Summarize the above proof:
Combining the above three cases, we can obtain:
9
16(n 1)
8(n 1)
E...REV((L.o..)) DEP, DEP.. (M,, 3+ Lo,
+
Lp +8(n 1)
P. 4(n 1)8,
If we have the assumption L5; 2 1, is easy to find that:
16(n - 1)8;
8(n 1)
Ey-REVR(LO...) DEP, (M:, 5
+
3 + Lob
P 1n-
16(n 1)T
8(n 1)T.5?
+
3 + L8;
p/ n-
C(n - 1)
+
3 + LP;
P
34

---

Where C' = 24 is a constant.
Finally, derive the upper bound for the KL divergence between the distribution of sequences generated by the reverse model and the ground-trun truth distribution the n gram setting.
Lemma D.12 (Efficient Sampling with Small KL Divergence). Let denote the data distribution over sequences of length L, and p denote the distribution over sequences of length L generated by the reverse model with masking schedule and N reverse steps. Assume that satisfies
Assumption
1
For any >> O, there exists masking schedule ax such that, for L 2 3C(n-1) with
N =0
sampling steps, the KL. divergence between q and p satisfies:
(gl(g) L log [V]
I 4e + Clearning
log [V]
Proof. By Lemma D. know that:
N
DKL(ellp) s log [V]
Σ E RE DEP,, DM,,,M,, + Lejearning
Note that at step ti, the reverse process can be bounded using Lemma Mll By reviewing our proof process, it is easy that substitute DEP, (MM1Me1)) for (IM1l 1) log [V], where V
stands for the vocabulary. By the definition of 6, we know that:
BN (IM1) 1) log VI (61 T. 1) log |
Applying Lemma D to DEP, (M, Mc LÓ; 2 1, can obtain:
N
9
C(n ((m=1)LO7
(Kl(g s 61 log | + log V
Σ
+
+ LEjearning
+ Lo;
P, 1-1
1=2
By the definition of pt, we know that p2 = 61 For any small schedule:
0, consider the following masking
81 c, 5 e"
P. -, + (i 2)8,
Vi 2 2.
C(n 1)'
Then, for L }. the KL divergence can be bounded by:
DKl(qlp) L Log [V]
S
9(N - 1)
+
Σ
N
C(n - 1)8²
élearning log [
L(3 + Lg)
P Pp-1
1=2
= c 9(1 - 61)
C'n 1)82
N
C(n 1)82
Elearnnng log [
L5(3 + L6)
81
8n-1
(8) + 16)
9
C(n 1)82
C(n 1)8²
Clearning
sc+ L5(3 + L8)
8
(6) + 18)
log |
By simple calculations, we know that:
9
3
Se,
if >
Lö(3 + L8)
de2
is clear that < 1, so:
C(n 1182
< ed < E.
67
35

---

Since x is convex on [0, +oo), the accumulation can be bounded by:
N-2 C(n 1)82
N-2
C(n 1)82-n
1
(d1 26)m
+1)
E=1
8
+00
1
S C(nn 1)82-n
( + x)
dr
(=1
0 n-1
C(n 1)82-n
1
81
C6
87-1
S
Combining the above, we have:
(gl(g)
Qearning
S 4c +
L log [
log [V]
Meanwhile, the time step is limited by:
1
81
1
N
1
0
8
and the lower bound for L:
3C 1)
de2
T
t+
Combining the above lemmas, we can prove Theorem 4.2 by breaking the expression of log (ER(p) into two parts.
Theorem D.13 (TER Bounds for n- G-Gram Language Generation). For any n-gram language q and any e > O, let pe denote the reverse model and L denote the sequence length. The distribution over sequences generated by py is denoted as p. For any 0 == under Assumption H. there
exists a masking schedule a4 such that, with = 0 n sampling steps, the perplexity of the MDM is upper-bounded by:
log TER(P) S log TER(q) + Cleaming + 4c lol VI.
Proof. By Lemma 12122 for any L > ( n-1
ento.s) ). there exists a masking schedule ag with N
2-1 sampling steps satisfying:
(gl(gl
Gearning
< 4e +
L log [V]
log [V]
In other words:
g(z) p(x)
Bayy log
< 4e log [V] + Cleariing
L
By the definition of TER, we have:
logp(x)
(-log log g(2r) + log g(x) p(x:)
log TER(p) = Enng
Earw
T.
Note that:
log g(x))
log TER(g) Egaong
Baon loog q(æz).
x
We can obtain:
log TER(p)
log TER(g) + Elearning + 4e log (/.
36

---

E Proof for Theorem 33 and Theorem 4.4
E.1 Proof for Theorem
In this section, we aim to derive the upper bound for the SER of generated sequences with sufficient reverse steps. First, we argue that, given making schedule at,, with sufficient steps, the probability of sampling multiple locations in the sequence at the same time can be very low.
Lemma E.1 (Low Probability of Simultaneous Sampling with Sufficient Steps). Given a sequence of length L and masking schedule at, For any > O, there exists Ng. such that for any N Z Ng. with N reverse steps, the probability Pmull of sampling multiple locations in the sequence at the same time satisfies:
Pmnul
Proof. By Lemma DJI. know that the probability of location being sampled at time step
N-1 N is:
6, = at - 0t = = - aN aN
Since all the locations are sampled independently, for two distinct locations * j in the sequence. the probability that and j are sampled simultaneously is:
Pij Σ 87.
Summing up Ps.j. the probability of having two locations a=sampled simultaneously can be bounded by:
1(L-1)
Σ
Pmaul
2
Since a continuous on [0, 1]. we know that uniformly continuous. Therefore, for any > there exists No > 0 that satisfies:
2c
l0g agy < L(L-
Vz,y E [0, 1]. yl < No
In this case, for N > No. we know that:
2e
[6. = 10N a N-N-it1
Vi E [N].
T(L-1
Combining with the fact that ΣN 1==1 5, = 1, we can obtain:
L(L 1)
Pmnul
de d3
2
JE[N]
Next, we consider the SER increase due the learning error. Specifically, we only investigate the case where all the locations are sampled at different steps.
Lemma E.2 (Accurate Step-by-Step Generation with Low Learning Error). Let q denote any HMM, and let py represent the reverse model under arbitrary masking schedule, where is the se- quence length. Let denote the distribution over sequences generated by pe- Under Assump- tion H.Il with learning error Eleorning < T, 8 0, and given instance of reverse process = -M,,M2,,- ,MN) with [Mill < 1, let Pace denote the probability of generating a valid sequence. Then Pace satisfies:
Pare 2 e
Proof. Since |Mil S we only need to consider the steps where one token sampled. Let d denote the previously sampled tokens, and ã, denote the token sampled at the current step. If w
37

---

is can later form valid sequence, let Xr denote the set of valid choices for Σt. In other words, if Te N, then the combination of ø; and o, is can later form valid sequence, or more intuitively:
2oje Ttt) > O.
Under Assumption we know that:
Dkr. Propegoee(2 āz,) (P)o( [+)) < élearning
Since is assumed that 0 log 0 = we have:
Goje(Fe (t) (0 xx)
Σ E,E
(
Tt) log
Clearning
Equivalently, we have:
Goje @+)) log po (x's (t.)
Eleaming
2aje (Ie ab:)
Ine Ex
Due to the concavity of log v. by Jensen's Inequality, we can obtain:
( (zt) log pa (.))
po po Tt:)
log
Coje(Zz at))
log Σ
pa it).
Goje (xt xx,)
40je e
(t))
K,EX
L
ar E.Y
Therefore, the probability that each step remains valid satisfies:
Σ
T4) 2 e Choning 2 -
Since there are L locations in the sequence, the probability of generating a valid sequence bounded by:
Pace 2 (E 4-L = =
Combining the above lemmas, we can derive the upper bound of SER by taking sufficient reverse steps and small learning error.
Theorem E.3 (Accurate Generation of HMM with Sufficient Steps). Let denote any HMM, and let po represent the reverse model under an arbitrary masking schedule, where the sequence length. Let p denote the distribution over sequences generated by pa- Under Assumption I.ll with learning error Elearning < x44), and given sufficient number of reverse steps, the sequence error rate SER(p) of the generated text satisfies
SER(p) S 8.
Proof. For 5 > 0, we know that:
1-8
By Lemma B. given the masking schedule at, there exists No. for N No and N reverse steps, the probability of sampling multiple locations in the sequence at the same time is bounded by:
1
Pmuu 1
other words, the probability of sampling all the locations at different steps at least L-8 By Lemma EM2, for each reverse process which satisfies that all the locations are sampled at different steps, the probability generating a valid sequence is lower bounded by:
Pace 2
Therefore, the sequence error rate SER satisfies:
1-6
SER(p) <
8.
e
38

---

E.2 Proof for Theorem 1
In the section, we aim to find an example (Example E.ll with high sequence enror rate. To present this example, we begin with a special class of languages defined under the interval setting:
Definition E.4 (Interval Setting). Consider a sequence of length L, which is divided equally into M intervals I,, I2, _IM, each of length / N7 2. Given masking schedule ot, instance of reverse process T = (MM,,M,--- MN) is defined by Definition D.I. For any two locations within different intervals, their corresponding tokens
7.
independent from each other. In other words, let (.)) denote the new tokens M, n Nj. x62) denote the previously sampled tokens in Mei M. and p denote the distribution over sequences generated by the reverse model with reverse process T, then for time step 1 N N
p
p( ( 22
In this case, we have:
M
M N
p(x) = II p() j=1
p a 22))
We denote the above setting Inter 1, o4).
Under the interval setting defined above, we can control the probability of sampling simultaneously in the same interval.
Lemma E.5 (Simultaneous Sampling Probability for Interval). Consider the interval setting Inter L, L, a+). For each interval I of length I, let h2 denote the probability that all the locations in I are sampled in different time steps. Then, h2 can be bounded by:
hg 1 N
Proof. Let 6; = 0g;- - -0t 1- Similar to Lemma DJIL we know that 5; is the probability of a location being sampled time step 4. Take the first location in [Ty], denote X1, and let x,, denote the rest 1 locations in Zy. If X2 is sampled at step 4, then X2, ... X₁ must be sampled time steps other than 4,. Therefore, hy can be bounded by:
N
N
hy S 8 81(1-,))--
8,) = Σ
8, 6,).
im1
Let f(6) = 5(1 - 5). Note that we have:
- 0,
which indicates that f(0) is concave. Using Jensen's 's Inequality, we can obtain:
N = 1
hj S Σ ( S i=1
N
Using the above lemma, if we assume that sampling simultaneously in one interval increases SER, then derive an lower bound for SER(p).
Lemma E.6 (SER bound for Interval Setting). Consider the interval setting Inter(L, o.). Assume that sampling simultaneously in the same interval introduces an error with probubility at least po- and other actions do not reduce error. In other words, if two locations in an interval are both sampled at step tv, then there is a probability of Pe that the sequence will not be accurate afterwards. In this case, let denote the distribution over sequences length L generated by the reverse model with masking schedule a₁ and reverse steps. We have the following bound for SER:
(1
Pe 1,/1
SER(p) 2
39

---

Proof. By Lemma B we can obtain that for each interval Zy, the probability pemor of generating an error in I lower-bounded by:
Penor 2 Po -
Pe
Due to the independence between different intervals, the accuracy SER(p) can be calculated as:
M
SER(p)
II
(1
j=1
Therefore, we have the bound:
SER(p) 2 21 (1 (1- Pe 1/1
N
To show that the above setting is reasonable and achievable, give the following example, which later shown to be the example we are looking for.
Example E.7. Consider sequence of length L, which divided equally into M intervals, each of length / = L/M. Denote the k-th interval as I₁ = [1 (k - 1)1, kl]. The tokens ø₁, S i E L in the sequence satisfy the following rules:
Each takes values in the set A = {a11 a2t-1) }. For each aj A. there corresponds vector vj = (U,,,... 13,-1) E {0, 1)--1, where (Uj,1 ... U3,1-122 is the binary expression for j - 1. Thus, each random variable v; corresponds a random vector (u(*) ... (11))
(6)
where ( {0. 13 for = =.. -.....--1
For i E Ig and j E Ig. if + s, then x, and 2, are independent.
For i,j E Ig such that < j. let i' = (s - 1)l and = j - (s 1).. Then, x; and zy are the i'-th and j'-th elements in interval Zg respectively, The corresponding binary
components satisfy (() m ~ Bernoulli (+). which is independent of all other of
In this setup, each interval Ia contains 2 pairs of mutually independent random variables. Given an arbitrary masking schedule an, this setting is consistent with Definition E. Let denote the data distribution described above.
[(--1)
Under Assumption I. we only need to examine the case where has no enror. By Lemma we know that:
1 (26 a.)) pz( =x))|; S 2Dx (2) (x)))po(z))
xx)) S 2c learning
Let M denote the set of previously sampled locations. For g and any unsampled location interval Z, all of the potential tokens r at this location which is consistent with æ, have the same probability:
g ())) 1M-1-
If two locations 2;, xj within the same interval are sampled simultaneously. ignoring the possible inconsistency with previously sampled tokens (since error can not be reduced), the independence of the random variable pairs implies that the probability of generating an error is lower-bounded by:
1 Pe
+
+ e2) + +( eaa) + e4)
2
where 1 implies the probability (for 2) of letting
( or - to be O 1, and c1, 62, 63, satisfies:
(8)
[e + |eal = (0 mx) Po (#) xx)
eal + Jeal = |101c(a6 xx)) pa (arg xx)
40

---

Thus, we know that:
1 2
(leil + |e22 |eal + +eel)) 2
2 2 2ctearning
In other words, this is consistent with the setting Lemma E.G. with an error probability
2/ teterinng.
Although the example above seems a bit tricky, it can actually be modified into the form of an HMM, commonly considered structure for generative models.
Note E.8 (HMM Form of Example E.Z).. The setting described in Example E.7 can be alternatively modeled Hidden Markov Model (HMM), where the observation space is O A. and the state space is S {(i, ) E [[(-1)x(-1),
I.... .1.. Here. i represents the current position within the interval, and A is upper triangular matrix with entries taking values of 0 or 1. For j S i, the j-th row of ( encodes the values sampled by the variable pairs formed between the j-th position and all its subsequent positions in the interval. For j > i, the j-th row of A is set to 0.
Given the current state 8 (i, ()), the state transition and emission process can be describe as follows:
The observation o, corresponds to the 1-th column and the i-th row of the matrix A(9, where the values of variable pairs relevant to the i-th position within the interval are en- coded. Specifically, we know that og E A corresponds to a vector e; (Vi,1, 11 , where
AA 1--1 j jci
Vig
j2i
If < I, the next state is s' = (i, ((+1)), where the first rows of 16+1) is the same as A and A ((tt)) ~ Bernoulli( {)) i.d. for = i . - with the remaining entries set to 0.
If i 1, the next state resets to s' (1, AA)), where the entries in the first row are independently sampled from Bernoulli()) ()), and other entries are set to
The size of the observation space is given by |0| = |A| 2/-1_ The size the state space is computed as:
|S| Σ 2(8---1)6// 1)6/2 < 222((11)/22
In fact, with appropriate adjustments, can be further modified into n-gram language. Using the HMM defined above, can prove Theorem 1
The above Note gives the HMM form Example HM
Theorem E.9 (SER Bound for HMM Generation). There exists an HMM q over vocabulary of size 16 that satisfies the following conditions: for any reverse model pe under Assumption t. with Gearning < 12g. and any masking schedule as, let p denote the distribution over sequences generated by po. There exists a constant C such that if the number of sampling steps satisfies N = CL, where lower-bounded by:
the sequence length, the SER of the generated
SER(p) >
2
Proof. Take the HMM described in Note E and 5, N CL. The vocabulary is the
observation space O which satisfies ( = 2 By Lemma E.G. for any masking schedule a; we have:
Pe L/1
SER(p) 2
As illustrated in Example E.r.
1
Pe 2
2 24jearinng
41

---

Therefore, take N = C'L, and let CL Po
we have:
SER(P) 2
Since (1 1 is decreasing, and apparently y
C Pe
know that:
SER(p) 2
Pe CI
Let C== 2p. [+1 we can get the upper bound:
SER(p) >
2
In this way:
2pe
1
2/
2 Elearnnng
1
C
2
0(1)
1+1
24
E.3 Extending Theorem 9.4 to Remasking Strategies
In this section, we extend the conclusion of Theorem 4.4 to masked diffusion models with remasking sampler (named ReMDM) proposed by (Wang all (025). We begin by presenting the main mechanisms the sampler, followed by the justification for analogous results.
As is introduced in the paper, ReMDM is an MDM with remasking designs, where preciously sam- pled tokens have a chance to be remasked and resampled again in later steps. Formally, o, be remasking schedule that satisfies 0 < I m1, I-ax for any time step < t. ar
In contrast to the conventional reverse process defined in Equation 2), the reverse process of ReMDM (with the original sequence æ:) is defined
L-1 II
gajr(2; D1, x)
Oute (x (x) x), where
Ot.
2 *
[m]] x 4
2 * [m]. xx [m]
(7)
Gojo (
1-a, 0,ar
at
[m], at [m]
cie as - (1-0))aa
2o (x))),
2 [m]. x * [m]]
0,
otherwise.
Intuitively, compared the original reverse process, there is probability that already generated tokens are remasked during the generation. Now, consider the last time t that location is sampled. In other words, the location sampled step t, and is not remasked in later steps, thus the token sampled at í. will stay unchanged. We will derive the probability that a location is sampled for the last time time step t4 2
Lemma E. (Last Sample Probability Estimate of ReMDM), Given a masking schedule remasking schedule o and reverse steps. for ReMDM, the probability ò, that a location is sampled for the last time at time step t, N satisfies that:
N
N-1
8, = (as, (1- -00 )a II
(1 - (1-or)).
Proof. It follows from the symmetry that we can consider any location in the sequence. First, we use induction show the probability pmn() that the token this location is [m] at 4 satisfies pm)
Ot.,
For i 0, since a 0, it is direct that Pm (0) 1 = Cto
42

---

For i = k + 1, assume that Pm (k) 1 O12 Combining with Equation (1). we know that
1 Oty-1 Ote Otta (1 Pm (k:) ot. = O1e11"
Pm + 1) - Pm (ki)
Otts -tts
Thus, conclude that Pm (8) 1 Oit, Therefore, the probability ó, can be decomposed into
d; = Pr: [m] at (,,-)) Pr(not [m]at at 4,
[m] at 1,, Pr(stay unmasked not [m] at b,
=pm -1)- 1)- at - (1 Jei-1 )at
N-1
ot,)
1 041-1
j=z
N-1
=(as, - -01 1 )at,))
(1 - o1,).
z=1
By replacing the probability of a location being sampled at time step i with the probability of that location being sampled for the last time be time step & (and letting to be the corresponding probability in Lemma [=l)), we can derive analogous results to those presented in Lemma E.S. Lemma E.G, and Theorem B.J, This substitution is justified because when
locations are sampled simultaneously and are not later remasked and resampled, there exists a probability of introducing
errors. Therefore, by applying similar proof techniques, we arrive at the same conclusion stated in Theorem A.4.
F Experiment Details
In this section, we will present the details of the experiments.
F1 Data Generation
We evaluate the MDMs in a variety of formal languages, including n-gram languages and HMMs. For each formal language, parameters are generated through random sampling, we present the sam- pling algorithm Algorithm DI and Algorithm language model in the evaluation of SER, we add the parameter of thres to prune the tail proba- bilities, making sure the language model only generates the correct sequence. For the evaluation of TER, set the thres to be 0, for the well definition of generative perplexity. The detailed parameters to generate the formal languages are listed in Table E
It is notable that to add some deterministic to
Table 6: Generation Parameters for Different Language Models
Parameter
2-gram
3-gram
4-gram
HMM
vocabulary size
Hidden States (n)
N/A
N/A
N/A
32
Temperature
3.2
Threshold
0.008
0.008
0.005
0.003
43

---

Algorithm Generate 7-gram Language Model
Input:
n: number of grams
vocab_siie sizeesssieeeeee size of vocabulary
temp: temperature (controls randomness, higher indicates more randomness)
thres: threshold for pruning small probabilities
Output: n--ram language model with parameters:
T: transition probability matrix (vocab size"~1 x vocab_sizeg size)
Init_ dist: initial state distribution
I: Init_dist
rand (hidden_staall states__nnn
2: Init dist + Init dist/ C(mit dist)
3: T' t randn(vocab_sat "is_sizee" vocaab size) x randomness
4: T' softmax(T)
5: if' thres > 0 then
6: T[where(T < thres)] <
7: T - L-TTrroweee T/rowsum(T)
8: end if
9: return T and Init_ dist
Algorithm 2 Generate Hidden Markov Model
Input:
n: number of hidden states
vocab_sizze size of vocabulary
randomness: temperature parameter to control probability distributions
thres: threshold for pruning small transition probabilities
Output: HMM with parameters:
A: state transition matrix (n n)
B: emission probability matrix (n x (vocab size + 1))
Init_dise initial state distribution (n-dimensional)
I: hidden_states_un statestttttttte _attees_ummm--e +
2: _ + rand (hidden states states_num)
3: Init dist + Init dist/ ((Initddie _dst)
4: A + randn(hidden stttesttttessettee num, hhcdhheedddeeeeeeeeeeeeeeeeeeeae _um) x randomness
5: A <- softmax(A)
6: if thres > 0 then
7: A [[where(A A < three)) +-
8: A + A/rowsum(A)
9: end if
10: B + randn((idden_stann statestttte__t_ettttteet num, vocab_size) X randomness x 2.5
11: < ssotmax
12: B B[where(B < 0.05)] t-
13: t- B/rowsummB)
14: + concat( B, ones(hidden states num, 1) ///hideen states num)
15: return A, B, and Inst_dist
F.2 Model Training and Testing
our experiments of formal languages, all training was conducted on NVIDIA A100 GPUs. The model architectures and train configurations are listed in Table 0 and Table H. The training configu- ration of the auto-regressive model listed Table We run the each experiment for times and report the mean and standard deviation.
44

---

Model Configuration
Hidden Size
768
Sequence Length
(512.1024,2048)
Number Layers
Attention Heads
12
Table 7: Model Configuration for the Formal Language Tasks
Training Configuration for MDMs
Epochs
20
Learning Rate
3e-4
Optimizer
AdamW
81
0,9
32
0.999
Learning Rate Scheduler
Cosine Scheduler with Warmup
Warmup Ratio
0.1
Table 8: Training Configuration for MDMs on the Formal Language Tasks
Training Configuration for Auto-regressie Models
Epochs
20
Learning Rate
3e-4
Optimizer
AdamW
31
0.9
32
0.999
Learning Rate Scheduler
Cosine Scheduler with Warmup
Warmup Ratio
0.1
Table 9: Training Configuration for Auto-regressive Models on the Formal Language Tasks
Speedup Testing Settings
GPU
Nvidia RTX 4090
Batch Size
1
Sequence Length Testing Model Configuration
2048
In Table M
Table 10: Setting for the experiments to test the speedup of MDMs under different sampling steps compare to auto-regressive models.
45


Reviews:
[{"review_id": "F2ci69yYpP", "reviewer": "Reviewer_4VkA", "summary": "This paper provides an analysis of the properties of MDMs in the context of language modeling and compares them to autoregressive LMs. According to the paper's findings, the number of steps required to achieve near-optimal perplexity or a reasonable Token Error Rate (TER) for MDMs is relatively constant, regardless of sequence length. Conversely, the number of steps needed to achieve a specific Sequence Error Rate (SER) scales linearly with increasing input sequence length. Theoretical findings are validated on synthetic tasks, and the experimental results confirm these theoretical insights.", "questions": "Q1: Does Theorem 4.4 hold for continuous diffusion language models like [1]?\nQ2: Diffusion models are less sample-efficient during training, as each training step involves only a single noise level [2]. Would the results of the experiments in Section 5.1 change if the number of training epochs for MDMs were increased compared to the AR model?\nQ3: Where would be Qwen 2.5 3B and Qwen 2.5 1.5B in Figure 1?\n\n[1] [Likelihood-Based Diffusion Language Models](https://arxiv.org/pdf/2305.18619)\n[2] https://sander.ai/2023/01/09/diffusion-language.html", "limitations": "The authors adequately addressed the limitations", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n - S1: This contribution could be very important for the field of diffusion language models. Diffusion LMs are believed to be more efficient on code and math, however, this work suggests that the number of steps scales linearly with sequence length to achieve low SER. Therefore, using diffusion for this task could be less efficient compared to AR models.\n - S2: Measuring TER and SER on synthetic tasks could be a useful metric for future research on Diffusion LMs.\n - S3: The paper is easy to follow because of the structure.\n\nWeaknesses\n\n- W1: The main text only includes results on the GSM8K dataset. Adding additional datasets and reporting mean accuracy across them would help address this limitation.\n - W2: The apparent superiority of the AR model in Figure 1 might be explained by differences in the dataset used and the amount of FLOPs during training. \n - W3: Setup where #steps < sequence length should be compared to AR model with lower number of parameters during inference, matching the speed or computational cost (FLOPs) of MDMs like LLaDA with lower number of steps.", "was_revised": true, "final_justification": "During the rebuttal phase, the authors provided additional experiments on the HumanEval benchmark, which addressed my earlier concerns regarding the limited scope of their evaluation. They also included additional baselines using smaller autoregressive models, further strengthening their empirical analysis.", "rebuttal": "Thank you for your valuable feedback. Here, we address your concerns and questions below:\n\n---\n\n# Regarding experiments on additional benchmarks\n\n**In the submitted version, we have already included experiments on MBPP in addition to GSM8K.** The observations and conclusions are consistent across both benchmarks. Due to space limitations, the MBPP results are presented in Appendix A.3, as referenced in Line 160.\n\nTo further address your concern, during the rebuttal period, we extended our comparison to include LLaMA 8B, Qwen2.5-3B and Qwen2.5-1.5B, and conducted additional experiments on the HumanEval benchmark. The results are shown in the table below (* indicates AR baselines). The conclusions remain consistent: MDMs fail to achieve both higher efficiency and better performance simultaneously in realistic settings.\n\n| Model                           | Accuracy on HumanEval | Time cost (s) |\n| :------------------------------ | -------- | ------------- |\n| Dream-v0-Base-7B, step 128      | 15.9     | 499.5         |\n| Dream-v0-Base-7B, step 256      | 32.9     | 954.6         |\n| Dream-v0-Base-7B, step 512      | 56.1     | 1838.7        |\n| Dream-v0-Base-7B, left-to-right | 57.9*     | 784.1*         |\n| LLaDA-8B-Base, step 128         | 12.8     | 626.2         |\n| LLaDA-8B-Base, step 256         | 26.8     | 1143.9        |\n| LLaDA-8B-Base, step 512         | 32.9     | 2058.9        |\n| LLaDA-8B-Base, left-to-right    | 28.7*     | 1842.4*        |\n| Qwen2.5-7B                      | 56.7*     | 145.5*         |\n| Qwen2.5-3B                      | 39.0*     | 244.5*         |\n| Qwen2.5-1.5B                    | 37.2*     | 203.1*         |\n| Llama-3-8B                      | 62.2*     | 147.0*         |\n\n\n# Regarding the performance gap between AR and MDMs\n\n**We have made every effort towards a fair comparison, and we believe the conclusion is well-justified.**\n\nIn the first step, we compare open-sourced MDM and AR models in the left subfigure of Figure 1. As you point out, this comparison inherently favors AR models, which were trained by top-tier industry labs with access to high-quality training data and extensive computational resources. We acknowledge and discuss this limitation in Line 163.\n\nTo address this concern, we have already adopted a more controlled setting. As noted in Line 164, we decode the MDMs auto-regressively from left to right, token by token, and use this as an \"AR\" baseline for comparison. Admittedly, this setup inherently favors MDM models, as the \"AR\" decoding is performed directly using the pre-trained MDMs, without any additional training via next-token prediction. Nonetheless, even under this unfavorable comparison for the AR baseline, MDMs fail to achieve both higher accuracy and greater efficiency.\n\nGiven the above discussion, we believe that both results together well support our conclusion: MDMs do not offer a better efficiency–accuracy trade-off compared to auto-regressive models.\n\n# Regarding comparison to smaller AR models\n\nTo address your concerns that MDMs with less steps should be compared with AR models with lower number of parameters, we conducted experiments to test the performance of Qwen2.5-3B and Qwen2.5-1.5B on GSM8K, MBPP and HumanEval benchmarks. The results on the HumanEval benchmark are listed in the above table, and results on GSM8K and MBPP are shown below. It is clear that in order to achieve comparable accuracy on the benchmarks, MDMs require much more time during inference, which aligns with our conclusion that MDMs do not offer a better accuracy-efficiency trade-off. For potential concerns on the fairness of comparison, please refer to the previous section.\n\n| Model                           | Accuracy on GSM8K | Time cost (s) |\n| :------------------------------ | -------- | ------------- |\n| Dream-v0-Base-7B, step 64      | 47.5     | 1349.9         |\n| Dream-v0-Base-7B, step 128      | 68.6     | 2649.5         |\n| Dream-v0-Base-7B, step 256      | 76.3     | 5253.7         |\n| LLaDA-8B-Base, step 64         | 54.5     | 2803.3         |\n| LLaDA-8B-Base, step 128         | 66.0     | 5413.7         |\n| LLaDA-8B-Base, step 256         | 69.1     | 10696        |\n| Qwen2.5-3B                      | 76.5*     | 553.3*         |\n| Qwen2.5-1.5B                    | 63.2*     | 448.6*         |\n\n| Model                           | Accuracy on MBPP | Time cost (s) |\n| :------------------------------ | -------- | ------------- |\n| Dream-v0-Base-7B, step 128      | 26.4     | 2380.1         |\n| Dream-v0-Base-7B, step 256      | 42.8     | 4677.0         |\n| Dream-v0-Base-7B, step 512      | 56.6     | 9197.0         \n| LLaDA-8B-Base, step 512         | 39.6     | 10839        |\n| Qwen2.5-3B                      | 55.2*     | 213.2*         |\n| Qwen2.5-1.5B                    | 43.4*     | 166.2*         |\n\n# Regarding continuous diffusion language models\n\nNo. Theorem 4.4 is specialized for the discrete masked diffusion model. It cannot be extended to continuous diffusion language models [1]. \n\n[1] Likelihood-Based Diffusion Language Models, arxiv 2305.18619\n\n# Regarding experiments in Section 5.1\n\nIn our experiments, both MDMs and AR models were trained until convergence. While the optimal perplexity in these synthetic datasets can be calculated, our trained MDMs and AR models have achieved the optimal perplexity on the validation sets (refer to line 316). We believe the comparison is fair enough.\n\n---\n\nThank you again for your thoughtful feedback. We hope that these clarifications and additions will enhance the strength and clarity of the paper’s contributions, and we would be happy to answer any further questions."}, {"review_id": "XRkrVjaTu5", "reviewer": "Reviewer_ZofZ", "summary": "This work theoretical studies the benefits and limitations of Masked diffusion models for text generation. It first empirically shows that existing autoregressive models such as qwen perform better in terms of efficiency and accuracy than diffusion models such as Llada, which claims better efficiency. It is shown that for n-gram langauges diffusion models can outperform autoregressive models in efficiency with competitive accuracy at token-level metrics such as perplexity. However, when it comes to sequence-level tasks such as correctness of answers or logic, it is shown that there exists an Hidden Markov Model language such that diffusion models show no such advantage over autoregressive models.\n\nExperimental results on synthetic data shows similar pattern as claimed by the theorems, i.e., for sequence-level metrics, the performance of diffusion models are much worse than autoregressive models. However, for token-level metrics the performance of diffusion model looks nearly independent of the number of steps taken by the diffusion model, and the performance of diffusion and autoregressive models look comparable.", "questions": "Please also answer the weaknesses.\n\nAdditional Questions\n-  Line 248: even though it is claimed that the number of samples required is constant. Is it not dependent on the Markovity n of the language model?\n\n- Why is the TER result in Thm. 4.2 only for n-gram language whereas the SER result in Thm. 4 gives an existence result but does not mention the n-gram of the language. Does the result in Thm. 4 claim the existence of an n-gram language for which the theorem holds or is it for any possible Markovian language?\n\n- Since diffusion models perform well on token-level metric but not on sequence level metric. Can we not modify the sampling algorithm for using speculative decoding? That is, use diffusion model as a draft model and use autoregressive to fix sequence level metric. This is a general question. No need for theoretical analysis or experiments. I am trying to understand if the limitation of diffusion models shown a major issue for sequence-level metric or is there a way around that is not discussed.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n- The paper provides interesting theoretical results showing that the performance of emerging diffusion language models are dependent on the nature of the evaluation metrics, in particular, for token level metrics diffusion models show promise of outperforming autoregressive models. But for sequence-level metrics such as correctness of reasoning or complete answer, diffusion model fails to offer benefits compared to autoregressive models. These results are shown for Markov-style language assumption, nevertheless, the results are interesting.\n\n- Experimental results on synthetic data validates both the claims for token-level as well as sequence-level metrics.\n\n\nWeaknesses\n- One weakness already mentioned in the paper is that all theoretical analysis and experimental results are restricted to HMM-style language. However, a) this assumption may not hold for general tasks, b) even if the assumption of HMM holds, tasks like infilling may benefit from diffusion models more. Even if the theoretical analysis for such non-HMM languages may be difficult, the paper must have some experimental evaluations provided to better understand the possible generalization of the results in the paper.\n\n- Fig 1 compares performance of qwen versus Llada models on GSM8k to claim the poor performance of diffusion models compared to autoregressive models. But to better understand the result, we should compare with more available models of comparable sizes such as llama 8b and also test on various other benchmarks such as Math500, HumanEval, MBPP, etc.", "was_revised": true, "final_justification": "I have read through the authors' rebuttal as well as other reviews and their rebuttals.\n\nThe authors' rebuttal addresses my concerns, especially, adding experiments with other models such as Llama, as well as pointing out other experiments in the appendix.\n\nOverall, I find the results showing that MDMs are much worse than Autoregressive Models in tasks requiring sequence correctness very interesting and useful for the LLM reasoning community.\n\nHence, I update my score to accept", "rebuttal": "We sincerely thank you for your insightful feedback and suggestions. Below, we address the listed weaknesses and questions in detail.\n\n---\n# Regarding the use of HMMs and experimental evaluations\n\n**Our theory is primarily motivated by experimental evaluations conducted in practical applications**, i.e., on reasoning benchmarks (GSM8k and MBPP), we observed that MDMs typically require more sampling steps to reach competitive performance to either AR models or the AR-style generation of MDMs, which diminishes their efficiency advantage.\n\nTo better understand these observations, we begin with a theoretical investigation. It is important to note that any theoretical result must be grounded in explicit assumptions. To bound the approximation error of MDMs and analyze the number of steps required to reach that bound, it is essential to specify the underlying ground-truth distribution. To this end, we focus on Hidden Markov Models (HMMs) and n-gram languages, which capture key characteristics of natural language in practical settings, and the theoretical findings reveal that MDMs may require a significant number of steps to achieve a good approximation, which is consistent with the experimental observations.\n\nAs you rightly point out, certain gaps between theory and practice still remain.  Moving forward, we plan to follow your suggestion and extend our analysis to more realistic scenarios, including long-range dependency structures, syntactic hierarchies, and distributions derived from large-scale language model pretraining corpora. \n\n# Regarding infilling tasks \n\nSpecialized tasks, such as bidirectional infilling, can be effectively addressed using dedicated frameworks like BERT (masked language modeling) and diffusion models, which take the entire sequence as input and generate missing tokens conditioned on the surrounding context. In this paper, however, we focus on general NLP tasks. We agree that your suggestion — to compare MDM and AR on more specific tasks — is insightful, and we consider it a valuable direction for future work.\n\n# Regarding broader model comparison and benchmarks\n\nIn the submitted version, we have already included experiments on MBPP in addition to GSM8K. The observations and conclusions are consistent across both benchmarks. Due to space limitations, the MBPP results are presented in Appendix A.3, as referenced in Line 160.\n\nTo further address your concern, during the rebuttal period, we extended our comparison to include LLaMA 8B and conducted additional experiments on the HumanEval benchmark. The results are shown in the table below （* indicates AR baselines）. The conclusions remain consistent: MDMs fail to achieve both higher efficiency and better performance simultaneously in realistic settings.\n\n| Model                           | Accuracy | Time cost (s) |\n| :------------------------------ | -------- | ------------- |\n| Dream-v0-Base-7B, step 128      | 15.9     | 499.5         |\n| Dream-v0-Base-7B, step 256      | 32.9     | 954.6         |\n| Dream-v0-Base-7B, step 512      | 56.1     | 1838.7        |\n| Dream-v0-Base-7B, left-to-right | 57.9*     | 784.1*         |\n| LLaDA-8B-Base, step 128         | 12.8     | 626.2         |\n| LLaDA-8B-Base, step 256         | 26.8     | 1143.9        |\n| LLaDA-8B-Base, step 512         | 32.9     | 2058.9        |\n| LLaDA-8B-Base, left-to-right    | 28.7*     | 1842.4*        |\n| Qwen2.5-7B                      | 56.7*     | 145.5*         |\n| Llama-3-8B                      | 62.2*     | 147.0*         |\n\n\n# Regarding the dependency of the number of steps\n\nThanks for the question. The number of steps in the theorem depends on the order $n$ of the Markov model (See line 238). The \"constant\" here mainly refers to the dependency on sequence length. We will make it clear in the next version.\n\n# Regarding the HMM in Theorem 4.4\n\nGood catch — HMMs and n-gram language models are closely related. It's straightforward to show that all n-gram languages can be represented as HMMs, and HMMs can be transformed into n-gram models under certain conditions (e.g., finite state and finite-memory assumptions; a direct proof can be obtained using GPT).\n\nThe SER result in Theorem 4.4 also holds for n-gram languages, as the construction used in the proof of Theorem 4.4 can be viewed as an n-gram language with some modifications (detailed in Appendix E.7 and E.8). However, using the HMM framework offers several advantages, particularly in simplifying the proof construction and making it easy for the reader to understand. We will carefully consider both the unification of the proof and the consistency of the overall framework.\n\n# Regarding combining AR and MDM\n\nThis is an excellent suggestion — integrating diffusion-based text generation with speculative decoding is a very promising direction.\n\n---\n\nThank you once again for your time and effort. We hope the clarifications and explanations above have adequately addressed your concerns."}, {"review_id": "csoUcvteko", "reviewer": "Reviewer_QaD3", "summary": "This paper analyzes the theoretical limitations of masked diffusion models (MDMs). It proposes two evaluation metrics: token error rate and sequence error rate, which aim to quantify the uncertainty in token prediction and the correctness of entire generated sequences, respectively. Through theoretical analysis and toy experiments, the paper shows that while MDMs can achieve low perplexity with few sampling steps, minimizing sequence error requires steps that scale with sequence length.", "questions": "- How does SER relate to the performance on reasoning tasks?\n- It is mentioned that SER is computed directly using Equation (5). How is the summation over $\\\\mathcal{L}\\_q$ performed in practice, given that the cardinality appears intractable?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper analyzes the theoretical limitations of masked diffusion models, which is an important and timely topic in generative language modeling.\n\nWeaknesses:\n- The soundness of the proposed evaluation metric appears questionable. SER is defined as one minus the sum of model probabilities over all sequences in the ground-truth support set $\\\\mathcal{L}\\_q$, regardless of their probabilities under the ground-truth distribution. This leads to unintuitive behavior: if all sequences have non-zero probability under the ground-truth distribution, then SER = 0, regardless of the actual distributional alignment. Consider the following two cases:\n    - 1) The model distribution has the same support as the ground truth but a different probability assignment.\n    - 2) The model distribution is nearly optimal but assigns a small probability $\\\\delta$ outside the support.\nIn these cases, SER would be 0 for the first and $\\\\delta$ for the second, incorrectly favoring the worse model. This raises concerns about whether SER is a reliable or meaningful metric for analyzing language models or their reasoning capabilities.\n- The significance of the theorems is also unclear. Theorems 4.2 to 4.4 provide bounds on the required sampling steps. However, these bounds may be of limited practical value since it's known that MDMs can approximate any ground-truth distribution if the number of sampling steps ≥ the sequence length—because the issue of conditional independence disappears when generating one token per step. (I am not an expert on these proofs and acknowledge the possibility of misinterpretation.)\n- The experimental design is limited to toy settings up to 4-gram synthetic languages. While this may help illustrate the theoretical claims, it does not adequately reflect the complexity of real natural language, limiting the broader applicability of the results.\n\nMinor:\n- Line 279: \\citet", "was_revised": true, "final_justification": "The rebuttal addressed most of my concerns.", "rebuttal": "Thank you for your feedback and comments. We have carefully considered each point you raised and will address them one by one below.\n\n---\n\n# Regarding the soundness of the evaluation metric SER\n\nOur primary motivation for introducing SER is to provide a metric for evaluating the validity of reasoning chains, particularly in tasks that require logically correct sequences, such as mathematics or code generation. These tasks involve highly structured data, where the set of correct sequences, $\\mathcal{L}_q$, typically occupies a very small subset of the overall sequence space. Therefore, we believe our proposed metric — measuring the probability of generating a sequence outside the correct set — is reasonable. \n\n**This design is novel and has received positive feedback from all other reviewers.** For example:\n\n- “Measuring TER and SER on synthetic tasks could be a useful metric for future research on Diffusion LMs” — Reviewer 4VkA\n- “...For sequence-level metrics such as correctness of reasoning or complete answers, diffusion models fail to offer benefits...” — Reviewer ZofZ\n- “The authors provide insights on the strength of parallel sampling in terms of...sequence-level holistic accuracy metrics” — Reviewer Gs9S\n\n**You proposed two scenarios, and we demonstrate below that neither presents a problem for the SER metric:**\n\n- Case 1: The model distribution has the same support as the ground truth but a different probability assignment. In this scenario, SER = 0. For verifiable reasoning tasks, which may admit multiple correct solutions, SER = 0 is the ideal outcome, indicating that the model exclusively generates correct sequences.\n\n- Case 2: The model distribution is nearly optimal but assigns a small probability $\\delta$  outside the support set. Here, SER = $\\delta$, which accurately quantifies the model's risk of producing an incorrect output with probability $\\delta$.\n\nFrom the perspective of reasoning accuracy, the model in Case 1 is superior because it never fails, whereas the model in Case 2 will fail with probability of $\\delta$. SER correctly captures this distinction, favoring the model that is guaranteed to be correct.\n\n# Regarding the significance of the theorems\n\n**You misinterpret the theoretical results of the paper.** Our target is not to establish the universal approximation capability of MDMs, but rather to rigorously investigate the efficiency–accuracy trade-off (the trade-off between approximation error and computational cost) in comparison to auto-regressive (AR) models. We have emphasized this point multiple times throughout the paper, including in the abstract (Lines 18–20), the introduction (Lines 35–37, 41–42, 64–66, 72–74), Section 4 (Lines 245–250, 292–297), and the conclusion (Lines 363–366).\n\nWe demonstrate that the number of sampling steps required by MDMs to achieve a given approximation error varies significantly depending on the evaluation metric:\n\n- For TER (refer to line 240~250): Theorem 4.2 proves that an MDM requires only a constant number of sampling steps (independent of sequence length L) to achieve near-optimal TER. In contrast, AR models inherently require $L$ sequential steps. This result implies that for tasks prioritizing textual fluency (as captured by TER), MDMs offer a substantial theoretical efficiency advantage over AR models.\n\n- For SER (refer to line 268~284): Theorem 4.4 proves that to achieve a low SER, the number of sampling steps required for the MDM must scale linearly with the sequence length L, indicating that the number of neural network executions is comparable between MDMs and auto-regressive models. Consequently, for tasks requiring strict reasoning correctness (as measured by SER), MDMs lose their efficiency advantage.\n\n# Regarding experimental design\n\n**We cannot agree that the paper only contains toy settings. Our theory is primarily motivated by experimental evaluations conducted in practical applications. See lines 155-170 for the detailed discussion.** We observed that on reasoning benchmarks (GSM8k and MBPP), MDMs typically require more sampling steps to reach competitive performance to either AR models or the AR-style generation of MDMs, which diminishes their efficiency advantage. \n\nTo better understand these observations, we begin with a theoretical investigation. It is important to note that any theoretical result must be grounded in explicit assumptions. To bound the approximation error of MDMs and analyze the number of steps required to reach that bound, it is essential to specify the underlying ground-truth distribution. To this end, we focus on Hidden Markov Models (HMMs) and n-gram languages, which capture key characteristics of natural language in practical settings, and the theoretical findings reveal that MDMs may require a significant number of steps to achieve a good approximation, which is consistent with the experimental observations. \n\n\n# Regarding the relationship between SER and the performance on reasoning tasks\n\nAs stated in our response to Weakness 1, SER is intrinsically linked to performance on reasoning tasks. In many reasoning benchmarks, especially for the verifiable reasoning tasks, there are correct reasoning paths and answers. By verifying the correctness of the entire sequence, SER provides a much stricter evaluation than accuracy, which only considers the final answer. A model that consistently achieves a low SER demonstrates a reliable reasoning capability.\n\n# Regarding the calculation of SER\n\nWe have explicitly described how TER and SER are computed in practice. As stated in Line 235, “For robust evaluation, all reported TER and SER values are averages over 2000 generated sequences for each experimental setting.” In fact, we have also tried increasing the number of samples to 20000, and the estimated accuracy shows negligible differences compared to the results with 2000 samples, confirming the reliability and stability of our evaluation.\n\n\n---\n\nThank you once again for your time and effort. We hope the clarifications and explanations above have adequately addressed your concerns, and we sincerely look forward to receiving your support."}, {"review_id": "YrUJAW2Ttl", "reviewer": "Reviewer_Gs9S", "summary": "The authors find that the utility of MDMs is highly dependent on the evaluation metric used. When assessed by token-level accuracy, MDMs can achieve near-optimal results with a constant number of sampling steps, regardless of the length of the sequence. However, when evaluated based on sequence-level correctness, which is critical for tasks like logical reasoning, the required number of sampling steps for MDMs must increase linearly with the sequence length. This research provides a theoretical framework for understanding when to use MDMs, suggesting they are well-suited for tasks where fluency is paramount, while auto-regressive models are better for tasks demanding high accuracy and logical consistency.", "questions": "Does the metrics TER and SER defined in section 4.1 generalized to conditional generation?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength\n1. The authors study an important problem from a theoretical perspective on the inference of MDMs with comparison to auto-regressive LM.\n2. The authors provide insights on the strength of parallel sampling in terms of two types of methods as token-level independent metric and sequence-level holistic accuracy metric.\n3. The authors carry out empirical evaluation on synthetic tasks (HMM and n-gram) to corroborate the theoretical finding.\n\nWeakness\n1. Though the chosen metrics provide good theoretical finding, it is not directly related to performance of real-world task performance. SER should be too harsh on the success of even reasoning tasks as errors on a few tokens may not have large effects on final accuracy.\n2. It is hard to achieve a fair comparison of MDM and AR models especially on real datasets due to differences in model structure and training to isolate the effect of inference. As the authors suggest, even “AR” generation of MDM still leads to gap in performance compared to true AR models.", "was_revised": true, "final_justification": "I have read authors' rebuttal and will remain my initial evaluation", "rebuttal": "Thank you for your thoughtful feedback. We address the raised concerns below:\n\n---\n\n# Regarding the practical relevance of SER in reasoning tasks\n\nThanks — this is an excellent point. We intentionally adopt the correctness — or more precisely, the validity — of the entire trajectory as the evaluation metric for sequence-level assessments, rather than relying solely on the final outcome.\n\nIt is widely acknowledged that verifying the correctness of a solution to a mathematical problem requires examining all intermediate steps, not just the final answer (as exemplified by the recent IMO proof verification process). The widespread reliance on final-answer evaluation of LLMs is largely due to the inherent difficulty of automatically assessing the full reasoning chain.\n\nIn fact, alongside our work, there has been a surge of recent research revealing the limitations of using only final outcomes. For example, [1] explores how agents can be used to verify reasoning paths, while [2] develops methods for identifying mistakes and correcting outputs. Additionally, a recent survey [3] provides a comprehensive framework for evaluating step-by-step reasoning traces.\n\nWe believe that the shift from outcome-based to path-based evaluation will happen soon, and our work will become even more impactful.\n\n[1] Derailer-Rerailer: Adaptive Verification for Efficient and Reliable Language Model Reasoning, arxiv 2408.13940 \\\n[2] LLMs cannot find reasoning errors, but can correct them! arxiv 2311.08516v2 \\\n[3] Evaluating Step-by-step Reasoning Traces: A Survey, arxiv 2502.12289v1\n\n\n# Regarding the comparison between AR and MDMs\n\nWe have made every effort towards a fair comparison, and we believe the conclusion is well-justified.\n\nIn the first step, we compare open-sourced MDM and AR models in the left subfigure of Figure 1. However, this comparison inherently favors AR models, which were trained by top-tier industry labs with access to high-quality training data and extensive computational resources. Consequently, the superior performance of AR models in this setting may stem from these advantages rather than from fundamental framework-level differences. **We acknowledge and discuss this limitation in Line 163**.\n\nTo address this concern, we adopt a more controlled setting. As noted in Line 164, we decode the MDMs autoregressively from left to right, token by token, and use this as an \"AR\" baseline for comparison. Admittedly, **this setup inherently favors MDM models, as the \"AR\" decoding is performed directly using the pre-trained MDMs, without any additional training via next-token prediction. Nonetheless, even under this unfavorable comparison for the AR baseline, MDMs fail to achieve both higher accuracy and greater efficiency.** \n\nGiven the above discussion, we believe that both results together well support our conclusion: MDMs do not offer a better efficiency–accuracy trade-off compared to autoregressive models.\n\n\n# Regarding the generalization to conditional generation\nYes. These metrics can be extended to conditional generation settings with minor modifications.\n\n---\nThank you once again for your thoughtful feedback. We hope our clarifications have adequately addressed your concerns, and we would be happy to answer any further questions."}]

Author rebuttal:

Meta-review: This paper investigates the theoretical benefits and limitations of diffusion LLMs. By modeling natural language generation through n-grams or hidden Markov models, the authors derive theoretical bounds on both token-level and sentence-level error rates. A key finding is that, in the worst case, the number of required sampling steps must scale linearly with sequence length in order to control the sequence-level error rate—thereby questioning the efficiency advantages often attributed to diffusion LLMs. While reviewers initially raised concerns about the limited experimentation with state-of-the-art diffusion language models, these were satisfactorily addressed during the rebuttal discussion. In light of the overall positive reviews, I recommend acceptance.
Decision: Accept (poster)