PaperlayerView exact revision on arXiv

Source-linked AI summary

Insertion-based Decoding with automatically Inferred Generation Order

Jiatao Gu, Qi Liu, Kyunghyun Cho

arXiv:1902.01370v3cs.CLcs.LG

TL;DR

Conventional autoregressive decoding typically uses a fixed left-to-right order, while prior approaches to alternative orders used fixed choices or restricted the problem to n-gram segments. InDIGO infers order through insertion-based decoding and achieves competitive or better performance than left-to-right decoding across four tasks.

  • Problem

    Neural autoregressive decoding commonly uses a fixed left-to-right order, while prior generation-order studies used fixed choices or restricted the task to n-gram segments.

    Source: §1 · p. 1

  • Method

    InDIGO models generation order as latent and predicts each word with its insertion position, using a Transformer trained with predefined or beam-search-derived adaptive orders.

    Source: §1 · p. 1

  • Results

    Across word order recovery, machine translation, code generation, and image captioning, InDIGO generates arbitrary-order sequences with performance competitive with or better than left-to-right generation.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    Case studies show that InDIGO adopts adaptive generation orders based on input information.

    Source: §1 · p. 2

    Training with searched adaptive orders is slower than left-to-right training and difficult to parallelize; beam sizes 1 and 8 are 3.8 and 7.2 times slower, respectively.

    Source: §5.3 · p. 9

Abstract

from arXiv · show

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 to the conventional left-to-right generation. The generated sequences show that InDIGO adopts adaptive generation orders based on input information.

1 Introduction

InDIGO replaces the usual fixed left-to-right order with insertion-based decoding that infers generation order. It extends Transformer for predefined or beam-search-derived orders and performs competitively or better than left-to-right decoding across four tasks.

1 Introduction

  • Earlier work used fixed generation orders or restricted the problem to n-gram segment generation, leaving adaptive-order inference unaddressed.Autoregressive models commonly assume left-to-right generation.Source: §1 · p. 1
  • InDIGO models generation orders as latent variables by predicting each word and its insertion position, represented relative to the sequence.Decoding proceeds through insertion operations.Source: §1 · p. 1
  • The method extends Transformer and trains with either a predefined order or adaptive orders obtained from beam search.Learning maximizes an evidence lower bound of the maximum-likelihood objective.Source: §1 · pp. 1–2
  • Across four tasks, InDIGO generates sequences in arbitrary orders with performance competitive with or better than conventional left-to-right generation.The tasks are word order recovery, machine translation, code generation, and image captioning.Source: §1 · p. 2

2 Neural Autoregressive Decoding

Neural autoregressive decoding models a target sequence conditioned on an input as a sequence of next-token predictions. Training maximizes conditional likelihood, and decoding commonly follows the factorization order.

2 Neural Autoregressive Decoding

  • A conditional sequence model represents the probability of target sequence y given input x.The input may itself be a source sequence.Source: §2 · p. 2
  • The autoregressive factorization predicts each next token conditioned on the preceding target tokens and the input.The sequence begins and ends with special boundary tokens.Source: §2 · p. 2
  • Training commonly maximizes conditional log likelihood over parallel examples.Source: §2 · p. 2
  • Greedy decoding and beam search generate tokens sequentially by following the model's factorization order.Source: §2 · p. 2

3 Insertion-based Decoding with Inferred Generation Order (InDIGO)

InDIGO addresses whether generation should follow the conventional left-to-right order by treating order as latent and decoding through insertions. It uses relative positions to represent and update order, then predicts each new token's insertion location.

3 Insertion-based Decoding with Inferred Generation Order (InDIGO)

  • Left-to-right order is not necessarily optimal, motivating the question of how to decode a sequence in its best order.Prior work has shown that generation order can matter in real-world tasks such as language modeling.Source: §3 · p. 2

3.1 Orders as Latent Variables

  • InDIGO treats generation order as latent, representing a sequence as word-position pairs and modeling their joint distribution across orders.At decoding time, it predicts a word and its position step by step, thereby inferring the order.Source: §3.1 · p. 2

3.2 Relative Representation of Positions

  • Relative-position vectors encode each token's position with respect to other words in the partial sequence and can be mapped back to absolute positions.Using relative rather than absolute positions avoids the need to know the final sequence length in advance.Source: §3.2 · pp. 2–3

3.3 Insertion-based Decoding

  • The relative-position matrix is updated by appending each new position, allowing previous hidden states to be reused without recomputation.Each new token is inserted to the left or right of an existing word, which determines its next relative position.Source: §3.2 · p. 3, §3.3 · p. 3

4 Model

Transformer-InDIGO extends Transformer for insertion-based decoding, using relative positions to support arbitrary generation orders. Its learning procedure considers both predefined and beam-searched adaptive orders.

4 Model

  • Transformer-InDIGO extends Transformer to support insertion-based decoding.Its framework includes word-and-position prediction, position updating, and final output reordering.Source: §4 · p. 3, §4.1 · p. 3, Figure 2 · p. 4

4.1 Network Design

  • Relative-position self-attention addresses changing absolute positions, and updated representations let the decoder reuse previous hidden states.The method preserves only left, middle, and right relations; updating the relative-position matrix is append-only.Source: §4.1 · pp. 3–5
  • The decoder predicts the next word and then its insertion position, with preliminary experiments favoring word-first factorization.The position prediction uses a pointer over insertion choices for existing words.Source: §4.1 · p. 4

