Smoothing Techniques for N-gram LLMs: Laplace to Kneser-Ney

In the previous chapter on N-gram Language Models, we built a system for estimating the probability of a word given its history. We used maximum likelihood estimation (MLE): count how many times a particular n-gram occurs in training data, divide by the count of the context. Clean and intuitive. But there is a fundamental problem lurking in this approach, one that appears the moment you apply your model to any text it hasn't seen before.

The problem is zero probabilities. If your training corpus never contains the trigram "the crimson aardvark," MLE assigns it a probability of exactly zero. That's fine in isolation, but recall the chain rule: the probability of a sentence is the product of its word-level conditional probabilities. One zero anywhere in that product collapses the entire sentence probability to zero. The model claims that "the crimson aardvark ate the mango" is impossible, not just unlikely. For a language model, this is catastrophic: virtually any naturally occurring sentence will contain at least one n-gram your training data didn't cover.

This is the data sparsity problem, and smoothing is how we solve it. Smoothing is a family of techniques that redistribute probability mass away from seen n-grams to cover unseen ones. The core idea is deceptively simple: instead of assigning zero probability to unseen events, give them a small positive probability by "borrowing" a little mass from the events you have seen. The challenge is doing this redistribution in a way that is both principled and accurate, so that the resulting probability distribution still matches observed language.

Over the decades, researchers developed a rich progression of smoothing methods, each addressing shortcomings in the ones before it. This chapter walks through the full arc: starting with the naive Laplace approach, moving through Good-Turing estimation and its frequency-of-frequency insights, then exploring interpolation and backoff strategies for combining evidence from different n-gram orders, and finally arriving at Kneser-Ney smoothing, which remains one of the best-performing methods for n-gram models even today. Along the way, we'll understand what each method does, why it does it, and what failure mode it was designed to address.

Before diving into solutions, let's develop a crisp understanding of why this problem is so severe and how pervasive it is.

Suppose you train a bigram model on 1 million words of newspaper text. Your model has learned $P(\text{"president"} \mid \text{"the"})$, $P(\text{"company"} \mid \text{"the"})$, and thousands of other bigrams. Now you want to evaluate the probability of a sentence containing the bigram "the aardvark." Unless your training corpus happened to discuss aardvarks, this bigram has count zero. MLE gives it probability zero.

The formal quantity at stake is the MLE bigram probability. To estimate how likely word $w_i$ is given the preceding word $w_{i-1}$, MLE computes:

where:

• $C(w_{i-1}, w_i)$: the count of the bigram $w_{i-1} w_i$ in the training corpus
• $C(w_{i-1})$: the count of the word $w_{i-1}$ in the training corpus (the context)

When $C(w_{i-1}, w_i) = 0$, the probability is zero, regardless of how large the corpus is.

How bad is this in practice? A vocabulary of $|V|$ words produces $|V|^2$ possible bigrams and $|V|^3$ possible trigrams. For a typical vocabulary of 50,000 words, that's 2.5 billion possible bigrams and 125 trillion possible trigrams. No training corpus of any realistic size will cover more than a tiny fraction of these. Zipf's Law compounds the problem: most words are rare, so most n-grams that do occur in language appear only once or twice even in large corpora. The distribution is extremely heavy-tailed, which means that even after collecting tens of millions of sentences, you'll still encounter enormous numbers of bigrams in real text that never appeared in your training data.

To make this concrete, consider what happens at the level of trigrams. A well-built bigram model might have coverage for most bigrams in common text. But a trigram model trained on even a large corpus will miss the vast majority of possible three-word sequences. This is the curse of dimensionality applied to discrete combinatorial spaces: the number of possible sequences grows exponentially in $n$, but the amount of training data grows only linearly. The mismatch is permanent, no matter how much data you collect.

Smoothing solves this by ensuring every n-gram gets a positive probability. The challenge is doing this in a principled way that doesn't distort the probability distribution too badly. A terrible smoothing method would assign equal probability to all unseen n-grams regardless of how plausible they are. A good one will allocate probability mass in proportion to evidence about how likely each word is to appear in a given context, even if that specific context was never observed.

One important constraint governs any valid smoothing scheme: the probabilities of all possible next words given a context must still sum to 1. This is the fundamental property that makes a conditional probability distribution valid.

If we add probability mass to unseen n-grams, we must subtract an equal amount from the seen ones. This is the "conservation" intuition behind smoothing: probability mass is neither created nor destroyed, only redistributed. The question is how to redistribute it wisely.

Most smoothing methods follow a two-step pattern. First, they apply a discount to reduce the probability assigned to seen n-grams. Second, they distribute the freed-up probability mass to unseen n-grams using some lower-order model as a guide. The choice of how much to discount and where to send the freed mass is what distinguishes one smoothing method from another.

The simplest smoothing method is Laplace smoothing, also called add-one smoothing. The idea predates NLP entirely, originating with Pierre-Simon Laplace's "rule of succession," his 18th-century method for estimating the probability of events that haven't been observed yet. Laplace applied it to the question of predicting whether the sun would rise tomorrow given that it had risen every day in recorded history. The same reasoning applies here: if we haven't seen a bigram, that doesn't mean it's impossible, just that our sample was finite.

The intuition is direct: pretend you saw every possible n-gram at least once. To achieve this, add 1 to every n-gram count before normalizing. This ensures no count is zero and therefore no probability is zero.

