Attention Complexity › Attention Complexity

The power of self-attention comes with a price. Every token attends to every other token, creating $n^2$ pairwise interactions for a sequence of $n$ tokens. This quadratic scaling is both the source of attention's strength and its primary limitation. Understanding the computational and memory costs of attention is essential for working with transformers at scale, choosing appropriate model configurations, and knowing when alternative architectures might be necessary.

Think of it this way: if you have a classroom of 30 students and every student must pass a note to every other student, you need $30 \times 30 = 900$ note exchanges. If the class doubles to 60 students, you need $60 \times 60 = 3600$ exchanges, four times as many. Self-attention faces exactly this combinatorial growth with every token in a sequence. At modest sequence lengths, this overhead is affordable. At the scale of entire documents, codebases, or long conversations, it becomes the central engineering challenge of modern language models.

The quadratic complexity is not an accident or an oversight. It is a direct consequence of what makes attention powerful: every token can consult every other token in a single operation. There are no intermediaries, no bottlenecks from sequential processing, no information that must travel through a chain of steps before reaching its destination. This directness is why transformers capture long-range dependencies so much more effectively than recurrent networks. The cost is that the number of computations grows as the square of the context, rather than linearly.

In this chapter, we analyze the complexity of attention from multiple angles: time complexity measured in floating-point operations (FLOPs), memory requirements for storing attention weights, and practical scaling limits. We compare attention to recurrent models and explore why the quadratic cost becomes prohibitive for long sequences. We also survey a range of efficient attention variants, which attempt to preserve the quality of full attention while reducing its computational footprint.

By the end of this chapter, you will have a precise, quantitative understanding of where the costs come from, which hardware constraints matter most in practice, and how researchers have approached breaking the quadratic barrier. This understanding is not merely academic. It determines which models you can run, which tasks require specialized infrastructure, and which architectural choices are worth the trade-off at a given scale.