Lesson 4.2 · 27 min

Autoregressive Models: Predicting One Token at a Time

Why does ChatGPT type its answer one word at a time instead of showing the whole reply at once?

In short: An autoregressive model generates a sequence one piece at a time, and each new piece is predicted from all the pieces before it. The chain rule of probability says this is a complete way to describe any sequence, which is why GPT-style language models use it. It needs a causal mask during training, benefits hugely from a KV cache during generation, and is accurate but inherently sequential and therefore slow for long outputs.

What is an Autoregressive Model?

An autoregressive model produces a sequence step by step, where every new element is predicted from the elements it has already produced. The word comes from statistics: auto means “self” and regressive means “predicting a value from other values”. So: a model that predicts from its own earlier outputs.

The idea is older than deep learning. Classic time-series models, written AR(p), forecast tomorrow's temperature as a weighted sum of the last p days. Modern language models apply the same principle to tokens (words or word pieces): given “The cat”, predict the next token; append it; predict again.

Think of it like writing with a pen When we write a sentence by hand we cannot jump to the end first. We write a word, re-read what we have, and decide the next word. We never erase earlier words. An autoregressive model writes exactly like that: left to right, each choice based on everything already on the page.

Throughout this lesson we use a tiny vocabulary: <s> (start), the, cat, dog, sat, ran and </s> (end). Our toy model will generate short sentences such as “the cat sat”.

The Chain Rule of Probability

Why is predicting one token at a time a valid way to model language, and not just a convenient trick? Because of the chain rule of probability. It says that the probability of a whole sequence can always be written as a product of conditional probabilities, one per position:

So if a model can answer one question well, “given this prefix, how likely is each next token?”, it can describe the probability of any full sentence and generate sentences too. That is the entire job of a GPT-style model.

Small numbers. Suppose our model says P(the | <s>) = 1.0, P(cat | the) = 0.6, P(sat | cat) = 0.7 and P(</s> | sat) = 1.0. Then P(“the cat sat”) = 1.0 × 0.6 × 0.7 × 1.0 = 0.42. And P(“the dog ran”) = 1.0 × 0.4 × 0.8 × 1.0 = 0.32.

Pause and think: Using the same numbers plus P(ran | cat) = 0.3, what is P(“the cat ran”)? Do the four sentences the cat/dog sat/ran add up to 1?

P(the cat ran) = 1.0 × 0.6 × 0.3 × 1.0 = 0.18. With P(sat | dog) = 0.2, P(the dog sat) = 0.08. Total: 0.42 + 0.18 + 0.08 + 0.32 = 1.00. Because each step's probabilities sum to 1, the whole tree of sentences sums to 1 as well.

The Generation Loop

Generation turns the chain rule into a loop. The model never outputs a whole sentence; it outputs a probability distribution for one next token. A small piece of code around the model, the decoding loop, does the rest.

The pick step is called the decoding strategy. Greedy decoding always takes the top token: fast and repeatable, but it can be dull and can get stuck repeating phrases. Sampling picks randomly in proportion to the probabilities. Top-k keeps only the k most likely tokens before sampling, and top-p (nucleus sampling) keeps the smallest set whose probabilities add up to p. Beam search keeps several candidate sequences in parallel and is common in translation.

Step-by-Step Numeric Example in Code

Here is a complete autoregressive generator with a hand-written probability table. To keep it readable, our toy model only looks at the last token. A real LLM looks at the whole context, but the loop around it is identical.

autoregressive_toy.py

