KV Cache in LLM Inference Explained

The Redundancy Problem

What is the KV Cache?

During text generation, the model recomputes attention for the entire sequence at every step — including tokens it has already processed. The KV cache solves this by storing the Key and Value tensors from previous tokens so they only need to be computed once. This turns generation from O(n²) recomputation into O(n) incremental work. The tradeoff is memory: for a model like Llama-2 7B serving a 4K-token sequence, the KV cache alone can use about 2 GB of GPU memory per request, making it the primary constraint on how many users a server can handle simultaneously.

Where does the cache live?

Before the why, the where — because "the model stores K and V" leaves out the part that makes the memory arithmetic make sense.

The cache is not a single store bolted onto the model. It lives inside one specific box of the transformer block: the Multi-Head Attention sub-layer.

Why only that one box? Think back to the meeting and the desks.

Most of the block is desk work. LayerNorm, the feed-forward network and both residual adds each take one token's numbers and hand back new numbers for that same token. No other token is involved. Run the step again and you simply redo one small sum off your own sheet — nothing another token produced would have saved you a thing, so there is nothing worth filing away.

Attention is the meeting. Here a token has to hear what every other token said. And what they said never changes: the word cat says exactly the same thing at step 3 as it does at step 300. So write it down once, and on every later step read your notes instead of asking everyone all over again. Those notes are the KV cache.

Now multiply by the floors

One more thing, or the memory numbers will look impossible.

A block is not run once. It is stacked — 96 of them in GPT-3, one on top of the next. Every floor has its own weights, so the same word gets written up differently on each one. Floor 6's notes on cat and floor 7's notes on cat are different documents, and floor 7 cannot read floor 6's cabinet.

So the model does not keep one notebook. It keeps 96, one per floor, and each of them files a new entry for every word that arrives:

That is where the gigabytes come from. Not because any single note is large — a K or V entry is a few hundred numbers — but because there are that many cabinets and every one of them gets a line per word. The next step does the arithmetic.

The Redundancy Problem

How generation uses attention — a concrete example

Imagine the model has generated "The cat" and is about to predict the next word.

To decide what comes next, the model asks a question on behalf of the new token position: "Given everything so far, what should I pay attention to?" This question is the Query (Q).

To answer it, the model needs to check every previous token. Each previous token has two things:

