Answers · How models work

Why does a transformer need a cache that grows with sequence length?

In shortA transformer stores the key and value for every token it has already seen so later tokens can look back at them, and that store grows with the conversation.

A transformer caches the key and value vectors for every token it has already processed, in every layer, because each new token's attention compares against all of them. The cache therefore holds one entry per token per layer, so its size rises in a straight line with the length of the conversation, and the work needed to read it for each new token rises in the same way.

M(t)=c\,t,\qquad c=\frac{0.5\ \text{MB}}{1000\ \text{tokens}}=0.0005\ \text{MB per token}

Take the store at 0.5 MB for the first thousand tokens. At 8 thousand tokens the conversation is eight times longer, so the store is $0.5 \times 8 = 4.0$ MB. At 64 thousand it is another factor of eight, $4.0 \times 8 = 32$ MB. At 512 thousand it is another factor of eight, $32 \times 8 = 256$ MB. A fixed carried state of 8 MB does none of this: it is 8 MB at 1 thousand tokens and 8 MB at 512 thousand. At the long end the cache is $256/8 = 32$ times the fixed state, for one conversation.

The constant is the whole argument. At 2000 tokens the store is $0.0005 \times 2000 = 1.0$ MB; at 4000 tokens it is $0.0005 \times 4000 = 2.0$ MB. Doubling the tokens doubles the store. Linear growth is not constant, and no amount of fast arithmetic changes the fact that the store has to be held somewhere.

FIG 1

context	store per conversation	conversations in 40,960 MB
1 thousand tokens	0.5 MB	81,920
8 thousand tokens	4.0 MB	10,240
64 thousand tokens	32.0 MB	1,280
512 thousand tokens	256.0 MB	160
fixed state, any length	8 MB	5,120

Read the last column as capacity. At 1 thousand tokens the store is small, so $40{,}960/0.5 = 81{,}920$ conversations fit. At 8 thousand tokens the store is 4 MB and only $40{,}960/4 = 10{,}240$ fit: eight times the context, an eighth of the conversations. At 64 thousand tokens $40{,}960/32 = 1{,}280$ fit, and at 512 thousand only $40{,}960/256 = 160$ . The fixed state holds 5,120 at every one of those lengths. The machine's capacity has become a function of how long people have been talking, which is the operator's problem.

The cache exists because the alternative is recomputation. For each new token the layer makes a query and compares it with stored keys, then mixes the stored values. Without the cache it would recompute keys and values for every previous token at every step, which is more work, not less. So the cache trades recomputation for memory, and the memory it trades for is linear in the number of tokens.

Why one new token is slower at the end

Each new token must consult every entry in the store, not just the newest one. At 512 thousand tokens there are $512{,}000/1000 = 512$ times as many entries as at 1 thousand, so the read is roughly 512 times larger. The arithmetic may be cheap relative to moving the data, which is why time per token climbs roughly with context length and a reply late in a session feels slower than the same reply early on.

The fixed-state guess

The natural guess is that attention is a fixed operation on a fixed-size state, so serving cost should be flat. The weights are fixed, but the per-conversation state is not: it is the concatenation of every previous token's key and value. Recomputing those from scratch for each new token would be worse, so the cache is necessary, but the cache is exactly the thing whose size grows. Nothing in the weights grows; the growth is in the working memory held for each conversation.

The comparison with a carried state can be made exact. Write the look-back layer as a recurrence: $s_t = s_{t-1} + \phi(k_t)v_t^\top$ . Here $s_t$ is the running summary, and it accumulates one contribution per token. That is why it keeps growing in effect: nothing is discarded. Put a decay factor in front of $s_{t-1}$ and the state becomes fixed; that single coefficient is the difference between the two families.

Where the growth can be removed

The growth disappears if the layer is not allowed to look back without limit. Restricting attention to a fixed window caps the store at the window size, and replacing the layer with a recurrence that carries a fixed block removes it entirely. The price is exact recall: a window cannot recover a name from before the window, and a fixed state compresses rather than stores. A hybrid keeps most layers fixed and a few looking back. Two look-back layers out of thirty six scale the growing part of the bill by $2/36 = 1/18$ , so the slope is eighteen times smaller than a pure look-back stack's. That turns a slope that forces short contexts into one that can be absorbed, while the look-back layers still recover exact details when needed.

Worth keeping

At half a million tokens the growing store is 256 megabytes per conversation, while a fixed carried state is 8 megabytes.
On forty gigabytes that is 160 conversations against 5,120 for the fixed state at the long end.
Capping attention to a window or carrying a fixed state removes the growth, at the price of exact recall over everything older.

Where this goes next

This question is one step of Models That Carry a Memory, a course that works through its subject from the beginning. The page that teaches this part of it is Constant Memory Against a Growing Cache, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course