What "Generative" Means: Autoregression, the Chain Rule, and Perplexity

The series’ first models, from Learning Is Optimization on, were all discriminative: given an input, predict a label. The router reads a question and picks one of four routes. Sequences Before Attention’s character models already did something else, predicting the next character of the blog, and this post is about what that means. A generative model is different in what it learns. It learns a probability for the input itself: how likely is this whole piece of text? With that, it can score text, compare two continuations, or produce new text by drawing from the distribution.

For text there’s one standard way to build that probability, and this post is about taking it seriously. Everything a language model does, how it’s trained, how it writes, why it needs a KV cache, how it’s evaluated, falls out of a single line of probability.

Table of contents

One line of probability

The chain rule of probability says that any joint probability splits into a product of conditional ones. For a sequence of tokens $x_1, \dots, x_T$:

This isn’t an assumption about language; it’s always true. What a language model does is learn one function that predicts the next token’s distribution from the ones before it, and use it for every factor. That’s an autoregressive model: each value is predicted from the sequence’s own earlier values. (In practice the first factor is $p(x_1 \mid \text{start})$, conditioned on a special beginning-of-text token, and a complete text ends with an end-of-text token whose probability is a factor too. Without it, the product is the probability that a text begins this way.)

The simplest model that obeys it is a bigram model, which pretends the next character depends only on the one before it. Counted on the blog:

import math
from collections import Counter

# The chain rule, with the simplest model that obeys it: each character's
# probability given only the one before it (a bigram model), counted on the
# blog's training text with add-one smoothing.
train, val = open("blog_train.txt").read(), open("blog_val.txt").read()
V = len(set(train)) + 1
first, pair = Counter(train), Counter(train[i:i + 2] for i in range(len(train) - 1))
p = lambda c, prev: (pair[prev + c] + 1) / (first[prev] + V)

text = "the cache"
logp = math.log(first[text[0]] / len(train))
print(f"p('{text[0]}') = {math.exp(logp):.4f}")
for prev, c in zip(text, text[1:]):
    logp += math.log(p(c, prev))
    print(f"p('{c}' | '{prev}') = {p(c, prev):.4f}")
print(f"p('{text}') = product = {math.exp(logp):.3e};  -log2 p = {-logp / math.log(2):.1f} bits "
      f"for {len(text)} characters")

# Perplexity of the bigram model on the held-out posts.
nll = -sum(math.log(p(c, prev)) for prev, c in zip(val, val[1:])) / (len(val) - 1)
print(f"bigram model on held-out posts: {nll:.3f} nats per character, perplexity {math.exp(nll):.1f}, "
      f"{nll / math.log(2):.3f} bits per character")

Full script: bigram.py

p('t') = 0.0635
p('h' | 't') = 0.2066
p('e' | 'h') = 0.4248
p(' ' | 'e') = 0.2166
p('c' | ' ') = 0.0259
p('a' | 'c') = 0.1363
p('c' | 'a') = 0.0674
p('h' | 'c') = 0.1844
p('e' | 'h') = 0.4248
p('the cache') = product = 2.250e-08;  -log2 p = 25.4 bits for 9 characters
bigram model on held-out posts: 2.849 nats per character, perplexity 17.3, 4.110 bits per character

Nine small probabilities multiply to $2.3 \times 10^{-8}$. Real texts are long, so their probabilities underflow any number format (see PyTorch from the Inside), which is why models work with log-probabilities and sums instead: 25.4 bits for these nine characters. The negative log-probability of a text is, to within a couple of bits, the size a compressor built on the model would need to store it, by arithmetic coding (Shannon; entropy as in Cross-Entropy and the Softmax Gradient), as long as the model gives every possible text some probability. That’s why language modeling and compression are the same problem, and why this post will compare the models with ordinary compressors.

The same idea scores continuations. To ask how likely an answer $y$ is after a prompt $x$, a model computes $\log p_\theta(y \mid x) = \sum_t \log p_\theta(y_t \mid x, y_{<t})$, the chain rule over the answer only, not the joint probability of prompt and answer together. That’s how multiple-choice benchmarks are commonly scored (Evaluating LLMs covers benchmarks).

