Source-linked AI summary
Levenshtein Transformer
Jiatao Gu, Changhan Wang, Jake Zhao
TL;DR
Existing sequence decoders lack flexibility because they generate step-by-step or constrain sequence length during iterative modification. LevT uses alternating insertion and deletion policies trained with imitation and dual-policy learning, achieving comparable or better generation performance with improved efficiency while also supporting refinement and post-editing.
Problem
Current decoding models use fixed or monotonically increasing sequence lengths, limiting flexible revision of generated text.
Method
LevT models generation and refinement as iterative insertion and deletion actions, trained with imitation learning and complementary dual-policy roll-ins.
Results
LevT achieves comparable or better results than a strong Transformer baseline on machine translation and summarization, with up to ×5 faster actual execution time and direct post-editing applicability.
Takeaways & Limitations
A machine-translation-trained LevT can directly perform translation post-editing without changes, unifying generation and refinement.
Abstract
from arXiv · showhide
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.
1 Introduction
Levenshtein Transformer addresses inflexible decoding by replacing fixed or monotonically growing sequence generation with insertion and deletion operations. It combines dual-policy learning with parallel decoding to support efficient generation and refinement.
- 1 Introduction: The work targets neural sequence generation settings where autoregressive models decode step-by-step and nonautoregressive models reduce decoding iterations.Machine translation is given as a representative deployment task.
- 1 Introduction: LevT replaces standardized decoding with insertion and deletion, enabling generated sequences to be revised, replaced, revoked, or deleted.Existing frameworks use fixed or monotonically increasing sequence lengths during decoding.
- 1 Introduction: The same model supports generation from an empty sequence and refinement from a low-quality sequence, unlike frameworks that treat these as separate tasks.A machine-translation-trained LevT is directly applicable to translation post-editing without changes.
- 1 Introduction: The model alternates two policies trained through dual policy learning, using one policy’s previous output as input while an expert policy supplies correction signals.Insertion and deletion are treated as complementary but adversarial policies.
- 1 Introduction: LevT achieves comparable or better results than a strong Transformer baseline on machine translation and summarization with up to ×5 faster actual machine execution time.Its efficiency benefits from parallel decoding.
2 Problem Formulation
LevT formulates generation and refinement as iterative sequence editing with deletion and insertion actions. These actions alternate in parallelizable stages, allowing dynamic sequence modification from either an empty or existing sequence.
- 2.1 Sequence Generation and Refinement: LevT casts sequence generation and refinement as a Markov Decision Process over sequences, actions, environments, rewards, and an initial sequence.The initial sequence determines whether the agent performs generation or refinement.
- 2.1 Sequence Generation and Refinement: An empty initial sequence triggers generation, whereas an already generated initial sequence supports refinement.The policy receives the current sequence and acts within the editing environment.
- 2.2 Actions: Deletion & Insertion: Deletion makes a binary keep-or-delete decision for every token while preserving the sequence boundary symbols.The deletion classifier predicts token-level “fake” or “real” labels.
- 2.2 Actions: Deletion & Insertion: Insertion first predicts placeholders in token slots and then replaces each placeholder with vocabulary tokens, allowing multiple tokens at one slot.This two-stage process combines ideas from insertion models and masked language models.
- 2.2 Actions: Deletion & Insertion: Figure 1 depicts one refinement iteration and indicates that the architecture serves three tasks through task-specific classifiers.Encoder-decoder attention is omitted from the illustration for simplicity.
- 2.2 Actions: Deletion & Insertion: The decoder alternates deletion and insertion because the two operations are complementary.During generation from empty input, insertion is called first, followed by deletion, repeatedly.
- 2.2 Actions: Deletion & Insertion: One iteration decomposes into delete tokens, insert placeholders, and replace placeholders with new tokens.The policy predicts deletion, placeholder, and token actions for the current sequence.
- 2.2 Actions: Deletion & Insertion: The updated sequences are formed by applying deletion and placeholder insertion before token replacement, with computation parallelized within each subtask.The intermediate sequences are y′ = E(y, d) and y′′ = E(y′, p).
3 Levenshtein Transformer
Levenshtein Transformer iteratively refines sequences by alternating deletion and insertion, using shared Transformer components and imitation-learning policies. Its design supports parallel decoding, dynamic sequence lengths, and training through complementary roll-in strategies.
- Model and inference: LevT takes a sequence, or no sequence, and repeatedly modifies it by alternating insertion and deletion until the policies converge.The model's inference procedure combines the operations into iterative refinement.
- Model and inference: Three policy classifiers delete tokens, predict placeholder counts between tokens, and fill placeholders with predicted tokens.Placeholder prediction enables multiple tokens to be inserted at one slot before token prediction fills them.
- Model and inference: Each decoding iteration parallelizes deletion, placeholder insertion, and placeholder replacement, while the shared Transformer backbone can optionally be disabled without changing inference time.Early exit further reduces computation for deletion and placeholder policies while retaining the final block for token prediction.
- Dual-policy learning: LevT is trained with imitation learning using expert actions derived from ground truth or sequence-distilled autoregressive outputs.Oracle actions minimize Levenshtein distance through dynamic programming, while distillation uses an autoregressive teacher's beam-search output.
- Dual-policy learning: Dual-policy learning trains each insertion or deletion policy on adversarial-policy outputs from the previous iteration, with expert actions supplying correction signals.Roll-in policies can also mix initial or deletion outputs with random noise to encourage exploration.
- Evaluation and inference: Table 1 evaluates LevT and autoregressive baselines using generation quality, latency, and average decoder iterations on standard test sets.The table includes LevT models trained from oracle and autoregressive-teacher targets.
4 Experiments
Experiments evaluate LevT across generation and refinement tasks, finding comparable or better quality than autoregressive baselines alongside substantially improved decoding efficiency. Ablations and post-editing results further examine its learning design, flexibility, and transfer from machine translation.
- Generation results: LevT achieves comparable or sometimes better generation quality than a strong autoregressive baseline on machine translation and summarization, while decoding more efficiently.Speed is assessed using single-sequence latency and decoder iterations.
- Generation results: Up to ×5 execution-time speed-up is achieved with early exit compared with a strong autoregressive Transformer using beam-search, at some cost to quality.LevT also adjusts decoding time according to input length.
- Ablations: Weight sharing between insertion components is beneficial, while separating deletion from insertion provides another +0.5 BLEU improvement over the default setting.The result suggests insertion and deletion may capture complementary information requiring separate capacity.
- Sequence refinement: On automatic post-editing, LevT consistently improves either PBMT or NMT inputs when trained from scratch and outperforms an autoregressive Transformer in most cases.Evaluation uses BLEU and case-sensitive TER on synthetic and real post-editing settings.
- Sequence refinement: MT-pretrained LevT can be applied directly to refinement, improving initial MT outputs in synthetic post-editing and achieving the best real-task results after fine-tuning.Real post-editing differs from synthetic data because human translators usually fix only a few errors.
- Controllability: Oracle deletion instructions substantially improve MT and PE performance, with further gains when oracle insertion counts are also supplied.These experiments illustrate the controllability enabled by separating insertion and deletion operations.
5 Related Work
Prior work relaxes autoregressive or monotonic decoding through parallel generation, iterative refinement, and editing-based architectures, but these approaches remain specialized.
- Partially parallel decoders output multiple tokens per step, reducing dependence on strictly left-to-right generation.
- Nonautoregressive models use discrete latent variables or iterative refinement to generate sequences with fewer autoregressive decoding constraints.
- Editing-based systems iteratively substitute or refine tokens, often using convolutional or autoregressive decoder architectures.
6 Conclusion
The paper presents Levenshtein Transformer as an insertion-and-deletion model that supports both sequence generation and refinement, with algorithms for learning and decoding.
- Levenshtein Transformer uses insertion and deletion operations to support sequence generation and refinement in one model.
- Its learning and inference procedures are described through dedicated algorithms, with source information handled by encoder cross-attention in conditional tasks.
- Inference skips the initial deletion when the starting sequence is empty and otherwise begins by deleting tokens to refine the input.
- The learning algorithm initializes training data, expert and model policies, and randomized deletion, then iterates until the maximum training steps are reached.
B Dataset and Preprocessing Details
The paper reports dataset statistics and preprocessing choices for generation and refinement tasks, alongside the decoding algorithm’s iterative control flow.
- Dataset and Preprocessing Details: WMT En-De and Gigaword use 32,000 joint BPE operations, WMT Ro-En uses 40,000, and WAT En-Ja uses separate 16,384 BPE vocabularies.
- Dataset and Preprocessing Details: The work provides separate dataset-statistics tables for sequence generation tasks and sequence refinement tasks.
- Dataset and Preprocessing Details: Decoding initializes an input sequence, step counter, maximum step limit, and model policy before iteratively applying operations.
- Dataset and Preprocessing Details: Decoding terminates when no deletion or insertion remains, the output stabilizes, or the maximum number of steps is reached.
C.1 Sequence Generation Tasks
The experiments use Transformer-based baselines and select checkpoints by validation scores because the LevT training objectives include randomness terms.
- Transformer models serve as autoregressive baselines and teacher models, using shared embeddings except for WAT En-Ja.
- BLEU for machine translation or ROUGE-2 for text summarization selects the best checkpoint because the training objectives contain randomness terms.
C.2 Sequence Refinement Tasks
The refinement experiments evaluate LevT against Transformer baselines using imperfect MT outputs from PBMT and an LSTM-based NMT system, with synthetic and real APE data under specified training conditions.
- Baseline setup: The baseline Transformer concatenates the source and MT output for encoder input, while restarting MT-output positional embeddings and adding language embeddings.These modifications identify each input token’s language type; other hyperparameters match the standard Transformer.
- Training setup: LevT uses the same training conditions as the MT tasks for synthetic APE experiments.This keeps the refinement model’s training setup aligned with the machine-translation experiments.
- Refinement inputs: PBMT and single-layer attention-based LSTM systems provide the imperfect MT outputs used as refinement inputs.The PBMT baseline is built with Moses, while the LSTM-based NMT model uses fairseq-py defaults.
- Training data: Synthetic APE data comprise 500K and 4M subsets, with real data oversampled tenfold and merged with the 500K subset for APE training.A LevT MT model is also trained on the 4M synthetic corpus using only source-target pairs.
C.3 Implementation
The implementation uses PyTorch with code released in Fairseq-py, and the reported examples cover translation, summarization, post-editing, and zero-shot refinement.
- Implementation: Both LevT and the baseline Transformer are implemented in PyTorch, with code released as part of Fairseq-py.The implementation information identifies the framework and the public code distribution.
- Decoding efficiency: Most LevT predictions terminate within 1–4 iterations, with an average of 2.43 iterations and only approximately 0.1% reaching the maximum.The maximum-iteration setting illustrated is 10, and the reported distribution is presented as evidence of efficiency.
- Examples: The paper presents further examples from the proposed Levenshtein Transformer.This passage introduces the example material without specifying an additional task or result.
- Examples: The paper provides translation examples for WAT’17 Small-NMT En-Ja, WMT’16 Ro-En, WMT’14 En-De, and English Gigaword.These examples span machine translation and English Gigaword generation tasks.
- Post-editing examples: Additional examples cover WMT’17 APE En-De and zero-shot post-editing over PBMT output with a LevT trained for machine translation.The zero-shot example contrasts refinement of PBMT output with translation from scratch.