Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 53 ยท Inside the Transformer

A Language Model in 20 Lines

Build a bigram and trigram language model in plain Python: count next-word probabilities, generate text, measure perplexity and see why n-grams fail.

A language model is a function that answers one question: given the text so far, how likely is each possible next token? Everything else a chatbot does, from answering questions to writing code, is built by asking that question over and over. Before we open up the transformer, it helps to build the simplest language model there is, one that fits in about 20 lines of Python.

This model is called an n-gram model. It looks only at the last few tokens, counts what followed them in some training text, and turns those counts into probabilities. It is far weaker than a transformer, but it shows the whole idea: training is counting, generation is sampling from a distribution, and quality is measured with perplexity. Knowing where it breaks also explains why transformers needed attention. If tokens are new to you, read Tokens and Tokenization first; here we use whole words as tokens to keep the examples readable.

Predict the next token

Context The last n-1 tokens.
Counts How often each token followed it.
Sample Pick one by probability, repeat.

Training is counting. Generation is sampling.

1 / 2

Probability of the next token

Suppose our training text has the phrase "the cat sat" three times and "the cat ran" once. After "the cat", the word "sat" followed 3 of 4 times, so we estimate P(sat | the cat) = 3/4 = 0.75 and P(ran | the cat) = 0.25. That is the whole model: for every context, a table of counts, divided by the total.

In a bigram model the context is one word. In a trigram model it is two. In general an n-gram model uses the previous n-1 tokens. The formula is just a ratio of counts:

P(next | context) = count(context, next) / count(context)

Here is the model in code. We use collections.defaultdict and Counter, and add a special <s> token at the start and </s> at the end of each sentence so the model can learn how sentences begin and finish.

Python Count bigrams and read probabilities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output as a distribution: the probabilities after "the" add up to 1, and "cat", "dog", "mat" and the others share it according to how often they followed "the" in the corpus. A word that never followed "the" gets probability zero. We will come back to that problem.

Generating text by sampling

To generate, start from the sentence-start token, look up the distribution for the current context, sample one token from it, append it, slide the context window forward, and repeat until the end token appears. The randomness comes from the sampling step: a token with probability 0.4 is chosen about 40% of the time. Later lessons on logits, softmax and temperature and top-k and top-p sampling show how real models shape that distribution before sampling.

Python Generate text with a bigram and a trigram model

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bigram model sometimes produces sentences that were never in the corpus, such as mixing the start of one sentence with the end of another. They are locally plausible (every adjacent pair was seen) but may be nonsense as a whole. The trigram model sticks closer to the training sentences, because with two words of context there is often only one continuation. That is the trade-off at the heart of n-grams: more context gives sharper predictions but fewer examples per context.

Seeding the random generator (random.Random(7)) makes the output repeatable. Real LLM APIs sometimes offer a seed for the same reason, but it only helps if everything else is identical.

Measuring quality with perplexity

How do we say one language model is better than another? We show it text it has not seen and ask how much probability it gave to the words that actually appeared. Multiply those probabilities together and you get the probability of the whole text; the higher, the better. Because that number gets tiny, we use logarithms.

Cross-entropy is the average negative log-probability per token, and perplexity is exp(cross-entropy). A good way to read perplexity is as the model's average branching factor: a perplexity of 8 means the model was, on average, as uncertain as if it were choosing uniformly among 8 equally likely tokens. Lower is better. A model that is always certain and correct has perplexity 1.

There is a catch. If the test text contains a pair the model never saw, its probability is 0 and the log is minus infinity. The standard fix is smoothing: pretend every possible token was seen a tiny bit. The simplest version is add-k smoothing, which adds k to every count.

Python Perplexity with add-k smoothing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the unigram model (no context) is the worst, and that the best choice of k depends on the data. With tiny training text, a large k hands too much probability to unseen words. Real systems use better smoothing schemes, but the lesson is general: a model must never be certain that something is impossible just because it has not seen it.

Why n-grams fail

N-gram models fall short in three ways.

  1. Short memory. A trigram sees two tokens. In "The keys that I left on the kitchen table yesterday are missing", the verb must agree with "keys", which is far behind the context window. Extending n fixes this only in theory, because...
  2. Sparsity. The number of possible contexts grows exponentially with n. With a vocabulary of 50,000 tokens there are 2.5 billion possible bigrams and 125 trillion possible trigrams. Almost every long context is unseen, so counts are zero or one.
  3. No sense of similarity. To an n-gram model, "cat" and "kitten" are unrelated symbols. Seeing "the cat sat" teaches it nothing about "the kitten sat". Embeddings solve this by giving similar words similar vectors, so what is learned about one transfers to the other.

Neural language models replace the lookup table with a function that has parameters, takes embeddings as input, and generalizes between similar contexts. Early ones (feed-forward and recurrent networks) still struggled with long range. The transformer's key trick, attention, lets each position look directly at any earlier position. That is the subject of the next lesson.

N-gram models are not obsolete toys. They are still used for fast autocomplete, spell checking, and as a cheap baseline. When someone says a new model "has perplexity X", comparing it with a trigram baseline shows how much the extra machinery buys.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a bigram language model use to predict the next token?

    A bigram model conditions on one previous token, so it counts which token followed each single token in the training text.
  2. 2. A model has perplexity 10 on a test text. How can you read that?

    Perplexity is exp(cross-entropy), the average branching factor. Lower values mean the model is less surprised by the text.
  3. 3. Why is smoothing needed when computing perplexity?

    Without smoothing, one never-seen pair makes the log-probability minus infinity and the perplexity infinite.
  4. 4. Which problem makes large-n n-gram models impractical?

    Sparsity grows exponentially with n. Neural models avoid it by generalizing between similar contexts.

Summary

  • A language model assigns a probability to every possible next token given the context.
  • An n-gram model estimates those probabilities by counting what followed each (n-1)-token context.
  • Generation means sampling a token, appending it, sliding the context and repeating.
  • Perplexity (exp of average negative log-probability) measures how surprised a model is by held-out text; lower is better.
  • Smoothing keeps unseen events from getting probability zero.
  • N-grams fail from short memory, sparsity and no notion of similarity, which is what embeddings and attention address.

Next: see how a transformer lets every token look at every other in Attention from Scratch.