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

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)

• 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.