Autoregressive Generation: How GPT Produces Text

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.

Autoregressive generation follows a straightforward principle: at each step, the model predicts a probability distribution over possible next tokens, selects one token from that distribution, appends it to the sequence, and repeats until some stopping condition is met. This loop is deceptively simple to describe but rich with design decisions. Which token do you select from the distribution? Do you always take the highest-probability token, or do you sample? How do you decide when to stop? Each of these choices substantially affects text quality and diversity, as well as coherence.

The generation procedure has two distinct phases. The first is the prefill phase, where the model processes the entire input prompt in parallel. Because all prompt tokens are known in advance, the transformer can compute all their representations simultaneously, taking advantage of the GPU's parallel processing capabilities. This phase is relatively fast even for long prompts. The second is the decode phase, where the model generates new tokens one at a time. Each new token depends on all previous tokens, so this phase is inherently sequential: you cannot compute token $t+1$ until you have committed to token $t$. This sequential bottleneck is what makes inference fundamentally different from training, and it is the primary engineering challenge in building fast language model serving systems.

Think of the prefill/decode split as analogous to reading a document versus dictating a response. Reading (prefill) is fast because your eyes can scan the entire page at once. Dictating (decode) is slower because each word must be chosen and spoken before you can choose the next. No matter how fast your thinking, you are bounded by the sequential nature of speech. Similarly, no matter how much GPU parallelism is available, decode is bounded by its step-by-step dependency structure.

The process begins with a prompt, a sequence of tokens provided by the user. The model processes this prompt to produce hidden states, then uses the final hidden state to predict the first generated token. This token is appended to the prompt, the model processes the extended sequence, and the cycle continues. Each iteration of this loop produces exactly one new token. The model does not "plan ahead" or "commit" to a sentence structure in advance; it simply picks the locally most reasonable next token given everything so far. This myopic, one-step-at-a-time nature is both a feature and a limitation: it keeps generation computationally tractable, but it means the model can back itself into corners that would require backtracking to escape.

Let's trace through exactly what happens at each step of generation. The mechanics here are worth understanding precisely because they reveal both why generation works and why it is expensive. Consider a simple 4-token vocabulary and a prompt of 3 tokens:

Each iteration of the loop performs a complete forward pass through the transformer. The input is the entire sequence assembled so far, including both the original prompt tokens and any tokens generated in previous iterations. The model computes representations for every position using multi-head self-attention, propagates those representations through feed-forward layers, and finally uses the representation at the last position to produce a distribution over the next token. The representations at all other positions are computed too, even though we only care about the last one. This redundancy, computing representations for positions whose outputs we discard, is precisely the inefficiency that key-value caching eliminates.

It is worth pausing to appreciate what "conditioned on all previous tokens" means computationally. The attention mechanism at each layer allows every position to attend to every earlier position. This means that when predicting token $t$, the model can draw on information from any token in the prompt or any previously generated token. The representation of the current position is not a fixed embedding; it is a function of the entire preceding context, computed fresh at every generation step. This is what allows transformers to maintain long-range coherence: they do not rely on a compressed "summary state" of the past (as RNNs do) but instead directly access any prior position through attention.

At each step, the model must process the entire sequence to maintain the correct attention patterns. The attention mechanism at position $i$ computes weighted sums over all positions $j \leq i$, so earlier tokens influence later predictions. This creates a computational challenge: as the sequence grows, each forward pass becomes more expensive. A sequence that started at 10 tokens will be 60 tokens long after 50 generation steps, and each of those 60-token forward passes is approximately 6 times more expensive than the original 10-token pass. The total work grows quadratically, not linearly, with the number of tokens generated.

This diagram illustrates why the model is "coherent": at step 3, when predicting whether to generate "mat", "floor", or "bed", the attention mechanism at the final position can directly inspect "sat" (the verb that demands a landing place) and "The cat" (the subject that constrains the space). The generated context is not compressed or summarized; it is fully accessible. This direct access to all prior context is what distinguishes transformer-based generation from RNN-based generation, where the prior context is compressed into a fixed-size hidden state that loses information over long distances.