For a bigram model, the smoothed probability is computed by adding 1 to the raw bigram count and adding $|V|$ to the denominator (to account for all the extra counts across the full vocabulary):

where:

• $C(w_{i-1}, w_i)$: raw bigram count in the corpus
• $C(w_{i-1})$: raw unigram count of the context word
• $|V|$: vocabulary size (number of unique words)

We add 1 to the numerator for every possible bigram (including unseen ones), and add $|V|$ to the denominator to normalize correctly. Since there are $|V|$ possible next words and each gets one extra count, the total extra count is $|V|$, which must be reflected in the denominator to preserve the sum-to-one property.

The general form for an n-gram model extends this naturally. To estimate the probability of $w_i$ given an $(n-1)$-word context $w_{i-n+1}^{i-1}$:

where $w_{i-n+1}^{i-1}$ denotes the $(n-1)$-word context.

Consider a tiny corpus: "the cat sat on the mat the cat sat." Let's compute some bigram probabilities.

Raw bigram counts:

• C("the cat") = 2
• C("cat sat") = 2
• C("sat on") = 1
• C("on the") = 1
• C("the mat") = 1
• C("mat the") = 1

Raw unigram counts: C("the") = 3, C("cat") = 2, C("sat") = 2, C("on") = 1, C("mat") = 1.

Vocabulary size: $|V| = 5$.

The MLE probability of "cat" given "the" is:

The Laplace-smoothed probability of the same bigram is:

For an unseen bigram ("the sat"), the two methods give:

The zero probability disappears. But notice how much probability mass has shifted: "the cat" dropped from 0.667 to 0.375, nearly cut in half. This turns out to be a significant problem.

Laplace smoothing is intuitive but performs poorly in practice. The reason is that it steals far too much probability from seen n-grams to give to unseen ones.

The amount stolen can be quantified by an adjusted count: the count a bigram effectively acts as after smoothing, relative to the denominator. For a bigram with raw count $c$ and context count $C(w_{i-1})$, the adjusted count is:

where all symbols are as defined above. This formula converts the smoothed probability back into "effective count" units so you can directly compare how much the raw count was distorted.

For our example, the adjusted count of "the cat" is:

So the bigram "the cat" (which occurred twice) is being treated as if it occurred only 1.125 times, a 44% reduction. For a bigram that occurred 100 times, adding 1 barely changes anything. But for a bigram that occurred once or twice, the effect is enormous. Laplace smoothing systematically underestimates frequent n-grams and over-estimates the probability mass to allocate to unseen ones.

Church and Gale (1991) showed empirically that Laplace smoothing allocates far more probability mass to unseen bigrams than empirical evidence justifies. For realistic vocabulary sizes (tens of thousands of words), the $|V|$ term in the denominator is huge, and adding 1 to each count forces massive reallocation regardless of what the data shows. When your vocabulary contains 50,000 words and your context word appeared 1,000 times, the denominator becomes 51,000, reducing every probability by roughly 2%. That might seem small, but applied to counts of 1 or 2, it reduces those bigrams to near-uniform noise.

The core insight from this analysis is that the severity of the discount should depend on the raw count. A bigram seen 1,000 times shouldn't be discounted by the same proportion as one seen twice. Laplace uses a fixed additive adjustment that ignores this completely. This motivates more principled alternatives.

A natural generalization is to add a fractional amount $k$ instead of 1. This is called add-k smoothing or Lidstone smoothing. Rather than inflating every count by a full unit, we inflate by a fraction $k \in (0, 1]$:

where:

• $k$: a hyperparameter in the range $(0, 1]$ controlling how much mass to redistribute to unseen events
• $C(w_{i-1}, w_i)$: raw bigram count
• $C(w_{i-1})$: raw unigram count of the context
• $|V|$: vocabulary size

When $k = 1$, this reduces to Laplace smoothing. When $k$ is small (for example, $k = 0.01$), the adjustment is gentler and less mass is stolen from seen bigrams.

The value of $k$ should be tuned on a held-out development set. You train the model on training data, then try different values of $k$ and pick the one that minimizes perplexity on the held-out data. Typical values range from 0.001 to 0.5.

However, even with optimally tuned $k$, add-k smoothing remains a relatively poor performer. The core problem is that it uses the same $k$ for all n-grams, regardless of how often they appear. A word that appears once in the training set and a word that appears 1,000 times receive the same additive adjustment, which isn't what the data suggests. More principled methods use different discount amounts for different n-grams based on their observed counts.

There's a deeper issue too. The add-k family of methods treats the lower-order distribution (what probability to give unseen bigrams) as uniform: every word in the vocabulary gets the same small baseline probability of $k / (C(w_{i-1}) + k|V|)$, regardless of how common the word is. But in reality, some words are much more likely to appear in new contexts than others. A common function word like "the" is far more likely to follow any given word than a rare content word. The lower-order distribution should reflect this, and add-k doesn't.

Good-Turing smoothing takes a fundamentally different and more sophisticated approach. Rather than adding a fixed constant, it estimates the true probability of unseen events using information about the frequency of rare events in the data itself.

The key insight, due to Alan Turing and I. J. Good (developed during World War II for cryptanalysis and later published in 1953), is this: the probability of seeing a new n-gram, one you haven't seen before, can be estimated from the fraction of n-grams you saw exactly once. Things you've seen only once are "almost" like things you haven't seen at all, and they give you a statistical foothold for estimating the probability of completely novel events.

