PaperlayerView exact revision on arXiv

Source-linked AI summary

Lossless Acceleration for Seq2seq Generation with Aggressive Decoding

Tao Ge, Heming Xia, Xin Sun, Si-Qing Chen, Furu Wei

arXiv:2205.10350v1cs.CLcs.LG

TL;DR

Seq2seq autoregressive inference is inefficient because it decodes sequentially, while prior acceleration methods may sacrifice quality. Aggressive Decoding combines parallel drafting with verification, using IAD for similar input-output tasks and GAD for general tasks, achieving substantial speedups with identical or better quality. The approach remains limited by GAD’s dependence on drafter and verifier quality and by sequential encoding overhead in its implementation.

  • Problem

    Autoregressive seq2seq inference is inefficient because it sequentially decodes tokens, while prior acceleration efforts can sacrifice generation quality.

  • Method

    Aggressive Decoding drafts multiple tokens in parallel and verifies them autoregressively, using input-guided drafting for similar tasks and a non-autoregressive drafter for general tasks.

  • Results

    Aggressive Decoding achieves lossless acceleration across tasks: IAD provides 7×∼9× speedup, while GAD/GAD++ provides 3×∼5× speedup with identical or better quality.

  • Takeaways & Limitations

    Aggressive Decoding provides significant lossless speedups for both rewriting and general seq2seq generation and may benefit further from more parallel computing hardware.

  • Takeaways & Limitations

    GAD’s translation quality depends mainly on the autoregressive verifier, its efficiency depends on the non-autoregressive drafter, and the implementation spends approximately 16% of total time on sequential input encoding.

Abstract

from arXiv · show

We study lossless acceleration for seq2seq generation with a novel decoding algorithm -- Aggressive Decoding. Unlike the previous efforts (e.g., non-autoregressive decoding) speeding up seq2seq generation at the cost of quality loss, our approach aims to yield the identical (or better) generation compared with autoregressive decoding but in a significant speedup, achieved by innovative cooperation of aggressive decoding and verification that are both efficient due to parallel computing. We propose two Aggressive Decoding paradigms for 2 kinds of seq2seq tasks: 1) For the seq2seq tasks whose inputs and outputs are highly similar (e.g., Grammatical Error Correction), we propose Input-guided Aggressive Decoding (IAD) that aggressively copies from the input sentence as drafted decoded tokens to verify in parallel; 2) For other general seq2seq tasks (e.g., Machine Translation), we propose Generalized Aggressive Decoding (GAD) that first employs an additional non-autoregressive decoding model for aggressive decoding and then verifies in parallel in the autoregressive manner. We test Aggressive Decoding on the most popular 6-layer Transformer model on GPU in multiple seq2seq tasks: 1) For IAD, we show that it can introduce a 7x-9x speedup for the Transformer in Grammatical Error Correction and Text Simplification tasks with the identical results as greedy decoding; 2) For GAD, we observe a 3x-5x speedup with the identical or even better quality in two important seq2seq tasks: Machine Translation and Abstractive Summarization. Moreover, Aggressive Decoding can benefit even more from stronger computing devices that are better at parallel computing. Given the lossless quality as well as significant and promising speedup, we believe Aggressive Decoding may potentially evolve into a de facto standard for efficient and lossless seq2seq generation in the near future.

1 Introduction

Aggressive Decoding accelerates seq2seq inference by drafting tokens aggressively and verifying them in parallel, while preserving autoregressive generation quality. It uses input-guided drafting for similar input-output tasks and a non-autoregressive drafter for general tasks.

  • Aggressive Decoding targets quality-lossless acceleration rather than the quality sacrifice associated with prior non-autoregressive approaches.Its goal is identical or better generation compared with autoregressive decoding.
  • Aggressive Decoding replaces sequential autoregressive decoding with parallel aggressive drafting followed by autoregressive verification, accepting only verified tokens.This cooperation enables multiple tokens to be processed per decoding iteration while guaranteeing agreement with autoregressive decoding.
  • Input-guided Aggressive Decoding copies input tokens as drafts for tasks whose inputs and outputs are highly similar, such as Grammatical Error Correction.
  • Generalized Aggressive Decoding uses an additional non-autoregressive model to draft tokens before autoregressive verification for general tasks such as Machine Translation.
  • 7×∼9× speedup is achieved for Grammatical Error Correction and Text Simplification with identical results to greedy decoding, while GAD delivers 3×∼5× speedup with identical or better quality in Machine Translation and Abstractive Summarization.These results are reported for a 6-layer Transformer across multiple seq2seq tasks.

2 Background: Autoregressive Scoring and Decoding in Transformer

