The KV cache is the single most important data structure in large-language-model serving, and it exists to fix one specific piece of waste. A transformer generates text one token at a time, and each new token attends to every token that came before it. Done naively, that means recomputing the same quantities over and over — work that grows quadratically with the length of the text. The KV cache is the standard cure: store the reusable per-token quantities once, and each step only computes what is genuinely new. This piece builds the idea from first principles — the redundancy it removes, the O(N^2) → O(N) compute saving, the formula for how many bytes it costs per token, and the twist that trading recompute for storage turns decoding into a memory-bandwidth problem. The deeper mechanics — tensor layout, paging, and quantization — live in the companion articles; this is the map you read first.
The problem: generation repeats itself
An autoregressive model produces a sequence by predicting the next token from all the tokens so far, appending it, and repeating. The heart of each step is self-attention. For a token at position i, the model forms a query q_i, and compares it against a key k_j for every earlier position j ≤ i, then mixes the corresponding values v_j weighted by those scores: attn(q_i) = Σ_j softmax(q_i · k_j / √d_k) · v_j.
The keys and values are linear projections of the token embeddings: k_j = W_K x_j and v_j = W_V x_j. Here is the crucial observation hiding in that line: k_j and v_j depend only on token j, not on anything that comes after it. The key and value for the fifth word are the same whether the sequence is five tokens long or five hundred. That stability is the entire foundation the cache is built on.
Life without a cache: the O(N^2) trap
Suppose you keep nothing between steps. To generate token t, attention needs k_j, v_j for all j < t, so you re-run the forward pass over the whole prefix and recompute every past key and value from scratch. Step 1 processes 1 token, step 2 reprocesses 2, step t reprocesses t. Summed over an N-token generation:
work ∝ 1 + 2 + 3 + ... + N
= N(N+1)/2
= O(N^2) token-forward-passesA 1000-token answer would perform roughly half a million token-forward-passes instead of a thousand. The redundancy is total: the projections W_K x_j and W_V x_j produce the identical result each time, burning compute to reconstruct numbers you already had. This is the quadratic wall the cache knocks down.
The fix: store what does not change
The cure follows directly from the observation that k_j and v_j are fixed once token j is seen. Instead of throwing them away, keep them: maintain two running buffers per layer, one holding every key computed so far and one every value. That pair of buffers is the KV cache.
Now a decode step does almost no redundant work. When the model emits a new token, it computes just that token’s key and value — a single projection each — and appends them to the buffers. Attention then reads the whole cache to score the new query against all history. The heavy, repeated recomputation of past keys and values is gone; what remains per step is one new token plus a read of stored history. The model trades a growing pile of recompute for a growing pile of memory — almost always the right trade.
Why keys and values, but not queries
The name is precise: it caches keys and values, not queries, because of how each is used. A key k_j and value v_j for a past token are consulted again on every future step — token 5’s key is dotted against the query of token 6, 7, 8, and so on. They are long-lived and shared across all later steps, so caching them pays off repeatedly.
A query q_t, by contrast, is used exactly once: it attends over the history, produces this step’s output, and is never needed again — caching it would store something with no future reader. So the query is computed fresh each step and discarded; only the keys and values, whose usefulness compounds over the rest of the generation, earn a place in the cache. That is why the structure is a KV cache and not a QKV cache.
The saving made concrete: O(N^2) to O(N)
With the cache in place, count the work again. Each decode step now runs the full model stack for exactly one new token — one key, one value, one query — regardless of how long the sequence already is. Over N generated tokens that is N single-token forward passes, linear in N:
without cache: Σ t = O(N^2) token-forward-passes
with cache: N = O(N) token-forward-passesThat is a change in asymptotic complexity, not a constant-factor tweak — the longer the output, the larger the win. The genuine cost, to name it honestly: attention still reads the whole cache each step, so reads across a generation sum to O(N^2). But reading stored numbers is vastly cheaper than recomputing them through the weight matrices. The cache converts an O(N^2) compute problem into an O(N) compute problem plus an O(N^2) memory-traffic problem — and that reshaping is the whole reason serving LLMs is feasible.
The price tag: the bytes-per-token formula
Storage is the bill for that speed. Each cached token contributes one key vector and one value vector, in every layer, for every key/value head. Multiply the pieces:
bytes_per_token = 2 * L * H_kv * d_head * dtype_bytes
L=layers H_kv=kv-heads d_head=head-dim
dtype: bf16=2, int8=1, int4=0.5 factor 2 = K plus VFor standard multi-head attention where H_kv · d_head = d_model, this collapses to the tidy form 2 · L · d_model · dtype_bytes per token, and the whole-sequence cost is just bytes_per_token × N. Notice what is absent — the feed-forward width, the vocabulary size, the batch. Per-sequence cache size is set entirely by depth, key/value head geometry, precision, and length.
A worked example
Take a 13B-class model with multi-head attention: L = 40 layers, d_model = 5120 (so H_kv · d_head = 5120), stored in bf16 at 2 bytes. Per token:
bytes_per_token = 2 * L * d_model * 2
= 2 * 40 * 5120 * 2
= 819,200 bytes ~ 800 KiB / tokenSo a single 4096-token conversation holds 800 KiB × 4096 ≈ 3.1 GiB of KV cache — for one user; ten such users need about 31 GiB on top of the weights. This is why a back-of-the-envelope KV calculation, not the parameter count, usually decides how many sessions a GPU can hold. The number is large, per-user, and grows every single token — three facts that dominate every capacity decision downstream.
The twist: decode becomes bandwidth-bound
Here is the consequence that surprises people. Having removed the recompute, what remains on each decode step is dominated by moving the cache. To generate one token, attention in every layer must read every stored key and value — the entire current cache streams out of memory once per token. The math per element is trivial: a multiply-add for the score, another for the weighted value. That is an arithmetic intensity of roughly one operation per byte.
Modern accelerators can do hundreds of floating-point operations in the time it takes to fetch one byte from high-bandwidth memory. So at one op per byte the compute units sit idle waiting for data: decode is memory-bandwidth-bound, not compute-bound, with per-token latency essentially cache_bytes_read / HBM_bandwidth. Reading our 3.1 GiB example cache over a ~2 TB/s bus costs roughly 1.5 ms per token from the cache alone — a floor decode cannot beat. The cache’s size is therefore also its speed.
The budget: weights versus cache
The formula also fixes the growth laws: the cache is linear in length (token 4000 costs the same to store as token 4) and linear in batch, since each user keeps an independent cache with no shared history. The total is B × N × bytes_per_token, so the real limit is the product B × N. A serving node’s memory then splits into two pools: the weights, a fixed slab loaded once and shared across the batch, and the KV cache, a per-user cost nothing amortizes. Whatever the weights leave free, divided by the per-sequence cache size, is your hard concurrency ceiling.
On an 80 GB accelerator holding 26 GB of a 13B model in bf16, about 54 GB is left for cache. At 3.1 GiB per 4K sequence that is roughly 17 concurrent users — a hard stop set by the KV arithmetic, not by raw compute. Push either batch or context higher and you run out of cache room, not FLOPs. Every serving knob — maximum context, batch size, admission control — is a negotiation over this one pool.
The levers that shrink it
Because the cache is the binding constraint, most serving optimizations are just ways to make the number in that formula smaller. Read the formula factor by factor and each lever names itself. Shrink H_kv with grouped-query attention (GQA) or multi-query attention, where many query heads share a few key/value heads — a 4:1 ratio cuts the cache to a quarter. Shrink dtype_bytes with KV quantization, storing keys and values in int8 or int4 to halve or quarter both storage and the bandwidth that gates decode speed.
Attack waste rather than size with paged attention, which allocates the cache in small blocks so a short request does not reserve room for a long one. Each has real depth — covered in the companion articles on the KV cache’s tensors and bandwidth, KV quantization, and paged attention. All of them are the same move: fewer bytes, or fewer wasted, along the one axis that grows.
Pitfalls and a mental model
A few traps recur. First, the cache is not the weights — sizing a GPU by parameter count alone ignores that a long-context, high-batch workload can spend more memory on cache than on the model. Second, the cache does not shrink prefill: processing a long prompt still runs the full quadratic-attention pass to fill the buffers; the cache saves the decode steps that follow. Third, quantizing the cache is not free — keys and values carry outliers, so aggressive precision cuts can quietly degrade output quality.
The mental model to keep: the KV cache trades an O(N^2) recompute for an O(N) compute plus a large, growing, per-user memory footprint re-read every token. That trade is what makes generation fast; its size is what makes serving expensive. Master the bytes-per-token formula and its two growth laws, and almost every serving capacity and latency question becomes back-of-envelope arithmetic.