Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Autoregressive Generation › The Generation Procedure

Michael BrenndoerferUpdated July 30, 202520 min read

Language AI HandbookAll chapters

Part 28 of 67GPT Architecture

Chapter 201Autoregressive Generation › The Generation Procedure

Reading section 2 of 12 · The Generation Procedure · 20 minSection 2 of 12 · 20 min

Section 2 of 12 · 20 min read

Autoregressive Generation › The Generation ProcedureOne section · Sections in this chapter2 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

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.

Autoregressive Generation

Autoregressive generation produces sequences token-by-token, where each new token is conditioned on all previously generated tokens. The probability of generating a complete sequence factorizes as $P(x_1, \ldots, x_n) = \prod_{i=1}^{n} P(x_i | x_1, \ldots, x_{i-1})$ , meaning we multiply together the probability of each token given everything that came before it.

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.

In[4]:

Code

def greedy_generate(model, tokenizer, prompt: str, max_new_tokens: int = 50):
    """
    Generate text using greedy decoding (always pick the most likely token).

    This is the simplest generation strategy: at each step, select the token
    with the highest probability.
    """
    # Encode the prompt
    input_ids = tokenizer.encode(prompt, return_tensors="pt")

    # Generate tokens one at a time
    for _ in range(max_new_tokens):
        # Forward pass through the model
        with torch.no_grad():
            outputs = model(input_ids)
            logits = outputs.logits

        # Get logits for the last position
        next_token_logits = logits[:, -1, :]

        # Greedy selection: pick the highest probability token
        next_token_id = next_token_logits.argmax(dim=-1, keepdim=True)

        # Append to the sequence
        input_ids = torch.cat([input_ids, next_token_id], dim=1)

        # Check for end of sequence
        if next_token_id.item() == tokenizer.eos_token_id:
            break

    # Decode and return the generated text
    return tokenizer.decode(input_ids[0], skip_special_tokens=True)

This implementation reveals several important aspects of generation. First, the model produces logits (unnormalized log-probabilities) for every position in the vocabulary at once. We only use the logits at the final position since that's where the next token prediction happens. Second, greedy decoding, which always selects the most probable token, is deterministic: the same prompt always produces the same output. Third, the loop continues until we either reach max_new_tokens or generate an end-of-sequence token.

Out[6]:

Console

Prompt: The future of artificial intelligence
Generated: The future of artificial intelligence is uncertain.

"We're not sure

The generated continuation flows naturally from the prompt. This shows that the model has learned meaningful language patterns. Notice how each word follows logically from the previous context. Greedy decoding often produces repetitive or generic text because it always takes the safe, high-probability path, converging on the same safe completions regardless of creative variation. For a prompt like "The future of artificial intelligence", greedy decoding will reliably produce something factual and generic because those patterns dominate the training distribution. We'll explore more sophisticated sampling strategies in subsequent chapters on temperature, top-k sampling, and nucleus sampling. For now, the main point is that all generation strategies share the same underlying loop: predict, select, append, repeat. The strategies differ only in how they implement the "select" step.

Out[7]:

Visualization

Horizontal bar chart showing the top 20 most probable next tokens, with floor and ground having the highest probabilities around 0.10-0.12. — Top-20 token probabilities after processing 'The cat sat on the'. The model assigns highest probability to 'floor' and 'ground', which reflects common language patterns. Most of GPT-2's 50,257 vocabulary tokens receive near-zero probability, putting the mass on contextually appropriate completions.

The Generation Loop in DetailLink Copied

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.

Out[8]:

Visualization

Diagram showing three iterations of the generation loop with growing sequences and probability distributions. — The autoregressive generation loop. At each step, the model processes the current sequence to produce logits, selects the next token, and appends it. The sequence grows by one token per iteration until a stopping criterion is met.

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.

Mathematical FormulationLink Copied

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:

P(x_1, x_2, \ldots, x_T) = \prod_{t=1}^{T} P(x_t | x_1, x_2, \ldots, x_{t-1})

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":

First token: $P(\text{"The"})$ asks how likely "The" is as an opening. Common sentence starters like "The", "A", "I" receive high probability.
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.
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.

Out[9]:

Visualization

Bar chart showing conditional probabilities for each token in the sequence The cat sat, with probability values decreasing from left to right. — Autoregressive probability factorization for ''The cat sat''. Each bar shows the conditional probability at that step. The sequence probability is the product of all factors: 0.08 × 0.15 × 0.25 = 0.003, meaning this specific three-word sequence appears in about 0.3% of contexts where ''The'' could start a sentence.

From Hidden States to ProbabilitiesLink Copied

Now we need to understand how the model computes each conditional probability $P(x_t | x_{<t})$ . This happens in two stages:

