The Autoregressive Generation Loop

One token at a time: the autoregressive factorization

Autoregressive means the model regresses on its own past output: each new token is predicted from the tokens that came before it. The justification is exact, not an approximation. The chain rule of probability lets you write the joint probability of any sequence as a product of conditionals:

p(x_1, x_2, …, x_T) = p(x_1) · p(x_2 | x_1) · p(x_3 | x_1, x_2) · …
               = ∏_{t=1}^{T}  p(x_t | x_1, …, x_{t-1})
               = ∏_{t=1}^{T}  p(x_t | x_<t)

No information is lost in this rewrite — it holds for any distribution over sequences. A language model’s only job is to approximate one factor, the next-token distribution p(x_t | x_<t), and it is trained to do exactly that: given a prefix, predict the token that follows. Because every factor conditions only on earlier positions, a transformer enforces the same causality with a causal mask — position t may attend to positions ≤ t but never to the future. Generation is then just sampling from the factorization left to right: draw x_1, condition on it to draw x_2, and so on. The loop in your inference server is a literal, mechanical execution of that product.

The chain rule, made concrete

Make the product tangible with a three-token continuation. Suppose the prompt is fixed and the model must score the completion “cats sit quietly.” Its probability under the model is the product of three conditionals, each read straight off a forward pass:

p("cats sit quietly" | prompt)
  = p(cats | prompt)
  × p(sit  | prompt, cats)
  × p(quietly | prompt, cats, sit)

Suppose those three probabilities are 0.30, 0.50, and 0.40. The sequence probability is 0.30 × 0.50 × 0.40 = 0.06. Because such products underflow fast for long sequences, everything downstream works in log space: the log-probability is a sum, log 0.30 + log 0.50 + log 0.40 ≈ -2.81 (nats). The average negative log-probability per token, exponentiated, is the model’s perplexity on that span — the same quantity used to train and evaluate the model. The point for generation is structural: the score of a whole sequence is nothing more than the running sum of per-step surprises, one per trip through the loop, which is why a single mechanical step can build a paragraph of arbitrary length.

Anatomy of one step: embed → layers → logits → sample → append

Every iteration of the loop runs the same five-stage pipeline. Track the shapes as they flow, writing d for the model dimension, V for the vocabulary size, and L for the number of layers:

token id (int)
  → embed         : lookup row of E  → x : [d]
  → L transformer layers (attention + FFN, causal)  → h : [d]
  → LM head        : h · W_U  (W_U : [d, V])  → logits : [V]
  → sample/argmax  : pick next token id from softmax(logits)
  → append         : add token id to the running sequence

Embed turns the integer id into a vector. The layers mix it with the (cached) context to produce a final hidden state h. The LM head — a single [d, V] projection, often tied to the embedding matrix — turns h into one logit per vocabulary entry. Sampling collapses those V logits into a single chosen id, and append feeds it back as the input to the next iteration. During prefill the network computes a hidden state for every prompt position at once, but only the last position’s logits are needed to choose the first generated token — the rest exist only to populate the cache the decode phase will lean on.

The naive loop and its quadratic tax

Written without any optimization, the loop is disarmingly short — and quietly wasteful:

def generate(model, prompt, max_new):
    tokens = tokenize(prompt)
    for _ in range(max_new):
        logits = model(tokens)          # full forward over ALL tokens
        next_id = sample(logits[-1])    # but only the last row is used
        tokens.append(next_id)
        if next_id == EOS:
            break
    return tokens

The bug is not correctness but cost. At step t the model reruns a full forward pass over all t tokens, recomputing the keys and values for every token it already processed on the previous step. Summing the work across N generated tokens gives 1 + 2 + … + N = O(N^2) per-token forward passes — the same quadratic wall that attention itself is famous for, here paid again in the generation loop. For a 1000-token reply that is roughly half a million redundant token-forwards. Everything the past produced was already computed once; recomputing it every step is the single biggest avoidable expense in generation, and it is exactly what the KV cache removes.

