Quadratic Attention Bottleneck › Motivation for Efficient Attention

Instead of computing all $n^2$ attention scores, sparse attention methods compute only a subset. Local windows, strided patterns, and learned sparsity can reduce complexity to $O(n \cdot k)$, where $n$ is the sequence length and $k \ll n$ is the number of positions each token attends to. For example, with a local window of 256 tokens, $k = 256$ regardless of how long the sequence is, making the total cost linear in $n$. The assumption underlying sparse attention is that most long-range attention weights are small and can be set to zero without significantly affecting model quality. This holds surprisingly well for many practical tasks, where local context carries the most information.

Linear attention approximates the softmax attention mechanism with kernel functions that allow associativity. The key insight is changing the order of matrix operations: instead of computing $(QK^T)V$, which requires the $n \times n$ intermediate matrix, linear attention computes $Q(K^TV)$. Since $K^TV$ has shape $(d \times d)$ rather than $(n \times n)$, the $n^2$ term disappears, achieving $O(nd^2)$ complexity where $d$ is the model dimension. The trade-off is that the kernel approximation may not perfectly replicate the expressiveness of softmax attention, particularly for tasks that require sharp, content-dependent attention patterns.

FlashAttention and similar methods do not reduce asymptotic complexity but dramatically reduce memory consumption by restructuring the computation. Rather than materializing the full $n \times n$ attention matrix in GPU memory, they compute attention in small blocks, keeping only the current block in fast SRAM. This trades some recomputation for massive memory savings, enabling longer sequences within the same memory budget. FlashAttention is now standard in virtually every production transformer implementation because it requires no architectural changes and has near-zero accuracy cost.