N-gram Language Models

An N-gram language model predicts the next token by counting what followed the same recent history in a training corpus. The order n decides how many tokens the model remembers. Smoothing can produce a valid distribution when counts vanish; it cannot create contextual evidence.

The method is small enough to audit by hand. There is no hidden vector and no learned neural network: you can trace a prediction from one query, through exact corpus matches, into integer counts, and finally into probabilities. That makes an N-gram useful as an auditable baseline and in tightly scoped domains. Longer histories describe context more precisely, but exact long histories disappear from finite data.

How N-gram Language Models Work

An N-gram is a sequence of n tokens. For next-token prediction, an order-n model uses the last n - 1 tokens as its history h, then counts the token w that followed each exact occurrence of that history.

For a 4-gram, the prefix at dusk the cat produces the history:

h = dusk the cat

The words before dusk are outside the model's memory. The model scans its corpus for that exact three-token sequence and records the token immediately after every match. If the history appears three times, followed by sat twice and ate once, the maximum-likelihood estimate is:

P(sat | dusk the cat) = 2 / 3

P(ate | dusk the cat) = 1 / 3

Every other vocabulary token gets probability zero. More generally:

P(w | h) = C(h, w) / C(h)

C(h, w) is the number of times token w follows history h. C(h) is the number of observed continuations after h, which is also the sum of all C(h, w) values.

The vocabulary includes an explicit <eos> token at the end of every sentence. That token lets the model predict that a sequence should stop. Without it, sentence endings would vanish from the training signal.

Smoothing Fixes Zeros, Not Missing Evidence

Maximum likelihood assigns zero probability to every continuation that was not observed after a particular history. That is brittle: one unobserved target continuation makes the probability assigned to a whole evaluated sentence zero. Add-alpha smoothing gives every vocabulary token the same pseudo-count alpha before normalizing:

P_alpha(w | h) = (C(h, w) + alpha) / (C(h) + alpha |V|)

The denominator must add alpha once for each of the |V| vocabulary tokens. If you add pseudo-counts only to the numerator, the probabilities no longer sum to one.

Smoothing changes probabilities, not evidence. A token with adjusted count 0.1 still has zero corpus observations. Likewise, an unseen history remains unseen even if smoothing produces a valid distribution for it.

N-gram Language Models Step by Step

The default animation uses n = 4, alpha = 0.1, and five training sentences:

The vocabulary has 12 tokens in first-appearance order: at, dusk, the, cat, sat, <eos>, ate, dawn, dog, slept, by, and noon.

1. Frame the seen query. The prefix is at dusk the cat. A 4-gram remembers three tokens, so the active history is dusk the cat.

2. Scan for exact histories. The history appears in sentences 1, 2, and 3. The first two matches are followed by sat; the third is followed by ate. Sentences 4 and 5 contain familiar words, but neither contains the exact sequence dusk the cat.

3. Tally and normalize. The continuation counts are sat: 2, ate: 1, and zero for the other ten vocabulary tokens. C(h) = 3, so maximum likelihood gives sat: 0.6667 and ate: 0.3333.

4. Add the pseudo-counts. With alpha = 0.1, the two observed numerators become 2.1 and 1.1. Each unobserved continuation gets 0.1. The denominator is:

3 + 0.1 × 12 = 4.2

The smoothed distribution is:

The probabilities still sum to one. The observed leaders lose some mass because smoothing reserves mass for outcomes the corpus did not show.

5. Change one word. Replace dusk with dawn: the prefix becomes at dawn the cat, and the 4-gram history becomes dawn the cat. Every word belongs to the vocabulary, but the three-token history never appears in the corpus. Vocabulary coverage is not context coverage.

6. Face the zero-count history. Here C(dawn the cat) = 0. Maximum likelihood would divide by zero, so it is undefined; a list of zeros is not a probability distribution. Add-alpha smoothing gives every token numerator 0.1 and denominator 1.2, producing the uniform probability 1 / 12 = 0.0833. The result is valid, but it contains no contextual evidence.

7. Shorten the memory. Move from a 4-gram to a 3-gram. The history shrinks from dawn the cat to the cat, which appears four times: twice before sat, once before ate, and once before slept.

With the same alpha = 0.1, the denominator is 4 + 0.1 × 12 = 5.2. The recovered probabilities are sat: 0.4038, ate: 0.2115, slept: 0.2115, and 0.0192 for each remaining token. The model has evidence again, but it no longer distinguishes at dawn the cat from at dusk the cat or by noon the cat.

Why Longer Memory Creates Sparse Evidence

Increasing n narrows the set of corpus positions that qualify as evidence. A unigram uses an empty history, so every token position is a continuation; this corpus contributes 30 positions including <eos>. A bigram asks what followed one token. A trigram asks what followed two. A 4-gram asks for three consecutive tokens in the right order.

That shrinking match set creates two opposing effects:

• A longer history can separate contexts that a shorter model merges. In this corpus, dusk the cat excludes the by noon the cat slept example, making sat more dominant.
• A longer history is easier to miss completely. dawn the cat contains only known words, yet it has no exact match. The shorter the cat history immediately recovers four examples.

This is the sparsity problem. The number of possible histories grows roughly like |V|^(n - 1), while the training corpus supplies only a finite number of observed positions. Most possible long histories never occur, even in a large corpus.

Smoothing and shorter memory solve different problems. Smoothing prevents zero probabilities inside a fixed history length. Shortening the history changes which corpus positions count as evidence. Add-alpha can turn an undefined distribution into a uniform one, but it cannot discover that the cat has four useful continuations until the model changes its conditioning history.

Modern neural language models address sparsity by representing tokens and contexts as vectors, so similar histories can share statistical strength without being exact string matches. The N-gram model remains a useful baseline because its evidence is explicit: you can point to every count and explain every probability.

Choosing n and alpha

Use n to decide how much exact context the model keeps. Use alpha to decide how much probability mass to reserve for unseen continuations within that context.

• n = 1 ignores the prefix and predicts from global token frequency.
• n = 2 conditions on the last token.
• n = 3 conditions on the last two tokens.
• n = 4 conditions on the last three tokens.

Small positive alpha values soften hard zeros while leaving strong counts visible. Large alpha values push every distribution toward uniform. In the default seen history, increasing alpha from 0.1 to 1.0 changes P(sat | h) from 0.5000 to 3 / 15 = 0.2000; the model still ranks sat first, but the two real observations exert much less influence.

There is no universally correct pair. A larger corpus can support longer histories. A tiny corpus needs shorter histories or a stronger backoff strategy. Add-alpha is mainly a teaching tool and a simple baseline; production count-based models use methods such as interpolation, backoff, discounting, and Kneser-Ney smoothing because they preserve frequency structure more carefully.

Choose n and alpha on held-out data, not by maximizing fit to the training corpus. Compare mean negative log-likelihood (cross-entropy), or its exponentiated form, perplexity, under the same tokenization, vocabulary, and evaluation set; lower is better. A setting that improves training fit but worsens held-out perplexity has memorized the supplied counts more than it generalizes beyond them.

Edge Cases

• Unseen history with alpha = 0. C(h) = 0, so maximum likelihood is undefined. Do not report twelve zeros as a distribution; they sum to zero, not one.
• Unseen history with alpha > 0. Every token receives 1 / |V|, regardless of alpha. Both numerator and denominator contain the same alpha factor, so it cancels.
• Unseen continuation after a seen history. Maximum likelihood gives that token zero. Add-alpha gives it positive probability while reducing the observed tokens' probabilities so the total remains one.
• Unigram order. The history is empty. Every token position in the corpus is a continuation, including each <eos>, so the model predicts global token frequency and ignores the query.
• A history at the end of a sentence. The appended <eos> supplies a continuation. Without an end token, that occurrence could not contribute to next-token prediction.
• Tokens outside the vocabulary. This lesson keeps both queries inside a fixed vocabulary. A real count model needs an <unk> policy or a tokenizer that maps arbitrary input into known units.
• Case and punctuation. Exact string counts treat Cat, cat, cat,, and cat followed by punctuation as different tokens unless preprocessing says otherwise.

Common Mistakes

• Counting words anywhere in the sentence. A continuation counts only when it immediately follows the complete active history. Shared words and partial matches do not contribute.
• Using all prefix tokens regardless of n. An order-n model keeps exactly n - 1 history tokens. For n = 3, changing dusk to dawn has no effect because both words sit outside the cat.
• Dividing by corpus size. The denominator is C(h), not the number of sentences or total tokens. Each history has its own local distribution.
• Adding alpha only to observed tokens. Add-alpha applies to every vocabulary outcome. Otherwise the method leaves zeros in place and the stated denominator is wrong.
• Calling pseudo-counts observations. Smoothing changes the estimator. It does not alter the corpus, create new history matches, or prove that an unseen continuation is plausible.
• Assuming larger n is always better. More context helps only when the corpus supports that exact context. Otherwise the model becomes more fragile.
• Treating a uniform fallback as informed prediction. The distribution is mathematically valid, but every token is tied because the selected history supplied no evidence.

A Note on Simplification

The corpus is deliberately five sentences, the vocabulary is fixed by first appearance, tokenization is whitespace-based, and every sentence receives one <eos> marker. The lesson stops at order 4 and uses add-alpha smoothing from 0 to 1 so each probability can be checked by hand. It does not model unknown tokens, capitalization choices, punctuation splitting, sentence-start markers, pruning, interpolation across several orders, or held-out parameter selection.

Real count-based language models usually combine several history lengths rather than switching from one to another only after failure. They also prefer discounting and backoff methods that use evidence about how widely a word appears across contexts. Neural language models replace exact history tables with learned representations, though they still end each forward pass with a probability distribution over the next token. This lesson isolates the count-based mechanism that makes the memory-versus-coverage problem visible.