Why each next word stays cheap to generate. · Source

To add one word, it should reread the whole chat. It doesn't.

A chatbot streams words almost as fast as you can read them. But to choose each next word, a model is built to look back over everything said so far. Do that from scratch every single word, and a long conversation would crawl. It doesn't crawl — it pours. The trick that keeps it pouring is the whole story here.

Each new word re-reads every word before it. It piles up.

\sum_{t=1}^{n} t = \frac{n(n+1)}{2} \approx \frac{n^2}{2}

A model writes one word at a time, and to pick each one it looks back across the whole prefix. Word 2 re-reads 1, word 100 re-reads 99, word 1000 re-reads 999. Like a switchboard re-patched by hand for every call: the same wiring laid down again and again. Add up all that rework and the cost climbs with the square of the length — double the chat, quadruple the work.

But the past never changes. So why recompute it?

k_j = x_j W_K, \qquad v_j = x_j W_V

When the model turns an earlier word into the two things attention needs — a Key and a Value — those depend only on that word. Words added later can't reach back and alter them. Like a handprint pressed into wet cement: the moment it sets, it's fixed for good. Compute it once, and you're done with it.

So save them. Keep a running table of Keys and Values.

\mathrm{Attn} = \mathrm{softmax}\!\left(\frac{q_t\,K_{1:t}^{\top}}{\sqrt{d}}\right) V_{1:t}

Don't redo the past — store it. Every Key and Value the model computes drops into a growing table. To write the next word, it forms one fresh Query and looks it up against that whole saved table. Like a chef's mise en place: prep every ingredient once, then just reach for what you need. That table is the KV cache.

Now each new word is cheap: encode one, glance at the rest.

\underbrace{O(d^2)}_{\text{one new word}} + \underbrace{O(t\,d)}_{\text{the glance}} \;\ll\; \underbrace{O(t\,d^2)}_{\text{re-encode all } t}

With the table saved, adding a word costs almost nothing. The model encodes just that one word — a flat cost, however long the chat — then takes a quick glance across the cached rows. Like paving a road: you don't re-lay the miles behind you, you add fresh asphalt only at the leading edge. The expensive re-encoding of the whole prefix is simply gone.

The catch: that table only grows. Memory is the new bill.

\text{cache bytes} = 2 \cdot L \cdot n \cdot d_{\text{model}} \cdot b

You bought speed with space. The cache stores two vectors for every layer, for every word so far — and it only swells as the chat goes on. For long contexts it balloons into gigabytes, and that, not compute, becomes the wall. Like a hiker who never sets anything down: the notes that keep you fast also pile onto your back, step after step.

Read the prompt once. Then stream — one cheap word at a time.

That's the KV cache: trade memory for time, so the past is never recomputed. It splits the work in two — read your whole prompt in one parallel pass to fill the table, then stream out each word by adding a single row and glancing back. Like a freight train: you don't rebuild it to go farther — you couple one more car and roll on.

It can add to its memory. It can never revise it.

🌱 The cache is append-only. Every word the model has seen is fixed the instant it lands — kept perfectly, never rewritten, like a record cut once and only ever replayed. And each new thought must still glance back across all of it. So is a memory you can only add to — never edit, never shorten — a kind of freedom, or a weight that can only grow?