N-Gram Models and Smoothing

Before transformers, before recurrent networks, the dominant language model was almost embarrassingly simple: count how often each word follows each short history in a huge corpus, and use the counts as probabilities. This is the n-gram model, and it powered production speech recognition and machine translation for roughly three decades. Understanding why it eventually lost to neural models, and exactly what problem it never solved, still frames how people talk about language-model probability today.

The Markov assumption and MLE by counting

The full chain rule needs P(word | entire preceding history), which is intractable to estimate directly: almost every long history in a real corpus is unique, so you have exactly one observed count to estimate a probability from, which is useless. N-gram models sidestep this with the Markov assumption: approximate P(word | history) using only the last n-1 words instead of the whole history. For a bigram model (n=2), the maximum-likelihood estimate is pure relative frequency:

P(w_i | w_i-1) = count(w_i-1, w_i) / count(w_i-1)

This is maximum-likelihood-estimation applied to the simplest possible case, a categorical distribution: no gradient descent needed, the closed-form MLE solution is just counting.

The zero-count problem

Any bigram that never appeared in training gets probability exactly zero. Sentence probability is a product of these conditional probabilities, so a single zero anywhere collapses the entire sentence's probability to zero, even if every other word choice in it was perfectly ordinary. This is not a rare edge case; it is the default outcome. With a realistic vocabulary, most possible bigrams simply never occur in even a very large training corpus, so an unsmoothed n-gram model assigns zero probability to nearly every sentence it has not effectively memorised. This is the sparse-data failure mode that entropy-and-surprise and cross-entropy-and-kl both point toward from the theory side: an event treated as truly impossible is infinitely surprising if it happens, and infinite surprise inside a sum is infinite loss.

Smoothing: stealing probability mass from the seen to give to the unseen

Laplace (add-one) smoothing adds 1 to every count before normalising, which guarantees no probability is ever exactly zero. It is simple, but with a large vocabulary it steals far too much mass from frequent, well-observed events to spread thinly across the enormous number of unseen ones, badly distorting the distribution.

Better methods back off or interpolate: blend the n-gram estimate with lower-order (n-1)-gram, (n-2)-gram, and unigram estimates, so an unseen trigram falls back on a well-estimated bigram instead of collapsing to zero. Kneser-Ney smoothing, the strongest classical method, refines this further: instead of backing off using the raw frequency of the lower-order term, it uses the number of distinct contexts that term has appeared in. A word like "Francisco" is frequent, but it appears almost exclusively after "San," so its raw frequency badly overstates how good a generic fallback guess it is for some other, genuinely novel context. Counting distinct contexts instead of raw occurrences corrects for exactly this. See Jurafsky and Martin's SLP3 for the full derivation.

Why n-grams still show up

Even after neural language models won decisively on quality, n-gram models stayed useful for years as a fast rescoring or shallow-fusion component bolted onto speech recognition and translation pipelines, because an n-gram lookup is a hash table access, orders of magnitude cheaper than a neural forward pass. And Shannon's original entropy-of-English estimates, the ancestor of every perplexity number reported today, were themselves produced using n-gram-style statistics and human guessing games (see entropy-and-surprise).

When it falls down

• Sparsity gets worse, not better, as n grows. A 5-gram model has an astronomically larger space of possible histories than a bigram model, so most 5-grams remain unseen even in a web-scale corpus, forcing heavy reliance on backoff and capping how much context an n-gram model can practically use. This is exactly the wall that made recurrent, and later attention-based, models attractive.
• No notion of similarity between words. "The cat sat" and "the dog sat" are entirely unrelated events to a count table, even though "cat" and "dog" behave almost identically distributionally in most contexts. Closing this gap is what dense embeddings were built for.
• Smoothing hyperparameters need re-tuning per domain. Discount values and interpolation weights are fit on held-out data and do not transfer cleanly across domains or languages; a smoothing scheme tuned for news text can perform badly on conversational text or source code without being re-fit.

Further reading

• Jurafsky and Martin, Speech and Language Processing, Ch. 3 (N-gram Language Models) - the canonical treatment of n-gram estimation and smoothing, including Kneser-Ney.
• Bengio et al., 2003, A Neural Probabilistic Language Model - the paper that began replacing count-based n-grams with learned distributed representations.