What Attention Costs, and the Trilemma Underneath

Attention is expensive in two different ways, at two different times, and confusing them leads to reaching for the wrong fix.

The training cost is quadratic in sequence length. Every token attends to every other, so the score matrix has n squared entries per head per layer. Going from 2,048 to 8,192 tokens multiplies that by 16. Going to 131,072 multiplies it by 4,096.

The inference cost is different and often larger in practice. Generating one token requires attending to every previous token, so their keys and values must be retained. That is the KV cache, and it grows linearly with the sequence.

For a 70-billion-parameter model with grouped-query attention, the cache runs at about 320 KB per token. At 8k context that is 2.7 GB. At 128k it is 42.9 GB. At a million tokens it is 343.6 GB, which is more memory than the weights.

Memory-efficient attention implementations fixed the first cost by never materialising the score matrix. They did not touch the second, because the cache is not an implementation detail. It is what attention is.

It is worth dwelling on why the KV cache cannot simply be optimised away, because that constraint is what motivates every architecture in this path.

Attention has no persistent state. It does not summarise the past into anything. When it needs information from token 7, it goes and reads token 7's key and value directly. That direct access is the whole mechanism.

The consequence is that attention's memory is exact and complete. Nothing has been compressed, so nothing has been lost, and a model can retrieve an arbitrary detail from an arbitrary position with equal facility whether it appeared three tokens ago or three hundred thousand.

That is an extraordinary property and it is not free. Perfect recall over n items requires storing n items.

Grouped-query attention, multi-query attention, and cache quantization all shrink the constant. None of them change the fact that the cache is proportional to the sequence. To make memory constant in sequence length you have to give up perfect recall, and the interesting question is how much you give up and what you get for it.

The alternative is to compress. Maintain a fixed-size state, update it as each token arrives, and answer from the state rather than from the history.

The arithmetic is startling. A selective state space model with model dimension 4,096, an expansion factor of 2 and a state dimension of 16 holds 131,072 values per layer. Across 64 layers that is 8.4 million values, or about 16.8 MB in 16-bit.

That figure is constant. It is 16.8 MB at 8k context, at 128k, and at ten million. Nothing grows.

Against the transformer's 343.6 GB at a million tokens, the recurrent state is roughly twenty thousand times smaller.

The per-token compute is constant too. Generating a token means updating a fixed-size state and reading from it, regardless of how much came before, where attention must attend over an ever-growing cache.

What has been given up is exactness. Everything the model knows about the past is now compressed into those 8.4 million numbers, and compression is lossy. The rest of this path is about how much of the loss can be controlled.

Recurrent networks with fixed state predate transformers and were displaced by them, and understanding why is essential, because the reason was not accuracy.

A classical recurrent network computes each hidden state from the previous one through a nonlinearity. That dependency is strictly sequential: state t cannot be computed until state t minus 1 exists.

At inference that is fine, and in fact ideal, since you generate one token at a time anyway.

At training it is fatal. Attention computes all positions simultaneously as a matrix multiplication, saturating the hardware. A recurrent network must walk the sequence one step at a time, and a modern accelerator spends that walk almost entirely idle, because each step is far too small to occupy it.

The gap is not a constant factor. It is the difference between a job that scales across thousands of devices and one that does not.

So transformers won on trainability rather than on modelling. That framing tells you exactly what a successful alternative has to do: recover parallel training without giving up the constant-size state.

Three properties are wanted and, for a long time, only two seemed simultaneously achievable.

Parallel training means the whole sequence can be processed at once as dense matrix operations, which is what makes large-scale training possible at all.

Constant-cost inference means generating a token takes fixed time and memory regardless of how long the context is.

Perfect recall means any detail from any position can be retrieved exactly, without compression loss.

Attention takes parallel training and perfect recall, and pays with inference that grows without bound.

Classical recurrent networks take constant-cost inference and offer bounded recall, and pay by being untrainable at scale.

The diagram's third corner is what the field has been working toward: architectures that train in parallel and infer at constant cost, accepting compressed rather than perfect recall, and then trying to make the compression good enough that the loss does not matter.

The next two lessons are two routes to that corner, and they turn out to be the same route.

Before the mechanisms, it is worth knowing which workloads care, because for many the answer is none.