• A Key (K) — a label describing what that token contains (like a book title). "The" has a key, "cat" has a key.
• A Value (V) — the actual information that token carries (like the book's content). "The" has a value, "cat" has a value.

The model compares the Query against all Keys to find which tokens matter, then reads those tokens' Values to produce the output.

The problem: to predict "sat" (the 3rd token), the model already computed K and V for "The" and "cat." Now to predict "on" (the 4th token), it needs K and V for "The", "cat", and "sat." The only new K/V needed is for "sat." But the model doesn't remember the K/V it already computed for "The" and "cat" — it runs the same matrix multiplications again to get the exact same numbers. That's wasted work.

How the waste grows

Without any optimization, every step recomputes everything. Each row below is one generation step — the colored squares are K/V computations performed at that step:

Each step recomputes K/V for all tokens up to that point — not just the new one. The colored area forms a triangle, which is why the total follows the formula n × (n + 1) / 2. For 1000 tokens:

1000 × 1001 / 2 = 500,500 total K/V computations

But with a cache, only 1000 computations are needed (one per token). That's a 500× difference — and it gets worse the longer the sequence.

Why Recomputing Is Pure Waste

K/V vectors for a token depend only on the token itself and the weights of that layer. "The" at position 3 produces the exact same K/V vectors whether it's computed at step 3 or step 3,000. The matrix multiplications are identical. The output is identical. The computation is redundant.

• Step 2: recomputes token 1's K/V pair — already done at step 1
• Step 3: recomputes tokens 1 and 2 — already done at steps 1 and 2
• Step n: recomputes all n−1 prior tokens' K/V pairs, again

This is the problem the KV cache solves.

Explore the simulation to see the computation cost grow with each token generated.

The KV Cache Solution

The KV Cache Solution

The fix is straightforward: compute each token's K/V vectors once, store them, and reuse them on every subsequent step. This is the KV cache.

How It Works

With the cache, every step computes exactly one new K/V pair regardless of context length. Total cost becomes linear — O(n) instead of O(n²).

Why Q Is Not Cached

Attention uses three vectors per token: Query, Key, and Value.

• K and V come from the context — tokens that have already been processed. Once computed, they never change. Cache them.
• Q comes from the current prediction token — the one the model is generating right now. It changes every step. There is nothing to cache.

The cache stores K/V. Q is always freshly computed.

The cache lives at every layer

Remember from the transformer block module: a model like GPT-3 has 96 layers stacked on top of each other. Each layer has its own attention, which means each layer computes its own K and V vectors for every token.

So the KV cache isn't one big storage box — it's one cache per layer. When the model generates a new token, all 96 layers compute and store their K/V for that token. When the next token is generated, all 96 layers read their cached K/V for all previous tokens.

Think of it like a 96-floor building. Each floor (layer) has its own filing cabinet (cache). When a new document (token) arrives, every floor files a copy. When the next document needs context, every floor pulls out all its previous files.

• Llama-2 7B (32 layers): 32 separate K/V caches growing together
• GPT-3 (96 layers): 96 separate K/V caches growing together

This is why KV cache memory scales with both sequence length and number of layers.

Play through the side-by-side simulation — watch how the "without cache" side grows as a triangle while the "with cache" side stays flat at 1 computation per step.

Prefill vs Decode

Prefill vs Decode

When you send a message to ChatGPT, two very different things happen behind the scenes — and they are the same machine, run twice:

Three things in that picture catch people out, so they are marked: the LM head looks at only the last row even though 500 came out of the stack, the generated word skips the tokenizer on its way back in, and decode's matrix has one row rather than 501.

The rest of this step unpacks that picture — first as an analogy, then as a cost comparison, then as a piece of vocabulary history.

Prefill is like a teacher reading an entire essay at once — the GPU processes all your prompt tokens in parallel, computes K/V for every token, and fills the cache in one shot. This is fast because GPUs are built for parallel work.

Decode is like writing a reply one word at a time — the model generates each output token by looking back at the entire KV cache (everything seen so far), producing one token, then repeating. This is slower because the GPU spends most of its time loading the cache from memory, not computing.

They are the same stack, run twice

The two analogies make prefill and decode sound like different machinery. They are not. There is one model, one stack of transformer blocks, one set of weights, and one code path. Between the two phases exactly one thing changes: the seq axis of the tensor going in.

Prefill hands the stack your whole prompt at once — [1, 500, 768] for a 500-token prompt. Decode hands the same stack a single row — [1, 1, 768] — because the other 500 positions are already sitting in the KV cache and never need recomputing.

That one difference is the whole story, and it works through the cost of loading weights rather than the cost of arithmetic. Running the stack means pulling every block's weights out of GPU memory, and that bill is identical either way. Prefill pays it once and gets 500 tokens of work done; decode pays exactly the same bill and gets one token.

So prefill keeps the GPU's math units busy and is limited by compute, while decode leaves them mostly idle and is limited by how fast weights and cache can be read. Same hardware, same model, opposite bottleneck — decided by a single number in the input shape.

Compute-bound and memory-bound are places on a plot

Those two phrases are not loose descriptions. They are positions on the roofline, the standard way of asking whether an operation is limited by arithmetic or by moving bytes — and prefill and decode land in different regions of it.

The GPU & CUDA track works the numbers for exactly this pair in Roofline Model → Prefill vs Decode. Taking one 4096 × 4096 weight matrix and a 512-token prompt:

Read the last two rows together. The FLOPs fall by roughly 500×, but the bytes barely move — you haul the same weight matrix out of memory either way. So the work you get per byte hauled collapses by about 340×, and that is what slides the operation off the compute roof and down onto the bandwidth slope.

It is the same fact this step opened with, now with a number attached: the expensive thing is the trip to memory, and decode makes that trip for a single token.

Why are they called that?

The two names look like a matched pair. They are not — they come from different decades and different fields, and knowing that stops the asymmetry from nagging.

"Prefill" is named after what it leaves behind

Pre (before generation) + fill (the cache). Not after what it does — reading your prompt — but after the leftover.

That sounds like a strange thing to name a phase after, until you notice something: without the cache there is no separate phase to name.

Switch the cache off above. Every step is the same kind of step, just longer than the last — 500 tokens, then 501, then 502. Nothing distinguishes the first step from the tenth, so nobody needs two words.

Switch it on and step 1 becomes a different animal: it is the one that deposits, and every step after it lives off the deposit. Those are now two visibly different kinds of work, and the thing that separates them is the filling. So that is what the name points at.

The cache did not merely make the phase faster. It is the reason the phase exists as a nameable thing at all.

"Decode" is a survivor from an older architecture

This one has nothing to do with the cache, and nothing to do with prefill.

The original 2017 Transformer was an encoder–decoder built for translation: the encoder read the French sentence, and the decoder emitted the English one a token at a time. Generating output step by step was the decoder's whole job, so that activity was called decoding.

GPT-style models are decoder-only — the encoder is gone. The name for the generation loop outlived the architecture that produced it.

Which is why you have already met the word:

All four mean emitting output, never "the opposite of encoding your prompt." The deeper root is information theory, where decoding means recovering a message from a coded signal — here, extracting an actual token sequence from a probability distribution.

TTFT vs TPS

Time to first token (TTFT) measures how long prefill takes. A short prompt prefills quickly. A 10,000-token document takes 100× longer — the model must process every token before it can output anything.

Tokens per second (TPS) measures decode throughput — how fast the model generates after the first token. Longer context doesn't slow decode dramatically, but larger cache means more memory bandwidth consumed per step.

The two metrics are largely independent. A model can have excellent TPS but poor TTFT for long prompts, or vice versa.

In production these two phases don't run in rigid lockstep. A serving engine re-decides at every generation step — every iteration — which waiting requests to prefill and which in-flight ones to decode, then packs them into a single batch. That policy has a name, iteration-level scheduling, and it's the idea the Batching module builds on.

The simulation shows the growing KV cache — this is the cache being read during decode, built during prefill.

Memory Cost

Memory Cost

The KV cache trades computation for memory. But how much memory exactly? Let's build up the formula piece by piece for Llama-2 7B:

Each term corresponds to a real part of the model:

• × 2 (K and V) — we store two vectors per token: one Key and one Value
• × 32 (layers) — each transformer layer has its own cache (remember the 32-floor building from step 2)
• × 32 (heads) — recall from the Attention module: each layer runs multiple attention heads in parallel, each looking for different patterns (syntax, semantics, etc.). Each head stores its own separate K/V pair.
• × 128 (head size) — each K or V vector has 128 numbers. The model's full dimension (4096) is split evenly across heads: 4096 ÷ 32 heads = 128 per head
• × 2 (bytes per number) — each number is stored in FP16 (half precision), which takes 2 bytes of memory

Multiply them all: 2 × 32 × 32 × 128 × 2 = 524,288 bytes ≈ 512 KB per token.

That's half a megabyte for every single token in the conversation.

What this means in practice

• Llama-2 7B at 4,096 tokens: 512 KB × 4,096 = ~2.1 GB per request
• GPT-3 175B (96 layers, 96 heads): ~4.7 MB/token → 4,096 tokens = ~19 GB per request — only ~5% of its ~350 GB FP16 weight footprint at this context, but the ratio climbs fast as context and concurrency grow (see below)
• 10 concurrent users on Llama-2 7B: 2.1 GB × 10 = 21 GB just for KV cache, more than the 14 GB FP16 weights of the model itself

Context Window = Memory

Doubling the context window doubles the KV cache. Quadrupling it quadruples it. The cache grows linearly with context — while attention's own compute is quadratic in sequence length (Flash Attention cuts attention's memory traffic, not its FLOP count).

