Language Models and Decoding

Predict the next word: n-gram counts, smoothing and perplexity on real text, then greedy, beam search and sampling, and the bridge to neural models.

Intermediate lesson, about 40 minutes, with interactive demos and a quiz.

What you will learn

What is a language model?

Your phone suggests the next word as you type. A speech recogniser decides you said “recognise speech”, not “wreck a nice beach”. A chatbot writes an answer one token at a time. Behind all three is the same object: a model that says how likely each possible next word is.

What is it?

A language model assigns a probability to a sequence of words (or, in modern systems, tokens). In practice it does this one step at a time: given the words so far, it gives a probability for every word in its vocabulary to come next. “The cat sat on the” should give “mat” a decent probability and “photosynthesis” a tiny one.

How does it work?

The chain rule of probability turns next-word predictions into the probability of a whole sentence. No assumptions, just multiplication: the probability of the sentence is the probability of the first word, times the probability of the second given the first, and so on.

P(w₁, w₂, …, wₙ) = P(w₁) · P(w₂ | w₁) · P(w₃ | w₁ w₂) · … · P(wₙ | w₁ … wₙ₋₁)

The chain rule. w₁ … wₙ are the words of the sentence; each factor is one next-word prediction. Real models also predict an end-of-sentence token, so they know when to stop.

Every language model, from a table of counts to the largest chatbot, is a way of estimating those factors. The rest of this lesson builds the simplest one that works, measures it, and then uses it to write.

Why does it matter?

Ranking sequences is useful whenever a system must choose between candidates: spelling correction, speech recognition, translation, handwriting recognition. Generating from the model gives autocomplete and, scaled up enormously, the large language models behind modern assistants. The ideas in this lesson, predicting the next token, measuring surprise and choosing a decoding strategy, carry over to them unchanged.

New to language processing? Natural Language Processing covers tokens, embeddings and the road from counting words to transformers.

Key takeaways

  • A language model gives a probability for every possible next token, given the tokens so far.
  • The chain rule multiplies those next-token probabilities into the probability of a whole sentence.
  • Every language model, from count tables to chatbots, is a way of estimating those factors.

N-gram models: counting what comes next

The exact chain rule needs the probability of each word given everything before it. Almost no long history ever repeats, so the oldest trick in language modelling is to forget most of it.

What is it?

An n-gram model assumes the next word depends only on the previous n − 1 words. A unigram model (n = 1) ignores context entirely; a bigram model looks at one previous word; a trigram model at two. This is the Markov assumption, and it turns an impossible estimation problem into counting.

How does it work?

P(w | v) = c(v w) / c(v) (bigram)
P(w | u v) = c(u v w) / c(u v) (trigram)

Maximum-likelihood estimates. c(·) is how often a word sequence occurs in the training text.

Count how often each context occurs, and how often each word follows it; divide. These relative frequencies are the probabilities that make the training text as likely as possible, which is why they are called maximum-likelihood estimates (Jurafsky and Martin, ch. 3). Sentences are padded with a start marker, so the first word is predicted from “start”, and closed with an end token the model also predicts.

The demos in this lesson train on the full text of Alice’s Adventures in Wonderland (Lewis Carroll, 1865, public domain), split into 1,503 sentences. Every tenth sentence is held out for testing and another tenth for tuning, so the model counts 21,931 words from the rest. It does this in your browser in a few milliseconds.

Generating text

Generate the rest is the simplest way to write with a language model: draw the next word from its distribution, append it, and repeat until the end token appears. Claude Shannon did exactly this by hand in 1948, building word and letter “approximations to English” from frequency tables. His word-bigram sample begins “THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS…” (Shannon, 1948): locally plausible, globally meaningless.

You will see the same pattern. Unigram output is word salad with the right word frequencies. Bigram output has grammatical pairs but drifts. Trigram output reads much better, but look at the readout: after two words, many contexts have been seen only once or twice, so the model can only copy the book. On this little corpus, 8,715 of the 11,391 two-word contexts occur exactly once.

Why does it matter?

N-gram models powered speech recognition, machine translation and predictive text for decades, and they remain a fast, transparent baseline. They also make the central trade-off of language modelling visible: more context gives better predictions, but every extra word of context splits the data into many more, emptier cells.

The Next-Token Sampling Lab trains a smoothed n-gram model on Alice, Shakespeare or Python and lets you steer its output with temperature, top-k and top-p.

Key takeaways

  • An n-gram model predicts the next word from only the previous n − 1 words (the Markov assumption).
  • Its probabilities are counts divided by counts: c(context, word) / c(context).
  • Longer contexts read better but are seen far less often, so a trigram model on a small corpus mostly copies its training text.