This is a remarkably elegant idea. The problem is that you can't directly observe the probability of something you've never seen. But you can observe how many things appeared exactly once, and use that as a proxy for the rate at which you're still missing things.

Define $N_c$ as the frequency of frequency $c$: the number of distinct n-grams that occur exactly $c$ times in the training corpus. This is sometimes called the "count of counts" or "frequency spectrum."

For example:

• $N_0$ = number of possible n-grams never seen (conceptually very large)
• $N_1$ = number of n-grams seen exactly once ("hapax legomena")
• $N_2$ = number of n-grams seen exactly twice
• And so on...

The sequence $N_1, N_2, N_3, \ldots$ reveals the shape of the count distribution. In natural language, this sequence is always steeply decreasing: many n-grams appear once, fewer appear twice, even fewer appear three times, and so on. This follows from Zipf's Law, which we encountered in the chapter on N-gram Language Models.

Good-Turing estimation defines an adjusted count $c^*$ for any n-gram with raw count $c$. The core idea is to replace each raw count $c$ with an estimate that accounts for the systematic underestimation caused by data sparsity:

where:

• $c$: the raw count of the n-gram
• $c^*$: the Good-Turing adjusted count (what the count "should" be given the shape of the distribution)
• $N_c$: the number of distinct n-grams with raw count exactly $c$
• $N_{c+1}$: the number of distinct n-grams with raw count exactly $c + 1$

The formula says: if you want to estimate the "true" probability of n-grams seen $c$ times, look at how many n-grams were seen $c+1$ times. The ratio $N_{c+1} / N_c$ tells you about the shape of the count distribution.

Think of it this way. Suppose you collect a new independent sample of the same text distribution. Some of the n-grams you never saw in the original corpus will appear in this new sample, and some of those n-grams will appear exactly once. The fraction of the original probability mass coming from never-seen events is approximately $N_1 / N$, where $N$ is the total number of tokens. This gives you a foothold for estimating the total probability mass that belongs to the "unseen" category.

More generally, the adjusted count $c^*$ for n-grams with raw count $c$ adjusts upward when $N_{c+1}$ is large relative to $N_c$ (suggesting there are many n-grams with count $c$ that, in another sample, would have appeared $c+1$ times) and adjusts downward when $N_{c+1}$ is small relative to $N_c$.

For the total probability of unseen n-grams (count = 0), Good-Turing gives a direct estimate: it should equal the fraction of tokens that were singletons. Formally:

where:

• $N_1$: the number of distinct n-grams seen exactly once
• $N$: the total number of tokens in the training corpus

This is the fraction of the probability mass assigned to all unseen events collectively. We then divide this evenly among all unseen n-grams, giving each unseen n-gram a probability of $N_1 / (N \cdot N_0)$.

The formula has a beautiful consistency property: you can verify that the adjusted counts, when summed and normalized, produce a valid probability distribution. The total probability mass remains 1.

Good-Turing estimation has several practical limitations that arise when you try to apply it to real data.

The most significant limitation is that the ratio $N_{c+1}/N_c$ becomes unreliable for large values of $c$. When $c$ is large (say, 20 or more), $N_c$ and $N_{c+1}$ may both be very small integers, making the ratio noisy. If $N_5 = 3$ and $N_6 = 1$, then $N_6/N_5 = 1/3$, which might just be random fluctuation rather than a meaningful signal. In practice, Good-Turing is only applied for small values of $c$ (typically $c \leq 5$). For larger counts, the MLE estimate is usually used directly because the probability estimates are already reliable enough.

The $N_c$ sequence can also be erratic for intermediate values of $c$. Simple Good-Turing (SGT) addresses this by fitting a smooth curve through the $N_c$ values before using them in the formula. This prevents the ratio from being dominated by random spikes in the frequency-of-frequency distribution.

Good-Turing also has no mechanism for out-of-vocabulary words: it handles unseen n-grams of known words, but if a word itself is novel, you need a separate strategy. For test data containing words never seen in training, even the best smoothing of the n-gram model breaks down unless you have a dedicated unknown-word handling strategy.

Despite these limitations, Good-Turing provides a principled statistical foundation for understanding what "unseen probability" should be, and it motivates more sophisticated methods that build on its frequency-of-frequency insight.

Laplace and Good-Turing both focus on a single n-gram order and address the zero-count problem in isolation. A more powerful idea is to combine evidence from different orders: use trigrams when you have enough data, but fall back to bigrams or unigrams when you don't. This captures a natural intuition. If you've seen "San Francisco" 1,000 times and "San Francisco Giants" 200 times, but never "San Francisco aardvark," the best estimate for P("aardvark" | "San Francisco") comes from the general bigram distribution for words following "Francisco," not from the trigram count alone.

There are two main ways to combine n-gram orders: interpolation and backoff. They differ in philosophy but often produce similar results.

Interpolation mixes the probabilities from different n-gram orders using learned weights. The idea is to always use all orders simultaneously, weighted by how reliable each one is. For a trigram model with interpolation, the probability of $w_i$ given its two-word context combines trigram and bigram predictions with the unigram prediction:

where:

• $\lambda_1, \lambda_2, \lambda_3$: mixing coefficients satisfying $\lambda_1 + \lambda_2 + \lambda_3 = 1$ and each $\lambda_i \geq 0$
• $P_3(w_i \mid w_{i-2}, w_{i-1})$: the trigram MLE probability
• $P_2(w_i \mid w_{i-1})$: the bigram MLE probability
• $P_1(w_i)$: the unigram MLE probability

