What a Language Model Computes

A chat model can look like it understands you. Underneath, it does one thing over and over: given the text so far, it gives a probability to every possible next piece of text. It picks one piece, adds it to the text, and repeats. Everything an assistant writes, including answers, code, and tool calls, is built this way, one piece at a time.

This lesson builds the smallest possible model of this kind in Java: a table of counts over characters. You will measure how good it is with two numbers (cross-entropy and perplexity), see why a table cannot grow into a real model, and see what replaces it: a function with adjustable numbers that is trained to lower a loss. Afterwards you can explain what a model's output is, what "training" means, and how the numbers in a model card relate to the small examples here.

All programs use the same tiny corpus. A corpus is the body of text a model learns from. This one has 119 characters, which is small enough to read every count by hand. A real model reads trillions of tokens. The method is the same. Only the model, the symbols, and the amount of text change.

the cat sat on the mat. the dog sat on the log. the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.

Lesson 6 explains tokens, the pieces real models use. Until then, one symbol is one character, and the vocabulary is the set of distinct symbols.

Example 1: text as a sequence of symbols

A language model does not see words or meaning. It sees a sequence of symbols taken from a fixed list. Before building anything, this example counts the characters of the corpus and how often each one occurs. Look at how few distinct characters there are.

import java.util.Map;
import java.util.TreeMap;

public class Characters {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Integer> counts = new TreeMap<>();
        for (char c : CORPUS.toCharArray()) counts.merge(c, 1, Integer::sum);
        System.out.println("length = " + CORPUS.length());
        System.out.println("distinct = " + counts.size());
        StringBuilder sb = new StringBuilder();
        counts.forEach((c, n) -> sb.append('[').append(c).append("]=").append(n).append(' '));
        System.out.println(sb.toString().trim());
    }
}

The program prints the length, the number of distinct characters, and one count per character.

length = 119
distinct = 15
[ ]=30 [.]=5 [a]=15 [c]=4 [d]=5 [e]=8 [g]=5 [h]=8 [l]=1 [m]=2 [n]=4 [o]=8 [s]=5 [t]=17 [w]=2

The corpus has 119 characters and 15 distinct ones, so the vocabulary has 15 symbols. The space is the most common symbol (30 times), then t (17) and a (15).

Counting symbols is already a model. The unigram model predicts each character by its overall frequency, with no context at all. If you had to guess the next character with no other information, you would guess a space, because it is the most common. Example 14 measures how weak that guess is.

Example 2: bigram counts

A better guess uses the character just before. After h, an English reader expects e, not z. A bigram is a pair of neighbors. The table counts, for every character, how often each other character follows it. This table is the whole model: nothing else is stored. The program prints four rows of it.

import java.util.Map;
import java.util.TreeMap;

public class BigramCounts {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        for (int i = 0; i + 1 < CORPUS.length(); i++) {
            table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                 .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
        }
        for (char c : new char[] {'t', 'h', ' ', '.'}) {
            System.out.println("after [" + c + "]: " + table.get(c));
        }
    }
}

Each printed row is a map from "next character" to "how many times it followed".

after [t]: { =6, .=3, h=8}
after [h]: {e=8}
after [ ]: {a=4, c=4, d=4, l=1, m=2, o=3, s=5, t=7}
after [.]: { =4}

Each row answers the question "what followed this character in the corpus?" Take the rows one at a time:

• After h, the corpus has only e (8 times), because every h in the text sits in the word the.
• After t there are three options: h (8 times, the start of the), a space (6 times, the end of cat and sat), and . (3 times, the end of mat or cat before a full stop).
• After a space, 8 different characters occur, because any word can start there.
• After . only a space follows.

The model has no idea what a word is. It knows only which character tends to come after which.

Example 3: counts become probabilities

Counts are hard to compare between rows, because a row with 30 observations and a row with 8 observations have different totals. Dividing each count by its row total fixes that. The result is a conditional probability. The notation P(next | current) reads "the probability of next given current".

For example, after t the corpus has 6 spaces, 3 full stops, and 8 h characters, 17 in total. So P(h | t) = 8/17, which is about 0.471. Each row then sums to 1, which makes it a probability distribution: a list of non-negative numbers that add up to 1. The program does this division for three rows and checks the sums.

import java.util.Locale;
import java.util.Map;
import java.util.TreeMap;

public class Probabilities {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        for (int i = 0; i + 1 < CORPUS.length(); i++) {
            table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                 .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
        }
        for (char c : new char[] {' ', 't', 'a'}) {
            Map<Character, Integer> row = table.get(c);
            int total = row.values().stream().mapToInt(Integer::intValue).sum();
            double sum = 0;
            StringBuilder sb = new StringBuilder("P(. | [" + c + "]) ");
            for (Map.Entry<Character, Integer> e : row.entrySet()) {
                double p = (double) e.getValue() / total;
                sum += p;
                sb.append(String.format(Locale.ROOT, "[%c]=%d/%d=%.3f ", e.getKey(), e.getValue(), total, p));
            }
            System.out.println(sb.toString().trim());
            System.out.println("  row sum = " + String.format(Locale.ROOT, "%.3f", sum));
        }
    }
}