Perplexity: how surprised is the model?

To compare language models you need one number that says how well each predicts text it has never seen. The standard one measures, in effect, how surprised the model is.

What is it?

The surprisal of a word is −log₂ P(word | context), measured in bits. A word the model gave probability ½ costs 1 bit; ¼ costs 2 bits; 1/1,024 costs 10. Perplexity is 2 raised to the average surprisal per token over a test text. It reads as an effective number of choices: a perplexity of 50 means the model was, on average, as unsure as if it were picking uniformly among 50 words.

PP = P(w₁ … w_N)^(−1/N) = 2^( −(1/N) Σ log₂ P(wᵢ | context) )

Perplexity of a test text of N tokens. The two forms are equal; the second is the one computed in practice. Lower is better.

How does it work?

Take four tokens the model predicted with probabilities ½, ¼, ⅛ and 1/16. Their surprisals are 1, 2, 3 and 4 bits, averaging 2.5 bits, so the perplexity is 2^2.5 ≈ 5.7. One confident miss matters a lot: if one of those probabilities were 0, its surprisal would be infinite, and so would the perplexity. That is exactly what happens to a raw count model on new text.

With no smoothing, the bigram model is fine until “queer thing”, a pair that never occurs in the training sentences. Probability zero, infinite surprise, infinite perplexity, however good the rest of the predictions were. The trigram model fails on seven of the ten tokens. The interpolated models (next section) never give zero, and the bigram one scores this sentence at a perplexity of about 94.

Why does it matter?

Perplexity is cheap to compute and needs no human judges, so it is the everyday measure for language models of every size. Its exponent, the average negative log-probability, is the cross-entropy loss that neural language models are trained to minimise (usually in nats, with e instead of 2). Two cautions: perplexities are only comparable on the same test text with the same vocabulary or tokeniser, and low perplexity does not guarantee useful or truthful output.

Key takeaways

  • Surprisal is −log₂ of the probability the model gave the word that actually came next.
  • Perplexity is 2 to the average surprisal per token: an effective number of equally likely choices. Lower is better.
  • A single zero-probability word makes perplexity infinite, so raw counts cannot be evaluated on new text.

Sparsity and smoothing

Most perfectly ordinary word sequences never appear in any given training text. Of the 3,329 trigrams in the Alice test sentences, only 815 occur in the training part of the book. A usable model has to give the rest some probability.

What is it?

Smoothing moves a little probability from the events the model has seen to the ones it has not, so nothing is impossible. It is the n-gram model’s answer to sparsity: the number of possible n-grams grows as the vocabulary size to the power n, while any corpus is finite.

How does it work?

Add-one (Laplace) and add-k

P(w | v) = ( c(v w) + k ) / ( c(v) + k·V )

V is the vocabulary size (2,345 here, including the end token and a slot for unknown words). k = 1 is add-one, or Laplace, smoothing.

Pretend you saw every possible pair k more times than you did. Simple, but with a large vocabulary it is a blunt tool. After “the”, the training text shows 381 different next words; add-one invents a count for the other 1,964 and hands them 54% of the probability. P(queen | the) falls from 0.038 to 0.014. Smaller values of k help, but not enough.

Backoff and interpolation

A better idea: when the long context has little evidence, trust a shorter one. Backoff uses the trigram estimate if the trigram was seen, and otherwise falls back to the bigram, then the unigram (Katz backoff does this while keeping the probabilities summing to one). Interpolation always mixes all of them:

P(w | u v) = λ₀ · 1/V + λ₁ · P(w) + λ₂ · P(w | v) + λ₃ · P(w | u v)

Linear interpolation. The weights λ sum to 1 and are tuned on held-out data, not the training text. The demos use λ = 0.08, 0.40, 0.40 and 0.12, chosen on the development sentences; the uniform term covers words never seen at all.

Chen and Goodman (1999) compared the main smoothing methods on large corpora and found that a modified form of Kneser-Ney smoothing, which interpolates using how many different contexts a word appears in rather than its raw frequency, consistently did best. It remained the standard for n-gram models until neural models replaced them.

Without smoothing every model is infinitely perplexed. Add-one makes longer contexts worse. Add-k with k around 0.01 brings the bigram down to about 324, but the trigram stays above 800. Only interpolation lets the extra context pay off: unigram 407, bigram 195, trigram 185. Even then the gain from bigram to trigram is small, because 22,000 words is a tiny corpus; with millions of words the gap widens.

Why does it matter?

