LLMs 2026-03-02 4 min read

KV-Caching, and How Autoregressive Decoding Stays Fast

How key-value caching turns autoregressive generation from a quadratic recomputation problem into a linear one, and where its memory cost bites at long context lengths.

Why naive decoding is wasteful

An autoregressive transformer generates text one token at a time, and each new token’s forward pass needs attention over every token that came before it. If you regenerate the full forward pass from scratch at every step, the model recomputes the key and value projections for all previous tokens every single time, even though those tokens and their projections never change once they are in the sequence. For a sequence of length $n$ , that means the total work across generation grows like $O(n^2)$ in the number of attention operations, purely from redundant recomputation.

The fix is obvious once stated: cache the keys and values computed for each token the first time they are produced, and reuse them on every subsequent step. Only the newly generated token needs a fresh key, value, and query computed at each step.

What actually gets cached

For each transformer layer and each attention head, the model projects the hidden state $h_t$ at position $t$ into a key vector $k_t = W_K h_t$ and a value vector $v_t = W_V h_t$ . During generation, once token $t$ has been processed, $k_t$ and $v_t$ are fixed for the rest of decoding, since they depend only on that token’s own hidden state, not on anything generated afterward.

The KV cache is just a growing tensor per layer, per head, storing every $k_t$ and $v_t$ seen so far:

K_{1:t} = [k_1, k_2, \ldots, k_t], \qquad V_{1:t} = [v_1, v_2, \ldots, v_t]

At decode step $t+1$ , the model only computes $q_{t+1}$ , $k_{t+1}$ , $v_{t+1}$ for the new token, appends $k_{t+1}$ and $v_{t+1}$ to the cache, and attends $q_{t+1}$ against the full cached $K_{1:t+1}$ and $V_{1:t+1}$ . This turns the total decoding cost from quadratic to linear in sequence length for the attention step itself.

def decode_step(model, token_id, kv_cache):
    h = model.embed(token_id)
    q, k, v = model.project_qkv(h)
    kv_cache.append(k, v)  # grows the per-layer K, V tensors
    attn_out = attention(q, kv_cache.K, kv_cache.V)
    return model.output_head(attn_out), kv_cache

The memory cost

Caching is a straightforward compute-for-memory trade, and the memory bill is not small. For a model with $L$ layers, $H$ heads, head dimension $d_h$ , at sequence length $n$ , and batch size $b$ , the cache size in float16 is:

\text{Cache bytes} = 2 \times L \times H \times d_h \times n \times b \times 2

(the leading 2 is for storing both K and V, the trailing 2 is bytes per float16 element). For a 70B-parameter class model with 80 layers and a 128k context, this reaches tens of gigabytes per sequence in the batch, often exceeding the memory used by the model weights themselves at long context lengths.

Technique	What it reduces	Rough savings
Multi-query attention (MQA)	Shares K/V across all heads	Up to Hx cache reduction
Grouped-query attention (GQA)	Shares K/V across groups of heads	4x to 8x typical
KV cache quantization	Stores K/V in int8 or lower	2x to 4x
Sliding window attention	Bounds cache to a fixed window	Turns O(n) into O(w)

Grouped-query attention is the detail that made long-context serving practical at scale: it is a small architectural change at training time, but it changes the memory-per-token cost of serving by a large constant factor, which is why nearly every serving-oriented model released after 2023 uses GQA or MQA instead of full multi-head attention.

Prefill versus decode

Serving systems split inference into two phases with very different performance characteristics. Prefill processes the entire prompt in one parallel forward pass, building the initial KV cache for all prompt tokens at once, and is compute-bound because it can use large batched matrix multiplications. Decode processes one token at a time per sequence, is memory-bandwidth-bound because it has to stream the entire KV cache through the GPU for every single token, and is where most serving frameworks spend their optimization effort (paged attention, continuous batching, speculative decoding) because the bottleneck is fundamentally different from prefill.

Why this matters for cost

Every serving framework worth using (vLLM, TensorRT-LLM, and similar) is built around efficient KV cache management, because at production scale, the cache is frequently the resource that determines how many concurrent requests a single GPU can serve, not the model weights. Techniques like PagedAttention treat the KV cache like virtual memory with fixed-size blocks specifically to reduce fragmentation and let more sequences share a GPU concurrently.