Encode the context: The transformer processes all tokens $x_1, \ldots, x_{t-1}$ to produce a hidden state $h_t$ that summarizes the relevant context.
Project to vocabulary: A linear layer maps this hidden state to a score for every token in the vocabulary, then softmax converts these scores to probabilities.

The formula for this computation is:

P(x_t | x_{<t}) = \text{softmax}(W_{\text{lm}} \cdot h_t + b)_{x_t}

where:

$h_t \in \mathbb{R}^{d}$ : the hidden state vector at position $t$ from the final transformer layer, where $d$ is the hidden dimension (e.g., 768 for GPT-2 Small). This vector encodes everything the model "knows" about the context so far.
$W_{\text{lm}} \in \mathbb{R}^{V \times d}$ : the language modeling head weight matrix that projects from hidden dimension to vocabulary size $V$ . Each row of this matrix can be thought of as a "template" for one vocabulary token.
$b \in \mathbb{R}^{V}$ : the bias term (often zero or absent in modern implementations), which captures token-independent frequency preferences.
$\text{softmax}(\cdot)_{x_t}$ : the probability assigned to token $x_t$ after normalization.

The product $W_{\text{lm}} \cdot h_t$ computes a score (logit) for each vocabulary token by measuring how similar the current context representation is to each token's template. Higher scores indicate more likely next tokens. The rows of $W_{\text{lm}}$ can be thought of as "prototype vectors" for each vocabulary token: a token is predicted as likely when the current context representation $h_t$ aligns well (high dot product) with that token's prototype. This geometric intuition explains why related tokens often have similar logit scores: their prototype vectors point in similar directions in the hidden space.

The softmax function then performs two important operations:

Exponentiation ( $e^{z_i}$ ) ensures all values become positive
Normalization (dividing by the sum) ensures probabilities sum to 1

Why does this formula make sense? Notice that exponentiation preserves the relative ordering of logits: if token A has a higher logit than token B, it will also have a higher probability after softmax. The exponential amplifies differences, so a logit advantage of 2.0 translates to roughly $e^2 \approx 7.4$ times the probability, rather than only twice the probability. This amplification is what allows the model to express strong preferences for particular tokens even when multiple tokens have plausible logits.

Out[10]:

Visualization

Horizontal bar chart showing raw logit values for candidate tokens, ranging from negative to positive values. — Raw logits can be any real number. Negative logits (red) indicate less likely tokens, while positive logits (green) indicate more likely ones. The token 'on' has the highest logit at 2.1.

Horizontal bar chart showing probability values after softmax normalization, with all values between 0 and 1 summing to 1. — After softmax, logits become probabilities that sum to 1.0. The token 'on' receives the highest probability (0.62) because it had the highest logit.

Why Generation Must Be SequentialLink Copied

This mathematical structure reveals a basic constraint: we cannot parallelize generation across positions. To compute $h_t$ , the model must know tokens $x_1, \ldots, x_{t-1}$ , because the transformer's causal attention mask prevents each position from seeing future tokens. The causal mask is not an arbitrary restriction imposed to make training efficient; it is the architectural guarantee that makes autoregressive generation self-consistent. If position 5 could attend to position 8 during generation, it would need to know what token occupies position 8 before that token has been chosen, creating a logical impossibility.

Concretely, if we want to predict the 10th token:

We need $h_{10}$ , the hidden state at position 10
Computing $h_{10}$ requires attention over positions 1 through 9
But positions 1 through 9 must contain actual tokens, not placeholders
Therefore, we must have already generated tokens 1 through 9

This sequential dependency is what makes autoregressive generation inherently step-by-step. Unlike tasks like classification where we process the entire input in parallel, generation must proceed one token at a time, with each new token depending on all previous decisions. This is a basic difference from training: during training, the target tokens are all known in advance, so the causal mask allows all positions to be computed simultaneously. During inference, each position's token is unknown until the model produces it, forcing strict left-to-right ordering. This training-inference asymmetry is one of the key reasons why training transformers is highly parallelizable while inference is not.

You might wonder whether there is some clever way around this constraint. Researchers have explored non-autoregressive generation, where all output tokens are predicted simultaneously, and masked diffusion models that iteratively refine a full-length output. These approaches trade off quality and flexibility for speed. In practice, for tasks requiring high-quality coherent text, autoregressive generation remains the dominant approach because the conditioning on previous tokens is precisely what ensures each new token fits naturally into the evolving context.

Out[11]:

Visualization

Heatmap showing a lower triangular attention mask where green cells indicate allowed attention and gray cells indicate masked future positions. — Causal attention mask enforcing the autoregressive property. Each position can only attend to itself and earlier positions (green cells). Future positions are masked (gray cells). This triangular structure ensures the model cannot 'cheat' by looking ahead during generation.