The KV cache: making each step O(1) in past length

Attention needs, for the new token’s query, the keys and values of every previous token. But those keys and values depend only on the past tokens, which do not change once produced. So compute them once and cache them: after each step, append the new token’s K and V vectors (per layer, per head) to a growing buffer. The next step projects only the single new token to a query, key, and value, then attends over the cached K/V.

The effect on cost is decisive. The expensive per-token work — the embedding lookup, the Q/K/V projections, and the feed-forward network — now runs for exactly one token per step, O(1) in the past length instead of O(t). Only the attention score-and-blend against the cache scales with history, and that is a cheap dot-product sweep, not a re-projection. Total generation drops from O(N^2) forward work to O(N). The price is memory: the cache holds 2 · L · n_kv_heads · d_head values per token, and it grows every step. That buffer — not the weights — is what fills up during a long conversation, and managing it (paging, quantizing, evicting) is a whole discipline of its own.

Two phases: prefill and decode

Once the cache exists, inference splits cleanly into two phases with opposite personalities. Prefill ingests the prompt: all P prompt tokens go through the network in a single forward pass, in parallel, filling the KV cache for every prompt position and producing the logits that pick the first output token. Decode then generates the reply one token at a time, each step consuming the cache the previous steps built and extending it by one.

The reason to name them separately is that they stress completely different parts of the machine. Prefill is a big, wide matrix multiply — many tokens at once — and is limited by how fast the hardware can compute. Decode is a thin trickle — one token at a time — and is limited by how fast the hardware can move weights from memory. The same model, the same layers, the same arithmetic, yet one phase is compute-bound and the other is memory-bound. Almost every inference optimization — batching, quantization, speculative decoding, prefill/decode disaggregation — is really a response to this split, so it is worth understanding why the two phases land on opposite sides of the roofline.

Prefill: parallel over the prompt, compute-bound

Prefill is the one moment the loop is not a loop. The whole prompt is available up front, so there is no left-to-right dependency to respect within it — the causal mask handles ordering — and all P positions stream through each layer together as one [P, d] activation matrix. That batching over the sequence dimension is what makes prefill efficient.

Consider a single weight matrix W : [d, d] inside a layer. To apply it, the hardware loads its d^2 parameters from memory once, then reuses them against all P token vectors. The compute is ≈ 2 · P · d^2 FLOPs; the memory traffic is ≈ d^2 weight reads. The ratio — the arithmetic intensity — is therefore proportional to P. A long prompt means each loaded weight does a lot of work before it is discarded, which pushes prefill onto the compute-bound side of the roofline: the processor’s multiply-add throughput, not its memory bandwidth, is the bottleneck. On a CPU this is where SIMD width and core count earn their keep, and it is why a very long prompt can make time-to-first-token painfully long even before a single word has been generated.

Decode: one token at a time, memory-bound

Decode inverts every one of those properties. Each step there is exactly one new token, so the activation is a single [1, d] vector. Applying the same W : [d, d] now costs ≈ 2 · d^2 FLOPs against the same d^2 weight reads — an arithmetic intensity of about one, independent of how much text has already been generated.

That is the definition of a memory-bound workload: for every weight the processor pulls from memory it does only a couple of FLOPs, so the multiply-add units sit idle waiting on the memory bus. The step time is set almost entirely by how long it takes to stream the model’s weights past the processor once:

inter-token latency  ≈  (bytes of weights + KV cache read) / memory bandwidth

This single fact drives most of decode-side engineering. Adding more compute does nothing when you are bandwidth-limited — but shrinking the weights does, which is why quantization (fp16 → int8 → int4) is the highest-leverage knob for decode speed on a CPU. Halve the bytes per weight and you roughly halve the inter-token latency, because you have halved the traffic on the bus that actually gates the step.

