The KV Cache

At generation time, keys and values for past tokens do not change. Servers store them in a KV cache so each new token only computes one new row of scores against the stored keys.

That is why the first token of a long prompt is slow (prefill: attend over the whole prompt) and later tokens are faster (decode: attend to the cache plus the new token) — until the cache is huge and memory-bound.

Agent loops that resend a 20k-token transcript from scratch pay prefill again if the prefix is not cached. A stable pinned prefix is a performance feature, not just a safety feature. If you edit a token in the middle of the prompt, every key after that is invalid. That is why “edit the system prompt every turn” kills cache hits.

This lesson is the cache. The next two lessons are the window as a suitcase, and prefill vs decode as a latency picture. They are the same machine from three sides.

A wrong picture

A wrong picture is: “the cache stores the answer.” It stores keys and values for tokens already processed: lists of numbers from each layer and head. It does not store the user’s goal as English.

Another wrong picture is: “decode is free.” Each new token still scores against the growing cache. Long traces are a memory bill, not only a token bill. Cache size grows with layers × heads × sequence × key width. Grouped-query attention (multi-head lesson) exists partly to shrink this.

A third wrong picture is: “I can rewrite the spec every turn and still hit the cache.” Byte-for-byte prefix stability is the hit. A timestamp in the system spec, a shuffled tool list, a comma change — any of those can miss.

Prefill writes, decode appends

Prefill: run every prompt token through the stack. Write K and V for each position into the cache. Produce logits for the next id. Cost grows with prompt length (and with n² attention unless the kernel is clever).

Decode: take the newly chosen id, embed it, run it through the stack as one position, score against all cached keys, append the new K/V, sample the next id. Repeat until stop.

If you change token 5 of a 5,000-token prompt, positions 5…4999 must be recomputed. Positions 0…4 could stay. In practice many stacks drop the whole suffix after the edit. Put volatile text at the end so the long prefix can stay cached.

A tiny example in words

Toy: keys are the token vectors. Prefill three prompt vectors. Cache length 3. Decode one new vector: dots against the three stored keys, then append. Cache length 4. You did not rebuild the prompt keys.

That is the whole idea, without layers and heads. Production is this per layer, per head, with larger lists of numbers.

Store keys, then append one

Lists of numbers. Print cache length and scores. No extra libraries.

Run to execute this in your browser. Nothing is sent to a server.

Prefill writes the cache. Decode only appends. Second decode scores against four keys, including the first generated vector. That growing list is why very long generations become memory-bound.

If you mutated prompt[1] after prefill, this toy would not update past_keys[1]. That stale key is the bug a real cache would have if you edited the middle and forgot to invalidate. Real servers invalidate. You still pay to rebuild.

What blows the cache

• Spec text that includes “today’s date” rewritten every call
• Tool schemas serialized in random key order
• Injecting a new “remember:” line at the front
• Summaries that replace the head instead of the tail
• Multi-agent copies of the full transcript as a new prefix

Keep the system spec byte-for-byte stable across turns. Put volatile stuff (the latest observation) at the end. If you must summarize, replace the tail, not the pinned head.

Cache is also why streaming UIs feel fast after the first token: you are watching decode. They do not shrink prefill. A 100k-token “just in case” pack still makes every turn feel like a cold start if the prefix cannot be reused.

Common mistakes

Putting a request id or a wall-clock timestamp in the system spec every turn. The prefix never matches. Prefill runs in full. Put clocks in the tail.

Serializing tool schemas with unsorted keys. One extra space, one shuffled field, cache miss. Canonicalize the schema bytes.

Summarizing by rewriting the spec (“here is a shorter policy”). You just invalidated every cached key after token 0. Summarize history. Pin the spec as a frozen string.

Assuming a multi-agent crew can each send a unique 8k spec and still share a cache. They cannot, unless the bytes match. Share one pin.

Watching later tokens crawl and adding more prompt “for context.” You made the cache longer. Shorten. The memory bill is layers × heads × sequence × width, every decode step.

How agents use this

Keep the system spec byte-for-byte stable across turns so the prefix can be cached. Put volatile stuff at the end. If you must summarize, do it in a way that replaces the tail, not the pinned head.

Measure: if every turn’s first token is slow, you are probably missing the cache (or the prompt is huge). If later tokens crawl, the cache may be huge — shorten the sequence.

• Stable head: spec and tool schemas frozen as bytes.
• Volatile tail: latest observation last.
• Edits: middle edits invalidate the suffix.
• Memory bill: layers × heads × sequence × width.
• Streaming: does not erase prefill.

Tip:Prefill cost is why a 100k-token “just in case” pack makes every turn feel like a cold start. Streaming UIs do not change that. They only change when bytes arrive.