The key is that all three probabilities are always present in the mixture. Even when the trigram count is zero, the bigram and unigram terms ensure a positive overall probability. The weighted sum is always positive as long as the unigram probability is positive (which it is for any word that appeared in training).

The $\lambda$ weights are estimated using Expectation-Maximization (EM) on held-out data. This is the method of Jelinek and Mercer (1980), hence the name. The EM procedure alternates between computing the expected contribution of each n-gram order given the current weights, and then updating the weights to maximize the likelihood of the held-out data. This converges to a local maximum fairly quickly.

A more powerful variant makes the weights context-dependent: if the trigram context has been seen many times in training, give more weight to $\lambda_3$; if the context is rare, lean more on $\lambda_2$ and $\lambda_1$. This deleted interpolation method adapts the mixing to how much statistical evidence each order has for the given context. You estimate $\lambda$ values for each distinct context rather than using global values, which captures the fact that a trigram with context count of 1,000 is far more reliable than one with context count of 3.

Interpolation works well but has a conceptual limitation: it mixes probabilities from all orders all the time, even when the higher-order estimate is reliable and specific. The mixing somewhat dilutes the high-quality estimate with lower-quality ones. If the trigram is very well-attested, the bigram information is mostly noise that drags down the probability slightly.

Backoff takes a different philosophy: use the highest-order estimate when the context has been seen enough times, and fall back to a lower-order model only when the count is zero. The most influential backoff scheme is Katz backoff (1987).

The core intuition is: trust the data when you have it, back off when you don't. When the trigram "San Francisco aardvark" has a nonzero count, use the trigram probability. When it's zero, fall back to the bigram P("aardvark" | "Francisco"), scaled by a factor that preserves the probability distribution.

Katz backoff uses Good-Turing-style discounting to set aside probability mass, then distributes it through backoff. The probability is:

where:

• $C^*$: the Good-Turing discounted count (always less than or equal to the raw count $C$)
• $\alpha(w_{i-n+1}^{i-1})$: a backoff weight that ensures the probabilities sum to 1 over all possible next words
• $P_{\text{Katz}}(w_i \mid w_{i-n+2}^{i-1})$: the Katz probability using a shorter context (one word less)

The discounting of seen n-grams is required. Without it, when you back off to a lower-order model for unseen n-grams, the total probability would exceed 1 (because the seen n-grams already use up all the probability mass under the context). By pre-discounting every seen n-gram slightly, Katz creates "leftover" probability mass that can be distributed to unseen n-grams via backoff.

The backoff weight $\alpha$ ensures that the leftover probability mass (after discounting seen n-grams) is allocated proportionally to the lower-order model. It is defined as:

where:

• The numerator is the leftover probability mass after all discounted seen n-grams take their share
• The denominator normalizes so that the backoff distribution sums to 1

Katz backoff is computationally efficient and works well in practice. The main drawback is that it uses Good-Turing-style discounting, which can be unreliable for larger counts. Also, the backoff structure means it never blends in higher-order evidence when backing off, which sometimes leaves useful signal on the table.

Interpolation and backoff represent two fundamentally different approaches to the same problem, and they have different strengths.

Interpolation always uses all orders, which means even when you have zero trigram evidence, you smoothly blend in bigram and unigram evidence. This prevents sharp discontinuities in the probability estimates. The downside is that even well-attested trigrams get diluted by bigram and unigram noise.

Backoff uses the highest-order estimate when available, which preserves the precision of specific n-gram observations. But the transition from using a trigram to backing off to a bigram is a hard step function: if the trigram count is 0, you get bigram, and if it's 1, you get (discounted) trigram. This can produce undesirable behavior near the boundary.

In practice, both methods perform similarly for large corpora. The more important distinction is the choice of discount and the choice of lower-order distribution, which is where Kneser-Ney makes its key innovation.

Before introducing Kneser-Ney, we need to understand absolute discounting, which supports Kneser-Ney's most useful idea.

Absolute discounting is based on a remarkable empirical observation made by Church and Gale (1991): when you subtract a constant $d$ from every non-zero bigram count, the resulting adjusted counts closely match the Good-Turing adjusted counts across the whole count spectrum. In other words, Good-Turing's sophisticated per-count calculation can be approximated simply by subtracting a fixed discount $d$ from every non-zero count, using the same $d$ regardless of the count value.

This is surprising. You might expect that a bigram seen 2 times needs a different proportional discount than one seen 20 times. But Church and Gale found empirically that subtracting the same constant $d \approx 0.75$ from both cases produces adjusted counts very close to what Good-Turing would give. The reason is that the ratio $N_{c+1}/N_c$ turns out to be approximately constant for small values of $c$ in most natural language distributions, which means the Good-Turing adjustment is approximately linear in $c$ for small counts, which in turn means subtracting a constant works well.

The absolute discounting formula combines a discounted seen-bigram term with a lower-order interpolation term:

where:

• $d$: the discount parameter, typically between 0 and 1 (often around 0.75), subtracted from every non-zero bigram count
• $\lambda(w_{i-1})$: a normalization constant ensuring all conditional probabilities sum to 1
• $P_{\text{lower}}(w_i)$: a lower-order (backoff or interpolation) probability for $w_i$

The $\max(\cdot, 0)$ ensures we never give a negative probability to seen n-grams. For very rare n-grams (count = 1 or 2), $C - d$ is still positive (since $d < 1$), so this clamp is usually not triggered unless $d > 1$.

