KV caching and prefix caching

#Attention in one equation

At every layer, each token $j$ is projected into a query $q_j$, a key $k_j$, and a value $v_j$. In a causal (decoder-only) model, token $i$ attends only to itself and the tokens before it:

The property everything else rests on is this: $k_j$ and $v_j$ depend only on tokens $1$ through $j$ and on position $j$. Tokens that come later never change them. So once computed, they stay valid for as long as nothing before them changes.

#The KV cache: compute each token once

Generation has two phases:

• Prefill. The whole prompt is processed in parallel, producing $k_j, v_j$ for every prompt token in every layer. This phase is compute-bound.
• Decode. Output is produced one token at a time. Each new token computes only its own $q, k, v$ and attends over the stored keys and values. This phase is memory-bandwidth-bound.

Storing those keys and values is the KV cache. Without it, every generated token would redo the entire prompt.

The cache is not free. Per token it holds

where the leading 2 counts keys and values, and $b$ is the bytes per value (2 in bf16). For Qwen3.6-27B (16 full-attention layers, 4 KV heads, head dimension 256, bf16) that’s $2 \times 16 \times 4 \times 256 \times 2 = 65{,}536$ bytes, or 64 KiB per token, and 2 GiB for a single 32K-token context. The model’s other 48 layers use linear attention, which keeps a fixed-size state instead of per-token entries; more on that below.

#Prefix caching: reuse across calls

An agent resends its entire message list every turn (see the agent-loop refresher). Serving engines exploit this by keeping the KV cache from earlier requests and reusing it whenever a new prompt starts with the same tokens. SGLang does this with a radix tree over token sequences (RadixAttention); vLLM does it with hashed token blocks. Hosted APIs offer the same idea as “prompt caching.”

Reuse stops at the first token that differs. Every later token’s keys and values were computed with the old token in their past, through all the layers above the first, so they are no longer valid:

previous turn : [ A ][ B ][ C ]
append        : [ A ][ B ][ C ][ D ]    reuse A, B, C  ->  prefill only D
edit middle   : [ A ][ B'][ C ]         reuse A        ->  re-prefill B' AND C
edit start    : [ A'][ B ][ C ]         reuse nothing  ->  re-prefill everything

That’s the whole cost story in one picture. Appending is cheap. An edit costs roughly the number of tokens after the edit point, even when those tokens didn’t change. The paper’s cost metric, prefix-reuse FLOPs (§4.1, Eq. 9), counts exactly this. And because hosted-API prompt caching is also prefix-based, the same geometry shows up on your bill.

#The position wrinkle: RoPE

Most modern LLMs encode position with rotary embeddings (RoPE): queries and keys are rotated by an angle proportional to their position, $k_j = R(j)\,W_k h_j$. Rotations compose,

so moving a cached key to a new position costs one extra rotation. The position part of a stale cache entry is therefore easy to fix. The content part isn’t: $h_j$ was computed with the old prefix. Suffix Cache Reuse (§4.3) re-rotates surviving keys and accepts the content staleness as an approximation.

#Linear-attention layers: a state, not a cache

Linear-attention layers (such as Gated DeltaNet in hybrid models) squeeze the entire history into a fixed-size recurrent state, updated token by token. You can’t delete one token from the middle of such a state. You can only resume from a saved snapshot of the state taken at some earlier point. SGLang saves those snapshots only at request boundaries, which is why hybrid models suffer extra cache misses after edits (Appendix B).

#The takeaway

1. Keys and values depend on everything before them, so caches are valid only for an unchanged prefix.
2. Edit cost scales with how much text comes after the edit, not how big the edit is.
3. Positions can be patched cheaply with RoPE. Content can’t, and that tension is exactly what the paper’s serving section is about.