The generation loop we've been exploring raises a basic question: how do we assign a probability to an entire sequence of tokens? Consider the sentence "The cat sat on the mat". It would be impractical to maintain a probability table for every possible sentence, as natural language allows infinitely many valid sequences. Instead, we need a way to decompose sequence probability into manageable pieces.

From Intuition to the Chain RuleLink Copied

Think about how you might estimate the likelihood of a sentence. You wouldn't evaluate it as a monolithic unit. Instead, you'd naturally consider: How likely is "The" as an opening word? Given that we started with "The", how likely is "cat" to follow? Given "The cat", how likely is "sat"? This intuitive approach of building probability step by step is exactly what autoregressive models formalize.

The mathematical foundation comes from the chain rule of probability, which states that any joint probability can be decomposed into a product of conditional probabilities. For a sequence of $T$ tokens, this gives us the autoregressive factorization:

where:

• $x_t$: the token at position $t$ in the sequence
• $T$: the total sequence length (number of tokens)
• $P(x_t | x_1, x_2, \ldots, x_{t-1})$: the conditional probability of token $x_t$ given all preceding tokens, often written as $P(x_t | x_{<t})$ for brevity
• $\prod_{t=1}^{T}$: the product over all positions from 1 to $T$

This factorization is powerful because it turns the impossible task of modeling all possible sentences into a tractable one: we only need to model what comes next given what we've seen so far. Each factor in the product corresponds to exactly one step of the generation loop.

A Concrete ExampleLink Copied

Let's trace through the factorization for our example sentence "The cat sat":

1. First token: $P(\text{"The"})$ asks how likely "The" is as an opening. Common sentence starters like "The", "A", "I" receive high probability.

2. Second token: $P(\text{"cat"} | \text{"The"})$ asks what noun is likely after "The". Words like "cat", "dog", "man", "house" all receive some probability mass.

3. Third token: $P(\text{"sat"} | \text{"The cat"})$ asks what action a cat might perform. "sat", "jumped", "ran", "slept" become likely candidates.

The full sequence probability is the product: $P(\text{"The"}) \times P(\text{"cat"} | \text{"The"}) \times P(\text{"sat"} | \text{"The cat"})$. If any factor is near zero, the entire product collapses. This reflects that an unlikely transition makes the whole sequence improbable.

This explains a key challenge in evaluating language models: sequence probabilities get very small very quickly. A sequence of 10 tokens, each with conditional probability 0.1, has a joint probability of $0.1^{10} = 10^{-10}$. This is why language models are typically evaluated using log-probability (summing log-probabilities rather than multiplying probabilities) and perplexity (the geometric mean inverse probability per token). These metrics avoid numerical underflow and give interpretable numbers even for long sequences.

The generation loop seems straightforward, but the naive implementation hides a severe performance problem. At each step, we feed the entire sequence, prompt plus all previously generated tokens, back through the model from scratch. The model recomputes every QKV projection for every token it has already processed. None of those computations change between steps: if token 5 is "cat", its key and value projections are identical whether we are computing step 6 or step 106. Yet the naive implementation throws away all this prior work at the end of each step and recomputes it from scratch at the next.

Think of naive generation as a student who, every time they need to answer the next question on an exam, re-reads the entire question paper from the beginning rather than remembering what they already read. The cost of each question answer grows linearly with how many questions have already been answered, making the total exam time grow quadratically with the number of questions. Key-value caching is the insight that you only need to read the new question, not the entire paper again.

Consider generating 100 tokens after a 50-token prompt. With naive generation, each step requires a full forward pass through the model. The first generated token requires processing 50 tokens. The second requires processing 51 tokens. The hundredth requires processing 149 tokens.

The total computation scales quadratically with sequence length because attention at each position must attend to all previous positions. To see why, consider that at generation step $i$, we must compute attention over a sequence of length $i$. The total number of attention operations across all $T$ generation steps is:

where:

