KV Cache: The Memory Backbone of LLM Serving

How does an LLM write?

One token at a time. Slowly. Like a metronome.

And every new token must be conditioned on everything written before it. That is what attention does (the core Transformer mechanism from earlier topics, in one plain sentence: each token looks back at every previous token and decides which ones to listen to).

So generating token t+1 means running attention over tokens 1…t.

Now imagine doing that naively, from scratch, every step.

At step 1 you process 1 token. At step 2 you re-process tokens 1–2. At step 3, tokens 1–3. By step N you have re-run the whole prefix over and over — O(N²) total work to generate something that is only N tokens long.

So the question becomes

No. They do not.

Because of causal masking (a token can only see itself and its past, never the future), the Key and Value vectors computed for token 3 are identical whether you are generating token 4 or token 4,000. Recomputing them is pure waste.

That observation is the whole reason the KV cache exists:

Without this trick, every chatbot reply would get slower and slower as the conversation grew, and the compute bill would be quadratic. With it, each decode step is cheap and flat: project one new token → append it → attend over the stored history.

The catch: "store the result" means memory. Lots of it. The size of that memory, the speed of reading it, and how you organize it is everything that follows in this topic.

The KV cache is simply

Let's unpack those words.

• Key (K) — what a token advertises: "my topic is this." Future tokens match their question against keys to decide what to listen to.
• Value (V) — what a token actually carries: the information that flows forward once some future token decides to listen to it.
• Per layer — every attention layer keeps its own K and V stack for every token. 32 layers means 32 independent stacks.
• Query (Q) — the new token's question. Only q_t is needed for the current step, and it is used immediately and thrown away — that is why only K and V are cached, not Q.

So one decode step is exactly three moves:

1. Project the new token into q_t, k_t, v_t.
2. Append k_t and v_t to each layer's stack. The cards never change after that.
3. Attend: match q_t against the whole stack — every cached K and V in the layer — then sample the next token.

No old token is ever re-projected. The entire conversation history becomes read-only memory instead of a compute task. That is what turned chat generation from a quadratic nightmare into a linear one — and what quietly moved the bill from the calculator to the warehouse.

How fat is one "card"? A one-line multiplication answers it.

Per token, per layer, you store both K and V, each of shape n_kv_heads × head_dim, and each number costs 2 bytes in FP16:

bytes per token = 2 (K and V) × n_layers × n_kv_heads × head_dim × 2

Now plug in a real model, Llama-3-8B (32 layers, 8 KV heads, head_dim 128, FP16):

2 × 32 × 8 × 128 × 2 = 131,072 bytes ≈ 0.13 MB per token

One token. One card. 131 KB. Now scale it up, brutally:

• 1,000-token chat → 0.13 MB × 1,000 ≈ 0.13 GB
• 2K context → about 0.26 GB
• 100K-token context → about 13 GB — for one conversation
• Llama-2-70B (GQA-8): about 0.31 MB/token → a 128K context ≈ 40 GB for a single sequence

And nobody serves one sequence at a time. Serving means a batch of concurrent users, so multiply the whole thing by batch size — 100 parallel chats is the actual game.

An A100 with 80 GB running a 70B model in FP16 spends ~140 GB on the weights alone across two GPUs before a single cache card. That is exactly why self-hosted 70B servers show a brutal "max context × max concurrency" trade-off: the binding constraint is the cache, not the math.

layers, kv_heads, head_dim = 32, 8, 128   # Llama-3-8B shape
bytes_per_number = 2                       # FP16

per_token = 2 * layers * kv_heads * head_dim * bytes_per_number
print(per_token)                           # 131072 bytes = 0.125 MB per token
print(per_token * 100_000 / 1e9)           # ~13.1 GB for ONE 100K-token sequence
# multiply by batch size for the serving bill

Picture the decode loop from above. Each box is one token's cached pair; every step reads all of them.