Smoothing decides how a model behaves on anything new, which is most real input. Getting it right was the main engineering problem of statistical language modelling for two decades. Neural language models handle the same problem differently: instead of reserving probability for unseen events, they generalise from similar ones.

Key takeaways

  • Most n-grams in new text never appeared in training, and an unsmoothed model gives them probability zero.
  • Add-one smoothing removes the zeros but gives far too much probability to unseen events when the vocabulary is large.
  • Backoff and interpolation lean on shorter contexts when longer ones lack evidence; Kneser-Ney was the best-performing variant.

Decoding: greedy and beam search

A language model gives a distribution over the next token. Turning that into text means choosing, again and again. How you choose, the decoding strategy, changes the output as much as the model does.

What is it?

Decoding strategies fall into two families. Sampling draws each token at random from the distribution, as the explorer above does; the Next-Token Sampling Lab covers temperature, top-k and top-p, which reshape that distribution. Search tries to find the single most probable output. The simplest search is greedy decoding: always take the most likely next token. Beam search keeps several candidates alive.

How does it work?

Greedy decoding is short-sighted. A word that looks best now can lead to poor continuations, and greedy never reconsiders. Beam search with width B keeps the B best partial sequences (the beam). At each step it extends every one of them by every possible next token, scores each extension by its total log-probability, and keeps the best B. Width 1 is greedy; an infinite width would be an exhaustive search.

A worked beam of width 2

  1. Step 1. The first word: “the” 0.5, “a” 0.4, “one” 0.1. Keep “the” and “a”. Greedy keeps only “the”.
  2. Step 2. Extend both. “the dog” 0.5 × 0.4 = 0.20, “the cat” 0.175, “the house” 0.125, “a small” 0.4 × 0.9 = 0.36, “a big” 0.04. Keep “a small” and “the dog”. The beam has overtaken greedy: “a small” started from the second-best word.
  3. Step 3. “a small dog” 0.36 × 0.6 = 0.216, “a small cat” 0.144, “the dog barked” 0.10. The best is “a small dog”, more than twice as probable as greedy’s “the dog barked”.

Width 3 keeps “the cat” too, which adds “the cat slept” (0.105) to the finalists but does not change the winner. In real systems the vocabulary has tens of thousands of tokens, so the search never looks at a whole tree: it scores B × V extensions per step and throws almost all of them away. Beam widths of 4 to 10 are typical.

Why does it matter?

Beam search is the standard decoder wherever the input pins down the right output: machine translation, speech recognition, summarisation with a fixed source, image captioning. There, more probable usually means more correct, and a small beam finds outputs that greedy misses at a modest cost.

Machine Translation shows beam search inside real translation systems, and how their output is scored with BLEU.

Key takeaways

  • Greedy decoding takes the most probable token each step and can miss a much more probable sequence.
  • Beam search keeps the B best partial sequences by total log-probability; width 1 is greedy.
  • It is the standard decoder for tasks with one right answer, such as translation and speech recognition.

Why beam search writes badly

If beam search finds more probable text, why do chatbots sample instead? Because for open-ended writing, the most probable text is not the best text.

What is it?

Text degeneration is the tendency of probability-maximising decoders to produce bland, generic and repetitive text when there is no single right answer. Holtzman and colleagues (2020) showed it with large neural models: beam search output fell into loops, and real human text turned out to be much less probable, token by token, than the text beam search chose.

How does it work?

Three forces combine. Common, safe words have the highest probabilities, so maximising favours them. Once a phrase has appeared, repeating it is often the most probable continuation, and each repetition makes the next more likely, so the loop feeds itself. And every extra token multiplies in a probability below 1, so when the search may end the text it prefers to stop early.

After “said the”, greedy decoding writes “king said the king said the king…”: 80% of its word pairs are repeats. Widths 2 and 3 do the same. At width 10 the search finds a log-probability of −28.0, much higher than greedy’s −35.3, by reproducing a sentence of the book almost word for word: “mock turtle sighed deeply and drew herself up closer to alice’s shoulder”. A sample has a lower probability and no repeats. (The odd “the the lobsters” that some outputs fall into is a real line, where the Gryphon interrupts the Mock Turtle; a count model will happily loop through a quirk it saw once.) Allow the sentence to end, and the search stops almost at once: greedy writes “said the king” and ends, and from width 7 the best hypothesis ends straight after “said the”, at −3.8. Short outputs win simply because they multiply in fewer probabilities.

Why does it matter?

The choice of decoder is a product decision, not just a technical one. The same model can sound repetitive or creative, safe or wild, depending on how its probabilities are turned into words. Modern assistants mostly sample, with settings tuned per task, and some systems generate several samples and then rank them, combining the two families.