• $T$: the total number of tokens generated
• $\sum_{i=1}^{T} i$: the sum of sequence lengths processed at each step (1 + 2 + 3 + ... + T)
• $\frac{T(T+1)}{2}$: the closed-form solution for this arithmetic series
• $O(T^2)$: big-O notation showing quadratic growth with sequence length

This quadratic relationship means that generating 1000 tokens requires roughly 1,000,000 attention operations proportionally, while generating just 100 tokens requires only about 10,000. The cost grows much faster than the output length.

For practical deployments where latency matters, this quadratic scaling is unacceptable. Generating a single response could take tens of seconds even on powerful hardware. The solution is to cache intermediate computations and reuse them across generation steps.

The key insight behind KV caching is that during autoregressive generation, the attention keys and values for positions 1 through $t-1$ don't change when we generate token $t$. Only the new token at position $t$ introduces new keys and values. Instead of recomputing everything, we cache the keys and values from previous positions and only compute the new entries. This changes the scaling: generation that was quadratically expensive becomes linearly expensive, making practical deployment of large language models feasible.

To understand why the keys and values are stable, recall how they are computed. Keys and values are linear projections of the token embeddings at each layer: $k_i = W_K h_i$ and $v_i = W_V h_i$, where $h_i$ is the hidden state at position $i$. In a decoder-only model, the hidden state at position $i$ depends only on tokens at positions $1$ through $i$ due to the causal mask. When we generate token $t+1$, the hidden state at position $i$ (for $i \leq t$) does not change, because the causal mask prevents position $i$ from attending to position $t+1$. This is the important invariant: adding new tokens to the right of the sequence cannot affect the representations of tokens already in the sequence. Therefore, all their keys and values remain valid from the previous step.

Think of the KV cache as a library where each book represents the compressed meaning of one input token as "seen" by each attention layer. Once a book has been written and shelved, it never changes; you only ever add new books to the right end of the shelf. When the model attends from the new token to all prior context, it reads from the existing library without re-reading or re-processing any prior books. The library grows by exactly one book per generation step, keeping the marginal cost of each step constant rather than growing.

To understand why KV caching helps, we first need to understand what happens in standard attention. In multi-head attention, for a sequence of length $T$, we compute QKV projections from the input, then use them to compute a weighted sum:

where:

• $Q \in \mathbb{R}^{T \times d_k}$: the query matrix containing a query vector for each of the $T$ positions
• $K \in \mathbb{R}^{T \times d_k}$: the key matrix containing a key vector for each position
• $V \in \mathbb{R}^{T \times d_v}$: the value matrix containing a value vector for each position
• $d_k$: the dimension of each key (and query) vector, typically 64 in GPT-2
• $QK^T \in \mathbb{R}^{T \times T}$: the attention score matrix where entry $(i, j)$ measures how much position $i$ attends to position $j$
• $\sqrt{d_k}$: a scaling factor that prevents the dot products from growing too large, which would push softmax into regions with vanishing gradients
• $\text{softmax}(\cdot)$: normalizes each row of the attention scores to sum to 1, creating attention weights

The formula works in three steps: (1) compute attention scores by taking dot products between queries and keys, (2) normalize scores with softmax to get attention weights, and (3) compute weighted sums of values using those weights.

During generation, we only need the query at the last position to predict the next token. But without caching, we must recompute the entire $K$ and $V$ matrices at every step because the attention mechanism requires all previous keys and values to compute the softmax normalization correctly.

With KV caching, we maintain running matrices $K_{\text{cache}}$ and $V_{\text{cache}}$ that accumulate the keys and values for all tokens processed so far. When generating token $t$:

1. Compute only $q_t$, $k_t$, $v_t$ for the new token (a single vector each)
2. Append $k_t$ to $K_{\text{cache}}$ and $v_t$ to $V_{\text{cache}}$ (cache grows by one row)
3. Compute attention using $q_t$ (single query) against the full cache

The attention computation for the new token becomes:

where:

• $q_t \in \mathbb{R}^{1 \times d_k}$: the query vector for the single new token at position $t$
• $K_{\text{cache}} \in \mathbb{R}^{t \times d_k}$: the cached key matrix containing keys for all $t$ positions seen so far
• $V_{\text{cache}} \in \mathbb{R}^{t \times d_v}$: the cached value matrix containing values for all $t$ positions
• $q_t K_{\text{cache}}^T \in \mathbb{R}^{1 \times t}$: a single row of attention scores (the new token attending to all previous positions)
• $\sqrt{d_k}$: the same scaling factor as before

The key insight is that $q_t K_{\text{cache}}^T$ produces just a single row of attention scores rather than a full $T \times T$ matrix. We compute $t$ dot products instead of $t^2$, reducing the per-step computation from $O(T^2)$ to $O(T)$. Over the full generation of $T$ tokens, this changes the total cost from $O(T^3)$ to $O(T^2)$, a dramatic improvement for long sequences.

The cache has grown from 10 to 11 positions after processing a single new token. Notice that the input to this step was just one token, not the entire sequence of 11. This is the efficiency gain: we only compute the new keys and values while reusing all previously cached entries.

The shapes reveal the broader efficiency principle. After the initial prompt, each generation step only processes a single token, but the cache grows to include all previous positions. The attention computation uses the single-token query against the full key cache. The computational cost per step is now $O(T)$ (one query dot-producted with $T$ cached keys), rather than $O(T^2)$ (the full attention matrix). Summed over $T$ generation steps, total cost is $O(T^2)$ rather than $O(T^3)$, a qualitative improvement that becomes more dramatic the longer the sequence grows.

The KV cache is per-layer. Each transformer layer maintains its own cache of keys and values, because each layer produces different projections. A model with 12 layers maintains 12 separate key caches and 12 separate value caches. This is why the memory formula for the KV cache includes the number of layers $L$ as a multiplicative factor: cache memory scales with both context length and model depth.

KV caching trades memory for computation. We gain speed by storing intermediate results, but this requires additional GPU memory that grows with sequence length. Understanding this trade-off is needed for deploying models with long context windows. In practice, KV cache memory often becomes the primary constraint on serving large language models: you might have enough GPU memory to load the model weights, but run out of memory when trying to maintain caches for many concurrent users with long conversations.

For a model with $L$ layers, $H$ attention heads per layer, head dimension $d$, batch size $B$, and sequence length $T$, the total cache memory requirement is:

where:

• $2$: accounts for storing both keys and values (two tensors per layer)
• $L$: number of transformer layers (each layer has its own cache)
• $B$: batch size (number of sequences being generated in parallel)
• $H$: number of attention heads per layer
• $d$: dimension of each head (typically $d_{\text{model}} / H$)
• $T$: current sequence length (grows during generation)
• $\text{sizeof(dtype)}$: bytes per element (4 for float32, 2 for float16/bfloat16)

The product $H \times d$ equals the model's hidden dimension $d_{\text{model}}$, so we can also write this as $2 \times L \times B \times d_{\text{model}} \times T \times \text{sizeof(dtype)}$. The key insight is that cache memory grows linearly with both model depth $L$ and sequence length $T$.

For GPT-2 Small (12 layers, 12 heads, 64-dimensional heads, giving $d_{\text{model}} = 768$) with float16 precision:

The custom CachedAttention implementation above reveals the mechanics, but in practice you will use the Hugging Face transformers library, which handles cache management automatically. The library's implementation is more complete: it handles multi-head attention, positional encodings, the interaction between the cache and the causal mask for mixed-length inputs, and GPU memory management. Understanding the principles from the custom implementation allows you to reason about what the library is doing under the hood, even when you do not implement it yourself.

Let's implement efficient generation with KV caching using the Hugging Face transformers library, which handles cache management automatically:

The speedup from KV caching becomes more pronounced with longer sequences. For production deployments, cached generation is needed for acceptable latency.

Generation must stop at some point. Without explicit stopping criteria, the model would continue generating tokens indefinitely, or until hitting a maximum length set by the system. Several strategies determine when to halt generation, and choosing the right one matters both for output quality and for computational efficiency. Stopping too early truncates incomplete thoughts; stopping too late wastes compute and may produce degenerate repetition.

