Sparse Transformer

Analysis

Why This Paper Matters

Standard transformers scale quadratically with sequence length, making them impractical for long sequences like high-resolution images, long audio, or extended text. The Sparse Transformer breaks this barrier by introducing factorized attention patterns that reduce complexity to O(n√n), enabling models to handle sequences of tens of thousands of tokens. This is a foundational step toward efficient attention mechanisms that later inspired models like Longformer, BigBird, and Reformer.

How It Works

The core idea is to replace the full attention matrix with a sparse factorization. Instead of each token attending to all previous tokens, two attention heads each attend to a subset of size O(√n).

Two-dimensional factorized attention offers two patterns:

• Strided attention: One head attends to the previous l local positions, the other attends to every l-th position (stride l ≈ √n). This works well for periodic data like images or music.
• Fixed attention: One head attends to positions within the same block (size l), the other attends to a fixed set of positions that summarize previous blocks. This is better for non-periodic data like text.

Factorized attention heads can be integrated in three ways: interleaved (different pattern per residual block), merged (single head covering both patterns), or multi-head (parallel heads with reduced dimensions). The multi-head approach is typical.

Scaling to hundreds of layers uses pre-activation residual blocks with LayerNorm and GELU activation. Weight initialization is scaled by 1/√(2N) to keep gradient flow stable across N layers.

Efficient block-sparse kernels compute attention by slicing query, key, and value matrices into blocks. The softmax is fused into a single GPU kernel, and the upper triangle of the attention matrix is never computed, halving operations. Gradient checkpointing recomputes attention weights during backpropagation to save memory.

Results

Experiments on density modeling for images (CIFAR-10, ImageNet), text (Enwik8), and raw audio (WaveNet-style) show that sparse attention not only runs faster but also converges to lower negative log-likelihood than full attention. This suggests the sparsity patterns provide a useful inductive bias.

The model trains on sequences up to 16,384 tokens with hundreds of layers, which was previously infeasible.

Significance

The Sparse Transformer demonstrated that carefully designed sparse attention can match or exceed the performance of dense attention while being computationally tractable for long sequences. It opened the door to modeling raw data at scale without hand-crafted preprocessing. The techniques—factorized attention, gradient checkpointing, block-sparse kernels—became building blocks for later efficient transformer variants. This paper remains a key reference for anyone working on long-context or memory-efficient transformers.