Each printed row shows the fractions and then the row sum.

P(. | [ ]) [a]=4/30=0.133 [c]=4/30=0.133 [d]=4/30=0.133 [l]=1/30=0.033 [m]=2/30=0.067 [o]=3/30=0.100 [s]=5/30=0.167 [t]=7/30=0.233
  row sum = 1.000
P(. | [t]) [ ]=6/17=0.353 [.]=3/17=0.176 [h]=8/17=0.471
  row sum = 1.000
P(. | [a]) [ ]=3/15=0.200 [n]=1/15=0.067 [t]=9/15=0.600 [w]=2/15=0.133
  row sum = 1.000

The rows show the counts as fractions of the row total. After a space, t has 7 of 30 (0.233) because the is the most common word. After t, the three options have 6, 3, and 8 of 17. The row sum of 1.000 confirms each row is a distribution.

These fractions are the maximum-likelihood estimate. This means they are the probabilities that make the corpus most probable for a model of this shape. The next examples use them to predict and to generate.

Example 4: predict the most likely next character

With probabilities in hand, prediction is a lookup: find the row of the current character and take the entry with the highest count. Ties resolve to the first character in sorted order. The program predicts the character after each of t, h, e, s, a space, and ., and prints the evidence behind each answer.

import java.util.Map;
import java.util.TreeMap;

public class MostLikely {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        for (int i = 0; i + 1 < CORPUS.length(); i++) {
            table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                 .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
        }
        for (char c : "thes .".toCharArray()) {
            char best = 0;
            int bestCount = -1, total = 0;
            for (Map.Entry<Character, Integer> e : table.get(c).entrySet()) {
                total += e.getValue();
                if (e.getValue() > bestCount) { best = e.getKey(); bestCount = e.getValue(); }
            }
            System.out.println("after [" + c + "] predict [" + best + "] (" + bestCount + " of " + total + ")");
        }
    }
}

The line (8 of 17) means the winner had 8 of the row's 17 observations.

after [t] predict [h] (8 of 17)
after [h] predict [e] (8 of 8)
after [e] predict [ ] (8 of 8)
after [s] predict [a] (5 of 5)
after [ ] predict [t] (7 of 30)
after [.] predict [ ] (4 of 4)

The model predicts e after h with certainty (8 of 8), because the corpus never shows another letter there. After t it predicts h with 8 of 17, a weak majority. After a space it predicts t with only 7 of 30.

The count in parentheses is the evidence behind each answer, and it shows how confident the model should be. A prediction with probability 0.23 is wrong more often than it is right. This is why a model's output is a distribution and not a single answer.

Example 5: greedy generation

Prediction looks one step ahead. Generation repeats it: append the predicted character, then predict again from the new last character. Greedy generation always takes the most likely symbol. Starting from t, this program generates 60 characters. Watch for a pattern in the result.

import java.util.Map;
import java.util.TreeMap;

public class GreedyGeneration {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        for (int i = 0; i + 1 < CORPUS.length(); i++) {
            table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                 .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
        }
        StringBuilder out = new StringBuilder("t");
        char current = 't';
        for (int i = 0; i < 59; i++) {
            char best = 0;
            int bestCount = -1;
            for (Map.Entry<Character, Integer> e : table.get(current).entrySet()) {
                if (e.getValue() > bestCount) { best = e.getKey(); bestCount = e.getValue(); }
            }
            out.append(best);
            current = best;
        }
        System.out.println(out);
    }
}

The program prints the 60 characters on one line.

the the the the the the the the the the the the the the the

The output is the the the .... Follow the steps: greedy generation went t, then h, then e, then a space (the most likely character after e), then t again (the most likely after a space), and so on. The state after the space is the same as at the start, so the sequence cycles forever.

The cause is that the next symbol depends only on the current symbol, and the choice is deterministic. Real models have far longer contexts, but greedy decoding can still fall into loops on repeated phrases. This is one reason engines sample (lesson 12) and offer repetition penalties (lesson 13).

Example 6: sampling instead of always taking the best

To escape the loop, the model must sometimes pick a less likely character. Sampling draws the next symbol at random with the probabilities of the row, so a symbol with probability 0.3 is chosen about 30 percent of the time.

The program does this with a simple walk along the row. It picks a random number in [0, 1), scaled to the row total, and subtracts each count in turn. The symbol where the number drops below zero is the chosen one. A larger count takes a larger share of the line, so it is chosen more often. Lesson 12 calls this inverse-CDF sampling. A java.util.Random with a fixed seed gives the same numbers on every run, so the output below can be reproduced.

import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

public class SampledGeneration {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        for (int i = 0; i + 1 < CORPUS.length(); i++) {
            table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                 .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
        }
        for (long seed : new long[] {1, 2, 3}) {
            Random rng = new Random(seed);
            StringBuilder out = new StringBuilder("t");
            char current = 't';
            for (int i = 0; i < 59; i++) {
                Map<Character, Integer> row = table.get(current);
                int total = row.values().stream().mapToInt(Integer::intValue).sum();
                double r = rng.nextDouble() * total;
                char chosen = 0;
                for (Map.Entry<Character, Integer> e : row.entrySet()) {
                    chosen = e.getKey();
                    r -= e.getValue();
                    if (r < 0) break;
                }
                out.append(chosen);
                current = chosen;
            }
            System.out.println("seed " + seed + ": " + out);
        }
    }
}

