Language modeling: next-token prediction, from n-grams to neural models
Session 1 showed that an LLM predicts the next token. This session asks the harder questions: how much of the past do you need, why counting stops working, and how neural networks fixed it. We follow the history from n-gram models to the first neural language model, with real numbers on real data, and end with the one weakness that next-token training still has.
What you will learn
- The chain rule and the Markov assumption: what an n-gram model throws away
- n-gram counting, data sparsity, and why bigger n overfits, shown with real train and validation numbers
- Smoothing, interpolation and back-off, and the idea behind Kneser–Ney
- Why neural language models generalize: shared embeddings and a fixed number of parameters
- Teacher forcing vs free running, and exposure bias
- Language modeling as compression
Why this matters
“Predict the next token” sounds simple. The hard part is the condition: the next token given everything before it. For sixty years, language models could not afford “everything”, and the reasons why are exactly the reasons transformers work.
Every idea in this session still matters today. Context length is still the main cost of an LLM. Sparsity is why we use subword tokens and embeddings. Smoothing became weight decay and label smoothing. Exposure bias is still a known weakness of next-token training, and part of the reason we do reinforcement learning after pretraining. And n-gram counts are still used to find duplicated training data and to check whether a test set leaked into training.
The exact model and the Markov shortcut
The chain rule from Session 1 is exact. It loses nothing:
The problem is the condition. With a vocabulary of \(|V|\) tokens, there are \(|V|^{t-1}\) possible histories of length \(t - 1\). Nobody can store a probability table for each of them. The classic shortcut is the Markov assumption: only the last \(n - 1\) tokens matter.
A model that uses this with \(n\) tokens in total (\(n - 1\) of context plus the one predicted) is an n-gram model: unigram (\(n = 1\), no context), bigram (\(n = 2\), Session 5), trigram (\(n = 3\)), and so on.
What does the shortcut throw away? In “The keeper who played for three clubs in Spain finally saves”, the verb agrees with “keeper”, eight words back. A trigram model sees only “Spain finally” and has no idea a person is the subject. Long-range agreement, topic, the names of people in a story, the question in a prompt: all of it is lost outside the window.
n-gram models by counting
As in Session 5, the maximum-likelihood estimate is a frequency. With \(c(\cdot)\) meaning “how many times this sequence appears in the training data”:
It looks perfect: more context, better predictions. So why not use \(n = 10\)? Because of sparsity. The number of possible n-grams grows as \(|V|^n\), but the data does not.
Using an 80/10/10 split of names.txt (25,626 training names), with the best add-\(k\) smoothing for each \(n\) chosen on the validation set:
| \(n\) | Possible n-grams \(27^n\) | Seen in training | Validation n-grams never seen in training | Train loss | Validation loss |
|---|---|---|---|---|---|
| 1 | 27 | 27 | 0% | 2.823 | 2.821 |
| 2 | 729 | 620 | 0.0% | 2.454 | 2.453 |
| 3 | 19,683 | 5,806 | 0.6% | 2.187 | 2.223 |
| 4 | 531,441 | 22,701 | 4.9% | 1.919 | 2.102 |
| 5 | 14,348,907 | 44,426 | 13.7% | 1.753 | 2.152 |
The training loss keeps falling as \(n\) grows. The validation loss falls until \(n = 4\), then rises: the 5-gram model has memorized contexts it will rarely see again, and 13.7% of the 5-grams in new names never appeared in training at all. This is overfitting caused by sparsity.
With words instead of characters it is much worse. With a 50,000-word vocabulary there are \(1.25 \times 10^{14}\) possible trigrams, more than any corpus could ever contain. Most perfectly normal sentences contain at least one trigram that was never seen in training.
How to read Figure 1
The gap between the blue and orange bars is overfitting. It grows with \(n\). Now move \(k\) to the far left (almost no smoothing): the validation loss for large \(n\) explodes, because many validation n-grams have probability close to 0. Move it right (heavy smoothing): the large-\(n\) models get closer to uniform and lose their advantage. Sample from \(n = 6\): many names are copies of training names. The model is not generalizing; it is replaying. Also notice that with only 2,400 training names the best \(n\) is smaller than with the full 25,626 names (where it was 4): less data can only support less context.
Fixing sparsity: smoothing, interpolation and back-off
Statistical language modeling spent about thirty years on one question: how much probability to give to things you have never seen.
Add-\(k\) smoothing
Simple, but crude: it gives the same extra probability to every unseen continuation, sensible or not.
Figure 2 runs formulas (6.3) and (6.4) on a corpus small enough to follow by eye: four sentences, a vocabulary of 8 words, and “.” as the start and end token. Each step of the animation is one line of the counting loop. Then the chosen row of the table is turned into probabilities, one word at a time, with the real numbers put into (6.4).
- \(c(h, w) \leftarrow 0\) and \(c(h) \leftarrow 0\) for all words
- for each sentence, padded with “.” at both ends:
- for \(t = 1, \dots, T\): \(h \leftarrow x_{t-1},\ w \leftarrow x_t\)
- \(c(h, w) \leftarrow c(h, w) + 1;\ c(h) \leftarrow c(h) + 1\)
- for each \(w \in V\): \(p_k(w \mid h) \leftarrow (c(h, w) + k)/(c(h) + k|V|)\) // (6.4)
- check: \(\sum_w p_k(w \mid h) = 1\)
How to read Figure 2
Press Play. The window moves over 24 bigrams (6 per sentence), and each one adds 1 to one cell and 1 to its row sum. At the end, the row “the” holds keeper 3, striker 1, shot 2, ball 2, so \(c(\text{the}) = 8\). Then the probabilities are filled in. With \(k = 0.5\): \(p(\text{keeper} \mid \text{the}) = (3 + 0.5)/(8 + 0.5 \times 8) = 3.5/12 = 0.292\), lower than the unsmoothed 3/8 = 0.375. Each of the 4 unseen words gets \(0.5/12 = 0.042\), together 0.167 of the mass. Move \(k\) to 0: unseen words get exactly 0. Move it to 2: the row is close to uniform. Choose the row “striker”: it was seen only once, so smoothing changes it the most. The more data a context has, the less smoothing matters.
Interpolation and back-off
A better idea: mix models of different orders. A long context is precise but often unseen; a short context is vague but always available. Linear interpolation combines them with weights that sum to 1:
The \(\lambda\)s are tuned on held-out data. On the names, interpolating the 1- to 4-gram models with \(\lambda = (0.01, 0.1, 0.3, 0.59)\) gives a validation loss of 2.083, better than the best single model (2.102). Back-off is the related idea of using the longest context that was actually seen, and “backing off” to a shorter one otherwise.
Kneser–Ney: the best classical method
Kneser–Ney smoothing adds one clever observation. When you back off to a shorter context, ask not “how frequent is this word?” but “in how many different contexts does it appear?”. “Francisco” is frequent, but almost only after “San”, so it is a bad guess after an unseen context. “Glasses” follows many different words, so it is a better guess. This is the continuation probability:
Modified Kneser–Ney with interpolation was the standard baseline until neural models took over in the 2010s. [Certain]
Neural language models: sharing what you learn
Even with perfect smoothing, n-grams have a deeper problem. They treat every context as a separate, unrelated row of a table. Seeing “the keeper saves the shot” teaches the model nothing about “the goalkeeper stops the shot”, because those are different rows.
Bengio et al. (2003) fixed this with three ideas, all still inside every LLM:
- Map every word to a learned embedding vector (Session 1, formula 1.4). Similar words get similar vectors.
- Predict the next word with a neural network that reads the embeddings of the context words.
- Train everything together with the cross-entropy loss.
With context embeddings \(\mathbf{e}_{t-n+1}, \dots, \mathbf{e}_{t-1} \in \R^{d}\) joined into one long vector, the model is:
Why does this generalize? If “keeper” and “goalkeeper” have similar embeddings, any context containing one predicts almost like a context containing the other, even if one of them was never seen in that position. The model shares statistical strength between similar contexts, which a table cannot do.
The parameter count also changes from exponential to linear in the context size:
Words with \(|V| = 50{,}000\), a 5-gram (\(n = 5\)): a full table would need about \(50{,}000^5 \approx 3 \times 10^{23}\) numbers. The neural model with \(d = 100\) and \(h = 500\) needs \(5{,}000{,}000 + 200{,}000 + 25{,}000{,}000 \approx 30\) million. And doubling the context only adds another \((n-1)\,d\,h\) block.
This model still has a fixed window of \(n - 1\) tokens. Recurrent networks (session 7) removed the fixed window but forgot slowly; transformers (Track 2) let every token look at every earlier token directly. Each step is the same story: use more of the context, without a table that explodes.
Training vs generation: teacher forcing and exposure bias
During training, the model always conditions on the true previous tokens from the data. This is teacher forcing. It is what makes training parallel (Session 1, Figure 5) and stable.
The training loss of one sentence is the average, over its positions, of the negative log-probability of the true next token, each computed from the true history:
- \(x_1, \dots, x_T\)
- the true (gold) tokens of the sentence, including the end token
- \(p_\theta\)
- the model with parameters \(\theta\), for example (6.7)
- \(-\log p_\theta(x_t \mid \dots)\)
- the loss \(\ell_t\) at position \(t\): 0 if the model gave the true token probability 1, large if it gave it almost 0
- \(e^{\mathcal{L}}\)
- the perplexity (Session 3)
Figure 4 computes (6.9) token by token. The model is the neural model (6.7) with a context of 2 words, embeddings of size 4 and 12 hidden units, trained in your browser on the four sentences of Figure 2 (400 full-batch Adam steps, fixed seed). You can also score the sentence with the add-k bigram of Figure 2.
- \(L \leftarrow 0\)
- for \(t = 1, \dots, T\):
- context
- p
- \(\ell_t \leftarrow -\log p(x_t)\) // \(x_t\) is the gold token
- \(L \leftarrow L + \ell_t\)
- return \(L/T\) // (6.9)
How to read Figure 4
Press Play with the defaults (neural model, 400 steps, the first sentence). After “. the”, the training data had keeper 3 times and striker once, so the model gives keeper 0.750 and the loss is \(-\ln 0.750 = 0.288\). After “the keeper” it gives saves 0.666 (loss 0.406), and after “saves the” it splits between shot and ball (loss 0.692). The other positions are certain (loss close to 0). The mean is 0.231 nats per token. That is the lowest possible value for a model with a context of 2 words on this data: the model has learned the counts. With 0 training steps every word gets about 1/8 and the mean is 2.011, close to \(\ln 8 = 2.079\). Now choose the new sentence “the striker saves the ball”. The striker was never seen saving. After 25 steps the loss at “saves” is 1.523; after 400 steps it is 7.600, because the model has become sure that a striker kicks. On 4 sentences, more training means memorizing, not generalizing. The bigram with \(k = 0.5\) gives 2.303 there; with \(k = 0\) it gives infinity. Finally, choose “the striker kicks the ball”, then Free running: the model writes “keeper” instead of “striker” at \(t = 2\), so at \(t = 3\) it reads “the keeper” and gives the gold word kicks only 0.333 (loss 1.098, against 0.001 with teacher forcing).
During generation, the model conditions on its own previous tokens. If it makes one mistake, every later prediction is conditioned on a history it never saw in training. This mismatch is called exposure bias. A rough way to see why it matters: if each token is “acceptable” with probability \(p\), independently, a whole output of \(T\) tokens has no bad token with probability
Even with \(p = 0.99\), an output of 100 tokens is error-free only \(0.99^{100} = 36.6\%\) of the time. With \(p = 0.999\) and 1,000 tokens: \(36.8\%\). The independence assumption is too simple (models can recover from small slips), but the trend is real: long generations drift.
Free running in Figure 4 shows the start of this drift on a tiny scale: one different word at \(t = 2\), and the model reads a history that differs from the text it is scored on. How the field deals with it: scheduled sampling (sometimes feed the model its own predictions during training), sequence-level training with rewards (reinforcement learning after pretraining, Track 4), better decoding (session 79), and asking the model to check and correct its own work.
Language modeling is compression
There is a deep link between predicting and compressing. With arithmetic coding, a text can be stored in almost exactly \(\sum_t -\log_2 p(x_t \mid x_{\lt t})\) bits. So the cross-entropy loss is literally the number of bits per token needed to store text with that model. A better language model is a better compressor. Shannon used this idea in 1951 to estimate the entropy of English by asking people to guess the next letter. This is also why bits per byte (Session 3) is the natural unit for comparing language models.
What a language model can do with one formula
| Use | How | Example |
|---|---|---|
| Score a text | Sum of log-probabilities, formula (6.1) with logs | Rank speech-recognition or OCR candidates; detect unusual text |
| Generate | Sample one token at a time | Chat, captions, scene descriptions |
| Complete a prompt | Condition on a prefix, then generate | Every instruction-following use of an LLM |
| Classify | Compare the probability of label words (Session 1, formula 1.13) | Sentiment, IAB category, “is this a goal?” |
| Compress | Arithmetic coding with the model’s probabilities | Bits per byte as an evaluation metric |
| Find duplicates and leaks | Long n-gram overlap (for example 13-grams) | Remove duplicated training text; check that test sets did not leak into training |
Pseudo-code
- input: training sequences, max order \(n\), smoothing \(k\), weights \(\lambda_1..\lambda_n\) (sum to 1)
- for \(m = 1\) to \(n\) do count every m-gram \(c_m(\cdot)\) and every context \(c_m(\text{context})\)
- function \(p(x \mid h)\):
- \(s \leftarrow 0\)
- for \(m = 1\) to \(n\) do
- \(h_m \leftarrow\) last \(m - 1\) tokens of \(h\)
- \(s \leftarrow s + \lambda_m \cdot \dfrac{c_m(h_m, x) + k}{c_m(h_m) + k|V|}\) // formulas (6.4), (6.5)
- return \(s\)
- tune \(k\) and \(\lambda\) on a validation set by minimizing its average \(-\log p\)
- input: a batch of (context of \(n-1\) token IDs, next token ID)
- \(E \leftarrow C[\text{context}]\) // \((B, n-1, d)\): one shared table
- \(\mathbf{x} \leftarrow\) reshape \(E\) to \((B, (n-1)d)\) // concatenate
- \(\mathbf{h} \leftarrow \tanh(\mathbf{x} H^\top + \mathbf{b}_h)\)
- \(\mathbf{z} \leftarrow \mathbf{h}\, U^\top + \mathbf{b}\) // \((B, |V|)\) logits, formula (6.7)
- \(\mathcal{L} \leftarrow\) cross-entropy\((\mathbf{z}, \text{next token})\)
- backpropagate and take an AdamW step // Session 4
Algorithm 2 in PyTorch, for the names data (a context of 3 characters). This is the model you will build in the next labs:
import torch, torch.nn as nn, torch.nn.functional as F torch.manual_seed(1337) words = open("names.txt").read().split() stoi = {c: i + 1 for i, c in enumerate(sorted(set("".join(words))))}; stoi["."] = 0 ctx = 3 X, Y = [], [] for w in words: h = [0] * ctx # start with "..." for ch in w + ".": X.append(h); Y.append(stoi[ch]); h = h[1:] + [stoi[ch]] X, Y = torch.tensor(X), torch.tensor(Y) class BengioLM(nn.Module): def __init__(self, V=27, d=10, ctx=3, h=200): super().__init__() self.C = nn.Embedding(V, d) # shared table, |V| x d self.H = nn.Linear(ctx * d, h) self.U = nn.Linear(h, V) def forward(self, idx): # idx: (B, ctx) int64 x = self.C(idx).flatten(1) # (B, ctx*d): concatenation return self.U(torch.tanh(self.H(x))) # (B, V) logits, formula (6.7) model = BengioLM() opt = torch.optim.AdamW(model.parameters(), lr=1e-2, weight_decay=0.01) for step in range(5000): ix = torch.randint(0, len(X), (64,)) # a random mini-batch (Session 4, formula 4.7) loss = F.cross_entropy(model(X[ix]), Y[ix]) opt.zero_grad(set_to_none=True); loss.backward(); opt.step() with torch.no_grad(): print(F.cross_entropy(model(X), Y).item()) # compare with the 4-gram table (about 1.9 train, 2.1 validation)
Use a validation split as in Session 5 before you believe any number. The neural model should match or beat the best interpolated n-gram on validation once it is trained long enough, with far fewer parameters than a 4-gram table. Measure it rather than trusting this sentence: the result depends on size and training time.
Common mistakes
- Choosing \(n\) on training loss. Training loss always prefers larger \(n\). Choose on validation (Figure 1).
- Tuning smoothing on the test set. Use a separate validation split, or your reported number is optimistic.
- Forgetting start padding. The first tokens need a context too; pad with start tokens (“...” in the code).
- Thinking a longer context window always helps. Only if the model can use it and has the data to learn it; that is the whole lesson of sparsity.
- Mixing up “model of the next token” and “model of the truth”. A language model is trained to imitate text, so it scores fluent nonsense highly (Session 3).
Interview questions
What is the Markov assumption in language modeling, and what does it cost?basic
Why do higher-order n-gram models overfit?core
Explain interpolation, back-off and the main idea of Kneser–Ney.core
Why do neural language models generalize better than n-grams?core
What is exposure bias? How is it addressed?advanced
How is the training loss of a sentence computed with teacher forcing, and why is it cheap?core
Why is cross-entropy the number of bits needed to compress text?advanced
Where are n-grams still used in modern LLM work?basic
Exercises
- Using Figure 1, find the \(k\) that gives the lowest validation loss for \(n = 5\). How does it compare with the best \(k\) for \(n = 3\)? Why is it different?
- Implement Algorithm 1 for \(n = 4\) on names.txt and reproduce a validation loss near 2.08. Try tuning the \(\lambda\)s.
- Train the PyTorch model with \(d = 2\) and plot the 27 character embeddings. Which letters end up close together?
- With per-token accuracy 0.995, how long can an output be before the chance of no error drops below 50% under (6.10)?
- Count the parameters of
BengioLMwith the defaults, and compare them with the number of seen 4-grams (22,701) and possible 4-grams (531,441).
Answers and hintscheck
Key takeaways
- The chain rule (6.1) is exact; the Markov assumption (6.2) makes counting possible but throws away everything outside a short window.
- n-gram tables grow as \(|V|^n\): on names, validation loss is best at \(n = 4\) (2.10) and worse at \(n = 5\) (2.15), while training loss keeps falling.
- Smoothing, interpolation (2.08 on names) and Kneser–Ney were the classical fixes.
- Neural LMs (6.7) share strength through embeddings, with parameters growing linearly in context (6.8). Transformers continue the same idea with full context.
- Teacher forcing trains on gold history; generation runs on its own outputs, so errors can compound (exposure bias, 6.10). Cross-entropy in bits is compressed size.
References for this session
- Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 3: N-gram Language Models
- Bengio et al. (2003). A Neural Probabilistic Language Model
- Bengio et al. (2003). A Neural Probabilistic Language Model
- Chen & Goodman (1998). An Empirical Study of Smoothing Techniques for Language Modeling
- Bengio et al. (2015). Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks
- Shannon (1951). Prediction and Entropy of Printed English