Decoding strategies: greedy, beam, top-k, top-p, temperature

Summary

Decoding turns next-token scores into eligible outputs using a declared selection or search policy. Temperature changes probabilities; truncation removes tokens before the retained distribution is normalized. Neither high model probability nor low temperature establishes factual correctness.

Specify vocabulary, allowed-token mask, processor order, tie policy, and EOS or budget stopping. Our default calculation uses temperature $T = 1$ , then truncation, renormalization, and sampling. An empty allowed set is an error requiring an explicit recovery policy, not an arbitrary token.

The strategies

Greedy

Pick $ar g max_{x} p (x ∣ x_{< t})$ at every step.

Declare tie-breaking among allowed maxima. Local argmax need not maximize complete-sequence probability or task quality.

Beam search

Retain a declared number of prefixes, expanding them by cumulative score $\sum_{t} lo g p (x_{t} ∣ x_{< t})$ . Finite beams prune possibilities and need not find the global optimum. Specify completed-EOS handling, length normalization, and stopping together; these can change the selected sequence.

Temperature sampling

Sample from $softmax (z / T)$ where $z$ is the logit vector and $T$ is the temperature.

Require $T > 0$ . Lower values sharpen relative probabilities; $T \to 0$ concentrates on maximizers, with ties requiring a policy. Large $T$ approaches uniform over finite allowed logits, not masked tokens.

Top-k sampling

Retain exactly $k$ highest-probability allowed tokens, resolving cutoff ties by a declared order (Fan et al., 2018). Renormalize their probabilities; a fixed count does not fix retained mass.

Top-p (nucleus) sampling

Retain the smallest sorted prefix whose mass reaches at least threshold $p$ , including the crossing token. Choose a threshold in $(0, 1]$ ; declare cutoff ties and renormalize (Holtzman et al., 2020).

Learning objective

Top-k fixes a count; top-p changes the count to reach a probability mass

Derivation

both panels use the same vertical probability scale. Solid top-k brackets retain three tokens with masses 0.90 and 0.61. Dashed top-p brackets retain two and five tokens, reaching at least 0.80 with masses 0.84 and 0.86. Divide by the retained mass before sampling; do not sample from the original probabilities without renormalizing.

Check: Why does the uncertain distribution need five tokens rather than four to reach 80% mass?

Read it this way: Top-k with k=2 keeps mass 0.70 here. Top-p with p=0.8 needs the third token too, reaching mass 0.85.
Why must the 0.8 cutoff include a third token?

Confident top-k becomes $(0.8, 2/15, 1/15)$ ; confident top-p becomes $(6/7, 1/7)$ . Uncertain top-k becomes $(24, 20, 17) /61$ ; uncertain top-p becomes $(24, 20, 17, 14, 11) /86$ .

Change processor order

New task: use $T = 2$ and top-p $0.85$ on probabilities $(0.6, 0.3, 0.1)$ .

Picture and change: temperature transforms probabilities proportionally to their square roots.

Check: temperature first gives approximately $(0.472734, 0.334273, 0.192993)$ , requiring all three tokens. Truncation first retains mass $0.9$ , then temperature gives $(0.585786, 0.414214)$ .

Use when: reproducing a serving pipeline; processor order is part of the distribution.

Search complete sequences

New task: maximize a two-token sequence’s probability, then stop.

Picture and change: first-token probabilities are $p (A) = 0.6, p (B) = 0.4$ . Their best continuation probabilities are $0.5$ and $0.9$ .

Check: greedy follows A, obtaining joint probability $0.30$ . A width-two search can retain B and its $0.36$ completion.

Use when: sequence-score search, rather than a single-step sample, matches the actual objective.

Min-p sampling

Retain $p_{i} \geq p_{m i n} max_{j} p_{j}$ and renormalize. This compares individual probabilities with the maximum, not cumulative mass.

Repetition penalty and other modifiers

Real systems layer modifications on top of the base sampler:

Repetition penalty: one sign-aware convention divides positive repeated-token logits by $c > 1$ and multiplies negative ones by $c$ .
Frequency / presence penalty: linear adjustment based on how often a token has appeared.
No-repeat n-gram: forbid repeating any n-gram already in the output.
Logit bias: add token-specific offsets; use an explicit hard mask to forbid tokens.

Dividing a negative logit alone is wrong: $- 2/2 = - 1$ increases its score, while $- 2 \times 2 = - 4$ decreases it. Grammar constraints restrict allowed tokens but do not establish semantic or factual correctness.

Choosing per task

Task	Policy to evaluate
Translation, QA, summarization	Compare search/sampling against task metrics, not likelihood alone
Code	Declare sampling and stopping; evaluate generated programs
Open chat	Evaluate quality and diversity under fixed settings
Creative writing	Choose support and temperature against a declared objective
Structured output	Enforce grammar, then validate the completed result

Common pitfalls

Compare models under declared policies, random states, masks, and stop rules. An EOS mask can make a budget endpoint differ from a naturally completed sequence. Zero temperature is an implementation’s argmax policy, not a division operation.

What does min-p $0.2$ retain from the uncertain seven-token fixture?

Answer

All seven: the threshold is $0.2 (0.24) = 0.048$ , below the smallest probability $0.06$ . Neither top-k’s count nor top-p’s cumulative threshold describes that support.

Speculative decoding. Faster decoding, same distribution.
Perplexity.