The program generates one 60-character text for each of three seeds.

seed 1: the dog. the dog. ca sa on mat sa cathe cand on san mat. sat
seed 2: the the athe t lon mathe t sandon a t og a at. the t. cat ca
seed 3: the t sa the the og log the caw ca sa mat. don the a og sa c

Each seed gives a different text, and each text contains pieces of real words (the dog., sat, mat., cand). Sampling lets less likely transitions happen, so the output escapes the the the loop. Fragments such as cathe and san appear because the model sees one character of context and cannot track a word.

The same program with the same seed prints the same text, because java.util.Random is deterministic for a given seed. Lesson 4 showed the same behavior in llama-server with the seed request field.

Example 7: the probability of a whole sentence

How likely is a whole sentence under the model? The chain rule of probability answers this. It says that the probability of a sequence is the product of each symbol's probability given the ones before it:

P(x1, x2, x3) = P(x1) * P(x2 | x1) * P(x3 | x1, x2)

A bigram model keeps only the last symbol as context, so P(x3 | x1, x2) becomes P(x3 | x2). The program computes the probability of the cat. this way, one step at a time.

Multiplying many numbers below 1 gives a very small result, and computers cannot store arbitrarily small numbers. So the program also shows why real code adds logarithms instead. The logarithm of a product is the sum of the logarithms, and a sum of ordinary numbers stays easy to store.

import java.util.Locale;
import java.util.Map;
import java.util.TreeMap;

public class ChainRule {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        Map<Character, Integer> unigram = new TreeMap<>();
        for (int i = 0; i < CORPUS.length(); i++) {
            unigram.merge(CORPUS.charAt(i), 1, Integer::sum);
            if (i + 1 < CORPUS.length()) {
                table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                     .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
            }
        }
        String sentence = "the cat.";
        double p = (double) unigram.get(sentence.charAt(0)) / CORPUS.length();
        double logP = Math.log(p);
        System.out.println(String.format(Locale.ROOT, "P(%c) = %.4f", sentence.charAt(0), p));
        for (int i = 1; i < sentence.length(); i++) {
            Map<Character, Integer> row = table.get(sentence.charAt(i - 1));
            int total = row.values().stream().mapToInt(Integer::intValue).sum();
            double step = (double) row.get(sentence.charAt(i)) / total;
            p *= step;
            logP += Math.log(step);
            System.out.println(String.format(Locale.ROOT, "P(%c | %c) = %.4f", sentence.charAt(i), sentence.charAt(i - 1), step));
        }
        System.out.println(String.format(Locale.ROOT, "product = %.6f, exp(sum of logs) = %.6f", p, Math.exp(logP)));

        double product = 1.0, logSum = 0.0;
        for (int i = 0; i < 400; i++) { product *= 0.1; logSum += Math.log(0.1); }
        System.out.println("400 steps of 0.1: product = " + product + ", sum of logs = " + String.format(Locale.ROOT, "%.1f", logSum));
    }
}

The program prints each step's probability, the final product, and the underflow demonstration.

P(t) = 0.1429
P(h | t) = 0.4706
P(e | h) = 1.0000
P(  | e) = 1.0000
P(c |  ) = 0.1333
P(a | c) = 1.0000
P(t | a) = 0.6000
P(. | t) = 0.1765
product = 0.000949, exp(sum of logs) = 0.000949
400 steps of 0.1: product = 0.0, sum of logs = -921.0

The first line uses the character's overall frequency: 17 of 119 positions hold t, so P(t) = 0.1429. The next lines are row lookups from Example 3. Two steps are certain (P(e | h) and P(a | c) equal 1), and the others reduce the probability. Multiplying all eight numbers gives 0.000949 for the whole sentence.

The product and exp(sum of logs) agree to six decimals, so the two ways of computing it are the same. The last line shows why logs are used. Multiplying 400 numbers of 0.1 gives 0.0, because the true value, 10^-400, is smaller than the smallest double (about 4.9e-324). The computer rounds it down to zero. This is called underflow. The sum of logs stays an ordinary number, -921.0. A model scoring a document with thousands of tokens needs logs for the same reason.

Example 8: cross-entropy and perplexity

Sentence probabilities shrink with length, so they cannot compare texts of different sizes. Two averages fix that, and both are used on every model card.

To measure a model on a text, take the model's probability for each actual next symbol and compute the surprise, which is -log2(p) bits. A symbol the model expected (p near 1) has surprise near 0. A symbol it thought unlikely has large surprise. One bit of surprise is the information in one fair coin flip. The average surprise over the text is the cross-entropy.

Perplexity is 2 raised to the cross-entropy. It reads as "the model is as unsure as if it chose among this many equally likely symbols at each step". A hand-sized case: if the model gave every symbol probability 1/4, each step has surprise 2 bits, and the perplexity is 2^2 = 4.

The program scores two sentences. One is made of transitions the corpus contains. The other has a transition the corpus never contained.

