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.

Advertisement

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-passes

A 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.

Advertisement

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-passes

That 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 V

For 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 / token

So 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.