Insertion-based Decoding with Automatically Inferred Generation Order

By Jiatao Gu, Qi Liu, Kyunghyun Cho. 2019

122 citations recorded by the source corpus.

Abstract Conventional neural autoregressive decoding commonly assumes a fixed left-to-right generation order, which may be sub-optimal. In this work, we propose a novel decoding algorithm— InDIGO—which supports flexible sequence generation in arbitrary orders through insertion operations. We extend Transformer, a state-of-the-art sequence generation model, to efficiently implement the proposed approach, enabling it to be trained with either a pre-defined generation order or adaptive orders obtained from beam-search. Experiments on four real-world tasks, including word order recovery, machine translation, image caption, and code generation, demonstrate that our algorithm can generate sequences following arbitrary orders, while achieving competitive or even better performance compared with the conventional left-to-right generation. The generated sequences show that InDIGO adopts adaptive generation orders based on input information.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

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 Computer Vision and Pattern Recognition

In Natural Language Processing

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.”
Imputer: Sequence Modelling via Imputation and Dynamic Programming (2020, methodology): “The Insertion Transformer (Stern et al., 2019) and other insertion-based models (Gu et al., 2019a; Welleck et al., 2019; Chan et al., 2019b; Li & Chan, 2019; Ruis et al., 2019) generates sequences through a series of insertions.”
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”
Offline Reinforcement Learning as One Big Sequence Modeling Problem (2021, background): “…language, this design corresponds to generating sentences in the linear order in which they are spoken as opposed to an ordering reﬂecting their hierarchical syntactic structure (see, however, Gu et al. 2019 for a discussion of non-left-to-right sentence generation with autoregressive models).”
Efficient Training of Language Models to Fill in the Middle (2022, background): “XLNet [Yang et 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 b”
Insertion Transformer: Flexible Sequence Generation via Insertion Operations (2019, methodology): “We must also mention the concurrent work of Gu et al. (2019).”
Enabling Language Models to Fill in the Blanks (2020, background): “Many systems are unable to automatically determine span length, and thus, can only inﬁll ﬁxed-length spans (Fedus et al., 2018; Devlin et al., 2019; Yang et al., 2019; Joshi et al., 2019; Gu et al., 2019; Liu et al., 2019).”
Real or Fake? Learning to Discriminate Machine from Human Generated Text (2019, background): “r review. arXiv:1906.03351v1 [cs.LG] 7 Jun 2019 2 Related Work While there is ongoing effort towards generating text without specifying a word ordering [Kaiser et al., 2018, Stern et al., 2018, 2019, Gu et al., 2019, Ghazvininejad et al., 2019], the dominant approach to text generation is still base”
Levenshtein Transformer (2019, background): “Welleck et al. (2019); Stern et al. (2019); Gu et al. (2019) generate translations non-monotonically by adding words to the left or right of previous ones or by inserting words in arbitrary order to form a sequence.”
Blank Language Models (2020, methodology): “Another stream of work focuses on generating sequences in a non-autoregressive fashion for fast decoding in machine translation (Gu et al., 2017; Lee et al., 2018; Stern et al., 2019; Gu et al., 2019b).”
Logical Natural Language Generation from Open-Domain Tables (2020, background): “Non-monotonic Generation There have been attempts recently to study the problem of non-monotonic text generation, which aims to teach the generation model to learn the generation order without external supervision (Ford et al., 2018; Welleck et al., 2019; Gu et al., 2019; Mansimov et al., 2019).”
Deep Encoder, Shallow Decoder: Reevaluating the Speed-Quality Tradeoff in Machine Translation (2020, unknown): “Non-autoregressive Translation In addition to the work already discussed, several other works proposed to iteratively reﬁne (or insert) output predictions (Mansimov et al., 2019; Stern et al., 2019; Gu et al., 2019a; Chan et al., 2019a,b; Li et al., 2020).”
A Survey of Transformers (2021, background): “As a special case, InDIGO [39] sets 𝐾 to 3 for their specially designed framework for non-autoregressive generation.”
Neural Machine Translation: A Review (2019, background): “, 2019), insertionbased (Gu et al., 2019; Stern et al., 2019; Östling & Tiedemann, 2017; Gu et al., 2019), or in source sentence order (Stahlberg et al.”
Insertion-Deletion Transformer (2020, background): “Recently, research in insertion-based non- or partially- autoregressive models has spiked (Stern et al., 2019; Welleck et al., 2019; Gu et al., 2019a; Chan et al., 2019).”
FlowSeq: Non-Autoregressive Conditional Sequence Generation with Generative Flow (2019, background): “However, this assumption of left-to-right factorization may be sub-optimal from a modeling perspective (Gu et al., 2019; Stern et al., 2019), and generation of outputs must be done through a linear left-to-right pass through the output tokens using beam search, which is not easily parallelizable on…”
Big Bidirectional Insertion Representations for Documents (2019, background): “Recently, insertion-based models (Stern et al., 2019; Welleck et al., 2019; Gu et al., 2019; Chan et al., 2019) have been introduced for text generation.”
An Empirical Study of Generation Order for Machine Translation (2019, methodology): “, 2019), random (Gu et al., 2019), or balanced binary trees (Stern et al.”
Non-Autoregressive Transformer Automatic Speech Recognition (2019, unknown): “Another direction explored in previous studies is to allow the output sequence to grow dynamically [7, 8, 9].”
Deep Encoder, Shallow Decoder: Reevaluating Non-autoregressive Machine Translation (2020, unknown): “Non-autoregressive Machine Translation In addition to the work already discussed, several other works proposed to iteratively reﬁne (or insert) output predictions (Mansimov et al., 2019; Stern et al., 2019; Gu et al., 2019a; Chan et al., 2019; 2020; Li et al., 2020; Guo et al., 2020).”