Chapter 10n-gram Language Models and Perplexity

Guess the next word

Finish this sentence.

You said are. Everyone says are. Now try this one.

Here the answers spread out, because is, does, time and longer are all reasonable, so you did not pick one answer but held several, ranked.

That ranking is the subject of Part III, and a model that can produce it is a language model. The rest of this book is a series of steadily more capable ways to build one.

What you used to answer

Notice how much you brought to a two word prompt. Lexical knowledge told you which words exist and which are common, syntactic rules told you that How are needs a subject next, and semantic cues ruled out How are cement. World knowledge told you that people greet each other this way, and pragmatics told you the sentence was a greeting rather than a question about health.

That is five kinds of knowledge, none of them written down anywhere, all applied in under a second.

The engineering question is how to put that box on a computer. For thirty years the field tried to write the five knowledge sources down as rules, and it did not work, for the reasons Chapter 1 gave.

This chapter takes the other road. Rather than encode the knowledge at all, it counts how often things happened and lets the counts stand in for all five. That sounds far too crude to work, and it works very well, while where it fails it fails in ways that point straight at what comes next.

What a language model is

A language model assigns a probability to a sequence of words, and that is the whole definition. Pause on how strange it is, since nothing in it mentions grammar, meaning or truth, and a language model is simply a probability distribution over strings.

Yet this one idea is the foundation of everything after, because the neural models of Chapter 11, the recurrent networks of Chapter 12 and the large language models of Chapter 18 all answer the same question. Given what has been said so far, what comes next, and with what probability? Only the machinery changes.

Why anyone wants one

Historically, because many language technologies reduce to choosing between candidate word sequences. A speech recogniser hears a signal that fits both “recognise speech” and “wreck a nice beach” and must pick one, a translation system generates a dozen candidate renderings and must rank them, and a spelling corrector must decide whether “their going home” was meant to be “they’re going home”. In every case the winning move is the same, which is to prefer the candidate the language model scores higher.

Today the motivation is more direct, because a modern large language model is a language model in exactly this chapter’s sense, producing its output one next word distribution at a time.

The chain rule

We want the joint probability of a sentence $W = w_1 w_2 \cdots w_n$, and the chain rule of probability factorises it exactly, with no approximation:

$$\begin{equation} p(w_1 w_2 \cdots w_n) \;=\; \prod_{i=1}^{n} p\big(w_i \mid w_1, \ldots, w_{i-1}\big). \label{eq:chainrule} \quad\text{(10.1)} \end{equation}$$

Equation (10.1) converts one impossible problem into $n$ merely difficult ones, where the impossible problem was a distribution over all sentences and the difficult one is a distribution over the next word given a history.

It also shows why a language model is a generative model. Sample from the first factor, append the word, condition on it and sample again, repeating until you draw the stop symbol, and you have written a sentence.

The difficulty that remains is the history, because the context $w_1, \ldots, w_{i-1}$ can be arbitrarily long and almost every particular history is one nobody has ever seen. No corpus contains reliable statistics for the exact prefix “The results of the 2026 municipal elections in Tenkasi suggest”, which has appeared once, in this book.

The Markov assumption

The n-gram model’s answer is bold, which is to forget the past. More precisely, assume the next word depends only on the previous $n-1$ words:

$$\begin{equation} p\big(w_i \mid w_1, \ldots, w_{i-1}\big) \;\approx\; p\big(w_i \mid w_{i-n+1}, \ldots, w_{i-1}\big). \label{eq:markov} \quad\text{(10.2)} \end{equation}$$

With $n = 2$, a bigram model, each word depends only on its predecessor, while with $n = 3$, a trigram model, it depends on the previous two, and with $n = 1$, a unigram model, on nothing at all.

This is a Markov assumption and it is plainly false, since in “The book that the committee rejected was short” the verb agrees with book, eight words away. The assumption is made because it buys something we cannot otherwise have, which is contexts short enough to recur.

The history “of the” appears thousands of times in a modest corpus, so statistics conditioned on it are trustworthy, whereas the history in the Tenkasi example appears once and statistics conditioned on it are worthless.

The whole art of n-gram modelling is therefore one trade off. Longer context means a sharper prediction on thinner evidence, and shorter context means a blunter prediction on firmer evidence.