Training: teacher forcing

Training maximizes the probability of the training text, which, by the chain rule, means minimizing the sum of $-\log p(x_t \mid x_{<t})$ over every position: the cross-entropy of Cross-Entropy and the Softmax Gradient, once per token. Crucially, every factor conditions on the true previous tokens, which are all known in advance. So a model can compute all $T$ predictions for a training sequence at once, in one forward pass, with the target at each position being the next true token. That’s teacher forcing, and it’s what lm.py does. Its train() draws random windows of the training text and scores every position of each window in one forward pass:

def train(kind, seed, steps=3000, B=64, T=128, checkpoints=()):
    """Returns the model and, at each checkpoint, validation bits per byte."""
    vocab, tr, va = build(kind)
    n_bytes, seen = len(val_text.encode("utf-8")), {}
    torch.manual_seed(seed)
    model, g = LSTMLM(len(vocab) + 1), torch.Generator().manual_seed(seed)
    opt = torch.optim.AdamW(model.parameters(), lr=2e-3, weight_decay=0.0)
    for step in range(1, steps + 1):
        i = torch.randint(0, len(tr) - T - 1, (B,), generator=g)
        x = torch.stack([tr[j:j + T] for j in i]); y = torch.stack([tr[j + 1:j + T + 1] for j in i])
        logits, _ = model(x)                                  # teacher forcing: every position at once
        loss = torch.nn.functional.cross_entropy(logits.reshape(-1, logits.shape[-1]), y.reshape(-1))
        opt.zero_grad(); loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step()
        if step in checkpoints:
            seen[step] = total_nats(model, va) / math.log(2) / n_bytes
    return model, vocab, va, seen

Full script: lm.py

The rest of lm.py trains the byte-level BPE tokenizer, defines the model (an embedding, one LSTM layer of 256 units, and an output layer), and scores held-out text with total_nats(), carrying the LSTM’s state from one window to the next. python lm.py char 0 trains one model and prints its summary. In that summary, characters never seen in training share id 0, so the character model has 147 + 1 = 148 units; “unseen” is the share of held-out units that never occur in the training units; passes are steps × batch × window (3,000 × 64 × 128) divided by the number of training units; and perplexity per unit is the exponential of the held-out nats divided by the number of units predicted. Pooling unseen characters into one id means the score never charges for which unseen character comes next; at 0.2% of held-out characters, that barely moves the comparison.

For an RNN (Sequences Before Attention) the forward pass is still serial inside, one step per position. For a Transformer it’s truly parallel: every position is computed at once, as matrix multiplications, and that’s the main reason Transformers train so much faster on a GPU.

Trained on the blog, one model over characters and one over byte-level BPE tokens, two seeds each. On an Apple M4 laptop’s CPU, the post’s scripts, these four training runs included, take about 22 minutes. The BPE tokenizer is trained on the training posts alone, the method of Byte-Pair Encoding, with all 256 bytes in its vocabulary, so held-out text is always written in tokens the model has seen: only 0.6% of the held-out tokens, and 0.2% of the held-out characters, never occur in training. (A tokenizer trained elsewhere, like GPT-4o’s, would cut these posts into many tokens that 600,000 characters of training text never show the model, and the comparison would mostly measure that.) train_all.py runs lm.py for each unit and seed:

Full script: train_all.py

char seed 0: 148 units, 377,236 parameters, 1.01 bytes per unit, 0.2% of held-out units unseen in training; at 3,000 steps (41 passes) perplexity 6.4 per unit
      validation bits per byte at 250 / 500 / 1,000 / 2,000 / 3,000 steps: 3.311 / 2.973 / 2.737 / 2.621 / 2.657
char seed 1: 148 units, 377,236 parameters, 1.01 bytes per unit, 0.2% of held-out units unseen in training; at 3,000 steps (41 passes) perplexity 6.4 per unit
      validation bits per byte at 250 / 500 / 1,000 / 2,000 / 3,000 steps: 3.297 / 2.967 / 2.741 / 2.647 / 2.659