code
Copy
 token 1    token 2    token 3     ...     new token t
 ┌────────┐ ┌────────┐ ┌────────┐          ┌─────┐
 │ K₁ V₁  │ │ K₂ V₂  │ │ K₃ V₃  │  ...     │ q_t │──► attend over
 └────────┘ └────────┘ └────────┘          └─────┘   ALL the cards,
   cached     cached     cached              only q     every single step
   (read-only, never recomputed)          computed

And the stack grows with the conversation:

code
Copy
 step 1   [K₁V₁]
 step 2   [K₁V₁][K₂V₂]
 step 3   [K₁V₁][K₂V₂][K₃V₃]
   ...       ▲ every step scans the whole strip, end to end
 step t   [K₁V₁]...[K_tV_t]   ← bytes READ grow linearly with t

That is the punchline hiding in the drawing:

• The compute per step barely changes — always one token's projections.
• The reads per step grow with the context — the entire stack, every step, every layer.

The GPU spends its time fetching cards from memory, not doing arithmetic on them. Keep that picture in mind for the next section — it is the whole economics of LLM serving.

Carry one picture through everything that follows:

Your workaround: a pad of note cards. Every time a message arrives, you write one card:

• front = what the message is about → that is the Key (how you look it up later).
• back = what the message says → that is the Value (what you quote from it).

To write your next sentence you never re-read messages. You fan through the cards. When your own sentence gets posted, you add a card for it. One card per message: written once, read many times. That pad is the KV cache.

Now notice — every engineering trick in this topic is just a policy about the pad:

• Pad too tall to carry? → eviction (throw away cards nobody references).
• Card-writing too slow? → quantization (write in shorthand).
• One card per few messages? → GQA/MLA (thinner cards, shared fronts).
• Cards scattered messily across your desk? → PagedAttention (numbered drawers + one index page).
• Many chats share the same pinned announcement? → prefix caching (photocopy those cards).
• Your bottleneck is the fanning, not the thinking? → that is bandwidth-bound decode.

Whenever a new technique appears below, ask one question: "what does it do to the cards?" If you can answer that, you understand KV-cache serving.

Now the uncomfortable physics lesson.

Per decode step the GPU must touch the entire cache — tens of gigabytes per conversation at long context, read again for every single token — while computing only one token's worth of arithmetic.

Decoding is therefore memory-bandwidth-bound:

throughput ceiling ≈ HBM bandwidth ÷ bytes read per token

HBM (High Bandwidth Memory) is the stack of DRAM sitting right beside the GPU chip — roughly 3 TB/s on H100-class parts. When moving bytes dominates doing math, the fancy tensor cores sit idle. Extra FLOPs buy nothing; extra bandwidth buys everything.

This single fact explains which levers actually raise serving throughput — all of them reduce bytes read or increase reuse per read:

• GQA/MQA (topic 213): fewer KV heads → physically thinner cards → less to read.
• Quantized caches (section 9): 2-bit or FP8 shorthand → 2–8× fewer bytes.
• Bigger batches: the same cached K/V is read once and used for many users' queries in parallel — bytes amortized, arithmetic intensity up. This is why batching is king for serving economics.

It also splits a request into two very different beasts:

• Prefill — processing your long prompt at once, all positions in parallel: compute-bound, FLOPs-heavy.
• Decode — the serial card-fanning loop: bandwidth-bound, FLOPs idle.

That asymmetry motivates everything in sections 7–8: paging to fit more cards, sharing cards across requests, and even putting prefill and decode on different GPU pools (Mooncake, DistServe) because they strain different hardware.

How should the card stack live in GPU memory?

The naive answer: give each sequence one big contiguous buffer, sized to its maximum possible length.

The problem: generations vary wildly. A chat that ends after 200 tokens reserved room for 32K. On a busy server, 60–80% of the reserved cache is wasted — internal fragmentation (half-empty buffers at the end of each sequence) plus external fragmentation (unusable gaps between freed buffers).

So the question becomes

