Autoregressive Generation › Autoregressive Generation

When you ask a language model to complete the sentence "The cat sat on the", it doesn't produce the entire response at once. Instead, it generates text one token at a time, each new token conditioned on all the tokens that came before. This process, called autoregressive generation, is the basic mechanism by which decoder-only transformers like GPT produce coherent, contextually appropriate text. The word "autoregressive" comes from time-series modeling: a process is autoregressive when each new value in a sequence depends on the values that came before it, feeding back into itself. In language modeling, every new token is conditioned on the entire history of previously generated tokens, making the model literally "regress" on its own prior outputs.

Understanding autoregressive generation is needed for working with modern language models. The process seems simple on the surface: predict the next token, append it to the sequence, and repeat. But underneath this simple loop lies a computational challenge that has driven significant research into efficiency optimizations. The key insight is that naive generation would recompute the same attention calculations repeatedly, wasting enormous amounts of compute. The solution, key-value caching, transforms generation from quadratically expensive to linearly efficient. This single optimization is what makes practical deployment of large language models possible: without it, generating a single paragraph would take minutes even on powerful hardware.

Think of autoregressive generation like a skilled improviser building a story out loud. Each word they speak constrains and informs the next. They can't go back and revise what they've already said; each new word must follow from the entire context established so far. The model faces exactly the same constraint: each token decision is permanent and becomes part of the context for all future decisions. This one-way, committed nature of generation is both a strength, because it keeps outputs coherent and contextually grounded, and a limitation, because errors early in a sequence can compound and distort everything that follows.

The mathematical foundation of autoregressive generation is the chain rule of probability. Any joint probability over a sequence of tokens can be exactly factored into a product of conditional probabilities: the probability of the first token, times the probability of the second token given the first, times the probability of the third given the first two, and so on. This factorization is not an approximation; it is mathematically exact. The practical question is how well a neural network can approximate each conditional probability. GPT-style transformers turn out to be extraordinarily effective at this task, capturing subtle long-range dependencies through their attention mechanism.

Beyond the mathematical elegance, there is a practical engineering story here. Early language models computed autoregressive generation straightforwardly, paying a quadratic cost in sequence length at every step. As contexts grew from dozens of tokens to thousands, this cost became prohibitive. The invention of key-value caching reduced that cost to linear, making the long-context capabilities of modern chat assistants, code generation tools, and document summarizers practical. Understanding this optimization is not just academic: it shapes deployment decisions, memory budgets, and the architectural choices made in models like GPT-4 and Llama.

This chapter explores the mechanics of autoregressive generation in detail. We'll implement the generation loop from scratch, understand why KV caching is important for practical deployment, examine stopping criteria that determine when generation ends, and explore techniques for optimizing generation speed. By the end, you'll understand how generation works inside the model, from the probability factorization that justifies the approach through the memory arithmetic that determines whether a given model can fit in your GPU.