linear attention
**Linear Attention and Subquadratic Alternatives** are the **efficient attention mechanisms that reduce the O(N²) computational and memory cost of standard Transformer self-attention to O(N) or O(N log N)** — enabling processing of extremely long sequences (100K+ tokens) that would be prohibitively expensive with quadratic attention, with architectures like RWKV, RetNet, and Mamba offering Transformer-competitive quality at a fraction of the inference cost for long contexts.
**The Quadratic Attention Problem**
- Standard attention: Attention(Q,K,V) = softmax(QK^T/√d) × V
- QK^T is an N×N matrix → O(N²) computation and memory.
- 4K tokens: 16M attention entries → manageable.
- 128K tokens: 16B attention entries → 64GB memory for one layer.
- 1M tokens: 1T entries → completely impossible with standard attention.
**Subquadratic Architectures**
| Architecture | Complexity | Mechanism | Quality vs. Transformer |
|-------------|-----------|-----------|------------------------|
| Standard attention | O(N²) | Full pairwise | Baseline |
| Linear attention | O(N) | φ(Q)φ(K)^T trick | 90-95% |
| RWKV | O(N) | RNN-like recurrence + attention | 95-98% |
| RetNet | O(N) | Retentive network, decaying attention | 95-98% |
| Mamba/S4 | O(N) | Selective state space model | 97-100% |
| Mamba-2 | O(N) | Structured SSM = linear attention | 98-100% |
**Linear Attention**
```
Standard: Attn = softmax(QK^T) V → O(N²d)
Linear: Attn = φ(Q)(φ(K)^T V) → O(Nd²)
Key insight: Compute (K^T V) first → this is d×d matrix (not N×N)
Then multiply Q × (K^T V) → O(Nd²)
When d << N, this is O(N) in sequence length
```
- Trade-off: φ(Q)φ(K)^T ≈ softmax(QK^T) only approximately.
- Quality gap: Depends on the kernel function φ — ELU, Random Fourier features, Cosine.
**RWKV (Receptance Weighted Key Value)**
- Combines RNN efficiency with Transformer-like parallelizable training.
- Training: Parallel scan (like attention, but O(N)).
- Inference: RNN-like recurrence → O(1) per token, constant memory.
- Architecture: Uses time-decay factors instead of attention matrices.
- RWKV-7 (Eagle): Competitive with Llama-3 at similar model sizes.
**RetNet (Retentive Network)**
```
Retention = (Q × K^T ⊙ D) × V
where D[i,j] = γ^(i-j) for i ≥ j, else 0
- γ < 1 → exponential decay → recent tokens matter more
- Training: Parallel (matrix form) → efficient on GPU
- Inference: Recurrent (O(1) per token)
- Chunk mode: Hybrid for moderate-length processing
```
**Inference Cost Comparison (2048 tokens)**
| Model | Prefill | Per-token decode | Memory |
|-------|---------|-----------------|--------|
| Transformer (7B) | 100 ms | 15 ms | 14 GB + KV cache |
| RWKV-7 (7B) | 80 ms | 8 ms | 14 GB (no KV cache) |
| Mamba-2 (7B) | 60 ms | 6 ms | 14 GB (no KV cache) |
- Key advantage: No KV cache → memory consumption is constant regardless of sequence length.
- Transformer at 128K context: KV cache is ~32GB. RWKV at 128K: still ~14GB.
**Trade-offs**
- In-context learning: Transformers still slightly better for few-shot learning.
- Retrieval: Attention can precisely recall any past token; linear models have decaying memory.
- Training parallelism: All approaches now support parallel training.
- Hardware: Standard attention is well-optimized (FlashAttention) → linear's theoretical advantage may not translate to wall-clock speedup for moderate lengths.
Linear attention and subquadratic alternatives are **the architectures that will enable truly long-context AI** — while Transformers with FlashAttention handle sequences up to 128K tokens practically, processing million-token documents, full codebases, or hours of audio will require O(N) architectures, making RWKV, Mamba, and their successors essential for the next generation of context-hungry AI applications.