Quadratic Attention Bottleneck › The All-Pairs Problem

Self-attention computes relationships between every pair of tokens in a sequence. For a sequence of $n$ tokens, this means $n^2$ pairwise interactions. This is the defining structural feature of attention, and it is the root cause of every scaling challenge discussed in this chapter.

To understand why all pairs are necessary, consider what attention is trying to accomplish. When reading the sentence "The trophy didn't fit in the suitcase because it was too big," a model needs to determine that "it" refers to "the trophy," not "the suitcase." To resolve this correctly, the word "it" must simultaneously consider "trophy," "suitcase," and "big" and compare their relevance. Attention provides exactly this capability: every token can look at every other token and decide how much weight to give each one. Restricting this to a subset of tokens would risk missing the very long-range dependencies that make attention powerful.

The complete attention formula captures this all-pairs comparison in matrix form. To compute attention for a sequence of $n$ tokens with representations of dimension $d_k$, we first project each token into QKV vectors, then compute:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

where:

• $Q \in \mathbb{R}^{n \times d_k}$: the query matrix, with one row per token representing "what this token is looking for"
• $K \in \mathbb{R}^{n \times d_k}$: the key matrix, with one row per token representing "what this token contains"
• $V \in \mathbb{R}^{n \times d_v}$: the value matrix, with one row per token representing the information to aggregate
• $d_k$: the dimension of queries and keys, used as a scaling factor
• $n$: the sequence length (number of tokens)

The critical operation is $QK^T$, which produces an $n \times n$ attention score matrix. Every element $(i, j)$ in this matrix represents how much token $i$ should attend to token $j$. Computing all $n^2$ entries is what gives attention its power: any token can directly influence any other, regardless of distance. But this same property creates the quadratic scaling problem.

Consider the contrast with sequential processing. In a recurrent neural network, information from token 1 must propagate through tokens 2, 3, 4, and so on to reach token 100. In attention, token 1 directly connects to token 100 in a single step. This short path length is why transformers excel at capturing long-range dependencies. The price is computing all pairwise interactions up front, and that price grows quadratically.

Notice that there is no mathematical shortcut here. The score matrix entry at position $(i, j)$ requires knowledge of both token $i$'s query and token $j$'s key. Until you compute all $n^2$ scores, you cannot determine which tokens attend to which. Later in this part of the book, we will explore approximations that avoid computing the full matrix, but they do so at the cost of either accuracy or certain types of dependencies.

The "Growth Factor" column reveals the quadratic pattern with stark clarity: doubling the sequence length quadruples the number of interactions. At 128 tokens, we compute roughly 16,000 pairs. At 4,096 tokens, this explodes to over 16 million pairs. The 4x growth for each 2x increase in sequence length is the signature of $O(n^2)$ complexity, and it compounds relentlessly as sequence lengths scale toward the tens or hundreds of thousands of tokens that modern applications demand.

In practice, this means that a model processing a 32,768-token document performs roughly 65,000 times more attention interactions than the same model processing a 512-token paragraph. No other component of the transformer scales this aggressively with input length, which is why attention dominates the resource budget at long sequences.

The first panel shows the raw explosion in pair count, rising from near zero at short sequences to over 16 million at 4,096 tokens. The second panel, using logarithmic scales on both axes, reveals the underlying structure: a straight line with slope 2, confirming the $n^2$ relationship. Each doubling of sequence length produces exactly a 4x increase in pairs, marked along the curve.

The log-log view is particularly instructive because it turns the quadratic relationship into something visually linear, making the constant growth factor visible at every step. Any time you see a log-log plot produce a straight line with slope 2, you are looking at quadratic scaling.