Birth, Death and Diff: Insertion-Based Sequence Generation with Corrections

Durga Prasad Maram; Dhruvesh Patel; Tahira Naseem; Benjamin Rozonoyer; Gaurav Pandey; Ramón Fernandez Astudillo; Andrew McCallum

cs.LGOct 25, 2026

Birth, Death and Diff: Insertion-Based Sequence Generation with Corrections

Authors: Durga Prasad Maram, Dhruvesh Patel, Tahira Naseem, Benjamin Rozonoyer, Gaurav Pandey, Ramón Fernandez Astudillo, Andrew McCallum

Organizations: University of Massachusetts Amherst · IBM Research

Abstract

Insertion-based masked diffusion models enable flexible-length, parallel generation by interleaving mask insertion with token unmasking. However, because their generation decisions are irreversible, aggressive parallel decoding can introduce errors that subsequent steps cannot correct, necessitating conservative decoding with more forward passes (NFEs). Moreover, they exhibit higher entropy than standard MDMs because they marginalize over multiple alignments during training and therefore require even more conservative decoding in the absence of a correction mechanism. To address this limitation, we introduce $δ$ MDM, which makes intermediate generations revisable by equipping an insertion-based model with substitution and deletion operations. During training, we expose the model to errors caused by aggressive unmasking and insertion, teaching it to correct its own mistakes. At inference time, we interleave insertion and unmasking with correction steps that can revise previously unmasked tokens and remove unnecessary masks. This mechanism makes aggressive decoding practical, improving both generation speed and quality. $δ$ MDM Pareto-dominates FlexMDM, a vanilla insertion-based MDM, on the speed--quality trade-off. On high-diversity unconditional text generation on OpenWebText, it halves the generative perplexity relative to FlexMDM at the highest inference budget. It also achieves lower generative perplexity at all inference budgets compared to MDM trained from scratch with variable-length padded sequences. On low-diversity conditional text generation on TinyGSM, it matches FlexMDM accuracy with half as many NFEs.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of the $\updelta$ MDM generation process. The plots on the right show GSM8K code-execution accuracy and OpenWebText generative perplexity versus the sampling budget. Numeric annotations on the OpenWebText plot are token-entropy values.

Panel of Figure 2 — Figure 2: Two alignments of the same $x_{t}$ to the same $x_{1}$ : $s_{t}=(1,2,4)$ and $\tilde{s}_{t}=(1,3,4)$ .

Panel of Figure 3 — Figure 3: $\updelta$ MDM Training Step. Left: Algorithm 1 ; right: toy example. The three shaded blocks in the algorithm correspond to stages 1–3 of the illustration. 1 Proposal training as described in Section 2.2 . 2 Sample proposal by filling every position with the argmax of $K^{\theta}$ , including tokens already unmasked in $x_{t}$ , and inserting from a Poisson count with mean between 0 and $g^{\theta,i}(x_{t})$ for each gap. All counts are drawn in the coordinates of $x_{t}$ , and inserting them shifts every later token to the right ( $\Expand$ , Section 3.1 ). In the example the argmax replaces the already-unmasked $A$ with $Z$ , and the correction target at that cell remains $A$ . 3 Correction training by aligning $y_{t}$ to $x_{1}$ via $q_{t}=\Expand(s_{t},N_{{{\textnormal{in}}}})$ ( Section 3.1 ): each new cell is aligned to a missing ground-truth position, or gets $-1$ and is deleted by predicting [DEL] . Then we substitute tokens ( $\mathcal{L}_{\mathrm{subs}}$ ), fill the leftmost new [M] s, and delete the excess [M] s from the right ( $\mathcal{L}_{\mathrm{del}}$ ).

Figure 4

Model	Gen. PPL ( $\downarrow$ )						Entropy ( $\uparrow$ )
Steps $T$	32	64	128	256	512	1024	32	64	128	256	512	1024
MDM	230.96	87.48	54.18	45.08	40.10	38.16	3.33	3.59	3.98	4.32	4.56	4.71
ILM †	-	-	222.19	53.70	51.21	49.74	-	-	4.27	4.42	4.30	4.42
DILM-S †	-	-	36.10	29.91	23.20	21.21	-	-	3.45	3.61	3.71	3.79
FlexMDM	73.80	57.59	48.83	43.81	42.80	40.37	4.83	4.87	4.89	4.88	4.88	4.88
$\updelta$ MDM	75.23	46.76	32.85	25.94	22.89	20.35	4.47	4.55	4.60	4.64	4.69	4.72

Table 1: Generative perplexity and token entropy under GPT-2 Large at different sampling budgets

T

(network forward passes).

\updelta

MDM uses insertion scale

\lambda=0.90

