Language Modeling as Next-Token Prediction

Arc 2 examines language models before transformers, starting with the prediction task they share. The cross-entropy post and probability distributions post introduce the loss and probability notation used here.

An autoregressive language model assigns a probability to the next token, given the tokens that came before it. Given a sequence of words (or subwords, or bytes), it outputs a probability distribution over what comes next.

Autoregressive neural models and n-gram language models share this prediction task, despite their different architectures. Chat models often receive additional training for instruction following and other behavior. (BERT and its descendants use a related but distinct objective, masked language modeling, where you predict held-out tokens from their bidirectional surroundings rather than predicting strictly left-to-right. We'll come back to that in Arc 4.)

The Chain Rule: Why This Works

Why does predicting the next token let you model entire sequences? Because of a fact from probability theory that we covered in Post 1.3: the chain rule.

Any joint probability over a sequence of tokens can be decomposed into a product of conditionals:

Or more compactly:

The factorization is exact for any joint sequence distribution. A model that accurately estimates every conditional $P(w_t \mid w_{<t})$ can therefore recover the joint distribution. Learning those conditionals from finite data is the modeling problem.

Here's what that factorization looks like in practice, for the first few words of a sentence:

Syntax, factual statements, and worked solutions all affect which tokens are likely to follow a prefix. Next-token prediction gives a model a training signal for those patterns. The chain rule explains why the representation is general; it does not guarantee which patterns a trained model will discover.

Shannon's Guessing Game

Claude Shannon understood this in 1948. His paper "A Mathematical Theory of Communication" is where entropy, cross-entropy, and most of information theory come from. But he also played a revealing game. In a 1951 follow-up paper, he had human subjects try to guess the next letter in English text, one character at a time.

People could predict the next letter with high accuracy, especially after seeing a few characters of context. After "the United Sta", the next letter is almost certainly "t". After a space following a period, it's probably a capital letter. After "q", it's almost certainly "u".

For the alphabet, texts, and procedures he studied, Shannon estimated English entropy at roughly 0.6 to 1.3 bits per character with substantial preceding context. Predictable structure reduced the average uncertainty well below a uniform character model.

Language models also use that structure to predict continuations. As in Post 1.4, cross-entropy measures the model's average surprise on the data; a better-matched distribution wastes fewer bits.

The hand-built distributions below illustrate the difference between uncertainty over possible letters and surprise at the letter that follows.

The concentration slider varies a five-outcome distribution from uniform ($\log_2 5 \approx 2.32$ bits of entropy) to one-hot (zero). A training objective asks the model to match the data, which may remain uncertain in ambiguous contexts.

Perplexity: Making the Numbers Interpretable

Perplexity expresses average log loss as an equivalent number of equally likely choices.

Perplexity is just the exponentiated cross-entropy:

where $H(p, q)$ is the cross-entropy of the model $q$ with respect to the true data distribution $p$, measured on some held-out test set. In practice, since we compute cross-entropy using natural log in PyTorch, you'll often see:

where "loss" is the average cross-entropy loss per token.

A perplexity of 10 means the observed tokens received the same average log loss as uniform choices among ten outcomes. It does not describe the number of plausible continuations at each position.

Slide the cross-entropy below to see where different regimes land:

Perplexities are comparable only when the evaluation text, tokenizer, context policy, and treatment of boundaries match. A uniform distribution over a 50,000-token vocabulary has perplexity 50,000. A perplexity of 30 means the observed tokens received the same average log-loss as uniform choices among 30 outcomes; it does not mean every position had exactly 30 plausible continuations.

A Worked Example

Consider the sentence:

"the cat sat on the mat"

Let's compute the probability of this sentence under three different models: a unigram model, a bigram model, and a hypothetical "good" model. Then we'll compare their perplexities.

Unigram model. A unigram model ignores all context. It just knows how frequent each word is. Let's say in our training corpus:

The unigram probability of the sentence is:

Per-token cross-entropy (using log base 2):

Perplexity: $2^{7.105} \approx 137.7$

Bigram model. A bigram model conditions on the previous word. With invented probabilities for this worked example:

Per-token cross-entropy:

Perplexity: $2^{3.917} \approx 15.1$

The chosen bigram probabilities give a perplexity of about 15, compared with 138 for the unigram example. In these assignments, "sat" receives more probability after "cat" than in isolation.

A "good" model. For comparison, assign higher probabilities by hand to a hypothetical model that uses the full context:

Per-token cross-entropy:

Perplexity: $2^{2.240} \approx 4.7$

The visualization compares these three hand-chosen assignments. Blue bars show the probability of each observed token; red bars show its surprise ($-\log_2 P$). Higher probabilities for those tokens reduce average surprise and perplexity.

Here's what those probability assignments look like side by side at a single position. The blue bars show how a "good" model distributes probability at position 5 (predicting "the" after "cat sat on"), and the red bars show what a bigram model does with only the previous word "on":

Implementation: A Minimal Bigram LM

Here's a complete bigram language model with perplexity evaluation. This is the simplest possible language model that actually conditions on context.

import math
from collections import defaultdict
 
class BigramLM:
    def __init__(self):
        self.counts = defaultdict(lambda: defaultdict(int))
        self.totals = defaultdict(int)
        self.vocab = {"<UNK>"}
 
    def train(self, sentences):
        """Train on a list of tokenized sentences."""
        for tokens in sentences:
            tokens = ["<s>"] + tokens + ["</s>"]
            for i in range(1, len(tokens)):
                self.counts[tokens[i-1]][tokens[i]] += 1
                self.totals[tokens[i-1]] += 1
                self.vocab.add(tokens[i])
 
    def prob(self, word, context):
        """P(word | context) with add-1 smoothing."""
        word = word if word in self.vocab else "<UNK>"
        context = context if context in self.vocab or context == "<s>" else "<UNK>"
        V = len(self.vocab)
        return (self.counts[context][word] + 1) / (self.totals[context] + V)
 
    def perplexity(self, sentences):
        """Compute perplexity on held-out data."""
        log_prob_sum = 0
        token_count = 0
 
        for tokens in sentences:
            tokens = ["<s>"] + tokens + ["</s>"]
            for i in range(1, len(tokens)):
                p = self.prob(tokens[i], tokens[i-1])
                log_prob_sum += math.log2(p)
                token_count += 1
 
        avg_cross_entropy = -log_prob_sum / token_count
        return 2 ** avg_cross_entropy
 
# Train on a small corpus
corpus = [
    "the cat sat on the mat".split(),
    "the cat ate the fish".split(),
    "the dog sat on the rug".split(),
    "a dog chased the cat".split(),
    "the cat slept on a mat".split(),
]
 
lm = BigramLM()
lm.train(corpus)
 
# Test probabilities
print(f"P(cat | the) = {lm.prob('cat', 'the'):.3f}")
print(f"P(sat | cat) = {lm.prob('sat', 'cat'):.3f}")
print(f"P(on  | sat) = {lm.prob('on', 'sat'):.3f}")
 
# Evaluate perplexity on held-out sentence
test = ["the cat sat on the rug".split()]
print(f"\nPerplexity on 'the cat sat on the rug': {lm.perplexity(test):.1f}")

Training counts pairs. Evaluation looks up their conditional probabilities, averages the log probabilities, and exponentiates. The +1 applies add-one (Laplace) smoothing so unseen bigrams retain probability. The next post compares smoothing methods.

Why Not Just Use Accuracy?

Why train language models with cross-entropy loss on the predicted distribution, rather than just scoring accuracy ("did the model guess the right word")?

Two reasons. First, accuracy is not differentiable. It's a step function: right or wrong, 1 or 0. It supplies no useful gradient for ordinary backpropagation, so it is not a suitable direct objective for this training setup.

Second, accuracy throws away information about confidence. If "mat" is the most probable token for both models, assigning it 35% in one and 99% in the other gives the same accuracy when it occurs. Cross-entropy sees the difference. It rewards high confidence in the correct answer and heavily penalizes confident wrong answers (because $-\log(0.01) \gg -\log(0.5)$).

The Sufficiency Argument

The chain rule represents any joint distribution over token sequences as a product of next-token conditionals. It does not establish how well a trained model will estimate them.

Many tasks can be written as a prefix followed by an answer. Training on varied text can therefore support several tasks without a separate output head for each.

A translation prompt can end with a source sentence; the continuation is its translation. A worked arithmetic problem can end just before the answer. Both fit the same interface, though useful performance requires learning the relevant patterns from training data.

Misconceptions

"Next-token prediction only learns local word patterns." The objective also rewards useful patterns across longer contexts. Experiments with GPT-2 and GPT-3 showed task performance from prompting a language model, including translation and question answering. How much a model learns depends on its training, not just the form of the objective.

"Perplexity tells you how good a model is at real tasks." It measures average log loss on the evaluation text. A model with lower perplexity need not follow instructions better, reason more reliably, or generate more useful responses under a particular decoding policy. Those behaviors require task evaluations, which Arc 8 covers.

"You need a different objective for each NLP task." GPT-2 and GPT-3 demonstrated tasks such as translation and question answering through prompts to a next-token model. Those results show what particular trained models could do; the chain rule alone makes no guarantee of task performance.

What's next

The next post covers n-gram models and the curse of sparsity: estimating next-token probabilities by counting, handling contexts absent from the data, and smoothing the resulting distributions.

Additional reading (and watching)

• Shannon, C.E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379-423. The foundational paper for information theory, entropy, and the mathematical framework for thinking about language as a probabilistic source.
• Shannon, C.E. (1951). Prediction and Entropy of Printed English. Bell System Technical Journal, 30(1), 50-64. Shannon's human guessing-game experiments that estimated the entropy of English at ~1.0-1.3 bits per character.
• Kaplan, J., et al. (2020). Scaling Laws for Neural Language Models. Showed that loss scales as a power law with model size, dataset size, and compute, with predictable returns.
• Hoffmann, J., et al. (2022). Training Compute-Optimal Large Language Models. The "Chinchilla" paper. Showed that previous models were significantly undertrained relative to their size, and that data and parameters should scale together.
• Wei, J., et al. (2022). Emergent Abilities of Large Language Models. Documents capabilities that appear suddenly at certain model scales, though see Schaeffer et al. (2023), "Are Emergent Abilities of Large Language Models a Mirage?" for a counter-argument.
• Radford, A., et al. (2019). Language Models are Unsupervised Multitask Learners. The GPT-2 paper. Showed that a single next-token-prediction model could do reading comprehension, translation, and summarization zero-shot.
• Brown, T., et al. (2020). Language Models are Few-Shot Learners. The GPT-3 paper. Demonstrated that in-context learning from next-token prediction scaled smoothly with model size across a wide range of benchmarks.
• Jelinek, F., Mercer, R. L., Bahl, L. R., & Baker, J. K. (1977). Perplexity — a measure of the difficulty of speech recognition tasks. JASA. The original introduction of perplexity as an evaluation metric for language models in the speech recognition community.