Attention Complexity › Summary

Attention's quadratic complexity is a fundamental characteristic that shapes how we build and use transformer models. In this chapter, we analyzed this complexity from multiple angles, built precise formulas for estimating real-world costs, compared attention to recurrent alternatives, and surveyed a range of efficient attention methods.

Key takeaways:

• Time complexity: Standard self-attention requires $O(n^2 d)$ operations, where $n$ is sequence length and $d$ is model dimension. The $n^2$ term means doubling sequence length quadruples computation. This is not an approximation or a worst-case bound: it is the exact cost of the all-pairs interaction that defines the mechanism.

• Memory complexity: Storing attention matrices requires $O(h \cdot n^2)$ memory, where $h$ is the number of heads. This quadratic memory scaling often becomes the limiting factor before compute does. Doubling context length quadruples memory for attention matrices, which is why GPU memory capacity is a central constraint in long-context systems.

• Three-stage decomposition: The cost breaks down as score computation ($n^2 d_k$ operations), softmax normalization ($3n^2$ operations), and output aggregation ($n^2 d_v$ operations). The softmax is negligible; the two matrix multiplications dominate.

• Crossover with RNN: Setting $n^2 d = nd^2$ shows that attention is cheaper than RNN when $n < d$, but more expensive when $n > d$. For typical model dimensions (512 to 4096), attention becomes more expensive beyond a few hundred tokens. Despite this, attention is preferred because path lengths are $O(1)$ rather than $O(n)$, making long-range dependencies much easier to learn.

• Practical limits: GPU memory and compute time impose hard constraints on context length. Even with 80GB GPUs, sequence lengths beyond tens of thousands of tokens require specialized techniques. The memory bottleneck typically arrives before the compute bottleneck at realistic batch sizes.

• The attention bottleneck: As sequence length grows, attention dominates transformer computation. At 256 tokens, attention is only 5% of layer FLOPs. At 4096 tokens, it approaches 45%. Beyond 8192 tokens, attention is the primary cost component in each transformer layer.

• Efficient alternatives: Linear attention, sparse attention, and memory-efficient implementations (especially FlashAttention) can reduce effective complexity from $O(n^2)$ to $O(n)$ or $O(n \cdot k)$, where $k$ is the number of attended positions. FlashAttention achieves the same result as full attention with less memory by restructuring computation to minimize data movement between memory tiers.

Understanding these complexity characteristics is essential for choosing appropriate architectures, estimating computational requirements, and knowing when to apply optimization techniques. The quadratic wall is real, but the right tools and understanding can help keep it manageable. The progression from 512-token BERT to million-token Gemini reflects hardware improvements and algorithms such as FlashAttention, supported by engineering that keeps the $n^2$ term manageable without sacrificing the expressive power that makes attention valuable in the first place.