Context
The standard self-attention mechanism in Transformers has O(n²) time and memory complexity with respect to sequence length. This quadratic scaling is the primary bottleneck for processing long documents, high-resolution images, and extended conversations.
Recent work has explored several approaches to break this barrier while preserving the expressiveness that makes attention so effective.
Linear Attention Variants
The core idea behind linear attention is to decompose the softmax attention kernel into separable feature maps, allowing the computation to be restructured from O(n²) to O(n):
Standard attention:
Attention(Q, K, V) = softmax(QK^T / √d) VLinear attention:
Attention(Q, K, V) = φ(Q)(φ(K)^T V) / φ(Q)(φ(K)^T 1)Where φ is a feature map (e.g., elu(x) + 1, or random Fourier features). The key insight is that by changing the order of matrix multiplication, we avoid materializing the n×n attention matrix entirely.
Notable Approaches
RetNet (Retentive Networks)
Proposes a “retention” mechanism that supports three computation paradigms: parallel (for training), recurrent (for inference), and chunk-wise (for long sequences). Achieves competitive performance with Transformers while enabling O(1) inference cost per token.
Mamba (Selective State Spaces)
Takes a different approach entirely by using structured state space models (SSMs) with input-dependent selection. Avoids the attention mechanism altogether while achieving strong performance on language modeling benchmarks. The key innovation is making the SSM parameters functions of the input, allowing the model to selectively propagate or forget information.
GLA (Gated Linear Attention)
Combines linear attention with a data-dependent gating mechanism. The gate allows the model to modulate the contribution of each key-value pair, recovering some of the expressiveness lost by removing softmax.
Open Questions
- Quality ceiling: Do linear attention models have a fundamental quality ceiling compared to softmax attention, or is it a matter of training methodology and scale?
- In-context learning: Softmax attention seems particularly well-suited for in-context learning. Can linear variants match this capability?
- Hybrid architectures: Is the optimal architecture a hybrid that uses full attention for some layers and linear attention for others?
Personal Take
The field seems to be converging on the idea that we need different mechanisms for different aspects of sequence modeling. Full attention is expensive but expressive; linear variants are efficient but may miss fine-grained dependencies. The winning architecture probably uses both strategically.
I’m particularly excited about Mamba’s approach of making state dynamics input-dependent. It feels like the right level of abstraction — the model learns what to remember rather than being forced to attend to everything.