Attention scales quadratically with sequence length, and it is the single most expensive operation in inference across nearly every model and architecture. The KV Cache turns decode into a linear-time operation in practice, but even linear scaling gets expensive, so optimizing attention is one of the most active areas of inference research.
Two strategies
- Implementation improvements: faster kernels that use memory and compute better. Lossless (no quality change), but still bound by the O(N²) time complexity.
- New algorithms: sub-quadratic approximations of attention. Trade some quality for better time/space complexity, though training can minimize the impact.
Implementation improvements
- FlashAttention: the famous one. The naive algorithm writes the intermediate S and P matrices to memory and reads them right back; FlashAttention eliminates those excess reads/writes and lays the computation out to fit the GPU exactly. Especially valuable for compute-bound work like LLM prefill and video generation.
- Paged Attention: partitions the KV cache into fixed-size blocks addressed through a lookup table, so the cache can live in fragmented memory instead of one contiguous block.
Neither changes the complexity
FlashAttention and PagedAttention make quadratic attention feasible, but attention is still O(N²). Breaking that ceiling needs a different algorithm.
Sub-quadratic variants
- Sliding window attention: attend only to the previous tokens, turning O(N²) into O(Nw), with often 8K–32K.
- Gated attention: layers introduced in training approximate attention over chunks in linear time.
- Linear attention: replaces the softmax with a linear-time approximation.
- Compressed attention: periodically compresses earlier context; attention sees compressed history plus recent tokens.
- Multi-latent attention (MLA): approximates attention in a low-dimensional latent space (DeepSeek).
Intuition
Nearby tokens matter more than distant ones, this sentence follows from the last more than from the start of the note. Applied during training, techniques like sliding-window attention produce models that keep quality high when the same trick is used at inference.
Escaping attention entirely
- State-space models (Mamba) replace self-attention with a recurrent state update, scaling linearly in sequence length.
- Hybrid models interleave Mamba-style blocks with transformer blocks; open models like NVIDIA Nemotron Nano are adopting the pattern.
See Self-Attention and Transformers for the underlying mechanics, and Arithmetic Intensity for why attention is the operation to profile when hunting bottlenecks.