import java.util.Locale;
import java.util.Map;
import java.util.TreeMap;

public class Perplexity {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    static double crossEntropyBits(Map<Character, Map<Character, Integer>> table, String text) {
        double bits = 0;
        for (int i = 1; i < text.length(); i++) {
            Map<Character, Integer> row = table.getOrDefault(text.charAt(i - 1), Map.of());
            int total = row.values().stream().mapToInt(Integer::intValue).sum();
            int count = row.getOrDefault(text.charAt(i), 0);
            if (count == 0) return Double.POSITIVE_INFINITY;
            bits += -Math.log((double) count / total) / Math.log(2);
        }
        return bits / (text.length() - 1);
    }

    public static void main(String[] args) {
        Map<Character, Map<Character, Integer>> table = new TreeMap<>();
        for (int i = 0; i + 1 < CORPUS.length(); i++) {
            table.computeIfAbsent(CORPUS.charAt(i), k -> new TreeMap<>())
                 .merge(CORPUS.charAt(i + 1), 1, Integer::sum);
        }
        for (String s : new String[] {"the dog saw the mat.", "the bird sat."}) {
            double h = crossEntropyBits(table, s);
            System.out.println(String.format(Locale.ROOT, "%-22s cross-entropy = %.3f bits, perplexity = %.3f", "\"" + s + "\"", h, Math.pow(2, h)));
        }
    }
}

The program prints a cross-entropy and a perplexity for each sentence.

"the dog saw the mat." cross-entropy = 1.135 bits, perplexity = 2.196
"the bird sat."        cross-entropy = Infinity bits, perplexity = Infinity

The first sentence has a cross-entropy of 1.135 bits per character and a perplexity of 2.196. On average, the model is as unsure as if it chose between 2.2 equally likely characters. That is much better than 15, the perplexity of guessing among all 15 characters.

The second sentence contains the pair [ ] followed by b, which never occurs in the corpus. The model gives it probability 0, so the surprise is infinite and the cross-entropy is infinite. One unseen pair ruins the score of the whole sentence. Real evaluations avoid this because a neural model gives every token a nonzero probability. The idea of a huge penalty for a confident wrong prediction carries over as a very large loss.

Example 9: a trigram model

The bigram model looks at one character. What if the model looks at two? A trigram model uses the last two symbols as context. More context makes predictions sharper. For example, t alone is followed by h only 8 times in 17, while a space followed by t is always followed by h, because every word that starts with t is the.

The cost is that more contexts appear only rarely or never. This program scores a sentence from the training text and a new sentence with both models. It also counts how many of the new sentence's transitions have a count of zero.

import java.util.Locale;
import java.util.Map;
import java.util.TreeMap;

public class Trigram {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    static Map<String, Map<Character, Integer>> build(int n) {
        Map<String, Map<Character, Integer>> t = new TreeMap<>();
        for (int i = n; i < CORPUS.length(); i++) {
            t.computeIfAbsent(CORPUS.substring(i - n, i), k -> new TreeMap<>()).merge(CORPUS.charAt(i), 1, Integer::sum);
        }
        return t;
    }

    static String score(Map<String, Map<Character, Integer>> t, int n, String text) {
        double bits = 0;
        int zeros = 0;
        for (int i = n; i < text.length(); i++) {
            Map<Character, Integer> row = t.getOrDefault(text.substring(i - n, i), Map.of());
            int total = row.values().stream().mapToInt(Integer::intValue).sum();
            int count = row.getOrDefault(text.charAt(i), 0);
            if (count == 0) { zeros++; continue; }
            bits += -Math.log((double) count / total) / Math.log(2);
        }
        int steps = text.length() - n;
        String ppl = zeros > 0 ? "infinite" : String.format(Locale.ROOT, "%.3f", Math.pow(2, bits / steps));
        return "perplexity = " + ppl + ", zero-count steps = " + zeros + " of " + steps;
    }

    public static void main(String[] args) {
        var bi = build(1);
        var tri = build(2);
        System.out.println("contexts: bigram " + bi.size() + ", trigram " + tri.size());
        for (String s : new String[] {"the cat sat on the mat.", "the dog saw a cat."}) {
            System.out.println("\"" + s + "\"");
            System.out.println("  bigram:  " + score(bi, 1, s));
            System.out.println("  trigram: " + score(tri, 2, s));
        }
    }
}

For each sentence, the program prints the perplexity under each model and the number of zero-count steps.

contexts: bigram 15, trigram 31
"the cat sat on the mat."
  bigram:  perplexity = 2.308, zero-count steps = 0 of 22
  trigram: perplexity = 1.441, zero-count steps = 0 of 21
"the dog saw a cat."
  bigram:  perplexity = 2.513, zero-count steps = 0 of 17
  trigram: perplexity = infinite, zero-count steps = 1 of 16

The trigram model has 31 contexts (pairs of characters) against 15 for the bigram model, so its table has more rows, each with fewer entries.

On the sentence made of text seen in training, perplexity drops from 2.308 to 1.441, because two characters of context narrow the choice. On the new sentence the dog saw a cat. the bigram model still works (2.513). The trigram model meets one step with a zero count, so its perplexity is infinite.

