Autoregressive Generation

A next-token model predicts one step ahead. To produce a response, we choose a token, append it to the existing text, and ask the model to predict again with that new context.

10 sections · 9 questions · 4 coding challenges

1 / 10

The arrow keys move between sections too.

How Does One Prediction Become a Whole Passage?

BOTIE

A model that predicts the next token produces only one distribution at a time. To write a passage, we need to decide what happens after that prediction. The token we select becomes part of the context for the following decision.

Autoregressive sequence modelling predates today's large language models. GPT-2, described by Radford and colleagues in 2019, is a familiar application: a Transformer language model trained to predict text from its preceding context could continue supplied passages and perform tasks expressed through that context.

Generation repeats a short procedure. Read the available context, calculate next-token probabilities, choose a token, append it, and continue until a stopping condition is reached. Every choice changes the input to later predictions. This explains both the flexibility and a weakness of the procedure: an early mistake can become context that later tokens elaborate rather than correct.

Sources for this history

Radford and colleagues (2019), Language Models Are Unsupervised Multitask Learners

How Does One Predicted Token Become a Paragraph?

A next-token model gives us a distribution for one following token. A reader asking for a paragraph needs much more than one token. How do we turn that single prediction into a longer response?

We can repeat the operation. Select a token, add it to the text we already have, and ask the model for the next distribution. Each choice becomes part of the context for the choices that follow.

Start with the user's text

The prompt supplies the initial context. The tokenizer converts it into token IDs, and the model reads the whole available prefix. We use a short sentence here so the growing context is easy to follow.

Prefix

Next position

Illustrative starting context.

1 of 4

Follow the changing prefix, not changing weights

The full example runs this loop through the SDK's tiny untrained decoder and displays every prefix and selection probability.

Its incoherent output is useful here: the loop alone cannot supply learned language. Architecture, training, and token selection play different roles.

Part 1. Follow One Complete Loop

1. Read the prefix and select the next token

A next-token model answers one question, which is what token is likely to follow this text. A response is many tokens long. The loop in this part is how one answer at a time becomes a sequence, and following it once with real numbers shows everything it does.

Tokenize the prompt and run a forward pass. The final position's vocabulary scores describe what may follow the whole prefix. Convert them to a distribution, then apply the chosen selection rule.

The live example uses the seven-entry vocabulary from the previous lesson and the prompt <start> the cat. A forward pass returns a row of seven scores at each of the three positions. The first two rows are predictions about tokens the prompt already contains, so generation has no use for them. Only the last row, the one read after the whole prefix, is turned into a distribution.

candidate	probability after <start> the cat
<start>	0.1756
the	0.1208
cat	0.1815
dog	0.2334
sat	0.0395
slept	0.1728
<end>	0.0763

The decoder is untrained, so these shares say nothing about language. They are the distribution the loop has to choose from.

Greedy decoding selects a highest-probability token. Sampling draws according to the selection distribution. Both operate on a model prediction; neither modifies the learned parameters.

On this row greedy decoding takes dog, the largest share at 0.2334. Sampling draws one token with the seven shares as its odds. Dog is the likeliest single outcome, and it is still more likely than not that the draw lands somewhere else. With the default seed the draw happens to be dog as well.

2. Append, then predict with the new context

The selected ID is appended to the prefix before another forward pass. A later distribution depends on the earlier selections. The model does not first write a whole answer in a hidden buffer and reveal it one token at a time.

Autoregressive describes this dependence on earlier sequence elements. A token can be a word part, so a generated step need not correspond to a complete word.

Initial prefix:       the cat
Illustrative choice:  sat
Next prefix:          the cat sat
Next prediction:      distribution after the cat sat

The displayed continuation is an illustration of the loop. The live example uses an untrained decoder and can produce incoherent sequences.

The default run, one pass per row

With sampling, the default seed and five new tokens, the live example runs as follows. Each row is one forward pass, and each prefix is the previous prefix with the previous selection appended.

step	prefix read	selected token	selection probability
1	<start> the cat	dog	0.2334
2	<start> the cat dog	the	0.1179
3	<start> the cat dog the	<start>	0.2015
4	<start> the cat dog the <start>	<start>	0.0938
5	<start> the cat dog the <start> <start>	slept	0.2696

The start token is an ordinary vocabulary entry to this untrained decoder, so it can be selected again.

Now run the same prompt with greedy selection. Step 1 is identical, because dog is both the largest share and the token the default seed drew. At step 2 the distribution after <start> the cat dog gives dog the largest share again, 0.2388, and greedy decoding takes it, where the draw landed on the at 0.1179. From that point the two runs read different prefixes, so each later pass is answering a different question. The greedy run continues dog, slept, slept, with selection probabilities of 0.2450, 0.2495 and 0.3438.

Nothing about the model changed between the two runs or between any two steps. The parameters are fixed. The only thing that moves is the prefix, and one different selection at step 2 was enough to change every prefix after it.

Part 2. The Probability of a Sequence

3. Combine conditional predictions

A conditional probability describes a token given the prefix before it. The chain rule writes the probability of a whole continuation as a product of these next-token probabilities. Here x names tokens and T names the sequence length.

p(x₁, …, x_T) = ∏ₜ p(xₜ | x₁, …, xₜ₋₁)

For an illustrative two-token continuation:
p(sat | the cat) = 0.5
p(<end> | the cat sat) = 0.4

p(sat, <end> | the cat) = 0.5 × 0.4 = 0.2

These are assigned probabilities to expose the multiplication. If a sampler changes probabilities through temperature or filtering, the sampling policy's sequence probability uses those changed distributions.

The probability of each default run

The table in step 2 supplies real factors. Each selection probability there is the probability of that token given the prefix beside it, which is exactly the term the chain rule asks for. Multiply the five from the sampled run, and separately the five from the greedy run.

