Counting isn't enough

In chapter 1, you wrote a generate loop that bailed out at "dead ends" — tokens whose row in the counts table was all zeros. That's not just a UI issue. The model has been asked: "what comes after X?" and the table has a single, honest answer: I have no idea, the row is empty.

That answer is fine for one chapter. It's not fine for any kind of scale. A real bigram model in practice can't just give up the moment it sees a pair it doesn't recognize — it needs to assign some probability to every possible next word, even ones it has never seen in this context. The general name for that move is smoothing.

We're going to build it from scratch. Same kind of corpus as last chapter, but bigger so we can split it 80/20 into train and validation. In the browser, you will see exactly what smoothing does. In your local my-llm/ repo, you will turn the bigram baseline into something you can evaluate.

1. Look the problem in the face

Take one row of the counts table — the row for the most-bigram-rich token in the corpus. Most cells will be positive (lots of seen continuations); some will be exactly zero (continuations the model has never witnessed).

The cell turns counts into a conditional distribution: divide every cell by the row sum.

The bars in loss color are zeros. As far as the model can tell, those continuations have no probability at all. If any one of them shows up in the validation set, the validation perplexity is mathematically infinite — log(0) is undefined, and the geometric mean of an inverse probability with one zero in it blows up.

That's the whole problem. Smoothing is how we route around it.

2. Add a little to everything: Laplace

The simplest fix has been around since the 1700s. Take every cell of the counts table — yes, including the zeros — and add a small constant α. Then renormalize. Formally:

Where $V$ is the vocabulary size. With α = 1 this is the original "add-one" smoothing; smaller values are usually better in practice.

The cell writes the formula as a function. It receives (count, rowSum, alpha, V), returns a probability, and the chapter draws what that function says about the same row as before — with an α slider so you can watch the bars flatten as α grows.

Slide α from 0.001 to 2. Two things happen:

• All the zeros become positive. The model is no longer surprised by anything.
• The non-zero bars shrink. The model is also less confident about the things it had seen.

That second effect is the cost of smoothing. Add too much and you're effectively saying "every word is roughly as likely as any other".

3. Find the sweet spot: perplexity vs α

If α = 0 makes the model crash on unseen pairs and α huge makes the model say nothing useful, there's a sweet spot in between. The standard way to find it: compute validation perplexity (the geometric mean of inverse probability) at a range of α values and pick the lowest point.

The cell computes perplexity from validation transitions (each is a { count, rowSum } object — the model-side numbers needed to score it under our train counts), an alpha, and a vocabulary size V. The script includes the canonical laplaceProbability from the previous cell so the sweep can call the same formula repeatedly.

You should see a U-shape. Far left (tiny α): the model trusts its training data too much; one rare unseen pair is enough to send perplexity through the roof. Far right (large α): the model is too uniform; it's spending its probability mass equally on plausible and absurd continuations. The bottom of the U is the best Laplace can do for this corpus.

4. A smarter family: Kneser-Ney

Laplace's laziness is that it treats unseen pairs uniformly. Every unseen (w_{t-1}, w_t) gets the same tiny probability. But that's silly — words like Francisco should mostly only follow San, not "any context with equal weight".

Kneser-Ney smoothing is a smarter member of the same family:

• Subtract a small constant d from every seen count (call it the discount). The total mass you took away is d × (number of distinct continuations seen).
• Redistribute that mass through a fallback distribution. Real KN uses a clever continuation table; we use the uniform 1/V for simplicity.

Run the formula. Same shape as Laplace, but with the extra distinctContexts argument and the lambda-times-fallback construction.

We sweep d and overlay the result on top of the Laplace curve from the previous cell. The two curves usually have different shapes — KN often has a sharper minimum at a smaller smoothing strength. On a real corpus the gap is meaningful; on this toy text the differences are subtle, but the point is that "smoothing" is a family of choices, and Laplace is the simplest member of the family.

5. Upgrade your local baseline

Open llm/bigram.py and add a smoothed probability function:

def laplace_probability(
    model: dict[str, Counter[str]],
    previous: str,
    token: str,
    vocab: set[str],
    alpha: float = 0.1,
) -> float:
    # [1]
    row = model.get(previous, Counter())
    # [2]
    count = row[token]
    # [3]
    total = sum(row.values())
    # [4]
    return (count + alpha) / (total + alpha * len(vocab))

Read the formula directly from the code:

• [1] row is everything the model has ever seen after previous.
• [2] count is the specific pair you are scoring: previous -> token.
• [3] total is the row sum, the number of observed continuations after previous.
• [4] gives every possible token alpha extra mass, then normalizes the row so the probabilities still sum to 1.

Then create scripts/eval_bigram.py:

from __future__ import annotations
 
import math
 
from llm.bigram import laplace_probability, tokenize, train
 
TEXT = "the cat sat on the mat the dog sat on the rug the cat watched the dog the dog watched the cat"
 
tokens = tokenize(TEXT)
# [1]
split = int(len(tokens) * 0.8)
train_tokens = tokens[:split]
val_tokens = tokens[split:]
 
# [2]
model = train(train_tokens)
vocab = set(tokens)
 
loss = 0.0
n = 0
# [3]
for previous, token in zip(val_tokens, val_tokens[1:]):
    p = laplace_probability(model, previous, token, vocab, alpha=0.1)
    # [4]
    loss -= math.log(p)
    n += 1
 
# [5]
print(f"validation perplexity: {math.exp(loss / n):.2f}")

The evaluation script has one job: make the model answer on text it did not train on.

• [1] creates a tiny train/validation split.
• [2] trains only on train_tokens; val_tokens stays held back.
• [3] walks each validation pair and asks, “what probability did the model assign to the true next token?”
• [4] is next-token loss. High probability means small loss; low probability means large loss.
• [5] turns average loss into perplexity, a more readable “how many plausible choices did the model feel it had?” score.

Run it:

python -m scripts.eval_bigram

python -m scripts.eval_bigram

python -m scripts.eval_bigram

The number is not impressive. That is the point. You now have a baseline you can beat.

Why this whole chapter feels like a hack

Because it is.

Smoothing is what you do when you've decided to model language with a counts table. The problem isn't that a better smoother would save the bigram model — the problem is that no amount of patching helps with the fundamental limitation: the model has no memory beyond one word. It can't tell that the sentence is about cats. It can't notice that "the" is followed by a noun. It is reasoning from one token of context.

The next several chapters are about replacing the counts table with something that can actually generalize — words that mean similar things should behave similarly, even on contexts they've never seen. The trick is to stop storing facts about every pair and start storing facts about every word individually, then learning how the words combine.

That trick has a name: embeddings. We get there in chapter 4. First we have to teach the model to chop up the input properly.

Going further

• The classic Jurafsky & Martin chapter on smoothing (PDF). The reference for n-gram smoothing in detail.
• Kneser & Ney's original paper (1995) is short and surprisingly readable.
• The full reference implementation lives in lib/ml/bigram/smoothing.ts if you want to see what the project's "official" version looks like.

Next up: training your own tokens — what if "the cat" and "thecat" should be the same input? What if "running" and "run" should share something? Time to stop splitting on whitespace.