The choice of stopping criterion is tightly coupled to the task. A question-answering system wants to stop when the answer is complete, not when some fixed token count is reached. A chat application wants to stop at the end of the assistant's turn, before starting the next user turn. A code generation tool might want to stop after a complete function definition. In each case, the optimal stopping criterion encodes task-specific knowledge about what "done" means, and generic length limits are a blunt instrument compared to structured stop conditions.

It is worth understanding how stop tokens are introduced during training. Models are trained on documents that naturally contain EOS tokens at their ends. When the training objective is to predict the next token given all previous ones, the model learns to assign high probability to the EOS token when it has "said everything there is to say" about a topic. This learned behavior transfers to generation: a well-trained model will produce EOS at the right moment naturally, which makes it the most semantically aware stopping mechanism available.

The most common stopping criterion is the end-of-sequence (EOS) token. During training, sequences end with a special token that signals completion. When the model generates this token, we stop:

The EOS token works well for tasks with natural endings, like completing a sentence or answering a question. However, some prompts don't have clear endpoints, and the model may never generate EOS. Instruction-tuned models are trained to use EOS reliably because their fine-tuning data includes explicit turn boundaries, but base language models trained purely on raw text may rarely emit EOS in open-ended generation. For base models, a length limit is often necessary as a safety net.

A hard maximum length prevents runaway generation:

For specific applications, we might want to stop when certain text patterns appear. This is common in chat applications where we stop at user turn markers:

The generation stopped as soon as it encountered one of our specified patterns. This is particularly useful for structured outputs where you know the format in advance, such as generating exactly three items in a list or stopping at the end of an assistant's turn in a conversation.

One practical implementation challenge with stop sequences is that they may span multiple tokens. The string "\n\n" (double newline) might tokenize to a single token in some tokenizers or to two separate newline tokens in others. The check must operate on the decoded text string rather than on token IDs, which means decoding the generated tokens at each step. This adds some overhead compared to a simple token-ID comparison, but it is the only reliable way to detect multi-token stop sequences. For performance-necessary applications, it is worth pre-tokenizing common stop sequences and checking token IDs directly when possible.

In practice, we often combine multiple criteria. The Hugging Face library supports this through StoppingCriteria objects:

Beyond KV caching, several techniques can accelerate generation. These optimizations are important for production deployments where latency directly impacts user experience. A user waiting for an AI assistant expects responses within seconds; a code completion tool must respond within milliseconds to avoid disrupting the programmer's flow. Meeting these latency requirements while serving thousands of concurrent users demands careful engineering at every layer of the stack.

The optimizations we explore in this section operate at different levels. Batch processing amortizes fixed costs by sharing them across multiple users. Mixed precision reduces the memory bandwidth required per operation, directly translating to faster computation on GPU hardware. Speculative decoding exploits the observation that a cheap model can correctly predict what an expensive model would have generated most of the time. Quantization goes further than half-precision, reducing weights to 8 bits or fewer. Continuous batching addresses the throughput problem of serving many users with different output lengths. These techniques are not mutually exclusive: production serving systems typically combine all of them.

The key mental model is to think about where time is being spent. For small batch sizes (a single user), generation is typically memory-bandwidth-bound: the bottleneck is loading model weights from GPU memory to the compute units, not the mathematical operations themselves. For large batch sizes, it becomes compute-bound: the GPU is fully utilized doing matrix multiplications. Mixed precision and quantization help in the memory-bandwidth-bound regime by shrinking the weights. Batching helps by moving into the compute-bound regime where the GPU is more fully utilized.

Processing multiple prompts simultaneously amortizes the overhead of loading model weights. The attention computation is parallelized across the batch dimension:

Batch generation processes all four prompts faster than running them one at a time. The speedup comes from amortizing the model loading overhead and parallelizing the attention computations across the batch dimension. This makes batching needed for high-throughput serving scenarios.