and one correction step per proposal step from the start, both counted in

T

. † ILM ( Patel et al., 2025c ) and DILM-S ( Patel et al., 2026a ) , replicated from the implementation and checkpoints provided by Patel et al. (2026a) .

Model	GSM8K pass@1 (%, $\uparrow$ )
Steps $T$	125	250	500	1000	1500
MDM	37.38	40.71	$40.33$	$40.64$	$41.09$
FlexMDM	$8.72$	$20.77$	$31.77$	$40.41$	$41.39$
$\updelta$ MDM	$20.62$	$33.06$	42.23	46.85	47.01

Table 2: GSM8K test pass@1 vs. budget

T

(forward passes). MDM and FlexMDM are trained for 800k steps and

\updelta

MDM for 400k.

\updelta

MDM uses

\lambda=1.75

and one correction step per proposal step from the start, both counted in

T

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Sequences and spaces
Notation	Description
$[\![n]\!]$	The set $\{1,2,\ldots,n\}$
${\mathbb{V}}$	Vocabulary of tokens, including the mask token [M]
[M]	Mask token
[D]	Marker for a dropped position; not part of ${\mathbb{V}}$ and never seen by the model
[DEL]	Deletion token; the correction target for surplus inserted masks

Appendix

Table 3: Summary of notation used throughout the paper.

Hyperparameter	Value
Layers	$12$
Hidden size	$768$
Attention heads	$12$
Feed-forward width	$3072$
Rotary dimension	$64$
Dropout	$0.1$

Appendix

Table 4: Architecture and optimization settings shared by all trained models. The parameter count is the transformer body and excludes token embeddings.

Model	Star ${}_{\text{easy}}$ ( $\uparrow$ )	Star ${}_{\text{medium}}$ ( $\uparrow$ )	Star ${}_{\text{hard}}$ ( $\uparrow$ )
MDM	100	100	74.38
FlexMDM	92.00	93.13	7.27
Ours	98.70	98.60	96.47

Appendix

Table 5: Star-graph exact match (%) at

T{=}500

sampling steps.

Figure 7: Star

{}_{\text{hard}}

exact match (

\uparrow

) vs. sampling budget for

\updelta

MDM and FlexMDM at

T\in\{32,64,128,256,512\}

Model	250	500	1000
FlexMDM	$20.77$	$31.77$	$40.41$
FlexMDM (time-blind)	$21.00$	$31.84$	$38.13$

Appendix

Table 6: GSM8K test pass@1 (%) vs. sampling budget

T

for FlexMDM and time-blind FlexMDM, both trained for 800k steps.

Panel of Figure 10 — Figure 10: Entropy vs. generation perplexity (GPT-2 Large) on OWT for nucleus sampling with $p\in\{0.9,0.95,0.99,1\}$ at the remaining sampling budgets.

Panel of Figure 11 — Figure 11: Distribution of substitution and deletion intensity over normalized time for $\updelta$ MDM on OWT.

Panel of Figure 13 — Figure 13: GSM8K pass@1 vs. insertion scale at sampling budgets $T\in\{250,500,1000\}$ .

Diffusion Language Models

Diffusion language models generate and refine text through iterative denoising, enabling bidirectional context and parallel token updates.

See all 471 papers

Beyond Masks: Efficient, Flexible Diffusion Language Models via Deletion-Insertion Processes
Mar 4, 2026Fangyu Ding, Ding Ding, Sijin Chen +8Diffusion Language Models Language Modeling
HKUST · Huawei Foundation Model Dept · CUHK
Learn from Your Mistakes: Self-Correcting Masked Diffusion Models
Feb 12, 2026Yair Schiff, Omer Belhasin, Roy Uziel +6Masked Diffusion Models Diffusion Language Model Decoding
Cornell · NVIDIA
Random Remasking Scales Masked Diffusion Inference
Oct 22, 2026Zhaoyi Zhou, Frank Wu, Andrea ZanetteMasked Diffusion Models Diffusion Language Model Inference
Carnegie Mellon University

Mar 4, 2026J/K move · Enter open · S save

Beyond Masks: Efficient, Flexible Diffusion Language Models via Deletion-Insertion Processes

Fangyu Ding, Ding Ding, Sijin Chen, Kaibo Wang+7

HKUST · Huawei Foundation Model Dept · CUHK

Diffusion Language Models Language Modeling Masked Diffusion Models Diffusion Model Inference Acceleration

Open paper AskPDF arXiv

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.

Abstract

Diffusion Language Models

Explore similar work

Beyond Masks: Efficient, Flexible Diffusion Language Models via Deletion-Insertion Processes

Learn from Your Mistakes: Self-Correcting Masked Diffusion Models

Random Remasking Scales Masked Diffusion Inference