The quadratic wall: Why LLM context windows are expensive

yourbasic.org/algorithms

Self-attention compares every token in a text with every other token. The cost grows with the square of the input size.

Two friendly robots in armchairs: one calmly holds a short scroll, the other is flustered by an endless scroll of parchment spilling across the floor.

STEFAN NILSSON – NOV 7, 2026

A large language model breaks the rules of correct, clear and efficient code, yet is very useful. But one part of an LLM is completely ordinary: the math inside the model obeys the same laws of time complexity as any other algorithm.

The self-attention algorithm used by an LLM has quadratic time complexity. This shapes the AI assistant you actually use: it is one of the main reasons long context windows are scarce and priced as premium features.

Counting the cost of attention

LLMs are built from a mechanism called self-attention. In plain language:

Self-attention gives each token in a text a query and a key, and computes a similarity score for every pair of tokens. Each score measures how much one token should attend to the other.

This is simply an algorithm that scores all pairs of elements. In pseudocode:

// Score every token against every other token.
Algorithm attention(q, k, s)
    for i ← 0 to n-1
        for j ← 0 to n-1
            s[i,j] ← dot(q[i], k[j])  // one pairwise score

The time complexity analysis is straightforward. There are n queries and n keys, and computing one score, dot(q[i], k[j]), is a constant-time operation. This makes the dot computation an obvious elementary operation: it dominates the computation and its cost doesn’t depend on the length of the text. Since each of the n queries is compared with each of the n keys, attention has quadratic time complexity, Θ(n²).

There is also a quadratic amount of memory: the table s of pairwise scores has n² entries. In naive implementations the full table exists during the computation. As we will see, memory is often the wall you hit first.

Example

Plug in some context-window sizes:

1,000 tokens: 1,000,000 pairwise scores,
8,000 tokens: 64,000,000,
64,000 tokens: ~4,100,000,000,
512,000 tokens: ~260,000,000,000.

An eightfold increase in context buys a sixty-fourfold increase in attention work. The model emits text one token at a time, and producing token k scores one new query against all k keys seen so far.

An implementation trick called the KV cache stores the key and value vectors of earlier tokens instead of recomputing them, but the total still sums to roughly n²/2: each additional token costs work proportional to the whole text so far.

The middle ground

Quadratic algorithms sit in a peculiar spot:

A linear or n log n algorithm grows smoothly with input.
An exponential algorithm is unfeasible everywhere; it never finishes.
A quadratic algorithm is feasible – until it suddenly isn’t.

A quadratic algorithm runs happily at n = 1,000. At n = 100,000 it performs ten billion operations.

Unlike the exponential case, the wall is real but movable – and its location is visible in public: doubling the context window quadruples the compute cost, while pricing stays linear per token.

Constants still count

The same lesson as always applies: constants matter. The FlashAttention algorithm keeps the exact same Θ(n²) score count, but computes the scores block by block in the GPU’s fast on-chip memory, so that the full quadratic table never has to be written to slow main memory. Same asymptotics, radically moved wall.

Beyond the wall

Compute is not the only limit on long context. Empirical studies report that models use long inputs unevenly, retrieving information from the beginning and end of a text better than from its middle. And a quadratic cost is not a law of nature: it is a property of one algorithm.

Sparse and sliding-window variants restrict which pairs are scored, and state-space models aim for linear complexity – so far with a quality trade-off. The search for an attention mechanism with provably good subquadratic behavior is an open problem, and one of the more consequential ones in computing today.