Skip to content

KV Cache

Cache Flow Statement

1. KV Cache

🎞️One Decode Step

At each step, only the newest token gets computed:

  • Its KK & VV get appended to the cache.
  • Its QQ looks at all cached KK & VV, then is dropped — later tokens never need an old QQ.
  • Old KK & VV never change, since masked attention only lets a token see the past.
One decode step, one layer shownKV cache of this layert1K1, V1t2K2, V2t3K3, V3t4K4, V4t5K5, V5t6K6, V6appendNew token t6only this one is computedq6k6v6q6 is used onceand never cachedread K1 to K5 andV1 to V5 from cacheAttention for t6q6 vs K1 to K6, then weighted sum of V1 to V6Output of t6, feeds next layer

🗜️Cache Size Formula

Actually, it is very clearly top-down layered:

  • 2 Lines: K & V each.
  • Layers per line.
  • KV heads per layer.
  • Dimensions per head.
  • Bits per dimension, and 1 byte = 8 bits.

So cache size in bytes: Lines x Layers x Heads x Dimensions x Bits / 8.

Quite often we see terms like FP16, INT8, etc.

Terms’ numbers = how many bits needed for each value stored.

KV Cache’s Roommate 🛌

Not all VRAM can be used by KV cache. In fact, somebody eats up lots of VRAM before KV cache has its share:

Pre-trained model weights.

We can know how much room is left for KV cache only after deducting size of pre-trained model weights.

🔄Concurrent Conversations

Suppose we have an initial VRAM of VV GB. Pre-trained model weights eat away WW GB.

Now we have V−WV - W GB saved for KV cache. Let’s assume our decoder has:

  • LL layers.
  • HkvH_{kv} KV heads per layer — query heads don’t count. With GQA/MQA, Hkv<<<H_{kv} <<< number of query heads.
  • DD dimensions per head.
  • Precision of PP.

Then each decoded token requires C=2×L×Hkv×D×P8=L×Hkv×D×P4C = \frac{2 \times L \times H_{kv} \times D \times P}{8} = \frac{L \times H_{kv} \times D \times P}{4} bytes of KV cache.

With each conversation reaching a maximum text length of TT tokens, each conversation takes away CTCT bytes of KV cache.

Thus, we can parallelize ⌊109⏟1 GB=109 bytes×V−WCT⌋\lfloor \underbrace{10^9}_{\text{1 GB} = 10^9 \text{ bytes}} \times \frac{V - W}{CT} \rfloor conversations at the same time.

We must take floor since a conversation either fits entirely or doesn’t — it has no fraction.

Note “at the same time” means these conversations’ KV cache stays resident in VRAM, not that all of them are computed in the same step.

Reminders:

  • V−WV - W isn’t all usable: activations & CUDA graphs take some too.
  • TT is max length. Real conversations are often shorter, so more can fit in practice.

2. Prefix Cache

KV cache lives inside one request. Prefix cache asks: when a request ends, why throw its KK & VV away?

Keep them, indexed by the tokens they came from. Next request starting with same tokens skips prefill for those:

  • KV cache — within one request: each decoded token skips recomputing earlier ones.
  • Prefix cache — across requests: skip prefill for prompt tokens already seen.

🧬What Counts as a Prefix?

Leading tokens, same order from the very first token. No gaps allowed:

  • A token’s KK & VV depend on every token before it, and on its position.

  • Same word after a different history means different KK & VV.

  • One different token causes everything after it to differ. Like a Trie.

In chat, current turn’s prefix is the previous turn’s finalized system prompt, user message and reply:

Turn 1: cold start123456789101112system + user: prefillreply: decodePrefix cache, across requests:turn 2 starts with the same 12 tokensTurn 2: prefix hit123456789101112131415161718tokens 1 to 12: KV read from cache, no prefillnew userdecodeprefillKV cache, within one request: every decoded token (9 to 12, then 16 to 18)appends its own K and V, so no earlier token is ever recomputed.computed in prefillgenerated by decodeKV served from cache

Real systems cache in fixed-size blocks, so only full blocks of the shared prefix get hit.

🌳One Trunk & Many Branches

Many users share the same system prompt, tools or documents. That trunk’s KV is computed once; every request just points at it.

System prompt + toolsKV computed once, cachedBoth requests point atthe same KV blocksFirst differing token: branches apartUser A: questionprefill, own blocksUser B: questionprefill, own blocksReply Adecode, own blocksReply Bdecode, own blocksSame token after a different history has different KV, so nothing is shared past the fork.

🏏How Hits Are Found

  • vLLM: KV lives in fixed-size blocks. Each full block is hashed together with the hash of the block before it, so a block’s identity = its own tokens + everything before. Lookup walks blocks from the front until the first miss.
  • SGLang: a radix tree over token sequences — longest matching path is the hit.
  • Both: blocks being used carry a reference count. Unused ones linger until memory is needed, then the least recently used go first.
  • Only full blocks count. A partial tail block gets recomputed.

🎯What It Saves

  • Prefill for every hit token — lower TTFT: Time to First Token; less compute.
  • VRAM: shared blocks are stored once, leaving more room for concurrent conversations.
  • Not decode. Each new token still reads the whole KV cache, so that part stays memory-bound.

✍️Writing Prompts That Hit

  • Place stable ones first: system prompt, tool definitions, few-shot examples, long documents.
  • Then concat varying ones last: new user message.
  • One changed token early — say, a timestamp on first line — and everything after it misses.
  • Keep history append-only. Edit, truncate or reorder earlier turns, and prefix breaks right there.
  • Routine agents are the best case: big fixed head, small changing tail.