Blockwise Parallel Decoding for Deep Autoregressive Models

By Mitchell Stern, Noam Shazeer, Jakob Uszkoreit. 2018

386 citations recorded by the source corpus.

Deep autoregressive sequence-to-sequence models have demonstrated impressive performance across a wide variety of tasks in recent years. While common architecture classes such as recurrent, convolutional, and self-attention networks make different trade-offs between the amount of computation needed per layer and the length of the critical path at training time, generation still remains an inherently sequential process. To overcome this limitation, we propose a novel blockwise parallel decoding scheme in which we make predictions for multiple time steps in parallel then back off to the longest prefix validated by a scoring model. This allows for substantial theoretical improvements in generation speed when applied to architectures that can process output sequences in parallel. We verify our approach empirically through a series of experiments using state-of-the-art self-attention models for machine translation and image super-resolution, achieving iteration reductions of up to 2x over a baseline greedy decoder with no loss in quality, or up to 7x in exchange for a slight decrease in performance. In terms of wall-clock time, our fastest models exhibit real-time speedups of up to 4x over standard greedy decoding.

Subfields: Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Model Architectures

Citations in the corpus

SpanBERT: Improving Pre-training by Representing and Predicting Spans (2019, methodology): “Stern et al. (2018) focus on improving language generation speed using a block-wise parallel decoding scheme; they make predictions for multiple time steps in parallel and then back off to the longest preﬁx validated by a scoring model.”
KERMIT: Generative Insertion-Based Modeling for Sequences (2019, methodology): “We also follow prior work (Gu et al., 2018; Stern et al., 2018, 2019; Lee et al., 2018) in using distillation (Hinton et al., 2015; Kim and Rush, 2016) to train our models.”
Scaling Autoregressive Video Models (2019, background): “Though this might still be impractical we argue that further advances in parallel sampling strategies (Stern et al., 2018) and future hardware will alleviate this disadvantage significantly.”
Predictive Sampling with Forecasting Autoregressive Models (2020, methodology): “Finally, a method that predicts what a language model will output in order to save runtime has been proposed in (Stern et al., 2018).”
Fast Inference from Transformers via Speculative Decoding (2022, background): “Blockwise Parallel Decoding (Stern et al., 2018) decodes several to-kens in parallel, similarly to our work.”
Accelerating Large Language Model Decoding with Speculative Sampling (2023, methodology): “This can be attained with either a parallel model (Stern et al., 2018) or by calling a faster, auto-regressive model 𝐾 times.”
Instantaneous Grammatical Error Correction with Shallow Aggressive Decoding (2021, methodology): “In contrast, our proposed shallow aggressive decoding tries to accelerate the model inference through parallel autoregressive decoding which is related to some previous work (Ghazvininejad et al., 2019; Stern et al., 2018) in neural machine translation (NMT), and the imbalanced encoder-decoder archi”
Insertion Transformer: Flexible Sequence Generation via Insertion Operations (2019, background): “Semi-Autoregressive Left-to-Right SAT (Wang et al., 2018) 24.83 n/ 6 Blockwise Parallel (Stern et al., 2018) canvas is an embedding space, while our canvas contains discrete tokens.”
Insertion-based Decoding with Automatically Inferred Generation Order (2019, background): “Semi-autoregressive modelling (Stern et al., 2018; Wang et al., 2018a) is a mixture of the two approaches, while largely adhering to left-to-right generation.”
Real or Fake? Learning to Discriminate Machine from Human Generated Text (2019, background): “ontribution Preprint. Under review. arXiv:1906.03351v1 [cs.LG] 7 Jun 2019 2 Related Work While there is ongoing effort towards generating text without specifying a word ordering [Kaiser et al., 2018, Stern et al., 2018, 2019, Gu et al., 2019, Ghazvininejad et al., 2019], the dominant approach to tex”
Levenshtein Transformer (2019, background): “Stern et al. (2018); Wang et al. (2018) designed partially parallel decoding schemes to output multiple tokens at each step.”
Understanding Knowledge Distillation in Non-autoregressive Machine Translation (2019, methodology): “To improve the model’s ability to handle multi-modality, recent works have incorporated approaches including (1) relaxing the fully non-autoregressive restriction and adopting K decoding passes (instead of just one) to iteratively refine the generated outputs (Lee et al., 2018; Ghazvininejad et al.,”
Non-Monotonic Sequential Text Generation (2019, background): “Stern et al. (2018) and Wang et al. (2018) proposed to mix in these two paradigms and build a semi-autoregressive sequence generator, while largely sticking to left-to-right generation.”
Better & Faster Large Language Models via Multi-token Prediction (2024, methodology): “Self-speculative decoding Stern et al. (2018) are, to the best of our knowledge, the first to suggest a speculative decoding scheme for faster inference.”
Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads (2024, methodology): “To streamline and democratize the acceleration of LLM inference, we take inspiration from Stern et al. (2018), which utilizes parallel decoding for tasks such as machine translation and image super-resolution.”
Deep Encoder, Shallow Decoder: Reevaluating Non-autoregressive Machine Translation (2020, background): “, 2021), partially decoding autoregressively (Stern et al., 2018; 2019), rescoring output candidates autoregressively (e.”
Speculative Decoding: Exploiting Speculative Execution for Accelerating Seq2seq Generation (2022, methodology): “However, previous attempts in the “ draft-then-verify ” paradigm such as Blockwise Decoding (Stern et al., 2018) and Aggressive Decoding (Sun et al., 2021) tend to lack in-depth investigation of this paradigm.”
Parallel Iterative Edit Models for Local Sequence Transduction (2019, methodology): “Stern et al. (2018) use a parallel generate-and-test method with modest speed-up.”
Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding (2024, methodology): “Particularly, Blockwise Decoding (Stern et al., 2018) and Medusa (Cai et al., 2023) introduced additional FFN heads on top of the Transformer decoder, enabling the generation of multiple tokens simultaneously per step.”