bpe  seed 0: 2,048 units, 987,136 parameters, 2.56 bytes per unit, 0.6% of held-out units unseen in training; at 3,000 steps (113 passes) perplexity 261.5 per unit
      validation bits per byte at 250 / 500 / 1,000 / 2,000 / 3,000 steps: 2.912 / 2.730 / 2.692 / 2.853 / 3.133
bpe  seed 1: 2,048 units, 987,136 parameters, 2.56 bytes per unit, 0.6% of held-out units unseen in training; at 3,000 steps (113 passes) perplexity 268.9 per unit
      validation bits per byte at 250 / 500 / 1,000 / 2,000 / 3,000 steps: 2.903 / 2.728 / 2.690 / 2.865 / 3.148

The validation numbers are printed at five points during training, in bits per byte, which the last section explains; lower is better.

• Both models overfit. The character model is best at 2,000 steps (2.62–2.65) and slightly worse at 3,000 (2.66). The BPE model is best at 1,000 steps (2.69) and much worse by 3,000 (3.13–3.15). A BPE step covers 2.5 times as much text, so in passes over the training text the two peaks are closer than they look, about 28 passes for the characters and 38 for the tokens, though checkpoints this coarse only place each peak within a factor of two. The BPE model also has 2.6 times the parameters, most of them in its 2,048-row embedding and output layers, which is why it overfits harder.
• At their best, characters win slightly. 2.62–2.65 bits per byte against 2.69. The BPE model’s training windows are also longer, 128 tokens of about 2.6 bytes each against 128 characters, so its small loss isn’t for lack of context. Both numbers are the best of five checkpoints on the very text they’re scored on, so they’re optimistic; the fair comparison is at the fixed 3,000 steps, 2.66 against 3.14, and there the character model is clearly ahead. On this little text, a model with fewer, smaller choices overfits less.

Generation: the factorization run forward

To write, run the chain rule forward: predict the next token’s distribution, choose a token from it, append it, and repeat, each step conditioning on everything so far, including what the model itself just wrote. generate.py loads the character model that lm.py char 0 saved (char_lstm.pt) and runs it forward from a prompt:

@torch.no_grad()
def generate(prompt, n, greedy, seed=0):
    g = torch.Generator().manual_seed(seed)
    logits, state = model(torch.tensor([[index[c] for c in prompt]]))
    out = []
    for _ in range(n):
        p = torch.softmax(logits[0, -1], -1)
        nxt = p.argmax() if greedy else torch.multinomial(p, 1, generator=g)[0]
        out.append(vocab[nxt - 1] if nxt > 0 else "?")
        logits, state = model(nxt.view(1, 1), state)       # feed its own output back in
    return "".join(out)

prompt = "The KV cache "
print(f"greedy:  {prompt}{generate(prompt, 200, greedy=True)!r}")
print(f"sampled: {prompt}{generate(prompt, 200, greedy=False)!r}")

Full script: generate.py

The same script then times three ways through 512 characters, the median of seven runs each: scoring known text in one call (teacher forcing), feeding the same known text one call per character, and generating.

greedy:  The KV cache 'post costs a settings of the same post is the same post is the same post is the same post is the same post is the same post is the same post 2.1 on the same post 2.1 found the same post 2.1 on the sam'
sampled: The KV cache 'han the routure model. Write at it\n*sort** (Zheng](hts forkens only a\nmeany sublay.\n- Imm and generated units including token\n  to best process to the graming story, and every step. The loss over\n  us'
512 characters: teacher forcing 5.9 ms; the same known characters one call at a time 16.4 ms; generating 19.2 ms

• Greedy decoding always takes the most probable character, and falls into a loop within a few words: “the same post is the same post is…”. The loop isn’t a failure to find better text: beam search, which searches harder for the most probable continuation, repeats even more (Holtzman et al., 2020). Repetitive text is simply high-probability under the model, and each repetition makes the next more likely.
• Sampling draws from the distribution instead. It escapes the loop and writes something with the blog’s texture: Markdown, citations, words like “token” and “every step”. It’s still gibberish, because this is a small character model trained on 600,000 characters.
• Generation is serial; scoring doesn’t have to be. Scoring 512 known characters in one call took 5.9 ms. Generating 512 took 19.2 ms, but feeding the same known characters one call at a time takes nearly as long, 16.4 ms. For an LSTM both are serial inside, so most of the gap is the cost of 512 calls instead of one, not the dependence on its own output. A Transformer is where the dependence bites: with teacher forcing it computes all positions at once, in parallel, while generation still has to wait for each token before it can compute the next. That’s the defining cost of serving.