That is the trade-off of context length: more context gives sharper predictions on familiar text and more holes on unfamiliar text. Smoothing fills the holes.

Example 10: add-one smoothing

A zero probability makes a whole sentence impossible and its perplexity infinite, even when only one transition is new. Smoothing moves a little probability to unseen pairs.

Add-one smoothing (also called Laplace smoothing) adds 1 to every count, including counts of zero. It also adds the vocabulary size V to the row total, so rows still sum to 1:

P(next | context) = (count + 1) / (total + V)

Here V is 15, the number of distinct characters. A hand-sized case: after h the corpus has e 8 times out of 8. With smoothing, P(e | h) = 9/23, about 0.39, and an unseen letter gets 1/23, about 0.04. No probability is zero any more.

import java.util.Locale;
import java.util.Map;
import java.util.TreeMap;

public class Smoothing {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    static Map<String, Map<Character, Integer>> build(int n) {
        Map<String, Map<Character, Integer>> t = new TreeMap<>();
        for (int i = n; i < CORPUS.length(); i++) {
            t.computeIfAbsent(CORPUS.substring(i - n, i), k -> new TreeMap<>()).merge(CORPUS.charAt(i), 1, Integer::sum);
        }
        return t;
    }

    static double perplexity(Map<String, Map<Character, Integer>> t, int n, String text, int vocab) {
        double bits = 0;
        for (int i = n; i < text.length(); i++) {
            Map<Character, Integer> row = t.getOrDefault(text.substring(i - n, i), Map.of());
            int total = row.values().stream().mapToInt(Integer::intValue).sum();
            double p = (row.getOrDefault(text.charAt(i), 0) + 1.0) / (total + vocab);
            bits += -Math.log(p) / Math.log(2);
        }
        return Math.pow(2, bits / (text.length() - n));
    }

    public static void main(String[] args) {
        int vocab = (int) CORPUS.chars().distinct().count();
        System.out.println("V = " + vocab);
        var bi = build(1);
        var tri = build(2);
        for (String s : new String[] {"the cat sat on the mat.", "the dog saw a cat.", "a bird saw the dog."}) {
            System.out.println(String.format(Locale.ROOT, "%-26s bigram %.3f   trigram %.3f", "\"" + s + "\"",
                perplexity(bi, 1, s, vocab), perplexity(tri, 2, s, vocab)));
        }
    }
}

The program prints perplexities under both models for three sentences, the last containing pairs the corpus never had.

V = 15
"the cat sat on the mat."  bigram 4.554   trigram 4.287
"the dog saw a cat."       bigram 5.149   trigram 4.860
"a bird saw the dog."      bigram 7.068   trigram 6.674

Every sentence now has a finite perplexity, including a bird saw the dog., which contains pairs the corpus never had (7.068 for bigram, 6.674 for trigram).

The price is paid on familiar text. The first sentence rises from 2.308 to 4.554 for the bigram model and from 1.441 to 4.287 for the trigram model. With only 15 symbols and rows of 1 to 30 observations, each added count takes a visible share of probability. The trigram model still wins over the bigram model on all three sentences.

Real systems use better smoothing methods. With neural models the issue disappears, because softmax never outputs exactly zero. The principle stays the same: reserve some probability for events not yet seen.

Example 11: why tables do not scale

Longer context helps, so why not use a very long one? A model with n symbols of context needs one row per possible context, and each row has V entries. So the table has V to the power n+1 cells. The size multiplies by V with every extra symbol of context.

This program prints the cell counts for characters (V = 27: letters and a space) and for a real token vocabulary (V = 100,000) as the context grows. It compares them to 10^80, the order of magnitude often quoted as an estimate of the number of atoms in the observable universe.

import java.math.BigInteger;

public class TableSize {
    public static void main(String[] args) {
        System.out.println("context  V=27 (characters)             V=100000 (tokens)");
        for (int n : new int[] {1, 2, 4, 8, 16, 32, 64}) {
            BigInteger chars = BigInteger.valueOf(27).pow(n + 1);
            BigInteger tokens = BigInteger.valueOf(100_000).pow(n + 1);
            System.out.println(String.format("%7d  %-30s %s", n, compact(chars), compact(tokens)));
        }
        System.out.println("atoms in the observable universe (estimate): about 10^80");
    }

    static String compact(BigInteger v) {
        String s = v.toString();
        if (s.length() <= 12) return s;
        return s.charAt(0) + "." + s.substring(1, 3) + " x 10^" + (s.length() - 1);
    }
}

The program prints one row per context length, with a compact form of each huge number.

context  V=27 (characters)             V=100000 (tokens)
      1  729                            10000000000
      2  19683                          1.00 x 10^15
      4  14348907                       1.00 x 10^25
      8  7.62 x 10^12                   1.00 x 10^45
     16  2.15 x 10^24                   1.00 x 10^85
     32  1.71 x 10^47                   1.00 x 10^165
     64  1.09 x 10^93                   1.00 x 10^325
atoms in the observable universe (estimate): about 10^80

With a vocabulary of 27 characters and a context of 8, the table already has 7.62 x 10^12 cells. With a vocabulary of 100,000 tokens, 4 symbols of context need 10^25 cells and 16 symbols need 10^85 cells. That is more than the estimated number of atoms in the observable universe.

