LLM Inference: KV Caching

Ask a language model for a long answer. Without a cache, each new token makes it go back over the answer so far. By the end, it is doing work it did hundreds of tokens ago.

The KV cache is the fix. It is the first optimisation anyone serving an LLM turns on, and without it nothing you use today would be affordable. It is also the reason a GPU runs out of memory long before it runs out of compute.

First, what K and V are

Attention is the operation where a token decides which earlier tokens matter to it. Every token gets projected into three vectors:

• Q, the query. What this token is looking for.
• K, the key. What each token advertises about itself, so others can find it.
• V, the value. What a token contributes once someone attends to it.

The operation is a lookup with soft matching:

Attention(Q, K, V) = softmax( Q Kᵀ / √d ) V

Q Kᵀ scores the current token's query against every earlier token's key. The softmax turns those scores into weights. Those weights then mix the values. So K and V describe the past, and Q describes the token being generated right now.

That asymmetry is the whole trick. Q changes on every step and is thrown away. K and V belong to tokens that already exist and never change again, because attention is causal and nothing arriving later alters what came before.

What generation costs without a cache

A transformer generates one token at a time, and each new token attends to every token before it. To produce token 100, the model needs K and V for tokens 1 through 99, at every layer.

The naive implementation has no memory between steps. So it feeds the whole sequence back in, projects all of it into K and V again, and discards everything except the last position.

step 1:  [The]                        → compute K,V for 1 token
step 2:  [The, capital]               → compute K,V for 2 tokens
step 3:  [The, capital, of]           → compute K,V for 3 tokens
step 4:  [The, capital, of, France]   → compute K,V for 4 tokens

The simple count is 1 + 2 + 3 + ... + n: every step runs an ever-longer sequence. Full attention is more expensive still, because it also recomputes attention across each of those prefixes. The old tokens keep getting worked over even though nothing about them has changed.

That is what the KV cache fixes: stop recomputing K and V for tokens that have not changed.

The fix

Keep the K and V tensors as you go, one set per layer, and feed the model only the newest token.

step 1:  [The]      → compute K,V for "The",     append to cache
step 2:  [capital]  → compute K,V for "capital", append to cache
step 3:  [of]       → compute K,V for "of",      append to cache

KV caching stops the model from recomputing the earlier tokens’ keys and values at every step. The new token must still attend over the cached history, so full-attention decode work grows with context length. But the cache removes the redundant prefix computation that otherwise dominates generation. With a fixed sliding-attention window, even that remaining attention work is bounded.

The code below is the textbook version: a Python loop calling transformers one token at a time, where the cache is a single argument. That is not how anything is served in production. Real inference runs on an engine, vLLM or SGLang or TensorRT-LLM, and everything later in this essay, paged attention and prefix caching included, lives in the engine rather than in transformers. The loop is here because it isolates the mechanism, not because it resembles a serving stack.

@torch.no_grad()
def generate(prompt_ids, new_tokens, use_cache):
    ids, past = prompt_ids, None
    for _ in range(new_tokens):
        if use_cache and past is not None:
            out = model(ids[:, -1:], past_key_values=past, use_cache=True)
        else:
            out = model(ids, use_cache=use_cache)
        past = out.past_key_values if use_cache else None
        ids = torch.cat([ids, out.logits[:, -1:].argmax(-1)], dim=-1)
    return ids

I ran that against GPT-2 (124M), fp32, on CPU, from a 64 token prompt, greedy decoding, timing both paths back to back and reporting the median of three runs per cell. Small model, no GPU. I later ran the same benchmark on a rented GPU, and neither the absolute times nor the shape survived the move. That is the next section.

Each row doubles the output length, so the two vs previous row columns show what one doubling costs:

The table shows the shape of this particular run, not a law about attention. On this small CPU model, cached time almost doubles as output doubles. The new query still looks across a longer and longer cache; at these lengths, the rest of the per-token work is what dominates the clock. The uncached path gets expensive faster because it does that work and goes back through the prefix.

That is why the speedup column climbs from 3.9× to 12.8× in this run rather than holding steady. It is not a fixed multiplier bolted onto the same calculation. The cache removes a growing pile of repeated work as the answer gets longer.

The same benchmark on a GPU

I reran the same script on a rented NVIDIA L40S, changing one thing at a time:

Move GPT-2 from CPU to GPU with nothing else changed and the 512 token speedup falls from 12.8× to 1.1×. The cache did not get worse. The GPU made the expensive path cheap, so there was less left to save: uncached generation dropped from 50.61s to 3.32s, while cached generation barely moved, 3.96s to 3.12s.

