N-gram language models

Read the roadmap as one story. We want to predict the next word, so we count words in a corpus to estimate probabilities. We measure the result with Perplexity, and we look at what the model has learned by generating text from it. Then the model breaks: any word sequence it never saw gets probability zero. The second half of the lecture is the repair kit, from Smoothing through interpolation, Backoff and absolute discounting to Kneser-Ney, and it closes by connecting perplexity to Entropy.

1. Motivation: predicting words. What an LM computes and where that number is used. This part.
2. N-grams. The chain rule and the Markov assumption turn an impossible history into the last few words.
3. Estimating n-gram probabilities. Counting and dividing: maximum likelihood estimates, and log probabilities to avoid underflow.
4. Evaluating language models: perplexity. How to tell a better model from a worse one on held-out text without building a whole application.
5. Sampling from an LM. Generating text by drawing from the distribution, which shows what the model has actually learned.
6. Generalization and overfitting. Why a model tuned to its training corpus fails on new genres and assigns zero to unseen n-grams.
7. Smoothing, interpolation and backoff. Moving probability mass to unseen events and mixing in shorter contexts.
8. Absolute discounting. Subtracting a fixed amount from every seen count, justified by held-out data.
9. Kneser-Ney intuition. A lower-order distribution built from how many contexts a word completes, not how often it occurs.
10. Interpolated Kneser-Ney for bigrams. The full computation step by step on a toy corpus.
11. General Kneser-Ney. The recursion to higher-order n-grams, the standard count-based baseline.
12. Perplexity and entropy. The information-theoretic meaning of the evaluation metric.

Underneath the twelve stops there is a single question: how do we turn finite counts into a probability for every possible next word, including words never seen after this context? Stops 2 to 4 answer the easy half, for events we have seen. Stops 6 to 11 answer the hard half, for events we have not. The model family that carries all of it is the n-gram language model.

Finish this sentence: The water of Walden Pond is so beautifully ___. You probably thought of blue, green or clear. You did not think of refrigerator or this. You did not produce one word with certainty either. You produced a ranking with a sense of how much more likely some words are than others. That ranking, made numeric, is a language model.

A language model assigns a probability to each possible next word given the words so far, the history. Its output for one history is therefore a whole probability distribution over the vocabulary, and the task of producing it is next-word prediction. Writing the history as w<t, every word before position t:

The constraint that the probabilities sum to 1 is what makes the numbers comparable. If blue gains probability, something else must lose it. It also explains why the rest of the lecture worries about zeros: a model that spends all its mass on words it has seen has nothing left for refrigerator, even when a strange sentence really does continue that way.

This is not a toy objective. Jurafsky and Martin put it bluntly: large language models are built just by training them to predict words. GPT-3, with 175 billion parameters, is described by its authors as an autoregressive language model, which means exactly this: it computes P(w_t | w<t) one position at a time. A neural language model and an n-gram model answer the same question; they differ only in how they estimate the answer. GPT-3 itself was pretrained with plain next-token prediction, and modern LLMs use this objective or close variants of it; later tuning stages change the objective and shift the probabilities, but the output is still a distribution over the next token.

Run a dictionary spell checker over Their are two midterms. Every word is in the dictionary, so it passes. The error is a real-word error: the typo produced another valid word, and nothing about any single word reveals it. What reveals it is context. There are is a very common Bigram and Their are is rare, so a model that compares P(There are) with P(Their are) flags the sentence at once. The same holds for Everything has improve, where the fix improved makes the more probable sentence.

Now speech. A recognizer hears something that sounds like I will be back soonish, but the audio is almost identical to I will be bassoon dish. The acoustic evidence cannot separate them. The language model can: back soonish is a far more probable continuation of I will be than bassoon dish.

The pattern: candidates in, ranking out

Both examples share a structure, and it is worth naming because it covers almost every classical application. Some other component proposes candidates: a set of spelling variants, an acoustic model, a translation model, a keyboard decoder. The language model does not know what you meant. It scores how plausible each candidate is as a piece of language, and the system combines that score with the evidence. Brown and colleagues wrote this down for statistical machine translation in 1990 as the noisy channel decoder: given a foreign sentence T, output the English sentence S that maximizes the product below, and they call the first factor the language model probability of S.

The split of labour is clean. Pr(T | S) rewards faithfulness to the input. Pr(S) rewards fluency, and it does not care about the input at all, which is why one well trained language model can be reused across speech, translation and spelling. It is also why these are the settings where language models are judged by extrinsic evaluation: a better LM is one that lowers the word error rate or raises the translation score of the whole system.

Prediction on its own

In a second family of applications there is no separate candidate generator. The prefix you have typed is the history, and the system shows the top few entries of P(next | prefix). Search autocomplete turns a quick into brown fox. A translation input box suggests think after what do you. A phone keyboard offers bro, brown and brother while you type The quick bro. All of these are argmax or top-k over the same distribution from the previous concept.

The application with the highest stakes is augmentative and alternative communication (AAC). People who cannot speak or sign may select words from a menu with eye gaze or other small movements. Trnka and colleagues report that AAC users often communicate at under 10 words per minute, against 150 to 200 for speech, and that in a study with simulated AAC users (able-bodied typists slowed by an artificial key delay), advanced word prediction produced 59.9% more words per minute than no prediction. More accurate predictions significantly improve the communication rate, so here a better language model is directly a faster conversation.

