Overview

Messages from the Zarbonian Empire regularly reach Earth, its most distant and recent addition, in fragments. Our archival assistant has to make sense of these incomplete transmissions. Here's one of them:

Zarbon the Great favors

What comes next? Tea? Coffee? Interstellar conquest? We'll follow how a model assigns probabilities to possible continuations and how a decoding rule turns those probabilities into an answer.

In How LLMs See Text, we saw how text becomes token IDs. Here we'll start with those IDs and revisit the language models from LING 529. The modeling problem will look familiar. The way a transformer represents and uses context deserves a closer look.

Outcomes

After this lesson, you should be able to…

• explain how n-gram contexts, recurrent state, and causal attention differ
• trace logits through softmax and a decoding rule to a continuation
• explain why generation changes the context for the next prediction
• distinguish context capacity, generation limits, and evidence for an answer

Complete How LLMs See Text first, and review transformers and causal attention as needed. The calculation below uses only Python's standard library. You can run it without downloading model weights or making API requests.

Wait, didn't we already cover language models in LING 529?

Great memory! We did introduce language models in LING 529. Those models assigned probabilities to word sequences. “Language model” describes the modeling problem. It doesn't specify a transformer or a particular number of parameters.

In the basic word level n-gram model we studied, we approximated the next word distribution using only a short recent history. A trigram model conditions on the previous two words. A bigram model uses one. Counting the word being predicted is where that n comes from.

Consider these two unfinished sequences, treating words as the units for this illustration:

Zarbon requested tea. Later the archivist brought ...
Zarbon requested coffee. Later the archivist brought ...

Our ordinary word trigram sees the same conditioning context in both: archivist brought. Changing tea to coffee earlier in the input cannot change its next word distribution, because the model's conditioning rule doesn't include that part of the sequence. Training it on another trillion sentences¹ doesn't change that rule. It may estimate the distribution for that short context better, but it still has the same horizon.

For a token sequence, this contiguous n-gram approximation is:

$$P(x_t \mid x_1,\ldots,x_{t-1}) \approx P(x_t \mid x_{t-n+1},\ldots,x_{t-1}).$$

For a trigram, the context on the right is just $x_{t-2},x_{t-1}$. We aren't claiming earlier context is irrelevant to language. We're choosing a model that ignores it once those recent tokens are given.

What changes in a neural model?

Neural models introduce several key changes. First, it's worth keeping in mind that a neural model can still use a fixed short context window. An early feedforward neural language model, for example, can use that limited history, while learning embeddings and sharing parameters across similar contexts. Bengio et al.'s neural probabilistic language model [2003] is a useful historical example. Learned representations change how the model generalizes, but they don't by themselves remove a context limit.

A transformer learns contextual vector representations through successive layers. Its attention weights depend on those representations, so the contribution of an earlier position can change with the input. Both approaches learn from data. The difference involves how they represent context and compute a prediction, as well as how far back they can look.

We've already met the recurrent state idea in the RNN unit. A longer prefix can affect that state. The innovation of attention is really in allowing a model to draw directly on representations at earlier positions, with weights that depend on the current context.

Attention enables selective access

In a causal transformer with full prefix attention, the current position can use representations of earlier positions within the available context. The query/key scores determine how information from those permitted positions is weighted. Different layers and heads can combine different relationships [2017]. A kind of probabilistic butterfly effect 🦋: our change from tea to coffee can affect a later prediction even when the final two words stay the same.

This architectural possibility doesn't mean that a particular model will use an earlier request to predict the drink Zarbon ordered. We need to test it. Some architectures also use local or sliding attention patterns, so we shouldn't assume every layer attends directly to every earlier token.

Training can process many positions in parallel because their preceding context is already supplied. Generating a new continuation still requires selecting its tokens in sequence.

Scale matters too: data, compute, capacity, tokenization, and training objectives all affect the result. Instruction and preference training add further changes to behavior. We'll separate those in the next lesson.

TL;DR: An LLM isn't simply a trigram model that ate a larger corpus.

Now let's follow the neural model's scores into the actual choice of a token.

From an input to a distribution

As we saw in How LLMs See Text, the tokenizer converts the input into IDs. Embeddings and position information turn those IDs into representations that transformer blocks can process. Causal attention lets a position use the prefix available to it. A final projection gives a logit, an unnormalized score, for each vocabulary item. Softmax turns those scores into a probability distribution over next token IDs.

Position information is necessary, but models don't all encode it in the same way. Learned absolute position embeddings are one option. Rotary position representations are another [2021]. Check the architecture of the model you're using rather than assuming the original transformer's choices are universal.

The loop above describes the computation conceptually. Implementations can cache attention keys and values instead of recomputing the whole prefix.

Inspect a tiny distribution

Suppose our assistant is continuing Zarbon the Great favors. We'll invent four candidate pieces and their logits so that we can inspect the calculation. These scores aren't measurements from a trained model, and a real vocabulary contains many more choices. The leading spaces belong to the decoded pieces.

from collections.abc import Sequence
import math
import random

# Invented pieces and scores for one next token prediction.
pieces: list[str] = [" tea", " coffee", " conquest", "."]
logits: list[float] = [2.0, 1.0, 0.0, -1.0]


def probabilities(
    scores: Sequence[float], temperature: float = 1.0
) -> list[float]:
    """Convert logits into probabilities at a positive temperature."""
    if temperature <= 0:
        raise ValueError("Use a positive temperature. Greedy is separate.")

    # Lower temperatures amplify differences between scores.
    scaled = [score / temperature for score in scores]

    # Subtracting the maximum keeps exponentials small without changing softmax.
    maximum = max(scaled)
    weights = [math.exp(score - maximum) for score in scaled]
    total = sum(weights)
    return [weight / total for weight in weights]