Look at that second pair. A cached decode step is one token through the model, and the GPU is barely faster at it than the CPU was, because hardly any of those milliseconds are arithmetic. They are the fixed cost of asking: Python, kernel launches, pulling the weights out of memory. A faster card does not help with any of that.

Llama 8B recovers some of it, because it is large enough for the arithmetic to matter again. Its speedup then climbs with output length exactly as the CPU run's did: 1.8× at 512 tokens, 2.6× at 1024, 4.5× at 2048. I did not measure past 2048, and the trend was still rising there.

So the 12.8× above is not a number to carry anywhere. The direction transfers: caching saves more the longer the output runs. How much it saves depends on your hardware and your model, and on a fast GPU with short outputs it is less than you would guess.

What the cache costs

The cache lives in GPU memory, and its size is fixed by the model's shape and how long the conversation is:

def kv_cache_bytes(layers, kv_heads, head_dim, seq_len, batch=1, dtype_bytes=2):
    # 2 = one tensor for K, one for V
    return 2 * layers * kv_heads * head_dim * seq_len * batch * dtype_bytes

seq_len is prompt plus everything generated so far, because that is what the cache holds. It grows by one every decode step, so a cache bill is never fixed per request. It climbs as the answer gets longer.

Setting seq_len to each model's full context window gives the worst case, one conversation that has filled the model:

Llama-3 serves twice Llama-2's context for half the cache. Grouped-query attention is why that longer context needs less cache memory: keep all 32 query heads, but let groups of four share one key and value head. Each query head still attends its own way; there are four times fewer things to store.

Hold the context fixed to see what that is worth. Mistral serves 32K for 4 GB. Build the same model with multi-head attention instead and that same 32K conversation costs 16 GB, against roughly 14 GB of fp16 weights. The cache would outweigh the model. Long context did not arrive because memory got cheaper. It arrived because architectures stopped caching so much per token.

Capping the window instead of shrinking the rows

Grouped-query attention makes each token cheaper to keep. Sliding window attention changes how many tokens you keep at all.

Under a sliding window, a token attends only to the last W tokens rather than to everything before it. Older entries fall out of the cache, so seq_len in the formula stops being the conversation length and becomes min(conversation, W). The cache stops growing once the window fills.

Mistral-7B-v0.1 shipped with a 4096 token window against a 32K context, which puts its cache at 0.5 GB rather than the 4 GB in the table above, an eightfold difference from one config value. The instruct model at v0.3 sets the window to null and pays the full 4 GB.

That is why the row above names a version. Two checkpoints of the same architecture, the same parameter count, the same advertised context, and caches that differ by 8×. Reading sliding_window out of config.json tells you more about what a model will cost to serve than its parameter count does.

The cost is real: tokens outside the window are gone, and the model cannot attend to them. Long-range recall is what buys the memory back.

The formula is worth checking rather than trusting. I read the tensors GPT-2 retains during generation and compared them against what the arithmetic predicts:

Exact at every checkpoint, flat at 0.0703 MB per token.

I repeated the check on Llama 3.1 8B, grouped-query rather than multi-head, fp16 rather than fp32, on a GPU rather than a CPU, and got the same answer: measured matches formula exactly at all four checkpoints, flat at 128 KiB per token. The cache is one of the few things in a serving stack you can size on paper and be right about.

The trade you made

A KV cache does not make inference cheap. It trades repeated computation for memory that has to stay alive for the whole conversation. The model still does work on every decode step, but the cache is now a second bill, paid in gigabytes for every live request.

Those two resources fail differently, and that is the whole point. Compute is elastic. A busy GPU makes everyone slower, the queue lengthens, latency degrades, and the system keeps serving. Memory is not elastic. It fits or it does not. A server with no room left refuses the next session outright.

One number decides how many people can use your product at once: the memory left after the weights, divided by one conversation's cache.

On an 80GB card holding a 16GB model, that is 64GB of headroom:

Whoever picked the attention shape set that ceiling, months before anyone wrote a serving config, and no amount of tuning moves it.

Spending that memory well

Once memory is the binding constraint, that is where the engineering goes. Three techniques, and they build on each other: stop wasting the memory you allocate, then stop allocating memory you already have elsewhere, then make sure requests land where that memory lives.

Paged attention

You are holding two facts at once. The cache has to grow as the conversation does, and nobody knows how long the answer will be until it is finished.