Gboard is the best documented production example. Hard and colleagues describe how the keyboard shows three suggestions and the numbers behind them, and they make a useful benchmark for the comparison in the last concept of this part.

Compare all of a sudden I notice three guys standing on the sidewalk with on guys all I of notice sidewalk three a sudden standing the. Same twelve words, and none repeats, so there are 12! = 479,001,600 orderings. A good language model must put the fluent one near the top of all of them. That asks for something new: not a next word, but a probability for a whole sentence.

Language models offer two views. View one is the next-word distribution, P(w_t | w<t). View two is the probability of an entire sequence, P(w_1:T). They are not two models. The chain rule of probability turns one into the other exactly:

Going the other way, a next-word probability is a ratio of two sequence probabilities, P(w_t | w<t) = P(w_1:t) / P(w_1:t-1), so either view gives you the other. That is why slide 8 can call them equivalent. Here is a preview of the computation with the toy corpus Part 03 uses to teach counting.

Is the sentence view really enough to recover word order? Brown and colleagues tested exactly the claim on slide 8 with an experiment they called bag translation. They cut sentences into an unordered bag of words, then asked a Trigram language model to choose the ordering with the highest Pr(S).

The idea is older still. In 1948 Shannon drew each word of English text from the distribution of words that follow the previous word, a word bigram model done by hand, and got strings such as THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER: not meaningful, but recognizably English in its local order. Local next-word statistics already carry a surprising amount of a sentence's shape.

Train a model on the cat sat on the mat, then ask it about the dog sat on the rug. A model that only counts has never seen dog sat, so it has no evidence for it beyond whatever Smoothing hands out. A model that knows dog behaves like cat and rug like mat can carry the probability across. That difference is the whole of slide 9.

A count-based language model, also called statistical, estimates P(w | h) by maximum likelihood estimation: the relative frequency of the exact n-gram among all n-grams that share its history. It is transparent, fast and cheap. Its weakness is Sparsity. Bengio and colleagues put the problem as the curse of dimensionality: modelling the joint distribution of 10 consecutive words with a vocabulary of 100,000 has potentially 100,000^10 − 1 = 10^50 − 1 free parameters, and a test sequence is likely to differ from every sequence seen in training.

A neural language model maps each word or token to a continuous vector and learns a function from those vectors to the next-word distribution. Bengio and colleagues explain why this generalizes: an unseen sequence gets high probability if it is made of words similar to words in an already-seen sentence. Jurafsky and Martin name the two n-gram problems neural models solve: the number of parameters increases exponentially as the n-gram order increases, and n-grams have no way to generalize from training to test examples unless they use identical words.

This lecture is about count-based models only, which is why slide 9 sets them in bold. That is not nostalgia. Around the turn of the century the standard baseline was modified interpolated Kneser-Ney, available in public toolkits such as SRILM and KenLM, and it is still what you compare against when you need a cheap, inspectable model or a strong prior for a small device.

Take the phrase the water of Walden Pond and lay a frame two words wide over its start. Inside the frame you read the water. Slide it one word to the right and you read water of, then of Walden, then Walden Pond. Widen the frame to three words and the same sweep gives the water of, water of Walden and of Walden Pond. Those are the bigrams and trigrams of the phrase.

The general rule: an n-gram is a contiguous run of n tokens, read in order. A Unigram is a single token. A sequence of L tokens contains exactly L - n + 1 n-grams of order n, because the frame has that many starting positions. For our five-token phrase that is 5, 4 and 3.

The word carries a second meaning that you must keep apart from the first. "N-gram" also names the probabilistic model that predicts a word from the previous n - 1 words, so a "bigram model" is built from bigram counts and predicts each word from one word of context. Jurafsky and Martin call this "a bit of terminological ambiguity" and use the same Walden Pond examples as the slide [SLP3, ch. 3]. Context nearly always disambiguates: "count the trigrams" means the sequences, "train a trigram" means the model.

The units need not be words. In current systems the frame often slides over BPE subword tokens from Lecture 02, and nothing in this part changes when it does; only the vocabulary does. To see what n-gram counting looks like at web scale, here are the n-gram counts Google released from about a trillion tokens of English web text, after dropping the rare ones.

Distinct bigrams, trigrams and fourgrams climb steeply even after rare n-grams are dropped. The fivegram row dips only because every n-gram seen fewer than 40 times was discarded, and the long tail is where most fivegrams live. Longer windows produce more distinct patterns, each seen fewer times. That is Sparsity, and it will drive the rest of this part.

Suppose you want the probability that the next word is blue given the history The water of Walden Pond is so beautifully. The most direct estimate is a relative frequency: of all the times this eight-word history appeared in a corpus, in what fraction was it followed by blue?

The formula is correct. The trouble is the denominator. How many times does that exact eight-word history occur, even on the whole web? Probably zero, and if it occurs at all, a handful of times, which is far too few to estimate a probability. Jurafsky and Martin put it plainly: "even the entire web isn't big enough", because language is creative and "new sentences are invented all the time" [SLP3, ch. 3]. Most sentences you will read today have never been written before.