import numpy as np
vocab = ["<s>", "the", "cat", "dog", "sat", "ran", "</s>"]
ix = {w: i for i, w in enumerate(vocab)}
# A toy "model": P(next | last token). A real LLM conditions on ALL previous
# tokens, but the generation loop around it is exactly the same.
P = np.zeros((7, 7))
P[ix["<s>"],  [ix["the"]]]                = [1.0]
P[ix["the"],  [ix["cat"], ix["dog"]]]     = [0.6, 0.4]
P[ix["cat"],  [ix["sat"], ix["ran"]]]     = [0.7, 0.3]
P[ix["dog"],  [ix["sat"], ix["ran"]]]     = [0.2, 0.8]
P[ix["sat"],  [ix["</s>"]]]               = [1.0]
P[ix["ran"],  [ix["</s>"]]]               = [1.0]
# 1. Chain rule: P(sentence) = product of each next-token probability
def sentence_prob(words):
seq = ["<s>"] + words + ["</s>"]
p = 1.0
for prev, nxt in zip(seq, seq[1:]):
step = P[ix[prev], ix[nxt]]
print(f"  P({nxt:5s}| ...{prev:4s}) = {step:.1f}")
p *= step
return p
print("P('the cat sat') =", round(sentence_prob(["the", "cat", "sat"]), 3))
# 2. The generation loop: predict -> pick -> append -> repeat
def generate(greedy=True, seed=0):
rng = np.random.default_rng(seed)
seq = ["<s>"]
while seq[-1] != "</s>":
probs = P[ix[seq[-1]]]
nxt = probs.argmax() if greedy else rng.choice(7, p=probs)
seq.append(vocab[nxt])
return " ".join(seq[1:-1])
print("greedy :", generate(greedy=True))
print("sampled:", [generate(greedy=False, seed=s) for s in range(4)])

Output:

  P(the  | ...<s> ) = 1.0
P(cat  | ...the ) = 0.6
P(sat  | ...cat ) = 0.7
P(</s> | ...sat ) = 1.0
P('the cat sat') = 0.42
greedy : the cat sat
sampled: ['the cat sat', 'the dog sat', 'the cat ran', 'the cat ran']

Notice two things. First, greedy decoding returned “the cat sat”, the most likely sentence here, but greedy is not guaranteed to find the most likely sentence in general, because a low-probability early token can lead to very high-probability later tokens. Second, sampling produced “the cat ran” twice in four tries even though it has only an 18% chance: randomness is lumpy in small samples.

Why GPT-style Models are Autoregressive

GPT stands for Generative Pre-trained Transformer. It is trained on one objective: next-token prediction on huge amounts of text. That objective is exactly the chain rule, so the trained model is autoregressive by construction.

• Free labels: every position in every text is a training example (the label is simply the next token), so no human labelling is needed.
• One model, many tasks: answering, translating, summarising and coding can all be phrased as “continue this text”.
• Exact likelihood: we can compute how probable any text is, which makes training stable and evaluation easy.
• Natural streaming: tokens can be shown to the user as soon as they are produced.

A subtle but important point: training is parallel, generation is sequential. During training we already know the whole sentence, so we feed the true tokens in and ask the model to predict every next token at once. This is called teacher forcing. During generation we do not know the future, so we must produce one token, feed it back, and run again.

Pause and think: If training already predicts all positions in parallel, why can't generation do the same?

In training the inputs at each position are the real tokens from the data, which we have in advance. In generation, the input at position t+1 is the token the model has just chosen at position t, which does not exist until that step finishes. The dependency forces a sequential loop.

Why Autoregressive Models Need Causal Masking

A Transformer lets every token look at other tokens through attention. If, during teacher-forced training, the token at position 2 could look at position 3, it could simply read the answer it is supposed to predict. The model would learn to cheat and would be useless at generation time, when the future does not exist yet.

The fix is a causal mask: before the attention softmax, every score where a token would look at a later position is set to −∞. After softmax those weights become exactly 0. Each position can only use itself and the past, which matches the chain-rule term P(xₜ | x₍<t₎).

The Connection with KV Cache

Inside attention, each token is turned into a query, a key and a value vector. Because of the causal mask, the key and value of an earlier token never change when new tokens are appended: token 5 cannot see token 6, so its vectors are the same at step 6, 7, 8 and onward.

