Abstract
Self-attention has recently been adopted for a wide range of sequence modeling problems. Despite its effectiveness, self-attention suffers from quadratic compute and memory requirements with respect to sequence length. Successful approaches to reduce this complexity focused on attending to local sliding windows or a small set of locations independent of content. Our work proposes to learn dynamic sparse attention patterns that avoid allocating computation and memory to attend to content unrelated to the query of interest. This work builds upon two lines of research: it combines the modeling flexibility of prior work on content-based sparse attention with the efficiency gains from approaches based on local, temporal sparse attention. Our model, the Routing Transformer, endows self-attention with a sparse routing module based on online k-means while reducing the overall complexity of attention to $O(n^{1.5}d)$ from $O(n^2d)$ for sequence length $n$ and hidden dimension $d$. We show that our model outperforms comparable sparse attention models on language modeling on Wikitext-103 (15.8 vs 18.3 perplexity) as well as on image generation on ImageNet-64 (3.43 vs 3.44 bits/dim) while using fewer self-attention layers. Additionally, we set a new state-of-the-art on the newly released PG-19 data-set, obtaining a test perplexity of 33.2 with a 22 layer Routing Transformer model trained on sequences of length 8192.
The Quadratic Bottleneck in Self-Attention
Standard Transformer architectures rely on a self-attention mechanism that 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 effective for short contexts, this quadratic scaling becomes a prohibitive bottleneck for long documents, high-resolution images, or audio sequences.
Previous solutions generally fall into two categories: fixed temporal sparsity (e.g., local sliding windows) and content-based sparsity. Fixed patterns are efficient but often miss dynamic, long-range dependencies. Conversely, prior content-based methods often required computing the full $N \times N$ dense attention matrix before sparsifying it, failing to provide actual compute or memory savings during training. The Routing Transformer addresses this by introducing a natively sparse, content-based attention mechanism.
Routing Attention via Online K-Means
The core innovation of the Routing Transformer is the use of spherical $k$-means clustering to route queries to relevant keys. Instead of exhaustive comparison, 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 permitted to attend to keys within its own cluster. Since vectors in the same cluster exhibit high dot products, this serves as an efficient approximation of Maximum Inner Product Search (MIPS).
By setting the number of clusters $k = \sqrt{n}$, the attention complexity is reduced to $O(n^{1.5}d)$. In practice, the architecture utilizes a synergy between local and global attention: half of the attention heads focus on local sliding windows to maintain local fluency, while the remaining "routing" heads capture global context via clustering.
Experimental Results
The Routing Transformer was evaluated on diverse benchmarks including Wikitext-103, enwik-8, ImageNet-64, and PG-19. A key advantage of the model is its ability to train directly on massive 8192-token sequences, unlike models that rely on truncated backpropagation through time.
Key performance highlights include:
- PG-19: Achieved a state-of-the-art test perplexity of 33.2, outperforming the Compressive Transformer (33.6) and Transformer-XL (36.3).
- Wikitext-103: Improved perplexity to 15.8, compared to 18.3 for Transformer-XL.
- ImageNet-64: Reached 3.43 bits/dim, surpassing the Sparse Transformer (3.44) and Reformer (3.65).
Discussion and Limitations
While the Routing Transformer offers significant theoretical efficiency gains, current hardware accelerators (like TPUs) lack highly optimized kernels for sparse matrix operations, leading to slower wall-clock times compared to purely local attention (e.g., 1.7x slower on PG-19). Furthermore, to maintain parallel efficiency, the authors employ a top-k sorting method to ensure balanced clusters, which is a practical approximation of strict clustering. Future work may involve exploring strictly balanced online $k$-means algorithms and applying this routing mechanism to other naturally sparse modalities like 3D point clouds or protein structures.
Summary updated