Beyond In-Place Corruption: Insertion and Deletion In Denoising Probabilistic Models

1. Introduction

• Autoregressive models generate tokens one at a time, while DDPMs iteratively corrupt data and learn a reverse denoising process, enabling generation in fewer steps in some cases.The cited work reports DDPMs achieving results comparable to autoregressive models in some cases.Source: §1 · p. 1
• In-place corruption cannot easily compensate when a word or phrase is placed in the wrong position.The cited limitation applies to the diffusion models described in the passage.Source: §1 · p. 1
• Levenshtein and Insertion-Deletion transformers address in-place edit limits, but were not designed as purely generative models and generally lack likelihood estimates through both edit phases.The cited works are Gu et al. (2019) and Ruis et al. (2020).Source: §1 · p. 1
• The paper integrates insertion and deletion into DDPMs, designs a tractable corruption process, and reports arithmetic-sequence gains and text error correction on misaligned inputs.The framework generalizes multinomial diffusion models (Hoogeboom et al., 2021) and D3PMs (Austin et al., 2021).Source: §1 · p. 1

2.1. Denoising diffusion probabilistic models

• DDPMs define a forward Markov chain toward a known noise distribution and train a reverse process to match forward posteriors, yielding gradual denoising and a tractable log-likelihood bound.Discrete variants include mixture-based transitions and wider structured transition matrices; recent diffusion models corrupt tokens in place.Source: §2.1 · p. 2

2.2. Levenshtein and Insertion-Deletion Transformers

• The Levenshtein Transformer predicts deletions, insertion counts, and inserted token values to recover a dataset example from a noisy proposal.It imitates edit actions computed by a dynamic program.Source: §2.2 · p. 2
• The Insertion-Deletion Transformer performs insertion steps before one deletion phase, while both edit-based approaches target sequence-to-sequence tasks and lack tractable sample log-likelihood estimates.They use hand-designed losses for the insertion and deletion phases.Source: §2.2 · p. 2

3. Method

• The design targets a diffusion-based insertion-deletion generator with tractable likelihood bounds and reverse insertion, deletion, and replacement operations.Source: §3 · p. 2, §3.1 · p. 2

3.1. Forward Process

• Forward corruption removes prior DEL markers, samples token replacements or deletions, and inserts geometrically many INS markers; marker constraints ensure unique one-step alignments.Source: §3.1 · p. 2

3.2. Parameterization of the reverse process

• The reverse model removes INS, predicts prior token values and preceding DEL counts, then uses an inferred edit summary to derive each denoising transition.Source: §3.2 · pp. 2–3

3.3. Loss function

• The standard evidence bound is optimized with a closed-form inner expectation; its terminal term uses a tabular distribution over all-DEL sequence lengths.Source: §3.3 · p. 3

3.4. Computational considerations

• Many skipped markers create multiple possible intermediate paths; PFST composition marginalizes irrelevant intermediates, while conditioning on edit summaries enables closed-form terms.Source: §3.4 · pp. 3–4

• Moderate insertion/deletion probabilities improve log-likelihoods and yield generated arithmetic sequences with fewer deviations from a valid step size.Source: §4 · p. 4
• The experiment augments a 10-step multinomial diffusion corruption process with varying insertion and deletion probabilities.Source: §4 · p. 4
• When insertions and deletions are too frequent, noise overpowers the data patterns and accuracy falls.Source: §4 · p. 4

5. Experiment: Text generation

• The text8 insert-delete model has slightly worse log-likelihood bounds than the in-place model, but still produces high-quality samples.The model uses 32 steps.Source: §5 · p. 4
• The model can correct spelling errors and insert spaces between words, showing qualitative edits beyond ordinary generation.These capabilities appear without fine-tuning on the spellchecking task.Source: §5 · p. 4
• Given a badly written sentence as x10, sampling from pθ(x0|x10) yields imperfect but intuitive suggestions, whereas an in-place model produces nonsense.Source: §5 · p. 4

6. Discussion

• The proposed class of denoising generative models includes insertion and deletion alongside in-place replacements.The discussion suggests possible applications to image super-resolution, video generation, and molecular structure generation, and future corruption edits such as duplication or reordering.Source: §6 · p. 4

A. Other related work

• Related work spans structured diffusion (Seff et al., 2019; Chan et al., 2020), latent-space editing (Guu et al., 2018), text simplification (Dong et al., 2019), and edit-based code bug-fixing (Yin et al., 2019; Zhao et al., 2019; Yao et al., 2021).Source: A. Other related work · p. 7

