Chapter 29 Generation Strategies: From Logits to Sampling

29.1 One model can produce several different continuations

A model has assigned scores after “The capital of France is”. The application still has a decision to make. Should it always take the highest-scoring token, or sometimes choose another? The same choice appears in our travel assistant, but the criterion is different: a correct current amount matters more than variety. A short fictional scene may welcome variety, provided it remains coherent.

Chapter 4 turned counts into probabilities, and Chapter 18 turned model scores into a next-token distribution. This chapter fixes the scores and changes only the selection rule. That isolates what generation policy can change. Later, actual Mini GPT records show the limit: a selection rule cannot insert missing knowledge or teach reliable instruction following.

29.2 Four scores, one explicit order

Example 29.1 — France, with a deliberately tiny candidate list. Candidates are ordered Paris, Lyon, red, EOS. EOS is the end-of-sequence token: selecting it stops this generation. Assign logits $[\ln4,\ln2,0,0]$, approximately $[1.386294,0.693147,0,0]$. These are teaching scores, not measured model logits. Logits are unnormalized numerical scores; a zero logit does not mean zero probability.

Exponentiating gives weights $[4,2,1,1]$. Their sum is 8, so the probabilities are $[4/8,2/8,1/8,1/8]$. The denominator adds the weights of all currently eligible candidates. This is softmax. To avoid very large exponentials in code, subtract the largest score from every score before exponentiating. That multiplies all four weights by the same factor, which cancels in normalization.

Greedy decoding selects the largest score, here Paris. It does not draw from the distribution. Our tie convention is the first candidate in the original order; red precedes EOS when their scores tie. A different tie convention belongs in the run record.

To make the distribution flatter, divide every logit by a positive temperature before softmax. At temperature 2, the weights become $[2,\sqrt2,1,1]$, because exponentiating half a logarithm takes a square root. The denominator is $4+\sqrt2\approx5.414214$, giving approximately $[0.369398,0.261204,0.184699,0.184699]$.

Only now write the general expression:

$$p_i(\tau)=\frac{\exp(z_i/\tau)}{\sum_{j=1}^{V}\exp(z_j/\tau)},\qquad \tau>0.$$

The index i identifies a candidate; V is the number of eligible candidates; $z_i$ is its score; and $\tau$ is temperature. The sum in the denominator runs over those same candidates. Temperature 1 recovers our 4:2:1:1 weights; temperature below 1 sharpens the relative weights. Temperature 0 is a separate greedy convention in our scalar program, not permission to divide by zero. With tied maxima, the limit as temperature approaches zero is not the same as deterministically picking the first tied item. Negative temperature is rejected here.

29.3 Filtering changes the denominator again

A flatter distribution also gives low-ranked candidates more chance. Perhaps we want some variety without keeping every tail candidate. Top-k retains k highest-probability candidates. Top-p, or nucleus sampling, retains the smallest descending-probability prefix whose cumulative probability reaches at least p. Ties use the original candidate order. Both require renormalization after filtering.

Example 29.2 — Keep a count or keep enough mass. Work at temperature 1. With top-k = 2, keep Paris and Lyon. Their old mass is $0.5+0.25=0.75$, so divide the retained probabilities by 0.75. The new distribution is $[2/3,1/3,0,0]$.

For top-p = 0.6, Paris alone has mass 0.5 and is insufficient. Adding Lyon brings the mass to 0.75, so stop there and obtain the same two-candidate distribution. The retained mass may exceed the threshold; we do not split a token’s probability to hit it exactly. At top-p = 0.8, add red too: the mass is 0.875, and the final distribution is $[4/7,2/7,1/7,0]$.

Table 29.1 — Derived distributions in original candidate order

Policy	Paris	Lyon	red	EOS
Greedy convention	1	0	0	0
Temperature 1	0.5	0.25	0.125	0.125
Temperature 2	0.369398	0.261204	0.184699	0.184699
Temperature 1, top-k 2	2/3	1/3	0	0
Temperature 1, top-p 0.5	1	0	0	0
Temperature 1, top-p 0.6 or 0.75	2/3	1/3	0	0
Temperature 1, top-p 0.8	4/7	2/7	1/7	0

At exactly 0.75, our “at least” rule stops after Lyon. A rule that accidentally insists on exceeding 0.75 would retain red and change the distribution. If both top-k and top-p are requested in our implementation, temperature comes first, top-k second, then top-p uses the renormalized surviving distribution. That order is an explicit local contract; do not assume every service combines controls identically.

Normalize four weights

1. A list of numbersParis 4 | Lyon 2 | red 1 | EOS 1
2. An operationDivide each by 8
3. A list of numbers0.5 | 0.25 | 0.125 | 0.125

Paris ends at .5; the draw .60 lies in Lyon.

Top-p = .8

1. An operationCumulative .5 → .75 → .875: stop
2. A list of numbersKeep Paris, Lyon, red; exclude EOS
3. An operationWeights 4+2+1 = 7
4. A list of numbers4/7 | 2/7 | 1/7 | 0