Estimating by counting

How do we get the conditional probabilities? By the most honest method available, which is counting. The maximum likelihood estimate of a bigram probability is the fraction of times the context was followed by the word in question:

$$\begin{equation} p_{\text{MLE}}\big(w \mid c\big) \;=\; \frac{\operatorname{count}(c, w)}{\operatorname{count}(c)}. \label{eq:mle} \quad\text{(10.3)} \end{equation}$$

That is all, with no optimisation and no training loop. Read the corpus, keep two counters, divide.

A corpus small enough to check

We will use three sentences for the whole chapter, so that every number in it can be verified by hand.

The word the occurs three times, twice followed by cat and once by dog, so

$$p_{\text{MLE}}(\text{cat} \mid \text{the}) = \tfrac{2}{3}, \qquad p_{\text{MLE}}(\text{dog} \mid \text{the}) = \tfrac{1}{3},$$

and every other continuation of the has probability zero. Hold on to that zero, because it becomes the villain of the chapter.

Conventions that change the numbers

Before any two implementations of Equation (10.3) can agree, three bookkeeping conventions must match. They sound like pedantry, and each one changes the answers, which is why Project 4 checks them exactly.

The first is padding. Each sentence is padded with $n-1$ start symbols <s> and one stop symbol </s>. The start padding gives the first real word a context, so that a bigram model can speak of $p(\text{the} \mid \texttt{<s>})$, while the stop symbol does something deeper by making sentence length part of the model. Without it the model only ever assigns mass to continuing and never to stopping, so the probabilities of all sentences of all lengths sum to more than one, whereas with it ending a sentence is an event like any other.

The second concerns unknown words, because a model trained on our three sentences will one day meet the word elephant. The remedy is a designated symbol <unk>, to which every word absent from the training vocabulary maps, and which is an ordinary vocabulary item in its own right. So the vocabulary of our corpus is

$$V = \{\text{the, cat, dog, sat, ran}\} \cup \{\texttt{</s>}, \texttt{<unk>}\}, \qquad |V| = 7 .$$

Note what is not in $V$. The start symbol is context only, so it is never predicted, never needs a probability, and must never be mapped to <unk>.

The third convention settles what gets scored. Probabilities, and later perplexity, are computed over the predicted tokens, meaning the words of the sentence plus the one </s>, and the start padding is never scored.

State these three and Equation (10.3) is reproducible to the last decimal. Omit them and two correct programs will disagree.

The zero problem and smoothing

Our model believes $p(\text{sat} \mid \text{dog}) = 1$ and $p(\text{ran} \mid \text{dog}) = 0$.

The first claim is merely overconfident and the second is fatal, because under the chain rule a single zero factor drives the whole sentence to probability zero and its perplexity to infinity. Yet “the dog ran” is perfectly good English and merely failed to appear in three sentences of training data, so the model has confused unseen with impossible.

The remedy is to smooth, shaving a little mass off what we saw and handing it to what we did not. The simplest scheme is add-$\alpha$ smoothing, which pretends every vocabulary item was seen $\alpha$ extra times in every context:

$$\begin{equation} p_{\alpha}\big(w \mid c\big) \;=\; \frac{\operatorname{count}(c, w) + \alpha} {\operatorname{count}(c) + \alpha\,|V|}. \label{eq:addalpha} \quad\text{(10.4)} \end{equation}$$

The $\alpha|V|$ in the denominator is exactly what makes the probabilities sum to one again, which is why the vocabulary convention matters and why </s> and <unk> have to be counted in $|V|$.

Watching the mass move

Set $\alpha = 1$ and $|V| = 7$, then look at every continuation of the, whose context was seen $3$ times.

Both columns sum to one, as they must, and the two seen words gave up $0.5$ between them while the five unseen words received $0.1$ each. The counts did not change, and the belief did.

Now the same table for the context dog, which was seen only once.

This is the repair we wanted, since $p(\text{ran} \mid \text{dog})$ has risen from $0$ to $0.125$ and “the dog ran” is no longer impossible.

It is also where add-$\alpha$ shows its weakness, because moving $p(\text{sat} \mid \text{dog})$ from $1.00$ to $0.25$ is a scalping rather than a shave, and the evidence for it was a single observation.