Why the same model is compute-bound, then memory-bound

It can feel paradoxical that identical arithmetic is compute-bound in one phase and memory-bound in the next. The resolution is the single number above: arithmetic intensity, the FLOPs performed per byte of weight loaded. A weight matrix loaded from memory is a fixed cost; how many tokens you push through it before discarding it is a choice.

Prefill pushes P tokens through each loaded weight, so its intensity is roughly P — high, compute-bound. Decode pushes exactly one, so its intensity is roughly one — low, memory-bound. The roofline model makes this visual: every kernel sits at an x-position given by its intensity, rising with compute until it hits the flat ceiling of memory bandwidth. Prefill lives up on the sloped compute ceiling; decode lives down on the flat bandwidth floor. The crucial corollary is that batching moves decode rightward: run B independent generations together and each weight load serves B tokens, lifting decode’s intensity from one toward B. That is the entire reason inference servers batch — not to make any single user faster, but to reclaim the wasted bandwidth of a memory-bound phase.

Choosing the next token: greedy vs sampling

The loop’s sample() step deserves a brief pointer, because the same logits can yield wildly different text. The two poles are greedy decoding — always take argmax(logits), the single most probable token — and sampling — draw randomly from the distribution softmax(logits / T), where the temperature T flattens (T > 1) or sharpens (T < 1) the probabilities before the draw.

Greedy is deterministic and repeatable but tends toward bland, sometimes looping output; sampling adds diversity at the risk of incoherence, which practical schemes tame by truncating the tail — top-k keeps the k most likely tokens, top-p (nucleus) keeps the smallest set whose probability mass exceeds p — before renormalizing and drawing. The decisive point for this article is that the choice of decoding strategy sits entirely inside the last stage of the step and is essentially free: it touches only the V logits already computed, changes none of the expensive layer math, and therefore does not alter the prefill/decode cost structure at all. The mechanics of sampling are a topic of their own; here it is simply the knob that turns one logit vector into one token.

Knowing when to stop

The loop needs a termination condition, and there are three common ones, usually checked together. The first is the end-of-sequence token: models are trained to emit a special EOS (or <|im_end|>, or a chat-template stop token) when a turn is complete, and the loop halts the moment that id is sampled — the model deciding, from the inside, that it is done. The second is a hard max-new-tokens budget, a safety cap so a model that never emits EOS (or gets stuck repeating) cannot generate forever and blow the latency and cost budget.

The third is a set of caller-supplied stop sequences: strings like "\n\n", "User:", or a closing code fence that, when they appear in the decoded output, end generation — useful for structured formats and multi-turn transcripts where the natural boundary is not the model’s own EOS. Because stop sequences are defined on decoded text rather than token ids, they must be checked against the detokenized tail each step, and a stop string can straddle a token boundary — a subtlety worth handling carefully. Whichever criterion fires first wins, and the number of tokens actually produced, N, is what the latency math below multiplies.

Latency vocabulary: TTFT, inter-token latency, tokens/sec

The two-phase structure maps directly onto the numbers users feel. Time to first token (TTFT) is the wait from submitting the request to seeing the first generated token appear; it is dominated by prefill — the model must process the entire prompt before it can produce anything — so TTFT grows with prompt length. Inter-token latency (ITL), also called time-per-output-token, is the gap between successive streamed tokens during decode; it is the memory-bound step time and is roughly constant per token. Its reciprocal, tokens per second = 1 / ITL, is the streaming rate a reader watches scroll by.

Total end-to-end latency for an N-token reply is then simply:

total_latency  ≈  TTFT  +  (N - 1) × ITL
tokens_per_sec ≈  1 / ITL          (single stream, steady state)

These two numbers trade off differently and are optimized differently. TTFT is a compute-bound, one-time cost you attack with faster prefill (more cores, chunked prefill, a shorter or cached prompt). ITL is a memory-bound, per-token cost you attack with smaller weights (quantization) and higher effective bandwidth. A chatbot lives or dies on TTFT; a long document generation lives or dies on ITL. Quoting one without the other hides half the story.

