How predicting the next word taught machines to read in context, from counting word pairs to recurrent networks, contextual word vectors, translation, and the moment attention arrived.

§1.9 left a broken promise. A static embedding gives bank one vector, whether the sentence is about a loan or a river, and that vector is a frequency-weighted blur of both senses. Since then, Chapter 2 has shown what a model actually reads, a sequence of token ids, but each id still maps to one fixed row of the embedding table. What we want is a vector that has read the sentence. But "read the sentence" is not an objective you can minimize. What task would force a model to look at the words around bank and work out which bank is meant?

Here is a candidate. Cover the end of a sentence and ask the model to guess the next word. To finish "she deposited the check at the ___" you need to know that checks go to financial banks. To finish "the canoe drifted toward the muddy ___" you need the other sense. Prediction forces reading, and it needs no labels at all, because every sentence ever written is its own answer key.

Claude Shannon played exactly this game in 1951. He asked people to guess printed English one letter at a time and counted their mistakes. From the guessing statistics he bounded the entropy of English at roughly 0.6 to 1.3 bits per letter (Shannon 1951), far below the 4.75 bits that 27 equally likely symbols would need. Most of English is predictable from what came before. This chapter is the story of how machines learned to exploit that predictability, from counting word pairs to the attention mechanism that the rest of the book is built on.

This section builds the oldest working answer, the n-gram model. It is simple enough to implement in twenty lines, and every idea in it (the chain rule, maximum likelihood, perplexity, smoothing, sampling) survives unchanged into GPT.

The chain rule turns a sentence into a sequence of guesses

§2.1 gave the working picture. A language model reads token ids, outputs a probability for every id that could come next, and generates by predicting, picking one id, appending it, and repeating until an end-of-sequence id. This section puts that picture on firm ground, starting with what the model's probabilities mean. Formally, a language model assigns a probability to every sequence of tokens. For a sentence $w_1, w_2, \dots, w_T$ (each $w_t$ a token from the vocabulary $\mathcal{V}$ of size $V$), the chain rule of probability says, with no assumptions at all,

In plain words, the probability of a sentence is the probability of its first word, times the probability of the second word given the first, times the probability of the third given the first two, and so on. Modeling sentences and predicting the next token are the same problem.

Let's make it concrete. Suppose a model says $p(\text{the}) = 0.2$, $p(\text{cat} \mid \text{the}) = 0.01$, and $p(\text{sat} \mid \text{the cat}) = 0.1$. Then $p(\text{the cat sat}) = 0.2 \times 0.01 \times 0.1 = 2 \times 10^{-4}$. Each factor is one guess, and the sentence probability is the product of how well each guess went.

Two bookkeeping tokens make this precise. We prepend a start symbol <s> so that the first word is also "predicted from a context", and we append an end symbol </s> that the model must also predict. The end symbol is not decoration.

The chain rule also tells you how to generate. Sample $w_1$ from $p(\cdot \mid \texttt{<s>})$, then $w_2$ from $p(\cdot \mid w_1)$, and keep going until you draw </s>. This is the predict, pick, append loop of §2.1, now with a justification. It is called autoregressive generation, and it is exactly how GPT writes text in §6.4. Everything that follows is about one question. How do we estimate $p(w_t \mid w_{<t})$ when the history $w_{<t}$ can be any of an astronomical number of prefixes?

The Markov assumption gives n-gram models

The full history is too much. Most prefixes of length 20 have never been written down before, so we cannot estimate anything about them by counting. The Markov assumption throws most of the history away and keeps only the last $n-1$ tokens,

where $w_{t-n+1:t-1}$ means the $n-1$ tokens just before position $t$. This is an n-gram model. With $n = 1$ (a unigram model) every word is drawn independently of its neighbors. With $n = 2$ (bigram) each word depends on the one before it. With $n = 3$ (trigram) on the two before it.

Given the assumption, the natural estimate is the relative frequency. Write $\#(\cdot)$ for a count in the training corpus. For a context $h$ (the $n-1$ previous tokens) and a next token $w$,

In plain words, of all the times we saw context $h$ followed by something, what fraction of the time was that something $w$? Note that $\#(h)$ counts $h$ only where it is followed by a token, which is why the padded </s> matters.