The effect scales badly. With a realistic vocabulary of tens of thousands the denominator is dominated by $\alpha|V|$, so nearly all the mass goes to events nobody has ever seen. In practice one therefore uses a small $\alpha$ tuned on held out data, or one of the better schemes in Section 10.8.

The principle never changes. Every language model, up to the largest, must reserve belief for things it has not seen.

Perplexity: measuring a language model

Two colleagues each hand you a language model, and you must say which is better. The models are distributions, so let the data decide: the better model is the one that finds held out text less surprising, which is to say it assigns the text higher probability.

Raw probabilities are unwieldy because they shrink exponentially with length, so we normalise, and the average negative log probability per predicted token is the model’s cross-entropy on the text:

$$\begin{equation} H(W) \;=\; -\frac{1}{N} \sum_{i=1}^{N} \log_2 p\big(w_i \mid \text{context}_i\big), \label{eq:crossent} \quad\text{(10.5)} \end{equation}$$

measured in bits per token. Its exponential is the perplexity:

$$\begin{equation} \operatorname{PP}(W) \;=\; 2^{\,H(W)} . \label{eq:ppl} \quad\text{(10.6)} \end{equation}$$

Here $N$ counts the predicted tokens, meaning the words plus </s> by the convention above.

Perplexity has a clean reading as the model’s effective branching factor, the size of the uniform distribution that would be equally surprised. A perplexity of $100$ means the model is as uncertain at each step as if it were choosing among $100$ equally likely words, so lower is better, and a model that knew the text by heart would score $1$.

The zero we worried about gives $\log 0 = -\infty$ and hence perplexity $\infty$, which is the formal statement of why unsmoothed models are unusable.

Where $2^{H(W)}$ comes from

Equations (10.5) and (10.6) can look like a definition pulled out of the air. They are not. Perplexity begins as a statement about probability alone, and the exponential of an entropy is what that statement turns into.

Start with the probability the model assigns to the whole text. The chain rule splits it into one factor per predicted token:

$$\begin{equation} p(W) \;=\; p(w_1, w_2, \dots, w_N) \;=\; \prod_{i=1}^{N} p\big(w_i \mid w_{1:i-1}\big). \label{eq:chain-ppl} \quad\text{(10.7)} \end{equation}$$

Perplexity is the reciprocal of the geometric mean of those factors:

$$\begin{equation} \operatorname{PP}(W) \;=\; \Big(\frac{1}{p(W)}\Big)^{1/N} \;=\; \Big(\prod_{i=1}^{N} \frac{1}{p\big(w_i \mid w_{1:i-1}\big)}\Big)^{1/N}. \label{eq:ppl-geom} \quad\text{(10.8)} \end{equation}$$

Two choices in that line are doing real work. Taking the reciprocal makes a better model score lower, because assigning high probability to genuine text is what we are rewarding. Raising to the power $1/N$ divides the length out, so a long passage is not penalised merely for being long. Without it every text would score worse than a shorter one and no two test sets could be compared.

Now rewrite Equation (10.8) as an exponential. For any positive $x$ we have $x = 2^{\log_2 x}$, so

$$\begin{equation} \operatorname{PP}(W) \;=\; 2^{\,\log_2\!\left(p(W)^{-1/N}\right)} \;=\; 2^{\,-\frac{1}{N}\log_2 p(W)}, \quad\text{(10.9)} \end{equation}$$

where the second step uses $\log_2(a^b) = b\log_2 a$. Expanding $p(W)$ with Equation (10.7) turns the logarithm of a product into a sum:

$$\begin{equation} -\frac{1}{N}\log_2 \prod_{i=1}^{N} p\big(w_i \mid w_{1:i-1}\big) \;=\; -\frac{1}{N}\sum_{i=1}^{N} \log_2 p\big(w_i \mid w_{1:i-1}\big), \quad\text{(10.10)} \end{equation}$$

and the right hand side is exactly $H(W)$ from Equation (10.5). Substituting it into the exponent returns Equation (10.6), $\operatorname{PP}(W) = 2^{H(W)}$.