The arithmetic of histories

A short calculation shows that no amount of data closes the gap. With a vocabulary of V = 10,000 words, the number of possible histories of length k is V^k. A corpus of a trillion tokens contains at most about 10^12 history occurrences, one per position.

At k = 8 there are 10^32 possible histories, so even if every position in the corpus held a different history, at most a 10^-20 fraction of them could be seen once. The model needs many observations of each history, and it gets zero for nearly all of them. This is Sparsity in its most extreme form.

Before cutting the history short, look at what probability theory gives for free. The probability of the sentence its water is so transparent can be written as a product of five next-word probabilities:

Each factor predicts one word given all the words before it. Five words, five factors, and the product is exactly the joint probability. This is the chain rule of probability, which follows from applying the definition P(A, B) = P(A) P(B | A) repeatedly. In general:

What the chain rule buys is a change of question. "How probable is this sentence?" becomes "how probable is each next word, given what came before?", asked once per position. That is why a next-word predictor and a sentence scorer are the same object: give me one and I can build the other. Every language model you will meet, n-gram or neural, rests on this identity.

What it does not buy is any relief from the counting problem. Look at the last factor: P(transparent | its water is so) still conditions on the whole preceding history, and for a long sentence the late factors carry exactly the long histories that the previous concept showed we cannot count. As SLP3 admits, "using the chain rule doesn't really seem to help us!" It restates the problem in a usable shape; the next concept solves it.

Here is the move that makes language modelling learnable. Instead of P(blue | The water of Walden Pond is so beautifully), use P(blue | beautifully). Instead of asking about an eight-word history nobody has ever written, ask how often blue follows beautifully, which a modest corpus can answer. A Trigram model keeps one more word and uses P(blue | so beautifully).

This is the Markov assumption: the next word depends only on the last few words, not on the whole history. Written generally, with N the order of the n-gram model:

Read the subscripts carefully, because two letters share a name. Lowercase n is the position of the word being predicted. Uppercase N is the order of the model. The window w_(n-N+1) ... w_(n-1) contains exactly N - 1 words. For N = 2 it is P(w_n | w_(n-1)), the Bigram model; for N = 3 it is P(w_n | w_(n-2), w_(n-1)).

What the truncation trades

Cutting the history is a deliberate trade of long-range context for learnability. With a short window, each context recurs often enough to count. With a longer window, the model sees more of the sentence but each context is rarer, so the counts become sparse (Sparsity) and unreliable. The order N is the dial between the two, and the last concept of this part looks at where to set it.

In probability terms, an N-gram model is a Markov chain of order N - 1: the state that determines the next step is the last N - 1 tokens. Shannon described English text this way in 1948 as a "discrete Markoff process" [Shannon 1948].

Where the name comes from

In 1913 Andrei Markov took the first 20,000 letters of Pushkin's Eugene Onegin and classified each as a vowel or a consonant: 8,638 vowels and 11,362 consonants. If letters were independent, about 3,731 vowel-vowel pairs would be expected. He counted 1,104. The previous letter clearly mattered [Hayes 2013; Markov 1913, trans. 2006].

Apply the Markov assumption to every factor of the chain rule and a whole sentence becomes a product of short, countable pieces. Under a Bigram model, with the boundary symbols added:

Two new sentence boundary tokens appear. <s> gives the first word something to condition on, so P(its | <s>) measures how likely its is to open a sentence. </s> is predicted after the last word, so P(</s> | transparent) measures how likely the sentence is to stop there. The general bigram formula is:

A Trigram model needs two words of context for the first real word, so it pads with two start symbols, as in P(I | <s><s>) [SLP3 3.1.3]. For our sentence: P(its | <s><s>) P(water | <s> its) P(is | its water) P(so | water is) P(transparent | is so) P(</s> | so transparent). Still one end symbol: stopping is predicted once.

Why the end symbol is not optional

It is tempting to treat </s> as tidy formatting. It is not. Without it, the model never has to spend probability on stopping, and the sentence probabilities stop adding up. SLP3's footnote states the consequence: without the end symbol, "the sentence probabilities for all sentences of a given length would sum to one", so the model defines "an infinite set of probability distributions, with one distribution per sentence length" (Exercise 3.5). A tiny vocabulary makes this concrete.

In 1948 Claude Shannon generated text by sampling words from English statistics. Drawing each word independently by its frequency gave "REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE." Drawing each word given the previous one gave "THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT ..." [Shannon 1948]. One word of context, and local syntax already appears.

The first sample is a Unigram model, P(w), with no context at all. It knows which words are common and nothing about order, a bag of words: it gives dog bites man and man bites dog exactly the same probability. The second is a Bigram model, and a Trigram model with two words of context reads more fluently still.

The price of context

