Chapter 8

Autoregressive Generation and Efficient Inference

Follow generation through prompt prefill and repeated one-token decoding. Derive what a key-value cache stores, how its shapes and memory grow, and how to verify that cached and uncached computation produce the same logits.

A trained decoder produces one vocabulary-logit row for the next token. To generate a sequence, an inference loop chooses a token from that row, appends it to the context, and asks the model for another row.

This chapter reuses the trained 368-parameter model from Chapter 7. No parameter changes during generation. The work separates into three parts:

  1. the model calculates logits from a known prefix;
  2. a decoding policy chooses the next token;
  3. a key-value cache reuses stable attention projections from earlier tokens.

Changing the policy can change the selected token. A correct cache must not change logits beyond the declared floating-point tolerance.

The frozen model has a context length of four input positions. It can use the fourth position to predict a fifth token such as <eos>, but it cannot feed that fifth token back as another input. This small limit makes stopping and position accounting visible.

The complete CPU artifact compares every valid prefix of the four-pattern corpus. Its largest cached-versus-uncached logit difference is 4.7684×10−64.7684\times10^{-6}, below the frozen tolerance 10−510^{-5}.

After this chapter

  • Separate prompt prefill from one-token decode computation.
  • Track key-value cache shapes, positions, and memory growth.
  • Verify numerical equivalence between cached and uncached logits.

Lessons

  1. 01
    Generation Repeats Prediction and Appending

    Trace an autoregressive generation loop through prefix logits, token selection, append, EOS, context, and step limits.

    1 exercise
  2. 02
    Decoding Policy Acts on Fixed Logits

    Compare greedy decoding, temperature scaling, top-k filtering, sampling, seeds, and reproducible token selection from fixed logits.

    1 exercise
  3. 03
    Prefill and Decode Perform Different Work

    Understand Transformer prompt prefill and one-token decode phases, tensor shapes, cache creation, and repeated generation state.

    1 exercise
  4. 04
    A KV Cache Stores Layer-Specific Keys and Values

    Derive KV-cache contents, per-layer tensor shapes, query-key-value roles, scalar counts, and memory payload during incremental decoding.

    1 exercise
  5. 05
    Decode One Token against the Cached Prefix

    Trace a one-token cached Transformer decode with QKV projection, cache append, attention scores, residual updates, and logits.

    1 exercise
  6. 06
    Position Indices Must Continue through the Cache

    Track absolute position indices, consumed tokens, returned tokens, cache length, and context limits during cached generation.

    1 exercise
  7. 07
    Cached and Uncached Logits Must Match

    Verify KV-cache correctness by comparing cached and uncached logits, testing tolerances, prefixes, positions, layers, and failure interventions.

    1 exercise
  8. 08
    Caching Trades Recalculation for Growing Memory

    Analyze KV-cache compute reuse, dense attention work, memory growth, latency limits, and bounded inference claims.

    1 exercise
  9. 09
    Batches, Stopping, and Context Limits Complicate Decode

    Handle batched cached decoding with unequal lengths, padding masks, EOS, context limits, request isolation, and stopping records.

    1 exercise
  10. 10
    Audit Generation and Cache State

    Audit Transformer generation and KV-cache state with invariants, failure signatures, controlled interventions, and dependency-ordered debugging.

    1 exercise

Review and practice

  1. •
    Review

    Review autoregressive generation, decoding policies, prefill, one-token decode, KV-cache shapes, memory, equivalence, and debugging.

  2. •
    Exercises

    Solve Transformer generation and KV-cache exercises on policies, shapes, scores, positions, memory, equivalence, stopping, and debugging.

Chapter progress