N-gram Language Models

Every time your phone suggests the next word, or a search engine completes your query, something is estimating the probability of a word given its context. Long before neural networks dominated language, one idea handled this task surprisingly well: just count.

An n-gram is a sequence of $n$ consecutive words. A bigram is two words in a row — "the cat", "cat sat", "sat on". A trigram is three. The core insight is brutally simple: the probability of the next word depends only on the last $n-1$ words, not the entire preceding history. This is the Markov assumption, and it turns an impossible problem (condition on arbitrarily long histories) into a tractable one (condition on a short, fixed-length window).

Collect a large text, count every bigram, divide by unigram counts, and you have a working bigram language model:

$$P(w_k \mid w_{k-1}) = \frac{\text{count}(w_{k-1},\, w_k)}{\text{count}(w_{k-1})}$$

The beauty and the curse are the same: the model knows exactly what it has seen, and absolutely nothing about what it has not. Every unseen bigram gets probability zero — even plausible ones. This is the zero-frequency problem, and solving it with smoothing is where the real engineering lives.

The demo below trains a bigram model on a small built-in corpus and lets you generate text one word at a time — or all at once. You can toggle Laplace (add-1) smoothing to see how it rescues zero-probability words.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label class="switch-label">
    <input type="checkbox" id="smoothing"> {{label_smoothing}}
  </label>
</div>
<div class="model-row">
  <span class="model-label">{{label_context}}</span>
  <span id="context-word" class="word-badge">—</span>
  <span class="arrow">→</span>
  <span class="model-label">{{label_next}}</span>
</div>
<div id="prob-bars" class="prob-bars" aria-label="{{label_probs}}"></div>
<div id="generated" class="generated-text" aria-live="polite"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-gen" type="button">{{btn_gen}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status"></div>

/* {{c_style}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { margin-bottom: .6rem; }
.switch-label { display: flex; align-items: center; gap: .4rem; cursor: pointer; font-size: .88rem; }
.switch-label input { width: 16px; height: 16px; cursor: pointer; }
.model-row { display: flex; align-items: center; gap: .5rem; margin-bottom: .5rem; flex-wrap: wrap; }
.model-label { font-size: .8rem; color: #666; }
.word-badge { background: #1d3557; color: #fff; border-radius: 6px; padding: .15rem .55rem; font-weight: 700; font-size: .9rem; }
.arrow { font-size: 1.2rem; color: #999; }
.prob-bars { display: flex; flex-direction: column; gap: 3px; margin-bottom: .7rem; min-height: 60px; }
.bar-row { display: flex; align-items: center; gap: 6px; }
.bar-word { width: 80px; font-size: .8rem; text-align: right; overflow: hidden; text-overflow: ellipsis; white-space: nowrap; }
.bar-track { flex: 1; background: #e8eef3; border-radius: 4px; height: 14px; overflow: hidden; }
.bar-fill { height: 100%; background: #1d3557; border-radius: 4px; transition: width .3s; }
.bar-fill.smoothed { background: #457b9d; }
.bar-pct { font-size: .75rem; color: #666; width: 38px; }
.generated-text { min-height: 2.4rem; background: #f0f4f8; border-radius: 8px; padding: .4rem .7rem; font-size: .9rem; line-height: 1.6; margin-bottom: .6rem; word-wrap: break-word; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .85rem; font-weight: 600; min-height: 1.2em; color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Watch what changes when you enable smoothing: words that never appeared after the current word go from impossible to merely unlikely. The generated sentences become more varied — and sometimes delightfully odd — because smoothing spreads probability mass to every vocabulary item.

N-gram models look simple — just a table of counts — but their limits are instructive.

The sparsity wall. For a vocabulary of size $V$, a bigram table has up to $V^2$ entries; a trigram table $V^3$. Even with billions of training tokens, most $n$-grams never appear. A model trained on the works of Shakespeare has no idea what follows "machine" because the word never appears. Every unseen sequence gets probability zero, which poisons any sentence probability (a product containing one zero is zero).

Smoothing strategies redistribute probability mass from seen to unseen events:

• Laplace (add-1): pretend every $n$-gram appeared one extra time. Simple but over-smooths heavily.
• Good-Turing: estimate the probability of unseen events from the count of things seen only once.
• Kneser-Ney: the gold standard. Instead of raw counts it uses continuation counts — how many distinct contexts a word appears in. "Francisco" is common, but almost always after "San", so it deserves low probability in new contexts. Kneser-Ney captures this asymmetry elegantly.

Back-off and interpolation handle the case where a high-order $n$-gram has zero count: either fall back to a shorter $n$-gram (back-off) or mix probabilities across orders (interpolation).

Perplexity is the standard measure of how well a language model fits held-out text:

$$\text{PP}(W) = P(w_1, w_2, \dots, w_N)^{-1/N}$$

Lower perplexity means the model is less "surprised" by the test data — it assigned higher probability to what actually appeared. Comparing models by perplexity is meaningful only on the same vocabulary and test set.

The $n$ trade-off. Larger $n$ captures longer dependencies but exponentially worsens sparsity. Trigrams are about as far as raw counts can go without exotic smoothing; modern neural language models bypass the sparsity wall entirely by representing words as dense vectors.

N-gram models shaped the first generation of practical NLP and remain useful today:

• Spell and grammar correction: a spell checker can score candidate corrections by how likely they are in context. "I went to the stoor" — "store" beats "stoop" because the bigram "the store" is far more frequent.
• Speech recognition: acoustic models output many candidate transcriptions; a language model re-ranks them by fluency, turning phoneme confusions into real words.
• Machine translation: early statistical MT systems (IBM models, phrase-based SMT) used $n$-gram language models to prefer fluent target-language output over grammatically garbled alternatives.
• Keyboard prediction: the word-suggestion strip on mobile keyboards has run on bigram or trigram models for decades — fast, private, and surprisingly accurate for common phrases.
• Genomics: DNA and protein sequences are treated as "text" over a four- or twenty-letter alphabet. $k$-mer counting (the bioinformatics name for $n$-grams) powers assembly, alignment, and variant calling pipelines.
• NLP baselines: even today, a simple $n$-gram model is the standard baseline before reaching for transformers. If a neural model can't beat an $n$-gram baseline, something is wrong.

The ideas behind n-grams — the Markov assumption, smoothing, perplexity — echo through every modern language model, including the neural ones that replaced them. Understanding n-grams is understanding the vocabulary of probabilistic NLP.

N-gram language models distill language into arithmetic: count, divide, smooth. The Markov assumption trades perfect memory for computational tractability, and smoothing trades observed accuracy for robustness on unseen text.

Those trade-offs never go away — they just move. Modern transformers escaped the sparsity wall by replacing lookup tables with learned embeddings, but they still face the same fundamental tension: fitting the training distribution versus generalizing to new text. Perplexity is still the measuring stick.

The next time you tap a word suggestion on your phone, remember: beneath the neural layers there is still a ghost of the bigram table, counting what follows what, doing more with less than you might expect.