Why twice the context costs four times as much. · Source

Twice the text, four times the work.

Attention's gift is that every word gets to weigh every other word — that's how it reads context so well. It's also the catch. Feed it twice as much and it doesn't work twice as hard; it works four times as hard. The all-seeing glance is priced by the square — and that price is the invisible wall behind every 'context window.'

We want it to read everything. The bill says no.

The dream is simple: drop in a whole book, a whole codebase, and let it hold the entire thing in mind at once. Storing the text is easy — that grows politely, line by line. The trouble is the cost of relating it all, which races ahead far faster than the text itself. Length grows in a straight line. The bill grows in a curve.

Why squared? Every word weighs every other word.

\text{comparisons} = n \times n = n^2

Attention isn't a quick scan. To place one word, the model weighs it against all the others — and it does that for every word. With n words, that's an n-by-n grid: n² little comparisons, no shortcut. Like string art: stretch a thread between every pair of pins around the rim, and the threads pile up as the square of the pins. A few more pins, a whole lot more thread.

Double the length, quadruple the cost.

\dfrac{\text{cost}(2n)}{\text{cost}(n)} = \dfrac{(2n)^2}{n^2} = 4

Because the work rides on n², a little more text hurts a lot. Twice the words isn't twice the effort — it's four times. Ten times the words? A hundred times the effort. Like tiling a floor: double the room's width and you haven't doubled the tiles — you've quadrupled them. The edge grows by two; the floor inside grows by four.

It's not just the math. It's the memory.

A \in \mathbb{R}^{n \times n} \;\Rightarrow\; \text{memory} = O(n^2)

Those n² scores aren't made and forgotten — the whole grid has to be held at once before it can become attention. So memory swells like n² too, and it's often the first wall you hit: not 'too slow,' but 'out of room.' Like a reservoir behind a dam: the longer the river you try to hold back, the higher the water climbs — until it's lapping at the very top.

One step explodes. The rest stays calm.

\underbrace{O(n\,d^2)}_{\text{the rest}} + \underbrace{O(n^2 d)}_{\text{all-pairs}}, \qquad n^2 d \gg n\,d^2 \iff n \gg d

Here's the saving grace, and the trap. Most of the model scales gently — pushing words through its layers costs about n·d². Only the all-pairs step costs n²·d. Like two climbing vines: they start side by side, but one keeps doubling its reach and surges past. Once the text is longer than the model is wide — once n passes d — that one vine, the square, overtakes everything.

The famous formula — now read its price tag.

\mathrm{Attention}(Q,K,V) = \mathrm{softmax}\!\left(\dfrac{QK^{\top}}{\sqrt{d}}\right)V \;\Rightarrow\; O(n^2 d)

Here it is — the whole of attention in one line. That inner QKᵀ is the all-pairs grid; it's where the n² is born. The power and the price are the same fact: a glance that touches everything must touch everything. Like a chandelier: to light the whole hall at once, every crystal has to blaze. The splendor is the cost.

🌱 You don't weigh every word against every other. So why must it?

When you read this line, you don't hold up each word against all the rest — you lean on nearness, on habit, on the gist, and quietly skip almost everything. That quadratic wall is the price of refusing to skip. So the open question is the whole frontier: what could a model safely ignore — and still understand every word?