Below the API

Autoregressive Generation

Basic Intermediate 1h Difficulty 2/5

Prerequisites 03

1. What is it?#

Generating a sequence one element at a time, where each new element is conditioned on all previous ones — including the ones the model itself just generated.

P(x₁, x₂, ..., xₙ) = P(x₁) · P(x₂|x₁) · P(x₃|x₁,x₂) · ... · P(xₙ|x₁...xₙ₋₁)

In practice:

prompt → model → token 1
prompt + token1 → model → token 2
prompt + token1 + token2 → model → token 3
...

2. Why does it exist?#

Because that’s how the model was trained: predict the next token given all previous tokens. It’s the only thing the model knows how to do. Everything else — chat, reasoning, code generation, tool use — is this one operation applied repeatedly with clever prompting.

The engineering consequence is severe: generation is inherently serial. You cannot parallelize across the output length. A 1,000-token response requires 1,000 sequential forward passes, no matter how much hardware you have.

3. Simple analogy#

Improvising a story one word at a time, out loud, in front of an audience.

You cannot say word 50 before word 49. You cannot skip ahead and fill in the middle. Each word narrows what comes next. And because you can never take a word back, an early mistake propagates through everything that follows.

That last property — error accumulation — is why quantization degrades long generations more than short ones (Section III.12), and why a single bad token can derail an entire response.

4. Tiny example#

The generation loop, complete:

// Model is the only thing generation needs from an engine.
type Model interface {
	Prefill(ids []int) (logits []float32, cache KVCache)               // whole prompt, one pass
	Decode(token int, cache KVCache) (logits []float32, next KVCache) // one token, reuses the cache
}

func Generate(m Model, prompt []int, maxNew, eos int, temperature, topP float64) []int {
	// ---- PREFILL ----
	logits, cache := m.Prefill(prompt) // logits for the LAST position only

	var generated []int
	for len(generated) < maxNew {
		// ---- SAMPLE ----
		next := sampleTopP(logits, temperature, topP)
		if next == eos {
			break
		}
		generated = append(generated, next)

		// ---- DECODE STEP ----
		logits, cache = m.Decode(next, cache) // the cache grew by 1 token
	}
	return generated
}

// sampleTopP: temperature, softmax, keep the smallest set of tokens whose probability
// adds up to topP (the "nucleus"), then draw one of them.
func sampleTopP(logits []float32, temperature, topP float64) int {
	type cand struct {
		id int
		p  float64
	}
	maxLogit := float64(slices.Max(logits))
	cands, sum := make([]cand, len(logits)), 0.0
	for i, l := range logits {
		cands[i] = cand{i, math.Exp((float64(l) - maxLogit) / temperature)}
		sum += cands[i].p
	}
	slices.SortFunc(cands, func(a, b cand) int { return cmp.Compare(b.p, a.p) })

	keep, cum := 0, 0.0
	for keep < len(cands) && cum < topP*sum { // nucleus filter
		cum += cands[keep].p
		keep++
	}
	r := rand.Float64() * cum
	for _, c := range cands[:keep] {
		if r -= c.p; r <= 0 {
			return c.id
		}
	}
	return cands[keep-1].id
}

That is a complete LLM inference engine — minus batching, memory management, and everything that makes it fast. Project 04 extends this; Projects 05-09 make it production-grade.

Note the structure: one prefill call, then N decode calls. The cache value is the KV cache (file 05), growing by one token per iteration.

5. Technical explanation#

The serial dependency and its consequences#

Time to generate N tokens = TTFT + (N-1) × ITL

You cannot reduce N.
You cannot parallelize across N.
You can only reduce ITL, or produce more than one token per step.

The second escape is what speculative decoding (file 12) and multi-token prediction exploit. They’re the only techniques that break the “one forward pass per token” rule.

Stopping conditions#

