N-Gram Language Models: Predicting the Next Word With Counts

The Core Idea: Chain Rule Meets the Markov Assumption

A language model assigns a probability to a sequence of words w₁ w₂ … w_T. The exact factorization is the chain rule of probability:

P(w₁..w_T) = ∏ P(w_t | w₁ … w_{t-1})

The conditioning context grows without bound, so estimating P(w_t | w₁…w_{t-1}) directly is hopeless — you would need to have observed each full-length history. The n-gram model makes the (n−1)-order Markov assumption: the next word depends only on the previous n−1 words.

• Unigram (n=1): P(w_t) — ignores context entirely.
• Bigram (n=2): P(w_t | w_{t-1}).
• Trigram (n=3): P(w_t | w_{t-2} w_{t-1}) — the classic workhorse.

The estimator is the maximum-likelihood estimate (MLE): a plain conditional frequency count.

P(wₙ | w₁..wₙ₋₁) = count(w₁..wₙ) / count(w₁..wₙ₋₁)

You pad each sentence with n−1 start symbols <s> and one end symbol </s>; the </s> token is what lets the model represent “this sentence is complete,” and it is a common bug to forget it (your probabilities won't sum to 1 over all sentence lengths).

Training and Querying: Just Count, Then Divide

Training is embarrassingly simple: one linear scan that increments a hash-table entry per n-gram window. There is no gradient descent, no iteration to convergence — the MLE has a closed form.

for each sentence s (padded with <s> and </s>):
  for i in range(n-1, len(s)):
    gram   = s[i-n+1 : i+1]      // the n-gram
    ctx    = s[i-n+1 : i]        // its (n-1) context
    count[gram]  += 1
    count[ctx]   += 1

To score a next word at query time you do two hash lookups and one division — O(n) to hash the window, effectively O(1) for short n. To find the most likely next word given a context, you look up all continuations of that context. If you store the model as a trie (prefix tree) keyed by word IDs, the children of a context node are exactly its candidate next words, so top-k prediction is a bounded scan of that node's fan-out rather than a scan of the whole vocabulary.

• Data structure of choice: a trie of integer word IDs, or a set of hash maps (one per order). Google's production models used a compressed trie with quantized probabilities to fit billions of grams in RAM.
• Interning: map every word to a 32-bit ID first; you never store raw strings in the count tables.

Because probabilities of long sentences are tiny, always work in log space: replace the product ∏P with a sum Σ log P. This avoids floating-point underflow and turns the perplexity computation into a mean of logs.

Complexity: Where the Space Blows Up

Time. Training is a single pass: Θ(N) for a corpus of N tokens, since each position contributes O(1) amortized hash updates. There is no dependence on iterations because the estimator is closed-form — this is why n-grams train in minutes on corpora that take neural LMs GPU-days.

Query. Scoring one word is O(n) to build and hash the window — constant for fixed n. Scoring a length-T sentence is Θ(T·n). With backoff or interpolation the constant grows by a factor of n (you may consult every order from n down to 1), but it stays Θ(T·n).

Space is the real problem. The number of possible n-grams over a vocabulary of size V is Vⁿ. With V ≈ 10⁶ and n=3 that is 10¹⁸ — astronomically more than atoms you could store. In practice you only store observed n-grams, which by Heaps' law and Zipf's law grows sublinearly-to-linearly in N but is still enormous: Google's Web-1T release held ~1.2 billion 5-grams and shipped on six DVDs. The takeaway:

• Worst-case space: O(Vⁿ) — the reason nobody uses n > 5.
• Practical space: O(number of distinct observed n-grams), dominated by the highest order.
• Mitigations: count-based pruning (drop grams seen < k times), quantizing probabilities to 8 bits, and Bloom-filter language models that answer “have I seen this gram?” with tiny memory at the cost of false positives.

The Zero-Probability Catastrophe and Smoothing

MLE fails the instant you meet an n-gram absent from training: count = 0 ⇒ P = 0 ⇒ the entire sentence product becomes 0 and its log becomes −∞. Since a test set almost always contains unseen combinations of seen words, raw MLE is unusable. Smoothing steals probability mass from seen events and gives it to unseen ones.

• Add-one (Laplace): P = (count + 1) / (count(ctx) + V). Trivial, provably nonzero, but it over-smooths — with a large V it hands far too much mass to the vast sea of unseen grams. Add-k with k < 1 helps a little.
• Katz backoff (1987): if the n-gram was seen, use a discounted estimate (Good-Turing discounting); if not, back off to the (n−1)-gram, scaled by a normalizing weight α so probabilities still sum to 1.
• Interpolation (Jelinek-Mercer): always blend orders, P̂ = λ₃P₃ + λ₂P₂ + λ₁P₁, with the λ's tuned on held-out data (often via EM). Even seen trigrams borrow strength from bigrams.
• Kneser-Ney (1995), the gold standard: subtract a fixed discount D from every count and, crucially, estimate the lower-order model from continuation counts — how many distinct contexts a word follows, not how often it appears. This fixes the classic “San Francisco” failure: Francisco is frequent but almost never a novel continuation, so it should get low backoff probability. Modified Kneser-Ney (Chen & Goodman, 1998) uses three discounts and is the standard baseline.

Measuring Quality: Perplexity

You don't eyeball a language model — you measure its perplexity on held-out text, the standard intrinsic metric. Perplexity is the exponentiated average negative log-likelihood per word:

PP(W) = P(w₁..w_T)^(-1/T)
      = exp( -(1/T) Σ ln P(w_t | history) )

Interpret it as the weighted average branching factor: a perplexity of 100 means the model is, on average, as uncertain as if it had to choose uniformly among 100 words at each step. Lower is better. Perplexity is exactly the exponential of the cross-entropy between the true distribution and the model, tying the metric directly to Shannon entropy.

• On the classic Penn Treebank, a good Kneser-Ney trigram scores ≈ 140 perplexity; modern transformer LMs push below 20. The gap is precisely what neural context buys you.
• Warning: perplexity is only comparable across models with the same vocabulary and tokenization. Out-of-vocabulary handling (an <UNK> token) can make a model look artificially good if it hides rare words. Two models with different <UNK> rates are not comparable.

Where N-Grams Win — and Where They Break

Despite being eclipsed by neural models on raw quality, n-grams remain the right tool in several regimes:

• Ultra-low latency / on-device: a smartphone keyboard's autocomplete must answer in microseconds with a few megabytes of RAM. A pruned trigram trie does this; a transformer cannot.
• Interpretability & debuggability: every prediction traces to explicit counts. Regulated or safety-critical pipelines like that.
• Components inside larger systems: for decades, statistical machine translation (Moses) and speech recognition (HTK, Kaldi lattices) used an n-gram LM to rescore hypotheses. The KenLM and SRILM toolkits are still shipped in production ASR/MT stacks.

Where they break:

• No long-range dependencies. A trigram cannot connect a subject to a verb ten words later; the Markov horizon is n−1. This is the fundamental ceiling and the reason RNNs, then transformers, took over.
• No generalization across similar words. “the cat sat” and “the dog sat” are unrelated events to an n-gram — there is no notion that cat and dog are similar. Word embeddings and neural nets fix exactly this by sharing statistical strength across similar contexts.
• Sparsity explodes with n. Higher n captures more context but sees each gram fewer times, so estimates get noisier — the classic bias-variance tradeoff. Beyond n=5 the returns vanish under any smoothing.

Pitfalls, Edge Cases, and Variants

Common implementation bugs:

• Forgetting sentence padding. Without n−1 <s> tokens the first words have no context; without </s> the model can't score sentence length and probabilities won't normalize.
• Multiplying probabilities instead of summing logs. A 30-word sentence with per-word P ≈ 10⁻³ underflows float64. Always accumulate Σ log P.
• Smoothing the numerator but not renormalizing. Add-k must also add k·V to the denominator, or your “probabilities” sum to more than 1.
• Backoff weight (α) omitted. Backoff without the normalizing constant double-counts probability mass; the distribution is no longer valid.

Variants worth knowing:

• Stupid Backoff (Brants et al., 2007): drop normalization entirely — on unseen grams just multiply the lower-order score by a fixed λ ≈ 0.4. It is not a probability distribution, but at web scale (that trillion-token model) it matches Kneser-Ney and is trivially parallelizable in MapReduce.
• Class-based n-grams: cluster words into classes and model class transitions to combat sparsity.
• Skip-grams allow gaps in the context window; not to be confused with the word2vec skip-gram objective.
• Character n-grams sidestep out-of-vocabulary entirely and are heavily used in language identification and spelling correction.

Smoothing and modeling strategies for n-gram language models

Method	Idea	Zero-count handling	Quality
MLE (raw counts)	count(w₁..wₙ) / count(w₁..wₙ₋₁)	Assigns P = 0 (fatal)	Baseline, unusable alone
Add-k / Laplace	Add k to every count	Uniform mass to unseen	Poor; over-smooths
Katz backoff	Fall back to (n-1)-gram if unseen	Discount + redistribute	Good
Interpolation	Weighted mix of all orders	Lower orders fill gaps	Good, simple to tune
Kneser-Ney	Discount + continuation counts	Novel-context probability	Best classical LM