• 4K context → 2.1 GB (Llama-2 7B)
• 32K context → 16.8 GB — already larger than the 14 GB FP16 weights
• 128K context → 67 GB on one user's request — nearly 5× the 14 GB FP16 weight footprint of Llama-2 7B itself. Long context flips the cost ratio: cache, not weights, dominates HBM (High Bandwidth Memory)

This is why 128K context models need massive GPU clusters: the memory isn't for compute, it's for the cache.

The simulation shows the cache growing token by token — each block is one more token's K/V pair stored in memory.

GQA: Shrinking the Cache

GQA: Shrinking the Cache

From the previous step, we know the KV cache stores a K/V pair per head. More heads = more cache memory. Can we reduce the number of K/V pairs without losing quality?

The key idea: share K/V across query heads

In standard attention, every Query head (Q) has its own dedicated Key and Value heads (K/V). But what if multiple Q heads shared the same K/V?

In the diagram above, pink squares are Query heads (top row) and green squares are K/V heads (bottom row). The lines show which Q heads read from which K/V:

MHA — Multi-Head Attention (standard): Each Q head gets its own K/V — one-to-one. 8 Q heads = 8 K/V pairs. Full expressiveness, but the cache is large.

MQA — Multi-Query Attention: All Q heads share one K/V pair. The cache shrinks 8× — but all heads see the exact same Key/Value information. It's like 8 students all sharing one textbook — they all read the same page, so they all think the same way. The model loses the ability to look at the input from different angles, and quality drops.