A naive loop would recompute keys and values for the whole prefix at every step, wasting work that grows with the square of the length. The KV cache stores each token's keys and values the first time they are computed. At each new step the model only computes the new token's query, key and value, appends the new key and value to the cache, and attends over the cache.

Generating with a KV cache

1. Prefill: Process the whole prompt in one parallel pass and store the keys and values of every prompt token in the cache, for every layer.
2. Decode one token: Feed only the newest token. Compute its query, key and value.
3. Append: Add the new key and value to the cache. The cache grows by one entry per layer.
4. Attend: Compare the new query against all cached keys and mix the cached values to get the output, then predict the next token.
5. Repeat: Loop until the end token. The cost per step stays roughly proportional to the context length instead of re-running the whole prefix.

The trade-off The KV cache trades memory for speed. For long contexts and many simultaneous users, the cache can take more GPU memory than the model weights, which is why techniques like grouped-query attention and paged attention exist (covered in later lessons).

Autoregressive vs Non-Autoregressive Generation

A non-autoregressive model produces many or all output tokens at the same time, without waiting for each previous token. The idea was studied heavily for machine translation from 2018 onward. Diffusion models, the leading approach for images, are another alternative: they start from noise and refine the whole output over a fixed number of steps. Researchers have also built diffusion-style text models, and some have been released, but as of 2026 the strongest general-purpose language models are still autoregressive.

Popular Autoregressive Models we should know

What varies by vendor Companies do not always publish architecture details for closed models. What is public and consistent is that these chat models produce text token by token, which is why responses stream.

Worked example, step by step

We said greedy decoding is not guaranteed to find the most likely sentence. Here is a case small enough to check by hand. We use a new toy model with two-word sentences (illustrative numbers). The first word is the (0.6) or a (0.4). After the comes cat (0.55) or dog (0.45). After a comes bird (0.9) or fish (0.1).

Greedy versus a wider search

1. Greedy, step 1: Greedy looks only at the first word. the has 0.6 and a has 0.4, so it commits to the. It can never undo this.
2. Greedy, step 2: After the, the best word is cat (0.55). Greedy returns “the cat” with probability 0.33.
3. The real winner: The table shows “a bird” has 0.36. It starts with the less likely first word, but the second word is almost certain, so the product ends up higher.
4. Beam search with 2 beams: Keep the two best prefixes instead of one: the (0.6) and a (0.4). Extend both and score all four sentences. Now “a bird” (0.36) is found.
5. The price: Two beams mean about twice the model work per step. And on real models beams can still miss the best sentence, because the tree is far too large to search fully.

The lesson: a choice that looks best right now can close off a better path later. This is why decoding is a search problem and not a simple lookup. It also shows that the most likely sentence and the most likely next token are different questions.

Most likely is not always best For chat, we usually do not want the single most likely text anyway. It tends to be short and bland. That is why sampling is the common default for open-ended writing, while greedy or beam search suits tasks with one right answer.

Practice: try it yourself

We will score two finished replies the way real systems do: with log probabilities instead of products. We will also see the exact moment a plain product breaks, and compute perplexity by hand.

practice_log_probs.py

import math
# Next-token probabilities a model gave at each step of two replies (illustrative)
fluent = [0.9, 0.6, 0.7, 0.8, 0.95]
odd = [0.9, 0.05, 0.3, 0.1, 0.95]
def score(step_probs):
# Chain rule in log space: add logs instead of multiplying probabilities
log_p = sum(math.log(p) for p in step_probs)
avg_nll = -log_p / len(step_probs)   # average negative log-likelihood
return log_p, math.exp(avg_nll)      # perplexity = exp(average NLL)
for name, probs in [("fluent", fluent), ("odd", odd)]:
log_p, ppl = score(probs)
print(f"{name:6s} P = {math.exp(log_p):.5f}  log P = {log_p:7.3f}  perplexity = {ppl:.2f}")
# Why logs? A long text multiplies many small numbers.
long_text = [0.1] * 400
product = 1.0
for p in long_text:
product *= p
print("product of 400 steps:", product)
print("sum of 400 log steps:", round(sum(math.log(p) for p in long_text), 1))
print("perplexity          :", round(score(long_text)[1], 2))

