While Masked Diffusion Language Models (MDLMs) relying on token masking and unmasking have shown promise in language modeling, their computational efficiency and generation flexibility remain constrained by the masking paradigm. In this paper, we propose Deletion-Insertion Diffusion language models (DID) that rigorously formulate token deletion and insertion as discrete diffusion processes, replacing the masking and unmasking processes in current MDLMs. DID improves training and inference efficiency by eliminating two major sources of computational overhead in MDLMs: the computations on non-informative 1) <MASK> tokens inherent to the paradigm, and 2) <PAD> tokens introduced in variable-length settings. Furthermore, DID offers greater flexibility by: 1) natively supporting variable-length sequences without requiring fixed-length padding, and 2) an intrinsic self-correction mechanism during generation due to insertion that dynamically adjusts token positions. To train DID, we design a score-based approach that assigns scores to token insertion operations and derive appropriate training objectives. The objectives involve subsequence counting problems, which we efficiently solve via a parallelized dynamic programming algorithm. Our experiments across fixed and variable-length settings demonstrate the advantage of DID over baselines of MDLMs and existing insertion-based LMs, in terms of modeling performance, sampling quality, and training/inference speed, without any hyperparameter tuning.
Figures & tables
Figure 1: Conceptual diagram of MDLMs compared to Deletion-Insertion Diffusion language models (DID).
Size
Method
WikiText
Lambada
Pubmed
AG News
LM1B
Arxiv
PTB
Small
RADD
38.27
51.82
56.99
73.18
72.99
85.95
108.79
DID-S
38.72
49.10
55.02
76.02
74.04
82.41
115.37
DID-F
36.91
48.00
52.89
71.48
72.04
78.38
111.60
Medium
RADD
28.44
44.10
41.06
48.96
60.32
66.28
81.05
DID-S
29.19
41.94
40.84
52.53
59.88
63.95
91.87
DID-F
28.35
41.00
38.71
48.84
58.05
61.77
87.09
Table 1: Zero-shot language modeling perplexity. Results for diffusion models are perplexity upper bounds.
Method
Steps
16
32
64
128
256
512
1024
RADD
PPL
284.78
155.01
111.56
95.10
87.56
84.00
84.05
Entropy
8.35
8.26
8.20
8.15
8.11
8.10
8.09
Time (s)
0.220
0.317
0.499
0.879
1.644
2.882
4.512
DID
PPL
158.93
110.06
97.32
91.25
86.98
86.04
85.35
Entropy
8.15
8.13
8.13
8.12
8.09
8.08
8.09
Time (s)
0.169
0.246
0.353
0.573
1.047
1.826
3.006
Table 2: Generative perplexity (PPL, evaluated by GPT2 Large), unigram entropy, inference time (in seconds), speedup, and average generation length for fixed-length models under different total denoising steps.
Small
Medium
Large
RADD
26.46
53.17
92.90
DID
14.03
27.77
46.60
Speedup
1.89 ×
1.91 ×
1.99 ×
Table 3: Average training time (in seconds) per 50 steps (i.e. batches) on OpenWebText.
Method
Steps
64
128
256
512
ILM
PPL ∗
161.80
137.64
42.29
31.14
Entropy
5.20
5.65
5.97
6.01
Time (s)
0.016
0.034
0.087
0.271
Length
63.34
120.77
206.44
234.44
RADD
PPL ∗
81.92
50.89
34.47
26.78
Entropy
5.22
5.58
5.79
5.85
Table 4: Generative PPL, unigram entropy, inference time (in seconds), and average generation length for variable-length models under different denoising steps. *: as outliers significantly affect PPL, only samples with PPL < 300 are counted, † : speedup over RADD.
Figure 2: Cumulative distribution functions (CDFs) of generation length under different total denoising steps.
Small
Medium
Large
RADD
19.93
37.87
67.75
DID
7.71
12.30
19.83
Speedup
2.58 ×
3.08 ×
3.42 ×
Table 5: Average training time (in seconds) per 50 steps on Stories.
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
Notation
Description
V
Vocabulary.
X=⋃d=0∞Vd
Sequence state space (variable length).
x0,xt,y
Clean sequence; sequence at time t ; another sequence state.
Null token representing deletion or no insertion (not in V ).
Appendix
Table 6: Summary of Key Notations
Size
Layers
Hidden Dimension
Attention Heads
Non-Embedding Parameters
Small
12
768
12
85M
Medium
24
1024
16
302M
Large
36
1280
20
708M
Appendix
Table 7: Model architecture hyperparameters for difference model sizes of RADD and DID.
Small
Medium
Large
DID
14.03
27.77
46.60
DID-DP
2.38 (17.0%)
3.33 (12.0%)
3.35 (7.2%)
Appendix
Table 8: DP efficiency analysis in the fixed-length training setting (Sec. 4.1 ). The overall training time and DP cost for 50 steps are reported (in seconds).
Small
Medium
Large
DID
7.71
12.30
19.83
DID-DP
2.13 (27.6%)
2.01 (16.3%)
2.01 (10.1%)
Appendix
Table 9: DP efficiency analysis in the variable-length training setting (Sec. 4.2 ). The overall training time and DP cost for 50 steps are reported (in seconds).
Sequence Length ( S )
1k
2k
3k
4k
The Power Law Exponent a ( T∝Sa )
DP Time ( T )
2.05
3.64
8.07
11.2
1.26
Appendix
Table 10: The time cost of DP for different sequence lengths. In line with the training setting in Sec. 4 , we set the batch size as 64, and sequence lengths ( S ) as 1k, 2k, 3k, and 4k. The time to perform 50 times of the DP algorithm to get the subsequence count ratios are reported (in seconds).
Method
Steps
16
32
64
128
256
512
1024
RADD
Time
0.240
0.334
0.507
0.872
1.627
2.876
4.506
NFE
0.080
0.161
0.323
0.642
1.262
2.234
3.308
Sampling
0.019
0.036
0.071
0.141
0.280
0.558
1.115
DID
Time
0.171
0.225
0.359
0.604
1.029
1.818
2.987
Speedup (Time)
1.40 ×
1.48 ×
1.41 ×
1.44 ×
1.58 ×
1.58 ×
1.51 ×
NFE
0.029
0.076
0.159
0.323
0.641
1.131
1.712
Appendix
Table 11: Inference time comparison of fixed-length DID and RADD trained on OWT. Times are in seconds.
Method
Steps
64
128
256
512
RADD
Time
0.249
0.452
0.848
1.505
NFE
0.161
0.321
0.631
1.118
Sampling
0.043
0.085
0.170
0.340
DID
Time
0.089
0.135
0.217
0.384
Speedup (Time)
2.78 ×
3.35 ×
3.91 ×
3.92 ×
NFE
0.027
0.058
0.110
0.224
Appendix
Table 12: Inference time comparison of variable-length DID and padding-based RADD trained on Stories. Times are in seconds.
Size
Method
WikiText
Lambada
Pubmed
AG News
LM1B
Arxiv
PTB
Small
RADD
38.27
51.82
56.99
73.18
72.99
85.95
108.79
DID-F w/o SeqNorm
38.55
50.17
53.76
73.25
72.69
81.95
118.63
DID-F
36.91
48.00
52.89
71.48
72.04
78.38
111.60
Appendix
Table 13: Ablation study of sequence-level normalization for fixed-length DID, the zero-shot language modeling perplexity on seven datasets are reported. Results for these diffusion models are perplexity upper bounds.
Figure 3: Evaluation loss curve on Stories dataset for RADD and DID in the variable-length setting.
Method
Steps
16
32
64
128
256
512
1024
RADD
PPL
220.74
140.23
107.42
93.72
85.16
87.79
83.41
Entropy
8.24
8.17
8.14
8.12
8.09
8.09
8.08
Time
0.240
0.364
0.516
0.904
1.606
2.817
4.567
NFE
0.081
0.160
0.315
0.612
1.156
2.022
3.065
Sampling
0.023
0.046
0.090
0.178
0.356
0.708
1.414
DID
PPL
161.21
115.54
99.59
92.52
88.14
87.18
87.00
Appendix
Table 14: Performance comparison with cosine timestep schedule on fixed-length models trained on OWT. Times are in seconds.
Method
Steps
16
32
64
128
256
512
1024
RADD
PPL
95.55
55.21
40.38
34.22
31.79
30.31
30.51
Entropy
7.99
7.89
7.82
7.77
7.70
7.70
7.69
DID
PPL
54.40
36.80
31.73
29.61
28.23
27.29
27.05
Entropy
7.71
7.69
7.69
7.64
7.60
7.60
7.58
Length
1021.88
1023.66
1024.02
1024.12
1023.95
1024.06
1024.12
Appendix
Table 15: Nucleus sampling results for fixed-length models of RADD and DID trained on OpenWebText. Generative perplexity (PPL, evaluated by GPT2 Large), unigram entropy, and average generation length (for DID) under different denoising steps are reported.
Method
Steps
64
128
256
512
ILM
PPL ∗
174.29
27.04
14.50
15.31
Entropy
5.02
5.38
5.44
5.45
Length
62.68
110.05
120.75
122.99
RADD
PPL ∗
50.63
28.62
22.21
16.11
Entropy
4.81
5.20
5.39
5.52
Length
96.14
188.64
228.51
265.53
Appendix
Table 16: Nucleus sampling results for variable-length models of ILM, RADD and DID trained on Stories. Generative perplexity (PPL, evaluated by GPT2 Large), unigram entropy, and average generation length (for DID) under different denoising steps are reported. *: as outliers significantly affect PPL, only samples with PPL < 300 are counted.
Prompt Length
Method
Steps
16
64
256
1024
256
RADD
PPL
114.46
67.13
58.33
55.16
Entropy
8.12
8.03
8.03
8.01
DID
PPL
70.11
50.98
47.47
48.85
Entropy
7.92
7.94
7.92
7.92
Length
1022.48
1023.81
1023.88
1024.00
512
RADD
PPL
52.31
38.17
35.51
35.11
Appendix
Table 17: Conditional generation performance with different prompt lengths on OWT.
Method
Steps
64
128
256
512
RADD-512
PPL ∗
80.19
57.32
40.27
35.45
Entropy
4.89
5.21
5.56
5.63
Time (s)
0.123
0.221
0.383
0.608
Length
91.83
138.70
191.43
207.93
RADD-1024
PPL ∗
81.92
50.89
34.47
26.78
Entropy
5.22
5.58
5.79
5.85
Appendix
Table 18: Ablation study of padding length for RADD in the variable-length setting. Models are trained on Stories for 60K steps. Generative perplexity (PPL, evaluated by GPT2 Large), unigram entropy, inference time (in seconds), and average generation length under different denoising steps are reported. *: as outliers significantly affect PPL, only samples with PPL < 300 are counted.
Figure 4: Cumulative distribution functions (CDFs) of generation length under different total denoising steps.
Size
Method
WikiText
Lambada
Pubmed
AG News
LM1B
Arxiv
PTB
Average
Small
RADD-400k
38.27
51.82
56.99
73.18
72.99
85.95
108.79
69.71
DID-200k
40.50
50.55
57.87
81.02
76.37
85.86
122.84
73.57
DID-400k
38.72
49.10
55.02
76.02
74.04
82.41
115.37
70.10
DID-600k
37.41
48.40
53.59
72.88
72.64
79.94
112.95
68.26
DID-800k
36.91
48.00
52.89
71.48
72.04
78.38
111.60
67.33
Medium
RADD-400k
28.44
44.10
41.06
48.96
60.32
66.28
81.05
52.89
Appendix
Table 19: Zero-shot language modeling perplexity evaluation with more checkpoints.
Method (FLOPs)
Arc-c
Arc-e
Hellaswag
Obqa
Piqa
Race
Siqa
Winogrande
Average
SMDM (1.6e21)
24.57
48.91
44.37
31.20
65.23
33.78
39.00
52.88
42.49
DID (8e20)
25.17
47.73
40.79
31.20
64.58
31.48
38.33
51.62
41.36
DID (1.2e21)
26.11
49.20
43.98
32.80
65.72
32.06
37.97
54.62
42.81
DID (1.6e21)
26.54
49.37
45.72
32.00
66.16
32.44
38.89
54.85
43.25
Appendix
Table 20: Downstream task evaluation of 1.1B models. Zero-shot accuracy (%) is reported for each benchmark.
Top- p strategy
Steps
8
16
32
64
128
256
p=1.0 (direct sampling)
SMDM
27.82
33.97
35.78
36.85
36.54
36.69
DID
31.92
35.41
37.45
39.35
39.27
39.88
p=0.9
SMDM
32.22
36.92
37.38
39.58
39.58
39.65
DID
32.37
38.51
42.38
41.55
42.23
43.75
p=0.6
SMDM
36.01
40.03
40.56
42.00
43.37
42.61
DID
38.82
41.39
43.90
45.26
46.47
46.70
Appendix
Table 21: GSM8K evaluation under different top- p sampling strategies. Zero-shot accuracy (%) is reported.
Masked diffusion models (MDMs) have emerged as a promising alternative to autoregressive models (ARMs) for language modeling. However, MDMs are known to learn substantially more slowly than ARMs, which may become problematic when scaling MDMs to larger models. Therefore, we ask the following question: how can we accelerate standard MDM training while maintaining its final performance? To this end, we first provide a detailed analysis of why MDM training is slow. We find that the main factor is the locality bias of language: the predictive information for a token is concentrated in nearby positions. We further investigate how this bias slows learning and suggest a simple yet effective remedy: bell-shaped time sampling as a training strategy. Notably, MDMs trained with our training recipe reach the same validation negative log-likelihood (NLL) up to ∼4× faster than standard training on One Billion Word Benchmark (LM1B). We also show faster improvements in generative perplexity, zero-shot perplexity, and downstream task performance on various benchmarks.
Masked diffusion language models (MDLMs) decode by repeatedly committing tokens to masked positions, but these commitments are usually irreversible. A token chosen under sparse, partial context is kept fixed, even when later context no longer supports it. Existing samplers mainly decide when to commit a token, but rarely check whether an already committed token should still be kept, allowing early mistakes to propagate. We trace this issue to confidence drift, where the model's confidence in a committed token drops from its sparse commit-time context to the denser context available later. Based on this signal, we propose CoDR (Confidence Drift Remasking), a training-free and sampler-agnostic refinement pass. CoDR estimates drift for all committed positions in only k forward passes via k-partition probing, then remasks and regenerates only the tokens the model no longer endorses. Across two backbones, four reasoning and coding tasks, and three base samplers, CoDR improves average accuracy across all evaluated model-sampler configurations and improves most individual task settings with modest overhead. Controlled experiments show that the gains come from targeted confidence-drift remasking rather than extra compute alone, and that CoDR uses far fewer forward passes than prior remasking methods. Code is available at https://github.com/YueWu0301/CoDR.
Yue Wu, Qinghe Zhang, Yu Zhang +1
The Hong Kong Polytechnic University, Hong Kong, China · Southern University of Science and Technology, Shenzhen, China
Masked diffusion language models enable parallel token generation and offer improved decoding efficiency over autoregressive models. However, their performance degrades significantly when generating multiple tokens simultaneously, due to a mismatch between token-level training objectives and joint sequence consistency. In this paper, we propose ME-DLM, an edit-based refinement framework that augments diffusion generation with lightweight post-editing steps. After producing an initial complete response, the model refines it through minimal edit operations, including replacement, deletion, and insertion, conditioned on the full sequence. Training supervision is derived from edit distance, providing a deterministic signal under a fixed canonicalization scheme for learning minimal corrections. This approach encourages sequence-level consistency through globally conditioned edits while preserving the efficiency benefits of parallel diffusion decoding. Extensive experiments demonstrate that ME-DLM improves the quality and robustness of multi-token parallel generation. In particular, when built upon LLaDA, our method achieves consistent gains of 11.6 points on HumanEval and 33.6 points on GSM8K while using one-eighth of the total diffusion steps. Code is available at https://github.com/renhouxing/ME-DLM.
Houxing Ren, Mingjie Zhan, Zimu Lu +5
CUHK MMLab · SenseTime Research · Shenzhen Loop Area Institute +1