A worked latency example

Put numbers on it for a CPU-hosted small model. Take a 3-billion-parameter model quantized to int8, so the weights occupy about 3×10^9 × 1 byte = 3 GB. Run it on a CPU with 50 GB/s of usable memory bandwidth and, say, 500 GFLOP/s of sustained compute. The prompt is P = 128 tokens and the model generates N = 200 tokens.

DECODE (memory-bound): read all weights once per token
  ITL   ≈ 3 GB / 50 GB/s        = 0.060 s   = 60 ms / token
  rate  ≈ 1 / 0.060             ≈ 16.7 tokens / sec

PREFILL (compute-bound): ~2 · P · params FLOPs
  FLOPs ≈ 2 × 128 × 3e9     = 7.7e11 FLOPs
  TTFT  ≈ 7.7e11 / 500e9        ≈ 1.5 s

TOTAL for a 200-token reply
  total ≈ TTFT + (N-1) · ITL = 1.5 + 199 × 0.060 ≈ 13.5 s

Read the story in the numbers. The user waits ~1.5 s for the first token, then watches text stream at ~17 tokens/sec. Decode dominates the total (12 s of 13.5 s) because the reply is long. Now apply the levers: quantizing to int4 halves the weight bytes to 1.5 GB, cutting ITL to ~30 ms and doubling the stream to ~33 tokens/sec — a pure memory-bandwidth win. Throwing more FLOP/s at the same machine would speed up the 1.5 s prefill but do nothing for the 12 s of decode, because decode never had a compute problem. The math tells you exactly which knob to turn.

Throughput vs latency: batching and the memory-bound win

The worked example is a single stream, and its 16.7 tokens/sec badly under-uses the machine: while the memory bus is saturated streaming weights, the compute units are mostly idle. That idle compute is free throughput waiting to be claimed, and batching claims it. Run B independent generations in lockstep and each weight, loaded once, serves all B tokens at that step — the same load, B times the useful work.

So decode’s arithmetic intensity climbs from one toward B, and aggregate throughput scales with B until the batch grows compute-bound or the KV caches exhaust memory. The catch is that batching helps throughput, not single-stream latency: any one user’s ITL is no faster (and can be slightly slower). This is the fundamental serving tension — latency per request versus tokens per second across all requests — and it is why real servers use continuous batching, slotting new requests into a running batch as others finish rather than waiting to assemble a fixed batch. On a CPU SLM, where bandwidth is the scarce resource and spare cores are common, even a small batch can multiply total tokens/sec at almost no cost to any individual stream — the clearest practical payoff of understanding that decode is memory-bound.

CPU-SLM implications and common pitfalls

Everything above sharpens into a short checklist for running a small model on a CPU. Because decode is memory-bound, quantization is your primary speed knob: fewer bytes per weight means proportionally lower inter-token latency, full stop. Because prefill is compute-bound, long prompts are the TTFT tax; trim, cache, or chunk them, and remember that a reused system prompt can have its KV cache computed once and kept warm. Because the KV cache grows every token, a long conversation is a memory problem, not a compute one — budget it as 2 · L · n_kv_heads · d_head per token and watch it, since it eventually competes with the weights for bandwidth in the ITL formula.

The recurring pitfalls all trace to ignoring the structure. Forgetting to enable the KV cache silently restores the O(N^2) recompute and can make generation an order of magnitude slower. Quoting a headline tokens/sec measured on a trivial prompt hides a TTFT that balloons on real inputs. Trying to buy decode speed with more compute is spending on the wrong resource. And measuring generation latency without separating prefill from decode blends two costs with different cures into one uninterpretable number. Split the phases, name TTFT and ITL, and the right optimization is almost always obvious.