This is not just intuitive, it is the maximum likelihood estimate.

Here is a whole bigram model, the table of next-token counts that §2.1 sketched, now justified as maximum likelihood, on a four-sentence corpus small enough to check every number by hand.

The model gives "the cat sat on the mat" probability $1 \cdot \tfrac{3}{9} \cdot \tfrac{1}{3} \cdot 1 \cdot 1 \cdot \tfrac{2}{9} \cdot 1 = \tfrac{2}{81} \approx 0.0247$. Notice two things in the last line. "the dog sat on the mat" never appears in the corpus, yet it gets the same probability, because it is stitched together from bigrams that do appear. That is how n-grams generalize. And "the mat sat on the cat" gets probability exactly zero, because the bigram mat sat was never seen. That is how they fail.

import numpy as np

def bigram_mle(ids, V):
    """ids: (T,) int array. Returns P: (V, V) row-normalized bigram counts."""
    C = np.zeros((V, V))
    C[ids[:-1], ids[1:]] += 1
    return C / C.sum(1, keepdims=True)

Why bigger n is not always better

A larger $n$ captures longer dependencies. A 5-gram model knows that "the cat sat on the" is followed by "mat" far more than a bigram model that only sees "the". So why not use $n = 10$?

Because counts run out. There are $V^n$ possible n-grams. With a modest vocabulary of $V = 50{,}000$ there are $1.25 \times 10^{14}$ possible trigrams and $6.25 \times 10^{18}$ possible 4-grams, while a large corpus has perhaps $10^{11}$ tokens. Word frequencies are heavy-tailed (Zipf's law), so most n-grams that matter appear zero or one times. As $n$ grows, more and more of the n-grams in new text were never seen in training, and the maximum likelihood estimate gives each of them probability zero.

The widget below makes the trade-off visible. It counts character n-grams on a short story and scores the held-out ending. Slide $n$ and watch three things at once, the samples (gibberish at $n = 1$, plausible words at $n = 3$ or 4, verbatim copies of the training text at $n = 7$), the training perplexity (always falling), and the held-out perplexity.

With $k = 0$, only the unigram model survives. Every other order meets at least one held-out n-gram it never saw, and a single zero probability makes the whole held-out probability zero. To see why one zero is fatal, recall how perplexity is computed.

Perplexity scores a model on text it has never seen

How do we score a language model? Show it held-out text and ask how much probability it gave to what actually happened. §0.5 defined it, so here is a short recap. For a held-out sequence $w_1, \dots, w_T$ (with every </s> included as a predicted token), the per-token cross-entropy of a model $q$ and its perplexity are

In plain words, perplexity is the inverse of the geometric mean probability the model gave to each token that occurred, the effective number of equally likely choices it was torn between. A uniform model over $V$ tokens scores exactly $V$, a perfect model scores 1, and $H_2 = H/\log 2$ is the same quantity in bits per token. $H$ is also exactly the training loss that every language model in this book minimizes.

Two consequences matter for n-gram models in particular. First, one zero sends perplexity to infinity. If any $q(w_t \mid w_{<t}) = 0$, then $\log 0 = -\infty$ and $\operatorname{PPL} = \infty$, however good every other prediction was. That is why the gray bars in the widget are infinite, and it is the whole reason for the smoothing methods below. Second, there is a floor. Gibbs' inequality from §0.5 gives $H(p, q) = H(p) + D_{\mathrm{KL}}(p \,\Vert\, q) \ge H(p)$ for the true distribution $p$, so no model can push perplexity below $e^{H(p)}$, the irreducible uncertainty of the language itself. Shannon's one bit or so per letter says the best possible model of English letters has a perplexity around 2, and the same floor reappears as the irreducible loss term of the scaling laws in Chapter 9.

A quick check by hand. If a bigram model gives the four predicted tokens of "<s> the cat sat </s>" probabilities $0.5, 0.25, 0.125, 0.5$, then $H_2 = \frac{1}{4}(1 + 2 + 3 + 1) = 1.75$ bits per token and $\operatorname{PPL} = 2^{1.75} \approx 3.36$. If the model had never seen cat after the, the second factor would be 0 and the perplexity infinite.

Smoothing moves probability to the unseen

Maximum likelihood is overconfident. It gives every unseen n-gram probability zero, and new text is full of unseen n-grams. The fix, called smoothing, takes a little probability away from the n-grams we did see and spreads it over the ones we did not.

The simplest version is add-one (Laplace) smoothing. Pretend every possible n-gram was seen once more than it was,

with $k = 1$ for add-one and any $k > 0$ for add-k. In plain words, add $k$ phantom observations of every token after every context. The denominator grows by $kV$ so that the probabilities still sum to 1 (sum the numerator over all $V$ tokens and you get $\#(h) + kV$).

Add-k is not an ad hoc trick. It is Bayesian estimation with a prior.

Add-one is a disaster for large vocabularies, and it is worth seeing why with numbers. Suppose the context "of the" was seen $\#(h) = 10$ times, followed by 3 distinct words, and $V = 10{,}000$. After add-one, the 3 seen continuations share $(10 + 3)/(10 + 10{,}000) \approx 0.13\%$ of the probability, and the 9,997 never-seen words share the other $99.87\%$. The prior of 10,000 phantom counts swamps the 10 real ones. Smaller $k$ helps, and the right value is chosen on held-out data, never on the test set.

Read the table row by row. With $k = 0$ only the unigram model is finite. With a small $k$, held-out perplexity falls as $n$ grows from 1 to 3, then rises again as the longer contexts become too sparse to trust. With $k = 1$ the prior is so strong that every order above 2 is hurt. Choosing $n$ and $k$ is a bias-variance trade-off, and held-out perplexity is how you navigate it.

import math
from collections import Counter

def ngram_perplexity(train, test, n, k):
    raise NotImplementedError

Interpolation and backoff use shorter contexts as a fallback

Add-k spreads the stolen probability uniformly, as if every unseen word were equally likely after "of the". That is silly. A much better guess for an unseen trigram is what the bigram model says, and if the bigram is unseen too, the unigram.

Interpolation always mixes all orders,

with the $\lambda$ weights fit on held-out data (the EM algorithm does this neatly, and the weights can depend on how often the context was seen). Backoff uses the highest order whose count is positive and drops to a lower order only when it has to, with a discount on the higher order so that the result still sums to one (Katz backoff). At web scale, Brants et al. (2007) found that a crude unnormalized version they called stupid backoff worked about as well as careful smoothing once the corpus had trillions of tokens. More data beats cleverer counting, a lesson the field would relearn many times.

Kneser-Ney asks how many contexts a word completes

The best classical smoothing method rests on one sharp observation. Consider the sentence "I poured a cup of ___". Suppose the context "cup of" is rare in training, so we lean on the unigram distribution. In a news corpus, Lanka might be more frequent than tea, because Sri Lanka is in the news. But Lanka appears almost exclusively after Sri. As a guess for what follows a new, unfamiliar context, it is terrible.

The lower-order distribution is only consulted when the higher-order context is unfamiliar. So it should not measure how often a word appears. It should measure how many different contexts it appears in. Kneser and Ney (1995) replaced the unigram with this continuation probability,

In plain words, the number of distinct words that precede $w$, divided by the number of distinct bigram types. Tea follows of, green, iced, hot, your, the, so it has a high continuation probability. Lanka follows only Sri, so it has a tiny one, however often it occurs.

Interpolated Kneser-Ney combines this with absolute discounting, which subtracts a fixed amount $D$ (typically around 0.75) from every observed bigram count and hands the freed mass to the continuation distribution,

Why subtract a constant rather than a fraction? Church and Gale (1991) compared bigram counts in two halves of a large corpus and found that bigrams seen $c$ times in one half appeared about $c - 0.75$ times on average in the other half, for most $c$ above 1. A constant discount matches that empirical fact.

The bigram formula extends to any order by recursion, and this is the form interviewers expect you to write down. For a context $h$ of $n-1$ words, let $h'$ be $h$ with its oldest word dropped. Then

and the recursion ends at the continuation unigram $p_{\text{cont}}(w)$. One detail is easy to miss. Only the highest order uses raw counts $\#(\cdot)$. Every lower order replaces them with continuation counts, the number of distinct words seen to the left, $N_{1+}(\cdot\, h' w)$, for the same reason as in the bigram case. A lower order is only consulted for contexts the higher order found unfamiliar, so what matters is how many contexts a pattern completes, not how often it occurs.

Chen and Goodman (1998) ran the definitive comparison of smoothing methods and found that their modified interpolated Kneser-Ney (three discounts, for n-grams seen once, twice, and three or more times, each set by a closed-form estimate from how many n-grams occur once, twice, three, and four times) consistently performed best. It was the standard n-gram baseline for the next fifteen years, and it is the baseline the first neural language models had to beat in §3.2.

from collections import Counter

def kn_bigram(train, D=0.75):
    big = Counter((a, b) for s in train for a, b in zip(["<s>"] + s, s + ["</s>"]))
    uni = Counter(b for (a, b) in big.elements())
    total = sum(uni.values())
    return lambda v, w: uni[w] / total        # plain unigram: ignores the context and the "how many contexts" idea

Sampling text from a model

A language model is also a generator. Sampling one token at a time from $q(\cdot \mid \text{context})$ produces text, and the quality of the samples is the most vivid diagnostic there is. Shannon (1948) did this by hand with a book and a random page, producing "approximations to English" of increasing order, and the progression from word salad to locally fluent nonsense is the same one you saw in the widget.

One knob controls the trade-off between safe and adventurous samples. Temperature $\tau > 0$ reshapes a distribution by raising each probability to the power $1/\tau$ and renormalizing,

In plain words, $\tau < 1$ sharpens the distribution toward its most likely tokens, $\tau > 1$ flattens it toward uniform, and $\tau \to 0$ becomes greedy decoding, always taking the single most likely token. The same knob, and its cousins top-k and top-p, return for GPT in §6.4.

At $\tau = 0.3$ the samples loop on the most common patterns ("the river river the band"). At $\tau = 1$ you get the model's honest distribution, a mix of real fragments ("the people runnin to the") and junk wherever smoothing gave an unseen character a little probability. At $\tau = 2$ those invented continuations dominate. No temperature makes a trigram model coherent, because it cannot see past two characters.

In PyTorch, counting is a one-layer neural network

Here is the bridge to the next section. A bigram model is a $V \times V$ table of logits $\mathbf W$, with $q(w \mid v) = \operatorname{softmax}(\mathbf W_{v,:})_w$. If you train that table by gradient descent on the cross-entropy, the softmax-cross-entropy gradient from §0.2 is $\operatorname{softmax}(\mathbf W_{v,:}) - \mathbf e_w$ for each observed pair. Summed over the $\#(v)$ pairs that start with $v$, the gradient of row $v$ is $\#(v)\big(\operatorname{softmax}(\mathbf W_{v,:}) - \hat p(\cdot \mid v)\big)$, which vanishes exactly when the row's softmax equals the relative frequencies. (A zero count can only be matched in the limit, with its logit drifting toward minus infinity, which is why the cell below ends close to the counts rather than on them.) Counting is maximum likelihood training of the simplest neural language model. Adding L2 weight decay pulls the logits toward zero, which pulls the probabilities toward uniform, so it plays the role of smoothing.

In production nobody trains n-grams this way. Tools like KenLM count and smooth billions of n-grams with sorted arrays and tries, and n-gram models are still used where speed matters, for example as a fast draft model or a cheap filter of pretraining data. But the equivalence is the point. Once the table of logits is replaced by a function that can share statistics across similar contexts, we have a neural language model.

Read more

• Shannon (1948). A Mathematical Theory of Communication. Section 3 builds n-gram approximations to English by hand, the first language model samples.
• Shannon (1951). Prediction and Entropy of Printed English. The guessing game and the bound of about one bit per letter.
• Jurafsky and Martin. Speech and Language Processing, Chapter 3, N-gram Language Models, with Appendix C on Kneser-Ney smoothing. The standard textbook treatment, with many worked examples.
• Chen and Goodman (1996). An Empirical Study of Smoothing Techniques for Language Modeling. The definitive comparison. Their 1998 Harvard technical report of the same name extends it and introduces modified Kneser-Ney.
• Kneser and Ney (1995). Improved Backing-off for M-gram Language Modeling. The continuation-count idea.
• Brants et al. (2007). Large Language Models in Machine Translation. Stupid backoff on two trillion tokens, an early lesson that data can beat cleverness.

Watch next

▶

▶

▶