4.2 Learning

  • Training maximizes an evidence lower bound using an approximate posterior over latent generation orders.For a sampled order, the objective separates word and position prediction losses.Source: §4.2 · p. 5
  • With predefined-order training, the approximate posterior assigns all its probability to a selected order, including left-to-right.The paper studies several predefined orders to evaluate their effects on generation.Source: §4.2 · p. 5
  • Searched Adaptive Order estimates the most likely latent order with beam search over target-token permutations.It maintains B high-probability subsequences, evaluates possible next words and positions, and averages the objective over the resulting B orders.Source: §4.2 · pp. 5–6
  • Keeping dropout active during beam search encourages exploration, while predefined-order pretraining helps address degenerate early predictions.The authors report that beam-searched sequences often began with common or functional words and conjecture that position learning outpaced word learning.Source: §4.2 · p. 6

4.3 Decoding

  • At inference, beam search first searches words, then tests positions for those words and selects the top-B subsequences.Joint beam search over words and positions did not seem helpful in preliminary experiments.Source: §4.3 · p. 6

5 Experiments

Across four tasks, the experiments compare InDIGO using predefined and searched adaptive orders with conventional left-to-right decoding. Searched adaptive orders improve word-order recovery and are competitive or better on translation, code generation, and image captioning; the section also examines training cost and learned generation patterns.

5.1 Experimental Settings

  • Experiments use word-order recovery, three translation pairs, NL2Code, and image captioning, and select each model’s beam size using validation BLEU.The study compares predefined and beam-searched adaptive orders using the same architecture, including the standard L2R order.Source: §5.1 · pp. 6–7, §5 · p. 6

5.2 Results and Analysis

  • SAO gains up to 3 BLEU over L2R in word-order recovery, with larger improvements as decoding beam size increases.The authors suggest that more diversified predictions give SAO a higher chance of recovering the original order.Source: Figure 3 · p. 7, §5.2 · p. 8
  • On three translation pairs, SAO is competitive with and sometimes significantly improves on L2R, with larger improvements for Turkish and Japanese.Most predefined orders perform reasonably well, while tree-based orders do not; the reported translation metrics are BLEU, Meteor, TER, and Ribes.Source: Table 3 · p. 7, §5.2 · p. 8
  • For code generation, SAO significantly outperforms L2R on both BLEU and accuracy.The results are reported on the official test sets.Source: §5.2 · p. 8, Table 4 · p. 8
  • For image captioning, SAO yields higher BLEU and CIDEr-D than L2R.Testing compares one generated caption per image against five human-created captions.Source: §5.2 · p. 8, Table 4 · p. 8

5.3 Ablation Study

  • On WMT16 Ro-En, SAO without both bootstrapping and beam search degenerates by approximately 1 BLEU point; R2L and SYN bootstrapping yield slightly worse yet comparable results to L2R, which performs best.In a reimplemented fair comparison that removed knowledge distillation and used binary-tree/uniform slot-losses plus slot-termination, SAO outperformed Stern et al. (2019) on WMT16 Ro-En.Source: §5.3 · pp. 8–9, Table 5 · p. 8
  • Greedy decoding is as efficient as standard L2R decoding, but SAO training is slower because order search adds work and is difficult to parallelize.SAO with beam sizes 1 and 8 is 3.8 and 7.2 times slower than L2R during training, respectively; increasing training beam size does not affect decoding time.Source: Table 6 · p. 8, §5.3 · p. 9

5.4 Visualization

  • In the examples, learned orders vary by task: translation can use shuffled left-to-right chunks, while captioning and code mostly proceed left-to-right before later insertions.With the predefined SYN order, translation tokens approximately follow a dependency parse; with RF, verbs and nouns are generated before remaining functional words.Source: Figure 5 · p. 10, §5.4 · p. 11

6 Related Work

Prior approaches span parallel, semi-autoregressive, and non-left-to-right generation, but InDIGO supports flexible generation orders while remaining autoregressive. The section contrasts it with concurrent tree-based and insertion-based methods.

Decoding for Neural Models

  • Non-autoregressive models generate discrete tokens in parallel, while semi-autoregressive models mix approaches but largely retain left-to-right generation.InDIGO differs by supporting flexible generation orders while decoding autoregressively.Source: §6 · p. 11

Non-L2R Orders

  • Earlier non-L2R approaches use fixed orders, including R2L, two-pass templates, middle-out decoding, bidirectional decoding, or syntax structures; InDIGO supports fully flexible orders.Wu et al. (2018) report R2L gains over L2R in a few tasks; Ford et al. (2018) and Zhu et al. (2019) use templates, while Mehri and Sigal (2018) use middle-out decoding.Source: §6 · p. 11
  • Welleck et al. (2019)’s tree-like generation covers only a subset of possible generation orders; on machine-translation tasks, they found L2R superior to learned orders, while Transformer-InDIGO with searched adaptive orders performed better.Source: §6 · p. 11
  • Stern et al. (2019) use absolute positions and re-encode partial sequences at each step, whereas InDIGO uses relative positions without re-encoding the entire sentence.Stern et al. require knowledge distillation for good performance; InDIGO matches L2R without bootstrapping.Source: §6 · p. 11

7 Conclusion

InDIGO supports arbitrary generation orders and achieves competitive or better performance than left-to-right generation across four tasks. The conclusion identifies trainable permutation inference and post-editing operations as future directions.

7 Conclusion

  • Across machine translation, word order recovery, code generation, and image captioning, InDIGO achieves competitive or better performance than conventional left-to-right generation.The model can be trained with predefined or searched adaptive orders.Source: §7 · p. 12
  • InDIGO allows sequences to be generated in arbitrary orders, unlike conventional neural autoregressive models that often generate left to right.The paper proposes exploring deletion and substitution operations to extend the approach to post-editing.Source: §7 · p. 12
  • Future work could replace beam search with a trainable inference model that predicts permutations directly.The proposed extension would add deletion and substitution operations for post-editing tasks such as machine-translation post-editing and grammatical-error correction.Source: §7 · p. 12
Loading 1902.01370v3…