Sampled run:  0.2334 × 0.1179 × 0.2015 × 0.0938 × 0.2696 ≈ 0.000140
Greedy run:   0.2334 × 0.2388 × 0.2450 × 0.2495 × 0.3438 ≈ 0.001171

The factors shown are rounded and the products were calculated from the unrounded ones. Both products are small, and that is ordinary. Every factor is below one, so a sequence probability shrinks with each token, and a long sequence has a tiny probability even when every step was a likely one. Two sequences are compared fairly only at the same length. At five tokens the greedy run is roughly eight times as probable as the sampled one.

The caution about changed distributions applies as soon as a control moves. At a temperature of 0.5 the first distribution gives dog a share of 0.3202 in place of 0.2334. A run sampled at that temperature was drawn from the 0.3202 row, so that is the factor its probability under the sampling policy uses.

4. Understand why greedy choices are local

Choosing the largest probability at one step does not guarantee the highest-probability complete sequence. That choice also selects which future distributions become available. A locally less likely first token can lead to much more probable later tokens.

Where the greedy run is overtaken

Compare two continuations of four tokens from the same prompt. They share their first two selections and part at the third, where the distribution after <start> the cat dog dog gives dog a share of 0.2450 and <start> a share of 0.1921. Greedy decoding takes dog.

Greedy:       dog      dog      dog      slept
              0.2334 × 0.2388 × 0.2450 × 0.2495 ≈ 0.003405

Alternative:  dog      dog      <start>  slept
              0.2334 × 0.2388 × 0.1921 × 0.3835 ≈ 0.004104

Taking <start> at the third step gives up some probability there. The fourth step repays it. After the alternative prefix, slept has a share of 0.3835, and after the greedy prefix the best share on offer is 0.2495. The greedy rule never sees that trade, because at the third step it compares 0.2450 with 0.1921 and looks no further.

Seven candidates at each of four steps make 2,401 possible continuations. Scoring every one of them on this decoder puts the alternative first and the greedy continuation fourth. At two and at three tokens the greedy continuation is the most probable of all, so the gap opens only at the fourth step. A greedy choice can be the best one for a while and then stop being so.

Beam search keeps several partial sequences to explore this issue, but search and open-ended writing are different objectives. A more probable sequence is not necessarily a more useful response. The lesson's controls focus on greedy selection and sampling.

Part 3. Stop, Reproduce, and Inspect

5. Give the loop explicit limits

A loop that appends a token and predicts again has no natural end. Something has to say when the response is finished, and something else has to guarantee the loop halts when the first thing never happens.

The SDK stops at an optional end token, the requested number of new tokens, or its context bound. The end token is a model selection, so an untrained model may select it immediately or fail to select it. A length bound makes the loop finite regardless.

Four runs and how each one ended

All four runs start from the prompt <start> the cat and treat <end> as the end token. After the prompt its share is 0.0763, so a draw can select it at the very first step.

selection	new tokens requested	tokens selected	what stopped the loop
sampling, seed 0	5	dog the <start> <start> slept	the length bound
sampling, seed 1	5	dog <end>	the end token, at step 2
sampling, seed 4	5	<end>	the end token, at step 1
greedy	12	dog dog dog, then slept nine times	the length bound

Across the 101 seeds the control offers, at the default temperature, 25 runs of five new tokens stop early on the end token.

The seed 4 run produced a response with nothing in it, and the greedy run never selected the end token in the twelve steps the control allows, because <end> never held the largest share. Neither is a fault in the loop. An untrained model has not learned where a response should end, and the length bound is what keeps the second case finite.

The context bound is the third limit. It is the longest prefix the model can read. With that bound set to five tokens, the seed 0 run stops after two new tokens however many are requested, because the three prompt tokens and two selections fill it.

A fixed random seed reproduces sampling when model parameters, inputs, and selection settings are fixed. Greedy decoding does not use the seed. Different full-scale hardware and numerical implementations may need additional controls for reproducibility.

Both statements can be checked on the live example. Running the default settings twice gives the same five tokens both times. Greedy decoding gives dog, dog, dog, slept, slept whichever seed is set, because it never draws anything.

import numpy as np
from oop_ml.numpy.modern import CausalLanguageModel

model = CausalLanguageModel(n_vocab=7)
steps = model.generate(
    np.array([0, 1, 2]), max_new_tokens=5,
    seed=0, end_id=6,
)
for step in steps:
    print(step.context, step.token_id)

6. Recognize what an inference cache changes

This reference implementation recomputes the prefix on each step. A key/value cache can reuse attention keys and values from earlier positions, avoiding repeated work. It preserves information from earlier computation; it does not train the model or retrieve facts from an external database.

The table in step 2 shows how much is repeated. Its five passes read prefixes of three, four, five, six and seven tokens, and every pass starts again from the first token.

Positions read without a cache = 3 + 4 + 5 + 6 + 7 = 25
Distinct positions in the longest prefix read = 7

The reuse is safe because of the causal mask. A position reads only the tokens at or before it, so appending a token leaves the keys and values of every earlier position exactly as they were. Only the new position has to be computed. The selected tokens and their probabilities come out the same with or without a cache, and the gap between the two counts widens as the sequence grows.

Generation can continue an early mistake because that mistake becomes context. Inspect output for the task that matters rather than treating fluent continuation or a high selection probability as evidence of truth.

The default run shows the mechanism with no notion of truth involved. One unlikely draw at step 2, the at a share of 0.1179, changed every prefix after it, and no later step had a way to go back. A trained model is in the same position when an early token is wrong. It continues from what is there.

The paper describes an autoregressive model used through text prompts without parameter updates at inference time. Language Models are Few-Shot Learners.

Continue with Sampling and Temperature.