Big-O to the O(n squared) attention wall

The most expensive number in a modern LLM isn't a weight - it's an exponent. Self-attention is $O(n^2)$ in the prompt length, and that single "2" is why long context costs real money.

Back in Big-O notation, Big-O was an abstract way to say how does the work grow as the input grows? Here it stops being abstract. In a Transformer, every token in the prompt looks at every other token to decide what to pay attention to - that's an $n\times n$ grid of comparisons for a prompt of $n$ tokens. Filling an $n\times n$ grid is $O(n^2)$ work. So double the prompt and you roughly quadruple the compute and the size of the attention matrix. That quadratic is the "wall" the whole industry is trying to climb over.

Big-O, the part that bills you

Three growth shapes matter here. $O(\log n)$ barely moves - binary search on a doubled list adds just one step. $O(n)$ is a fair deal - twice the tokens, twice the work, like scanning a list once. $O(n^2)$ is the trap - twice the tokens, four times the work, because the cost is an area, not a length. Self-attention lives squarely in that last class, and unlike a textbook sorting example, the "input" here is your prompt, billed per token, per request, forever.

Watch the wall build itself

Drag $n$ to grow the sequence. On the left the attention matrix fills in cell by cell - each cell is one query-key comparison. On the right, live operation counts race: the dashed red curve is the pure $O(n^2)$ wall, and the thick teal curve is self-attention sitting right on it. Now flip linear attention and watch the teal curve peel away from the wall and bend down toward the linear floor - because each token now only looks at a fixed window of neighbours, not all $n$.

Where the n² comes from

You can read the exponent straight off the code, exactly the way Big-O analysis teaches: count the nested loops. Full attention has a loop over queries wrapped around a loop over keys - two loops over the same $n$, so $n\times n$. Cap the inner loop to a fixed window $w$ and one of the $n$'s becomes a constant.

# Full self-attention: every token scores every token
for i in range(n):              # query i  - n of them
    for j in range(n):          # key j    - n each  => n*n pairs
        score[i][j] = dot(Q[i], K[j])
# work grows as n*n   ->  O(n^2)

# Sliding-window attention: each token sees only w neighbours
for i in range(n):              # query i  - n of them
    for j in range(i - w, i + 1):  # only w keys  => n*w pairs
        score[i][j] = dot(Q[i], K[j])
# work grows as n*w   ->  O(n) when w is fixed

Bending the parabola

Two different escapes, often confused. FlashAttention keeps the same $O(n^2)$ FLOPs but tiles the computation so the giant $n\times n$ matrix is never stored - it turns memory from $O(n^2)$ into $O(n)$ and runs far faster, yet the exponent on compute is unchanged. Sliding-window, sparse, and linear attention (Longformer, Mistral, Performer) change the exponent itself: give each token a fixed window $w$ or a low-rank summary and the cost drops to $O(n\cdot w)\approx O(n)$. The switch in the demo is that second kind - you literally see the diagonal band replace the full square.

Check yourself