Transformer training can compute next-token probabilities in parallel because ground-truth prefixes are available, but inference lacks those prefixes and therefore decodes sequentially. This sequential dependence requires one token per iteration and limits inference parallelism.

  • The Transformer is widely used for seq2seq tasks including Machine Translation, Abstractive Summarization, and Grammatical Error Correction.
  • During training, teacher forcing allows each next-token probability P(y_i+1 | y≤i, x) to be computed in parallel because the ground-truth target sequence is available.
  • During inference, the Transformer decodes one token at each iteration conditioned on previously decoded tokens because ground truth is unavailable.
  • Sequentially iterating m steps to decode a sequence of length m becomes the main bottleneck of inference efficiency by limiting computational parallelism.

3 Aggressive Decoding

Aggressive Decoding accelerates autoregressive seq2seq generation by combining parallel drafting with verification, using input copying for similar input-output tasks and an NAR drafter for general tasks. IAD and GAD accept only verified predictions, while GAD++ relaxes verification to increase speed and potentially exceed greedy decoding.

  • Aggressive Decoding replaces sequential token generation with parallel drafting and verification, accepting only predictions that pass verification.This cooperation is designed to preserve autoregressive greedy-decoding results while improving inference efficiency.
  • 3.1 Input-guided Aggressive Decoding: Input-guided Aggressive Decoding copies likely output tokens from similar inputs, verifies them in parallel, then re-decodes after the first mismatch and resumes copying after suffix matches.The method is motivated by tasks such as grammatical error correction whose outputs closely resemble their inputs.
  • 3.2 Generalized Aggressive Decoding: Input-guided Aggressive Decoding cannot apply to tasks whose inputs and outputs are not highly similar, motivating GAD for general seq2seq tasks.GAD addresses this boundary by using an additional NAR model to generate draft tokens in parallel.
  • 3.2 Generalized Aggressive Decoding: Generalized Aggressive Decoding uses an NAR model to draft fixed-length token blocks conditioned on prior decoded tokens, then verifies those blocks with an AR model in parallel.The NAR drafter predicts blocks rather than entire sequences and proceeds left to right from the previously decoded prefix.
  • 3.2 Generalized Aggressive Decoding: GAD detects the first draft-verifier bifurcation and discards later drafted tokens, ensuring its accepted sequence matches AR greedy decoding.The iteration repeats until [EOS] or the maximum length, with both drafting and verification performed in parallel.
  • 3.2.3 GAD++: GAD++ accepts drafts among the AR verifier’s top-β candidates within tolerance τ, enabling more accepted tokens, higher speedup, and generation beyond greedy decoding.This relaxes vanilla GAD’s strict top-1 matching criterion.

4 Experiments

Across grammatical error correction, text simplification, machine translation, and abstractive summarization, Aggressive Decoding substantially accelerates inference while preserving or improving quality. IAD exploits input-output similarity, whereas GAD uses a non-autoregressive drafter with autoregressive verification, with performance shaped by edit rates, block size, model capacity, and verification strictness.

  • 4.1 Input-guided Aggressive Decoding: IAD exceeds 7× speedup over beam-5 autoregressive decoding on CoNLL-13 while producing exactly the same predictions as greedy decoding.Greedy decoding has comparable F0.5 to beam search but makes more edits, increasing recall and reducing precision.
  • 4.1 Input-guided Aggressive Decoding: IAD speedup increases as edit ratio decreases because fewer edits allow more input tokens to be decoded in parallel, whereas heavily edited sentences require frequent re-decoding.The analysis covers all 1,381 CoNLL-13 validation examples and presents additional examples with varied speedups.
  • 4.2 Generalized Aggressive Decoding: GAD matches autoregressive greedy translation quality at around 3× speedup, while GAD++ reaches 3.6× with better quality and 4.5× with only marginal quality loss.GAD++ obtains these trade-offs by loosening the strict top-1 verification criterion and accepting more drafted tokens.
  • 4.2 Analysis: GAD’s mean accepted tokens peak at block size k = 25; larger blocks reduce efficiency and quality because the drafter struggles to translate too many tokens simultaneously.Moderately increasing GAD++ tolerance and top-β increases accepted tokens and can improve BLEU, but excessive loosening lowers BLEU from 27.02 to 26.64.
  • 4.2 Analysis: Larger models support larger blocks and stronger drafters, while vanilla GAD accepts 6.13 tokens per iteration and GAD++ accepts 10.99 with comparable quality.The larger-model experiments use Transformer-big drafters and verifiers; model capacity improves parallel decoding ability.
  • 4.2 Generalized Aggressive Decoding: In abstractive summarization, vanilla GAD matches the autoregressive verifier exactly at 3× speedup, whereas GAD++ accelerates further without the translation-quality improvement observed in machine translation.The paper attributes the difference to the larger performance gap between the non-autoregressive drafter and autoregressive verifier.
  • Overall Results: 7×–9× speedup preserves greedy-decoding results for IAD in grammatical error correction and text simplification, while GAD/GAD++ delivers 3×–5× speedup with identical or better quality in translation and summarization.The overall experiments attribute the speed differences partly to GAD’s additional non-autoregressive drafter cost.

