Here is a summary of the paper "Efficient Content-Based Sparse Attention with Routing Transformers."
TL;DR
Standard Transformers struggle with long sequences because their self-attention mechanism scales quadratically with sequence length. The Routing Transformer solves this by using online $k$-means clustering to group similar queries and keys, reducing the complexity from $O(n^2)$ to $O(n^{1.5})$ without ever computing the full attention matrix. This dynamic, content-based sparse attention achieves state-of-the-art results on long-context benchmarks like PG-19 and Wikitext-103.
What Problem Does This Paper Address?
In a standard Transformer, the self-attention mechanism compares every token in a sequence to every other token. This results in a computational and memory complexity of $O(n^2)$, where $n$ is the sequence length. While fine for short sentences, this quadratic bottleneck makes it incredibly expensive to process long documents, high-resolution images, or audio.
Previous attempts to fix this generally fall into two camps:
- Temporal/Fixed Sparsity: Models only attend to a local sliding window or a fixed strided pattern (e.g., Sparse Transformer). While efficient, these models can miss dynamic, long-range dependencies.
- Content-Based Sparsity: Models learn which tokens should attend to each other based on their actual content. However, previous methods required calculating the massive $N \times N$ dense attention matrix first before making it sparse, which fails to actually save memory or compute during training.
This paper introduces a way to achieve content-based sparsity that is natively sparse—meaning it avoids computing the full attention matrix entirely.
Methods
The authors introduce the Routing Transformer, which combines standard local attention with a novel clustering-based global attention.
The core innovation is using spherical $k$-means clustering to route queries to relevant keys. Here is how it works:
- Instead of comparing a query to all possible keys, the model projects queries and keys onto a unit sphere and clusters them using an online, mini-batch $k$-means algorithm.
- A query is only allowed to attend to keys that fall into the same cluster.
- Because vectors in the same cluster have high dot products, this acts as a highly efficient approximation of Maximum Inner Product Search (MIPS). It ensures the model pays attention to the most relevant tokens while ignoring the rest.
By setting the number of clusters $k$ to $\sqrt{n}$, the computational complexity of the attention mechanism drops from $O(n^2d)$ to $O(n^{1.5}d)$. In practice, the authors design the network so that half of the attention heads focus on local sliding windows, and the other half use this $k$-means routing to capture global context.
Datasets
The model was evaluated across a mix of text and image generation tasks:
- CIFAR-10: Used primarily for ablation studies to test hyperparameter configurations.
- Wikitext-103: A standard word-level language modeling benchmark.
- enwik-8: A character-level language modeling benchmark.
- ImageNet-64 ($64 \times 64$): Used for autoregressive image generation.
- PG-19: A newly released (at the time) dataset by DeepMind consisting of Project Gutenberg books. It features massive sequence lengths (8192 tokens) designed to test true long-range memory.
Key Insights and Ideas
- Local + Global Synergy: The authors found that local attention is a surprisingly strong baseline on its own for maintaining local fluency. However, adding just a few "routing" heads forces global consistency (e.g., remembering a character's name or gender across thousands of words in a book).
- Clustering beats Hashing for MIPS: Contemporaneous work (like the Reformer) used Locality Sensitive Hashing (LSH) to approximate attention. This paper argues (and demonstrates empirically) that spherical $k$-means clustering is a superior approximation for Maximum Inner Product Search in dot-product attention.
- Direct Long-Sequence Training: Unlike models like Transformer-XL or Compressive Transformer—which train on short chunks and pass hidden states forward to simulate memory—the Routing Transformer is memory-efficient enough to train directly on massive 8192-token sequences.
Key Results
The Routing Transformer achieved state-of-the-art (SOTA) or highly competitive results across the board, often using fewer layers than competing models:
- PG-19: Set a new SOTA with a test perplexity of 33.2, beating the Compressive Transformer (33.6) and Transformer-XL (36.3).
- Wikitext-103: Achieved 15.8 perplexity, significantly improving over Transformer-XL's 18.3.
- ImageNet-64: Reached 3.43 bits/dim, outperforming the Sparse Transformer (3.44) and Reformer (3.65).
- enwik-8: Achieved a highly competitive 0.99 bits per byte.
Limitations and Future Work
- Wall-clock Speed: While theoretically more efficient ($O(n^{1.5})$), the Routing Transformer is currently slower in actual wall-clock time compared to purely local attention (e.g., 1.7x slower on PG-19). This is because standard hardware accelerators (like TPUs) lack highly optimized sparse matrix operations.
- Cluster Balancing: To ensure parallel processing efficiency, the authors force clusters to be perfectly balanced using a top-k sorting method. This is a slight hack that doesn't guarantee a point belongs to a single, strict cluster.
- Future Work: The authors suggest exploring strictly balanced $k$-means algorithms suited for online settings. They also note this routing mechanism could be highly useful for naturally sparse data modalities, such as 3D point clouds, social networks, or protein interactions.
Summary updated