Each extra word of context multiplies the number of possible contexts by V. At V = 10^4 the possible n-grams number 10^4, 10^8 and 10^12 for unigrams, bigrams and trigrams. Real corpora fill only a sliver of these tables. Shakespeare's works have N = 884,647 tokens and V = 29,066 types, giving V^2 ≈ 844 million possible bigrams and V^4 ≈ 7 × 10^17 possible 4-grams. With so few observed 4-grams per context, a 4-gram model trained on Shakespeare starts copying him verbatim, which Part 06 dissects. Even at web scale, Web 1T kept 314.8 million bigrams seen at least 40 times against about 1.85 × 10^14 possible over its 13.59 million unigram types, roughly a 1.7 × 10^-6 fraction (derived, a lower bound).

This is the same Sparsity that defeated full histories, now as a dial rather than a wall. A larger N captures more context but leaves most contexts unseen, giving zero counts and Overfitting to the training text. In practice SLP3 notes that "when there is sufficient training data we use trigram models ... or 4-gram or 5-gram models". At the modern extreme, infini-gram sidesteps the fixed dial altogether: it uses suffix arrays over about 5 trillion tokens to back off to the longest matching context of any length, with millisecond latency and about 47% next-token accuracy [Liu et al. 2024].

Suppose the word "Chinese" occurs 400 times in a corpus of one million words. What probability should a unigram model give it? The obvious answer is 400 / 1,000,000 = 0.0004, and that obvious answer has a name: it is the maximum likelihood estimate. Among every possible value you could pick, 0.0004 is the one that makes the observed data, 400 occurrences in a million draws, most probable. SLP3 is careful about what this does and does not mean: it is not a claim that the "true" probability of Chinese in all English is 0.0004. It is the best fit to this one training set.

Stated generally, maximum likelihood chooses the parameters of a model M that maximize P(T | M), the probability of the training set T. For a language model made of n-gram probabilities, the maximizing parameters turn out to be relative frequencies: count how often something happened and normalize, meaning divide by a total so the results lie between 0 and 1 and sum to 1.

From counts to a conditional probability

A Bigram model needs P(w_n | w_(n-1)): given the previous word, how likely is each next word? The relative frequency is the count of the pair divided by the total count of all pairs that start with the same previous word. That is SLP3 equation 3.10:

The denominator looks awkward, but it collapses. Walk through the corpus and look at every occurrence of the word w_(n-1). Each occurrence is immediately followed by exactly one word, so it starts exactly one bigram. Summing the bigram counts over all possible followers therefore just counts the occurrences of w_(n-1) itself. The only occurrence that could break this is a word at the very end of a sentence, which has no follower, and closing every sentence with </s> fixes this too: the last real word is followed by the end token, so it too starts a bigram. The result is equation 3.11:

It helps to see what the wrong denominator would give. If you divided C(w_(n-1) w_n) by the total number of bigrams N in the corpus, you would get the joint probability P(w_(n-1), w_n): how often this particular pair occurs among all pairs. That is a perfectly good number, but it answers a different question. All the joint values together sum to 1, while what theChain rule of probability needs is a distribution over next words for a fixed history.

The best way to make equation 3.11 automatic is to run it once by hand on a corpus small enough to hold in your head. SLP3 uses three sentences from Dr. Seuss, each wrapped in sentence boundary tokens:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

Now try it on your own data. The builder below pads every line, fills the count matrix and the MLE matrix, and scores any sentence as a product and as a sum of natural logs. Load the I am Sam preset and check the numbers above, then type a sentence containing a Bigram the corpus never saw and watch the product collapse to zero.

From bigrams to any N

Nothing in the recipe depends on the history being one word. For an n-gram model, the Markov assumption keeps the last N - 1 words as the history, and the estimate is the count of the full n-gram divided by the count of its prefix (equation 3.12):

For a Trigram, P(Sam | I am) is C(I am Sam) / C(I am). In the toy corpus that is 1/2: "I am" occurs twice, followed once by Sam and once by </s>. The price of the longer history is Sparsity. With a vocabulary of V words there are V^(N-1) possible histories, and each needs enough occurrences for its row of fractions to mean anything. The rows get thinner fast.

In the Berkeley Restaurant Project corpus, the word i occurs 2533 times and the pair "i want" occurs 827 times. So the maximum likelihood estimate is P(want | i) = 827 / 2533 = 0.33: a third of the time a user of this system says i, the next word is want. That single division is all there is to reading a real Bigram table.

BeRP was a spoken question-answering system from the 1990s that answered questions about a database of restaurants in Berkeley, California. Its transcripts are exactly the sort of text an assistant hears: can you tell me about any good cantonese restaurants close by, i'm looking for a good place to eat breakfast. SLP3 uses 9332 sentences with a vocabulary of V = 1446 and shows an 8 by 8 slice of the bigram table for eight hand-picked words.

Read the table as row then column: the row is the history and the column is the next word. The 827 in row i, column want means want followed i 827 times. To turn counts into probabilities, divide every cell in a row by that row word's unigram count. Row i is divided by 2533, row want by 927, row to by 2417, and so on:

Now look at the zeros. These eight words were chosen because they cohere, they are the words of "i want to eat chinese food" plus two neighbors, and still 32 of the 64 cells are zero. The full table has 1446 x 1446, about 2.09 million, cells, filled from only 9332sentences, so the overwhelming majority of the full table must be zero. That is Sparsity seen directly, and some of those zeros (chinese to and lunch to are both zero, yet "chinese to go" is ordinary English, while a zero for i lunch reflects grammar) are accidents of a small sample rather than facts about English.