5 Related Work

Prior work accelerates seq2seq decoding through non-autoregressive, semi-autoregressive, and cascade strategies, but quality or efficiency limitations motivate Aggressive Decoding.

  • Non-autoregressive Decoding: Non-autoregressive decoding reduces inference steps but generally has less reliable quality than autoregressive decoding because of conditional independence assumptions.
  • Semi-autoregressive Decoding: Semi-autoregressive methods combine autoregressive and non-autoregressive computation, including local parallelism, error-span editing, and parallel drafting with autoregressive verification.
  • Semi-autoregressive Decoding: Blockwise Decoding is closely related to Generalized Aggressive Decoding but its limited investment in non-autoregressive modeling restricts efficiency.
  • Cascade Inference: Aggressive Decoding can be viewed as cascade inference: aggressive drafting forms one inference stage and verification controls quality in a subsequent stage.

6 Conclusion

The paper proposes Aggressive Decoding as a lossless replacement for step-by-step seq2seq decoding, with specialized variants for rewriting and general tasks. It reports significant speedups while retaining generation quality, although substantial room for improvement remains.

  • 6 Conclusion: Aggressive Decoding replaces conventional step-by-step decoding with aggressive drafting and verification.
  • 6 Conclusion: Input-guided Aggressive Decoding and Generalized Aggressive Decoding target rewriting and general seq2seq tasks, respectively, while preserving quality with significant speedups.
  • 6 Conclusion: The authors report that Aggressive Decoding still has substantial room for improvement despite its lossless speedup results.

A Details of Evaluation of Input-guided Aggressive Decoding

The IAD evaluation details include CPU threading settings and report substantial online inference acceleration for a 6-layer Transformer on CoNLL-13.

  • A Details of Evaluation of Input-guided Aggressive Decoding: Over 6× online inference speedup is achieved over the Transformer-big baseline on CPU for the 6-layer Transformer.The measurement uses batch=1 on an Intel Xeon E5-2690 v4 processor with either 8 or 2 threads.
  • A Details of Evaluation of Input-guided Aggressive Decoding: The CPU evaluation reports IAD efficiency for the 6-layer Transformer on CoNLL-13 using 8 and 2 threads.
  • A Details of Evaluation of Input-guided Aggressive Decoding: The evaluation specifies OMP_NUM_THREADS values of 8 or 2 for the CPU experiments.

B Details of Evaluation of Generalized Aggressive Decoding

The Generalized Aggressive Decoding evaluation uses specified training hyperparameters and averages parameters from the last 10 checkpoints.

  • B Details of Evaluation of Generalized Aggressive Decoding: Training hyperparameters for Generalized Aggressive Decoding are specified for the evaluation.
  • B Details of Evaluation of Generalized Aggressive Decoding: The evaluation follows prior Transformer practices by averaging model parameters from the last 10 checkpoints.
  • B Details of Evaluation of Generalized Aggressive Decoding: The Generalized Aggressive Decoding setup applies checkpoint averaging alongside its listed training configuration.

B.2 Detailed results of GAD/GAD++ on WMT14 EN↔DE and WMT16 EN↔RO

GAD/GAD++ performs consistently across WMT14 EN↔DE and WMT16 EN↔RO language pairs, with only slight speedup differences. The reported configurations are tuned separately on each benchmark’s development set.

  • GAD/GAD++ performs consistently well across all evaluated language pairs, despite slight differences in speedup ratios.
  • The experiments cover WMT14 EN↔DE and WMT16 EN↔RO, with X denoting the corresponding target language.
  • All GAD/GAD++ hyperparameters are tuned on each benchmark’s development set before evaluation.

B.3 Speedup Distribution

GAD provides substantial sentence-level acceleration on WMT14 EN-DE. Most sentences achieve 3×–6× speedup, while rare cases exceed 10×.

  • 3×–6× speedup covers most WMT14 EN-DE sentences compared with the beam search baseline.
  • Over 10× speedup occurs for some rare WMT14 EN-DE sentences.

B.4 Profiling

Profiling shows that GAD++ spends nontrivial time on input encoding and on repeated NAR decoding. These costs identify implementation opportunities and explain part of the module-level overhead.

  • Approximately 16% of GAD++ inference time is spent sequentially encoding the input for AR and NAR.
  • The naive sequential encoding implementation can be optimized to reduce GAD++ inference overhead.
  • The NAR decoder costs more than the AR decoder because it performs multiple computation rounds for previously decoded tokens.

B.5 Memory Analysis

GAD adds GPU memory for the NAR drafter but the reported increase is modest relative to Transformer-base. The memory footprint also includes dynamic encoder-state storage.

  • GAD-Base uses approximately 400MB more GPU memory than Transformer-base during inference.
  • About 250MB of the additional memory stores static NAR-drafter weights.
  • The remaining additional memory mainly stores final NAR-drafter encoder states and varies with input shape.
Loading 2205.10350v1…