The retained mass exceeds .8; token probability is not split to hit the threshold.

Top-k = 2

1. A list of numbersWeights 4,2 → 2/3,1/3
2. An operationParis interval [0,2/3)
3. Text piecesDraw .60 → Paris

Same supplied draw, different decision after renormalization.

Figure 29.1 — Filtering changes probability intervals. Original book diagram · CC BY-SA 4.0.

Figure 29.1 shows why filtering is not merely graying out labels: retained probabilities grow when their common denominator shrinks.

29.4 A draw selects an interval, then the prefix changes

At temperature 1 with no filter, lay out intervals in original candidate order: Paris occupies $[0,0.5)$, Lyon $[0.5,0.75)$, red $[0.75,0.875)$, and EOS $[0.875,1)$. Draw a uniform number u from the interval starting at 0 and ending just before 1. Left endpoints are included, right endpoints excluded. A supplied draw of 0.74 chooses Lyon; 0.75 chooses red; 0.99 chooses EOS. A draw of exactly 1 is invalid.

Using u = 0.74 after top-k 2 still chooses Lyon; after top-p 0.8 it also lies in Lyon’s interval, now from $4/7$ to $6/7$. The same draw need not select the same token under another policy. At u = 0.60, the unfiltered distribution chooses Lyon, while top-k 2 chooses Paris. Changing the intervals changed the decision.

After choosing a non-EOS token, append its ID to the prefix and run the model again. The next distribution generally changes because the input changed. “Draw with replacement” is a good analogy for repeatedly testing one fixed distribution, not for claiming that every step of language generation uses the same probabilities.

Our real Mini GPT generator forbids BOS and PAD, permits EOS, and stops on EOS, an output-token budget or its context limit. A maximum-token stop is not evidence that an answer is complete. A byte tokenizer can also stop in the middle of a UTF-8 character, which is why raw bytes and decoding validity are retained. Text stop strings require a declared check over decoded output; they are not necessarily single tokens and are not implemented in this small generator.

29.5 A locally best token can lose over a complete path

Example 29.3 — A two-step search tree. At step 1, assign candidates A and B probabilities 0.6 and 0.4. After A, EOS and x each have probability 0.5. After B, EOS has 0.9 and x has 0.1. Candidate order is A before B and EOS before x. Stop completed paths at EOS; inspect a two-token horizon and mark a path ending in x unfinished.

Table 29.2 — Derived joint path probabilities

Path	Multiplication	Joint probability	Status
A, EOS	0.6 × 0.5	0.30	Complete
A, x	0.6 × 0.5	0.30	Unfinished at horizon
B, EOS	0.4 × 0.9	0.36	Complete
B, x	0.4 × 0.1	0.04	Unfinished at horizon

Greedy selects A, then EOS by our tie rule, obtaining 0.30. Beam search with width two retains both first-step prefixes, expands both, and can find B, EOS at 0.36. It approximately searches for a high-scoring sequence while retaining only a bounded number of partial paths. A wider beam does not prove that the sequence is true, useful or creatively good; it optimizes the declared model score, and finite pruning can miss the optimum.

For longer paths, summing log probabilities avoids multiplying many tiny numbers. Raw joint probability often favors shorter completed strings. Dividing log probability by length changes that preference: a one-token path of probability 0.4 beats a two-token path of probability 0.3 under raw probability, but $\ln(0.3)/2>\ln(0.4)$ under this particular length-normalized score. Different normalization formulas define different objectives. The GNMT paper supplies a concrete task-specific example; our formula is a simple illustration, not a universal beam recipe.

29.6 Penalties can suppress the correct repetition too

Suppose Paris already appeared twice, and we subtract 0.5 from its logit for each occurrence in the generated continuation. Its adjusted score becomes $\ln4-2\times0.5\approx0.386294$, below Lyon’s $\ln2\approx0.693147$. The repeated correct city loses first place. In general this chosen count penalty is $z'_i=z_i-\lambda c_i$, where $c_i$ counts prior generated occurrences of candidate i and $\lambda$ is the penalty per occurrence. Other implementations use presence or multiplicative rules; their names are not interchangeable.

A penalty can discourage loops. It can also damage repeated identifiers, quoted policy amounts or a structured field that must repeat an earlier value. Temperature and penalties change selection preferences, not the learned weights, the source document or execution permissions. Setting temperature low cannot update an old 600-yuan rule to 750 if the model fails to use the supplied evidence.

29.7 Fixed rules meet an actual small model

The companion experiment fixes MG-2’s step-600 weights, tokenizer and 24-new-token budget. It runs greedy and two top-k-5 sampling policies at temperatures 0.7 and 1.2, each with seeds 7, 42 and 31415. English and Chinese prompts are frozen in the same resource. All 36 attempts ran on CPU float64 with one thread; versions, per-step IDs, raw bytes and stops are in data/part-v/generation-run.json. These are actual model outputs, separate from Table 29.1’s assigned logits.