With a table in hand, scoring a sentence is mechanical. The Chain rule of probability writes the sentence probability as a product of next-word probabilities, and the Markov assumption cuts each history down to one word. For "i want english food", with the boundary tokens included, that is five factors:

Four of the five factors lie between 0.25 and 0.68. The fifth, 0.0011, is what makes the sentence improbable: the running product falls from 0.0825 to about 0.00009 at that single step. A sentence probability is dominated by its rarest transition.

What the numbers know

The table was built by counting, yet it already encodes several kinds of knowledge. Some is syntactic: after to, the high-probability words are verbs (P(eat | to) = 0.28), and after eat SLP3 notes that what follows is usually a noun or an adjective (lunch, chinese). Some is about the task: sentences tend to start with i, and "i want" is how people talk to an assistant. Some is cultural: the corpus makes Chinese food much more probable than English food, compare P(english | want) = 0.0011 with P(chinese | want) = 0.0065.

Multiply 400 probabilities of 0.1 in Python and the answer is exactly 0.0. The true value, 10^-400, is far below the smallest positive normalized double, 2.2 x 10^-308, and even below the smallest subnormal, about 5 x 10^-324, so the hardware rounds it to zero. Four hundred tokens is a paragraph, not a book. Yet the logarithm of the same product is simply 400 x ln 0.1 = -921.03, an unremarkable number.

This failure is called numerical underflow, and SLP3 gives it as the reason language models always work with log probabilities: probabilities are at most 1, so the more of them you multiply, the smaller the product gets. The identity that saves us is that the log of a product is the sum of the logs (equation 3.13):

import math, sys

print(0.1 ** 400)
print(400 * math.log(0.1))
print(sys.float_info.min, math.ulp(0.0))

factors = [0.25, 0.33, 0.0011, 0.5, 0.68]
log_p = sum(math.log(p) for p in factors)
print(log_p, math.exp(log_p))

The script prints 0.0, then -921.034..., then 2.2250738585072014e-308 and 5e-324, then -10.386 and 3.0855e-05. Note that math.log is the natural log unless you pass a base.

Longer context

With enough data, a bigram history is too short. Production systems use Trigram, 4-gram and 5-gram models, and the recipe is equation 3.12 again. The first words of a sentence need a full-length history, so a model of order N prepends N - 1 start tokens. For a trigram that is two, and the first word is scored as P(I | <s> <s>).

The tradeoff is direct. Each extra word of context makes predictions more specific and the generated text more fluent, but multiplies the number of possible histories by V, so each history is seen less often and the table fills with zeros. On a small corpus a high-order MLE model has almost one continuation per history and simply copies training sentences, the Overfitting that Part 06 shows with Shakespeare samples.

At web scale the balance shifts. Google's Web 1T 5-gram corpus counted n-grams over about one trillion tokens, with 13,588,391 unigram types and 1,176,470,663 distinct five-grams. Brants and colleagues in 2007 trained on two trillion tokens, about 300 billion n-grams, with the stupid backoff scheme you will meet in Part 07. Infini-gram (2024) drops the fixed N entirely: it indexes five trillion tokens with suffix arrays and computes counts for an n-gram of any length at query time. Toolkits like KenLM make large models fit in memory by storing log10 probabilities, quantizing them to 4 to 8 bits, hashing words to 64-bit integers, storing n-grams in reverse tries, and pruning rare n-grams.

Suppose you have two speech recognizers that are identical in every way except their Language model. The most convincing way to decide which LM is better is to run both systems on the same real audio and count how many words each gets wrong. Whichever has the lower word error rate has the better LM, for this task, on this data.

That is Extrinsic evaluation: you embed the model in an application and measure the application. SLP3 calls it "the only way to know if a particular improvement in the language model ... is really going to help the task at hand". Its weakness is cost. Every candidate model needs a full end-to-end run, and if you are trying twenty smoothing settings in an afternoon, twenty ASR decodes is not an option. Intrinsic evaluation trades realism for speed: it scores the model by itself, independent of any application. The standard intrinsic metric, for n-gram models and for neural LLMs alike, is Perplexity, which this part builds up step by step.

What "better" means: the Shannon game

To score a model by itself we need a definition of good that does not mention any application. The Shannon game supplies one. Cover the next word and ask the model to bet on it: "I always order pizza with cheese and ___". A good model spreads its bets over sensible continuations, say 0.1 on mushrooms, 0.1 on pepperoni, 0.01 on anchovies, a sliver on fried rice, and essentially nothing (10^-100 on the slide) on the word "and". Shannon ran the original version of this experiment in 1951 with letters rather than words, asking people to guess the next character of English text to estimate how predictable the language is. Contexts differ in how open they are: after "The 33rd President of the US was" almost all the probability belongs to one name, while after "I saw a" thousands of nouns are reasonable. The last concept of this part turns that difference into a number.

