Autoregressive Generation

Phase 2 · Document 05 · Transformer Foundations Prev: 04 — LayerNorm and Residuals · Next: 06 — KV Cache

Table of Contents

1. Why This Matters
2. Core Concept
3. Mental Model
4. Hitchhiker's Guide
5. Warmup Readings
6. Deep Readings and External References
7. Key Terms
8. Important Facts
9. Observations from Real Systems
10. Common Misconceptions
11. Engineering Decision Framework
12. Hands-On Lab
13. Verification Questions
14. Takeaways
15. Artifact Checklist

1. Why This Matters

Autoregressive generation is the loop that turns a next-token predictor into a text generator — and it's the source of three production realities: generation is inherently serial (each token depends on the last, which caps speed), latency is proportional to output length (TPOT × tokens), and the sampler (Phase 1.03) decides which token gets appended. Every speed optimization you'll meet — KV cache, speculative decoding, MTP — exists to fight the serial nature of this loop. Understanding it is what lets you reason about why streaming helps perception but not total time, and why "just generate less" is the most reliable cost/latency lever.

2. Core Concept

The loop

tokens = tokenize(prompt)
while not done:
    logits   = model(tokens)          # full forward pass (KV cache makes this incremental)
    next_id  = sampler(logits[-1])    # temperature/top-p/top-k pick ONE token
    tokens.append(next_id)
    if next_id == EOS or stop_hit or len(generated) == max_tokens:
        done = True

Each iteration produces exactly one token, appended to the sequence, then the model runs again. This is autoregressive: the output so far becomes part of the input for the next step.

Why it's serial (and why that's the core constraint)

You cannot generate token t+1 until you know token t, because t is part of the input that produces t+1. So decoding is fundamentally sequential — unlike prefill, which processes the whole prompt in parallel (07). This serial dependency is why:

• Per-token latency (TPOT) sets a hard floor on generation speed.
• Total latency ≈ TTFT + TPOT × output_tokens — output length is a first-class cost/latency driver.
• GPUs are underutilized during decode (one token's worth of work at a time) → batching across requests is how throughput is recovered (Phase 1.05).

Decoding strategies

• Greedy: always take the argmax token. Deterministic; can be repetitive.
• Sampling: draw from the (temperature/top-p/top-k/min-p–shaped) distribution. The standard for natural text. (See Phase 1.03.)
• Beam search: keep several candidate sequences and expand the best — common in translation, rarely used for open-ended chat (it tends to produce bland, repetitive text and is expensive).

Stopping

Generation ends at the EOS (end-of-sequence) token, a user stop sequence, or max_tokens. Forgetting max_tokens means the model runs until EOS or the context limit — an open-ended cost (Phase 1.03).

Streaming and beating the serial limit

• Streaming emits each token as it's produced (SSE). It improves perceived latency (user sees output immediately) but not total time — the loop is unchanged.
• To actually speed the loop, you must produce more than one token per model step: speculative decoding (a small draft model proposes several tokens, the big model verifies them in one pass) and MTP / multi-token prediction (the model is trained to predict several next tokens at once). Both preserve output quality while cutting wall-clock time (Phase 6).

3. Mental Model

PREDICT → SAMPLE → APPEND → REPEAT   (one token per turn; the future depends on the present)

   prompt ──prefill──► [logits] ─sample─► t1 ─► [logits] ─sample─► t2 ─► … ─► EOS
                          ▲                         ▲
                          └── serial: t2 needs t1, t3 needs t2 … (can't parallelize decode)

  total_time ≈ TTFT + TPOT × output_tokens
  fewer output tokens  = the most reliable latency & cost win
  streaming = same total time, better PERCEIVED speed
  speculative decoding / MTP = >1 token per step = real speedup, same quality

4. Hitchhiker's Guide

What to understand first: generation is a serial predict-sample-append loop; output length directly drives latency and cost; the sampler chooses the token.

What to ignore at first: beam search internals (rare for chat) and the math of speculative verification — know what it buys (more tokens/step).

What misleads beginners:

• "Streaming makes it faster." It improves perception, not total time.
• "The model writes the whole answer at once." It's one token at a time.
• "Bigger max_tokens is safer." It's an open-ended cost; cap it.
• "Greedy is best because deterministic." Greedy is often repetitive; sampling at low temperature is usually better for natural text.

How experts reason: they treat output tokens as the most controllable cost/latency lever (cap max_tokens, prompt for concise output, avoid needless reasoning tokens), use streaming for UX, and reach for speculative decoding/MTP when they need real decode speedups.

What matters in production: max_tokens discipline, stop sequences for clean termination, streaming for UX, and decode-acceleration (speculative/MTP) for latency-critical paths.

How to verify: measure TPOT and confirm total time scales with output length; verify a stop sequence actually terminates generation; check that speculative decoding preserves output vs the base model.

Questions to ask providers: Is streaming supported? Is speculative decoding/MTP used? How is max_tokens billed if hit? Are reasoning tokens counted toward output?

What silently gets expensive: unbounded/large max_tokens; verbose outputs; reasoning models emitting long hidden chains; retries that regenerate full outputs.

5. Warmup Readings

6. Deep Readings and External References

7. Key Terms

8. Important Facts

• Generation is autoregressive and serial — token t+1 needs token t; decode cannot be parallelized within a request.
• Total latency ≈ TTFT + TPOT × output_tokens — output length is a first-class driver.
• max_tokens is the most reliable latency/cost lever — always set it.
• Streaming improves perceived latency, not total time.
• Greedy = deterministic but often repetitive; sampling (low temp) is usually better for natural text.
• Beam search is rare for open-ended chat (bland/repetitive, expensive).
• Speculative decoding and MTP produce >1 token per step, cutting wall-clock time while preserving quality.
• Decode underutilizes the GPU per request → batching recovers throughput (Phase 1.05).

9. Observations from Real Systems

• OpenAI/Anthropic APIs stream tokens by default in chat UIs — perceived-latency UX over a serial loop.
• vLLM/TGI/SGLang implement speculative decoding to accelerate decode; vLLM also offers prefix caching to cut prefill.
• Unsloth's "Gemma MTP — ~2× faster" (the Phase 2 screenshot) is multi-token prediction beating the serial limit — and a reminder that "2×" is environment-specific (Phase 0.02).
• Reasoning models (o-series, thinking models) generate long hidden token chains before the answer — the same loop, but more (billed) output (09).
• llama.cpp/Ollama stream tokens and expose num_predict (their max_tokens) — the stop control made concrete.

10. Common Misconceptions

11. Engineering Decision Framework

Reduce latency/cost of generation:
  1. Generate FEWER output tokens — cap max_tokens, prompt for brevity, avoid needless reasoning.
  2. Use STREAMING for perceived speed in user-facing UIs.
  3. For real decode speedup → speculative decoding / MTP (Phase 6/7).
  4. Recover throughput → continuous batching across requests (Phase 1.05/7).

Pick a decoding strategy:
  deterministic/extraction/code → greedy / temp≈0 (Phase 1.03).
  natural conversation/creative → low-to-moderate temperature sampling.
  open-ended chat               → avoid beam search.

Always: set max_tokens + appropriate stop sequences.

12. Hands-On Lab

Goal

Implement the autoregressive loop yourself against a small model, compare greedy vs sampling, and measure how latency scales with output length.

Prerequisites

• Python 3.10+, transformers, torch (CPU fine for GPT-2).

Setup

pip install transformers torch

Steps

import time, torch
from transformers import AutoTokenizer, AutoModelForCausalLM

tok = AutoTokenizer.from_pretrained("openai-community/gpt2")
model = AutoModelForCausalLM.from_pretrained("openai-community/gpt2").eval()

def generate(prompt, max_new=40, greedy=True, temp=1.0):
    ids = tok(prompt, return_tensors="pt").input_ids
    t0 = time.perf_counter()
    for _ in range(max_new):
        with torch.no_grad():
            logits = model(ids).logits[0, -1]          # next-token logits
        if greedy:
            nxt = int(logits.argmax())
        else:
            probs = torch.softmax(logits / temp, -1)
            nxt = int(torch.multinomial(probs, 1))
        ids = torch.cat([ids, torch.tensor([[nxt]])], dim=1)
        if nxt == tok.eos_token_id: break
    dt = time.perf_counter() - t0
    gen = tok.decode(ids[0, -max_new:])
    return gen, dt, ids.shape[1]

print("GREEDY:", generate("The future of AI is", greedy=True)[0])
print("SAMPLE:", generate("The future of AI is", greedy=False, temp=1.0)[0])

# Latency vs output length
for n in (10, 40, 80):
    _, dt, _ = generate("Once upon a time", max_new=n)
    print(f"max_new={n:>3}  time={dt*1000:.0f}ms  ~TPOT={dt/n*1000:.1f}ms")

Expected output

• Greedy output is stable; sampled output varies between runs.
• Generation time grows roughly linearly with max_new (constant-ish TPOT) — the serial loop made visible.

Debugging tips

• Note: this naive loop recomputes the whole sequence each step (no KV cache) — that's the next document's optimization; here it exaggerates the per-token cost, which is fine for the demo.
• Sampling identical to greedy? You set temp≈0.

Extension task

Add top-p filtering before sampling; add a stop sequence (terminate when the decoded text contains "\n\n").

Production extension

Run the same prompts against a real API with stream=True; measure TTFT vs TPOT and confirm total time ≈ TTFT + TPOT×tokens (reuse Phase 1.05 lab).

What to measure

Greedy vs sampling variance; time vs output length (linearity); approximate TPOT.

Deliverables

• A from-scratch autoregressive generator.
• A latency-vs-output-length table showing linear scaling.
• A note: why streaming doesn't change this total, and what does (spec decoding/MTP).

13. Verification Questions

Basic

1. Why is autoregressive decoding inherently serial?
2. Write the formula for total generation latency.
3. What three things can stop generation?

Applied 4. Your TPOT is 25 ms and you generate 600 tokens. Estimate generation time and propose two ways to cut it. 5. Why does streaming improve UX but not total time?

Debugging 6. A request occasionally runs for 30 s and costs a lot. What's the most likely config mistake? 7. Outputs are bland and repetitive. Which decoding choice is likely responsible?

System design 8. Design generation settings for a latency-critical autocomplete feature vs a long-form report generator.

Startup / product 9. Your per-request cost is dominated by output tokens. Give three product/engineering changes (and why) to cut it without hurting perceived quality.

14. Takeaways

1. Generation is a serial predict→sample→append loop; the future depends on the present.
2. Total latency ≈ TTFT + TPOT × output_tokens — output length is the key lever.
3. Always cap max_tokens and use stop sequences.
4. Streaming = better perception, same total time.
5. Speculative decoding / MTP beat the serial limit by producing >1 token/step.
6. Generating fewer tokens is the most reliable cost/latency win.

15. Artifact Checklist

• Code: from-scratch autoregressive generator (greedy + sampling).
• Benchmark: latency-vs-output-length table (linearity).
• Notes: streaming vs real speedups (spec decoding/MTP).
• Config rule: your max_tokens/stop defaults by use case.
• Diagram: the decode loop with the serial dependency.
• Decision record: generation settings for one latency-critical feature.

Next: 06 — KV Cache