KV Cache › The Redundancy Problem in Autoregressive Generation

As we explored in Part XIII, decoder-only transformers generate text one token at a time. At each step, the model takes all tokens generated so far (including the prompt) and predicts the next token. The computational core of this process is the self-attention mechanism, which allows each token to gather information from all tokens that came before it. To understand why caching gives such large benefits, we must first examine exactly how attention operates during generation and identify where the redundant work occurs. The redundancy is not an accident or a design flaw; it is an inherent consequence of computing context-aware representations at every position.

Recall from Part XIII that self-attention computes queries, keys, and values from the input. The basic insight behind these three components is that attention works like an information retrieval system: queries stand for what a token is looking for, keys stand for what each token offers, and values contain the actual information to be retrieved. Think of it like a library search: the query is your search term, the keys are the catalog entries for every book on the shelf, and the values are the books themselves. When you search, you compare your query against every catalog entry and retrieve the books whose entries best match. We express these three components through linear projections:

$$Q = XW_Q, \quad K = XW_K, \quad V = XW_V$$

where:

• $X$: the input embedding matrix, containing the vector representations of all tokens in the sequence
• $W_Q, W_K, W_V$: the learned projection matrices that transform inputs into query, key, and value subspaces, each capturing a different aspect of the token's meaning
• $Q, K, V$: the resulting matrices, where $Q$ contains vectors representing what each token seeks, $K$ contains vectors representing what each token can be matched against, and $V$ contains the actual content to be aggregated

Each of these projection matrices is learned during training to extract the most useful representations for the attention mechanism. Once training is complete, these matrices remain fixed during inference. This means that given the same input token, the projections will always produce the same key and value vectors. This determinism is the property that makes caching possible: if the input and the weight matrix are unchanged, the output cannot change either.

The attention mechanism then computes a weighted sum of values based on the compatibility between queries and keys. This compatibility is measured through dot products, which capture how well a query's "question" matches each key's "answer." The full attention formula is:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

where:

• $Q, K, V$: the query, key, and value matrices computed from the input
• $K^T$: the transpose of the key matrix, arranged so that the dot product between queries and keys can be computed efficiently through matrix multiplication
• $d_k$: the dimension of the key vectors, used for scaling to prevent the dot products from growing too large
• $\text{softmax}$: the function that converts raw compatibility scores into probability weights summing to 1

The scaling factor $\sqrt{d_k}$ is necessary. Without this normalization, the dot products between high-dimensional vectors can become very large in magnitude. When these large values pass through the softmax function, the result becomes extremely peaked, meaning almost all attention weight concentrates on a single token. This causes gradients to vanish for all other positions, making training unstable. The square root scaling keeps the variance of the dot products roughly constant regardless of the dimension, and we explored this phenomenon in depth in Part XIII.

During generation, let's trace what happens at each step to understand precisely where the wasted work accumulates. Suppose we're generating a response to a 10-token prompt. The model must produce one token at a time, with each new token depending on everything that came before it.

Step 1 (Prefill): The model processes all 10 prompt tokens simultaneously. It computes the $Q$, $K$, $V$ matrices, each of shape $(10, d_k)$ or $(10, d_v)$ depending on the specific projection. The attention mechanism allows each prompt token to attend to all previous prompt tokens, establishing the initial context representation.

Step 2: After generating the first new token, we now have 11 tokens total. Without any optimization, the model would need to process the entire 11-token sequence from scratch. This means computing $Q$, $K$, $V$ for all 11 tokens, even though 10 of them are unchanged from the previous step.

Step 3: With 12 tokens total, we compute $Q$, $K$, $V$ for all 12 tokens, once again recomputing the projections for the original prompt tokens that haven't changed at all.

Notice the wasteful pattern: at step $t$, we recompute the keys and values for the first 10 prompt tokens, even though nothing about them has changed since step 1. The same tokens, passing through the same fixed projection matrices $W_K$ and $W_V$, produce the same $K$ and $V$ vectors every single time. This redundancy stems from a basic property of the attention mechanism: the key and value for a given token depend only on that token's embedding and the projection weights, not on what comes after it in the sequence. The causal mask ensures that earlier tokens never attend to later ones, so later tokens can never influence the keys and values of earlier tokens.

This redundancy has concrete costs that grow sharply with sequence length. For a model with $L$ layers, $H$ attention heads, and head dimension $d_h$, generating $T$ tokens requires computing $K$ and $V$ projections repeatedly at every step. The total number of projection operations across all generation steps sums to:

$$\sum_{t=1}^{T} t = \frac{T(T+1)}{2} \approx \frac{T^2}{2}$$

where:

• $T$: the final sequence length, representing the total number of tokens processed including both the prompt and generated tokens
• $t$: the current step number, which also is the sequence length at that particular step
• $\sum_{t=1}^{T} t$: the sum of the arithmetic progression $1 + 2 + 3 + \ldots + T$, capturing the total number of token-projection operations across all steps

This quadratic scaling has severe implications for practical deployment. If generating 100 tokens requires $\frac{100 \times 101}{2} = 5,050$ projection operations, then generating 1,000 tokens requires $\frac{1000 \times 1001}{2} = 500,500$ operations, a 100-fold increase in work for only a 10-fold increase in output length. This contrasts with the ideal case where each token's keys and values are computed only once, requiring $T$ projection operations. The KV cache reaches exactly this ideal.