Insertion Transformer: Flexible Sequence Generation via Insertion Operations

By Mitchell Stern, William Chan, Jamie Ryan Kiros, Jakob Uszkoreit. 2019

283 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Natural Language Processing, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

In Model Architectures

Citations in the corpus

Defending Against Neural Fake News (2019, background): “This also suggests that recent progress on generating text in any order (Gu et al., 2019; Stern et al., 2019; Ghazvininejad et al., 2019) may lead to models that evade a Grover discriminator.”
KERMIT: Generative Insertion-Based Modeling for Sequences (2019, methodology): “However, unlike Stern et al. (2019) we did not need to tune an EOS penalty, but simply set it to zero for all experiments.”
InCoder: A Generative Model for Code Infilling and Synthesis (2022, background): “Recent work addresses this by changing model architectures, inference procedures, and training objectives [2, 59, 67, 3].”
Imputer: Sequence Modelling via Imputation and Dynamic Programming (2020, methodology): “Insertion Transformer has been shown to generate sequences in log-arithmic log n iterations (Stern et al., 2019), where as the Imputer requires constant generation steps.”
Mask-Predict: Parallel Decoding of Conditional Masked Language Models (2019, methodology): “Unlike recently proposed insertion models (Gu et al., 2019; Stern et al., 2019), which treat each token as a separate training instance, CMLMs can train from the entire sequence in parallel, resulting in much faster”
CommonGen: A Constrained Text Generation Challenge for Generative Commonsense Reasoning (2020, background): “Recent advances (Lee et al., 2018; Stern et al., 2019) in conditional sentence generation have an emerging interest on (edit-based) non-autoregressive generation models, which iteratively reﬁne generated sequences.”
Efficient Training of Language Models to Fill in the Middle (2022, background): “…al., 2019] modifies the attention mask in a standard transformer to enable token generation in any userspecified order, while Insertion Transformer [Stern et al., 2019], KERMIT [Chan et al., 2019], and InDIGO [Gu et al., 2019] allow the model to predict a location for the next token before…”
Learning to Efficiently Sample from Diffusion Probabilistic Models (2021, background): “…very closely related to DDPMs, there has also been work on non-autoregressive modeling of text sequences that can be regarded as discrete-space DDPMs with a forward process that masks or remove tokens [Lee et al., 2018, Gu et al., 2019, Stern et al., 2019, Chan et al., 2020, Saharia et al., 2020].”
Levenshtein Transformer (2019, background): “The two-stage insertion process can also be viewed as a hybrid of Insertion Transformer (Stern et al., 2019) and masked language model (MLM, Devlin et al.”
Blank Language Models (2020, methodology): “, 2018) or the Insertion Transformer (Stern et al., 2019), BLM uses blanks to control which part of the sequence to expand.”
Understanding Knowledge Distillation in Non-autoregressive Machine Translation (2019, methodology): “…K decoding passes (instead of just one) to iteratively reﬁne the generated outputs (Lee et al., 2018; Ghazvininejad et al., 2019; Wang et al., 2018; Stern et al., 2018; 2019; Gu et al., 2019); (2) using latent variables (Kaiser et al., 2018; Ma et al., 2019; Shu et al., 2019) or structured…”
An Empirical Study of Generation Order for Machine Translation (2019, methodology): “Some of them also match the quality of state-of-the-art left-to-right models (Stern et al., 2019).”
EDITOR: An Edit-Based Transformer with Repositioning for Neural Machine Translation with Soft Lexical Constraints (2020, methodology): “Following Stern et al. (2019), we also experiment with adding penalty for inserting “empty” placeholders during inference by subtracting a penalty score γ = [0, 3] from the logits of zero in Eq.”
Seq2Edits: Sequence Transduction Using Span-level Edit Operations (2020, methodology): “Similar operations such as insertions and deletions have also been used for machine translation (Gu et al., 2019b; Stern et al., 2019; Gu et al., 2019a; Östling and Tiedemann, 2017; Stahlberg et al., 2018).”
SmBoP: Semi-autoregressive Bottom-up Semantic Parsing (2020, background): “We extend the notion of Z 0 recall to all decoding steps, where Z t recall is whether all gold t -high sub-trees were generated at step t .”
Continuous diffusion for categorical data (2022, background): “Insertion (Stern et al., 2019) and Lev-enshtein (Gu et al., 2019) transformers demonstrated good parallel decoding results on machine translation along with editing capabilities.”