Inference and Decoding

A language model does not write a sentence in one shot. It predicts one token, appends it to the input, and predicts the next — over and over. This is what autoregressive means: each output becomes part of the next input.

Each trip around the loop is a full forward pass through all N blocks from day 7. Generating 100 tokens means running the model 100 times. That repetition is exactly why inference needs the speed tricks below.

Here is the waste the cache removes. On day 3 you saw that attention builds a key and a value vector for every token. When the model generates token 101, tokens 1–100 have not changed — yet a naive loop recomputes all their keys and values from scratch every single step.

The KV cache stores each token's keys and values the first time they are computed and reuses them forever after. New work per step shrinks to a single token's keys and values. The cost is memory. Size the cache for a small model: n_layers = 12, d_model = 768, stored in fp16 (2 bytes per number).

per token = 2 (K and V) * n_layers * d_model
          = 2 * 12 * 768
          = 18,432 numbers
bytes per token = 18,432 * 2 = 36,864 bytes = 36 KB

So every token in the context permanently occupies about 36 KB. Multiply by how many tokens are cached:

The cache grows linearly with context length. For one small model 36 MB is nothing, but multiply by large models and many simultaneous users and the KV cache, not the weights, often becomes the memory bottleneck for serving.

With probabilities in hand, how do you pick the actual next token? The simplest rule is greedy: always take the highest-probability word. It is deterministic and safe, but it tends to loop — "the best the best the best" — because the single most likely continuation is often a word the model just used.

Sampling instead draws a token at random in proportion to its probability. That brings variety and creativity, but pure sampling occasionally picks an absurd low-probability token and derails. The fix is to cut the tail first:

• Temperature reshapes the distribution before sampling (its own lesson): low temperature sharpens toward greedy, high temperature flattens toward random.
• Top-k keeps only the k most likely tokens, renormalizes, then samples.
• Top-p (nucleus) keeps the smallest set of top tokens whose probabilities sum to at least p, then samples — an adaptive k.

Watch how top-k and top-p dim the tail of a fixed next-token distribution before a token is drawn:

Lower k or p until only two or three tokens survive, press Sample a few times, and notice the output stays sensible; widen them and the rare tokens can sneak back in.

Beyond the KV cache, a few levers trade quality or memory for tokens-per-second. They are worth knowing by name even at a high level.

The headline: inference cost is dominated by running the forward pass once per generated token, so almost every optimization is about doing less work — or reusing more — per step.

• Generation is an autoregressive loop: one forward pass per token, output fed back as input.
• The KV cache reuses past keys and values so each step only computes the new token; its memory grows linearly (about 36 KB/token for a 12-layer, 768-dim model).
• Greedy decoding is deterministic but repetitive; sampling adds variety but needs the tail truncated.
• Top-k keeps a fixed number of tokens; top-p keeps a probability mass — both renormalize before sampling.
• Inference cost is one forward pass per token, so speed tricks aim to reuse or skip work per step.

• [ ] Can you describe the autoregressive loop and say how many forward passes 50 tokens take?
• [ ] Can you compute a KV-cache size from 2·n_layers·d_model·bytes per token?
• [ ] Can you explain why greedy decoding tends to repeat itself?
• [ ] Can you state the difference between top-k and top-p in one sentence each?
• [ ] Can you name two levers besides the KV cache that speed up inference?