Quadratic Attention Bottleneck › The Bottleneck Visualization

To fully appreciate the quadratic bottleneck, we can visualize how attention costs compare to other transformer components as sequence length grows. The transformer is not only attention: it also includes feed-forward networks (FFN), layer normalization, and QKV linear projections. At short sequences, these other components can dominate. At long sequences, the quadratic attention core takes over.

The key conceptual point is that every other component in a transformer scales linearly with sequence length. The feed-forward network processes each token independently, so its cost grows as $O(nd^2)$. The QKV projection matrices each perform an $(n \times d) \times (d \times d)$ matrix multiplication, costing $O(nd^2)$. Layer normalization costs $O(nd)$. None of these touch the $n^2$ term.

This means the bottleneck is not a static property of the model architecture but a dynamic one that emerges as sequences grow. For short sequences, attention is just another cheap operation. The crossover point, where attention becomes the dominant cost, depends on the ratio of $n$ to $d$.

At short sequence lengths (128-256 tokens), the feed-forward network and projections dominate, and attention contributes less than 10% of total computation. As sequences grow, the quadratic term takes over. By 4K tokens, attention accounts for nearly half of all operations. At 16K tokens and beyond, attention consumes the vast majority of the compute budget, squeezing out everything else.

This is the attention bottleneck in visual form. Optimizing transformers for long sequences means addressing the red region in this chart. The feed-forward and projection components (orange and blue) scale linearly, which is theoretically optimal for per-token processing. It is attention's all-pairs structure that breaks linear scaling and creates the growing red region.

The crossover region around 1K-2K tokens is particularly important for practical system design. Models that process sequences mostly below this threshold can be optimized for the FFN and projection costs. Models that routinely process longer sequences must prioritize attention efficiency. This is one reason why code models and document models have driven much of the efficient attention research: they deal with long inputs by nature.