# Insertion Transformer: Flexible Sequence Generation via Insertion Operations

arXiv: https://arxiv.org/abs/1902.03249 · HTML: https://mlsanity.com/paper/1902.03249/

## Key facts

- Cited by 125 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2019.

## Built on by (most cited first, 30 of 125)

- [Diffusion-LM Improves Controllable Text Generation](https://mlsanity.com/paper/2205.14217/) (2022)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [Continuous diffusion for categorical data](https://mlsanity.com/paper/2211.15089/) (2022)
- [Speculative Decoding with Big Little Decoder](https://mlsanity.com/paper/2302.07863/) (2023)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [Learning to Efficiently Sample from Diffusion Probabilistic Models](https://mlsanity.com/paper/2106.03802/) (2021)
- [AR-Diffusion: Auto-Regressive Diffusion Model for Text Generation](https://mlsanity.com/paper/2305.09515/) (2023)
- [Step-unrolled Denoising Autoencoders for Text Generation](https://mlsanity.com/paper/2112.06749/) (2021)
- [Text Generation with Diffusion Language Models: A Pre-training Approach with Continuous Paragraph Denoise](https://mlsanity.com/paper/2212.11685/) (2022)
- [BLT: Bidirectional Layout Transformer for Controllable Layout Generation](https://mlsanity.com/paper/2112.05112/) (2021)
- [A Survey on Non-Autoregressive Generation for Neural Machine Translation and Beyond](https://mlsanity.com/paper/2204.09269/) (2022)
- [Relaxing the Conditional Independence Assumption of CTC-based ASR by Conditioning on Intermediate Predictions](https://mlsanity.com/paper/2104.02724/) (2021)
- [Edit Flows: Flow Matching with Edit Operations](https://mlsanity.com/paper/2506.09018/) (2025)
- [FastCorrect: Fast Error Correction with Edit Alignment for Automatic Speech Recognition](https://mlsanity.com/paper/2105.03842/) (2021)
- [MuseMorphose: Full-Song and Fine-Grained Piano Music Style Transfer with One Transformer VAE](https://mlsanity.com/paper/2105.04090/) (2021)
- [Non-Autoregressive Translation with Layer-Wise Prediction and Deep Supervision](https://mlsanity.com/paper/2110.07515/) (2021)
- [Learning to Reason and Memorize with Self-Notes](https://mlsanity.com/paper/2305.00833/) (2023)
- [A Comparative Study on Non-Autoregressive Modelings for Speech-to-Text Generation](https://mlsanity.com/paper/2110.05249/) (2021)
- [Parallel Refinements for Lexically Constrained Text Generation with BART](https://mlsanity.com/paper/2109.12487/) (2021)
- [Investigating the Reordering Capability in CTC-based Non-Autoregressive End-to-End Speech Translation](https://mlsanity.com/paper/2105.04840/) (2021)
- [Learning to Complete Code with Sketches](https://mlsanity.com/paper/2106.10158/) (2021)
- [Sketch and Refine: Towards Faithful and Informative Table-to-Text Generation](https://mlsanity.com/paper/2105.14778/) (2021)
- [Diffusion-NAT: Self-Prompting Discrete Diffusion for Non-Autoregressive Text Generation](https://mlsanity.com/paper/2305.04044/) (2023)
- [An Imitation Learning Curriculum for Text Editing with Non-Autoregressive Models](https://mlsanity.com/paper/2203.09486/) (2022)
- [Arrows of Time for Large Language Models](https://mlsanity.com/paper/2401.17505/) (2024)
- [Why is constrained neural language generation particularly challenging?](https://mlsanity.com/paper/2206.05395/) (2022)
- [DreamOn: Diffusion Language Models For Code Infilling Beyond Fixed-size Canvas](https://mlsanity.com/paper/2602.01326/) (2026)
- [Non-autoregressive Generative Models for Reranking Recommendation](https://mlsanity.com/paper/2402.06871/) (2024)

## Abstract (arXiv)

We present the Insertion Transformer, an iterative, partially autoregressive model for sequence generation based on insertion operations. Unlike typical autoregressive models which rely on a fixed, often left-to-right ordering of the output, our approach accommodates arbitrary orderings by allowing for tokens to be inserted anywhere in the sequence during decoding. This flexibility confers a number of advantages: for instance, not only can our model be trained to follow specific orderings such as left-to-right generation or a binary tree traversal, but it can also be trained to maximize entropy over all valid insertions for robustness. In addition, our model seamlessly accommodates both fully autoregressive generation (one insertion at a time) and partially autoregressive generation (simultaneous insertions at multiple locations). We validate our approach by analyzing its performance on the WMT 2014 English-German machine translation task under various settings for training and decoding. We find that the Insertion Transformer outperforms many prior non-autoregressive approaches to translation at comparable or better levels of parallelism, and successfully recovers the performance of the original Transformer while requiring only logarithmically many iterations during decoding.