The normalization constant $\lambda$ captures the total probability mass that was removed from the seen bigrams:

where:

• $\bigl|\{w : C(w_{i-1}, w) > 0\}\bigr|$: the number of distinct words that follow $w_{i-1}$ in the training corpus (the number of distinct bigram completions)
• $C(w_{i-1})$: the total count of $w_{i-1}$

The numerator $d \cdot \bigl|\{w : C > 0\}\bigr|$ equals the total probability mass removed from seen bigrams (each of the distinct continuations loses $d / C(w_{i-1})$ in probability). The denominator normalizes this so that $\lambda$ represents the fraction of mass to be redistributed.

Church and Gale estimated the optimal discount as:

where:

• $N_1$: the number of distinct bigrams seen exactly once
• $N_2$: the number of distinct bigrams seen exactly twice

This formula is surprisingly accurate: in most real corpora, $d$ ends up close to 0.75. The intuition behind the formula is that it minimizes the average squared error between the absolute-discounting adjusted counts and the Good-Turing adjusted counts, given the observed frequency-of-frequency distribution.

The key insight from absolute discounting is that the same discount works well across a wide range of counts. Whether a bigram appeared 2 times or 200 times, subtracting $d \approx 0.75$ gives a good adjusted count. This is much simpler than Good-Turing's per-count estimation, and it performs nearly as well because the Good-Turing adjustments are themselves nearly constant for typical natural language count distributions.

We now arrive at Kneser-Ney smoothing (Kneser and Ney, 1995), which is widely considered the best-performing standard smoothing method for n-gram language models. Kneser-Ney builds directly on absolute discounting but introduces a brilliant new idea for the lower-order distribution, one that addresses a fundamental flaw in all previous methods.

In absolute discounting (and Katz backoff), when we back off to a lower-order model, we use the ordinary unigram frequency as the lower-order distribution. A word that appears 10,000 times gets a higher lower-order probability than a word that appears 500 times. This seems natural: more frequent words should be more probable.

But this is wrong in a subtle way that has significant consequences. Consider the word "Francisco." It appears very frequently in many English corpora, but almost exclusively in the context "San Francisco." As a unigram, "Francisco" has high frequency. As a standalone word not following "San," it appears very rarely indeed. If our trigram probability for some context "...San Francisco" is unavailable and we back off to the unigram probability of "Francisco," we're dramatically overestimating how likely "Francisco" is to appear in that novel context.

The correct lower-order probability should reflect not how often a word appears total, but how often it appears in diverse contexts. A word like "Francisco" that's highly constrained to specific contexts should have a low lower-order probability. A word like "the" that appears after a huge variety of words should have a high lower-order probability. The unigram frequency conflates these two things, because a word can accumulate high frequency either by appearing often across many contexts or by appearing very often in just one or two fixed phrases.

This is not a corner case. Many high-frequency words in English are tightly bound to specific contexts: "Francisco" follows "San," "Vegas" follows "Las," "Kong" follows "Hong," "Turing" follows "Alan" in technical text. Using raw unigram frequency as the lower-order distribution systematically overestimates such words when they appear in novel contexts.

Kneser and Ney formalize this intuition with the continuation probability: the probability that a word $w$ completes a new, previously unseen bigram. This is estimated as the number of distinct preceding words that $w$ has appeared with, divided by the total number of distinct bigrams:

where:

• $\bigl|\{v : C(v, w) > 0\}\bigr|$: the number of distinct words $v$ that precede $w$ in the training corpus (the "continuation count" of $w$)
• $\bigl|\{(u, v) : C(u, v) > 0\}\bigr|$: the total number of distinct bigrams in the training corpus (is a normalizing constant)

For "Francisco," the continuation count is small: only "San" precedes it in typical text (and perhaps "Vice" in phrases like "Vice Francisco" in a translated corpus), so the continuation count is essentially 1. The KN unigram probability for "Francisco" is therefore very small.

For "the," the continuation count is enormous: "the" follows virtually every kind of word, so it has appeared as the second word in many thousands of distinct bigrams. The KN unigram probability for "the" is very high, correctly reflecting that it can complete almost any context.

For "on," the situation is intermediate: "on" follows many words (sat on, walked on, focused on, based on, ...) and has a moderate continuation count that accurately reflects its versatility as a word that can appear in many different positions.

This directly captures the property we want: the lower-order probability of a word should measure its tendency to appear in new, diverse contexts, not just its raw frequency.

Kneser-Ney smoothing for bigrams combines the discounted bigram term (using the same absolute discount $d$ from the previous section) with the continuation probability as the lower-order distribution:

where:

• $d$: the discount parameter (typically 0.75, estimated as $N_1 / (N_1 + 2N_2)$ from the training bigram counts)
• $\lambda(w_{i-1}) = \dfrac{d \cdot \bigl|\{w : C(w_{i-1}, w) > 0\}\bigr|}{C(w_{i-1})}$: the interpolation weight (probability mass freed up by discounting)
• $P_{\text{KN}}(w_i)$: the Kneser-Ney continuation probability for $w_i$, as defined above

The structure is identical to absolute discounting, with one difference: $P_{\text{lower}}$ is replaced by $P_{\text{KN}}$, the continuation probability, instead of the MLE unigram probability.

For higher-order models (trigrams, etc.), the recursion continues at each level using continuation counts rather than raw counts. For a trigram model:

where:

• $C(w_{i-2}, w_{i-1}, w_i)$: the raw trigram count
• $C(w_{i-2}, w_{i-1})$: the raw bigram count of the context
• $\lambda(w_{i-2}, w_{i-1})$: the interpolation weight at the trigram level, defined analogously to the bigram case
• $P_{\text{KN}}(w_i \mid w_{i-1})$: the Kneser-Ney bigram probability (using continuation counts at the bigram level)

At the bigram level within the trigram recursion, the "count" for $C(w_{i-1}, w_i)$ is replaced by the number of distinct words that precede the bigram $w_{i-1} w_i$, rather than the raw bigram count. This generalization ensures that at every level of the recursion, the distribution reflects diversity of contexts rather than raw frequency. The key property that makes Kneser-Ney so powerful is this consistent application of continuation counts at all lower-order levels.

Modified Kneser-Ney (Chen and Goodman, 1998) extends the basic Kneser-Ney by using different discount values for different count magnitudes, rather than a single discount $d$. The key observation is that n-grams seen exactly once are much more uncertain than n-grams seen 10 times, and both deserve different treatment than n-grams seen 100 times. A single discount parameter can't capture all three behaviors simultaneously.

The modified probability formula becomes:

where $D(c)$ is the count-dependent discount function:

The three discount values $d_1, d_2, d_{3+}$ are estimated from the data using frequency-of-frequency counts. The estimation procedure introduces an auxiliary quantity $Y$ and then computes each discount:

where:

• $Y$: auxiliary normalization factor derived from singleton and doubleton counts
• $N_1, N_2, N_3, N_4$: frequency-of-frequency counts (number of distinct bigrams with count 1, 2, 3, 4 respectively)
• $d_1, d_2, d_{3+}$: the discounts for n-grams seen once, twice, or three-or-more times