The efficiency gain from batching is most pronounced when the batch is large enough to keep the GPU fully occupied. A modern GPU has thousands of CUDA cores designed to work in parallel; a batch size of 1 typically leaves most of them idle during the matrix multiplications that dominate model computation. Increasing batch size from 1 to 16 might give a 10-15 times throughput improvement with only a modest latency increase, because the per-token cost is dominated by loading weights from memory, which is amortized across the batch. Beyond some point, increasing batch size further provides diminishing returns as the GPU becomes compute-bound rather than memory-bandwidth-bound.

Using half-precision (float16) or brain floating point (bfloat16) reduces memory bandwidth and enables faster computation on modern GPUs:

Cutting the model precision in half directly halves the memory footprint. This allows larger batch sizes or longer sequences to fit in the same GPU memory. On modern GPUs with tensor cores, float16 operations are also faster than float32. This provides both memory and speed benefits.

Speculative decoding uses a smaller "draft" model to propose multiple tokens, then verifies them with the larger model in a single forward pass. When predictions align, multiple tokens are accepted at once:

The effectiveness of speculative decoding depends on how well the draft model predicts the target model's outputs. When they agree frequently, significant speedups are possible, sometimes 2-4 times faster than standard generation. When they disagree often, the overhead of running two models provides little benefit, and it may be slower than just running the target model alone. The acceptance rate depends on the task: generating common phrases, code with predictable syntax, or formulaic responses tends to see high acceptance rates, while highly creative or unpredictable generation sees lower acceptance.

The main point behind why speculative decoding preserves output quality is that the rejection mechanism is mathematically calibrated to produce samples from the target model's distribution exactly, not approximately. When the draft token is rejected, the target model's distribution at that position is used to resample. This keeps the final output is statistically identical to what the target model would have produced without the draft. You get speed without sacrificing quality, though only when the draft model is accurate enough to provide a meaningful acceptance rate.

Reducing model precision further with quantization (8-bit, 4-bit, or even lower) enables faster inference with reduced memory:

For serving multiple users, continuous batching (also called in-flight batching) dynamically adds and removes sequences from a batch as they complete. This maximizes GPU utilization compared to static batching where all sequences must wait for the longest one. The difference is significant: with static batching, a batch containing one very long response and three short responses wastes three-quarters of its capacity while the long response is still being generated. With continuous batching, those three slots are freed up as soon as the short responses complete and immediately filled with new requests.

Think of continuous batching as analogous to a busy restaurant kitchen. A static batching kitchen would seat all tables only when all tables are empty, causing most tables to sit idle while a few slow diners linger. A continuous batching kitchen seats new parties as soon as any individual table clears, maximizing the number of customers served per hour. The analogy breaks down only in that the kitchen must serve all meals in a single GPU step: every sequence in the batch advances by exactly one token per iteration, so "clearing a table" and "seating a new party" both happen between iterations.

To solidify the mechanics, let's trace a concrete numerical example through the full generation pipeline. We will use a simplified vocabulary of six tokens: "The", "cat", "sat", "on", "the", and "mat", and a toy model with hidden dimension $d = 4$. The goal is to show exactly how each token is produced, from raw hidden states through logits and softmax to the final token selection.

Setup. Our prompt is "The cat" (2 tokens). After the prefill phase, the model has produced hidden states $h_1$ and $h_2$ for these tokens. We want to generate the third token.

Step 1: Get the logit vector. The language model head projects the hidden state at the last position to vocabulary logits:

Suppose the resulting logit vector is $\ell = [-2.1, \; 0.3, \; 3.1, \; 0.8, \; 0.1, \; -0.5]$, corresponding to the six vocabulary tokens in order.

Step 2: Apply softmax. We convert logits to probabilities using the softmax function. The maximum logit is $3.1$ (for "sat"), so we subtract this for numerical stability before exponentiating:

The sum of these values is approximately $1.244$. Dividing each by this sum gives the probability distribution:

Step 3: Select the next token. With greedy decoding, we pick the token with the highest probability. Token index 2 ("sat") has probability $0.804$, so it is selected. The sequence is now "The cat sat".

