Autoregressive Decoding

TL;DR: A language model does not write a sentence in one shot. It predicts one token, appends it to the input, and runs again to predict the next, looping until it emits a stop token. That loop is inherently sequential, which makes decode the slow, memory-bound half of inference (prefill, where it reads your prompt, runs in parallel). The KV cache exists precisely to keep each step of that loop cheap.

What "autoregressive" actually means

The model is trained to do one thing: given a sequence of tokens, output a probability distribution over the next token. Generation is just calling that function in a loop. You feed the prompt, get a distribution over the vocabulary, pick a token, glue it onto the end of the sequence, and feed the whole thing back in. "Autoregressive" means each output becomes part of the next input.

The consequence that trips people up: you cannot generate token 50 until you have generated token 49, because token 49 is part of the context that produces token 50. In standard decoding there is no way to parallelize across output positions. This is the opposite of training, where the entire target sequence is known up front and every position is scored in one parallel pass using a causal mask.

def generate(model, prompt_ids, max_new=128, eos_id=2):
    ids = list(prompt_ids)
    cache = None                          # KV cache, empty at first
    for _ in range(max_new):
        logits, cache = model(ids[-1:] if cache else ids, cache)
        next_id = sample(logits[-1])      # greedy, temperature, or top-p
        ids.append(next_id)
        if next_id == eos_id:
            break
    return ids

That cache argument is the whole game. Without it, every iteration would re-process the entire growing sequence from scratch. In a toy example starting with a one-token prompt, generating 1,000 tokens without a cache processes 1 + 2 + ... + 1,000 tokens, which is 500,500 token-positions of work, against 1,000 with one (computed). These totals include the initial prompt pass and count processed input positions. A longer prompt changes both totals; they are not counts of attention operations or elapsed time. Caching makes the count of newly processed positions linear in output length, which is why the loop above passes only ids[-1:] once the cache exists.

Prefill vs decode

The dashed arrow is the constraint the whole page is about. Everything above it happens once; everything inside it happens again for every single token the model writes.

Inference splits into two phases with very different performance profiles.

Prefill is compute-bound: a 2,000-token prompt is processed in a single parallel forward pass, so the GPU's matrix units stay busy and it scales well with prompt length. Decode is memory-bound: each step computes one token's worth of math but must read the entire model's weights and the whole KV cache from memory to do it. The arithmetic is tiny relative to the bytes moved, so the GPU sits waiting on memory rather than maxing out its FLOPs. This is why a long output feels slow even on a fast card, and why throughput tricks like continuous batching matter: you batch many requests' decode steps together to amortize the weight reads. Put numbers on the two phases for a 13-billion-parameter model. Prefill of a 2,000-token prompt is about 52 trillion floating-point operations, which a modern accelerator sustaining 400 trillion a second finishes in roughly 130 ms, all positions at once. Each decode step then reads the model's 26 GB of fp16 weights, which at a listed bandwidth of about 3.35 TB/s takes 7.8 ms, so a 500-token reply spends about 3.9 seconds in decode against 0.13 in prefill (computed; both rates are order-of-magnitude figures and the real numbers depend on the card and the kernels). Time-to-first-token is the prefill number; tokens per second is the decode number; and that is why the two have different fixes.

The KV cache, in one breath

At step t the model needs to attend over the keys and values of every earlier token. Those vectors never change once a token is emitted, so you compute them once and store them. Each new step then computes only the new token's query and attends over the cached keys and values, turning per-token cost from "recompute the whole history" into "compute one token, read the cache." The price is memory: the cache grows with sequence length times batch size, and that growth is the real serving constraint. See kv-cache.

How the next token gets picked

The model hands you logits; the decoding strategy turns them into a choice.

• Greedy: take the argmax every step. Deterministic, fast, and prone to dull or repetitive text.
• Sampling (temperature, top-k, top-p): draw from the distribution, optionally sharpened or flattened by temperature and truncated to the top tokens. This is the default for open-ended generation. See temperature-and-sampling.
• Beam search: keep the B highest-probability partial sequences and expand all of them each step. Good for short, high-precision outputs like translation; rarely used for chat because it produces bland, "safe" text and multiplies the already-sequential cost by B.

A subtle point interviewers like: the strategy only changes which token you pick, not how the model runs. The forward pass and the cache are identical whether you decode greedily or sample.

Why interviewers probe this

It is the cleanest test of whether you understand why LLM serving is hard. A candidate who only knows "it predicts the next token" misses that the prediction loop is sequential and memory-bound, which is the root cause of decode latency, the reason for the KV cache, and the motivation behind continuous batching and speculative decoding. The follow-up they hold in reserve: "your time-to-first-token is fine but tokens-per-second is poor, why?" The answer is that TTFT is dominated by prefill (compute) and per-token speed is dominated by decode (memory bandwidth), so they have different fixes.

Common misconceptions

• "The model generates the whole response at once." It generates one token per forward pass, in a loop.
• "Prefill and decode are the same speed per token." Prefill is parallel and compute-bound; decode is sequential and memory-bound. They scale differently.
• "Sampling is slower than greedy." The forward pass dominates; choosing the token is negligible either way.
• "Beam search is the best default." For chat it tends to produce bland text and multiplies cost; sampling with top-p is the usual choice.

Key takeaways

• Generation is a sequential loop: predict a token, append it, repeat until a stop token. Output positions cannot be parallelized.
• Inference splits into parallel, compute-bound prefill and sequential, memory-bound decode; they have different bottlenecks and different fixes.
• The KV cache makes each decode step cheap by storing past keys and values, at the cost of memory that grows with context times batch.
• Greedy, sampling, and beam search only change token selection, not how the model runs.