GQA — Grouped-Query Attention (modern): The fix for MQA's problem. Instead of forcing all heads to share one K/V, split them into small groups. Each group of 4 Q heads shares one K/V pair. Now there are 2 different K/V pairs — so the model still has 2 different perspectives on the input, not just 1. It's like splitting 8 students into 2 study groups of 4, each group with its own textbook. Each group still shares, but different groups read different material — preserving diversity while using far fewer books than giving one to each student.

In Practice

GQA is no longer a technique some models adopt. It is the floor. Every current open-weight family ships it — Llama 3 and 4 at every size, Mistral, Mixtral, Qwen, Gemma, Phi, Command R. MHA survives only in models that predate the idea, and MQA lost outright: it saved a little more memory than GQA and gave up too much quality to be worth it.

Llama-2 is the last generation where the choice was visible inside one family — 7B and 13B were MHA, and only 70B used GQA, with 8 query heads per K/V head. By Llama 3 even the 8B uses it.

An 8× cache reduction means 8× more concurrent users on the same hardware, or 8× longer context at the same memory budget. That is why the argument ended.

Where it goes after GQA

Sharing K/V heads is one lever on cache size. Two others matter now, and both come up constantly in serving work.

Compress instead of share — MLA. DeepSeek's Multi-head Latent Attention (V2, V3, R1) projects K and V down into one small shared latent vector and reconstructs each head's view on the fly. The cache holds the latent rather than the heads, so it gets below what GQA reaches without forcing every head to read identical keys. This is production machinery, not a paper: SGLang ships a Blackwell attention backend built specifically for MLA.

Stop the cache growing at all — hybrid layers. Models that interleave attention with linear-attention or state-space layers give those layers a fixed-size state instead of one that grows with every token. That bends the growth curve rather than shrinking the constant in front of it — see gated DeltaNet's erase and write gates and per-head hybrid attention.

The cache also does not have to be uniform. Budgets can be set per head instead of per model, and entries can be pruned once they stop earning their space.

GQA is still the right first one to understand. Every technique above is answering the question GQA asked first — how much of this cache do you actually need?

The simulation shows the standard side-by-side cache — imagine the "with cache" blocks compressed 8× for a GQA model.

KV Cache in Production

KV Cache in Production

The KV cache solves the computation problem but creates a memory management problem. Production serving systems spend enormous engineering effort on this cache.

Batch Size vs Context Length

GPU memory is finite. More cache per request = fewer concurrent requests. Both grids below use the same total GPU memory:

Serving providers must choose: many short conversations or few long conversations on the same hardware. This is the central serving tradeoff — throughput is maximized by batching, but batch size is constrained by cache memory per request.

KV Cache Quantization

Model weights are often quantized (FP16 → INT8). The KV cache can be quantized independently — shrinking the bytes per number stored in the cache:

KV quantization is one of the highest-leverage memory reductions because for long-context requests, the cache can be larger than the model weights themselves.

Eviction Policies

When cache memory fills up, something must be dropped. Toggle between strategies to see which tokens survive:

Each strategy has tradeoffs — "drop oldest" is simple but loses early context, "drop least-attended" is smarter but requires tracking attention, and "sliding window" (used in Mistral) is the most efficient but strictly limits how far back the model can look.

Memory-Bandwidth vs Compute

During decode, the GPU does two things: load the KV cache from memory and compute the attention math. Which one is the bottleneck depends on batch size:

With few requests, the GPU finishes computing quickly but spends most time waiting for cache data to arrive from memory. With many requests, the loading cost is shared — the GPU stays busy computing instead of waiting. This is why batching improves throughput.

Flash Attention

To understand Flash Attention, you need to know that a GPU has two types of memory:

• HBM (High Bandwidth Memory) — the GPU's main memory (e.g., 80 GB on an A100). Large but relatively slow to access. This is where the KV cache lives.
• SRAM — a tiny, ultra-fast scratchpad inside the GPU's compute cores (e.g., 20 MB on an A100). Data here can be read instantly, but there's very little of it.

The problem: standard attention loads the entire KV cache from HBM into SRAM, computes the scores, writes them back to HBM, loads them again for softmax, writes again... lots of back-and-forth between slow HBM and fast SRAM.

Flash Attention fixes this by computing attention in small tiles:

Instead of loading the entire cache at once (left), Flash Attention processes one tile at a time (right). Click the KV blocks on the right side to see: only one piece moves from HBM to SRAM at a time, gets computed, then the next piece takes its place. Each piece makes one round trip instead of multiple.

The result: 2–5× faster attention, much less memory for intermediate results. The KV cache still exists — Flash Attention just reads it more efficiently, like reading a book one chapter at a time instead of photocopying the entire book first.