Step 4: Update the KV cache. The model computes keys and values for "sat" at each layer and appends them to the existing cache. The prompt's keys and values for "The" and "cat" remain unchanged in the cache.

Step 5: Repeat for the next token. The input to the next forward pass is the single token "sat" (not the entire sequence). The model computes its query vector, attends to the full key cache (covering "The", "cat", and "sat"), and produces logits for the fourth token position. If the logit for "on" is now the highest, the sequence becomes "The cat sat on".

This trace makes several things concrete. The probability assigned to "sat" was $0.804$, meaning the model was quite confident given the context "The cat". The other tokens received small but non-zero probability: "on" received $0.08$, which would have been correct if the sentence were "The cat sat on". Greedy decoding committed to "sat" because it was most likely, but sampling could have selected "on" or another token. The step-by-step nature is clear: each token is a separate computation, the result is committed immediately, and the cache is updated before the next step begins.

Why does this formula make sense? Notice that the softmax denominator ensures all probabilities sum to 1, making the output a valid probability distribution. The exponential function amplifies differences in logit values: "sat" with logit 3.1 receives probability 0.804, while "a" with logit 0.3 receives only 0.049, even though the logit difference is only 2.8. This amplification is what makes the model's high-confidence predictions dominant under greedy decoding.

Let's put everything together into a complete, production-quality generation function:

Autoregressive generation, while powerful, comes with inherent limitations that affect both capability and deployment. These limitations shape what language models can and cannot do, and they inform the engineering decisions made when building systems on top of them.

The sequential nature of generation creates a basic latency floor. No matter how fast each token can be generated, creating 100 tokens requires at least 100 sequential steps. This contrasts with encoding, where an entire sequence can be processed in parallel. For applications requiring very long outputs, this sequential bottleneck becomes significant. A 1000-token response at 50 tokens-per-second takes 20 seconds, no matter how many GPUs you throw at the problem, because the steps cannot be parallelized. Techniques like speculative decoding and parallel draft trees attempt to mitigate this, but the basic constraint remains: each token must be decided before the next one can be chosen.

The left-to-right commitment structure creates a related problem: errors early in generation compound downstream. If the model generates an incorrect premise in the third token, everything that follows will be conditioned on that error. The model cannot go back and revise; it can only attempt to recover within the constraints of what it has already committed to. This makes autoregressive generation fragile in ways that human writing is not: a human writer can revise a passage, while an autoregressive model is locked into its sequential choices. This limitation motivates techniques like chain-of-thought prompting (giving the model space to "think out loud" before committing to a final answer) and best-of-N generation (running the model multiple times and selecting the best output), but neither fully solves the basic problem.

KV cache memory grows linearly with sequence length, which can become problematic for very long contexts. A 7B parameter model with 32 layers and a 128K context window might require tens of gigabytes just for the cache. This has motivated research into cache compression techniques like sliding window attention, sparse attention patterns, and cache eviction strategies. Some systems maintain only a fixed-size cache of the most recent tokens, trading off the ability to attend to distant context for bounded memory usage. The choice between "full context" and "bounded context" is not purely technical: it affects what kinds of tasks the model can perform. Code generation that must reference a function defined 50,000 tokens earlier requires full context; a customer service chatbot that only needs the last few turns of conversation can work fine with a bounded cache.

The quality of generated text depends heavily on decoding strategy, and there is no universally best strategy. Greedy decoding, while deterministic and fast, often produces repetitive or generic outputs because it always selects the locally optimal token without considering how that choice constrains future options. A greedy decoder might commit to "The quick brown fox" even when a more interesting completion was available, because each individual word in that phrase was slightly more probable than its alternatives. Temperature sampling introduces diversity but can also produce incoherent text at high temperatures, where low-probability tokens are selected too often. Beam search explores multiple hypotheses simultaneously but tends toward generic, high-probability sequences and can be worse than sampling for creative tasks. Finding the right balance for each application requires experimentation, and the optimal strategy differs by domain: factual question answering, creative writing, code generation, and mathematical reasoning each have different optimal settings.