Two consequences follow from generating one token at a time.

• Exposure bias. In training, the model only ever sees true previous tokens. In generation, it conditions on its own outputs, including its mistakes, a situation it never trained on (Bengio et al., 2015). A small early error can push it somewhere it has never been, one reason long samples drift off topic. How much it matters in practice is debated.
• The cost grows with length. A Transformer that recomputed the keys and values of the whole prefix for every new token would do $1 + 2 + \cdots + S$ times the work of one token, which grows as $S^2$ (here $S$ is the number of tokens in context, as in AI Engineering, from the Inside). Caching each token’s keys and values once, the KV cache (The KV Cache), removes that recomputation; attention still reads the whole cache at each step. An RNN doesn’t need a cache at all, because its whole past is already squeezed into one state, the trade-off Sequences Before Attention described.

How to choose the next token well, temperature, top-k, top-p, and beyond, is Decoding.

Perplexity, and why it depends on the tokenizer

Cross-Entropy and the Softmax Gradient defined perplexity as $e^{\text{cross-entropy}}$: the loss turned back into “as unsure as choosing among this many equally likely options”. For a language model it’s measured per token on held-out text:

The catch is the word token. A character model and a BPE model on the same text make very different numbers of predictions, and each prediction is a different kind of choice, so their perplexities measure different things. The character model’s perplexity at 3,000 steps is 6.4: at each character, it’s as unsure as a choice among six. The BPE model’s is 262–269 per token. That doesn’t mean it’s forty times worse; a token covers 2.56 bytes and is one of 2,048 possibilities, so each of its predictions is a bigger decision. The two numbers can’t be compared directly. They do convert, though, through the text: per-token perplexity is $2^{\text{bits per byte} \times \text{bytes per token}}$. At 3,000 steps the BPE model needs 3.13 bits per byte, and $2^{3.13 \times 2.56} \approx 260$. The character model, at 2.66 bits per byte, would score $2^{2.66 \times 2.56} \approx 110$ over the same 2.56 bytes: the BPE model really is worse at this checkpoint, by less than the raw perplexities suggest.

The fix is to divide by something both models share: the text itself. Bits per byte is the total number of bits the model needs for the held-out text, divided by the text’s length in UTF-8 bytes:

It doesn’t care how the text was cut into tokens, so it compares any two models, including ones with different tokenizers, on the same text (it’s the standard measure on the Pile, Gao et al., 2020). Neither number compares across test sets: a model scores differently on different text, and these two posts are not the blog as a whole. Bits per byte is also a compression rate, so it can be put on one ladder with models that aren’t neural at all:

# Baselines for "bits per byte" on the held-out posts, from knowing nothing
# to general-purpose compressors that are allowed to read the training posts.
train, val = open("blog_train.txt").read(), open("blog_val.txt").read()
tb, vb = train.encode(), val.encode()
n = len(vb)
print(f"raw UTF-8 bytes:                         {8.0:.2f} bits per byte")
V = len(set(train)) + 1
print(f"uniform guess over {V} characters:        {math.log2(V) * len(val) / n:.2f}")
freq = Counter(train)
uni = -sum(math.log2((freq[c] + 1) / (len(train) + V)) for c in val) / n
print(f"unigram character counts:                {uni:.2f}")
for name, f in [("zlib -9", lambda b: zlib.compress(b, 9)), ("bz2 -9", lambda b: bz2.compress(b, 9)),
                ("xz -9e", lambda b: lzma.compress(b, preset=9 | lzma.PRESET_EXTREME))]:
    alone = 8 * len(f(vb)) / n
    given = 8 * (len(f(tb + vb)) - len(f(tb))) / n       # extra bytes to add the held-out posts
    print(f"{name:8s} on the held-out posts alone {alone:.2f}; given the training posts {given:.2f}")

