Levenshtein Transformer

By Jiatao Gu, Changhan Wang, Jake Zhao. 2019

401 citations recorded by the source corpus.

Modern neural sequence generation models are built to either generate tokens step-by-step from scratch or (iteratively) modify a sequence of tokens bounded by a fixed length. In this work, we develop Levenshtein Transformer, a new partially autoregressive model devised for more flexible and amenable sequence generation. Unlike previous approaches, the atomic operations of our model are insertion and deletion. The combination of them facilitates not only generation but also sequence refinement allowing dynamic length changes. We also propose a set of new training techniques dedicated at them, effectively exploiting one as the other's learning signal thanks to their complementary nature. Experiments applying the proposed model achieve comparable performance but much-improved efficiency on both generation (e.g. machine translation, text summarization) and refinement tasks (e.g. automatic post-editing). We further confirm the flexibility of our model by showing a Levenshtein Transformer trained by machine translation can straightforwardly be used for automatic post-editing.

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

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.”
WaveGrad: Estimating Gradients for Waveform Generation (2020, background): “…2019; Chan et al., 2020; Saharia et al., 2020), insertion-based generative models (Stern et al., 2019; Chan et al., 2019b;a;c; Li & Chan, 2019) and edit-based generative models (Sabour et al., 2019; Gu et al., 2019; Ruis et al., 2019) found in the semi-autoregressive sequence generation literature.”
Instantaneous Grammatical Error Correction with Shallow Aggressive Decoding (2021, neutral): “0× Levenshtein Transformer (Gu et al., 2019) No No 53.”
CommonGen: A Constrained Text Generation Challenge for Generative Commonsense Reasoning (2020, methodology): “We assume that these models potentially would have better performance because of their explicit modeling on iterative reﬁnements, and thus study the most recent such model Lev-enshtein Transformer ( LevenTrans ) by Gu et al. (2019).”
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].”
HAT: Hardware-Aware Transformers for Efficient Natural Language Processing (2020, methodology): “We adopt the average iteration time of 2.88 for decoding (Gu et al., 2019 Latency BLEU Transformer (Vaswani et al., 2017) 4.3s 25.85 Levenshtein (Gu et al., 2019) 6.5s 25.20 Evolved Transformer (So et al., 2019) 3.7s 25.40 Lite Transformer (Wu et al., 2020) 3.4s 25.79 HAT (Ours) 3.4s 25.92…”
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).”
Understanding Knowledge Distillation in Non-autoregressive Machine Translation (2019, methodology): “…Shu et al., 2019) or structured information such as syntax trees (Akoury et al., 2019) to capture translation variation; (3) training NAT models with objectives other than maximum likelihood (Wang et al., 2019; Wei et al., 2019; Shao et al., 2019) which ameliorates the effects of multi-modality.”
TranSpeech: Speech-to-Speech Translation With Bilateral Perturbation (2022, background): “Unlike the relatively well-studied non-autoregressive (NAR) MT (Gu et al., 2017; Wang et al., 2019; Gu et al., 2019; Ghazvininejad et al., 2019; Yin et al., 2023), building NAR S2UT models that generate units in parallel could be much more challenging due to the joint linguistic and acoustic…”
Lexically Constrained Neural Machine Translation with Levenshtein Transformer (2020, methodology): “We refer the readers to (Gu et al., 2019) for a detailed description of the LevT model and training routine.”
EDITOR: An Edit-Based Transformer with Repositioning for Neural Machine Translation with Soft Lexical Constraints (2020, methodology): “Figure 4 shows an example for creating the roll-in sequences: we first create the initial sequence y0 by applying random word dropping (Gu et al., 2019) and random word shuffle (Lample et al.”
Learning to Model Editing Processes (2022, background): “Many previous works on editing have focused on conditional language modeling tasks such as machine translation or editing source code based on commit messages (Malmi et al., 2019; Gu et al., 2019; Reid and Zhong, 2021), and thus have used non-likelihood based metrics such as BLEU or F1 score.”
FELIX: Flexible Text Editing Through Tagging and Insertion (2020, methodology): “…T AGGER (Malmi et al., 2019), L EVEN - SHTEIN T RANSFORMER (L EV T) (Gu et al., 2019), which is a partially autoregressive model that also employs a deletion and an insertion mechanisms, a standard T RANSFORMER evaluated by (Gu et al., 2019), and a state-of-the-art method by (Lee et al., 2019).”
Big Little Transformer Decoder (2023, methodology): “Such a multi-iteration decoding scheme has also been proposed in [16, 55, 68], which generates texts with fewer steps than the autoregressive scheme by inserting or deleting multiple tokens per iteration.”
Insertion-Deletion Transformer (2020, methodology): “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).”
Step-unrolled Denoising Autoencoders for Text Generation (2021, background): “Insertion (Stern et al., 2019) and Levenshtein (Gu et al., 2019) Transformers are deviations from the standard paradigm of training and could potentially overcome some of AR problems.”
Fully Non-autoregressive Neural Machine Translation: Tricks of the Trade (2020, methodology): “To ease the modeling difﬁculty, recent state-of-the-art NAT systems (Lee et al., 2018; Stern et al., 2019; Ghazvininejad et al., 2019; Gu et al., 2019; Kasai et al., 2020a; Shu et al., 2020; Sa-haria et al., 2020) trade accuracy with latency by incorporating an iterative reﬁnement process in…”