vLLM's PagedAttention (Kwon et al., 2023, arXiv 2309.06180) copied the operating system's virtual-memory playbook:

1. Split cache into fixed-size blocks (say, 16 tokens each) — the rooms.
2. Keep a per-sequence block table mapping logical position → physical block — the hotel index. Sequences no longer need contiguous memory at all.
3. Allocate lazily — hand out another room only when the current one fills.
4. Share blocks when sequences have identical prefixes, with copy-on-write — two beam-search candidates with the same 100-token opening point at one physical block; only when they diverge does a copy happen.

Result: near-zero waste, and 2–4× serving throughput over naive HuggingFace pipelines at the same latency. It is the reason vLLM reshaped the inference stack, and by 2025–2026 paged, block-table KV management is standard in vLLM, SGLang, TensorRT-LLM, and LMDeploy alike.

SGLang added RadixAttention: organize shared blocks in a radix tree keyed by token prefix, so multi-turn chats and agentic calls automatically discover and reuse each other's cached openings — the photocopy shelf from the analogy.

With the stack organized, three patterns around it became production standards in 2024–2026. Each one answers the same question from a different angle:

The biggest unlock is realizing that most tokens in a served request were already processed for somebody else — same system prompt, same uploaded document, same earlier turns. Compute once, hit the stack forever.

Three orthogonal ways to make the cards smaller, fewer, or thinner — all active in production 2024–2026.

1. Eviction / selection — fewer cards. Not all cached tokens matter equally. H2O (arXiv 2306.14048) keeps the "heavy hitter" tokens — those that accumulated the most attention score over time — and drops the rest. StreamingLLM (arXiv 2309.17453) discovered the quirky "attention sink": the first few tokens soak up a lot of attention no matter what, so keeping those plus a sliding window of recent tokens stabilizes unbounded streaming. Newer designs (DSA/NSA, topic 210) push the selection into the architecture itself — the model learns which cards to file.

2. Quantization — shorthand cards. K and V values have skewed, forgiving distributions, so they tolerate tiny bit-widths. KIVI (arXiv 2402.02750) quantizes keys per-channel and values per-token down to 2 bits with near-lossless quality. FP8/INT8 caches are routine — KV quantization is half the reason 128K contexts serve at all on an 8×H100 node. One warning before shipping: cache quantization shifts attention numerics subtly, so test long-context retrieval specifically — aggregate benchmarks hide the damage.

3. Architecture — thinner cards by design. MLA (DeepSeek-V2/V3) compresses K and V into a low-rank latent of ~576 dims per token instead of thousands — GQA-plus shrinkage in one design. Sliding-window layers (Gemma 3, Mistral) bound each layer's stack to the window, keeping only a few global layers full. Mamba-style state-space models (topic 217) go maximalist: no cards at all, just a fixed-size running summary.

When you design or debug a serving stack, these are the checks that actually get used:

• Cache bytes per token first. 2 × layers × kv_heads × head_dim × bytes, then × max context × batch size. If that number exceeds spare HBM, no kernel trick will save you — fix the architecture (GQA/MLA), the numerics (FP8/KIVI), or the paging.
• Watch where the time goes. Prefill minutes vs decode milliseconds-per-token tells you which side (compute vs bandwidth) your workload starves — and whether PD disaggregation or chunked prefill pays.
• Measure hit rates on prefix caching before betting your cost model on it; a cache key that misses is a full prefill in disguise.
• After any eviction or quantization change, run long-context retrieval tests (needle-style, multi-hop) — capacity wins can hide quality cliffs exactly where RAG needs the cards.
• Decode throughput ≈ bandwidth ÷ bytes-read-per-token. Batching, GQA, and quantized caches move the number; a faster matmul does not.

The one-line worldview: in LLM serving, the model is small and the cache is big. Weights are read once per step and amortized across the batch; KV is read per-sequence, per-step, and grows forever until it is paged, shared, shrunk, or offloaded. That is why the topic is called the memory backbone of serving.