Memoization and queues to the KV cache

The one optimization that lets a chatbot answer in real time is nothing new - it is memoization plus an append-only queue, wearing a transformer's clothes.

You have already built both halves of the KV cache. In Recursion and the call stack you watched memoization turn an exponential Fibonacci into a linear one by storing each result the first time it was computed. In Stacks, queues, and deques you met the queue - an append-only buffer you only ever add to the end of. Bolt them together inside a transformer and you get the KV cache: each past token's key and value vectors are computed once, stored, and reused, so producing the next token stays $O(n)$ work instead of the $O(n^2)$ you would pay by recomputing the whole attention triangle from scratch.

Memoization, one level up

Recall self-attention: to attend, each token is projected into a query, a key, and a value vector. A new token's query is compared (dot product) against the key of every token at or before it - the causal mask means you never look ahead - and those scores mix the values into the output. The keys and values of the tokens already in the context do not change when a new token arrives. So recomputing them every step is exactly the wasted work naive Fibonacci did: recalculating $\text{fib}(3)$ over and over inside $\text{fib}(5)$.

Watch the recompute vanish

Two runs generate the same sentence one token at a time. Press Generate next token. On the left, with no cache, the model rebuilds the entire triangular attention pattern every step - the already-seen rows flash red because that work was done before and thrown away. On the right, the KV cache greys out every stored key/value and computes only the single new bottom row. Watch the two cell counters diverge: identical at token 1, then quadratic versus linear.

The aha to catch: at token 1 both runs do exactly one dot product - the cache buys you nothing yet. But the red triangle's area grows like $t^2$ while the cached run only ever adds a single row of length $t$. By the eighth token the no-cache run is doing 36 dot products to the cache's 8, and almost all of that 36 is re-deriving keys and values it already computed and discarded. The cache never recomputes - it only remembers and appends.

# No cache: re-feed the ENTIRE sequence, recomputing K,V for all of it -> O(n^2)/token
seq = [BOS]
for _ in range(max_new):
    logits = model(seq)                 # attends over ALL of seq from scratch
    seq.append(argmax(logits))

# KV cache: compute each token's K,V once, keep appending to the buffer -> O(n)/token
seq, cache = [BOS], None
for _ in range(max_new):
    logits, cache = model(seq[-1:], past=cache)  # feed ONLY the new token
    seq.append(argmax(logits))         # cache grows by one row (append-only queue)

How big does the cache get?

Because the cache is a pure function of the tokens seen so far, it is also shareable. Two requests that begin with the same long system prompt can reuse its keys and values instead of each recomputing them - this is prompt (prefix) caching. The provider stores the prompt's KV once and every later turn starts from it, so you are answered faster and billed less for the shared prefix. The flip side is the linear memory cost from the math above: with long contexts the KV cache, not the model weights, becomes the thing that fills the GPU - which is why techniques like paged and grouped-query caches exist.

Check yourself