Even if memory were free, no corpus contains enough text to count most of those contexts. Nearly every long context is new. A model must therefore share what it learns between similar contexts. A neural network does this by computing the scores from the context with a fixed set of weights.

Example 12: a model as a function

A table stores one row per context. A model instead computes the row from the context with a function that has adjustable numbers. These numbers are called parameters or weights.

The function's output is a list of logits: one raw score per vocabulary entry. A higher score means more likely, and a score can be any real number, including a negative one. Softmax turns logits into probabilities that sum to 1:

p_i = exp(z_i) / sum_j exp(z_j)

A hand-sized case: logits 0 and 0 give exp(0) = 1 for each, so each probability is 1/2. Logits 1 and 0 give 2.718 and 1, so the probabilities are 0.731 and 0.269. A higher logit gets a larger share, and the shares always add up to 1.

The program uses a 4-word vocabulary and a hand-set 2-number "meaning" per word. That meaning is an embedding: a list of numbers that stands for a word. Multiplying the embedding by a second matrix U gives logits. Lesson 8 explains these operations in full.

import java.util.Locale;

public class FunctionModel {
    static final String[] VOCAB = {"the", "cat", "sat", "mat"};
    // E: one 2-number vector per word. U: turns a 2-number vector into 4 logits.
    static final double[][] E = {{1, 0}, {0, 1}, {-1, 0}, {-1, -1}};
    static final double[][] U = {{-3, 2, 0, 2}, {0, -1, 3, -2}};

    static double[] logits(int context) {
        double[] z = new double[4];
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 2; k++) z[j] += E[context][k] * U[k][j];
        }
        return z;
    }

    static double[] softmax(double[] z) {
        double sum = 0;
        double[] p = new double[z.length];
        for (int i = 0; i < z.length; i++) { p[i] = Math.exp(z[i]); sum += p[i]; }
        for (int i = 0; i < z.length; i++) p[i] /= sum;
        return p;
    }

    public static void main(String[] args) {
        for (int c = 0; c < 4; c++) {
            double[] z = logits(c);
            double[] p = softmax(z);
            StringBuilder sb = new StringBuilder(String.format("after %-3s logits", VOCAB[c]));
            for (double v : z) sb.append(String.format(Locale.ROOT, " %5.1f", v));
            sb.append("  probs");
            for (double v : p) sb.append(String.format(Locale.ROOT, " %.3f", v));
            System.out.println(sb);
        }
        long v = 50_000, d = 256;
        System.out.println("full table, V=50000: " + v * v + " numbers");
        System.out.println("embedding + output matrix, d=256: " + 2 * v * d + " numbers");
    }
}

For each of the four words, the program prints the four logits and the four probabilities. It ends with two lines comparing the size of a full table with the size of this design.

after the logits  -3.0   2.0   0.0   2.0  probs 0.003 0.467 0.063 0.467
after cat logits   0.0  -1.0   3.0  -2.0  probs 0.046 0.017 0.930 0.006
after sat logits   3.0  -2.0   0.0  -2.0  probs 0.941 0.006 0.047 0.006
after mat logits   3.0  -1.0  -3.0   0.0  probs 0.934 0.017 0.002 0.047
full table, V=50000: 2500000000 numbers
embedding + output matrix, d=256: 25600000 numbers

The E matrix gives each word two numbers, and U converts two numbers into four logits. The row for the shows logits 2.0 for cat and mat and a very low -3.0 for the itself. The probabilities are 0.467 for cat, 0.467 for mat, and 0.003 for the, so after "the" a noun follows. After cat the model puts 0.930 on sat, and after sat or mat it puts 0.941 or 0.934 on the.

Nobody counted anything. The weights were set by hand to produce these preferences, and a model could instead learn them. The function has only 16 numbers here, as many as a 4 by 4 table. For V = 50,000 and d = 256, however, it has 25.6 million numbers instead of 2.5 billion.

Real models go much further. The embedding is only the first step, and many layers of computation (lessons 9 and 10) turn the whole context into the vector that U converts to logits.

Example 13: training by gradient descent

If the weights are not set by hand, how are they found? Training is the search for weights that make the corpus likely. The measure to lower is the loss: the average cross-entropy of the actual next symbols under the model. This program measures it in nats, which means it uses the natural logarithm instead of base 2.

Gradient descent lowers the loss with repeated small steps. Picture standing on a hill in fog and wanting to reach the valley. You feel which direction slopes downward and take a small step that way. In each step the program does two things:

1. It computes, for every weight, how much the loss rises if the weight rises. This is the gradient.
2. It moves the weight a small distance in the opposite direction. The size of that distance is the learning rate.

The analogy fits the idea of following the slope. It differs from the real thing in that the "hill" here has thousands of directions, one per weight, not two.

For a table of logits followed by softmax, the gradient of the loss with respect to the logit of symbol k in the row of context c is (p_k - target_k). It is summed over the training pairs that start with c. The target_k is 1 for the symbol that actually came next and 0 otherwise. In words: if the model gives too much probability to a symbol, its logit is pushed down. If it gives too little to the symbol that really came next, its logit is pushed up.

