N-grams: Language by Counting
Lesson 1 of 4 in From N-grams to Transformers.
A Language model does one job: given some text, assign a probability to what comes next. Every chatbot you have used is a descendant of that job description, and this module is the story of four generations of answers to it. The oldest answer is almost embarrassingly simple: count.
An N-gram model model predicts the next word from the previous n − 1 words alone. A bigram model (n = 2) looks at one word of context, a trigram at two. Training is literally counting: run through a pile of text, tally how often each word follows each context, divide to get probabilities. There is no learning in the modern sense — the “model” is a lookup table.
The idea has serious roots. Claude Shannon’s 1948 paper A Mathematical Theory of Communication — the founding document of information theory — built n-gram approximations of English from letter and word statistics, and showed generated text drifting from gibberish toward almost-English as the window grew. In his 1951 follow-up, Prediction and Entropy of Printed English, he had people guess the next letter of hidden text and used their success rate to estimate how predictable English is. Language as a guessing game, with probabilities attached: Next-token prediction was born here, seventy years before the models you use today.
| Bigram (context → next) | Count in corpus | P(next | context) |
|---|---|---|
“the” → “cat” | 2 | 2 / 4 = 0.50 |
“the” → “mat” | 1 | 1 / 4 = 0.25 |
“the” → “rat” | 1 | 1 / 4 = 0.25 |
“cat” → “sat” | 1 | 1 / 2 = 0.50 |
“cat” → “saw” | 1 | 1 / 2 = 0.50 |
“sat” → “on” | 1 | 1 / 1 = 1.00 |
Read the table the way the model does. The corpus contains “the” four times; half of those are followed by “cat”, so after “the” the model predicts “cat” with probability 0.50. To generate text, sample a next word from the current row, append it, look up the new row, repeat. That loop — predict, sample, append — is the same loop a modern Large language model (LLM) runs. Only the machinery inside changed.
For decades this worked well enough to matter: n-gram models powered speech recognition, spelling correction, and early machine translation. Then came the walls.
Counting cannot generalize. To an n-gram model, “cat” and “dog” are unrelated symbols. A million sightings of “the cat sat” teach it nothing about “the dog sat” — if that exact sequence never occurred, its count is zero, and zero count means zero probability. The model declares perfectly ordinary sentences impossible.
The window cannot grow. The obvious fix — raise n for more context — makes the zero problem exponentially worse. The number of possible 5-grams is so much larger than any corpus that most grammatical five-word sequences have never been written down even once in history. Statisticians patched the zeros with smoothing — backing off to shorter contexts, discounting schemes with names like Kneser–Ney — but smoothing redistributes probability; it cannot create the missing knowledge. In practice n-gram models stalled around n of 4 or 5, blind to everything earlier in the sentence.
The sparsity wall, in numbers
Take a modest Vocabulary of 50,000 words. Possible bigrams: 50,000² = 2.5 billion — already more than most historical corpora could fill. Possible 5-grams: 50,000⁵ ≈ 3 × 10²³. A corpus of a trillion words contains at most a trillion 5-grams, so even if every one were unique you would have observed roughly one in every 300 billion possibilities. The table is empty and will always be empty. That is not a data-collection problem; it is combinatorics, and no amount of scraping fixes it.
Shannon’s 1951 experiment supplies the other half of the diagnosis. Humans guessing the next letter of English do far better than chance — his estimates put English at roughly one bit of new information per letter, a fraction of the raw alphabet’s capacity. Text is highly predictable. But much of that predictability lives in long-range structure — topic, syntax, who did what to whom — exactly where a 4-word window cannot see. The gap between what humans exploit and what counting reaches was the standing challenge.
The scoreboard for that challenge also comes from Shannon’s framework: Cross-entropy — how surprised the model is by real text — and its exponentiated cousin Perplexity. Every architecture in the rest of this module earned its place the same way: by driving perplexity lower than the era before it.
The counting era
- 1948-07-01 — A Mathematical Theory of Communication:
Shannon modeled English as a chain of ever-better n-gram approximations and defined entropy as the limit they approach. The core framing — language as a probability distribution over symbol sequences — is the root idea every language model since has refined.
- 1951-01-01 — Prediction and Entropy of Printed English:
Shannon used human next-letter guessing to estimate the entropy of English at roughly one bit per character. It established prediction quality as the yardstick for a language model — the ancestor of today’s perplexity evaluations.
- 1997-11-01 — LSTM: gated recurrence:
Hochreiter and Schmidhuber added gates and a constant-error carousel so recurrent networks could learn long-range dependencies without vanishing gradients. The LSTM became the workhorse of neural sequence modeling for the next two decades.
- 2003-02-01 — A Neural Probabilistic Language Model:
Bengio et al. mapped words to learned embedding vectors and trained a neural network to predict the next word, sharing statistical strength across similar words. It broke the n-gram sparsity ceiling and set the embeddings-plus-neural-predictor template still in use.
- 2013-01-01 — word2vec: efficient word embeddings:
Mikolov et al. showed that stripped-down training objectives (CBOW and skip-gram) produce word vectors with rich semantic structure — famously king − man + woman ≈ queen. Cheap, high-quality embeddings made neural NLP practical on ordinary hardware.
- 2014-09-01 — seq2seq: encoder–decoder learning:
Sutskever et al. mapped an input sequence to an output sequence with a pair of LSTMs, reaching near state-of-the-art machine translation with a single end-to-end network. It established the general encode-then-generate recipe behind modern text generation.
- 2014-09-01 — Attention for neural translation:
Bahdanau et al. let the decoder learn to look back at every encoder state instead of squeezing the whole source through one fixed vector. Attention removed the seq2seq bottleneck and became the mechanism the transformer would later build everything on.
- 2018-02-01 — ELMo: contextual representations:
Peters et al. derived word representations from a pretrained bidirectional LSTM language model, so a word’s vector depends on its sentence. It showed that pretraining on raw text transfers broadly across tasks — the step just before whole-model fine-tuning.
Key terms: Language model, N-gram model, RNN, Seq2seq, Attention, Transformer
Interactive checkpoint quiz (2 questions) — open this page in a browser to take it.