1. EOS token generated              (model decides it's done)
2. max_tokens reached               (client-specified limit)
3. Stop string matched              (client-specified; see file 02)
4. Client disconnected              (must be detected and acted on!)
5. Timeout                          (server-side safety)
6. Max context reached              (prompt + generated = model's limit)

Condition 4 is the one people forget and it costs real money. In a chat product, 10-30% of generations are abandoned. If you don’t detect the disconnect and abort, you generate thousands of tokens nobody will read while holding a KV slot. Detecting it is equivalent to a 10-30% capacity increase.

Error accumulation#

P(correct sequence of N tokens) ≈ (1 - ε)^N

If each token has a 0.1% chance of being a “bad” choice that derails the response:

N=10:    99.0% chance of a clean response
N=100:   90.5%
N=1000:  36.8%

This isn’t a precise model, but the intuition holds: long generations are qualitatively harder, and small per-token quality regressions compound. It’s why:

  • Long-form quality degrades more from quantization than short-answer benchmarks suggest.
  • Chain-of-thought reasoning benefits disproportionately from a better model.
  • Beam search and self-consistency exist.

Why you can’t “just parallelize”#

People often ask: why not predict tokens 1-100 all at once and then refine?

The model computes P(x_t | x_1..x_{t-1}). To compute P(x_2 | x_1) you need x_1.
Predicting x_2 without x_1 means computing P(x_2) marginalized over x_1 —
which the model was never trained to do and which loses the conditioning
that makes the output coherent.

Speculative decoding gets around this by guessing x_1..x_k with a cheap model and then verifying them all in one parallel pass with the expensive model — accepting the prefix that matches. It works because verification is parallel even though generation isn’t.

6. Under the hood#

What changes between decode steps:

Constant:  weights (read every step, never modified)
           model architecture
Growing:   KV cache (one token per step per sequence)
           position index
Changing:  the single input token
           the sampling RNG state

That’s it. The model is stateless; the cache is the state. This is why a sequence’s state is exactly its KV cache blocks plus a few integers — and why moving a request between GPUs means moving its KV cache (Section XIII.06).

7. Performance implications#

  • The generation length distribution determines your capacity. A workload with a mean of 100 output tokens and one with a mean of 2,000 have 20x different costs per request.
  • Long-tail generations dominate. With a heavy-tailed distribution, a few very long generations hold slots for minutes.
  • max_tokens is a capacity control, not just a client convenience. Enforce a server-side cap.
  • Abandoned generations are pure waste. Instrument the abort rate.

8. Production implications#

  • Propagate client disconnects to the engine. In FastAPI/Starlette, check await request.is_disconnected(); in the engine, call the abort API. This is the highest return-on-effort item on the list.
  • Enforce a server-side max_tokens cap even if clients don’t set one.
  • Add a stall timeout: if no token has been produced in N seconds, something is wrong.
  • Track the output-length distribution as a first-class metric. It drives capacity planning.
  • Consider length prediction for scheduling: some systems estimate output length to make better admission decisions (an active research area, Section XIV).

9. Common mistakes#

Not aborting on disconnect. 10-30% of your capacity, wasted.

No server-side max_tokens cap. One client sets 100,000 and holds a slot for ten minutes.

Recomputing the full sequence each step (forgetting use_cache=True). Turns O(N) into O(N²). Easy to do in custom code, and the symptom is generation that gets slower and slower.

Assuming generation length is predictable. It isn’t.

Evaluating on short generations only.

10. Hands-on exercise#

A. Build the loop. Implement the generate function from section 4 from scratch. Verify it produces coherent text.

B. Prove the cache matters. Run generation with use_cache=True and use_cache=False. Plot per-token latency vs token index for both. Explain the shapes. (Without cache you’ll see linear growth; with cache, near-flat.)

C. Error accumulation. Generate 500 tokens from the same prompt and seed with FP16 and with an INT4-quantized model. Find the first token index where they diverge. Repeat for 50 prompts and plot the distribution.

D. Abandonment cost. Simulate a workload where 20% of requests are abandoned at a random point. Compute the wasted GPU time with and without abort propagation.

E. Length distribution. Collect the output-length distribution from a real chat log (or generate one). Fit a distribution. What’s the p50, p95, p99? How much capacity do the top 1% of requests consume?

11. Interview questions#

  1. Why is autoregressive generation inherently serial?
  2. Why can’t you generate multiple tokens in parallel? What technique gets around this and how?
  3. List the stopping conditions for a generation. Which one is most commonly mishandled?
  4. What happens to your capacity if you don’t handle client disconnects?
  5. Why does error accumulate in long generations, and what does that imply for evaluating quantization?
  6. What is the state of an in-flight request, and why does that make replicas stateful?

12. Further reading#

  • [FUNDAMENTAL] Any language modeling introduction covering the chain rule of probability
  • [ESTABLISHED] Leviathan et al., “Speculative Decoding” (2022) — the parallelization escape
  • [REFERENCE] HuggingFace generate() source — read it once to see all the stopping logic
  • Next: 05 — The KV cache
esc

↑↓ navigate ↵ open