Source-linked AI summary
Insertion Transformer: Flexible Sequence Generation via Insertion Operations
Mitchell Stern, William Chan, Jamie Kiros, Jakob Uszkoreit
TL;DR
Fixed-order sequence models make parallel or dynamically sized generation difficult, while non-autoregressive models introduce length, independence, or architectural constraints. The Insertion Transformer instead inserts tokens anywhere, supports serial and parallel decoding, and matches the standard Transformer with logarithmically many iterations.
Problem
Existing autoregressive models do not easily support parallel or non-left-to-right generation, while non-autoregressive approaches require a preset length or make restrictive modeling assumptions.
Method
The Insertion Transformer iteratively inserts tokens at arbitrary locations, allowing training for specific or entropy-maximizing orderings and serial or simultaneous decoding.
Results
The model matches the standard Transformer while requiring substantially fewer generation iterations, using close to ⌊log2 n⌋+1 steps without quality degradation.
Takeaways & Limitations
Insertion-based decoding accommodates dynamically growing outputs and parallel generation while preserving the quality of standard Transformer translation.
Takeaways & Limitations
Allowing insertions anywhere requires recomputing decoder hidden states after every insertion and can reduce effective batch size while increasing gradient variance.
Abstract
from arXiv · showhide
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.
1. Introduction
The Insertion Transformer addresses limitations of fixed left-to-right and length-precommitted generation by inserting tokens flexibly during iterative decoding. It supports serial or parallel generation and can follow specific orderings, including balanced binary trees.
- Autoregressive models support tractable likelihoods and beam search but do not easily accommodate parallel token generation or tree-structured orderings.
- Non-autoregressive approaches enable parallel generation but require target length in advance, may impose conditional independence, or need separate decoders.
- The Insertion Transformer repeatedly inserts tokens into an initially empty sequence, allowing the output length to grow dynamically and supporting non-left-to-right orderings.
- Balanced binary-tree decoding can generate a length-n sequence in as few as ⌊log2 n⌋+ 1 operations while permitting simultaneous insertions.
2. Sequence Generation via Insertion Operations
The framework represents generation as iterative insertion into a canvas that remains a subsequence of the final output. At each step, it selects both content and an available insertion location until emitting a termination marker.
- A hypothesis canvas must remain a subsequence of the final output because the framework supports insertion but not reordering.
- The model produces a joint distribution over the content token and every available insertion location in the current canvas.
- Selecting a token and location inserts that token into the canvas at the specified position, producing the next hypothesis.
- Generation starts from an empty canvas with one insertion slot and ends when a special marker token is emitted.
3. Insertion Transformer Model
The Insertion Transformer modifies the Transformer decoder to predict insertions throughout the current output, using slot representations and alternative content-location distributions. These changes support flexible insertion decisions across the canvas.
- The decoder is modified to induce a distribution over insertions anywhere in the current output rather than only at its end.
- Removing causal self-attention lets each insertion decision condition on the full canvas context at the current iteration.
- The model creates n + 1 slot representations by concatenating adjacent decoder outputs, including the beginning and end slots.Each slot is summarized by representations immediately to its left and right.
- Content-location prediction can directly model the joint distribution or factor it as p(c | l)p(l).
- The factorized approach separately models content per slot and location using row-wise vocabulary softmaxes and a learned query vector.
- The factorized content-location model requires only a small number of additional parameters h compared with direct joint modeling.
4. Training and Loss Functions
The Insertion Transformer supports prescribed generation orders, including left-to-right and balanced binary tree orderings, as well as order-agnostic training. Its losses prioritize different insertion behaviors, while training incurs recomputation and sampling costs.
- The framework accommodates arbitrary, input- and context-dependent generation orders, including left-to-right and balanced binary tree orderings.
- Left-to-right order: Left-to-right training samples a target prefix and maximizes the probability of inserting the next token in the rightmost slot.
- Balanced binary tree: Balanced binary tree training generates centermost tokens first, then recursively generates centers of the remaining spans for greater parallelism.The soft binary tree loss assigns higher probability weight to tokens near each span’s center.
- Balanced binary tree: The temperature τ controls weighting sharpness, from centermost-token emphasis as τ →0 to uniform weighting as τ →∞.
- Uniform loss: The uniform loss assigns equal probability mass to each correct action, encouraging awareness of all valid insertions and maximizing robustness.It is implemented as the τ →∞ limit of the binary tree loss.
- Training differences: Insertion anywhere removes state propagation, reduces the effective batch size by the average sequence length, and adds gradient variance from generation-step subsampling.The authors report that these costs are not major hindrances under suitable training conditions.
5. Inference
Inference selects insertion actions either serially or across multiple slots in parallel, with termination determined by sequence- or slot-finalization rules. Parallel decoding can achieve logarithmic iteration complexity in theory and practice.
- Greedy serial decoding selects the highest-probability content-location action, inserts its token, and repeats until the chosen termination condition is met.Sequence finalization stops at an end-of-sequence token, whereas slot finalization waits for end-of-slot predictions at every location.
- Parallel decoding: Slot-finalization models support parallel decoding by computing maximum-probability content actions independently for all active locations.The required conditional distributions can be computed in parallel for both factored and jointly normalized models.
- Parallel decoding: Parallel decoding filters completed locations and simultaneously inserts selected tokens into every remaining slot, repeating until all slots predict end-of-slot.
- Evaluation: Table 1 reports development BLEU for greedy decoding across loss functions and termination strategies, with separate EOS, distillation, and parallel-decoding variants.Parallel results apply to models trained with slot finalization.
- Parallel decoding: ⌊log2 n⌋+ 1 steps is the theoretical minimum for generating a sequence of length n when every slot receives an insertion at each step.The paper reports that this logarithmic complexity is attainable in practice.
6. Experiments
Experiments on WMT 2014 English-German translation examine training objectives, decoding strategies, distillation, architecture, and parallelism. Properly tuned insertion models achieve strong BLEU while supporting parallel decoding with logarithmic iteration complexity.
- Baseline results: 21.02 development BLEU is achieved by the binary tree loss under standard greedy decoding, outperforming the tested left-to-right ordering.The authors attribute this partly to gradients covering all missing tokens rather than only the next one.
- Baseline results: 22.64 development BLEU is reached by uniform loss with sequence-level finalization after applying a tuned EOS penalty.The penalty can increase BLEU by nearly 4 points in some settings by discouraging premature termination.
- Knowledge distillation: 3 to 4 BLEU points are gained across the distilled experiments, with binary tree loss at temperature τ = 2.0 achieving 25.80 development BLEU.The loss difference is about 2 BLEU points under standard decoding but largely disappears after EOS-penalty tuning.
- Architectural variants: 0.5-0.8 BLEU improvements from several architectural variants largely disappear after EOS-penalty tuning, leaving the best configurations within 0.1 BLEU of baseline.This suggests the core architecture is already sufficiently powerful when decoding is well-tuned.
- Parallel decoding: Parallel decoding produces scores comparable to or better than greedy decoding, while typically approaching the lower bound of ⌊log2 n⌋+ 1 iterations.The framework can produce high-quality output with a sub-linear number of generation steps, and fewer iterations may reduce premature EOS errors.
- Test results: The test-set comparison matches the quality of models requiring linear iterations while using a logarithmic number of generation steps, usually no more than 10 in practice.The binary tree loss is associated with substantially fewer generation iterations.
7. Related Work
Related work spans non-left-to-right, dynamic-canvas, and non-autoregressive generation approaches, while positioning the Insertion Transformer around discrete dynamic canvases and parallel decoding.
- Non-left-to-right generation: Prior work explores generation orders that differ from left-to-right, including set modeling, functional-word-first generation, and hierarchical autoregressive image generation.Hierarchical autoregressive image generation requires log n steps for n tokens.
- Dynamic canvases: Dynamic-canvas language generation is described as a continuous relaxation of the Insertion Transformer, using an embedding-space canvas rather than discrete tokens.The prior approach targets language modeling, whereas this work applies insertion-based generation to conditional machine translation.
- Machine translation: On WMT 2014 English-German translation, the parallel strategy reaches the accuracy of linear-complexity models with logarithmic decoding iterations.The result is reported as BLEU on the newstest2014 test set.
- Machine translation: Compared with non- and semi-autoregressive translation models, the Insertion Transformer supports a dynamically growing canvas while retaining sub-linear generation complexity.The passage also contrasts its parallelism behavior with degradation reported for other models.
- Concurrent work: Concurrent insertion-based work differs in whether successive canvases are modeled explicitly or implicitly, yielding different tradeoffs in autoregression, caching, and parallelism.The supplied passage is truncated after describing these tradeoffs.
- Concurrent work: Concurrent tree-based work did not examine the balanced binary tree policy or parallel generation, instead using serialized in-order traversal.On machine translation, that work reported left-to-right generation superior to its learned orderings.
8. Conclusion
The Insertion Transformer supports arbitrary generation orderings and both serial and parallel insertion decoding. With binary-tree training, it matches the standard Transformer on WMT 2014 English-German translation using substantially fewer decoding iterations.
- Conclusion: The model supports fixed orderings such as left-to-right or balanced binary trees, and can optimize over all valid orderings for completion or infilling.These capabilities arise from its insertion-based sequence-generation framework.
- Conclusion: Decoding can be serial, with one token produced at a time, or parallel, with simultaneous insertions at multiple locations.This gives the model both fully and partially autoregressive decoding modes.
- Conclusion: With binary-tree loss, sequences of length n are generated in close to ⌊log2 n⌋+1 steps without quality degradation.The reported step count approaches the asymptotic limit for insertion-based generation.
- Conclusion: On WMT 2014 English-German translation, the model matches the standard Transformer while using substantially fewer decoding iterations.This conclusion follows from the binary-tree decoding result.