Learn AI Create the Future — with Pranay
Main site

How Text Is Generated

The KV cache

Instead of re-reading the whole conversation for every new word, the model keeps a running summary of what each earlier token contributed and appends one row per new token.

Read these first

On this page 7
  1. What is actually stored
  2. How it works
  3. Why you should care
  4. The price you pay
  5. Where you have already seen this
  6. Remember this
  7. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

A KV cache is the model's running notes about the conversation so far. It exists so the model never re-reads the whole thing.

Picture adding up a long grocery bill with a calculator. You do not start from the first item again every time the shopkeeper adds one more packet. You keep the running total and add the new price to it.

Now imagine a version of you who forgot that trick. Twenty items in, you would be re-adding nineteen old prices for every new packet. Same answer, far more work, and it gets worse with every item.

That forgetful version is what a language model does without a KV cache. The cache is the running total.

What is actually stored

When a model reads a token, it works out two things about it. Those two things are all that later tokens ever need.

One is a key — a short description of what this token is about, used so later words can find it. The other is a value — the actual information this token offers to anyone who looks it up.

Keys and values, hence KV.

Here is the thing that makes caching possible. A token's key and value never change. Once the model works out what the third word contributes, that answer is fixed. Nothing written later changes it.

So there is no reason to compute it twice.

How it works

   WITHOUT a cache, generating the 4th word

     step 1:  read word 1, 2, 3        -> write word 4
     step 2:  read word 1, 2, 3, 4     -> write word 5
     step 3:  read word 1, 2, 3, 4, 5  -> write word 6
                    ^^^^^^^^^ all of this is repeated work


   WITH a cache

     step 1:  notes hold 1, 2, 3        -> write word 4
     step 2:  notes hold 1, 2, 3, 4     -> write word 5    (one row added)
     step 3:  notes hold 1, 2, 3, 4, 5  -> write word 6    (one row added)

Each step adds exactly one row of notes. Nothing already written down is touched again.

Why you should care

This is not a small optimisation. Without it, generating a thousand-word answer would cost hundreds of times more than it does.

Every chat assistant you have used is running one of these. It is the single reason streaming text feels steady rather than getting slower and slower as the reply grows.

The price you pay

Notes take up space. The cache lives in the fastest, most expensive memory on the graphics card, right beside the model itself.

A long conversation means a long set of notes. Run out of room and the server has to drop somebody's conversation, or refuse a new one.

That trade — enormous speed for real memory — is the subject of the next lesson.

Where you have already seen this

  • A chat that stays fast even after a very long conversation.
  • A coding assistant that answers follow-up questions quickly after a slow first read of your file.
  • A server that suddenly says it is at capacity, even though nothing about your request changed.

Remember this

  • A key says what a token is about; a value says what it offers.
  • Both are fixed once computed, so the model stores them instead of recomputing.
  • The cache buys huge speed and spends real memory.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install numpy

Two decoders, identical maths, identical output. One keeps the cache, one throws it away. Counting the work is the lesson.

Both versions, side by side

kv_cache.py
import numpy as np

rng = np.random.default_rng(0)
V, D = 12, 8
E  = rng.normal(size=(V, D)) * 0.5
Wq = rng.normal(size=(D, D)) * 0.5
Wk = rng.normal(size=(D, D)) * 0.5
Wv = rng.normal(size=(D, D)) * 0.5
Wo = rng.normal(size=(D, V)) * 0.5

kv_projections = 0        # every key/value we compute, cached or not


def softmax(z):
    z = z - z.max(axis=-1, keepdims=True)
    e = np.exp(z)
    return e / e.sum(axis=-1, keepdims=True)


def attend(q_row, K, Vm):
    """One query row against all cached keys and values. No mask needed:
    the cache only ever holds tokens that already exist."""
    w = softmax(q_row @ K.T / np.sqrt(D))
    return (w @ Vm) @ Wo


def decode_no_cache(prompt, n_new):
    global kv_projections
    seq = list(prompt)
    for _ in range(n_new):
        x = E[seq]
        kv_projections += len(seq)                 # keys and values for the WHOLE prefix
        K, Vm = x @ Wk, x @ Wv
        q_last = (x @ Wq)[-1]                      # only the last position predicts
        seq.append(int(attend(q_last, K, Vm).argmax()))
    return seq


