Quadratic Attention Bottleneck › Summary

The quadratic attention bottleneck is a fundamental constraint that shapes transformer design and deployment at every scale. In this chapter, we quantified the $O(n^2)$ scaling in both memory and compute, traced the cost through every stage of the attention computation, and visualized how attention costs grow to dominate transformer computation at long sequence lengths.

Key takeaways:

• The all-pairs structure drives everything. Attention computes $n^2$ interactions because every token must be compared to every other token. This is both the source of attention's power and the root cause of its scaling problems.

• Quadratic memory. Storing attention matrices requires $O(h \cdot n^2 \cdot b \cdot L)$ memory, where $h$ is the number of attention heads, $b$ is bytes per element, and $L$ is the number of layers. This often becomes the first constraint hit when extending context length.

• Quadratic compute. The attention core requires $O(n^2 d)$ operations per layer, dominated by two matrix multiplications: score computation ($QK^T$) and output aggregation ($AV$). Softmax contributes less than 1% of attention FLOPs for typical model dimensions.

• The crossover point. At short sequences, attention is a minor cost. At long sequences (roughly 1K-4K tokens for typical models), attention becomes the dominant expense and eventually consumes over 80% of transformer FLOPs.

• Memory before compute. Memory is typically the binding constraint, not compute. GPUs cannot process data that does not fit in memory, making memory-efficient attention more urgently important than compute-efficient attention.

• Practical limits. Standard attention on current GPUs is limited to roughly 16K-32K tokens for training and 50K-100K tokens for inference, depending on model size and hardware. Beyond these limits, specialized techniques are required.

• Motivation for efficiency. The quadratic bottleneck drives research into sparse attention, linear attention, and memory-efficient implementations, each trading different aspects to break the $O(n^2)$ barrier. None of these are free lunches: each introduces approximations, implementation complexity, or hardware dependencies.

Understanding this bottleneck is essential for working with long-context models and for appreciating why the efficient attention techniques covered in the following chapters are so important. The $n^2$ wall is real, but it can be scaled with the right approaches, and knowing exactly where the cost comes from is the first step toward addressing it effectively.