KV Cache
Cache Flow Statement
1. KV Cache
🎞️One Decode Step
At each step, only the newest token gets computed:
- Its & get appended to the cache.
- Its looks at all cached & , then is dropped — later tokens never need an old .
- Old & never change, since masked attention only lets a token see the past.
🗜️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 GB. Pre-trained model weights eat away GB.
Now we have GB saved for KV cache. Let’s assume our decoder has:
- layers.
- KV heads per layer — query heads don’t count. With GQA/MQA, number of query heads.
- dimensions per head.
- Precision of .
Then each decoded token requires bytes of KV cache.
With each conversation reaching a maximum text length of tokens, each conversation takes away bytes of KV cache.
Thus, we can parallelize 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:
- isn’t all usable: activations & CUDA graphs take some too.
- 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 & 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 & depend on every token before it, and on its position.
Same word after a different history means different & .
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:
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.
🏏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.