def decode_with_cache(prompt, n_new):
    global kv_projections
    x = E[prompt]
    kv_projections += len(prompt)                  # prefill: keys/values once
    K, Vm = x @ Wk, x @ Wv                         # <- the KV cache
    q_last = (x @ Wq)[-1]
    seq = list(prompt)
    for _ in range(n_new):
        nxt = int(attend(q_last, K, Vm).argmax())
        seq.append(nxt)
        x_new = E[nxt]
        kv_projections += 1                        # exactly ONE new key and value
        K = np.vstack([K, x_new @ Wk])             # append, never recompute
        Vm = np.vstack([Vm, x_new @ Wv])
        q_last = x_new @ Wq
    return seq


prompt = [3, 7, 1, 9, 4, 2]
N = 20

kv_projections = 0
slow = decode_no_cache(prompt, N)
cost_slow = kv_projections

kv_projections = 0
fast = decode_with_cache(prompt, N)
cost_fast = kv_projections

print("same text?          ", slow == fast)
print("sequence            ", fast)
print()
print(f"key/value vectors computed WITHOUT a cache: {cost_slow}")
print(f"key/value vectors computed WITH a cache   : {cost_fast}")
print(f"ratio                                     : {cost_slow / cost_fast:.1f}x")
print()
print(f"cache size after generation: {len(prompt) + N} rows x {D} numbers = {(len(prompt)+N)*D} numbers, twice (K and V)")
Output
same text?           True
sequence             [3, 7, 1, 9, 4, 2, 9, 1, 3, 1, 9, 1, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

key/value vectors computed WITHOUT a cache: 310
key/value vectors computed WITH a cache   : 26
ratio                                     : 11.9x

cache size after generation: 26 rows x 8 numbers = 208 numbers, twice (K and V)

Reading the output

same text? True is the headline. Caching is not an approximation. It is not a quality trade-off. The same numbers come out, because the quantities being cached are mathematically identical to the ones being recomputed.

310 against 26. Twenty tokens generated from a six-token prompt. Without the cache the cost grows with the square of the length; with it, the cost grows linearly. Push N to 200 and the ratio passes 100.

The cache holds 26 rows. One row per token seen so far, for keys, and another for values. That is the memory bill, and it grows by one row per generated token forever.

Notice attend has no causal mask. In the no-cache version, a mask stops a position from peeking at the future. In the cached version there is nothing to mask — the cache physically contains only tokens that already exist. Beginners often add a mask here and break their code.

The three lines that matter

K = np.vstack([K, x_new @ Wk]) is the entire idea. Real implementations preallocate a buffer and write into row t instead of reallocating, because vstack copies the whole cache every step. Correct here, wrong in production.

q_last = x_new @ Wq shows why queries are not cached. The query is a question asked by the newest token only. Every step needs a fresh one, so there is nothing to reuse. The cache is K and V, never Q.

kv_projections += 1 is the line to stare at. One new key, one new value, per token, forever. Everything else in the cached decoder is a lookup.

What a real implementation looks like

In PyTorch a cached attention step differs from the uncached one in about five lines:

python
# past_k, past_v have shape (batch, kv_heads, seen_so_far, head_dim)
k = torch.cat([past_k, new_k], dim=2)      # append along the sequence axis
v = torch.cat([past_v, new_v], dim=2)
attn = torch.softmax(q @ k.transpose(-1, -2) / head_dim ** 0.5, dim=-1) @ v

In HuggingFace Transformers this is handled by a Cache object and switched on with use_cache=True, which is the default for generation. In vLLM and SGLang the cache is not a tensor at all, but a pool of fixed-size blocks. That is the subject of PagedAttention.

Common mistakes

Passing the whole sequence back in on every step while also passing the cache. The model then recomputes everything and appends duplicates. With a cache you feed exactly one token per step. Getting an answer that looks stuttery or repeats the prompt is the usual symptom.

Forgetting positions. The new token's position index must continue from the cache length, not restart at zero. With rotary position embeddings this shows up as text that is fluent for a few tokens and then collapses.

Reusing a cache across a changed prompt. The cache is only valid for the exact token sequence that built it. Edit any earlier token and everything from that point on is stale. Truncate the cache to the shared prefix and re-prefill the rest.

Growing the cache with cat in a hot loop. Every call allocates and copies. Preallocate to the maximum length you allow and track a fill pointer.

Assuming the cache saves memory. It saves compute and spends memory. On long contexts the cache can outgrow the model weights themselves.

Try it yourself

Set N = 200 and print the ratio. Then delete the q_last = x_new @ Wq line and reuse the old query instead. The output will still run and will still look plausible, which is the most dangerous kind of bug in this area.

What to learn next

Researcher — Mathematics and papers.

What is being cached, exactly

For a single attention head at layer $\ell$, token $t$ produces

$$ k_t^{(\ell)} = W_K^{(\ell)} x_t^{(\ell)}, \qquad v_t^{(\ell)} = W_V^{(\ell)} x_t^{(\ell)} $$

where $x_t^{(\ell)}$ is the layer input at position $t$. Causal masking guarantees $x_t^{(\ell)}$ depends only on positions $\le t$, so $k_t$ and $v_t$ are invariant to everything generated later. That invariance is the correctness proof for the cache — it is exact, not approximate.

Decoding step $t$ then computes

$$ o_t = \mathrm{softmax}!\left( \frac{q_t K_{1:t}^{\top}}{\sqrt{d_h}} \right) V_{1:t} $$

with $q_t = W_Q x_t$, $d_h$ the head dimension, and $K_{1:t}, V_{1:t}$ read from the cache.

Complexity

Generating $n$ tokens from a prompt of length $m$, per layer, per head:

attention FLOPsprojection FLOPs
no cache$O!\left((m+n)^3 d_h\right)$$O!\left((m+n)^2 d\right)$
with cache$O!\left((m+n)^2 d_h\right)$$O!\left((m+n) d\right)$

The cache removes one full factor of sequence length from both terms. What it cannot remove is the remaining quadratic in attention: step $t$ still reads $t$ cached rows, so total cache traffic over a generation is $O(n^2)$ bytes. That residual is what long-context attention research attacks.

Why only K and V

The three projections are not symmetric in their reuse. $k_t$ and $v_t$ are consumed by every future query. $q_t$ is consumed once, at step $t$, and never again. Caching it would store data with no future reader.

This asymmetry also explains why grouped-query attention shrinks the cache but not the compute. Reducing the number of K and V heads while keeping all Q heads shrinks exactly the thing that gets stored.

Variants that change what is stored

  • Multi-query attention (Shazeer, 2019, arxiv.org/abs/1911.02150) — one K/V head shared by all Q heads. Cache shrinks by the head count; quality drops noticeably at scale.
  • Grouped-query attention (Ainslie et al., 2023, arxiv.org/abs/2305.13245) — $g$ K/V heads shared among $h$ query heads. The default in Llama 3, Qwen 3 and Mistral.
  • Multi-head latent attention (DeepSeek-V2, 2024, arxiv.org/abs/2405.04434) — cache a low-rank latent vector per token, reconstructing K and V on the fly. Trades arithmetic for memory.
  • Sliding-window and streaming attention — keep only a recent window, plus a few "attention sink" tokens (Xiao et al., StreamingLLM, 2023, arxiv.org/abs/2309.17453). Lossy: it bounds memory rather than preserving exactness.
  • KV cache quantisation — store K and V in 8-bit or 4-bit. Cheap and popular, and empirically keys tolerate quantisation worse than values do because of outlier channels.

Cross-request reuse

Within one request the cache is a compute optimisation. Across requests it becomes a systems problem.

Any two requests sharing a token prefix share the exact same K and V for that prefix. Automatic prefix caching (vLLM) and RadixAttention (SGLang) exploit this by hashing block-aligned prefixes and pointing multiple sequences at the same physical blocks. On agent workloads with a large fixed system prompt this can eliminate most prefill work entirely.

The invalidation rule is strict and worth stating: a cached prefix is valid only if every token id matches. Not the rendered string — the token ids. A change in chat template, tokenizer version, or whitespace silently misses the cache.

Papers

What to learn next