Build autocomplete by counting
Suggest the next word of a message, like a phone keyboard. Count which words follow which in thousands of normal messages, turn the counts into probabilities, handle word pairs you have never seen, generate messages, and measure how surprised the model is by new text. Then train a tiny neural network that learns the same probabilities by gradient descent.
The problem: guess the next word
You type "Can we meet" on your phone, and the keyboard offers three words: you, up, him. How does it know? It has seen many messages. After "meet", some words come often and most words never do.
In this quest you build that keyboard for the normal messages of our dataset (the "ham" messages: about 3,400 for training). First by counting, then by training a tiny neural network that learns the same thing. The second model is the one the next quests will grow.
Here is what the training messages say about a few words (real counts):
| After... | seen | most common next tokens |
|---|---|---|
| "meet" | 55 times | you (12), them (4), up (4), him (4), in (3) |
| "call" | 171 times | me (42), later (32), you (18), "." (8) |
| "sorry" | 117 times | "," (43), "." (11), i (11), da (6) |
| the start of a message | 3,372 times | i (289), <unk> (127), ok (93), no (80), sorry (73) |
So after "call", the chance that the next token is "me" is about 42 / 171 = 0.25. That one division is the whole idea of a bigram model: the next token depends only on the one token before it. A unigram model is even simpler: it ignores the previous token and just uses how common each token is.
A model like this, which gives a probability to every possible next token, is a language model. The big chat assistants are language models too, just with much longer memory.
What you build
ngram.py: aUnigramModeland aBigramModelbuilt from counts (stored in a PyTorch tensor), with smoothing for word pairs they have never seen. They suggest the next word, generate messages, and measure their perplexity on messages they never saw.neural_bigram.py: the same bigram predictor as a one-layer neural network, trained with gradient descent in PyTorch. You check that its probabilities approach the counts.- A comparison of the three models on the same validation messages.
tokenizer.py is provided (it is the last quest's reference solution; you may swap in your
own). autocomplete.py is a small given demo: python autocomplete.py "Can we meet" prints
your model's three suggestions.
Fixed vocabulary. Everyone uses the same one, so that numbers can be compared:
Vocab.build(training ham messages, min_count=2): 2,710 tokens, and about 9% of validation
tokens become <unk>. The grader builds it the same way.
Set up PyTorch
Same as the last quest: pip install -r requirements.txt (torch 2.14.1, Python 3.10 or newer). On an Intel Mac,
pip install torch==2.2.2 instead (Python 3.12 or older; a NumPy warning on import is harmless).
On Linux without a graphics card,
pip install torch==2.14.1 --index-url https://download.pytorch.org/whl/cpu saves a large
download.
Part 1: count pairs, with boundaries
Boundary tokens. Put <s> before every message and </s> after it, then count each pair of
neighbours:
"ok see you" -> <s> ok see you </s> -> pairs (<s>, ok) (ok, see) (see, you) (you, </s>)
<s> lets the model learn how messages start, and </s> how they end (and when to stop
generating). They also keep messages apart: the last word of one message is never counted
before the first word of the next one, because the two messages have nothing to do with each
other. Unknown words are counted as <unk>.
Counts in a tensor. With V tokens in the vocabulary, the bigram counts fit in a tensor of
shape (V, V): row = previous token, column = next token, so counts[i, j] is how often token j
followed token i. Store it in model.counts (raw counts, before smoothing). Dividing each row by
its total turns counts into probabilities: every row sums to 1. (A unigram model needs only one
row: how often each token is predicted, </s> included.)
Ranked suggestions. next_token_probs(prev) returns a probability for every token that can
come next, and suggest(text, k=3) the k most likely words after the text's last token, most
likely first. Don't suggest <unk>, <s> or </s>: nobody wants to type those.
Generate by sampling. Start at <s>. Draw the next token at random with the model's
probabilities (after "call", "me" a quarter of the time), then draw the one after that, and so
on until </s>. Use a seeded random generator (torch.Generator().manual_seed(seed) and
torch.multinomial), so the same seed gives the same message. Read some samples: they look
like messages for two or three words, then wander off. Why?
Part 2: pairs you have never seen
"meet tonight" never appears in the training messages, so its count is 0, and with plain division its probability is 0. But "Can we meet tonight?" is a perfectly normal message! A model that says "impossible" about normal text is broken, and you will see it in the numbers below (an infinite perplexity).
Smoothing moves a little probability to the pairs you have never seen. Two simple policies from the reading:
- Add-k: pretend every pair was seen k extra times: P(next | prev) = (count + k) / (total + k V). With k = 1 ("add-one") this takes far too much from the real counts here: with 2,710 possible next tokens, most of the probability goes to pairs that never happen. Try smaller k.
- Interpolation: mix the bigram with the unigram model: P(next | prev) = λ · count(prev, next) / count(prev) + (1 − λ) · P_unigram(next).
Choose k or λ using the validation messages, never the test messages. Also decide what an
unseen context gives: a previous token with no counts at all (for example </s>, or a word
the model has never seen, which becomes <unk>). Every next token except <s> must get a
probability above 0, and every distribution must sum to 1. Write your policy at the top of
ngram.py.
Part 3: how surprised is the model?
To compare models, measure how well they predict messages they have never seen. For each token
of a held-out message (and its final </s>), take the probability the model gave it, then:
message <s> ok see you </s> probabilities of ok, see, you, </s>: 0.05, 0.1, 0.5, 0.2
negative log-likelihood (NLL) per token: -ln 0.05 = 3.00, -ln 0.1 = 2.30, -ln 0.5 = 0.69, -ln 0.2 = 1.61
average NLL = (3.00 + 2.30 + 0.69 + 1.61) / 4 = 1.90
perplexity = e^1.90 = 6.7
Perplexity is "as unsure as choosing among about 6.7 equally likely tokens at each step".
Lower is better. A probability of 0 gives an infinite NLL, which is why smoothing matters.
Average over all the tokens of all the held-out messages (not per message). Compare models
only with the same tokenizer, the same vocabulary and the same text: with more <unk> tokens,
for example, the numbers look better while the model got worse.
Expect roughly: unigram about 240, a well-smoothed bigram well under 200, add-one smoothing much worse than the unigram model.
Part 4: the same model, trained instead of counted
Now build the bigram model as a neural network: a table W of shape (V, V) with one row of
scores (also called logits) per previous token. That's the entire model: one layer.
softmax turns a row of scores into probabilities:
scores after "call": me 2.0 later 1.0 you 0.0 (a tiny vocabulary of 3)
softmax: e^2.0, e^1.0, e^0.0 = 7.39, 2.72, 1.00 -> divide by their sum 11.11
-> me 0.67 later 0.24 you 0.09 (always positive, always sums to 1)
Training makes the true next token likely. For each (previous, next) pair from the messages,
the cross-entropy loss is −ln(probability of the true next token). That's exactly the NLL from
Part 3, so training lowers the same number you measured. Use bigram_pairs (with <s> and
</s>, as before) to get all the pairs, then the four-line training step from the last quest,
with random mini-batches of pairs (say 1,024 at a time: all 63,000 pairs at once would need
gigabytes of memory for 2,710 scores each). F.cross_entropy computes softmax and cross-entropy
together; check it once against your own computation on a tiny example.
The check you can trust. With no smoothing, the best possible table W gives exactly the count
fractions count(prev, next) / count(prev). So a well-trained network should agree with your
counts, most clearly for frequent contexts like <s>, "i" or "call". Measure it: for each
frequent context, compare the two rows (for example the largest probability difference, or the
KL divergence: Σ p · ln(p / q) over next tokens with count p > 0). Start W at zeros (all next
tokens equally likely) and train for a minute or two on all the training messages. Then measure
its validation perplexity too, and explain what you see: what does the network do with pairs it
never saw, compared with your smoothed counts? (Karpathy's video shows one fix: regularization
works like smoothing.)
Why bother, if counting gives the same answer? Because counting stops here: with two or three previous words, most combinations are never seen. A network can grow, and the next quest makes it bigger.
What to submit
ngram.py,neural_bigram.py(and yourtokenizer.pyif you changed it), plus the code you used to compare the models. No model files: the grader fits the counting models itself (it takes a second), and trains your neural bigram only on tiny corpora. (A full-size table has 2,710 × 2,710 = 7.3 million weights, too big to submit.)SUBMISSION.mdwith these sections (the starter has a template): 1. Counting and smoothing: your boundary handling, your smoothing policy and how you chose it on validation, some suggestions and samples. 2. Comparing unigram, bigram and neural bigram: one table, same tokenizer, vocabulary and validation text; how close the neural model gets to the counts on frequent contexts. 3. An unseen-context failure: a real example where the model has never seen the context or the pair, what it does, and why. 4. How I used AI and checked it.- Your AI transcripts in
.neugen/logs/(neugen log <file>).
How you're graded
- Hidden tests (
neugen testruns the public ones): - Counts, probabilities, sampling, perplexity (all must pass), mostly on tiny corpora where the right answer is known: raw counts with boundaries and nothing across messages, distributions that sum to 1 with no zeros, unseen contexts, suggestions, reproducible sampling that follows your probabilities, and aperplexity()that agrees with your own probabilities (starting at<s>, including</s>). - Held-out perplexity on normal messages you have never seen: unigram at most 260, bigram at most 200. - Neural bigram:bigram_pairs, the shapes, andtrain_neural_bigram(tokens, vocab, seed=0)with your default settings on tiny corpora must reach the counts (average KL at most 0.1 on contexts seen at least 4 times) within a minute. So the defaults must train plainly: put any regularization behind an argument that is 0 by default. - Rubric review by an AI grader: your comparison, the unseen-context failure, and how you used and checked AI.
- Defense: a short conversation about your code.
What you must be able to explain and change
This is an AI-on quest: use AI for anything, including writing code. In the defense you will be asked about these, in your own code:
- the bigram counts of a tiny corpus with
<s>and</s>, by hand, and why the boundaries matter; - your smoothing policy: the probability of an unseen pair, and of anything after an unseen context;
- the perplexity of a tiny example, by hand, and why a single zero makes it infinite;
- how
sample()draws a token, and why the seed makes it reproducible; - softmax and cross-entropy on a tiny row of scores, and why the trained network approaches the counts;
- a small change, for example a different smoothing setting, a trigram, or suggestions that skip punctuation, and what it would do to your numbers.
Suggested path (about 10 hours)
- Read the chapter, and watch the video segments if you like (2.5 hours).
- Counting models with boundaries, suggestions, sampling (2 hours).
- Smoothing and perplexity; tune on validation (2 hours).
- The neural bigram; compare it with the counts (2 hours).
neugen test, the comparison andSUBMISSION.md(1.5 hours).
Optional extension: a trigram model (two previous tokens) that backs off to your bigram when it has not seen a context. Does it beat the bigram on validation? It is not graded.
Tips
- Check on a tiny corpus first. Three short messages, counts by hand, then your code. The grader does exactly this.
- Print a row.
next_token_probs("call")sorted by probability tells you a lot. Does it sum to 1? Is anything 0? - Mind
<s>and</s>.<s>is never predicted;</s>is predicted once per message and counts in perplexity. - Use the tensor. Dividing all rows at once (
counts / counts.sum(dim=1, keepdim=True)) is one line; a Python loop over 2,710 × 2,710 cells is slow. - Shapes again: the network maps
(N,)IDs to(N, V)scores.F.cross_entropywants scores(N, V)and target IDs(N,).
Interface
# tokenizer.py is provided (from the last quest); IDs 0 <unk>, 1 <s>, 2 </s>.
# The grader builds the vocabulary as Vocab.build(train_ham_token_lists, min_count=2).
# Token lists are messages WITHOUT boundaries; the models add <s> and </s> themselves.
# ngram.py
class UnigramModel:
def __init__(self, vocab)
def fit(self, token_lists) -> "UnigramModel"
def next_token_probs(self, prev=None) -> dict[str, float] # ignores prev
def perplexity(self, token_lists) -> float
class BigramModel:
def __init__(self, vocab) # smoothing settings: your defaults
counts: torch.Tensor # after fit: (V, V) RAW counts, row = previous token
def fit(self, token_lists) -> "BigramModel"
def next_token_probs(self, prev: str) -> dict[str, float]
# every token except <s> (which may be left out) with probability > 0; sums to 1;
# works for "<s>", "<unk>" and words never seen
def perplexity(self, token_lists) -> float # exp(mean -log P), </s> included
def sample(self, seed=0, max_tokens=30) -> list[str] # without <s> / </s>
def suggest(self, text: str, k=3) -> list[tuple[str, float]] # no special tokens
# neural_bigram.py
def bigram_pairs(token_lists, vocab) -> tuple[torch.LongTensor, torch.LongTensor] # (prev, next)
class NeuralBigram(nn.Module):
def __init__(self, vocab_size) # a (V, V) table of parameters
def forward(self, prev_ids) -> torch.Tensor # (N,) -> (N, V) logits
def train_neural_bigram(token_lists, vocab, seed=0) -> NeuralBigram # plain training by default
Read now
Read 3.1 'N-Grams' (pages 2-6; skip 3.1.3 on large models), 3.2-3.4 on training and test sets, perplexity and sampling (pages 7-12), and 3.6.1-3.6.3 on Laplace, add-k smoothing and interpolation (pages 14-17). Skip stupid backoff (its scores are not probabilities, so they can't pass the checks) and 3.7.
Explore further
A walkthrough of both halves of this quest, on names letter by letter instead of messages word by word. Watch 12:45-36:17 (counts in a tensor, sampling), 50:14-1:02:57 (the loss, smoothing) and 1:02:57-1:26:17 plus 1:35:49-1:56:16 (the neural network version). He uses one '.' token for start and end; we use <s> and </s>.
Three stages. You only move on when the one before passes.
Automated gates
| Metric | Gate | What it checks |
|---|---|---|
| Counts and boundaries | ≥ 1.0 | Share of checks on tiny corpora that pass: model.counts holds the raw counts, with one <s> and one </s> per message, unknown words as <unk>, and nothing counted across two messages. All must pass. |
| Probabilities and suggestions | ≥ 1.0 | Share of checks that pass: next_token_probs sums to 1 and gives every token (except <s>) a probability above 0, also after <s>, </s> and unknown words; a frequent next word beats an unseen one; suggest() gives the 3 most likely words. All must pass. |
| Sampling | ≥ 1.0 | Share of checks that pass: the same seed gives the same message, different seeds give different messages, valid tokens, max_tokens respected, first words drawn with the model's probabilities. All must pass. |
| Perplexity | ≥ 1.0 | Share of checks where your perplexity() matches the perplexity of your own probabilities, starting at <s> and including </s> (unigram and bigram). All must pass. |
| Unigram perplexity (held out) | ≤ 260 | Perplexity of your UnigramModel on normal messages it never saw, computed by the grader from your next_token_probs. Lower is better. |
| Bigram perplexity (held out) | ≤ 200 | The same for your BigramModel. Add-one smoothing scores about 430 here (worse than the unigram model); a tuned smoothing policy scores under 200. |
| Neural bigram checks | ≥ 1.0 | Share of checks that pass: bigram_pairs with boundaries, one row of V scores per previous token, and train_neural_bigram runs and learns. All must pass. |
| Neural model matches the counts | ≤ 0.1 | After train_neural_bigram with your default settings on tiny corpora: the average KL divergence from the count fractions to your model's probabilities, on contexts seen at least 4 times (worst corpus). 0 means identical. |
| Neural training time (s) | ≤ 60 | Total time of train_neural_bigram on the tiny corpora in the grader (its computer can be 2 to 3 times slower than a laptop). |
Gates run on the public set (which you have) and a hidden set with inputs you haven't seen.
Rubric review need ≥ 60%
One table of validation perplexity for the unigram, smoothed bigram and neural bigram models, all with the same tokenizer, vocabulary (min_count 2) and validation text, plus how the smoothing setting was chosen on validation. A measured comparison of the neural model with the counts on frequent contexts (a probability difference or KL). The write-up explains the result: for example why the plainly trained network matches the raw counts on frequent contexts but does worse than smoothed counts on held-out text, and what would close the gap.
A real example from the messages where the context or the pair was never seen in training (an unknown word, a rare word, a normal pair with count 0). The write-up shows what the model does (its suggestions or probabilities), explains why from the counts and the smoothing policy, and says what a longer context or a neural model could and could not fix.
The logs show the student used AI to understand and to build, then checked it: worked out counts, a smoothed probability or a perplexity by hand on a tiny corpus; checked that rows sum to 1; compared F.cross_entropy with their own computation; caught at least one AI mistake (for example counts across messages, a missing </s> in perplexity, an unnormalized row, test data used for tuning). Using AI is expected and never penalised. Judge the logs, not the claims; missing logs cap this criterion at 1.
Defense need ≥ 50%
A 4-question conversation with the AI examiner about your code. It isn't a trick: if you did it and understood it, it's the easy part. A weak defense on strong work gets you a new variant to redo.