The program starts with all logits at 0, so every symbol is equally likely. It trains, and then compares the result to the counted probabilities from Example 3.

import java.util.Locale;
import java.util.TreeSet;

public class TrainBigram {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        String chars = CORPUS.chars().sorted().distinct().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
        int v = chars.length();
        int n = CORPUS.length() - 1;
        double[][] counts = new double[v][v];
        for (int i = 0; i < n; i++) counts[chars.indexOf(CORPUS.charAt(i))][chars.indexOf(CORPUS.charAt(i + 1))]++;

        double[][] logits = new double[v][v];
        double learningRate = 10.0;
        for (int step = 0; step <= 3000; step++) {
            double loss = 0;
            double[][] grad = new double[v][v];
            for (int c = 0; c < v; c++) {
                double[] p = softmax(logits[c]);
                double rowTotal = 0;
                for (int k = 0; k < v; k++) rowTotal += counts[c][k];
                for (int k = 0; k < v; k++) {
                    grad[c][k] = (p[k] * rowTotal - counts[c][k]) / n;
                    if (counts[c][k] > 0) loss -= counts[c][k] * Math.log(p[k]) / n;
                }
            }
            if (step == 0 || step == 10 || step == 100 || step == 1000 || step == 3000) {
                System.out.println(String.format(Locale.ROOT, "step %4d  loss = %.4f  perplexity = %.3f", step, loss, Math.exp(loss)));
            }
            for (int c = 0; c < v; c++) for (int k = 0; k < v; k++) logits[c][k] -= learningRate * grad[c][k];
        }

        double maxDiff = 0;
        for (int c = 0; c < v; c++) {
            double[] p = softmax(logits[c]);
            double rowTotal = 0;
            for (int k = 0; k < v; k++) rowTotal += counts[c][k];
            for (int k = 0; k < v; k++) maxDiff = Math.max(maxDiff, Math.abs(p[k] - counts[c][k] / rowTotal));
        }
        System.out.println(String.format(Locale.ROOT, "largest gap between learned and counted probability: %.4f", maxDiff));
        int t = chars.indexOf('t');
        double[] row = softmax(logits[t]);
        for (int k = 0; k < v; k++) {
            if (counts[t][k] > 0) {
                System.out.println(String.format(Locale.ROOT, "P([%c] | [t]) learned %.4f, counted %.4f", chars.charAt(k), row[k], counts[t][k] / sum(counts[t])));
            }
        }
    }

    static double sum(double[] a) { double s = 0; for (double x : a) s += x; return s; }

    static double[] softmax(double[] z) {
        double max = Double.NEGATIVE_INFINITY;
        for (double x : z) max = Math.max(max, x);
        double s = 0;
        double[] p = new double[z.length];
        for (int i = 0; i < z.length; i++) { p[i] = Math.exp(z[i] - max); s += p[i]; }
        for (int i = 0; i < z.length; i++) p[i] /= s;
        return p;
    }
}

The program prints the loss at five points during training. Then it prints the largest gap between learned and counted probabilities, and three probabilities for the context t.

step    0  loss = 2.7081  perplexity = 15.000
step   10  loss = 1.2707  perplexity = 3.563
step  100  loss = 0.9266  perplexity = 2.526
step 1000  loss = 0.9016  perplexity = 2.464
step 3000  loss = 0.9000  perplexity = 2.460
largest gap between learned and counted probability: 0.0038
P([ ] | [t]) learned 0.3528, counted 0.3529
P([.] | [t]) learned 0.1763, counted 0.1765
P([h] | [t]) learned 0.4704, counted 0.4706

At step 0 all logits are 0, so every character has probability 1/15. The loss is ln 15 = 2.7081, and the perplexity is 15, which is no better than guessing. After 10 steps the loss drops to 1.2707, after 100 to 0.9266, and by step 3000 it settles at 0.9000 (perplexity 2.460).

That value is close to the loss of the counted bigram model in Example 14 (0.8992 nats), which is the lowest value this table can reach. Training stays slightly above it. The logits of characters that never follow a context can only be pushed down gradually, and they never reach probability 0.

The largest gap between a learned probability and a counted probability is 0.0038, and the three probabilities for t differ from the counted values by at most 0.0002. So gradient descent, which knows nothing about counting, finds the same distribution that counting gives.

The same loop trains a real model. The transformer takes the place of the logit table, and backpropagation computes the gradients. Backpropagation is the method that computes the gradient of every weight in a function made of many layers.

Example 14: how much each extra symbol of context helps

The last example puts the models side by side. For each context length n, the program builds the counted model from the corpus and measures its perplexity on the same corpus. A context length of 0 means no context, only the overall frequency of each character. The result is the lowest loss that a model of that shape can reach on this text. The uniform model, where every character is equally likely, is the starting point of training in Example 13.

import java.util.Locale;
import java.util.Map;
import java.util.TreeMap;

public class ContextLength {
    static final String CORPUS = "the cat sat on the mat. the dog sat on the log. "
        + "the cat saw the dog. the dog saw the cat. a cat and a dog sat on a mat.";