The simple allocator handles that by reserving a contiguous slab per sequence, big enough for the longest answer it is permitted to produce. It works, and it wastes almost all of it. Most answers stop far short of their cap, so the tail of every slab is held and never touched. Worse, the leftovers are the wrong shape: you have plenty of memory free, in fragments too small and too scattered for the next sequence to use. You run out of memory with memory to spare.

vLLM took the fix from operating systems. Stop insisting the cache is contiguous.

Chop it into fixed-size blocks, each holding a fixed number of tokens. Give every sequence a block table mapping its logical positions to whichever physical blocks it happens to own:

logical position   0-15   16-31   32-47
sequence A     →  block 3  block 7  block 1
sequence B     →  block 2  block 9

free list      →  [0, 4, 5, 6, 8, 10, ...]

A sequence's blocks are scattered and nothing cares, because attention reads them through the table. The allocator hands out a block when the sequence reaches it, so the unknown final length stops being a problem you have to solve in advance. The only waste left is the unfilled remainder of the last block, which is a few tokens rather than a few thousand.

That is virtual memory, applied to attention. And like virtual memory, you get something beyond tidiness: once a block is a first-class object rather than an offset into somebody's slab, two sequences can point at the same one. Identical prefixes stop needing two copies, and a block only gets duplicated when one of them writes.

Prefix caching runs on exactly that machinery.

Prefix caching

Everything so far treats the cache as private to one generation. Often it should not be. Take a roleplay session in a sales training product: the system prompt, the persona the agent is playing, and the scenario context are byte-for-byte identical on every turn of that conversation. Only the newest exchange differs.

If the engine hashes prefixes and reuses matching blocks, turn two skips prefill for everything up to the first point of divergence. On early turns that shared prefix is most of the tokens.

The catch is that it demands an exact match from position zero, because attention state at position N depends on every token before it. One different character at the start and nothing downstream can be reused.

One practical consequence follows. Suppose your system prompt opens like this:

Current time: 2026-08-21 14:32:07
You are playing a hesitant customer evaluating a term insurance plan.
...

That timestamp changes every request. Position zero differs, so the hash differs, so not one block of that long, otherwise identical prompt can be reused and every request pays full prefill. Move the timestamp to the end, after everything stable, and the whole prompt above it becomes shareable. A stable prompt prefix is a performance feature, and the people writing prompts have no idea they are making a serving decision.

Cache-aware routing

Everything above assumes one machine. You will not be running one machine.

The cache is local to the box that built it. It is GPU memory on one replica, and no other replica can see it. So the second turn of a conversation only hits a warm cache if it lands on the same replica that served the first turn.

Default load balancing has no idea any of this is happening. Round-robin and least-connections optimise for spreading load, which is the wrong objective here, because it spreads a conversation across the fleet. On eight replicas, a session that should hit a warm cache every turn hits it roughly one turn in eight.

The failure mode is nasty because nothing looks broken. No errors, no alerts, the cache hit rate on each replica is low and nobody knows what it should be. You built the shared prefix right, the engine supports prefix caching, the feature is enabled, and you get an eighth of the benefit.

The fix is cache-aware routing: route on cache locality rather than connection count, sending a session back to the replica that already holds its prefix. So prefix caching is only half a serving-engine feature. The other half lives in the load balancer, and the two halves sit with different people.

For a multi-turn product this is the difference between the optimisation working and the optimisation existing. A roleplay session is the unit that should stick to one replica: same system prompt, same persona, same scenario, ten turns, all of it reusable and none of it reused if turn two goes somewhere else.

Prompt caching, the same thing with a bill

Everything above is a decision about memory you own. Call a model over an API and you own none of it. The paging and the routing belong to somebody else, and you get the same mechanism, now with a price list.

Prefix caching and prompt caching are not the same thing. Prefix caching is the engine feature from the section above. It is free, it happens on its own, and an entry lasts until the allocator needs the space. Prompt caching is a paid product built on that capability. It has a stated lifetime, a minimum size, and two prices: one to put a prefix into the cache and another to read it back. OpenAI does it for you automatically. Anthropic makes you opt in and mark the reusable span yourself.

What carries over is the matching rule. The cache matches from the first token forward, so the first thing that differs between two requests ends the reuse, and everything after it gets recomputed.

That turns how you assemble a prompt into a cost decision. Picture the support desk for a hardware company. Every incoming question gets answered against the same policy handbook: refund windows, warranty terms, escalation paths, about nine pages of it, or 5,144 tokens. The handbook is identical on every request. The question is different on every request. Nothing else varies.

You have two pieces and two fields to put them in, which gives four arrangements:

A   user:   [question][handbook]
B   user:   [handbook][question]
C   system: [handbook]            user: [question]
D   system: [question]            user: [handbook]

Eight requests each, same eight questions in the same order, same token count. How many of the seven requests that could have read from cache actually did:

A and D never cache on any model. Both lead with the question, so no two requests share a prefix. D is the interesting one: it puts the question in the system field, and that saves it nothing.

B is where the models disagree. Leading with the handbook inside the user message works on the two older models and does nothing at all on GPT-5.6, which read from cache on none of the eight requests. A separate check confirmed the boundary: the same handbook caches on GPT-5.6 when it sits in the system field and not when it sits at the head of a user message.

C works everywhere. Put the fixed document in the system field and the varying question in the user message.

C is the arrangement most people would reach for anyway, by instinct rather than by reasoning. The rule underneath it is that static text goes first. Learn the rule rather than the arrangement, because the next prompt will have more than two pieces in it.

On GPT-5.6 that gap is expensive. Column C bills at 0.25x what the same eight requests cost with no caching, and the other three bill at 1.25x, which is more than not caching at all: every request writes a fresh entry at 1.25x the input rate and nothing ever reads it back.

Caching does not start until the prompt is long enough

OpenAI documents a minimum number of tokens before caching happens at all: 1,024 on GPT-5.6 and later, and 2,048 on earlier models. So I checked that published number against the models I was actually calling.

GPT-5.4 sits where the documentation says. GPT-4o starts caching at about half that, so it is worth checking against the model you actually call.

When caching will not happen

Six ways to get nothing. The first four are measured above. The last two are documented behaviour I did not test:

• Anything that changes sits ahead of the fixed part. Columns A and D.
• The fixed part sits inside a user message instead of the system field. Column B on GPT-5.6.
• The prompt is shorter than that model's minimum.
• Requests scatter across machines. The same prompt sent eight times to GPT-4o read from cache on 3 of 7 requests with no prompt_cache_key, and 7 of 7 with one. The label is a hint rather than a guarantee: GPT-5.4 hit 7 of 7 either way, because routing was never its problem.
• The tool list changes, or serialises in a different order between requests.
• The model, the response schema, or the reasoning effort changes. Each is part of the cache key.

Every one of those fails the same way. No error, no warning, correct answers, and a larger bill.

Running this yourself

I produced every figure in this essay with the scripts below, and you can rerun them.

kv_cache_size.py is arithmetic and nothing else. It does not load or download any model. It evaluates the formula above against published config values for those three architectures, then divides free memory by the result to get the concurrency table. Every figure in the two tables above comes from it.

kv_cache_timing.py is the benchmark. It defaults to GPT-2 on CPU, which is the first table, and takes --model, --device and --dtype for the L40S runs in the second. It generates with and without the cache at each output length, three times per cell, and reports the median.

kv_cache_measured.py produces the validation table. It reads the K and V tensors the model holds and compares them to the formula.

Those three are short enough to read before running, and they make the cache's memory cost and the avoided recomputation checkable in about a minute rather than taken on trust.

The prompt caching numbers come from three more, and these are different in a way worth stating. They call a hosted API, so they need a key, a network, and about a dollar. Everything above runs offline and free.

prompt_cache_placement.py produces the arrangement table. It sends the same eight questions against the same handbook four times over, assembling the request a different way each round, and reads the cache hits and the token accounting out of each response.

prompt_cache_floor.py slices the handbook to exact token counts and finds where each model starts caching.

prompt_cache_routing.py runs the same prompt repeatedly with and without prompt_cache_key.

Two details in there cost me a run each, and both would have produced numbers that looked fine. Every run prepends a random nonce to the handbook, because otherwise the first request reads an entry the previous run left behind and scores a hit it did not earn. And the floor sweep gives every slice its own nonce, because a 512 token slice is a byte-for-byte prefix of the 1,024 token one, so without it the short slices warm the long ones and every threshold after the first is wrong.

What the cache cannot fix

The cache removed the recomputation. The other problem it leaves untouched, and that one is harder.

Generation is still one token per forward pass. Token 101 cannot be computed until token 100 exists, because the model has to know what it just said before deciding what comes next. That dependency is the definition of autoregressive generation, and no caching strategy touches it.

Decode leaves the GPU doing what it is worst at: a wide parallel machine running a sequential loop, one token at a time, waiting on memory bandwidth more than it does arithmetic.

You cannot make generation parallel. You can make verification parallel, and that is enough.

That is the next essay.