Finally, autoregressive generation has no mechanism for self-correction or planning. The model generates token by token without any explicit ability to evaluate whether the current trajectory is heading toward a good outcome. Humans writing a long document can pause, re-read, and restructure; autoregressive generation has no such facility. Research into "process reward models" and "tree-of-thought" prompting attempts to add higher-level planning on top of the base autoregressive mechanism, but these require additional inference compute and are not always practical at serving scale. Understanding this limitation helps calibrate expectations: autoregressive models are extraordinary pattern completers, but they are not planners, and tasks that require careful forward-looking reasoning expose this limitation.

Autoregressive generation is the basic process by which decoder-only transformers produce text. This chapter traced the mechanism from first principles, through its mathematical foundation in the chain rule of probability, through its computational implementation, and through the optimizations that make it practical at scale. This chapter covers:

• Generation loop: At each step, the model predicts a probability distribution over the vocabulary, samples or selects the next token, appends it to the sequence, and repeats until a stopping criterion is met.

• KV caching: By caching the key and value projections from previous positions, we avoid redundant computation during generation. This transforms the computational cost from quadratic to linear in sequence length, making practical generation possible.

• Stopping criteria: Generation can terminate via EOS tokens for natural endings, maximum length limits for bounded outputs, or custom stop sequences for structured outputs like chat turns.

• Speed optimizations: Batch processing and mixed precision reduce overhead. Speculative decoding plus quantization and continuous batching also make generation practical for production deployments.

• Memory trade-offs: KV caching trades memory for computation. For long sequences or large batch sizes, cache memory can become a significant constraint.

The generation procedure we've explored here forms the foundation for all the decoding strategies covered in subsequent chapters. Temperature scaling, top-k sampling, nucleus sampling, and repetition penalties all operate within this basic framework, modifying how we select the next token from the model's predicted distribution. The KV cache, the stopping criteria, and the optimization techniques are all orthogonal to these sampling choices: you can combine any decoding strategy with KV caching, any stopping criterion, and any precision level. This modularity is one of the strengths of the autoregressive framework: the core loop is simple, and each component can be optimized independently.

Two mental models are worth carrying forward. First, think of generation as a probability chain: every generated sequence is the product of a long chain of conditional probabilities, and the quality of the output depends on how well each link in the chain was estimated. Second, think of the KV cache as earned credit: every token the model has processed represents work that need never be repeated, and the cache is the mechanism by which that earned credit is stored and reused. Together, these two ideas capture both why autoregressive generation works, grounded probability theory applied at each step, and why it is efficient in practice, reuse of prior computation via caching.

When implementing autoregressive generation, these parameters have the most significant impact on behavior and performance:

• max_new_tokens: Maximum number of tokens to generate. Set based on your application's typical output length. Shorter limits reduce latency and memory usage. Longer limits allow more complete responses but increase the risk of degenerate outputs.

• temperature: Controls the randomness of token selection (covered in detail in the next chapter). Values below 1.0 make the distribution sharper, favoring high-probability tokens. Values above 1.0 flatten the distribution, increasing diversity. Use 0.0-0.3 for factual tasks, 0.7-1.0 for creative tasks.

• use_cache: Whether to use KV caching for efficient generation. Should almost always be True for inference. Only disable for debugging or when memory is extremely constrained.

• pad_token_id: Token ID used for padding in batched generation. Must be set to a valid token ID (often the EOS token ID) to avoid errors with variable-length sequences.

• do_sample: Whether to sample from the probability distribution (True) or use greedy decoding (False). Greedy decoding is deterministic but often repetitive. Sampling introduces variety but requires tuning temperature and other sampling parameters.

• stop_sequences: List of strings that trigger generation to stop. Useful for structured outputs, chat applications, and preventing runaway generation. Processed after each token, so slight performance overhead.

• batch_size: Number of sequences to generate in parallel. Larger batches improve throughput but increase memory usage. Find the sweet spot based on your GPU memory and latency requirements.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about autoregressive generation and KV caching.