A Unigram model plays this game badly. It ignores the context entirely, so after "cheese and" it bets the same way it bets everywhere, heavily on frequent words like "the". The rule that falls out is simple: a better model is one that assigns a higher probability to the word that actually occurs. A perfect model would give each real next word probability 1. Applied to a whole held-out text, the better model gives the test text a higher probability, and perplexity is just a length-normalized way of reporting that probability.

You build a Bigram model and, by accident, five of your test sentences are also in the training corpus. Every bigram in those sentences now has a nonzero count, so the model assigns them a much higher probability than it would to genuinely new text, and the Perplexity drops. The model has not improved at all. It has simply seen the answers.

SLP3 names this precisely: if a test sentence is part of the training corpus, "we will mistakenly assign it an artificially high probability", a situation called training on the test set, or Data contamination, and it "causes huge inaccuracies in perplexity". The cure is to split the data into three disjoint parts with different jobs: a Training set, a Development set and a Test set.

The devset exists because models have knobs. Interpolation weights, the k of add-k smoothing and the discount in Kneser-Ney are all hyperparameters: they are not learned from counts, so they must be chosen by trying values and keeping the best. If you choose them by checking the test set, the test set has become part of training by another route. SLP3's rule is to do all testing on the devset "until the very end" and to run the test set "once, or a very few number of times".

Two further requirements make the test set meaningful. It should be drawn from the domain you care about: if the model will transcribe chemistry lectures or hotel booking requests, the test text should be chemistry lectures or booking requests, and the devset should look like the test set. And it should be large enough to give the statistical power to show a significant difference between two candidate models. A ten-sentence test set can make any two models look different by luck.

The obvious intrinsic score is the probability the model assigns to the test set. It has one fatal flaw. The same Bigram model might give a 5-token sentence a probability around 10^-5 and a 50-token paragraph around 10^-50. Every extra token multiplies in another factor below 1, so raw probability mostly measures length, and two test sets of different sizes cannot be compared.

Perplexity fixes this by taking the Nth root, which turns the product of N factors into a per-token average, and by inverting it so that the number grows as the model gets more surprised. For a test set W = w_1 ... w_N:

Expanding the joint probability with the Chain rule of probability turns it into a product of next-word probabilities, so perplexity is the geometric mean of the inverse next-word probabilities:

A specific model only changes what goes in the denominator. A Unigram model uses P(w_i); a bigram model, under the Markov assumption, uses P(w_i | w_(i-1)).

Because the exponent is negative, lower perplexity means higher test probability. For a fixed test set N is fixed, and P^(-1/N) is strictly decreasing in P, so minimizing perplexity is exactly the same as maximizing the probability of the test set. The inversion is not arbitrary: it comes from the original definition of perplexity as two raised to a cross-entropy rate, which Part 10 develops.

A worked example with the Berkeley bigrams

Compute it in log space

On a real test set of a million tokens the product underflows any floating-point type, so in practice you sum log probabilities instead, average them, and exponentiate once at the end:

The exponent is the average number of bits the model needs per token, which is the bridge to cross-entropy in Part 10. The base does not matter as long as it matches: Hugging Face defines perplexity as "the exponentiated average negative log-likelihood of a sequence", using natural logs and exp, which gives the same number. The same documentation notes that perplexity is not well defined for masked models such as BERT, because they do not assign a left-to-right probability to the sequence.

SLP3 trained Unigram, Bigram and Trigram models on 38 million words of Wall Street Journal text and measured Perplexity on a 1.5 million word test set. The results were 962, 170 and 109.

More context gives the model more information about the next word, so it is less surprised and its perplexity falls. Notice the diminishing return: the first word of context cuts perplexity by a factor of more than five, the second by about a third. The catch is data. A trigram model needs reliable counts for three-word sequences, and Sparsity grows fast with the order, so the gain holds only when the training set is large enough to estimate the longer n-grams. With too little data a higher order can be worse, which is the subject of Part 06.

Conventions that change the number

A real test corpus is many sentences, not one, so the model is run over the whole stream and the probability runs across sentence boundaries. If you use Sentence boundary tokens, they enter the count. SLP3 includes one token per sentence in N: the end marker </s>, but not the start marker <s>. The reason is that </s> is a genuine prediction (the model must decide where the sentence ends), while the step from </s> to the next <s> happens with probability almost 1, so counting it would add an almost-free token and flatter the score.

The deeper rule is that perplexity is a property of a model, a test set and a vocabulary together. SLP3 states that the perplexity of two language models "is only comparable if they use identical vocabularies". A model with a 10k-word vocabulary maps every rarer word to a single unknown token and then predicts that token easily, so its perplexity is lower on a task that is genuinely easier. In modern subword models the same applies to tokenization: Hugging Face warns that "the tokenization procedure has a direct impact on a model's perplexity". Even the evaluation procedure matters. GPT-2 large on WikiText-2 scores 19.44 with non-overlapping 1024-token windows and 16.44 with a sliding window of stride 512, because each token gets more context.

Perplexity is not the task

Lower perplexity often correlates with better downstream performance, which is why everyone uses it, but SLP3 is explicit that an intrinsic improvement "does not guarantee an (extrinsic) improvement". When the decision matters, confirm with the task metric: Extrinsic evaluation with word error rate for speech, BLEU or COMET for translation.

