The KV Cache: Why Transformer Inference Needs It

Autoregressive decoding generates one token at a time, and each new token has to attend over every token that came before it — that much is already true by construction. What's easy to miss is a much more expensive fact hiding underneath: naively implemented, that attention step doesn't just use all prior tokens, it recomputes them, from scratch, at every single step. The KV cache is the fix, and it's one of the highest-leverage optimizations in all of LLM inference — without it, every production chat interface you've ever used would feel noticeably slower the longer its replies got.

The waste hiding inside every attention layer

Recall the shape of self-attention: at every layer, each token produces a Query, a Key, and a Value by projecting its hidden state through learned weight matrices. Generating token N+1 means taking that token's Query and attending it against the Keys and Values of tokens 1 through N. Nothing about that requirement has changed — but ask how a naive implementation gets those N Keys and Values, and the answer is uncomfortable: it recomputes key_proj and value_proj for all N tokens, every time, even though tokens 1 through N were already fully processed in earlier steps and haven't changed since.

That's pure waste. A token's Key and Value at a given layer are a function of that token's hidden state entering the layer — and for every token except the newest one, that hidden state was already finalized in an earlier step. Recomputing it again is doing real matrix-multiplication work to arrive at a number the model already knew.

The insight: cache what never changes

The KV cache exploits exactly that fact. Once a token has passed through a layer and produced its Key and Value vectors for that layer, those vectors are fixed forever — save them. On the next generation step, the only token whose Key, Value, and Query need to be computed fresh is the one new token that just arrived. Its Query attends against the Keys and Values already sitting in the cache, plus its own newly computed Key and Value, which then get appended to the cache for the step after that.

This is a cache in the plainest sense of the word: a store of previously computed results, keyed by position, that gets read before anything is recomputed and appended to as new results arrive. Every attention layer in the model keeps its own KV cache, since Keys and Values are layer-specific projections.

Without a cache vs. with one

The difference is easiest to see by writing both versions side by side. The naive version below recomputes Keys and Values for the entire sequence at every step; the cached version computes them once per token and never again.

# WITHOUT a cache: every step redoes work it already did
def generate_step_naive(all_tokens: list[int]):
    # Recomputes K and V for EVERY token, including ones
    # processed in every previous step. Only the last
    # position's output is actually new information.
    K = [key_proj(t) for t in all_tokens]      # O(n) work
    V = [value_proj(t) for t in all_tokens]    # O(n) work
    q = query_proj(all_tokens[-1])             # only this is new

    scores = [dot(q, k) for k in K]
    weights = softmax(scores)
    return weighted_sum(weights, V)

# Cost over a full generation: step 1 does 1 unit of K/V work,
# step 2 does 2, step 3 does 3, ... step n does n.
# Total = 1 + 2 + ... + n  ->  O(n^2) for the whole response.


# WITH a cache: only the new token's K/V are ever computed
kv_cache = {"K": [], "V": []}

def generate_step_cached(new_token: int):
    k = key_proj(new_token)     # O(1) work
    v = value_proj(new_token)   # O(1) work
    q = query_proj(new_token)   # O(1) work

    kv_cache["K"].append(k)     # append, never recompute
    kv_cache["V"].append(v)

    scores = [dot(q, k) for k in kv_cache["K"]]
    weights = softmax(scores)
    return weighted_sum(weights, kv_cache["V"])

# Cost per step is now constant in the K/V-projection work —
# the attention sum still scans a growing cache, but the
# expensive projection matmuls never repeat.

Sum the naive version's work across a full generation and it grows like 1 + 2 + 3 + … + n — quadratic in the number of tokens generated. The cached version does a constant amount of projection work per step, no matter how long the sequence has already grown. That difference is the entire reason KV caching exists: it turns an O(n²) generation cost into something close to O(n), simply by refusing to redo work whose answer was already sitting in memory.

The trade-off: memory instead of compute

None of this is free — it converts a compute problem into a memory problem. The cache has to store a Key and a Value vector, per layer, per attention head, for every token generated so far. That grows linearly with sequence length, and it multiplies by the model's depth and width: a model with more layers or more attention heads pays proportionally more memory for the same context length. For today's long-context models, the KV cache for a single long conversation can occupy gigabytes of accelerator memory — often rivaling the size of the model's own weights.

That memory pressure is precisely why techniques like multi-query attention and grouped-query attention exist. Instead of giving every attention head its own Key and Value projections, several (or, in the multi-query case, all) heads share the same Key/Value pair while keeping separate Queries. The Query still gives each head its own way of looking at the sequence, but the cache only needs to store one shared set of Keys and Values instead of one per head — shrinking the cache's memory footprint by the same factor without abandoning the caching idea itself.

Why this matters at serving time

This is the piece of infrastructure that makes long, fast LLM responses financially and practically viable at all. Without a KV cache, generating a long response would get progressively slower as it went — each new token would cost more to produce than the last, since the recomputation naive decoding does grows with everything already generated. With the cache, the per-token cost of generation stays roughly flat, which is exactly the property that lets a production system stream out a thousand-token answer at a steady pace instead of visibly grinding down as the response lengthens. It sits quietly underneath the autoregressive loop described earlier, doing nothing clever about what gets generated — only making sure the model never pays twice for work it already finished.