    public static void main(String[] args) {
        int vocab = (int) CORPUS.chars().distinct().count();
        System.out.println(String.format(Locale.ROOT, "uniform over %d characters: perplexity = %d", vocab, vocab));
        for (int n = 0; n <= 4; n++) {
            Map<String, Map<Character, Integer>> t = new TreeMap<>();
            for (int i = n; i < CORPUS.length(); i++) {
                t.computeIfAbsent(CORPUS.substring(i - n, i), k -> new TreeMap<>()).merge(CORPUS.charAt(i), 1, Integer::sum);
            }
            double nats = 0;
            for (int i = n; i < CORPUS.length(); i++) {
                Map<Character, Integer> row = t.get(CORPUS.substring(i - n, i));
                int total = row.values().stream().mapToInt(Integer::intValue).sum();
                nats -= Math.log((double) row.get(CORPUS.charAt(i)) / total);
            }
            double loss = nats / (CORPUS.length() - n);
            System.out.println(String.format(Locale.ROOT, "context %d: contexts seen = %2d, loss = %.4f nats, perplexity = %.3f",
                n, t.size(), loss, Math.exp(loss)));
        }
    }
}

The program prints one line for the uniform model and one for each context length from 0 to 4.

uniform over 15 characters: perplexity = 15
context 0: contexts seen =  1, loss = 2.3692 nats, perplexity = 10.689
context 1: contexts seen = 15, loss = 0.8992 nats, perplexity = 2.458
context 2: contexts seen = 31, loss = 0.3271 nats, perplexity = 1.387
context 3: contexts seen = 44, loss = 0.2635 nats, perplexity = 1.301
context 4: contexts seen = 56, loss = 0.2004 nats, perplexity = 1.222

The uniform model has perplexity 15 and the unigram model (context 0) has 10.689, because the character frequencies are uneven. One character of context lowers it to 2.458, two to 1.387, four to 1.222. The number of contexts the model must remember grows at the same time, from 15 to 31 to 56.

The curve is the trade-off of the whole field in one table: more context gives lower loss, and a table pays for it with storage and unseen cases. A perplexity near 1.2 here also reflects memorization. The model has seen every context in the corpus, so a low number on its own training text says little about new text, as Example 9 showed.

From this table to a real language model

Every part of the toy has a counterpart in a real model. The differences are in scale and in how the next-symbol scores are computed.

Two facts from the examples carry over without change. First, the model's whole output is a distribution over the next symbol, and everything an assistant does (answers, code, tool calls) is that distribution sampled one token at a time. Second, training makes the observed text likely, which is why a model repeats the habits of its training text.

Interview points

• A language model maps a context to a probability distribution over the next token. Generation samples from it, appends the result, and repeats.
• The chain rule factors a sequence probability into per-token conditional probabilities. Adding log probabilities instead of multiplying avoids floating-point underflow on long sequences.
• Cross-entropy is the average of -log p(actual token). Perplexity is its exponential, read as the effective number of equally likely choices per step.
• A model with perplexity equal to the vocabulary size is no better than uniform guessing.
• A count-based n-gram model needs V^(n+1) cells, so it cannot reach long contexts. Unseen contexts get zero probability unless smoothing is used.
• Add-one smoothing adds 1 to every count and V to the row total, so unseen pairs get a small positive probability and rows still sum to 1.
• A neural model computes logits with shared weights instead of storing a row per context, so it generalizes to contexts it never saw.
• With softmax, the gradient of cross-entropy with respect to a logit is the predicted probability minus the target (1 or 0).
• Training with gradient descent on a bigram logit table converges to the counted probabilities, which are the maximum-likelihood solution.
• Greedy decoding of a bigram model falls into loops because the most likely transition from a symbol always leads to the same next symbol. Larger models can also loop on repeated phrases.
• A sampled model with a fixed seed is reproducible. The same code with a different seed gives a different text.

Summary

• A language model is a function from a context to a probability distribution over the vocabulary.
• The smallest language model is a table of bigram counts. Dividing each row by its total gives P(next | current).
• Greedy generation picks the highest-probability symbol and falls into repeating cycles. Sampling draws by probability and varies with the seed.
• P(sentence) is the product of conditional probabilities (chain rule). Logs turn the product into a sum and prevent underflow: 400 factors of 0.1 underflow to 0.0 in a double, while the log sum is -921.0.
• Cross-entropy in bits is -log2 p averaged over the text. Perplexity is 2^cross-entropy, or e^loss for natural logs.
• A longer context lowers training perplexity and raises the number of contexts that need counts. Unseen contexts have zero probability without smoothing.
• Add-one smoothing: (count + 1) / (total + V).
• A table of V^(n+1) cells is impossible beyond short contexts: with V = 100,000 and a context of 16 tokens it has about 10^85 cells.
• A neural model computes logits from the context with shared weights, and softmax converts logits to probabilities.
• A factored model with embedding dimension d stores 2 * V * d numbers instead of V * V: 25.6 million instead of 2.5 billion for V = 50,000, d = 256.
• Training lowers the average cross-entropy by gradient descent. The logit gradient for softmax with cross-entropy is p - target.
• A bigram logit table trained from zero converges to the counted probabilities, starting at perplexity V.