The structured English prompt is Beijing lodging limit: 750. Answer: ; the Chinese prompt is 北京住宿限额750元。答案：. The required diagnostic output is exactly 750 after trimming. The creative prompts are The key is red. and 钥匙是红色的。; the criterion is a coherent short continuation retaining the red key. Mere distinctness does not satisfy that criterion.

Table 29.3 — Measured structured completions, seeds 7 / 42 / 31415 in that order

Input language and policy	Seed 7	Seed 42	Seed 31415
English, greedy	red.	red.	red.
English, 0.7 / top-k 5	t750on: n: old.	red.	red.
English, 1.2 / top-k 5	t750ol: n: old.	ped.	tNon: n: old.
Chinese, greedy	red red red t: red te. Ver: red t: red t	red red red t: red te. Ver: red t: red t	red red red t: red te. Ver: red t: red t
Chinese, 0.7 / top-k 5	blue key blue er: red red t: red te. Aeuo	red red te.	red red red t: red te red teu
Chinese, 1.2 / top-k 5	blue key blue er: red red red red te. Answer	red red te.	red red red t: red keye key.

None of these 18 structured attempts passes. The digits embedded in t750on are not a correct amount-only answer. All English rows stop at EOS. Chinese greedy attempts and seed-7 Chinese sampling attempts reach the token budget; the other Chinese sampling attempts stop at EOS. All 18 decode as valid UTF-8, which plainly does not make them good Chinese answers.

For the creative task, every English attempt, across all three policies and all three seeds, is Answer: red. followed by EOS. Every Chinese attempt immediately selects EOS and has an empty continuation. Thus each policy has one distinct completion per language across three repeats, and none supplies the requested scene. This is a failed capability/variety experiment, not evidence that sampling cannot vary any model. It also prevents a misleading report that selects the most attractive seed and discards the rest.

A seed initializes a particular random-number generator. Different libraries, precision, kernels, candidate filtering or draw order can still change outputs. Even a deterministic same-stack replay proves reproducibility of that configuration, not cross-platform identity. The next chapter follows the computation between these choices, where reuse and precision become resource decisions.

29.8 Summary

Generation policy turns logits into token choices through score adjustment, eligible-candidate selection, renormalization, a draw or search, and stopping. Each stage needs a convention. Greedy, sampling and beam search optimize different immediate or sequence criteria; none independently guarantees factual correctness, useful diversity or instruction following.

29.9 Exercises

1. Use Table 29.1’s unfiltered temperature-1 distribution with draws 0.49, 0.50, 0.75 and 0.99. Give the selections and explain the boundary at 0.50.
2. Set top-p to 0.76 at temperature 1. Which candidates remain, and what are their new probabilities? Why does top-p 0.75 differ?
3. Set temperature to 0.5 with no filtering. Derive the four weights and probabilities instead of merely describing the distribution as sharper.
4. In Example 29.3, change the first-step probabilities to A = 0.8 and B = 0.2. Compare the two completed paths. Does beam width two always change the greedy result?
5. A report says temperature 1.2 produced three distinct strings, so it improved structured-answer quality. Diagnose the claim using Table 29.3.
6. A run stops at the token budget with valid UTF-8. What two separate checks remain before calling the response successful?

29.10 Reference answers

1. Paris, Lyon, red, EOS. The Paris interval ends just before 0.50; the Lyon interval includes 0.50. Assigning both endpoints to both candidates would make the rule ambiguous.
2. Paris and Lyon reach only 0.75, so red is needed. Normalize by 0.875 to obtain $[4/7,2/7,1/7,0]$. At 0.75, the first two already meet the “at least” condition and normalize to $[2/3,1/3,0,0]$.
3. Dividing logits by 0.5 doubles them, giving weights $[16,4,1,1]$. Their sum is 22, hence probabilities $[8/11,2/11,1/22,1/22]$. The most likely candidate gains mass without gaining new knowledge.
4. A, EOS has $0.8\times0.5=0.4$; B, EOS has $0.2\times0.9=0.18$. Both searches can select A, EOS. Search width creates an opportunity to retain alternatives, not a requirement to disagree with greedy.
5. All three English temperature-1.2 outputs fail the exact amount requirement and do not convey a reliable policy answer. Distinctness measures variation; it does not establish factual or format quality. Preserve all seeds and evaluate the task criterion separately.
6. Check whether the intended response is complete, and whether its content/format satisfies the task. Valid UTF-8 only checks byte decoding; a budget stop supplies no semantic completion guarantee.

29.11 References

• Holtzman et al., The Curious Case of Neural Text Degeneration, 2020. Sections 2.2 and 3.1 distinguish sequence likelihood from open-ended quality and define nucleus filtering/renormalization.
• Wu et al., Google’s Neural Machine Translation System, 2016. Section 7 gives a concrete beam-search objective with length and coverage terms.