SPMDM: Enhancing Masked Diffusion Models through Simplifying Sampling Path
Authors: Yichen Zhu
Weiyu Chen
James Kwok
Zhou Zhao
Venue: NeurIPS 2025 poster ()
Keywords: discrete diffusion
generative modeling
Primary area: deep_learning

Abstract: Autoregressive models (ARMs) show strong capabilities in many domains but face challenges with planning and complex reasoning due to their sequential generation. Masked diffusion models (MDMs) address these issues by enabling controllable, any-order, and parallel generation but encounter training difficulties as token prediction complexity varies with unmasked token positions. This work identifies two key characteristics of efficient MDM sampling paths: prioritizing tokens near unmasked ones and generating subsequence earlier in reasoning. We propose the Simple Path Masked Diffusion Model (SPMDM), which partitions sequences into fixed-length, non-overlapping subsequences and applies varying noise scales to learn token-level and cross-subsequence dependencies. Experiments on synthetic data and tasks like Countdown and Sudoku show SPMDM captures structural rules effectively, significantly outperforming existing MDMs and ARMs, with competitive results on broader reasoning benchmarks.

SPMDM: Enhancing Masked Diffusion Models through Simplifying Sampling Path
Yichen Zhu 1.3. 'Zhejiang University
Weiyu Chen 2' James Kwok
Zhou Zhao 1,3,
HKKUS Shhnghai Artificial Intelligence Laboratory (yc_zhu, zhaozhou) @zju. bajjuedu.cco edu.cn on {uchenbx, jamesk) &cse. ust.hk
Abstract
Autoregressive models (ARMs) show strong capabilities in many domains but face challenges with planning and complex reasoning due to their sequential generation. Masked diffusion models (MDMs) address these issues by enabling controllable, any-order, and parallel generation but encounter training difficulties token prediction complexity varies with unmasked token positions. This work identifies two key characteristies of efficient MDM sampling paths: prioritizing tokens near unmasked ones and generating subsequence earlier in reasoning, We propose the Simple Path Masked Diffusion Model (SPMDM), which partitions sequences into fixed-length, non-overlapping subsequences and applies varying noise scales to learn token-level and cross cross- coos-subsequeece dependencies. Experiments on synthetic data and tasks like Countdown and Sudoku show SPMDM captures structural rules effectively, significantly outperforming existing MDMs and ARMs, with competitive results on broader reasoning benchmarks.
1 Introduction
Autoregressive models (ARMs) have ushered in a new era of artificial intelligence, demonstrating remarkable performance in applications such high-quality text generation [33]
3 43 code
generation [35. and chain-of-thought (CoT) reasoning for mathematical problem solving [45). Despite the remarkable achievements and widespread real-world applications of autoregressive models, the left-to-right generation paradigm continues to suffer from several inherent limitations [2]
46). Notable challenges include difficulties in future planning, complex reasoning and self- 8 20
correction 22 6 47). These constraints have spurred researchers to explore alternative architectures
for next-generation L.Mss.
A compelling direction in current research focuses on the development of masked diffusion models (MDMs) 5
30 36). Researchers have drawn inspiration from the remarkable success of diffusion models in image generation [19 42 14 and have increasingly focused on exploring MDMs for discrete sequence generation. In contrast AR models, which generate tokens sequen- tially, a unifying insight across these models is the potential of diffusion language models (DLMs) for controllable 29 any-order, and parallel text generation (2 16 27). Notably, DLMs exhibit
26
25
promising capabilities in complex reasoning and global planning limitations inherent the AR approach.
48 51
thereby addressing key
However, training MDMs is inherently more challenging than training ARMs 23 While ARMs aim predict the next token given unmasked prefix, MDMs are tasked with predicting token conditioned on a set of unmasked tokens located at arbitrary positions. In other words, unlike ARMs,
"qqual contribution. Conresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where the learning difficulty remains consistent, the denoising difficulty in MDMs varies depending on the positions of the unmasked tokens. As result, many existing studies focus on identifying simpler sampling paths to improve sample quality. This is typically achieved by carefully selecting
which token to unmask next during the sampling process 23 32
In this work, we begin by comparing the sampling paths, which refer to the token unmasking orders produced by different sampling strategies, and identify two key characteristics that define simpler and more efficient sampling paths: (a) From a generation-order perspective, prioritizing tokens in the local neighborhood of unmasked tokens. (b) From logical-ordes perspective, prioritizing the generation of subsequences that appear earlier in the reasoning process. Motivated by these observations, we propose a novel approach called the Simple Path Masked Diffusion Model (SPMDM), which encourages these characteristics during MDM training. Specifically, we partition the input sequence into non-overlapping, exed-length subsequences and assign different noise scales to each of them. This design encourages the model to capture token-level dependencies within each subsequence, while simultaneously learning logical dependencies across subsequences.
In our experimental evaluation, we first assess the intra- and inter-subsequence modeling capabilities of SPMDM on synthetic sequences that follow predefined structural rules. Our method significantly outperforms baseline MDMs in capturing these rules. We then focus on substantially more complex mobblem-solving. tasks, such as Countdown and Sudoku. These tasks require extensive planning over a large number of combinations and remain challenging even for commercial large language models (e.g., GPT-4 3. Notably. our method significantly outperforms its autoregressive counterpart and surpasses most existing discrete diffusion language models. Finally, we evaluate SPMDM on broader set of reasoning benchmarks, where it also demonstrates strong and competitive performance.
2 BBckground
In this section, we introduce the notation used throughout the paper and briefly review masked diffusion models (MDMs), along with method that optimizes MDM sampling trajectories during inference via an adaptive sampling strategy. Additional related works are discussed in Appendix A
Notations. We consider scalar discrete random variables with V categories as one-hot column vectors in the space V fx 1), E, x; 1} C V for the simplex AV. Let the V-th category denote a special [MASK] token, where m is its one-hot vector. We define x sequence of N tokens, where x" E V for all tokens & {L...., .N), and use y to denote the set of all such sequences. Throughout the work, we simplify notation and refer to the token sequence as x and an individual token as x Finally, let Cat(::p) be a categorical distribution with probability
p E A
2.1 Masked Diffusion Models
MDMs introduce a forward process that pro- gressively adds noise to data in the discrete domain, and learn the marginal distribution of the corresponding reverse process [36].
Similar to continuous diffusion models 41 42 19)
The forward process starts with clean data x and defines latent variables x, = [x], ... xX]] for I E [0, 1]. MDLM (36] defines coordinate-independeer masking process:
N
(x xo) = II
(0 x6), (x) x()) = Cat(arx + (1 aa,)))
(I)
E=1
where is the predefined noise schedule satisfying og 2 L, a1 2 0.
The reverse process in MDMs iteratively recover values for masked tokens, starting from mask sequence X1 = [m..... mm. Let 0 < t 1, the reverse process is given by
(af(xx)
x 7 m;
(x)e(Xe Xx, x)
I[ 2 (x,
Xx. x), (x
Xe, x)
Cat
(1-ar m + as a.-aex)) 1-ac
x m.
1-ai
(

---

M
M
M
Vanilla
M
M M M
Adantive
(h)
Figure 1: Motivation examples. (a) Denoising process of MDLM on the Countdown dataset using the prompt "1, 82, 8, 73,". (b) Average unmasking timestep per token index in generated chain-of- thought reasoning on the GSM8K test set.
distribution po(x x²) parameterized by & is employed to approximate gojo(x x,,x) & gote(x}) Xx.X (x xt)). optimizing the following upper bound on negative log likelihood:
a
LNELBO = En
Σ
log(p) (xi, 1), dt.
(m0 1 ate
2.2 Adaptive MDM Sampling Strategy
According Equation 2 the MDM inference can be decomposed into two steps: (a) randomly selecting a set of positions to unmask and (b) assigning token values to each position via the denoising network pe. However, unlike continuous diffusion, the reverse process MDMs permits multiple valid sampling paths, i.e., different token unmasking orders, that are consistent with the initial distribution defined by the forward process. To identify simpler and more efficient sampling trajectories within the space of valid ones, Kim et al. [23] proposed the Adaptive MDM sampling strategy. Specifically, they designed an efficient ordering oracle function, denoted as F, and used it to adjust the sampling process of MDMs as follows: (a) sample set of masked tokens S = F(0, xx) S
{L x m). then (b) for each E S, sample x ~ p xt).
Method
In this section, we begin with motivational experiment to identify key characteristics of effective sampling paths (Section 3.1 Based on these observations, we propose Simple Path Masked Diffusion Model (SPMDM), an effective method to encourage these key characteristics during training. We provide the formulation of forward and backward processes Section 3.2 We then discuss the network architecture in Section 3.3 and detail the training and sampling algorithms in Section 3.4
3.1 Motivation
Vanilla MDM inference aims to align the intermediate distributions with the forward process, follow- ing the approach used in continuous diffusion. However, a key distinction in MDMs is that the reverse process permits multiple valid sampling paths- saths--seecffiallly. different token unmasking orders all of which remain consistent with the initial distribution defined by the forward process 23
Figure illustrates two results generated by MDLM 36 trained on the Countdown dataset, em- ploying distinct sampling strategies: vanilla and adaptive (as discussed in Section 2.2) As shown Figure [a] the vanilla sampling strategy does not decode semantically related tokens at close timesteps, leading to incorrect outcomes. In contrast, the adaptive sampling strategy demonstrates that groups of related tokens are decoded closer timesteps, which contributes achieving the correct result.

---

To quantitatively analyze the impact of these two sampling strategies. we conducted an experiment. Specifically, we employed SMDM [27] fine-tuned on the GSM8K [T] dataset and compared its performance under the vanilla (original) sampling strategy and the adaptive sampling strategy. Using the GSM8K test set as input, we performed 256 sampling steps and recorded the average unmasking timestep for each token throughout the generation process. Figure shows the average decoding timestep for tokens at each index. As illustrated, under the vanilla sampling strategy, the unmasking timesteps are distributed almost uniformly across all tokens. In contrast, outputs generated using the adaptive sampling strategy exhibit distinct grouping pattern: (i) Tokens in the first half of the sequence, corresponding to the initial part of the problem (e.g.. the first mathematical equation), demonstrate similar average decoding timesteps. Likewise, tokens in the second half, corresponding to the subsequent part (e.g., the second equation), also show similar average decoding timesteps among themselves. (ii) Tokens from the first half are generally decoded earlier than those in the second half, highlighting sequential decoding pattern that aligns with the inherent structure of the problem, such as solving equations in order.
Based on the above observations, we summarize the two characteristics of simple sampling path as follows: (a) From a generation -order perspective, prioritizes tokens in the local neighborhood of unmasked tokens (x' & m). (b) From a logical-order perspective, it prioritizes the generation of subsequences that appear earlier in the reasoning process.
These characteristics are consistent with human problem-solving strategies, where we focus on each equation individually and solve them sequentially. However, the adaptive sampling strategy is applied only during inference. Can we encourage such characteristies during training to further improve performance?
3.2 Subsequence Level Forward and Reverse Process
Building upon the observation in Section 3.I our objective is to enhance two characteristics of sampling paths during training. To achieve this, we propose to partition the input sequence into multiple subsequences and apply noise of varying magnitudes across these subsequences.
Specifically, the input token sequence (of total length N) is divided into K non-overlapping subsequences, each length L. Thus, K = N/T., assuming N is an integer multiple of L.. The k-th subsequence, denoted as x* for k E {l,..., K}, comprises tokens from the original sequence. For convenience, we refer to the f-th token within the k-th subsequence *...
In the standard forward process of MDMs, each token x" in the input sequence x has an equal probability of being replaced by [MASK] token at any given noising step t. In contrast, our approach introduces noise with distinct magnitudes across different subsequences. The forward process for a token within a specific subsequence then becomes:
k.f xx x Cat(ar, x k.P. + (1- -ity )
k.C is the original f-th token of the k-th subsequence, x, is its state at noising step tg. and Here, X
4 is the noising step specifically assigned to the entire k-th subsequence x* att, controls the noise schedule for that subsequence.
Partitioning the sequence in this manner encourages the model to learn dependencies among tokens within each subsequence, thereby encouraging characteristic (a) (in Section Furthermore, assign- ing different noise scales (4&) to different subsequences prompts the model to leverage information from less noisy subsequences, which strengthens its capacity to capture logical relationships across subsequences.
Correspondingly, we define a reverse process to invert the noising process defined in Equation 4 This process adapts the formulation from Equation 2 to the subsequence level:
Asults (x
X k.C x
Cat(x
Cat
I-acy
at, aan wwa.kk. kit) I-are
xie)
X
l
k.8
R.8
m
(5)
Here, 8k < 4. are two noising steps for the k-tth subsequence.
We employ distribution (x
parameterized by 0 to approximate Loults (xht
ki xh((), and the upper bound on negative log- likeliiod at subsequence level can be written as X

---

MDLM
BDLM
Ours
X
x
Noise
ww
www
Training
X
1
X]
Sampling
t= 0
www Add Noise
Generation
Figure 2: Method Overview. During training, SPMDM partitions the input sequence x into K subsequences and introduces noise with varying magnitudes to each of them. Compared to MDLM, our method not only models token-level dependencies but also explicitly encourages the learning of inter-subsequence relationships. contrast to BDLM, SPMDM does not impose left-to-right generation order, enabling more flexible sampling strategies.
follows (see Appendix for the proof):
d'
LELLO = (0,1
log po (x"
xxf X,
(6)
Otty
where of denotes the derivative of a with respect to t, and x
x x
Xix
3.3 Network Architecture
We adopt transformer as the base model, following existing works 255
36
Many discrete diffusion
models do use explicit time embeddings for the current timestep 36 16
28] Instead, they
typically assume f, which indicates the noise scale applied to the input, can be implicitly inferred from the count of masked tokens.
However, the proposed method applies different noise scales to different subsequences, necessitating the introduction of time embedding layers. These layers explicitly encode the noise scale for each subsequence. In contrast to typical time embeddings in other discrete diffusion models, our design assigns K distinct timestep embeddings per input sequence, one corresponding each of the K subsequences. We therefore adapt the dimensionality and structure of the timestep embedding layer for this subsequence-baag levels within different subsequences. Note that the computational overhead from introducing these time embedding layers is minimal, as their parameter count is significantly smaller than that of other model components.
approach, improving the model's capacity capture localized noise
3.4 Training and Sampling
Training. We apply Equation language modeling sequences x I:K which are partitioned
into K subsequences. Specifically, we model the conditional distribution as po I:K x x:KK =
I px(x* x >) Accordingly, we employ a single model to compute (x each token subsequence, and optimize the following objective:
x k) for
K
a/2
LNELBO
Exe (o. 1,
log xxi X,
- 1-as at
1=1
5

---

Algorithm Sampling
1: Input: Network po. subsequence length L, time [0, 11, sampling steps T, oracle function F 1, + 1/7
2: Initialize X1
{m)} [
3: for = 0 to T do
4: vk: Count unmasked tokens n&
5: vk: f-
6: vk: 12) pol- 1 x,, [t2]
7:
if using adaptive sampling strategy then
8:
Sample set of masked token indices S = F(0, xx)
Vii, S::::: x 2/
9:
10:
else
11:
Vk: : 8k f max - 0,,
12:
4k: For all masked tokens, with probability st &0 <- m i
13:
Update Xt + 8o
end if
15:
end for Return X
Sampling. Since our forward process assigns distinct noise scales to different subsequences, we correspondingly modify the sampling procedure. Specifically, sampling starts from a fully masked sequence, denoted as X1. At each denoising step. for every k-th subsequence x* we count the number of unmasked tokens, denoted пą- The corresponding timestep l for this subsequence is then updated according to the formula ts = 1 - nx/ Lg, where L2 represents the length of the subsequence.
Through this timestep updating mechanism, we encourage the model to prioritize denoising tokens that are adjacent to clean tokens, fostering coherent generation. The detailed sampling process for SPMDM is depicted in Algorithm I It is also worth noting that our sampling method is compatible with adaptive sampling strategies. We present the corresponding ablation studies in Section 4.5 demonstrate this compatibility.
Experiments
In this section, we first demonstrate the intra- and inter-subsequence modeling capabilities of SPMDM using toy examples in Section 4. We then experiment with significantly more complex problem- solving tasks in Section which require extensive planning over a large number of combinations. Following this, we further evaluate SPMDM on a broader set of reasoning benchmarks in Section 4.3
Finally, we present an ablation study Section 4.5 Detailed descriptions of the experimental setup provided in the Appendix C
4.1 Toy Examples
Intra-subsequence modeling. To assess the model's capacity capture intra-subsequence de- pendencies, we construct a synthetic training dataset following a well-defined set constraints. Each input sequence consists of characters sampled from the English alphabet (i.e., a-z). Each sequence is divided into four consecutive, non-overlapping character pairs. A strict intra-pair ordering constraint is imposed: the first character in each pair must precede the second in alphabetical order. For instance, the sequence adghklmn is valid, as each of its four pairs, ad, gh, kd, and mn, satisfies the specified ordering constraint.
Inter-subsequence modeling. To evaluate the model's ability to capture inter-subsequence depen- dencies, we design a dataset based on a relational constraint between consecutive character pairs. Each sequence is again composed of characters drawn from English alphabet, divided sequentially into four non-overlapping pairs. An inter-block ordering constraint is enforced: for any two adjacent blocks, the sum of the alphabetical positions of the characters in the preceding block must be strictly less than that of the following block. This setup encourages the model to learn and generalize the

---

ordering relations between blocks. For instance, the sequence igveporw's is valid, as it consists of four letter pairs, ig. ye, po, and nw, which satisfies the predefined ordering constraints.
Baselines. In this toy example, compare the proposed method with representative discrete diffusion model: MDLM [6], a popular discrete diffusion model, and BDLM 4 which offers an interpolation between autoregressive models and discrete diffusion through block-wise partitioning. All methods share the same model architecture with 6M parameters, and all models are trained from scratch on the same datasets with the same number of training steps. For intra- and inter- sequence modeling, we randomly generate 50,000 samples for training and 1000 samples for testing, respectively. We use the success rate (i.e., the percentage of samples that satisfy the predefined rule) as the evaluation criterion.
As shown in Table I our method demon- strates promising performance in modeling both intra- subsequence and subsequueeeeee dependencies.
Results.
Table 1: Success rates of different methods on intra-subeeeeence and nntersubsseuuence modeling.
For intra-subsequence dependencies, the proposed method achieves 26.6% higher success rates than MDLM and 3.4% higher than BDLM, clearly show- casing the ability of SPMDM to effectively capture intra-subsequennce relationships.
Method
Intra-subseq
Inter-subseq
MDLM BDLM
69.2
58.3
92.4
87.1
In terms of suter-subseeeence modeling, our method also exhibits strong capabilities. outperforming MDLM by 22.3%. By assigning different noise scales to different subsequences, the method encourages the model to prioritize extracting information from subsequences with lower noise levels, thereby enhancing its ability to model inter-subsequence dependencies.
Ours
95.8
80.6
Although our method performs slightly worse than BDLM in inter-subsequence modeling, this is largely due to BDLM's use of a semn-avuoregressivve sampling strategy during inference. Specifically, BDLM decodes sequentially from the left block to the right block, which aligns perfectly with the requirements of this specialized task. However, as will be shown in real-world experiments, BDLM does not perform well overall.
4.2 Problem-solving Tasks
Dataset. Countdown [T] is mathematical reasoning task and a generalization of the classic "24 Game," which remains challenging even for advanced models such as GPT-4 (3). The objective is to combine given set of numbers using basic arithmetic operations (+, -, =) ) to exactly match specified target number. We consider three subtasks of increasing difficulty by varying the number of input digits in 4, Sudoku 2 is classic logic-based number placement puzzle, widely recognized for its stringent intellectual requirements. The objective is to fill a x 9 grid with digits such that each row, each column, and each of the nine 3 3 subgrids contains all numbers from to 9 exactly once. In our setup, the digit 0 is used to indicate vacant positions to be filled by the model. Each 9 grid is linearized into a sequence of 81 digits, which serves the model input. During tokenization, each digit is treated as an individual token.
Baselines. In addition to the previously introduced MDLM 36 and BDLM baselines, we also include autoregressive models based on the GPT-2 architecture 333 with parameter sizes ranging from 6M to 85M, as well as pretrained large language models from the LLaMA family 43), with parameter sizes ranging from 7B to 13B. Furthermore. other existing discrete diffusion models: D3PM (5), SEDD [25). and MGDM [48). D3PM serves as the canonical framework for discrete diffusion modeling. SEDD adapts score-based techniques from continuous diffusion into the discrete domain. MGDM exhibits strong performance on reasoning and planning tasks. Except for LLaMA, all other baselines trained from scratch on the dataset.
compare our approach against several
Results on Countdown. As shown in Table 2 our method demonstrates superior performance on the Countdown task. Notably, the performance gap widens as the number of input digits increases. We attribute this to the fact that countdown can be framed brute-force search problem, where larger
7

---

Table 2: Test Accuracy Countdown (CD).
Table 3: Test Accuracy Sudoku.
Method
Param
CD 3
CD 4
CD 5
Method
Param
Acc (1)
6M
94.1
31.9
4.3
6M
13.1
GPT-2
GPT-2
85M
95.9
45,8
5.1
85M
22.4
7B
95.7
44.1
6.7
7B
28.7
LLaMA
LLaMA
13B
96.5
51.1
7.4
13B
41.2
D3PM
85M
99.4
83.1
27.6
D3PM
85M
89.8
ScDD
85M
99.4
83.7
39.9
ScDD
85M
90.2
MDLM
85M
99.5
85.8
41.2
MDLM
85M
92.3
MGDM
85M
99.5
91.5
46.6
MGDM
85M
99.9
BDLM
85M
98.7
85.5
40.8
BDLM
85M
92.1
Ours (L 8)
6M
98.3
53.2
27.0
Ours (L -= 9)
6M
99.9
Ours (L
85M
99.6
92.7
46.1
Ours (L 9)
85M
100.0
Table 4:
Performance on language understanding and reasoning benchmarks. For GSM8K, we finetune the models; all other tasks are evaluated in zero-shot setting.
CommonSense Reasoning
Math GSM8K
Model
Param
HSwag
SIQA
PIQA
Wino.
LLaMA Plaid
7B
74.9
43.2
63.3
67.1
58.6
1.3B
39.3
32.3
54.5
51.3
32.6
GPT-2
127M
29.9
35.7
62.1
48.5
44.8
SEDD
170M
30.2
34.4
55.6
50.1
45.3
MDLM
127M
31.5
35.0
54.2
50.4
46.1
DiffuGPT
127M
33.4
37.0
57.7
50.8
50.2
Ours (L = 8)
127M
33.8
37.2
56.9
51.2
51.3
GPT-2
355M
38.8
37.7
67.4
50.7
50.7
SEDD
424M
31.5
35.4
56.1
49.0
53.5
MDLM
355M
32.7
37.4
55.1
51.5
54.1
DiffuGPT
355M
37.2
39.9
59.6
52.6
52.6
Ours (7. 8)
355M
36.3
41.7
58.4
53.2
56.4
number of input digits leads to a combinatorially larger search space and necessitates longer-range reasoning during generation. Under such conditions, the performance of autoregressive models and semi-autoreerresivee baselines such as BDLM degrades due to their limited horizon. In contrast, our approach exhibits robust performance when handling long reasoning chains, benefiting from its broader context window and stronger ability to model logical dependencies across subsequences.
Results on Sudoku. Unlike Countdown, the Sudoku task requires a balance between global structural consistency and fine-grained intra-subsequence constraints. We report the results the Sudoku in Table 3 Due to the superior capability of SPMDM capturing local patterns within subsequences, it able to effectively learn row-level constraints. At the same time, its strength in modeling logical dependencies across subsequences enables it to learn subgrid and column- level constraints well. In contrast, BDLM that follow left-to-right generation paradigm tend struggle with capturing subgrid and column-level rules effectively.
4.3 Reasoning Tasks
Benchmarks. We evaluate our model on suite of challenging benchmarks spanning language understanding and reasoning. For common sense reasoning. we include four multiple-choice datasets: HellaSwag( WellaSwag(HSSwgg [50], SocialIQA (SIQA) (38), PhysicalIQA (PIQA) (. and Wino- grande (Wino.) (37], with accuracy as the evaluation metric. Additionally, we test on GSM8K [T].
benchmark of grade school math word problems, to evaluate the model's mathematical reasoning

---

capabilities. We follow Ye et al. 49 in finetuning setting using the augmented symbolic data to test the CoT [45 math reasoning abilities of diffusion models.
Baselines. In addition the baselines introduced in earlier experiments, we incorporate sev- eral representative models for comparison in this section: Plaid [[7]. a state-of-the- art continuous diffusion-bann based language model; and DiffuGPT [16], discrete diffusion model for language genera- tion adapted from GPT-2.
Result. As shown in Table under the same parameter budget, our SPMDMs achieve state-of-the- art performance across variety of reasoning task benchmarks. The slightly worse performance on PIQA compared to GPT-2 may be due to the specific physical knowledge required for the task, which our models may lack. This limitation stems from fine-tuning on MDLMs trained on only 30B tokens of Open Text,, which may be insufficient to acquire broad general knowledge. In tasks that require more extensive global reasoning, such as GSM8K, SPMDMs consistently exhibit better performance compared to AR models that rely solely on left-to-right modeling capabilities.
4.4 Computational Overhead
We evaluated the computational efficiency of SPMDM through speed benchmarks the Countdown 4 dataset, utilizing a single RTX 4090 GPU. Specifically, we measured: (1) the training and evaluation token throughput of both MDLM and SPMDM with batch size of 32, and (2) the time required for a 32-step sampling process with a batch size of 1. The results are summarized in Table Note that the official MDLM implementation does not remove the timestep embedder but instead provides with an all-zero input. Consequently, reintroducing the timestep embedding in SPMDM incurs no additional computational overhead compared MDLM. As shown Table these results confirm that SPMDM matches the computational efficiency of baseline approaches.
Table 5: Comparison of computational efficiency between SPMDM and MDLM.
MDLM
SPMDM
Training (token/ms)
93.7
93.1
Evaluation (token/ms)
266.8
265.1
Sampling (s)
0.55
0.57
4.5
Ablation Studies
Effect of subsequence length. In the experiments of Section 4.2 we demonstrated the problem- solving capability of SPMDM under a fixed subsequence length. We now shift our focus to analyzing how different subsequence lengths affect model performance. Notably, when L = N, our model degenerates into MDLM. Specifically, SPMDM reduces to MDLM when L = 48 for Countdown and L, = 162 for Sudoku. The experimental results are shown in Figure 3a Overall, SPMDM consistently outperforms MDLM across most subsequence lengths. However, when L. = 4, we observe performance drop, which we attribute the subsequences being too short capture sufficient semantic or logical information, thus increasing the difficulty of modeling inter-subsequence dependencies. Conversely, when 16, the subsequences become too long and are likely to contain most of the solution within single subsequence, thereby diminishing the need for modeling logical dependencies across subsequences.
Effect of sampling strategy. We also conduct ablation studies on different sampling strategies. The evaluated strategies include: 1) DDPM sampling, the standard method introduced in MDLM, where the same timestep t is applied the entire sequence each denoising step; 2) Our proposed sampling strategy (i.e. lines 10 to 13 in Algorithm []] where each subsequence is assigned an individual noise scale and its timestep is dynamically updated during sampling; 3) A hybrid strategy that combines our sampling method with adaptive sampling (i.e. lines to 9 in Algorithm []]. The corresponding results are presented in Figure 3b) Clearly, our sampling aannncch--ssiginngg noise scales per-subsequence basis-lcade to more effective denoising. Furthermore, incorporating

---

105
Countdown
305.0
Countsown
Tisk
Sudeku
99.9
Countdow
Sudoku
100.0
Accuracy (%)
95
Accuracy (56)
97.5
90.0
95.0
92.7
92.5
85
87.5
16
81
167
Substring Length
DOPM
Ours
Ours+Adaptiive
(a)
(b)
Figure 3: Ablation studies on subsenquence length L and sampling strategy using SPMDM trained on countdown and sudoku datsets. (a) Accuracy on countdown and sudoku vs. subsenquence length. (b) Accuracy on countdown and sudoku vs. sampling strategy.
adaptive sampling further enhances generation quality, indicating the complementary strengths of both strategies.
Conclusion
In conclusion, we identify two key characteristics that define simpler and more efficient sampling paths during MDM sampling process. Motivated by this two characteristics, MDM framework, termed SPMDM, whose core idea is to encourage the characteristics simple sampling paths during training, thereby enhancing the model's 's ability to discover and follow simpler trajectories during the sampling process. Extensive quantitative experiments across a variety of tasks demonstrate the effectiveness and superiority of our proposed method.
propose novel
Acknowledgment
This work was supported by National Key R&D Program of China (N.20027/D0162000) and National Natural Science Foundation of China 612622222, No.U24A20326), This work was also supported in part by the Research Grants Council of the Hong Kong Special Administrative Region (Grants 16202523 and HKU C7004-22G).
References
[1] Countdown.
2024.
[2] million Sudoku games.
2024.
[3] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Lconi Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[4] Marianne Arriola, Aaron Gokaslan, Justin T Chiu, Zhihan Yang, Zhixuan Qi, Jiaqi Han, Subham Sekhar Sahoo, and Volodymyr Kuleshov. Block diffusion: Interpolating between autoregressive and diffusion language models. arXiv preprint arXiv:2503.09.: 2025.
[5] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:1 34:17981-1799 117993, 2021.
[6] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.06966. 2024.
10

---

[7] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang. Shijie Wang. Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang. Hao Yang, Jian Yang, Shusheng Yang. Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang. Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu, Qwen technical report. arXiv preprint arXiv:2309. 16609, 2023.
[8] Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. Scheduled sampling for sequence prediction with recurrent neural networks. Advances in neural information processing systems, 28, 2015.
[9] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piqa: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages 1432-7439, 2020.
[10] Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 35:28266-28221 2022.
[11] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14166 2021.
[12] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8799 2021.
[13] Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, al. Continu- ous diffusion for categorical data. arXiv preprint arXiv:2211. 2022.
[14] Xie Fan, Zeng Dan, Shen Qiaomu, and Tang Bo. A comprehensive survey on text-to-video generation. Chinese Journal of Electronics, 34(4): 100-10000--00..00 2025, doi: 10.23919/cjc 151. URL httpp://cccje...... ejounnal..laaaa.a.a.. org. cn/ en htt//aariceeeeee/e http:////.....1...............00
151
[15] Shansan Gong, Mukai Li, Jiangtao Feng, Zhiyong Wu, and LingPeng Kong. Diffuseq; Sequence to sequence text generation with diffusion models. arXiv preprint arXiv:2210.08933) 2022.
[16] Shansan Gong, Shivam Agarwal, Yizhe Zhang, Jiacheng Ye, Lin Zheng, Mukai Li, Chenxin An, Peilin Zhao, Wei Bi, Jiawei Han, et al. Scaling diffusion language models via adaptation from autoregressive models. arXiv preprint arXiv:2410. 178911 2024.
[17] Ishaan Gulrajani and Tatsunori B Hashimoto. Likelihood- based diffusion language models. Advances in Neural Information Processing Systems, 36: 36:16693-16715, 2023.
arXiv preprint [18] Jonathan Ho and Tim Salimans. Classifier-free diffusion guidance. arXiv:2207.12598, 2022.
[19] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
[20] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. arXiv preprint arXiv:1904.09551, 2019.
[21] Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. arXiv preprint arXiv:21 10.02037, 2021.
[22] Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. arXiv preprint 1100022310001798, 2023.

---

[23] Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham Kakade, and Sitan Chen. Train for the worst, plan for the best: Understanding token ordering in masked diffusions. arXiv preprint UrXiv:2502.06768. 2025.
[24] Xiang Li, John Thickstun, Ishaan Gulrajani, Percy S Liang, and Tatsunori B Hashimoto. Diffusion-Im improves controllable text generation. Advances in neural information processing 2022.
systems,
[25] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. 2023.
[26] Chenlin Meng, Kristy Choi, Jiaming Song, and Stefano Ermon. Concrete score matching: Generalized score matching for discrete data. Advances in Neural Information Processing Systems,
2022.
[27] Shen Nie, Fengqi Zhu, Chao Du Tianyu Pang, Qian Liu, Guangtao Zeng, Min Lin, and Chongxuan Li. Scaling up masked diffusion models on text. arXiv preprint 4rXiv:2410.18514 2024.
[28] Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin. Ji-Rong Wen, and Chongxuan Li. Large language diffusion models. arXiv preprint arXiv:2502.09992 2025.
[29] Hunter Nisonoff, Junhao Xiong, Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete state-space diffusion and flow models. arXiv preprint urXiv:2406.01572 2024.
[30] Jingyang Ou, Shen Nie, Kaiwen Xue, Fenggi Zhu, Jiacheng Sun, Zhenguo Li, and Chongxuan Li. Your absorbing discrete diffusion secretly models the conditional distributions of clean data. arXiv preprint arXiv:2406.0372 2024.
[31] Guilherme Penedo, Hynek Kydlfček, Vinko Sabolčec, Bettina Messmer, Negar Foroutan, Martin Jaggi, Leandro von Werra, and Thomas Wolf. Fineweb2: A sparkling update with 1000s of languages, December 2024. URL httt:httt/ttgggiiie http://www.......t.tttt//////naa
co Heattasset/Hugggnngghhe
fineweb-2
[32] Fred Zhangzhi Peng, Zachary Bezemek, Sawan Patel, Jarrid Rector-Brooks Sherwood Yao, Alexander Tong, and Pranam Chatterjee. Path planning for masked diffusion model sampling. arXiv preprint arXiv:2502.0335 2025.
[33] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 18):9, 2019.
[34] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pages 10684-10695, 2022.
[35] Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, al. Code Ilama: Open foundation models for code. arXiv preprint arXiv:2308. 12950, 2023.
[36] Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. arXiv preprint arXiv:2406.07524, 2024.
[37] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge scale. Communications of the ACM, 64(9):99-106. 2021.
[38] Maarten Sap, Hannah Rashkin, Derek Chen, Ronan LeBras, and Yejin Choi. Socialiga: Com- monsense reasoning about social interactions. arXiv preprint arXiv: arXiv:1904.0 09728, 2019.
[39] Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis Titsias Simplified and generalized masked diffusion for discrete data. arXiv preprint arXiv:2406.04433 2024.
12

---

[40] Andy Shih, Dorsa Sadigh, and Stefano Ermon. Training and inference on any-order autoregres- sive models the right way. Advances in Neural Information Processing Systems, 2--762227775 2022.
[41] Jascha Sohl- Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages
PMLR, 2015.
[42] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[43] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13397/ 2023.
[44] Siddarth Venkatraman, Moksh Jain, Luca Scimeca, Minsu Kim, Marcin Sendera, Mohsin Hasan, Luke Rowe, Sarthak Mittal, Pablo Lemos, Emmanuel Bengio, et al. Amortizing intractable inference in diffusion models for vision, language, and control. arXiv preprint 20X1:2200077 2024.
[45] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Lc, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-2482 2022.
[46] Juan Wen, Yaqian Deng, Wanli Peng, Xue Yiming, Wen Juan, Peng Wanli, and Xue Yiming. Linguistic steganalysis via fusing multi-granularity attentional text features. Chinese Journal of Electronics, pages 248-254, 07 2022. doi: 10. 10.1049/ce..022..00000
[47] Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner: benchmark for real-world planning with language agents, arXiv preprint arXiv:2402.01662,, 2024.
[48] Jiacheng Ye, Jiahui Gao, Shansan Gong, Lin Zheng, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Beyond autoregression: Discrete diffusion for complex reasoning and planning. arXiv preprint arXiv:2410.14157 2024.
[49] Jiacheng Ye, Shansan Gong, Liheng Chen, Lin Zheng, Jiahui Gao, Han Shi, Chuan Wu, Xin Jiang, Zhenguo Li, Wei Bi, et al. Diffusion of thoughts: -fthouh reasoning in diffusion language models. arXiv preprint 2rXiv:2402.07754 2024.
[50] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv: 2019.
[51] Yizhe Zhang, Jiatao Gu, Zhuofeng Wu, Shuangfei Zhai, Joshua Susskind, and Navdeep Jaitly. Planner: Generating diversified paragraph via latent language diffusion model. Advances in Neural Information Processing Systems, 36:80174 78-80190, 2023.
13

---

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

---

We provied the full set of assumptions and complete (and correct) proof related to the work in Appendix B
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provied the information needed to reproduce the main experimental results in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (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 reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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
15

---

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: Due to certain constraints, we are unable to release the code during the review period.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
ollicy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppgpuuiiieeeep httpa///uuidessoeeeuubbiiiis SroodeSubiissi.e ssiiiiolcccy for more details.
The authors should provide instructions 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:
We provied all the training and test details in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All error bars are suitably and correctly defined Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, 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 with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provied provide sufficient information on the computer resources in Appendix [
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
ctwhitteeeeeeeleeeeeeeeeeee diness
Answer: [Yes]
Justification: The research conducted have conducted in 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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss both potential positive societal impacts and negative societal impacts of the work performed in Appendix E
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate 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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
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)?
Answer: [Yes]
Justification:
We describe safeguards that have been put in place for responsible release of
models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the creators original owners of assets used in the paper properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
All new assets introduced in the paper are well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No such experiment in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No such experiment in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS 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
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 is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: No such usage of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should be described.
cc cc/Connerrncce/2225////////
A Related Works
Autoregressive Models. The autoregressive modeling paradigm, where the prediction of a token only depends the preceding context, is widely adopted in modeling language. Autoregressive models have catalyzed significant advances artificial intelligence, achieving state-of-the results range of tasks, including fluent text synthesis 33
43 7 program generation (35), and However, despite their transformative im- pact and broad deployment in real-world systems, ARMs are inherently constrained by their sequential, left-to-right generation strategy [21 40 g 20 This unidirectional nature presents persistent chal- lenges scenarios requiring foresight, multi-step reasoning, and iterative self-correction [22 47
-o-hhuotf reasoning in mathematical domains [45).
Diffusion Language Models.
Continuous diffusion models have demonstrated remarkable perfor- mance and controllability in image generation tasks [19 42 12 18) Building these successful
practices, several works have extended continuous diffusion models to text generation 24
15 13 17]
Among them, Plaid [17] is notable approach that maps discrete text into continuous embedding space and constructs a continuous diffusion framework in that space. Given the inherently discrete nature of language, Austin al. (5] proposed D3PM, diffusion framework tailored discrete data domains. They incorporate an absorbing [MASK] state as noise, laying the foundation for discrete diffusion models. This framework has been further developed by [25] (30 [36]. and 39 . Among
these, the MDLM (36) framework is one of the most widely adopted, offering simple and efficient training objective. More recently, BDLM 4 combines ARMs with MDMs through interpolation,
integrating the left-to-right generation paradigm of ARMs into MDMs and proposing a novel diffusion modeling framework. Furthermore, Ye et [48] have shown that MDMs significantly outperform ARMs in complex reasoning and global planning tasks.
B Simple Path Mask Diffusion Model
Recall that, under the SPMDM framework, the input token sequence x (of total length N) is divided into K vonoolerlapiing subsequences, each length L. Thus, K = N/L, assuming N is an integer multiple of T.. The k-th subsequence, denoted as x* for & E [1,..., K). comprises tokens from the original sequence. For convenience, refer the f-th token within the k-th subsequence as k.
B.1 Forward Process
The forward noise process applied independently for each token is defined as follows:
K J.
Xn)
IIII 9t oo (x
(xt((), a (x k.f x5 = Cat x l
(1 ar )m) (8)
l:
20

---

where t = t1,-11 1 tk, and Ey denotes the noising step applied to x".
B.2
Reverse Process
Under the framework of MDLM [36], the reverse process iteratively recover values for masked tokens, starting from mask sequence X1 = [m.... m.. Let S Sp tu S 1, the reverse process is given by:
K I. IIIII
(x/t(Xe xx0) =
Geulee (xtre
8
(9)
Asulte (xtiee
k.l Xbx xhit))
Cat(x
x le
R.8
f m;
Cat
1-a0e I-
m + I-cre
ang kile
x le
R.8
m.
B.3 Simple Path Mask Diffusion NELBO
We provide the negative evidence lower bound (NELBO) for the simple path masked diffusion parameterization. We firstly perform diffusion in each block over T discretization steps. Let D denote the Kullback-Leii Leibler divergence, Êg. 8% be shorthand for (i) = i/T and sy (i) = t(i 1)/T. vi []. We derive the NELBO follows:
K log E,
xx4" x)
- log Pa (xx)
xx))
1=1
K
po((x
x4. k)
I Po (x s2(t) xc (x)) x
log Eay
Il g(xt (1) xe x
K
Eg log pa (x*
xt X )t
(10)
Ererea
R te E
T-1 11 Bay DDKL (a(x |x x²) po
X X
DKL (1(x
x*) ) po (xc (xf(=1))
Lytix
B.4 Simplified NELBO
We adopt the SUBS parameterization proposed by Sahoo et al. (36]. Specifically, we impose the following constraints on the design of po by exploiting the fact that, at any timestep I, each token xf can only reside in one of two states: the original token xf or the mask token m, i.c., xf E x m for all É I,..,,L:
1. Zero Masking Probability. Since the clean target sequence x does not contain any mask tokens, enforce (x(x' denoising.
x)) 0, ensuring that the model never predicts mask token during
2. Carry-Over Unmasking, Once a token is unmasked in the reverse process, it is never remasked. Accordingly, we simplify the denoising model by enforcing po (x{ x x A m) 1, meaning that any token already unmasked remains unchanged in subsequent steps.
21

---

Table 6: Dataset Deatails, Intra and Inter refer toy datasets designed for intra- and inter-subsequence
modeling, respectively. CD is an abbreviation for Countdown..
Intra
Inter
CD3
CD4
CDS
Sudoku
Train Entries
50k
50k
500k
500k
500k
100k
Test Entries
1k
1k
1k
1k
1k
1k
Avg Input Token
11
13
16
81
Avg Output Token
12
25
35
81
Max Input Token
16
15
18
81
Max Output Token
22
35
52
81
As result, we will only approximate the posterior po = xf becomes:
xf m).
The diffusion loss term
Ldiffusion
Elg E
[DKL (g(x xxf x²)) po xx, x4. *)]]
1.
Erg E,,
DRL. (1(xb)) til R.l. ( (x xix xx
(11)
K
Ee, T.yT
at
ass
log (x | xee x xxe))
au2
k=
1=1
Σ E. R T
a2 log px xxxxx xxx
0z
Previous works have shown empirically and mathematically that increasing the number of steps T yields tighter approximation to the ELBO [1O]. Following similar argument, form continuous time extension by taking T + oo, which yields the following diffusion loss term:
a'y
Liiftusion
Σ EBa
log po(* xxx xx
(12)
- ac
For the continuous time case, have xt #+= limr Cat (xt+ (x/==+) Cat(x*). Then, the reconstruction loss term becomes:
Lrecons EE, log (x
x xx x
-lo xiu= = xx xx =0 (13)
The prior loss also reduces because 0t=11 0, which ensures q(xt;,=1 xx*) Cat(m) and ==) = Cat(m).
Finally, we obtain a simple objective as follows:
K
ag log (x xt, xxx)
CNLLO
E, E 0.11
(14)
1 a₁
C Experimental Details
C.1 Dataset Details
We present the detailed specifications of the toy datasets and problem-solving task datasets in Table 6
C.2 Implementation Details
Toy examples. We conduct all toy example experiments using four RTX 4090 GPUs. MDLM (6). BDLM 4, and SPMDM are implemented using a tiny model with 6M parameters. For BDLM, the block size is set to 2, and for SPMDM, the subsequence length is also set to 2. We use learning rate of x 10-3 and a batch size of 1024. All models are trained for epochs on the training set. Additionally, the number of sampling steps is fixed to 32 for all models.
22

---

Problem-solving tasks. We conduct all experiments related to problem-solving tasks using eight RTX 4090 GPUs. Both ARMs and MDMs are implemented based on the GPT-2 architecture. Across all datasets, we use learning rate of x 10-3 for the 6M-parameter tiny models and 3 x 10-4 for the 35M-parameter models. The batch size set to 512. For the countdown task, we train for 150 epochs, and for the sudoku task, we train for 100 epochs. Specifically, for the Countdown task, we set the block size of BDLM to 4, and for the Sudoku task, we set to During sampling, we fix the number of denoising steps to 32 for all MDMs across all tasks. For LLaMA, we follow the results reported in the work of Ye et al. 488; detailed fine-tuning settings can be found in Appendix C of 48
Reasoning tasks, For GPT-2, SEDD, and DiffuGPT, we borrow the results reported by Gong et al. [16]. Following their experimental setup, we also use the advanced Fine Web2 corpus [31]. which is derived from Common Crawl, as the training dataset for both MDLM and SPMDM. Training and sampling conducted on eight A100 GPUs with 40GB of memory. For models with 127M and 355M parameters, we use a learning rate of 3 x 10 with a cosine scheduler. The batch size is set to 512, and training is performed for total of 400K iterations. During inference, the number of sampling steps is fixed to 256.
C.3 Evaluation Details
For the intra- and inter-subsequence modeling tasks, we perform unconditional generation using MDMs, generating 1,000 samples per task and evaluating performance by counting the number of samples that satisfy the predefined structural constraints. For the countdown and sudoku tasks, con- duct conditional generation using the questions from the test set as prompts, and measure performance by the number of correctly solved instances. For common sense reasoning tasks HellaS (50), Winogrande [37]. SIQA (38], and PIQA 19 use answer accuracy as the evaluation metric. For GSM8K [11, take the questions from the test set as prompts for conditional generation and report the accuracy of the final predicted answers as the evaluation metric.
D Limitation
SPMDM framework is based on factorization assumptions. In a state space of length N, the transition matrix [10] contains an exponential number of possible states, making it computationally expensive assume independence between dimensions, treating each dimension as an independent one oie-dimensional diffusion process with the same transition rate matrix. Admittedly, in language modeling, tokens are not entirely independent, there exist complex dependencies between them. However, without this independence assumption, the computational cost of training would become astronomical, and the modeling complexity would increase significantly. Despite this simplification, extensive prior work [10] 25] 36 (39 and our own experiments demonstrate that under this assumption, the model achieves strong performance with practically acceptable results for real-world applications. At the same time, this presents an interesting research direction- direction-explorring ways to explicitly model the conditional dependencies between tokens. By leveraging these dependencies strategically plan the denoising process of DDMs, we can potentially unlock significant improvements in the model's generative capabilities.
to reverse. To alleviate this issue, existing works T0
25
36 39
E
Impact
Ethical impacts. This study does not pose any ethical concerns. does not involve subjective assessments or the use of private data, as all experiments are conducted on publicly available datasets.
Expected societal implications. The primary potential societal impact of SPMDM lies in its possible misuse, particularly in generating false or misleading information, which could contribute to misinformation. privacy violations, and other harmful consequences. To mitigate these risks, is essential to establish robust ethical guidelines and implement continuous monitoring to ensure the responsible and ethical deployment of such generative models.
23


Reviews:
[{"review_id": "MwDHv3SaL2", "reviewer": "Reviewer_kCs5", "summary": "The paper proposes a novel framework called Simple Path Mask Diffusion Model (SPMDM) to address challenges in masked diffusion models (MDMs) for discrete sequence generation. While MDMs enable flexible, parallel, and any-order generation, their training is more complex than autoregressive models (AR) due to variations in token prediction difficulty based on the positions of unmasked tokens. \n\nThrough analysis of adapative sampling on mutliple tasks. The authors identify two key patterns of efficient sampling paths: prioritizing tokens near unmasked ones and generating subsequences earlier in reasoning.\n\nBased on this observation, the authors propose SPMDM, which improves upon existing MDMs by partitioning input sequences into fixed-length, non-overlapping subsequences and applying varying noise scales. This approach encourages better token-level and cross-subsequence dependency modeling.", "questions": "see weakness", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1. Novel analysis on sampling of MDM: The paper provides a novel analysis of sampling paths in MDMs, identifying two key characteristics that define simpler and more efficient sampling strategies. This analysis provides a nice insight of how sampling paths influence both training efficiency and inference quality in MDMs.\n\n2. The model performs well across diverse tasks, including both general NLP tasks as well as tasks requiring combinatorial reasoning (Countdown) and structural consistency (Sudoku), showcasing its versatility in handling complex reasoning and planning problems.\n\n3. The architecture is designed to scale efficiently, showing strong performance even with smaller parameter budgets (e.g., 6M and 85M models), which is beneficial for resource-constrained environments.\n\nWeakness:\n\n1. How does SPMDM perform in comparison with block diffusion methods [1]? Block diffusion methods also break generation into chunks and model the relationship both between and within the chunks.\n\n2. The motivation emphasizes learning tokens in the neighborhood, which is improved by using subsequence-level diffusion. For planning tasks, the priority is to learn earlier reasoning tokens. Does this learning order also appear in SPMDM's inter-subsequence relationships? Additionally, SPMDM supports any-order subsequence relationships. How does the preferred order differ for different tasks, e.g., Countdown tasks vs. commonsense reasoning?\n\n[1] Arriola, Marianne, et al. \"Block diffusion: Interpolating between autoregressive and diffusion language models.\" ICLR 2025.", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. How does SPMDM perform in comparison with block diffusion methods?\n\nThank you for your thoughtful comments. The key difference is:\nBlock Diffusion (BDLM) [1] methods use autoregressive modeling, while SPMDM employs different noise scheduling across subsequences. BDLM is semi-unidirectional rather than fully bidirectional. While this may benefit general text modeling, it negatively impacts reasoning tasks that require bidirectional context understanding.\n\n Additionally, BDLM's hybrid diffusion-AR approach incurs higher training costs, whereas SPMDM adds minimal training overhead while achieving superior performance on reasoning tasks.\n\nAs for the empirical performance, the following is a summary of the observations from the real-world tasks.\nOn Countdown tasks (Table 2), SPMDM achieves 0.9%, 7.2%, and 7.9% higher accuracy than BDLM on CD-3, CD-4, and CD-5 respectively. On Sudoku (Table 3), SPMDM surpasses BDLM by 8.1% accuracy.\n\nWe will add the above discussion and more detailed comparison with BDLM in the final version.\n\n### Q2. For planning tasks, the priority is to learn earlier reasoning tokens. Does this learning order also appear in SPMDM's inter-subsequence relationships?\n\nThank you for your question. Yes, this learning order do appear in SPMDM's inter-subsequence relationships. To demonstrate \nhow SPMDM captures inter-subsequence relationships through its denoising order, we now add the following experiment on the Countdown task.\n\nFirst, we pick an example from the Countdown-3 test sets and show the step-by-step denoising process of SPMDM as follows:\n\n```\n1,82,8 ### 73 ### [MASK]2-[MASK][MASK][MASK][MASK][MASK][MASK]1[MASK][MASK]=[MASK][MASK]\n1,82,8 ### 73 ### [MASK]2-1[MASK][MASK][MASK][MASK][MASK]1[MASK][MASK]=[MASK][MASK]\n1,82,8 ### 73 ### 82-1[MASK]8[MASK][MASK][MASK]1[MASK]8=[MASK][MASK]\n1,82,8 ### 73 ### 82-1[MASK]8[MASK][MASK][MASK]1[MASK]8=7[MASK]\n1,82,8 ### 73 ### 82-1[MASK]81[MASK][MASK]1[MASK]8=7[MASK]\n1,82,8 ### 73 ### 82-1=81[MASK][MASK]1[MASK]8=7[MASK]\n1,82,8 ### 73 ### 82-1=81,[MASK]1-8=7[MASK]\n1,82,8 ### 73 ### 82-1=81,[MASK]1-8=73\n1,82,8 ### 73 ### 82-1=81,81-8=73\n```\n\nAs can be seen, SPMDM first decodes the first question, followed by the second equation.\n\nIn addition, we conduct a quantitative experiment on the Countdown test sets. \nSpecifically, following the experimental setup in Section 4.2, we set the sequence length to 48 and the subsequence length to 8, using the CD-3 problem as the prompt input. We calculate the average denoising timestep for tokens within each subsequence throughout the generation process. \n\nWe set the number of sampling steps to 12. The experimental results are presented in the table below, where *Index* indicates the subsequence index, and *Avg Unmask Steps* refers to the average denoising timestep of tokens within each subsequence:\n\n| Index | Avg. Unmask Timesteps |\n| ----- | --------------------- |\n| 0     | 0.0                   |\n| 1     | 0.0                   |\n| 2     | 4.58                  |\n| 3     | 5.29                  |\n| 4     | 6.37                  |\n| 5     | 6.25                  |\n\nNote that, based on the current partition with a subsequence length of 8, the first two subsequences are prompts. As a result, for sequence index 0 and 1, the average unmask steps are always zero. \n\nWe observe that SPMDM prioritizes denoising the first equation (i.e, sequence index 2). \nThis behavior is consistent with construction process of Countdown ground-truth solutions. \nThe process begins by solving the first equation, which helps determine the valid factors that can be used in subsequent equations. The last two subsequences mainly consist of padding tokens, and thus do not exhibit any significant differences in denoising order.\n\nTherefore, we believe that SPMDM successfully captures the underlying dependencies between subsequences.\n\n### Q3. How does the preferred order differ for different tasks?\n\nTo illustrate this, we perform the experiment in Q2 above on the Sudoku task. \nRecall that  each row in the Sudoku question is treated as a subsequence. \nWe set the number of sampling steps to 18, and the results are shown in the table below.\n\n| Index | Avg. Unmask Timesteps |\n| ----- | --------------------- |\n| 0     | 9.43                  |\n| 1     | 9.46                  |\n| 2     | 9.51                  |\n| 3     | 9.74                  |\n| 4     | 9.72                  |\n| 5     | 9.83                  |\n| 6     | 9.70                  |\n| 7     | 9.67                  |\n| 8     | 9.42                  |\n\nAs can be seen, the average denoising timestep of the subsequences exhibits a uniform distribution, which is different from that on the Countdown tasks we saw above.\nThis is because the rows in the Sudoku question vary in difficulty, thus prioritizing the denoising of simpler rows (subsequences) leads to a simpler overall sampling path. \nGiven a sufficiently large amount of data, the difficulty distribution across rows is likely to be approximately uniform. \n\nOverall, combining with the observations from Q2 above, we find that  SPMDM  prefers prioritizing the denoising of subsequences that are easier to complete.\n\n\n\n### References\n\n[1] Block Diffusion: Interpolating Between Autoregressive and Diffusion Language Models"}, {"review_id": "umvYwOiDEi", "reviewer": "Reviewer_kRCe", "summary": "This paper highlights the importance of sampling paths in masked diffusion models, emphasizing that effective generation should prioritize tokens near those already decoded and substrings that appear earlier in the reasoning process. To enforce these principles, the authors propose the Simple Path Mask Diffusion Model (SPMDM), which partitions the input sequence into subsequences and assigns each a distinct noise scale. Experiments on toy examples, problem-solving tasks, and a range of reasoning datasets demonstrate that SPMDM achieves superior performance.", "questions": "Can the proposed sampling method be directly applied to a pretrained MDLM? It appears that it can, and it would be valuable to understand how well the method performs in a training-free setting.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n1. The sampling path is a critical research topic for masked diffusion models (MDMs).\n\n2. The paper is clearly written and logically structured, making it easy to follow.\n\n3. The proposed method is well-motivated, intuitive, and straightforward to implement.\n\n## Weakness\nThe main limitation of this paper lies in its choice of baselines. Sampling strategies such as MaskGIT [1] (also referred to as Top-K probability sampling in [2]) and Top-K probability margin sampling [2] are widely adopted in MDM research. Importantly, these strategies can be applied to pretrained MDMs in a training-free manner. Given their relevance and practicality, they should serve as direct baselines for this work. However, the authors did not include comparisons with these methods.\n\n[1] Chang et al. MaskGIT: Masked Generative Image Transformer.\n\n[2] Kim et al. Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions.", "was_revised": true, "final_justification": "My initial concern was that the baseline did not include sampling methods commonly adopted in the field. Since this issue has been resolved in the rebuttal, I am raising my score from 3 to 4. However, as I do not find the proposed approach to be particularly innovative or impactful, I am not assigning a higher score.", "rebuttal": "### W1. Choice of Baselines\n\nThank you for your valuable feedback. We apologize for the misunderstanding and recognize that our sampling procedure (Algorithm 2) may not have been clearly written in the manuscript. \nThe following shows the revised Algorithm 2. In particular, we change $p_\\theta(\\cdot \\mid \\mathbf{x}\\_{t_k}^{k}, \\mathbf{x}\\_{\\mathbf{t}}^{-k})$ to $p_\\theta(\\cdot \\mid \\mathbf{x}\\_{t_k}^{k}, \\mathbf{x}\\_{\\mathbf{t}}^{-k},t_k)$ so as to explicitly show its dependence on the time step $t_k$.\n\n***\n$$\n\\begin{aligned}\n1.\\ & \\textbf{Input:} \\text{Network}\\ p_\\theta, \\text{subsequence length}\\ L, \\text{time}\\ [0, 1], \\text{sampling steps}\\ T, \\text{ordering oracle function}\\ \\mathcal{F} \\\\\\\\\n2.\\ & \\textbf{Initialize}\\ \\mathbf{x}\\_\\mathbf{1} \\sim \\{\\mathbf{m}\\}^N,\\ \\mathbf{t} \\gets \\mathbf{1},\\ \\Delta t \\gets 1 / T \\\\\\\\\n3.\\ & \\textbf{for } n=0 \\text{ to } T \\textbf{ do} \\\\\\\\\n4.\\ & \\quad \\forall k: \\text{Count unmasked tokens } n_k \\\\\\\\\n5.\\ & \\quad \\forall k: t_k \\gets 1 - n_k /L \\\\\\\\\n6.\\ & \\quad \\forall k: \\hat{\\mathbf{x}}\\_{0}^{k} \\sim p_\\theta(\\cdot \\mid \\mathbf{x}\\_{t_k}^{k}, \\mathbf{x}\\_{\\mathbf{t}}^{-k}, t_k) \\\\\\\\\n7.\\ & \\quad \\textbf{if} \\text{ using adaptive sampling strategy } \\textbf{then} \\\\\\\\\n8.\\ & \\quad \\quad \\text{Sample a set of masked token indices } \\mathcal{S} = \\mathcal{F}(\\theta, \\mathbf{x}\\_\\mathbf{t}) \\\\\\\\\n9.\\ & \\quad \\quad \\forall (i, \\ell) \\in \\mathcal{S}: \\mathbf{x}\\_\\mathbf{t}^{i, \\ell} = \\hat{\\mathbf{x}}\\_\\mathbf{0}^{i, \\ell} \\\\\\\\\n10.\\ & \\quad \\textbf{else} \\\\\\\\\n11.\\ & \\quad \\quad \\forall k: s_k \\gets \\max(t_k - \\Delta t, 0) \\\\\\\\\n12.\\ & \\quad \\quad \\forall k: \\text{For all masked tokens, with probability } \\frac{s_k}{t_k}, \\hat{\\mathbf{x}}\\_\\mathbf{0}^{k, \\ell} \\gets \\mathbf{m} \\\\\\\\\n13.\\ & \\quad \\quad \\text{Update } \\mathbf{x}\\_\\mathbf{t} \\gets \\hat{\\mathbf{x}}\\_\\mathbf{0} \\\\\\\\\n14.\\ & \\quad \\textbf{end if} \\\\\\\\\n15.\\ & \\textbf{end for} \\\\\\\\\n16.\\ & \\textbf{Return } \\mathbf{x}\\_\\mathbf{t}\n\\end{aligned}\n$$\n***\n\nMoreover, in the original submission, experimental results on the proposed method (denoted \"Ours\" in section 4.4) use steps 11-13 (note that these steps are directly inherited from the MDLM [1]), while the experimental results on the method denoted \"Ours + Adaptive\" in Figure 3(b) use steps 7-9 with top-K probability sampling.\nIn other words, the commonly-used adaptive sampling strategy mentioned by the reviewer has already been used as a baseline.\n\nAs suggested by the reviewer, we now conduct additional experiment with top-K probability margin sampling, using the setup as in Section 4.4 (Figure 3(b)).\nFor easier comparison, we convert Figure 3(b) to the table below, and add in the results on top-K probability margin sampling (note that 'Ours + Adaptive' in figure 3(b) now corresponds to the entry 'Ours + Top-K Probability Sampling'). \n\n| Task      | Sampling Strategy                        | Accuracy (%) |\n| --------- | ---------------------------------------- | ------------ |\n| CountDown | DDPM                                     | 87.9         |\n| CountDown | Ours                                     | 90.2         |\n| CountDown | Ours + Top-K probability sampling        | 92.7         |\n| CountDown | Ours + Top-K probability margin sampling | 92.9         |\n| Sudoku    | DDPM                                     | 95.4         |\n| Sudoku    | Ours                                     | 99.9         |\n| Sudoku    | Ours + Top-K probability sampling        | 100.0        |\n| Sudoku    | Ours + Top-K probability margin sampling | 100.0        |\n\nAs can be seen, while 'Ours + Top-K probability margin sampling' achieves the best performance, the improvement over 'Ours + Top-K probability sampling' is small. We will add this new comparison and further clarifications in the final version.\n\n### Q1. Training-free Setting Performance\n\nThank you for your question. As suggested, we also add an experiment on the training-free setting with a pretrained MDLM.\nHowever, as mentioned in the response above, \n$p_\\theta(\\cdot \\mid \\mathbf{x}\\_{t_k}^{k}, \\mathbf{x}\\_{\\mathbf{t}}^{-k},t_k)$\ndepends on the time step $t_k$. \nHowever, in the standard MDLM, time step $t_k$ is NOT used in the training. Hence, in order to be used \non a pretrained MDLM, we do not feed the time step into $p_\\theta$ (of the pretrained MDLM).\nThe algorithm (modified from the algorithm above) is shown in the following:\n\n***\n$$\n\\begin{aligned}\n1.\\ & \\textbf{Input: } \\text{Network}\\ p_\\theta, \\text{subsequence length}\\ L, \\text{time}\\ [0, 1], \\text{sampling steps}\\ T \\\\\\\\\n2.\\ & \\textbf{Initialize}\\ \\mathbf{x}\\_\\mathbf{1} \\sim \\{\\mathbf{m}\\}^N,\\ \\mathbf{t} \\gets \\mathbf{1},\\ \\Delta t \\gets 1 / T \\\\\\\\\n3.\\ & \\textbf{for } n=0 \\text{ to } T \\textbf{ do} \\\\\\\\\n4.\\ & \\quad \\hat{\\mathbf{x}}\\_{\\mathbf{0}} \\sim p_\\theta(\\cdot \\mid \\mathbf{x}\\_{\\mathbf{t}}) \\\\\\\\\n5.\\ & \\quad \\forall k: \\text{Count unmasked tokens } n_k \\\\\\\\\n6.\\ & \\quad \\forall k: t_k \\gets 1 - n_k /L \\\\\\\\\n7.\\ & \\quad \\forall k: s_k \\gets \\max(t_k - \\Delta t, 0) \\\\\\\\\n8.\\ & \\quad \\forall k: \\text{For all masked tokens, with probability } \\frac{s_k}{t_k}, \\hat{\\mathbf{x}}\\_\\mathbf{0}^{k, \\ell} \\gets \\mathbf{m} \\\\\\\\\n9.\\ & \\quad \\text{Update } \\mathbf{x}\\_\\mathbf{t} \\gets \\hat{\\mathbf{x}}\\_\\mathbf{0} \\\\\\\\\n10.\\ & \\textbf{end for} \\\\\\\\\n11.\\ & \\textbf{Return } \\mathbf{x}\\_\\mathbf{t}\n\\end{aligned}\n$$\n***\n\nThe following table shows the testing on the Countdown dataset. \nFor comparison, we also include the proposed SPMDM below.\n\n|               | Models | Sampling Strategy                 | Accuracy (%) |\n| ------------- | ------ | --------------------------------- | ------------ |\n| Training-free | MDLM   | DDPM                              | 75.5         |\n| Training-free | MDLM   | Top-K probability sampling        | 85.8         |\n| Training-free | MDLM   | Top-K probability margin sampling | 89.4         |\n| Training-free | MDLM   | Ours                              | 79.2         |\n| With Training | SPMDM  | Ours                              | 90.2         |\n\nAs can be seen, while the proposed subsequence-based sampling method can be applied on a pretrained MDLM and yields performance improvements, the gains are significantly smaller than those obtained by the proposed SPMDM (which modifies both both the training and sampling phases).\nThe results and discussion here will be included in the final version.\n\n\n### References:\n\n[1] Simple and Effective Masked Diffusion Language Models"}, {"review_id": "MZIdhkH2cr", "reviewer": "Reviewer_5B9g", "summary": "This paper introduces the Simple Path Mask Diffusion Model (SPMDM), improving masked diffusion models performance by simplifying sampling paths. The authors identify two key characteristics of efficient sampling: prioritizing tokens near unmasked ones and generating earlier reasoning subsequences. Comprehensive experiments show that SPMDM outperforms existing diffusion and autoregressive models, effectively capturing structural rules and enabling parallel and controllable generation.", "questions": "1. How was the optimal subsequence length (e.g., L=9 for Sudoku) determined? Why not use some regular values, e.g. 16, 32, but using like 9, 81 and 162 for Sudoku?\n\n2. How do you consider applying the proposed model to variable-length generation scenarios? For example, Block Diffusion appends blocks of tokens to the end of the generated sequence after the entire sequence is unmasked, while in the parallel sampling proposed in the paper, parallel sampling requires multiple blocks that are not completely unmasked, which is kind of contradictory.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. SPMDM partitions sequences into subsequences with distinct noise scales, encouraging the model to learn intra-subsequence token dependencies and inter-subsequence logical relationships. This design addresses MDMs’ training challenges where denoising difficulty varies with unmasked token positions .\n2. The paper identifies critical sampling path characteristics (local neighborhood prioritization and logical-order generation), which align with human problem-solving strategies. These insights guide the proposed model’s training and sampling to facilitate more efficient unmasking orders.\n3. SPMDM achieves state-of-the-art performance on complex tasks, outperforming auto-regressive and diffusion baselines. It handles large combinatorial spaces and long-range reasoning better due to its subsequence-based dependency modeling.\n\nWeaknesses\n1. When subsequence length is too short (e.g., L=4), performance drops because subsequences lack sufficient semantic or logical information, hindering inter-subsequence dependency modeling. In addition, long subsequences (e.g., L=16) reduce the need for cross-subsequence reasoning.\n2. There is a lack of a specific method to set up the subsequence length.", "was_revised": true, "final_justification": "I am satisfied with the rebuttal.", "rebuttal": "### W1, W2, Q1. Optimal Subsequence Length\n\nThank you for your insightful comments.\n\nFor datasets with clear structural patterns (e.g., Sudoku), we leveraged the inherent structure for segmentation. Specifically, since Sudoku inputs are 9×9 grids, we used the row length (i.e., 9) as the basis for subsequence segmentation. Here, the question length is 81 (9×9), and we segment the concatenated sequence of question and solution using a subsequence length of 81. As noted in Section 4.4, when the subsequence length is set to 162 (i.e., 81 + 81), the model effectively reduces to MDLM.\n\nFor datasets without obvious structure (e.g., Countdown, GSM8K), we used a fixed subsequence length of 8. Tables 2 and 4 demonstrate that this simple choice yields strong performance across all datasets.\n\nWe acknowledge that optimal sequence length selection is important. We are currently investigating adaptive methods and will include results in the final version if they improve performance.\n\n### Q2. Variable-length Generation Scenarios\n\nThank you for this insightful question. You are correct that our proposed SPMDM method cannot be directly applied to variable-length generation scenarios like Block Diffusion [1].\n\nThe key difference is that Block Diffusion handles variable-length generation through autoregressive modeling of inter-block dependencies, which SPMDM currently lacks. However, as shown in Tables 1-3, our method achieves superior performance compared to Block Diffusion due to its full bidirectional modeling capability, while Block Diffusion is limited by its semi-unidirectional approach and incurs higher computational costs during training.\n\nWe acknowledge that variable-length generation is an important problem. We are actively exploring approaches to extend our method to generate high-quality variable-length sequences while maintaining the performance advantages of SPMDM.\n\n### References\n\n[1] Block Diffusion: Interpolating Between Autoregressive and Diffusion Language Models"}, {"review_id": "6IksuB7rN0", "reviewer": "Reviewer_E7mR", "summary": "This paper introduces the Simple Path Mask Diffusion Model (SPMDM), a method designed to enhance the sampling efficiency and capability of Masked Diffusion Models (MDMs) for discrete sequence generation tasks. Unlike traditional autoregressive models, MDMs support parallel, non-sequential generation, but training can be (quite) challenging due to varying prediction difficulties depending on the positions of unmasked tokens. The authors observe two key properties that characterize efficient sampling paths: (1) tokens near already unmasked positions are easier and should be prioritized, and (2) subsequences appearing earlier in logical reasoning should be decoded first. Leveraging these insights, SPMDM partitions sequences into fixed-length, non-overlapping subsequences, applying varying noise scales to explicitly model both token-level dependencies within subsequences and logical dependencies across subsequences.\n\nMathematically, SPMDM modifies the standard forward and reverse diffusion processes by assigning distinct noising steps to each subsequence, introducing subsequence-specific noise levels. The forward process masks tokens differently across subsequences, and the reverse process denoises them accordingly. The training objective thus explicitly captures subsequence-level dependencies through differentiated noise scales, while the inference step employs a novel sampling mechanism that dynamically adjusts these noise levels based on the current decoding state.\n\nExperiments on synthetic data and structured reasoning benchmarks such as Countdown and Sudoku demonstrate that SPMDM substantially outperforms baseline MDMs and autoregressive models. Further evaluation on broader reasoning tasks, including commonsense reasoning and mathematical word problems, indicates competitive or superior performance compared to established diffusion and autoregressive models. The authors also perform ablation studies to highlight the importance of subsequence length and their novel sampling strategy.", "questions": "Here are my questions and suggestions for the authors to enhance the paper to help cross the acceptance barrier for me: \n\n1. The authors introduce a subsequence-based noise scheduling approach, assigning distinct noise scales to fixed-length subsequences (as formulated in Equations 4–6). However, the paper primarily investigates uniform-length partitions. It would be valuable for the authors to explore and present explicit experimental comparisons with alternative partitioning schemes, such as semantically driven partitions  (based on syntactic structure, logical boundaries, or token-level uncertainty) or dynamically adjusted adaptive-length subsequences. Quantitative results comparing these alternative methods against the proposed uniform-length partitioning would substantially enhance the rigor and robustness of the presented approach.\n\n2. The mathematical exposition around Equations (4–6) describing subsequence-specific noise scheduling currently lacks clarity in several important aspects. Could the authors explicitly clarify:\n   - The exact mechanism for determining or optimizing the subsequence-dependent noise scale parameters ($t_k$) during training, and specifically how this formulation differs mathematically from standard masked diffusion schedules used in previous work (e.g., D3PM, MDLM)? \n   - A detailed derivation or step-by-step intuition for these equations would greatly help me understand the precise modifications introduced by the authors, especially regarding how subsequence-level and token-level dependencies are mathematically decoupled or jointly modeled.\n\n3. While the authors briefly mention computational overhead is minimal, the current paper does not provide a clear analysis or benchmark to support this claim. Could the authors present explicit computational complexity analyses or empirical runtime measurements demonstrating the overhead of managing multiple subsequence-specific noise schedules during training and inference, particularly compared to baseline masked diffusion models? \n\n4. The authors achieve strong empirical results on structured reasoning tasks such as Countdown and Sudoku. However, it remains unclear to me whether these gains extend broadly to less structured, open-ended language generation tasks? Could the authors either provide additional experimental evaluations on such tasks (e.g., language modeling on standard benchmarks like WikiText or OpenWebText), or present a theoretical rationale explicitly discussing conditions under which the proposed subsequence partitioning approach is or is not expected to generalize effectively?\n\n5. The paper mentions compatibility with adaptive sampling (Section 4.4) and briefly shows empirical improvements (Figure 3b). Could the authors expand on the conditions or theoretical intuition under which adaptive sampling interacts effectively with their subsequence-specific noise schedules?", "limitations": "The authors haven't really touched on potential negative societal impacts or broader limitations beyond technical issues. While the method itself seems pretty benign, it'd be helpful for me if they briefly addressed whether better logical reasoning abilities might accidentally make models more convincing at generating misinformation or biased outputs. A quick discussion acknowledging these risks and mentioning potential ways to mitigate them or responsibly deploy the model would strengthen the paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The authors present an intuitive and nicely motivated improvement over standard masked diffusion approaches. They argue clearly (especially through Figure 1) that the ordering of token unmasking significantly affects generation quality, motivating their method of using subsequences with independently controlled noise levels.\n\n- Overall, I find that the central methodological contribution (partitioning sequences into fixed-length subsequences and assigning subsequence-specific noise scales) is a fun, clever. and somewhat original take on masked diffusion models. Mathematically, this translates into adjusting the forward and backward processes (Eqns. 4–6) to explicitly model intra- and inter-subsequence dependencies, potentially addressing well-known shortcomings in traditional masked diffusion.\n\n- Empirically, the results on challenging reasoning benchmarks like Countdown and Sudoku are quite compelling, significantly outperforming standard masked diffusion models (like MDLM, D3PM, SEDD), and even very competitive autoregressive baselines (GPT-2, LLaMA). Achieving near-perfect accuracy on Sudoku, for instance, really convinces me model’s ability to capture structural constraints effectively.\n\n- Early motivation experiments (particularly Figure 1) are quite illustrative to me, clearly highlighting the advantages of carefully chosen sampling trajectories. These provide solid intuition behind the proposed changes.\n\n## Weaknesses  \n\n-Despite a promising core idea, the paper is somewhat thin on (what could be) full methodological rigor. Compared to recent related works such as the cited \"P2\" paper (which conducts extensive, detailed ablations on various modeling choices) the current submission offers minimal systematic exploration. Beyond varying subsequence lengths (Figure 3a), the paper doesn’t investigate different noise schedules or alternative subsequence selection methods in sufficient depth. Given that their core innovation lies in subsequence-based partitioning and noise management, this kind of detailed analysis feels especially necessary.\n\n- The core mathematical description could definitely use more detail and clearer exposition. While the math isn't incorrect (at least what I could define), these equations are currently presented in a somewhat terse manner. It would be helpful to step through at least one equation derivation or clearly explain each variable’s intuitive meaning, to aid readers less familiar with discrete diffusion modeling.\n\n- While the results on structured tasks are quite nice, I'd appreciate if the authors would do more to clarify scalability and applicability beyond these specialized tasks. Specifically, it’s unclear if the subsequence-partitioning strategy will generalize equally well to less structured, more open-ended language generation problems.\n\n- The authors briefly mention that the computational overhead is minimal, but this claim isn’t supported by quantitative details or analysis. Given the complexity of handling multiple noise schedules, some careful characterization of runtime, memory overhead, and scalability should be presented. \n\nOverall, the paper presents an intriguing idea with strong empirical results on structured reasoning tasks but falls short of the rigorous experimentation and detailed mathematical clarity typical of top-tier diffusion modeling papers at NeurIPS.", "was_revised": true, "final_justification": "I am happy to increase my score to a 5 as I believe the paper should be accepted. This should hopefully guarantee the acceptance of the paper.", "rebuttal": "### Q1. Other Partitioning Schemes\n\nThank you for suggesting alternative segmentation strategies. This is indeed a promising direction. Indeed, we have explored similar approaches, including using punctuation marks as delimiters for text segmentation, which is similar to your proposed syntactic-structure-based partitioning.\nHowever, the main challenge is that such  syntactic structures are not available during inference with fully masked sequences.\n\n### Q2. Formulation\n\nThank you for your thoughtful consideration. We'd like to provide a comprehensive response to the concerns you raised.\n\n**About the subsequence-dependent noise scheduler.** \nFor each subsequence $\\mathbf{x}^k$, we independently sample noise scale parameters $t_k \\sim \\mathcal{U}[0, 1]$.\n\nThe fundamental difference from standard masked diffusion models lies in the forward process formulation. In standard MDMs (D3PM, MDLM), the forward process is defined as:\n$$\nq_{t|0}(\\mathbf{x}\\_t^\\ell \\mid \\mathbf{x}\\_0^\\ell) = \\operatorname{Cat}(\\alpha_t \\mathbf{x}\\_0^\\ell + (1 - \\alpha_t) \\mathbf{m}).\n$$\n In contrast, SPMDM's forward process operates at the subsequence level:\n$$\n  q_{\\mathbf{t}\\_k|0}(\\mathbf{x}\\_{t_k}^k \\mid \\mathbf{x}\\_0^k) =  \\prod_{\\ell}^L q_{t_k|0}(\\mathbf{x}\\_{t_k}^{k,\\ell} | \\mathbf{x}\\_{0}^{k,\\ell}), \\ \n      q_{t_k|0}(\\mathbf{x}\\_{t_k}^{k,\\ell} \\mid \\mathbf{x}\\_0^{k,\\ell}) = \\operatorname{Cat}(\\alpha_{t_k} \\mathbf{x}\\_0^{k,\\ell} + (1 - \\alpha_{t_k}) \\mathbf{m}).\n$$\nThis formulation introduces heterogeneous noise levels across subsequences within a single training sample.Meanwhile, the changes in the forward process also lead to modifications in the reverse process and the training objective (NELBO). We provide the detailed derivation and proof in Section 3.2 and Appendix B for your reference.\n\n**About the detailed derivation .** For Equation (4), the original process is $q_{t|0}(\\mathbf{x}\\_t^\\ell \\mid \\mathbf{x}\\_0^\\ell) = \\operatorname{Cat}(\\alpha_t \\mathbf{x}\\_0^\\ell + (1 - \\alpha_t) \\mathbf{m}),$\nand our modification is introduces heterogeneous noise levels across subsequences, which leads to\n $q_{t_k|0}(\\mathbf{x}\\_{t_k}^{k,\\ell} \\mid \\mathbf{x}\\_0^{k,\\ell}) = \\operatorname{Cat}(\\alpha_{t_k} \\mathbf{x}\\_0^{k,\\ell} + (1 - \\alpha_{t_k}) \\mathbf{m}).$\n\nFollowing previous work, we derive the reverse process Equation (5) corresponding to the forward process by applying Bayes’ theorem.\n\nThe modification above results in a different training objective (NELBO), as shown in Equation (6). \nA detailed derivation is provided in Appendix B. \nSince the derivation is somewhat complex, we may not have covered all the details. Please let us know if any parts are unclear.\n\nHere we provide a brief explanation of how our model captures inter-subsequence relationships. As reflected in our training loss:\n$$\n  \\mathcal{L}\\_{\\text{NELBO}} = \\sum_{k=1}^{K} \\mathbb{E}\\_{t_k \\sim [0,1]} \\mathbb{E}\\_{q} \\left[ \\frac{\\alpha_{t_k}'}{1 - \\alpha_{t_k}} \\log p_\\theta(\\mathbf{x}^k \\mid \\mathbf{x}\\_{t_k}^k, \\mathbf{x}\\_\\mathbf{t}^{-k}) \\right],\n$$\nWe shift the modeling unit from individual tokens to subsequences, and assign different noise scales to each subsequence. This design encourages the model to utilize information from other subsequences with lower noise levels, thereby facilitating the learning of inter-subsequence dependencies.\n\n### Q3. Computational Overhead\n\nThank you for raising the question regarding computational overhead. As discussed in Section 3.3, the potential computational overhead of our method compared to MDLM arises from two sources: (1) managing multiple subsequence-specific noise schedules (i.e. step 3 in Algo.1, step 5 in Algo.2), and (2) reintroducing the timestep embedding module (i.e. step 6 in Algo.2). Please kindly refer to the updated version of Algo.2 in our response to reviewer kRCe for clarification.\n\nRegarding the first point, managing separate noise schedules requires only basic matrix operations in PyTorch, which execute in constant time. Consequently, this overhead is negligible in practice.\n\nFor the second point, we found that the official MDLM implementation does not actually remove the timestep embedder—it simply feeds it an all-zero input. Therefore, our reintroduction of timestep embedding incurs no additional computational cost compared to MDLM.\n\nTo empirically validate SPMDM's efficiency, we conducted speed benchmarks on the Countdown dataset using 12K examples (batch size 32) on a single RTX 4090:\n\n|                      | MDLM  | SPMDM |\n| -------------------- | ----- | ----- |\n| Train (token/ms)     | 93.7  | 93.1  |\n| Eval (token/ms)      | 266.8 | 265.1 |\n\nFor sampling (i.e., Algo.2), we measured the generation time for a single sample with 32 sampling steps. The results are reported in the table below:\n\n|                      | MDLM  | SPMDM |\n| -------------------- | ----- | ----- |\n| Sample (s)           | 0.55  | 0.57  |\n\nThese results confirm that our method maintains computational efficiency comparable to baseline approaches while achieving superior performance.\n\n### Q4. Open-ended Language Modeling\n\nAs suggested by the reviewer, we now add an additional experiment on open-ended language modeling using the Text8 dataset (a small, character-level language modeling task). \n\nWe follow [1] for network hyperparameters and dataset splits and compare with methods that employ a similar model size. \nGiven the time constraints of the rebuttal period, we were limited to evaluating on this smaller dataset.\nThe results are presented below (baseline performances are from [1]):\n\n| Method | BPC  |\n| ------ | ---- |\n| D3PM   | 1.45 |\n| SEDD   | 1.39 |\n| MDLM   | 1.38 |\n| SPMDM   | 1.37 |\n\nThe results show that SPMDM achieves performance improvements on plain text generation, though the gains are relatively small. We attribute this to the nature of the Text8 dataset. Unlike reasoning tasks or structured datasets, Text8 lacks explicit inter-subsequence relationships that SPMDM is designed to exploit. \n\nFurthermore, uniform segmentation may inadvertently disrupt natural linguistic dependencies in Text8. This observation reinforces the importance of semantic or syntactic-based segmentation strategies mentioned in your earlier comment (Q1). \n\n### Q5. Effectiveness of Adaptive Sampling\n\nThank you for your thoughtful consideration. \nAs discussed in Section 3.1, the subsequence-specific noise schedule in SPMDM is designed to guide the sampling trajectory to better align with the simple path characteristics.\nSimilarly, adaptive sampling (including both top-K probability sampling and top-K probability margin sampling) aims to unmask the easier and/or more confident tokens first, and thus also encourages the model to follow simpler paths as demonstrated in Figure 1.\nIn other words, both the subsequence-specific noise schedules and the adaptive sampling strategy are motivated by the same underlying principle. Therefore, combining the two can enhance the model's overall performance, as shown in figure 3(b).\n\n\n### References\n\n[1] Simple Guidance Mechanisms for Discrete Diffusion Models"}]

Author rebuttal:

Meta-review: The paper proposes new improved to masked diffusion models (MDMs), which is an interesting alternative to the autoregressive model for language generation and reasoning tasks. The improvement is on proposing a heuristic that improve the decoding order of the MDMs. The experimental results demonstrate the effectiveness of the proposed method. The reviewers all acknowledge the contribution of the paper, and after an effective rebuttal and discussion period, the reviewers are satisfied with the authors' feedback. 

Therefore, I recommend the paper for acceptance at NeurIPS.

AC.
Decision: Accept (poster)