Sep 2026 draft
why does inference need a KV cache?
generating token 500 costs far more than generating token 5, unless you save something between steps. this is what that something is.
the naive loop
i started with the obvious decode loop. you have some tokens, you run the full model, you sample one new token, you append it, you repeat. each step runs attention over the whole prefix so far. step 5 attends over 5 positions. step 512 attends over 512 positions. add up steps 1 through 512 and the attention work grows with the square of the sequence length, even though each step only produces one token.
this felt wrong the first time i profiled it. most of the FLOPs at step 512 are recomputing keys and values for tokens 1 through 511, which have not changed since the last step. their embeddings are identical, their projections are identical, and i was paying full price for them again.
what gets cached
attention needs three things per position: a query, a key, and a value. the query is only ever needed for the current token, because only the new token is asking "what should i attend to". but the keys and values of every past token get reused at every future step. so after the first pass, you store the K and V vectors of each layer for each position, and on the next step you only project the single new token and append its entries.
each step after the first is then roughly constant work in sequence length instead of linear. the total over the whole generation drops from quadratic back to linear. nothing about the math changed, the model computes exactly the same numbers. it is purely refusing to redo finished work.
a concrete size
the part i underestimated is how big the cache gets. back of the envelope for a small model: 12 layers, hidden size 768, half precision (2 bytes), sequence length 512. per token per layer you store a key and a value vector, so that is 2 * 12 * 512 * 768 * 2 bytes, about 18 MB for one sequence. bump the context to 4096 tokens and it is about 145 MB. per sequence, before batching. at that point the cache is bigger than some of the weight matrices, and it grows with every token you generate.
this is why serving systems obsess over the cache. batching multiplies it by batch size, long contexts multiply it by length, and suddenly inference is not compute bound at all. it is memory bandwidth and capacity bound, shuttling the cache in and out for every token.
what surprised me
what surprised me is that the cache is the reason so many inference features exist. paged attention, cache eviction policies, quantized KV, prefix sharing across requests in a batch: all of them are answers to "the cache got too big" rather than "the model got too slow". i had assumed the interesting engineering was in the matmuls. for generation, the interesting engineering is in not recomputing things and then surviving the memory bill for that decision.
if i did this writeup over, i would benchmark it instead of asserting it: time naive versus cached generation at 64, 512, and 2048 tokens on the same machine and plot where the curves separate. the theory is clean, but i still have not felt the quadratic curve in my own measurements, and that is the next thing to do in MiniInfer.
all notes