So the two readings are one number. $H(W)$ is the average number of bits the model spends per token, and raising $2$ to that power converts bits back into a count of equally likely choices. The branching factor reading above is therefore not an analogy but a restatement: $2^{\text{bits}}$ is the number of uniform options those bits could index.

The base is bookkeeping. Use the natural logarithm in Equation (10.5) and the same derivation gives $e^{H(W)}$, which is the same number reached by a different route. Base $2$ is conventional because it reads directly as bits, which is how Shannon entropy is usually quoted.

One perplexity, worked in full

Take the bigram model with $\alpha = 1$ and score the sentence the cat sat, which padded is <s> the cat sat </s>, giving four predicted tokens. Each row applies Equation (10.4) with $|V| = 7$.

The count column is $\operatorname{count}(c, w)$ and of is $\operatorname{count}(c)$, so every probability is $(\text{count} + 1) / (\text{of} + 7)$. Now finish it:

$$H \;=\; -\frac{-6.8138}{4} \;=\; 1.7034 \text{ bits per token}, \qquad \operatorname{PP} \;=\; 2^{1.7034} \;=\; \mathbf{3.2568} .$$

So the model is about as unsure at each step as if it were choosing uniformly among $3.26$ words, where the vocabulary holds $7$, and on a corpus this small that is a respectable score.

Two details in that table are worth naming. The first row scores the in the context <s>, which is why the padding exists, and the last row scores </s>, which is why $N = 4$ rather than $3$.

Choosing $\alpha$, and why the test set must be new

Perplexity gives us a way to pick $\alpha$, which is to try several and keep the best. The catch is which text you measure on. Here are two sentences, where the cat sat is in the training data while the dog ran is not, though every word of it is and only the bigram $(\mathit{dog}, \mathit{ran})$ is new.

The two columns tell opposite stories. The seen column falls all the way down, because less smoothing always looks better on text the model has memorised, and it would keep improving as $\alpha \to 0$. The held out column is a U, bottoming at $\alpha = 0.10$ and rising on both sides.

Both sides of that U have a cause. Too little smoothing and the single unseen bigram is crushed towards zero probability, while too much and the seen bigrams are robbed to pay for events that never happen.

Tuning on training text would have chosen $\alpha = 0.01$, which scores $4.3297$ on new text against the best available $3.2047$, making it $1.35$ times worse from a decision that looked correct at the time.

Two cautions

Perplexity is only comparable across models that share a vocabulary and a tokenisation, because a model with a smaller vocabulary has an easier problem and the subword tokenisers of Chapter 5 change $N$ itself.

Perplexity also measures surprise rather than usefulness, so it correlates with downstream quality without guaranteeing it. Both cautions return with force in Chapter 22.

The curse of dimensionality

Everything so far suggests a simple way to improve the model, which is to use a longer context, on the grounds that if bigrams are good then trigrams should be better. They are, for a while, and then the arithmetic stops you.

An n-gram model needs one number per history and word, and there are $|V|^{n-1}$ possible histories with $|V| - 1$ free choices inside each, since the last probability is fixed by the others:

$$\begin{equation} \text{parameters} \;\approx\; |V|^{\,n-1} \times (|V| - 1). \label{eq:ngram-params} \quad\text{(10.11)} \end{equation}$$

That exponent is the whole problem.

Take the bottom right cell, where a 5-gram model over a $50{,}000$ word vocabulary has about $3.1 \times 10^{23}$ parameters. Now count what could fill them. A corpus of a trillion tokens contains at most a trillion distinct 5-grams, one per position, so at most one cell in $3 \times 10^{11}$ can hold a nonzero count.

The counts do not merely get thin. Almost the entire table is empty, and no corpus that will ever be assembled can change that.

Three consequences follow, and the lectures name them. Data sparsity means most n-grams have zero or tiny counts, so their probabilities cannot be estimated reliably. Overfitting means the model latches onto the exact phrases in the training text and generalises to nothing else. And computational cost means storing and searching the table grows with the same exponent.

Beyond counting

The framework can be pushed further than add-$\alpha$, and three techniques matter. Pruning discards n-grams with low counts, which saves space and removes estimates that were never trustworthy. Interpolation mixes the orders, so that when the trigram evidence is thin you lean on the bigram, and when the bigram fails too you lean on the unigram:

$$\begin{equation} p(w_3 \mid w_1, w_2) \;=\; \lambda_1\,p_1(w_3) \;+\; \lambda_2\,p_2(w_3 \mid w_2) \;+\; \lambda_3\,p_3(w_3 \mid w_1, w_2), \label{eq:interpolation} \quad\text{(10.12)} \end{equation}$$

subject to the one constraint $\lambda_1 + \lambda_2 + \lambda_3 = 1$, where the weights say how much to trust each level of context and are tuned on held out data like any other hyperparameter. Backoff does the same job with a switch rather than a blend, using the trigram if you have seen it and otherwise dropping an order and trying again.

Interpolation, worked

Take a four sentence corpus, so that the trigram counts can run out while the bigram counts still survive.

Set $\lambda_1 = 0.1$, $\lambda_2 = 0.3$ and $\lambda_3 = 0.6$, then take four queries in decreasing order of evidence. All three estimates below are unsmoothed, so the failures stay visible.

Read the four rows as a staircase. Row one has full evidence at every order, because the trigram cat sat on was seen twice and never continued any other way, so all three estimates are high and so is the mixture.

Row two shows what the extra context buys, since the trigram is sharper than the bigram at $0.6667$ against $0.4286$, because on the narrows the field more than the alone.

Row three is the one that matters. The trigram on the cat never occurred, so $p_3 = 0$ and a pure trigram model would call the phrase impossible, whereas the bigram has seen the cat twice and says $0.2857$. The mixture returns $0.0964$ and the sentence survives.

Row four is the last resort, where the word ran never follows the anywhere in this corpus, so both higher orders fail and only the unigram is left. The answer is small, and what matters is that it is not zero.

Kneser-Ney smoothing (Kneser and Ney 1995) is the state of the counting art, and it refines the lowest order term. What matters for an unseen context is how many distinct contexts a word occurs in rather than how often it occurs, so that Francisco is common yet occurs almost only after San and deserves very little unseen-context mass. Refinements of this kind carried speech recognition and translation for two decades.

Try it yourself. code/worked_examples/ngram_lm.py produces every table in this chapter, using the same conventions the autograder enforces. --counts prints the two smoothing tables, --perplexity the four row calculation, --alpha the U shape, --params the parameter explosion, --interpolate the staircase, and --unk what happens to a word the model has never met.

Run it in ColabNotebookSource

What counting cannot fix

Smoothing repairs the zeros and interpolation repairs thin evidence, while neither touches the two real blindnesses, and both of those are structural.

The first is the Markov assumption. The model cannot know that book, eight words back, governs the verb it is about to emit, because eight words back does not exist for it. Raising $n$ does not solve this, since the parameter table of Equation (10.11) explodes long before $n$ reaches eight.

The second is that words are opaque strings. Suppose the corpus contains the cat sat many times and the dog only once, and a counter has no way to let cat lend statistical strength to dog, because to a counter they are two unrelated symbols.

Chapter 9 already built the cure for the second problem, when words became vectors and similar words came out near each other, and what was missing was a way to put those vectors to work on prediction. That is exactly what the next chapter does, keeping the task, the corpus, the smoothing instinct and the perplexity yardstick while replacing the count table with a network.

Further reading.

Jurafsky and Martin (2025) cover this material with more smoothing variants and worked examples. Chen and Goodman (1999) remains the definitive empirical comparison of smoothing methods. Manning and Schütze (1999) treat the statistical foundations in depth. Kneser and Ney (1995) introduce the smoothing method that held the record for years. The class-based n-grams of Brown et al. (1992) are an early attempt to share statistical strength between related words, which is the problem Chapter 11 solves properly. The models of this chapter are implemented in nltk.lm, whose MLE, Laplace and KneserNeyInterpolated classes correspond to three of the estimators above, and the last exercise below is about the one thing that library cannot guess. Shannon (1948) is where the entropy of a text was first proposed as something measurable, and it is still worth reading.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• ngram_lm.pySmoothing, perplexity and the U-curve

  Add-alpha smoothing, held-out perplexity and interpolation, on three sentences of training data.

  standard library only Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.