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.

13 sections · 9 questions · 4 coding challenges

1 / 13

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.

Step 1 of 4

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

Position 1the
Position 2cat

Next position

Illustrative starting context.

Step 2 of 4

Choose from the first distribution

The model produces possible next tokens and their probabilities. A selection rule chooses one. Always selecting the largest probability is called greedy decoding; sampling instead makes a random choice according to the distribution.

Candidates

Position 1sat (highlighted)
Position 2slept
Position 3ran

Selected

sat

The choice shown here is illustrative, not a trained model result.

Step 3 of 4

Make the selected token part of the input

Now the prefix includes sat. The next forward pass therefore answers a different question: what follows this longer prefix? The model does not need to update its weights to do this. The input changes while the parameters stay fixed.

Before selection

Position 1the
Position 2cat

After appending

Position 1the
Position 2cat
Position 3sat (highlighted)

Next position

The new token becomes visible on the next pass.

Step 4 of 4

Stop when the response reaches a boundary

Repeat until an end token is selected or a length limit is reached. A different early choice can produce a different later context and continuation. The loop has no guarantee that a plausible sequence is factually correct.

Continue: Predict
Select
Append
Stop: End token
Length limit

A loop needs a stopping rule.

Follow the changing prefix, not changing weights

The tiny SDK decoder is untrained, so its words should not be read as meaningful language. Its visible prefixes and selection probabilities let us inspect how the generation loop works.

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

We know how to predict a distribution for the next token. How does that become a whole response? After choosing one token, we append it to the prefix and make another prediction. Let's follow the changing prefix and the scores used at each step, including the decision to stop.

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.

A Cache Reuses Computation from an Unchanged Prefix

During causal generation, earlier token representations cannot depend on tokens that have not been generated yet. Their key and value projections can therefore be retained while a new query is calculated for the appended token.

The cache must match the model weights, position convention, mask and exact prefix. Editing an earlier token invalidates affected cached state. A cache accelerates the same intended computation; it does not supply additional knowledge or change the probability model by itself.

Different Sequences Can Finish at Different Times

In a generated batch, one sequence can emit an end marker while another continues. Keep a finished mask and stop extending completed sequences. The remaining rows still need their own prefix and sampling state.

Also impose a maximum length. Reaching that limit means the run was truncated, which is different from the model choosing an end marker.

Retain a per-sequence stopping state

Token zero is the end marker. The supplied choices illustrate three generation rounds.

Python

import numpy as np
finished = np.array([False,False])
length = np.zeros(2, dtype=int)
for chosen in [np.array([2,1]), np.array([0,3]), np.array([4,0])]:
    length += ~finished
    finished |= chosen == 0
print(length.tolist())
print(finished.tolist())

Output

[2, 3]
[True, True]

The first sequence stops after its second generated token. The later supplied choice for that row is ignored by the length accounting.

Dropping Old Tokens Changes the Available Evidence

A context limit can require truncating a long prefix. Decide which information is retained, including task instructions and recent conversation. A model cannot reliably use evidence that has been removed from its input.

Position handling and cache updates must remain consistent with the chosen truncation method. Test the complete generation implementation against an uncached reference on short prefixes before relying on an optimisation for long ones.