Autoregressive Decoding, Step by Step

The loop, at a high level

A large language model generates text one token at a time, feeding each new token back in as input for the next step, until it produces a stop token or hits a length limit. This is called autoregressive generation — the output depends on the model's own previous outputs.

prompt: "The capital of France is"
step 1: model reads the whole prompt      → predicts " Paris"
step 2: model reads prompt + " Paris"     → predicts "."
step 3: model reads prompt + " Paris."    → predicts <stop>

Each step is a full forward pass through every layer of the model. If that sounds expensive to do for every single token — it is, and almost the entire field of inference optimization exists to make each step cheaper without changing the output.

Why not predict the whole sentence at once?

Because each token's probability distribution is conditioned on everything before it, including tokens the model itself just generated. The model literally cannot know what its third word will be until it has committed to the first two — that commitment is what "generation" means. This is fundamentally different from training, where the entire target sequence is already known and every position can be computed in parallel (this is called teacher forcing).

That asymmetry — parallel at training time, sequential at inference time — is the single fact that makes inference engineering its own discipline.

Prefill: processing the prompt

Before generating anything, the model has to run the entire input prompt through every layer once. This is called prefill.

Because the whole prompt is known in advance, prefill processes all prompt tokens in parallel in one forward pass — the same matrix multiplications used in training, at the same efficiency. A 500-token prompt does not take noticeably longer per-token than a 50-token prompt, because the GPU is doing dense matrix math it's built for.

Prefill is compute-bound: the GPU spends its time doing floating-point math, and it's kept busy the whole time. This is the phase that determines time to first token (TTFT) — the user is waiting for prefill to finish before they see anything.

Decode: generating one token at a time

After prefill, the model enters the decode loop. On each step it:

1. Takes the single most recently generated token as input
2. Runs it through every layer of the model
3. Produces a probability distribution over the vocabulary for the next token
4. Samples (or picks the highest-probability) token from that distribution
5. Appends it to the sequence and repeats

def generate(model, prompt_tokens, max_new_tokens):
    tokens = prompt_tokens
    cache = model.prefill(tokens)          # one parallel pass over the whole prompt

    for _ in range(max_new_tokens):
        logits, cache = model.decode_step(tokens[-1], cache)  # one token at a time
        next_token = sample(logits)
        if next_token == STOP_TOKEN:
            break
        tokens.append(next_token)

    return tokens

Each decode step only processes one new token, but it still has to load the entire model's weights from GPU memory to do it. That is an enormous amount of data movement for a tiny amount of math — which is exactly the definition of memory-bandwidth-bound. This is why decode is slow in a way that adding more raw compute doesn't fix.

Time per output token (TPOT) is set almost entirely by this loop. A model that streams text to you at a steady pace is running this loop once per token you see appear.

Why decode can't just reprocess everything

A naive implementation would, at every decode step, feed the entire sequence so far (prompt + all generated tokens) back through the model from scratch. This works, but it is wasteful: the attention computation for token 500 depends on the internal representations (keys and values) of tokens 1 through 499, and those representations don't change once computed — they only need to be computed once, ever.

Recomputing them at every step means step $n$ does $O(n)$ work it already did at step $n-1$, so generating a sequence of length $N$ costs $O(N^2)$ total instead of $O(N)$. For a 4,000-token response, that quadratic blowup is the difference between a system that works and one that doesn't.

The fix is to cache those key and value tensors instead of recomputing them — the subject of the next lesson.

Sampling: picking the next token

The forward pass produces logits — one score per vocabulary token, roughly 50,000–200,000 of them depending on the tokenizer. How you turn logits into a chosen token matters for both quality and, in some cases, latency.

• Greedy decoding — always pick the highest-probability token. Deterministic, fast, but repetitive and prone to getting stuck in loops.
• Temperature sampling — divide logits by a temperature $T$ before the softmax. $T < 1$ sharpens the distribution (more deterministic); $T > 1$ flattens it (more random).
• Top-k sampling — only sample from the $k$ highest-probability tokens.
• Top-p (nucleus) sampling — sample from the smallest set of tokens whose cumulative probability exceeds $p$, adapting the candidate pool size to how confident the model is.

None of these change the per-step cost meaningfully — they're cheap vector operations on top of logits the model already computed. They matter for output quality, not for the performance topics ahead, but you'll see the terms again when we discuss speculative decoding, since verifying a speculated token requires reproducing the same sampling decision.

Two phases, two different problems

Keeping this table in your head explains a surprising amount of serving system design. A request with a long prompt and a short answer (e.g., document summarization) is prefill-heavy. A request with a short prompt and a long answer (e.g., "write me an essay") is decode-heavy. A good serving system treats them differently — which is exactly what disaggregated prefill/decode serving, covered later in this course, is built around.

Summary

Generation is autoregressive: each token depends on every token before it, so it can't be parallelized across the output. Prefill processes the whole prompt at once and is compute-bound; decode produces one token at a time and is memory-bandwidth-bound because it reloads the full model for each token. Recomputing past tokens' internal state at every step would be quadratically expensive, which is why real systems cache it instead — the KV cache, covered next.