Try temperature, top-k and nucleus sampling on the same kind of model, and compare greedy and sampled output side by side.

Key takeaways

  • For open-ended text, maximising probability gives bland, repetitive or copied output: text degeneration.
  • Human text is not the most probable text, so chatbots sample, usually from a trimmed distribution.
  • Beam search is still right for translation and speech recognition, with a length correction.

From counts to neural language models

Modern language models keep the whole frame of this lesson: next-token probabilities, the chain rule, perplexity and decoding. They replace one piece, the table of counts.

What is it?

A neural language model computes P(next token | context) with a learned function instead of looking it up. Bengio and colleagues (2003) fed the vectors of the previous few words into a small neural network with a softmax output over the vocabulary, and reported lower perplexity than the best smoothed n-gram models on the corpora they tested.

How does it work?

The objective is the same: make the training text as probable as possible, which means minimising the average −log P(actual next token), the cross-entropy. For a count table, the answer has a closed form, and it is exactly the relative frequencies used above. A neural network has no formula, so it reaches its answer by gradient descent, just as linear regression can be solved by formula or by descent.

N-gram modelOne cell per context and word, filled by counting. Fixed window of n − 1 words. Unseen contexts get nothing unless smoothed. Every word is unrelated to every other.Neural language modelA network maps the context to a distribution. Words become vectors, so evidence about “the cat sat” helps with “the dog sat”. Recurrent networks and then transformers removed the fixed window.

Similar words end up with similar vectors, so a neural model can give a sensible probability to a sequence it has never seen, without any smoothing rule. Recurrent networks then carried a running memory through the whole text, and transformers let every position attend directly to every earlier one, letting context windows grow from a couple of words to hundreds of thousands of tokens.

Why does it matter?

Train that function with enough parameters on enough text and you get a large language model. Its perplexity on held-out text is measured exactly as above, it writes by greedy decoding, beam search or sampling exactly as above, and the decoding trade-offs are the same. The count model is a version of a chatbot you can read in full.

Step a recurrent network through a sequence in the Recurrent Networks Lab, the first neural answer to the fixed window.Transformers: how attention lets a language model use its whole context.

Key takeaways

  • Neural language models keep the objective (minimise cross-entropy) and replace the count table with a learned function.
  • Word vectors let them share evidence across similar contexts, which handles sparsity without smoothing rules.
  • Perplexity, the chain rule and decoding strategies apply to them unchanged.

Check your understanding

Six situations from real systems. Each one asks you to apply an idea from the lesson.

Question 1 of 6

A phone keyboard uses a trigram model trained on a user’s past messages. It gives the phrase “see you at the cinema” a probability of exactly zero, because “at the cinema” never appeared in training. What is the most sensible fix?

Next, see how a learned memory replaces the fixed window in the Recurrent Networks Lab, or steer a language model’s output yourself in the Next-Token Sampling Lab.

References

Papers and textbooks behind the methods and claims in this lesson.

References

  1. [1]

    Speech and Language Processing (3rd edition draft), chapter 3: N-gram Language Models(opens in a new tab)

    Daniel Jurafsky & James H. Martin, 2026

    The standard textbook treatment of the chain rule, n-gram estimation, perplexity, sampling, smoothing, interpolation and backoff. Free online draft.

  2. [2]

    A Mathematical Theory of Communication(opens in a new tab)

    Claude E. Shannon, 1948

    Bell System Technical Journal 27, 379–423 and 623–656. Founds information theory and, along the way, builds a series of letter and word n-gram "approximations to English" by hand.

  3. [3]

    An Empirical Study of Smoothing Techniques for Language Modeling(opens in a new tab)

    Stanley F. Chen & Joshua Goodman, 1999

    Computer Speech and Language 13(4), 359–394. A careful comparison of add-one, Good-Turing, Katz backoff, Jelinek-Mercer interpolation, Witten-Bell and Kneser-Ney; a modified Kneser-Ney performed best.

  4. [4]

    The Curious Case of Neural Text Degeneration(opens in a new tab)

    Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes & Yejin Choi, 2020

    ICLR 2020. Shows that maximising probability with greedy or beam search makes open-ended text bland and repetitive, that human text is not the most probable text, and introduces nucleus (top-p) sampling.

  5. [5]

    A Neural Probabilistic Language Model(opens in a new tab)

    Yoshua Bengio, Réjean Ducharme, Pascal Vincent & Christian Jauvin, 2003

    Journal of Machine Learning Research 3, 1137–1155. Replaces the count table with a neural network over learned word vectors, so similar contexts share statistical strength.

Related