The intuition behind these formulas is that they are derived from the Good-Turing framework, setting each discount to approximately minimize the expected squared error between the discounted counts and the "true" expected counts implied by Good-Turing. Because singletons are the most uncertain (by definition, we've only seen them once), they receive the largest absolute discount. Doubletons are more stable, and n-grams seen three or more times are treated as reliable enough to discount less aggressively.

In practice, $d_1$ typically comes out around 0.5-0.6, $d_2$ around 0.7-0.8, and $d_{3+}$ around 0.8-0.9. This graduated discounting scheme more accurately matches the Good-Turing ideal than a single discount value.

Chen and Goodman showed that modified Kneser-Ney consistently outperforms the original single-discount version across a variety of corpora and n-gram orders. Modified Kneser-Ney is the version used in most practical implementations today, including the popular KenLM toolkit, which is one of the most widely used n-gram language model implementations in NLP and speech recognition.

Let's implement each smoothing method step by step, building up to Kneser-Ney. We'll use a simple corpus to make the computations visible and verifiable.

First, let's prepare a small corpus and build the basic counting infrastructure. We'll use a slightly extended corpus so that the frequency-of-frequency statistics have enough variety to be meaningful.

Now let's implement Laplace and add-k smoothing functions and compare them to MLE for both seen and unseen bigrams.

The discount ratio shows how much of the original count is preserved. A ratio below 1 means we're reducing the effective probability of this bigram. Laplace with $k=1$ discounts aggressively for low counts, bringing a count-1 bigram down to roughly 10% of its original probability in this example. Add-k with $k=0.1$ is more conservative, and $k=0.01$ barely discounts at all. The key insight is that none of these methods differentiate between how much they discount based on the structure of the language, they just use the same mechanical formula for all contexts.

Now let's implement Good-Turing and examine the frequency-of-frequency distribution for our corpus.

The shaded region shows the probability mass that Good-Turing redistributes from seen to unseen n-grams. For our small corpus, the adjustments may be large because $N_c$ values fluctuate heavily with so few samples. In a real corpus of millions of sentences, the $N_c$ sequence is much smoother and the Good-Turing estimates are more reliable.

Now let's implement absolute discounting, which approximates Good-Turing with a single constant discount.

Now let's implement Kneser-Ney. The key addition is computing continuation counts for each word.

The contrast between the two plots reveals the power of the continuation count. In the MLE plot, words rank by their raw frequency in the corpus. In the KN continuation plot, words rank by how many distinct predecessors they have, capturing their contextual versatility. This is exactly the signal that makes Kneser-Ney a superior lower-order distribution.

Let's now evaluate all four methods on a held-out set of test sentences using perplexity as the evaluation metric.

The U-shaped curve in the add-k perplexity chart is informative. Too-small $k$ fails because unseen bigrams get near-zero probability and the test sentences contain many novel combinations. Too-large $k$ fails because it smooths away the evidence from well-attested bigrams, making the model approximately uniform. The optimal $k$ sits in the middle, but even that optimum falls short of Kneser-Ney, which achieves lower perplexity without any tuning of $k$ at all.

The key parameters for smoothing methods are:

• k (add-k smoothing): The additive constant. Tune on a held-out development set. Typical range: 0.001 to 0.5. Smaller values preserve more of the MLE signal; larger values move toward uniform redistribution.
• d (absolute discounting / Kneser-Ney): The discount subtracted from every non-zero count. Estimated automatically as $N_1 / (N_1 + 2N_2)$ from the training data. Typically around 0.75 for most natural language corpora.
• n (n-gram order): Higher orders capture more context but suffer more from data sparsity. Smoothing is more important for higher-order models. Trigrams with Kneser-Ney often give the best balance of expressiveness and reliability.

Understanding which smoothing method to use requires comparing them systematically. The standard evaluation metric is perplexity on held-out test data (covered in depth in the next chapter). But some general principles hold across many experiments and deserve careful attention.

Laplace smoothing performs poorly on realistic corpora. The fundamental problem is that it adds $|V|$ to the denominator, which is enormous for real vocabularies. This effectively discounts all n-gram counts massively and allocates an implausibly large fraction of probability mass to unseen events. Chen and Goodman's 1998 empirical comparison showed Laplace performing worst among all smoothing methods tested, across every corpus and n-gram order they examined.

Add-k with tuned $k$ can perform reasonably well, significantly better than Laplace. But it requires a held-out validation set and still uses the same discount for all count values, which is suboptimal. The sensitivity to $k$ means that a poorly tuned model can be worse than Laplace if $k$ is set too small.

Good-Turing estimation performs better than add-k for low-count n-grams (counts 1-5) but is unreliable for higher counts and requires a separate strategy for those. In practice, Good-Turing is rarely used in isolation but rather as a building block for better methods.

Katz backoff with Good-Turing discounting performs well and was the standard method for many years in speech recognition and machine translation systems. It's computationally efficient and handles the count-dependent discounting better than add-k. Many successful systems from the 1990s and early 2000s used Katz backoff.

Absolute discounting performs comparably to Katz in most settings and is significantly simpler to implement. The estimated discount from $N_1 / (N_1 + 2N_2)$ requires no tuning and works well across corpora.

Kneser-Ney and modified Kneser-Ney consistently outperform all other methods, especially for higher-order n-grams. The improvement comes entirely from the continuation-count lower-order distribution. On the Penn Treebank benchmark, for example, modified Kneser-Ney with trigrams achieves perplexity around 100-120 on standard test splits, while Laplace smoothing achieves perplexity many times higher. On the Wall Street Journal corpus, Kneser-Ney trigram models typically reduce perplexity by 30-40% relative to well-tuned add-k, a substantial difference that translates directly into improved speech recognition word error rates.

The following table summarizes the characteristics of each method:

An important pattern in empirical comparisons is that the performance gap between Kneser-Ney and simpler methods grows as the n-gram order increases. For unigrams, there's no smoothing to be done. For bigrams, the differences are meaningful. For trigrams, Kneser-Ney's advantage is substantial. For 4-grams and 5-grams, it's decisive.

The reason is that higher-order n-grams suffer from more severe data sparsity, which means the lower-order backoff model is consulted more frequently. When you back off from 5-grams to 4-grams to trigrams to bigrams to unigrams, the quality of the unigram distribution matters enormously, because many n-gram probability estimates ultimately depend on it. Kneser-Ney's continuation probability is a much better unigram distribution for this purpose than MLE frequency, and this advantage propagates up through all the higher-order calculations.

This is why modified Kneser-Ney remained the recommended method for n-gram language models for over two decades. Even as corpora grew from millions to billions of words, the continuation probability remained a superior choice for the lower-order distribution. The principle behind it, that a good lower-order distribution should measure contextual diversity rather than raw frequency, is a fundamental insight that doesn't become less true as data increases.

Smoothing was an essential advance for making n-gram language models usable in real applications. Without it, the models would assign zero probability to almost any sentence from the real world, making them impossible to evaluate or deploy. But understanding the limits of smoothing is equally important for understanding what eventually replaced n-gram models.

All smoothing methods share a fundamental limitation: they are patching over the inadequacy of n-gram models rather than solving the underlying problem. No matter how sophisticated the smoothing, an n-gram model still can't generalize beyond the literal patterns in its training data. It can't use grammatical knowledge, semantic understanding, or world knowledge. If "the crimson aardvark" never appeared in training data, smoothing gives it a small probability, but the model has no principled basis for estimating whether "crimson" is a plausible adjective for "aardvark" given what it knows about adjective-noun relationships. The model simply doesn't have that kind of relational knowledge.

This matters practically. Two sentences that are semantically almost identical can receive very different probability estimates if they use different surface forms. "The automobile departed" and "The car left" are semantically similar, but an n-gram model trained on one would give low probability to the other if the exact bigrams and trigrams differ. Smoothing gives unseen n-grams small positive probabilities, but it doesn't learn that "automobile" and "car" are semantically similar, so it can't transfer evidence from one to the other.

This limitation is precisely what motivated the development of neural language models. Instead of counting n-grams and smoothing, a neural model learns a continuous representation of each word (an embedding) and can generalize across semantically similar words. "The crimson aardvark" might not appear in training, but if the model has seen "the red aardvark" and "the crimson rabbit," it can combine this evidence to assign a reasonable probability. This generalization ability is why neural language models eventually displaced n-gram models for most applications, despite the many decades of work invested in refining smoothing techniques.

N-gram models also face a practical scaling challenge. The number of distinct n-grams grows combinatorially with vocabulary size and n-gram order. A 5-gram model with a 100,000-word vocabulary has up to $100,000^5 = 10^{25}$ possible 5-grams. In practice, of course, only a tiny fraction of these are observed, and storage is proportional to the observed count, not the theoretical maximum. But even the observed fraction is enormous: billion-word corpora produce hundreds of millions of distinct trigrams. Storing and querying these efficiently requires specialized data structures and significant engineering effort.

Modern n-gram language model implementations like KenLM use compressed trie data structures to reduce memory usage, and techniques like quantization to compress the floating-point probability values. Even with these optimizations, very large n-gram models (trained on hundreds of billions of words with vocabulary sizes over a million) require hundreds of gigabytes of memory. Neural language models, in contrast, represent the entire language distribution in a fixed-size parameter matrix and can process any vocabulary size with a fixed memory footprint, which is a structural advantage that becomes more pronounced as scale increases.

N-gram models with Kneser-Ney smoothing remain competitive in several important settings that shouldn't be underestimated.

In low-data regimes, when training data is limited to a few million words or less, neural models can overfit heavily, and simple n-gram models with good smoothing can outperform them. This matters for specialized domains where annotated data is expensive: clinical notes, legal documents, specialized technical domains.

For computational constraints, an n-gram model can be queried in microseconds with a fixed memory footprint once built. Neural language model inference requires matrix multiplications and typically needs a GPU for reasonable latency. In embedded systems, mobile devices, or any setting where compute is severely constrained, n-gram models remain practical.

Interpretability is another advantage. N-gram probabilities are directly interpretable as counts and continuation statistics. You can inspect exactly which n-grams drove a high or low probability estimate. Neural models are opaque: understanding why a neural model assigned a particular probability requires complex analysis.

Ensembling is a less obvious but practically important use. N-gram models with Kneser-Ney are often used as components in ensembles with neural models, particularly in production speech recognition systems. The n-gram model provides fast, lightweight estimates that complement the slower but more powerful neural component.

The theoretical insights from smoothing also carry forward into the neural era in non-trivial ways. The idea that lower-order distributions should reflect how well a word appears in diverse contexts (the core of Kneser-Ney) is mirrored in neural models by the use of embeddings trained with objectives that reward distributional context. Word2Vec, in particular, trains embeddings by predicting context words, which is directly related to the continuation count idea: a word that appears in many contexts will have a more distributed embedding that generalizes better.

The importance of not assigning too much mass to unseen events is reflected in regularization and weight decay in neural networks. Just as Laplace over-smoothing is harmful because it gives too much mass to unseen n-grams, neural models without regularization overfit in analogous ways: they assign too much probability to training patterns and not enough to generalizations.

The frequency-of-frequency analysis from Good-Turing connects to the study of Zipf's Law and heavy-tailed distributions in deep learning, where understanding the distribution of training examples is necessary for designing good learning algorithms. The careful empirical work by Church and Gale, along with Kneser and Ney, was extended by Chen and Goodman. Their work on count statistics and probability estimation established a rigorous tradition of empirical evaluation that modern deep learning has inherited.

In summary, smoothing made the problem of probability estimation in discrete spaces precise enough that researchers could study it systematically. That precision, and the conceptual framework it developed, informed how we think about generalization in all language models, including the transformer-based models covered later in this book.

This chapter covered the full family of smoothing techniques that make n-gram language models practical:

• The core problem: MLE assigns zero probability to any n-gram not seen in training, collapsing sentence probabilities to zero. Data sparsity is severe: the number of possible n-grams grows exponentially with order and vocabulary size, vastly outpacing any training corpus.
• Laplace (add-one) smoothing: Adds 1 to every count before normalizing. Simple and intuitive, but poor in practice because it over-redistributes probability mass. The fixed additive adjustment does not scale with count magnitude.
• Add-k smoothing: Generalizes Laplace with a tunable parameter $k < 1$. Better than Laplace but still uses a single discount for all counts and treats all unseen bigrams identically.
• Good-Turing estimation: Uses the frequency-of-frequency distribution to estimate adjusted counts. The formula $c^* = (c+1) N_{c+1} / N_c$ is principled and consistent, but unreliable for large counts where $N_c$ values are sparse.
• Interpolation and backoff: Combine multiple n-gram orders. Jelinek-Mercer interpolation mixes all orders with learned weights; Katz backoff uses the highest reliable order and backs off to lower ones when n-gram counts are zero.
• Absolute discounting: Subtracts a fixed discount $d \approx N_1/(N_1 + 2N_2)$ from every non-zero count and redistributes the saved mass through a lower-order model. Approximates Good-Turing with a single constant that works well empirically.
• Kneser-Ney smoothing: Replaces the lower-order MLE unigram distribution with a continuation count distribution, which measures how often a word appears in diverse preceding contexts. Words tightly bound to specific phrases (like "Francisco" after "San") get low continuation probability, while versatile words (like "the") get high continuation probability. This correctly captures the relevant information for backing off.
• Modified Kneser-Ney: Uses three separate discount values $d_1, d_2, d_{3+}$ for counts of 1, 2, and 3+, consistently outperforming single-discount Kneser-Ney. This is the version used in practical toolkits like KenLM.

The progression from Laplace to Kneser-Ney is a story of increasingly precise answers to the question: "What information in the training data is most informative for estimating probabilities of unseen events?" Laplace uses almost none of it. Good-Turing uses the frequency-of-frequency structure. Kneser-Ney uses the distributional diversity of each word's contexts. Each step improves on the previous method by using more of the structure of natural language.

In the next chapter, we'll formalize the perplexity metric used throughout this chapter to compare models, derive its relationship to cross-entropy and bits-per-character, and discuss why it's both a useful and sometimes misleading evaluation criterion.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about smoothing techniques for n-gram language models.