Classical NLP That Still Works
N-gram language models and smoothing
An n-gram language model predicts the next word from the last few words it saw, and smoothing stops it from calling any unseen sentence completely impossible.
- 12 min read
- 3 reading levels
- Published
Read these first
On this page 6
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
An n-gram language model guesses the next word by looking only at the last few words before it.
Think about how well you can finish a friend's sentence. "Pass me the..." — salt, sugar, remote. You are not thinking about the whole conversation from an hour ago. You are using the last two or three words to make a good guess.
That is exactly what an n-gram model does. Except it learned its guesses by counting. It counted, across a huge amount of text, which words tend to follow which other words.
Why it exists
Before today's AI chatbots, people still needed software that could judge whether a sentence sounded like real language. Spell-checkers needed it. Early machine translation needed it. Voice-typing needed it too. It had to decide between "recognize speech" and the nonsense "wreck a nice beach", which sound almost identical out loud.
The n-gram model was the practical answer. Count how often word sequences appear in real text, then use those counts to score how likely a sentence is.
How it works
"N-gram" means "a chunk of N words in a row". A bigram is 2 words, a trigram is 3.
Sentence: "I drink chai every morning"
Bigrams: (I, drink) (drink, chai) (chai, every) (every, morning)To predict the next word after "I drink", the model looks at every time "I drink" appeared in training. It checks what came right after, most often.
Training text saw "I drink" followed by:
chai -> 40 times
coffee -> 35 times
water -> 10 times
the -> 2 times
So the model predicts "chai" most confidently, "coffee" close behind.Chain enough of these guesses together, one word at a time. The model can then score, or even generate, a whole sentence.
The problem that needed a fix
What if the model needs to score a phrase it has genuinely never seen, like "I drink neem juice"? If "drink neem" never appeared anywhere in training, its raw count is zero. A probability of exactly zero for one phrase makes the entire sentence's probability zero too. That happens no matter how normal the rest of it sounds.
That is far too harsh. A phrase being new does not mean it is impossible. It might be rare, or the training text was too small to have seen everything.
Smoothing is the fix. It gives every possible word pair a small amount of probability, borrowed from the pairs it saw a lot. Even a pair the model never saw gets a small share. The simplest version, called Laplace smoothing, pretends every possible pair was seen one extra time before counting starts. Nothing is ever truly impossible anymore — only unlikely.
Where you have already seen it
- Autocomplete and predictive text, before phones switched to today's larger AI models.
- Spell-checkers, judging whether your correction sounds like real language.
- "Did you mean...?" on search engines, comparing how likely different phrasings are.
Remember this
- N-gram models guess the next word using only the last N-1 words, not the whole sentence.
- Without a fix, any sequence the model never saw scores a probability of exactly zero.
- Smoothing spreads a little bit of probability to unseen sequences, so nothing is treated as flatly impossible.
What to learn next
- Tokenization — n-grams are built from tokens, so this decides what a "word" even is here.
- Word2Vec — a different way of learning from word neighbours, built on prediction instead of counting.
- Attention — the modern replacement, which looks at the whole sentence, not only the last few words.
Developer — Code and libraries.
Two short programs. The first builds a real bigram model with smoothing and scores a sentence. The second shows exactly what breaks without the smoothing.
Both run on plain Python. No downloads, no GPU.
Setup
Nothing to install — this uses only the standard library.
python --version # 3.9 or newerA smoothed bigram model, from scratch
from collections import Counter
corpus = [
"<s> i drink chai every morning </s>",
"<s> i drink coffee every morning </s>",
"<s> she drinks tea every evening </s>",
"<s> i drink chai every evening </s>",
]
tokens = [sent.split() for sent in corpus]
unigrams = Counter()
bigrams = Counter()
for sent in tokens:
unigrams.update(sent)
bigrams.update(zip(sent, sent[1:]))
V = len(unigrams) # vocabulary size, needed by the smoothing formula
def bigram_prob(w1, w2):
# add-one (Laplace) smoothing: every possible pair gets a small floor,
# so a pair the model never saw still gets a non-zero probability
return (bigrams[(w1, w2)] + 1) / (unigrams[w1] + V)
test = "<s> i drink chai every evening </s>".split()
print("vocabulary size:", V)
print()
prob = 1.0
for w1, w2 in zip(test, test[1:]):
p = bigram_prob(w1, w2)
prob *= p
print(f"P({w2!r} | {w1!r}) = {p:.4f}")
n = len(test) - 1
perplexity = prob ** (-1 / n)
print()
print("sentence probability:", prob)
print("perplexity:", round(perplexity, 3))vocabulary size: 12
P('i' | '<s>') = 0.2500
P('drink' | 'i') = 0.2667
P('chai' | 'drink') = 0.2000
P('every' | 'chai') = 0.2143
P('evening' | 'every') = 0.1875
P('</s>' | 'evening') = 0.2143
sentence probability: 0.00011479591836734693
perplexity: 4.536Line by line
<s> and </s> mark the start and end of each sentence. Without them, the model has no way to learn which words tend to start a sentence, or when a sentence is expected to end.
bigrams[(w1, w2)] + 1 and unigrams[w1] + V are the whole of Laplace smoothing. Adding 1 to every possible pair's count, and V to the denominator to keep probabilities summing to 1 across the vocabulary. It is the simplest smoothing method that exists, and real systems use better ones — see the researcher block — but the core idea is identical.
Perplexity is a single number summarizing how "surprised" the model was by the test sentence. Lower is better. A perplexity of 4.5 roughly means the model was, on average, as uncertain as if it were guessing uniformly among 4 to 5 equally likely words at each step.
What happens without smoothing
from collections import Counter
corpus = [
"<s> i drink chai every morning </s>",
"<s> i drink coffee every morning </s>",
"<s> she drinks tea every evening </s>",
"<s> i drink chai every evening </s>",
]
tokens = [sent.split() for sent in corpus]
unigrams, bigrams = Counter(), Counter()
for sent in tokens:
unigrams.update(sent)
bigrams.update(zip(sent, sent[1:]))
test = "<s> she drink chai every morning </s>".split() # "she drink" never appeared together
print("bigrams in test sentence, and how often each was seen in training:")
for w1, w2 in zip(test, test[1:]):
print(f" ({w1!r}, {w2!r}) -> seen {bigrams[(w1, w2)]} times")
raw_prob = 1.0
for w1, w2 in zip(test, test[1:]):
p = bigrams[(w1, w2)] / unigrams[w1] # no smoothing at all
raw_prob *= p
print()
print("sentence probability with NO smoothing:", raw_prob)bigrams in test sentence, and how often each was seen in training:
('<s>', 'she') -> seen 1 times
('she', 'drink') -> seen 0 times
('drink', 'chai') -> seen 2 times
('chai', 'every') -> seen 2 times
('every', 'morning') -> seen 2 times
('morning', '</s>') -> seen 2 times
sentence probability with NO smoothing: 0.0One single unseen pair — ('she', 'drink'), seen zero times — collapses the probability of the entire six-word sentence to exactly zero, even though every other word pair in it was common. This is the concrete failure smoothing exists to prevent.
Common mistakes
Treating "sentence probability" as comparable across different sentence lengths. Longer sentences multiply together more probabilities under 1, so they are automatically less probable, regardless of quality. Always compare using perplexity, which normalizes for length, not raw probability.
Choosing too large an N for the size of your training text. A 4-gram or 5-gram model needs to see the same 4 or 5 word sequence repeated to learn anything. On a small corpus almost nothing repeats, and the model becomes indistinguishable from memorising the training set. See the "try it yourself" exercise in tokenization for the same small-corpus failure mode in a different algorithm.
Using Laplace smoothing in production. Add-one smoothing gives far too much probability mass to genuinely rare or nonsensical pairs, once vocabulary size V gets large. It is the right tool for learning the concept. It is not what production n-gram systems actually use — see the researcher block.
Try it yourself
Change test to "<s> i drink chai every morning </s>" — a sentence that actually appeared in the training corpus verbatim — and compare its perplexity to the one above. It should come out noticeably lower, because every bigram in it was seen at least twice, not once.
What to learn next
- Tokenization — what actually counts as one "word" before any of this counting starts.
- Attention — how modern models replaced "last N words" with "every word, weighted".
- BM25 — a different classical formula, scoring documents instead of predicting words.
Researcher — Mathematics and papers.
The Markov assumption
An n-gram language model approximates the probability of a token sequence w_1, ..., w_T using the chain rule of probability, then truncates the conditioning context to the last n-1 tokens:
P(w_1, ..., w_T) = product over t=1..T of P(w_t | w_1, ..., w_{t-1})
~= product over t=1..T of P(w_t | w_{t-n+1}, ..., w_{t-1})- The approximation is the Markov assumption of order
n-1: the next token depends only on the previousn-1tokens, not the full history.
Maximum likelihood estimates come directly from corpus counts:
P_MLE(w_t | w_{t-n+1}, ..., w_{t-1}) = count(w_{t-n+1}, ..., w_t) / count(w_{t-n+1}, ..., w_{t-1})Perplexity
PP(W) = P(w_1, ..., w_T) ^ (-1/T)- Equivalently,
PP(W) = exp( -(1/T) * sum_t log P(w_t | context) )— the exponential of the average negative log-likelihood per token, i.e. the model's cross-entropy in nats or bits, exponentiated. - Perplexity is interpretable as the size of an equivalent uniform vocabulary the model is, on average, as uncertain as. A perplexity of 50 means the model's average uncertainty at each step matches choosing uniformly among 50 options.
Smoothing methods, in order of sophistication
Laplace / add-one (used in the developer block): P(w_i | context) = (count + 1) / (count(context) + V). Simple, but assigns far too much mass to unseen events once V is large — it effectively assumes every unseen event is nearly as likely as a once-seen event, which is false for natural language's long tail.
Add-k: replace 1 with a tunable k < 1, chosen on held-out data. Reduces but does not eliminate the over-smoothing problem.
Good-Turing (Good, 1953, building on Turing's wartime cryptanalysis work): re-estimates the probability of an unseen event from the frequency of events seen exactly once, using the empirical observation that the count of once-seen events is a reasonable proxy for the rate of never-seen events.
Katz backoff (Katz, 1987): if the higher-order n-gram was unseen, fall back to a discounted lower-order estimate, recursively.
Kneser-Ney (Kneser & Ney, 1995), and its modified variant (Chen & Goodman, 1999): the empirical state of the art for count-based smoothing. Its key insight is continuation probability — a word's backoff weight should depend on how many distinct contexts it follows, not its raw frequency. This is why Kneser-Ney correctly down-weights a word like "Francisco", which is very frequent but almost always follows "San" specifically, versus a word that follows many different contexts. Chen & Goodman's 1999 empirical survey found modified Kneser-Ney the best-performing smoothing method across essentially every tested condition, and it remained the standard for count-based language models until neural methods replaced n-grams outright.
Complexity and scale
Training is O(T) — one pass over the corpus, incrementing counts. Storage for an unpruned n-gram model is O(min(V^n, number of distinct n-grams observed)); in practice the latter dominates for any real corpus. Industrial n-gram models (Google's Web 1T 5-gram corpus, 2006, built from a trillion tokens) prune rare n-grams aggressively and still require tens of gigabytes of storage — this storage cost, not modeling quality, was a major practical reason the field moved to neural language models, which store a fixed-size parameter set regardless of vocabulary or context length.
Key references
- Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal. Introduces entropy and the statistical language model concept the whole field builds on.
- Good, I. J. (1953). The Population Frequencies of Species and the Estimation of Population Parameters. Biometrika 40(3-4), 237–264.
- Katz, S. (1987). Estimation of Probabilities from Sparse Data for the Language Model Component of a Speech Recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing.
- Kneser, R. & Ney, H. (1995). Improved Backing-off for M-gram Language Modeling. ICASSP.
- Chen, S. F. & Goodman, J. (1999). An Empirical Study of Smoothing Techniques for Language Modeling. Computer Speech & Language 13(4), 359–394.
Current state and open problems
Pure count-based n-gram models are no longer the frontier — neural language models, from LSTMs onward, dominate on perplexity and every downstream task. But n-grams have not disappeared. They remain the backbone of fast, on-device predictive keyboards where a multi-billion-parameter model is infeasible, of speech recognition language-model rescoring in latency-critical pipelines, and of KenLM-style (Heafield, 2011) large-scale n-gram models still used as auxiliary signals in machine translation and as text-quality filters when curating training corpora for large neural models — an ironic role, since the corpora being filtered typically go on to train models that replace n-grams entirely.