Full script: baselines.py

raw UTF-8 bytes:                         8.00 bits per byte
uniform guess over 148 characters:        7.13
unigram character counts:                4.95
zlib -9  on the held-out posts alone 3.15; given the training posts 3.03
bz2 -9   on the held-out posts alone 2.87; given the training posts 2.34
xz -9e   on the held-out posts alone 2.95; given the training posts 2.44

Storing the text as is costs 8 bits per byte, and a uniform guess over the blog’s characters about 7.1. Counting single characters gets to 4.95. The count models of Sequences Before Attention, converted from bits per character (this text has 0.99 characters per byte): the bigram model 4.07, add-one smoothing’s best 3.54, and Kneser–Ney’s best 2.57. The LSTMs reach 2.62–2.66, behind the Kneser–Ney counts. And then the uncomfortable line: bz2, a general-purpose compressor from the 1990s, given the training posts to read first, needs only 2.34 bits per byte, and xz 2.44. Both beat the LSTM. These posts repeat phrases, headings and code from the training posts word for word, and a compressor can copy long stretches exactly, while a small LSTM with a 256-number state can only predict one character at a time from what it remembers. Copying from context is exactly what attention can do, and it’s what the model of Build a Tiny GPT, End to End, and Train It on This Blog has to learn.

Where this leads

• Byte-Pair Encoding is where the tokens come from, and what a tokenizer costs different languages.
• The Transformer’s Three Attention Patterns builds attention, and Build a Tiny GPT, End to End, and Train It on This Blog trains a tiny GPT on this blog, scored in bits per byte on the same two held-out posts, so it can be compared directly with these LSTMs.
• Decoding covers temperature, top-k and top-p sampling, beam search, and the other ways to choose a token from the distribution.
• vLLM Architecture and Speculative Decoding, Derived come back to generation’s serial cost, and the tricks (batching, speculative decoding) that work around it.

Takeaways

• A language model is the chain rule: the probability of a text is the product of each token’s probability given everything before it.
• Training minimizes the cross-entropy of every next token given the true previous ones (teacher forcing), so a whole sequence is one parallel pass. Generation conditions on the model’s own outputs, one token at a time.
• Greedy decoding degenerates into loops; sampling doesn’t, but a small model’s samples are fluent-looking nonsense.
• Exposure bias: a model trained only on true prefixes is tested on its own.
• Without caching, recomputing the prefix’s keys and values makes a Transformer’s generation cost grow as $S^2$; the KV cache computes each once.
• Perplexity is per token, so it depends on the tokenizer. Bits per byte divides by the text instead and compares any two models on the same text. Per-token perplexities convert to it through bytes per token.
• On this blog, a character model beat a BPE model at a fixed step count (2.66 against 3.14 bits per byte), and both overfit; well-smoothed character counts (2.57) and a stock compressor that can copy from the training posts (2.34) beat both.

References

Start with Shannon’s 1951 paper, a short and readable experiment on how predictable English is. Then read Holtzman et al. on why greedy decoding degenerates. The Pile paper explains why bits per byte is the measure to compare across tokenizers.

• Shannon, A Mathematical Theory of Communication (1948): n-gram models of English, and entropy as bits per symbol.
• Shannon, Prediction and Entropy of Printed English (Bell System Technical Journal, 1951): measuring how predictable text is, in bits per character.
• Bengio, Ducharme, Vincent and Jauvin, A Neural Probabilistic Language Model (JMLR, 2003): neural next-word prediction with learned embeddings.
• Radford et al. (OpenAI), Language Models are Unsupervised Multitask Learners (2019): GPT-2’s byte-level BPE, and scoring any benchmark by dividing total log-probability by the dataset’s own units.
• Gao et al., The Pile: An 800GB Dataset of Diverse Text for Language Modeling (2020): bits per byte as a tokenizer-independent measure.
• Holtzman, Buys, Du, Forbes and Choi, The Curious Case of Neural Text Degeneration (ICLR, 2020): why greedy and beam decoding repeat.
• Bengio, Vinyals, Jaitly and Shazeer, Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks (NeurIPS, 2015): exposure bias, and one way to train against it.