Typorithm · hard

KV Cache & Autoregression

kv-cachetransformersautoregressivedecoding

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn KV Cache & Autoregression

Inference & Sampling

Decoding is autoregressive — generate one token, append it, and feed it back. The KV cache stores past keys and values so each new step avoids recomputing the whole sequence (O(1) per step instead of O(n)). Generation stops at an EOS token or a max length.

Transformers generate text autoregressively: each token is produced from all the tokens before it, then appended and fed back as input for the next step. The output of one step becomes part of the input to the next.

Without optimization, every new token would re-run attention over the entire growing sequence. The KV cache fixes this by storing the key and value vectors of all previous positions, so a step only computes attention for the single new token.

With the cache, each decode step is roughly O(1) work in sequence length instead of O(n), making long generations far cheaper. The loop ends when the model emits the EOS token or reaches the maximum token budget.

Autoregressive: sample a token, append it, feed it back.

The KV cache stores past keys and values to skip recompute.

Cached steps are O(1) per token instead of O(n).

// generate one token at a time
for (let i = 0; i < maxTokens; i++) {
  const logits = model(token, kvCache);
  token = sample(logits);
  if (token === EOS) break;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Token loop

Decoding runs a loop, producing one token per iteration up to a maximum length.

for (let i = 0; i < maxTokens; i++) {

2. Cached step

The model takes only the latest token plus the KV cache of all previous keys and values.

const logits = model(token, kvCache);

3. Pick next

The sampled token is fed back in as input for the next iteration — the autoregressive loop.

token = sample(logits);

4. Stop token

Generation stops when the model emits the end-of-sequence token (or hits maxTokens).

if (token === EOS) break;

5. Cache reuse

Passing kvCache lets the model reuse past attention keys/values instead of recomputing them.

model(token, kvCache)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.