Short-context chat does not care. At 2k or 4k tokens, the KV cache is small and the quadratic term is not the bottleneck. An architecture change buys nothing measurable.

High-concurrency serving cares a great deal. As the quantization path showed, KV cache capacity determines how many sequences fit at once, so a constant-size state converts directly into concurrency. This is often the strongest practical argument.

Very long context cares. Whole codebases, long documents, hours of transcript, extended agent trajectories. Above roughly 100k tokens the cache starts to dominate the memory budget.

Edge and on-device inference cares acutely, because the memory ceiling is low and fixed, and an unbounded cache is disqualifying regardless of model size.

And long-horizon streaming cares, because attention has no notion of a bounded working set, so an agent running for hours accumulates cache indefinitely.

If your workload is none of these, the interest in this path is intellectual rather than operational, which is a perfectly good reason to continue.

Several techniques reduce attention's cost without leaving attention, and they are worth placing because they occupy the middle ground.

Sharing key and value heads across query heads, as in multi-query and grouped-query attention, shrinks the cache by the sharing factor. That is how the 320 KB per token figure was reached; without it the same model would need eight times more. It is a large constant-factor win and the scaling is unchanged.

Cache quantization shrinks the constant again, by up to four times before quality degrades sharply. Also unchanged scaling.

Sliding window attention does change the scaling: each token attends only to the last w tokens, so the cache is bounded by w. What it concedes is exactly what attention was for, since anything outside the window is unreachable except through whatever earlier layers propagated forward.

Attention sinks and similar mechanisms keep a few early tokens permanently, which stabilises the model at long lengths without restoring general recall.

The pattern is that every fix inside attention either preserves scaling and shrinks a constant, or bounds the cache by making distant tokens unreachable. Genuinely constant memory with genuine access to the past needs a different mechanism.

The framing that makes the rest of this path coherent is that a fixed-size state is not a limitation to be engineered around. It is a claim about the data.

A model with a bounded state is asserting that the information in a long sequence which is relevant to future predictions can be summarised in a fixed number of values. For most of what a sequence contains, that is obviously true: the general topic, the register, the syntactic state, the entities in play.

It is obviously false for one thing, and that thing is exact retrieval. If a phone number appeared 40,000 tokens ago and is needed verbatim now, no fixed-size summary reliably holds it, because at some sequence length the number of retrievable details exceeds the state's capacity.

So the question is not whether compression loses information. It does, necessarily. The question is whether what it loses matters for the task.

That is why the empirical results in the last lesson take the shape they do: broad language modelling holds up well, and copying and retrieval do not. It is also why the field converged on hybrids.

Two research lines arrived at parallel-training plus constant-cost-inference from opposite directions, and this path follows both.

One started from attention and removed things. Take softmax attention, replace the softmax with something that permits reordering the matrix products, and the computation can be rewritten so that a fixed-size quantity is maintained instead of an n-by-n matrix. This is linear attention, and the next lesson derives it.

The other started from classical signal processing and added things. Take a linear dynamical system of the kind used in control theory, discretise it, initialise it so it compresses history well, and note that because it is linear and time-invariant the whole sequence can be computed as one convolution, which is parallel. This is the state space model line, from S4 to Mamba, and the lesson after that follows it.

The two lines were understood as distinct for several years. They are not. Mamba-2's structured state space duality shows that a state space model with an appropriately structured transition matrix and a form of linear attention are the same computation seen from two angles.

That convergence is the most satisfying result in this area, and it is where the third lesson ends.

Four things carry through the rest of the path.

Attention has two costs, not one. Quadratic training compute, largely solved by memory-efficient implementations, and a cache that grows linearly with sequence length, which is not solved and cannot be, because it is the mechanism.

The cache is what buys perfect recall. Attention retrieves rather than summarises, so it never loses anything, and never losing anything requires storing everything.

Recurrence trades exactness for constancy. A fixed-size state is 16.8 MB at any length against 343.6 GB at a million tokens, and what it gives up is the guarantee that an arbitrary detail can be retrieved.

And the historical obstacle was trainability, not quality. Recurrent models lost because they could not be trained in parallel, so every modern alternative is organised around recovering that property.

With those in place, the next lesson can start from softmax attention and derive the fixed-size state by removing a single operation.