Quadratic Attention Bottleneck › Limitations of Standard Attention

The quadratic bottleneck is well-understood and extensively studied, but it is worth being explicit about what it means for real systems and what it does not mean.

Standard attention is not simply slow. It is correct, in the sense that it computes the exact full attention distribution over all tokens, with no approximation. Every efficient alternative introduces either an approximation (sparse and linear attention) or a restructuring that preserves exact answers but cannot be used everywhere (FlashAttention). This distinction matters because approximate methods may perform worse on tasks that require global, long-range attention. For short to medium sequences, standard attention is the right choice: it is simple, well-understood, and produces the best possible attention distribution.

The memory constraint is also more fundamental than the compute constraint for most practical systems. Modern GPUs can handle large amounts of computation in parallel, but GPU memory is small relative to the data sizes that long-context models need to process. A batch that does not fit in memory cannot be processed at all, regardless of compute speed. This is why FlashAttention's memory savings have been more practically impactful than its speed improvements, even though both are significant.

Another limitation that often goes unmentioned is the cost of the key-value cache during autoregressive inference. When a transformer generates text one token at a time, it reuses the key and value vectors from all previous tokens to avoid recomputing them. This KV cache grows linearly with sequence length in terms of the number of entries, but the memory it consumes is still $O(n \cdot d)$ per layer, which becomes substantial at long contexts. For a 32-layer model with a 128K-token context, the KV cache alone can consume dozens of gigabytes, creating a different kind of memory pressure from the training bottleneck.

The quadratic bottleneck is a property of the standard attention formulation, not of transformers as a class. Many transformer-like architectures have been proposed that avoid the $n^2$ scaling entirely while preserving the key benefits of attention: parallel computation, direct token-to-token interaction, and expressive capacity. State space models, linear recurrences, and hybrid architectures represent active areas of research aimed at breaking the quadratic barrier at the architectural level rather than the implementation level.