for temperature in (0.5, 1.0, 2.0):
    probs = probabilities(logits, temperature)
    rounded = [round(probability, 3) for probability in probs]
    print(f"Temperature {temperature}: {rounded}")

# Greedy selection chooses the piece with the highest logit.
greedy = pieces[max(range(len(logits)), key=logits.__getitem__)]

# The seed makes this local sampling example repeatable.
rng = random.Random(42)

# These are eight independent draws for the same position.
sampled = rng.choices(pieces, weights=probabilities(logits), k=8)
print(f"Greedy: {greedy!r}")
print(f"Sampled: {sampled}")

The eight sampled pieces are eight independent choices for the same next position, not an eight token sentence. An autoregressive model would append each chosen token and calculate a new distribution for the longer prefix.

For a fixed context, softmax with a positive temperature $T$ gives:

$$p_T(i) = \frac{\exp(z_i / T)}{\sum_{j=1}^{V}\exp(z_j / T)}, \qquad T > 0.$$

Here, $z_i$ is the logit for vocabulary ID $i$, and $z_j$ is the logit for vocabulary ID $j$. The denominator sums over all $V$ vocabulary IDs, where $V$ is the vocabulary size.

At temperature 1, the probabilities are approximately [0.644, 0.237, 0.087, 0.032]. Lowering the temperature concentrates mass on the higher-scoring options. Increasing it makes this distribution flatter. Neither operation checks whether an answer is true. Turning down the temperature doesn't give the assistant access to imperial records. It can make the same unsupported answer more likely to appear again.

Sampling strategies

Once we have a probability distribution, we still need to choose the next token. Sampling draws a token according to its probability, so more probable tokens are more likely to be selected. We can sample from the full distribution or restrict the choices first. Greedy decoding offers a deterministic alternative to sampling.

Greedy decoding selects a highest-scoring next token. Changing the temperature to another positive value has no effect on which token it picks, provided we use the same rule for breaking ties. It doesn't search all possible complete sentences for the best one. A locally attractive token can lead to a poor continuation.

Top-k sampling keeps the $k$ choices with the highest probabilities and samples after renormalizing their probabilities.

Top-p sampling sorts the choices from most to least probable and keeps adding choices until their cumulative probability reaches $p$. It then renormalizes the probabilities of those choices before sampling.

For $p = 0.8$, use this distribution at temperature 1:

1. Start with " tea": its probability is $0.644$, which is below $0.8$.
2. Add " coffee": the cumulative probability is $0.644 + 0.237 = 0.881$. We've reached the threshold, so we stop adding choices.
3. Renormalize the two retained probabilities by dividing each by $0.881$. " tea" now has probability $0.644 / 0.881 \approx 0.731$, and " coffee" has probability $0.237 / 0.881 \approx 0.269$.

We sample from those two choices. Conquest and punctuation will have to wait. These calculations use rounded probabilities, so the results are approximate.

Beam search keeps multiple candidate prefixes rather than committing to one prefix immediately. The beam's size, or width, determines how many candidate prefixes we retain at each step. A beam width of 1 gives greedy decoding. At the other extreme, retaining every possible prefix would explore every possible continuation up to the chosen length limit. That exhaustive search quickly becomes impractical as the number of possibilities explodes.

Beam search offers another way to explore continuations, though keeping more candidates doesn't guarantee a better answer for every task.

When does generation stop?

After selecting a token, the model predicts another distribution conditioned on the longer prefix. Generation can stop at an end token (a special token that programmatically breaks this loop), a configured stop condition, or a token limit. A response that hits its output limit may be an unfinished answer. Inspect the completion status before evaluating its content.

The context window must accommodate the input and leave space for generated tokens. Reserve output space when counting tokens (not words). Model Gateway basics explains how to inspect the request and response for the service we'll use.

Do we always want the most probable sequence?

Most probable according to which model, given which context? Finding a continuation with a higher probability doesn't necessarily give us a more useful answer. Meister et al. examine this distinction in neural machine translation [2020].

For our archival assistant, we might want an answer that follows instructions, uses the supplied evidence, and acknowledges missing information. Those requirements aren't automatically satisfied by choosing the most probable sequence. Sampling doesn't guarantee them either.

We'll explore how training and the information supplied in context shape an assistant's behavior in Training, context, and evidence, the next lesson in our unit roadmap.

Check your understanding

For optional practice, try a few of these on your own or with a classmate.

1. If we change tea to coffee in the earlier example, why must our basic trigram give the same next word distribution? What would need to change for an n-gram system to use that earlier request?
2. In the Python example, which temperature produces the greatest probability for " tea"? Does the highest-scoring choice change?
3. Suppose the assistant selects " conquest". What input should the next prediction condition on? Why shouldn't we reuse the same four scores?
4. The assistant confidently completes a sentence about a decree. What have we learned about the decree's existence?

Resources

• Language models (beginner): the LING 529 chain-rule and Markov horizon lesson.
• Hugging Face: generation strategies explains greedy selection, sampling, and beam search. Use this to compare strategies, not as a guarantee about a different service's API.
• Return to the LLM unit.

References

The original transformer paper [2017] focuses on sequence-to-sequence translation. Our discussion focuses on causal language modeling. Goodman's paper [2001] is the extended version.