Back to paper library
arXiv 2019Language & TransformersPaper notes

Sparse Transformer

Sparse Attention Mechanism

Original paper

Generating Long Sequences with Sparse Transformers

Paper authors

Rewon Child · Scott Gray · Alec Radford · Ilya Sutskever

Publication
Publication venue not yet verified
First submitted to arXiv
arXiv:1904.10509
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{transformerssparsetransformer2019,
  title = {{Generating Long Sequences with Sparse Transformers}},
  author = {Rewon Child and Scott Gray and Alec Radford and Ilya Sutskever},
  year = {2019},
  eprint = {1904.10509},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.10509}
}
On this page

The computational complexity of the self-attention mechanism in a Transformer is O(n2)O(n^2).

With a quadratic cost like this, there is plenty of room to look for ways to make long sequences cheaper to process. OpenAI has done a great deal of foundational research; Sparse Transformer is one of those efforts.

Defining the Problem

This is an excerpt of paper Figure 2 with Chinese labels added on the former site. The panels show early layers, layers 19–20, selected layers, and layers 64–128. The network still uses full attention; these are neither Sparse Transformer scores nor sparse masks.

To investigate how the attention mechanism in the original Transformer model operates in practical scenarios, the researchers first created an image generation model.

The decoder-only Transformer autoregressively models pixel-channel values. A CIFAR-10 RGB image gives a sequence of 32 × 32 × 3 = 3,072 values, rather than the patch tokens later used by ViT.

This 128-layer full-attention model was trained on CIFAR-10. The authors inspect its learned attention maps to motivate the later sparse patterns.


The white highlights are one head's attention weights while generating the current pixel value. Black is the autoregressive mask: future locations cannot be read yet. Selective brightness does not show that all dim connections can be removed without changing the model.

This analysis is broken down into several parts:

The Initial Layers

In the initial layers, the model's attention focuses around the "currently decoding token," similar to the receptive fields in convolutional neural networks.

Layers 19-20

In layers 19 and 20, weights gather along rows and columns. This is a learned pattern in a full-attention network that suggests the later factorization; this figure does not itself show a computation saving.

Various Layers

Some layers assign weight to distant positions in a data-dependent way. A predetermined sparse mask would change which such patterns the network can learn.

Layers 64-128

In the latter half of the network, attention concentrates on relatively few positions. These layers still compute attention over those positions.


The insights from these experimental results are:

  • This visualization suggests that some tasks may not require every layer to connect every token pair. Which connections can be removed still needs to be tested with a specific sparse pattern.

Solving the Problem

Paper Figure 3: the top row uses a 6×6 image to show which locations each factor reads; the lower row unfolds output rows and input columns into connectivity matrices. This shows connections, not the complete network architecture.

The solution is to create a mechanism that allows the model to selectively attend to certain tokens rather than all tokens.

Panel (a) has full attention, (b) uses strided connections, and (c) uses fixed connections. Each sparse scheme separates the readable positions into two factors. Across two attention steps, any past location can still reach a future output. Reachability does not make the resulting weights numerically identical to one full-attention step.

The blank upper triangle expresses causal decoding: a position reads itself and earlier positions, never future ones.

Solution 1: Fixed Stride

As shown in figure (b), this architecture takes inspiration from the earlier experimental results:

  • One pattern attends locally to roughly the previous ll positions.
  • The other attends every ll positions: for position ii, this means valid causal positions i,i−l,i−2l,…i, i-l, i-2l, \ldots. Choosing l≈nl \approx \sqrt{n} balances the two connection counts.

Solution 2: Fixed Specific Index Tokens

Figure (c) shows the fixed pattern. Strided attention suits images and some music/audio structures; the paper also uses it for audio.

Text lacks this regular structure, motivating the alternative fixed pattern.

Fixed attention combines local block connections with the final cc designated positions of earlier blocks. For stride l=128,c=8l=128,c=8, later positions can read roughly the last eight positions of each earlier block; the enwik8 experiment uses l=128,c=32l=128,c=32. Weights are learned, but the mask predetermines indices, and larger cc costs more. Stacked paths transmit distant information without reproducing the exact output of full attention.

Think of those end-of-block tokens as "anchors": one attention step can gather information there, and the next can pass it on to later positions.

Modified Attention Mechanism

Using row vectors for tokens and SiS_i for the allowed positions:

qi=xiWq,KSi=stack⁡j∈Si(xjWk),VSi=stack⁡j∈Si(xjWv)q_i = x_i W_q, \quad K_{S_i} = \operatorname{stack}_{j\in S_i}(x_j W_k), \quad V_{S_i} = \operatorname{stack}_{j\in S_i}(x_j W_v) a(xi,Si)=softmax⁡ ⁣(qiKSiTdk)VSia(x_i,S_i)=\operatorname{softmax}\!\left(\frac{q_i K_{S_i}^{T}}{\sqrt{d_k}}\right)V_{S_i}

Here Wq,Wk,WvW_q,W_k,W_v are projection matrices and dkd_k is the key dimension. Combining per-position outputs gives the layer output. If each of two factors keeps roughly n\sqrt n locations, the connection cost is O(nn)O(n\sqrt n). Real speedups require kernels that calculate only selected blocks; masking a fully calculated matrix retains its multiplications. The paper also tests alternating layers, merged heads and multihead variants, so the two factors in Figure 3 do not require exactly two heads in every layer.

Other Optimizations

Besides the attention mechanism optimizations mentioned above, the paper also discusses some other optimization methods:

For deep networks, the authors place LayerNorm before the attention and FFN branches, preserve a direct residual path, and additionally scale the initial output projections WpW_p and W2W_2 by 1/2N1/\sqrt{2N} for NN layers. These choices join activation recomputation, sparse kernels and mixed precision in the reported hundreds-of-layers setup.

  1. Checkpointing

    The gradient checkpointing technique doesn't save all intermediate activation values during the forward pass. Instead, it only saves a part of the critical activations. During backpropagation, it recomputes the discarded intermediate activations based on the retained ones. This reduces memory usage but increases computation since some forward pass portions need to be recomputed.

    This technique comes from the paper:

    In this paper, the attention matrix and intermediate FFN results are recomputed during backpropagation. That saves memory and helps the authors train deeper networks.

  2. Importance of Position Embedding

    The authors found that using position embeddings that encode data structure attention patterns is crucial for the model's performance.

    • For image data

      The authors used ddata=3d_{\text{data}} = 3, corresponding to the row, column, and channel positions of each input token.

    • For text and audio data

      The authors used dattn=2d_{\text{attn}} = 2, with indices corresponding to the row and column indices in the matrix.

    For text and audio, the row and column are attention coordinates after arranging the sequence with width equal to the stride, not an intrinsic two-dimensional layout of text or sound. The authors found these learned embeddings useful in their setup.

  3. Mixed Precision

    The authors stored network weights in single precision but computed network activations and gradients in half precision. They used dynamic loss scaling during gradient computation to reduce numerical underflow and transmitted half-precision gradients when averaging across multiple GPUs. During sampling, they converted queries and keys to single precision to avoid overflow.

Training Setup

  • Use Adam optimizer.
  • Perform 5000 iterations of linear warm-up.
  • Use gradient clipping with a value of 1.0.
  • Apply a weight decay penalty of 0.01.
  • Anneal the learning rate using cosine decay (referencing Radford et al., 2018).
  • Default training on 8 V100 GPUs.
  • Initialize content embeddings WeW_e from N(0,0.125/d)\mathcal{N}(0, 0.125/\sqrt{d}).
  • Initialize position embeddings from N(0,0.125/dnemb)\mathcal{N}(0, 0.125/\sqrt{d n_{\mathrm{emb}}}).
  • Initialize all biases in attention and FFN components to 0.
  • Initialize attention and FFN weights from N(0,0.125/din) \mathcal{N}(0, 0.125/\sqrt{d_{\mathrm{in}}}).
  • Initialize the output logits' weight matrix to 0.

Discussion

The imported image is paper Table 1. For image tasks, bits per byte equals bits per dimension. The dense/fixed/strided comparison below comes from paper Table 2 and is not pictured here.

CIFAR-10

The 59M-parameter strided model gets 2.80 bits per byte on the test set, versus 2.85 for PixelSNAIL in Table 1; three seeds give 2.798 ± 0.004. Table 2 compares the same setup: dense 2.82 / Time/Iter 0.54, fixed 2.85 / 0.47, strided 2.80 / 0.38. The paper does not state a unit for Time/Iter, so these values support comparisons within this table. Here strided has both lower loss and shorter iteration time.

  • Model Configuration:
    • 2 heads
    • 128 layers
    • Embedding dimension d=256d = 256
    • Half-size feed-forward networks and query-key projections
  • Training Parameters:
    • Learning rate: 0.00035
    • Dropout rate: 0.25
    • Trained for 120 epochs until validation error stopped decreasing
  • Data Split:
    • Training set: 48,000 samples
    • Validation set: 2,000 samples

EnWik8

The 95M-parameter fixed model gets 0.99 bits per byte, ahead of similar-sized Transformer-XL 88M / 1.03 and matching its larger 277M / 0.99 model; three seeds give 0.992 ± 0.001. In Table 2, dense yields 1.00 / Time/Iter 1.31, fixed 0.99 / 0.55, and strided 1.13 / 0.35. Strided is faster but clearly worse on this text benchmark.

  • Model Configuration:
    • 30 layers (Fixed)
    • 8 heads
    • Embedding dimension d=512d = 512
    • Dropout rate: 0.40
  • Training Parameters:
    • Trained for 80 epochs until validation loss stopped decreasing
    • Context length: 12,288
    • Stride: 128
    • Fixed summary width c=32c=32; this experiment merges the two factorized attention heads
  • Data Split:
    • Training set: First 90 million tokens
    • Validation and test sets: Last 10 million tokens

ImageNet 64x64

To test the model's ability to learn long-range dependencies and scale to large datasets, the authors trained it on a downsampled version of ImageNet and evaluated it on the validation set.

The 152M-parameter strided model gets 3.44 bits per byte on the validation set, versus the earlier 150M-parameter SPN at 3.52. The paper reports this value from one training run.

The authors visually inspect generated samples from a separately trained, roughly 300M-parameter model and judge that most show long-range structure. This is neither a blinded assessment nor a numerical result for the 152M model above.

  • Model Configuration:
    • 48 layers (Strided)
    • 16 heads
    • Embedding dimension d=512d = 512
    • Total parameters: 152 million
  • Training Parameters:
    • Stride: 128
    • Dropout rate: 0.01
    • Trained for 70 epochs
    • Used 64 V100 GPUs, training took 7 days

Conclusion

Sparse Transformer shows how sparse attention can reduce computation on natural images, text and raw audio. The results also remind us that the pattern has to suit the data: strided works best in the CIFAR-10 comparison, while fixed works best on enwik8. Table 2 shows that the faster strided scheme raises enwik8 loss from 1.00 to 1.13 bits per byte relative to dense attention.

This line of work appears again in many later studies. Let's keep this paper close at hand; we are sure to meet these ideas again.