Generating Long Sequences with Sparse Transformers

By Rewon Child, Scott Gray, Alec Radford, Ilya Sutskever. 2019

2,592 citations recorded by the source corpus.

Transformers are powerful sequence models, but require time and memory that grows quadratically with the sequence length. In this paper we introduce sparse factorizations of the attention matrix which reduce this to $O(n \sqrt{n})$. We also introduce a) a variation on architecture and initialization to train deeper networks, b) the recomputation of attention matrices to save memory, and c) fast attention kernels for training. We call networks with these changes Sparse Transformers, and show they can model sequences tens of thousands of timesteps long using hundreds of layers. We use the same architecture to model images, audio, and text from raw bytes, setting a new state of the art for density modeling of Enwik8, CIFAR-10, and ImageNet-64. We generate unconditional samples that demonstrate global coherence and great diversity, and show it is possible in principle to use self-attention to model sequences of length one million or more.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

In Model Architectures

Citations in the corpus

Scaling Laws for Neural Language Models (2020, background): “Sparsity [CGRS19, GRK17] or branching (e.g. [KSH12]) may allow for even faster training of large networks through increased model parallelism.”
PaLM: Scaling Language Modeling with Pathways (2022, background): “Sparsity in the sequence length is an area that allows for training efficiently with extremely long sequences (Zaheer et al., 2020; Tay et al., 2020; Choromanski et al., 2020; Kitaev et al., 2020; Roy et al., 2020; Child et al., 2019; Gale et al., 2019).”
Mistral 7B (2023, background): “Mistral 7B leverages grouped-query attention (GQA) [1], and sliding window attention (SWA) [6, 3].”
An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale (2020, neutral): “In a different line of work, Sparse Transformers (Child et al., 2019) employ scalable approximations to global self-attention in order to be applicable to images.”
Denoising Diffusion Probabilistic Models (2020, background): “Still, while our lossless codelengths are better than the large estimates reported for energy based models and score matching using annealed importance sampling [11], they are not competitive with other types of likelihood-based generative models [7].”
High-Resolution Image Synthesis with Latent Diffusion Models (2021, background): “While autoregressive models (ARM) [6, 10, 91, 92] achieve strong performance in density estimation, computationally demanding architectures [94] and a sequential sampling process limit them to low resolution images.”
ALBERT: A Lite BERT for Self-supervised Learning of Language Representations (2019, methodology): “An important next step is thus to speed up the training and inference speed of ALBERT through methods like sparse attention (Child et al., 2019) and block attention (Shen et al.”
Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism (2019, methodology): “Since the vocabulary size is on the order of tens of thousands of tokens for modern language models (for example, GPT-2 used a vocabulary size of 50,257), it is beneficial to parallelize the output embedding GEMM.”
CTRL: A Conditional Transformer Language Model for Controllable Generation (2019, methodology): “Yet language models show potential for mitigating these problems directly (Trinh & Le, 2018; Radford et al., 2019) or indirectly (Ra-jani et al., 2019; Xenouleas et al., 2019; Scialom et al., 2019).”
One Epoch Is All You Need (2019, background): “…2018) Not reported BERT (Devlin et al., 2018) 40 Mesh Transformer (Shazeer et al., 2018) 10 Transformer-XL (Dai et al., 2019) Not reported GPT-2 (Radford et al., 2019) Not reported (20 or 100) Sparse Transformer (Child et al., 2019) 70 - 120 dataset for many epochs to make the comparison with…”
Efficient Large Scale Language Modeling with Mixtures of Experts (2021, methodology): “We use prenormalization transformer blocks (Baevski and Auli, 2019; Child et al., 2019) and GELU activations (Hendrycks and Gimpel, 2016).”
Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity (2021, methodology): “Sparsity along the sequence length dimension (L) in the Transformer attention patterns has been a successful technique to reduce the attention complexity from O(L2) (Child et al., 2019; Correia et al., 2019; Sukhbaatar et al., 2019; Kitaev et al., 2020; Zaheer et al., 2020; Beltagy et al., 2020).”
Compressive Transformers for Long-Range Sequence Modelling (2019, methodology): “Several works have focused on reducing the computational cost of attention with sparse access mechanisms (Rae et al., 2016; Child et al., 2019; Sukhbaatar et al., 2019; Lample et al., 2019).”
Evaluating Large Language Models Trained on Code (2021, methodology): “Scalable sequence prediction models (Graves, 2014; Vaswani et al., 2017; Child et al., 2019) have become a general-purpose method for generation and representation learning in many domains, including natural language processing (Mikolov et al., 2013; Sutskever et al., 2014; Dai & Le, 2015; Peters…”
Rethinking Attention with Performers (2020, methodology): “, 2018) or incorporate structural priors on attention such as sparsity (Child et al., 2019), pooling-based compression (Rae et al.”
Big Bird: Transformers for Longer Sequences (2020, methodology): “Child et al. [16] proposed a sparse model that reduces the complexity to O ( N p N ) , Kitaev et al. [49] further reduced the complexity to O ( N log( N )) by using LSH to compute nearest neighbors.”
Efficient Content-Based Sparse Attention with Routing Transformers (2020, methodology): “(Child et al., 2019).”
Reformer: The Efficient Transformer (2020, methodology): “OpenAI introduced the sparse Transformer (Child et al., 2019) which exploits a factorized sparse representation of attention.”