Take a toy language with three words, red, blue and green, where any word can follow any word. At every position there are three possible next words, so its Weighted branching factor is 3. Model A knows nothing and gives each word probability 1/3. On any test set of five words, PP_A = ((1/3)^5)^(-1/5) = 3. A uniform model's perplexity is exactly the number of choices.

Now Model B has learned that red is common: P(red) = 0.8, P(blue) = P(green) = 0.1. On the textbook Test set "red red red red blue", the probability is 0.8^4 × 0.1 = 0.04096 and PP_B = 0.04096^(-1/5) ≈ 1.89. Three words are still possible at every step, but the model is effectively choosing among fewer than two.

This is the intuition SLP3 offers: perplexity is the weighted average branching factor. The plain branching factor counts the possible next words. Perplexity weights them by how much probability the model puts on the words that actually occur, and reports the size of a uniform choice that would leave you equally uncertain. So the WSJ Trigram's 109 means that, on average, the model was as unsure as if it were picking uniformly from about 109 words at each step, out of a vocabulary of tens of thousands.

In 1948 Claude Shannon wanted to show what a statistical model of English "knows", so he generated text from one. His first-order word approximation picks each word independently, with its real frequency:

REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.

His second-order approximation picks each word given the one before it, using word-transition probabilities:

THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.

The jump is obvious. The first is a bag of English words; the second has runs like "ATTACK ON AN ENGLISH WRITER" that read as real phrases. Shannon observed that such samples "have reasonably good structure out to about twice the range that is taken into account in their construction". Nobody had to inspect a single probability to see the difference. Jurafsky and Martin make this the official motivation: "One important way to visualize what kind of knowledge a language model embodies is to sample from it", crediting the idea to Shannon and to Miller and Selfridge (1950).

The rule behind it is simple. A Language model is a probability distribution over sentences. Sampling draws sentences from that distribution, so a sentence the model gives probability 0.001 shows up ten times as often as one it gives 0.0001. The sentences you see are therefore a portrait of where the model puts its mass. Train N-gram models of increasing order on Shakespeare and sample from each:

Reading samples like these gives you three diagnostics at once.

• Local coherence grows with n. The window of words that make sense together is about twice the model order, as Shannon noted.
• Verbatim fragments are a warning. A line you can find word for word in the training text, like the 4-gram's "It cannot be but so", means the model is replaying its corpus. Fluent output here is Overfitting, not understanding; Part 06 shows the sparse counts that cause it.
• Samples reveal the genre. The same procedure on 40 million words of Wall Street Journal text produces talk of percentages, dollars and interest rates instead. That is Genre dependence made visible, and Part 06 draws the lesson for choosing training data.

Start with the simplest model, a Unigram model computed from the text of the SLP3 book. Lay its words end to end along a ruler from 0 to 1, giving each word a strip exactly as wide as its probability. "the" has probability 0.06, so it owns [0, 0.06). "of" has 0.03 and owns [0.06, 0.09). Then "a" owns [0.09, 0.11), "to" owns [0.11, 0.13), and "in" owns [0.13, 0.15). Far along the line, "however" (p = 0.0003) sits near 0.66, and "polyphonic" (p = 0.0000018) is a hairline near 0.99.

Now draw a random number. If u = 0.10, it lands in [0.09, 0.11), so the model emits "a". If u = 0.07, it lands in [0.06, 0.09) and the model emits "of". That is the whole algorithm. Because u is uniform, the chance it lands in a strip equals the strip's width, and the width is P(w). Every word is drawn with exactly its model probability.

The general rule: inverse-CDF sampling

Put the vocabulary in any fixed order w_1, w_2, …, w_V and compute the running totals F(w_k), the cumulative distribution. Draw u from the uniform distribution on [0, 1), and return the first word whose running total exceeds u. Statisticians call this the inversion or inverse-CDF method: you are reading the cumulative distribution backwards, from a height on the vertical axis to the word underneath it.

A unigram model has no context, so to produce a sentence you simply repeat the draw. When do you stop? SLP3 generates "until we randomly generate the sentence-final token" </s>. That only works if </s> is itself a word on the line, which is one more reason the Sentence boundary tokens are part of the vocabulary. It also fixes the length distribution. If P(</s>) = p, every draw ends the sentence with chance p, so sentence length (counting </s>) is geometric with mean 1 / p. With p = 0.05, sentences average 20 tokens.

In code, this is exactly what Python's random.choices does: it turns weights into cumulative weights ("[10, 5, 30, 5] are equivalent to the cumulative weights [10, 15, 45, 50]") and binary searches them with bisect. The five-word toy below renormalizes over just those five words by scaling u by the total.

import bisect, itertools, random

words = ["the", "of", "a", "to", "in"]
probs = [0.06, 0.03, 0.02, 0.02, 0.02]
cumulative = list(itertools.accumulate(probs))
u = random.random() * cumulative[-1]
word = words[bisect.bisect_right(cumulative, u)]

Stanford's CS224N trains a Trigram model on about 1.7 million words of Reuters news and starts generating from "today the ___". The model's top candidates are "company" (0.153), "bank" (0.153) and "price" (0.077). It samples "price", a lower-ranked word, and the window moves to "the price ___", where "of" has probability 0.308. Keep going and you get:

today the price of gold per ton , while production of shoe lasts and shoe industry , the bank intervened …

CS224N's verdict is "Surprisingly grammatical! …but incoherent." Every three-word window is plausible newswire; the sentence as a whole is about nothing.

The loop

The unigram number line had a single, fixed line. A Bigram or trigram model has one line per context, and the loop chooses which line to throw at.

1. Start from <s>. A bigram needs one start symbol; a trigram pads with two, so the first context is <s> <s>.
2. Draw w_1 from P(w | <s>) using the number-line method on that conditional distribution. SLP3 describes it as "first generating a random bigram that starts with <s>", then choosing "a random bigram starting with w".
3. In general draw w_i from P(w_i | w_(i−N+1) … w_(i−1)): the Markov assumption decides how many previous words select the line.
4. Stop when </s> is drawn. Without </s> there is no stopping event, and no proper distribution over sentence lengths.

Because each draw is made with exactly its conditional probability, the probability of producing a particular sentence is the product of the conditionals you drew along the way. That is the Chain rule of probability under the Markov assumption, run forwards as a generator instead of backwards as a scorer. In practice you would add log probabilities rather than multiply.

SLP3 chapter 7 writes the same loop for neural language models, under the name random multinomial sampling: i ← 1; w_i ∼ p(w); while w_i != EOS: i ← i + 1; w_i ∼ p(w_i | w_<i). The only change is that an LLM conditions on all of w_<i, not on the last N − 1 words.

For an n-gram model the reason greedy text repeats is mechanical. The context is just the last N − 1 words, so there are finitely many contexts, and greedy decoding maps each context to one fixed next word. Greedy output either reaches </s> before any context repeats, or it comes back to a context it has already been in. From then on it must repeat everything it produced from there, forever: it already went through that stretch once without drawing </s>, so it never will. Sampling escapes because each visit draws a fresh u.

The lecture's walkthrough generates a phrase about machine learning one word at a time. After the context "deep", the model's top continuations are "learning" 0.23, "reinforcement" 0.05, "convolutional" 0.04, "neural" 0.04, "multi" 0.02, "-" 0.02 and "image" 0.01. The listed words add up to 0.41, so 0.59 of the probability sits on words the slide does not show. The draw lands on "learning".

Next, conditioning on "deep learning", the distribution is much flatter: "models" 0.06, "." 0.05, ";" 0.05, "based" 0.05, "," 0.05, "for" 0.04, "methods" 0.04, a listed mass of 0.34. The draw is ",", even though "models" is the single most likely word.

Three operations per step

1. The context selects one conditional distribution out of the model's table.
2. That distribution is laid on [0, 1), exactly like the unigram line.
3. A fresh u is drawn and the word whose interval contains it is emitted.

The shape of the two distributions matters as much as the draws. After "deep", one word holds 0.23 and the model is fairly confident. After "deep learning", the top word holds only 0.06: many continuations are plausible, the model is uncertain, and its effective Weighted branching factor is large. That is precisely what Perplexity from Part 04 measures when averaged over a test set. Flat steps are also where samples become diverse.

The output so far is "deep learning ,". To pick the next word, the model strikes "deep" out of its context and conditions on "learning ,". The distribution there is "and" 0.14, "we" 0.07, "which" 0.05, "the" 0.05, "where" 0.03, "a" 0.02, "but" 0.02, listed mass 0.38. The draw is "but", whose interval in listed order is [0.36, 0.38). The output becomes "deep learning , but", and "deep" is still printed at the front.

The probability of this particular path, given the start "deep", is the product of the three drawn conditionals: 0.23 × 0.05 × 0.02 = 0.00023. Three ordinary-looking steps already put the continuation at about one chance in four thousand, which is why sampled texts almost never repeat.

The window is a queue

An order-N model keeps exactly the last N − 1 tokens as its context. After each draw, the new token is pushed onto the back and the oldest is popped off the front: a first-in, first-out queue of fixed length. Two details are easy to get wrong.

• The popped word leaves the context, not the output. The text keeps growing; only the conditioning window has a fixed length.
• Punctuation is a token like any other. The comma fills one of the two context slots, which is why the Trigram context after "deep learning ," is "learning ," and not "deep learning".

This is the Markov assumption made physical. Once "deep" has scrolled out, nothing it contributed can influence any later draw. The model cannot remember that the sentence is about deep learning three words later, which is exactly why the Reuters sample drifts from gold to shoes to banks: every window is locally fluent, and the sentence is globally incoherent. The same queue mislabelled as a bigram explains the errata in the previous concept: a bigram queue has one slot, and the slides clearly hold two.

The obvious fix is a longer window, and CS224N states the dilemma directly: "We need to consider more than three words at a time if we want to model language well. But increasing n worsens sparsity problem, and increases model size". Longer windows mean more never-seen contexts, the Sparsity problem that leads to the memorized 4-gram Shakespeare. Breaking that trade-off is what a Neural language model does: SLP3 chapter 7 runs the very same loop, sampling each token "conditioned on our previous choices", but with a context of thousands of tokens that is represented rather than counted.