Decoding Strategies

Decoding strategies choose the next token from a language model's scores without retraining it. Greedy takes the highest score; Top-k samples from a fixed number of candidates; Top-p samples from enough candidates to reach a probability-mass threshold. Identical scores can produce different tokens, while temperature controls how concentrated the sampling probabilities are.

Picture a ruler from 0 to 1, divided into labeled intervals. Each token owns a length proportional to its probability. Sampling puts a random mark on the ruler and chooses the token underneath. A decoder can remove intervals and stretch the survivors to fill the ruler again. The model's scores can stay exactly the same while your mark lands on a different token.

How Decoding Strategies Work

A language model produces a logit, or unnormalized score, for each vocabulary token. For GPT-2, that means 50,257 scores for one fixed prefix. The decoder works with those scores; it does not need to change the model's weights.

Temperature T > 0 scales the scores before softmax:

p_T(i) = exp((z_i − max(z)) / T) / Σ_j exp((z_j − max(z)) / T)

Subtracting the largest score keeps the exponentials numerically manageable and leaves the probabilities unchanged. Lower temperature concentrates probability on the leading candidates. Higher temperature spreads it more broadly. Positive temperature never changes the rank order of a fixed set of logits. It cannot make the second-highest score become the highest.

Greedy decoding chooses the maximum logit. There is no random mark to place, so changing the seed has no effect. A unique maximum remains the choice for every positive temperature. Equal scores use a stated tie rule; this lesson prefers the smaller token ID.

Top-k keeps the first k tokens in the ranking. Top-p, also called nucleus sampling, walks that ranking until its cumulative probability reaches or exceeds the chosen threshold. It keeps the token that crosses the threshold. The candidate count can be one, seven, or thousands; the threshold specifies mass, not count.

Filtering leaves a gap on the ruler: the remaining probabilities may sum to less than one. A uniform mark anywhere from 0 to 1 could then land where every token has been excluded. The retained set must cover the whole ruler before we use it to select a token.

Both sampling methods normalize their retained set S. If M = Σ_(i in S) p_T(i), the sampling probability is q(i) = p_T(i) / M for retained tokens and zero for excluded tokens. This stretches the surviving intervals to cover the entire unit ruler while preserving their relative odds. When the surviving probabilities differ, uniformly selecting among them would be a different distribution: the random mark is uniform along the ruler, but wider token intervals are more likely to contain it.

The two methods here each start from the full temperature-adjusted distribution. Top-k is not silently applied before Top-p. The definitions follow the Transformers generation parameters; nucleus sampling was introduced in The Curious Case of Neural Text Degeneration.

Decoding Strategies Step by Step

The default experiment uses the exact prefix The colors of the rainbow are red, orange, yellow,, with T = 1, k = 3, top-p = 0.8, and seed 41. These are real GPT-2 outputs. A leading · makes a token's space visible; the vocabulary contains fragments and punctuation as well as words.

The remaining 50,249 tokens carry about 0.162419 probability between them. That tail remains part of every computation. The model's preference for ·blue here is an output to inspect, not a claim about rainbow ordering.

Greedy chooses ·blue. It is rank 1. This decision uses neither k, the Top-p threshold, nor the seed.

Top-k keeps three candidates. Their mass is M = 0.655268, leaving about 0.344732 excluded. On the original ruler, the eligible intervals end at 0.655268; a mark beyond that point could not select an eligible token. Dividing by the retained mass gives sampling probabilities of approximately 0.345777 for ·blue, 0.333200 for ·and, and 0.321023 for ·green. They now cover the whole ruler.

Place one random mark, then locate its token. Seed 41 produces the first draw u = 0.8510142471641302, a number in [0, 1). Read the normalized intervals from left to right in token-rank order. The ·green interval runs from approximately 0.678977 to 1, so Top-k selects ·green. Green has about a 32.10% chance here because its interval occupies that fraction of the ruler.

Top-p keeps seven candidates. Six tokens reach only 0.787099, below 0.8. Adding ·orange reaches 0.812691; it must be included. Normalize all seven probabilities by this new retained mass. The ·purple interval now runs from approximately 0.806294 to 0.880085. The same u falls inside it, so Top-p selects ·purple.