Output:

fluent P = 0.28728  log P =  -1.247  perplexity = 1.28
odd    P = 0.00128  log P =  -6.659  perplexity = 3.79
product of 400 steps: 0.0
sum of 400 log steps: -921.0
perplexity          : 10.0

Now change it:

• Change the 0.05 in odd to 0.5. Predict first: will the perplexity of odd fall below 2?
• Change [0.1] 400 to [0.1] 300. Predict: does the product still print 0.0, and does the perplexity change?
• Append one more 0.95 to fluent. Predict: does log P go up or down, and does perplexity go up or down?

Pause and think: The long text has 400 tokens and the fluent reply has 5, yet we can compare their perplexities (10.0 and 1.28). Why can we not compare their log P values (−921.0 and −1.247) in the same way?

log P is a sum over all steps, so it gets more negative as a text gets longer, even when every step is predicted well. Perplexity is built from the average per step, so length is divided out. To compare texts of different lengths we need the per-token view.

Pause and think: A perplexity of 10.0 came out for the text where every step had probability 0.1. Why exactly 10?

The average negative log-likelihood is −log(0.1) = log(10), and exp(log(10)) = 10. It matches the meaning of perplexity: the model is as unsure as if it picked evenly among 10 tokens at every step, and a probability of 0.1 is exactly a one-in-ten guess.

Pros, Cons and Quick Summary

• Pro – principled: the chain rule makes the model a complete probability distribution over sequences.
• Pro – simple, scalable training: next-token prediction on raw text, fully parallel thanks to teacher forcing and causal masks.
• Pro – flexible: any task that can be phrased as text continuation works.
• Con – latency: generation time grows with output length; each token waits for the previous one.
• Con – error accumulation: one bad token becomes part of the context and can steer the rest of the answer off course. Training only ever sees real prefixes, while generation sees the model's own, which is called exposure bias.
• Con – no going back: the model cannot edit what it already wrote, which is one reason “think step by step” prompting and reasoning tokens help.

Common misconception “The model plans the whole answer, then types it out slowly for effect.” No. Each token is a fresh prediction from the text so far. Streaming is not a show; the later words genuinely do not exist yet. (The model's internal states can still encode information about where the text is heading, but the output is committed one token at a time.)

Quick summary. Autoregressive models factor a sequence with the chain rule and generate it in a loop: predict, pick, append, repeat. Training is parallel with teacher forcing and a causal mask; generation is sequential and accelerated by a KV cache. This design powers essentially all popular LLMs today.

Key takeaways

• Autoregressive = each new token is predicted from all previous tokens, then fed back in.
• The chain rule makes this exact: P(sequence) = ∏ P(xₜ | x₍<t₎).
• Training is parallel (teacher forcing + causal mask); generation is a sequential predict–pick–append loop.
• The KV cache reuses unchanging keys and values of past tokens to make each step cheap.
• Strengths: simple objective, high quality, streaming. Weaknesses: latency and error accumulation.

Key terms

• Autoregressive model: A model that generates a sequence one element at a time, each conditioned on the elements before it.
• Chain rule of probability: The identity that a joint probability equals the product of each element's probability given the previous ones.
• Teacher forcing: Training by feeding the true previous tokens as input and predicting every next token in parallel.
• Causal mask: A mask that blocks attention to future positions so each token only uses itself and the past.
• KV cache: Stored keys and values of already-processed tokens, reused at each generation step.
• Greedy decoding: Always picking the most probable next token.
• Exposure bias: The gap between training on true prefixes and generating from the model's own, possibly flawed, prefixes.

← 4.1 Generative AI: Creating Instead of Classifying · 4.3 BPE Tokenization: How LLMs Split Text into Tokens →