B. Computing probabilities with PFSTs

• Probabilistic finite-state transducers are used to compute probabilities for the forward process and learned reverse process.Source: B. Computing probabilities with PFSTs · p. 7

B.1. Notation for PFST representations

• PFST transitions encode probabilistic consumption and production; empty input or output represents insertion or deletion, respectively.The multi-step probabilities use αt for insertion summaries, βt for deletion summaries, and Qt for token replacement probabilities, including silent edit pairs.Source: §B.1 · p. 7
• Figure 5 represents q(xt|xt−1), q(xt−1|x0), and their joint q(xt, xt−1|x0) as transducers.Source: Figure 5 · p. 7

B.2. Calculating q(xt|x0) from q(xt|xt−1)

• To derive q(xt|x0), the method composes transducers for successive steps and marginalizes out the intermediate sequence xt−1.Figure 6 represents the resulting transducer; its equations account for insertions, deletions, and replacements, including cases where an insertion-deletion pair appears as a replacement.Source: §B.2 · p. 8, Figure 6 · p. 8

B.3. Closed form of q(xt−1|xt, x0, a0→t)

• The edit summary a0→t records replacements, insertions, and deletions, but can leave the specific intermediate transitions ambiguous.The inference procedure combines probabilities of explicit deletions with a negative-binomial model for insertion-deletion pairs; the number of explicit deletions is modeled as a sum of Bernoulli variables. The implementation assumes tokens are equally likely to be deleted at each step, and treats deletion-insertion pairs as an insertion preceded by a deletion to simplify computation.Source: §B.3 · pp. 8–9

C.1. Model architecture

• The decoder-only T5-architecture transformer has six or twelve layers, depending on the task, and uses two output heads.Source: §C.1 · p. 9
• One head predicts replacement or insertion edits for each token; the other predicts the number of deletion edges before each token.The latter head is also used at EOS to determine the number of edits at the sequence end.Source: §C.1 · pp. 9–10
• For the arithmetic task, Figure 7 shows the noise schedule at r = 0.6; its red probability mass is divided evenly among the other 511 dataset tokens.Schedules for other r values have higher or lower α and Qx⟨DEL⟩.Source: Figure 7 · p. 10
• A fixed-size table pθ(|xT|) models the distribution of observed terminal sequence lengths.Source: §C.1 · p. 10

C.2. Arithmetic sequences

• Sequences vary step size, direction, length, and starting position, with terms constrained to 2–511 and lengths to 32–64.The step size is sampled from 1–10, subject to s(ℓ−1) < 509.Source: §C.2 · p. 10
• Four insert/delete rates, r ∈ {0, 0.4, 0.6, 0.8}, define schedules that add less noise near time 0 and more as t approaches 10.The schedules target cumulative deletions, insertions, and random replacements; r = 0 delays insertion and deletion until the final length-prediction step.Source: §C.2 · p. 10
• Each schedule is trained with a six-layer transformer for 100,000 minibatches, with results averaged across five random seeds.Validation metrics average the final 10,000 training steps; ELBO estimates use 46,080 examples and error rates use 2,304 generated samples.Source: §C.2 · p. 10

C.3. Text generation on text8

• Training examples are randomly selected 118-character chunks, with a 31-token vocabulary including characters, space, INS, DEL, and EOS.The dataset vocabulary also includes an extra hyphen token absent from the text8 dataset.Source: §C.3 · p. 10
• Four insert/delete rates use schedules with less noise near time 0, and the text8 corruption process has 32 steps.Random replacements are drawn from the 28 text8 characters.Source: §C.3 · p. 10
• For each insert/delete rate, twelve-layer transformers train for 1,000,000 minibatches across four learning rates and three schedule types.The schedule types are constant after warmup, reciprocal-square-root decay after warmup, and cyclical cosine.Source: §C.3 · pp. 10–11
• Preliminary bits/character measurements use 40,960 validation segments and average performance across the final 100,000 training steps.The authors report this as a preliminary estimate because training appeared to converge before 900,000 steps.Source: §C.3 · p. 11
• The typo-repair example samples five outputs from each of the 0.6 and 0.0 insert/delete-rate models, conditioned on a padded typo-ridden sentence.The input is padded to length 119; placeholder text is trimmed from the outputs without other edits.Source: §C.3 · p. 11