That controlled comparison is the point: identical model scores and an identical random draw give ·blue, ·green, and ·purple under the three rules.

The final ledger repeats the draw twelve times at this same prefix. Its columns are independent trials, not successive words. Both samplers share each trial's random value to make comparison easier; their outcomes are therefore coupled across methods. Greedy repeats ·blue throughout. Within each sampling method, later trials use fresh pseudorandom draws. Twelve observations illustrate variation, but cannot establish that observed frequencies equal the underlying probabilities.

Top-k Fixes Count; Top-p Adapts to Concentration

Keep the default prefix and top-p = 0.8. At temperatures 0.5, 1, 1.5, and 2, its nucleus contains 3, 7, 352, and 6,340 tokens, respectively. The ranking has not changed. Probability has spread far enough down that ranking that the same mass threshold needs many more tokens.

Now hold T = 1 and change only the prefix. After 1, 2, 3, 4, 5,, GPT-2 assigns about 0.909493 to ·6. That one token already exceeds 0.8, so Top-p has one candidate and behaves deterministically. After The capital of France is, the same threshold requires 502 candidates. Top-k still keeps exactly k in either case.

The controls answer different questions:

If k=1 leaves you without variation, raising temperature cannot help: the only surviving token still gets the entire ruler. Increase k to permit alternatives. When comparing settings, hold the prefix and seed fixed so a new random draw does not obscure the change. Neither rule guarantees correct statements, and increasing temperature is not a measured improvement in creativity or quality.

Time and Space Complexity

For vocabulary size V, Greedy needs O(V) time to find a maximum. This lesson ranks the full vocabulary in O(V log V) time, then computes probabilities, retained mass, and cumulative sampling intervals in O(V) time and space. A binary search locates each draw in O(log |S|) time once its cumulative distribution exists.

The fixed prefix allows its ranking to be reused across positive temperatures. Full sorting is this implementation's choice; specialized Top-k selection can use other algorithms. In a real generation loop, appending a token produces a new prefix and requires a new model forward pass, which is outside these decoder-only costs.

Edge Cases

• k = 1: the only retained token gets q = 1, even if its original probability is small. Temperature cannot restore variation after every alternative has been excluded.
• A threshold below the top token's probability: Top-p retains that single token. Sampling can therefore be deterministic without selecting Greedy explicitly.
• Threshold equality: stop as soon as cumulative mass reaches the threshold exactly. If it is still below the threshold, include the next token.
• top-p = 1 or k = V: retain the full vocabulary. With both settings enabled in this comparison, the two samplers use identical distributions and identical draws, so their selections match.
• A selection outside the displayed eight: the inspector names the actual token and its rank and interval. The grouped tail is never sampled as an artificial token called “Others.”
• Equal logits: the lesson breaks ties by token ID. Library cutoff conventions can differ at exact ties.
• T = 0: it is not a valid divisor in this formula. Greedy is provided as an explicit selection rule; the temperature control remains positive.

Common Mistakes

Treating Top-p as a per-token cutoff. A threshold of 0.8 does not mean “keep tokens individually above 80%.” It describes the sum of a ranked prefix.

Dropping the crossing token. In the default, removing rank 7 leaves only 78.71% mass, below the requested 80%. The token that reaches the threshold belongs in the set.

Sampling uniformly after filtering. Retained tokens usually have unequal odds. Dividing them all by the same mass preserves those odds; replacing each with 1 / |S| does not. The two agree only when every retained token has the same probability, such as the single survivor at k = 1.

Renormalizing only the visible bars. That would erase the model's tail before the decoder made its decision. Temperature and Top-p use all 50,257 entries here.

Reading a row of draws as generated text. A real continuation feeds each selected token back into the model. These redraws deliberately hold the prefix fixed to isolate the decoder. Next-Token Prediction shows the feedback loop.

A Note on Simplification

This is an explainer, not a substitute for formal training. It uses complete logits exported from three real GPT-2 forward passes, with the model revision and export metadata saved alongside the data. The browser recomputes decoding without loading the model, in double precision, so the Top-p input accepts up to six decimal places. Eight tokens are drawn individually and the rest are grouped visually. Repeated model inference, beam search, repetition penalties, and other logit processors are omitted so you can inspect retention, normalization, and selection separately.