Decoding & Sampling StrategiesOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Decoding & Sampling Strategies

A language model does not output text — it outputs a probability distribution over the next token at every position. Decoding is the algorithm that turns that distribution into the string you actually see. It is a deployment-time choice that lives entirely outside the trained weights, yet it is responsible for whether your model sounds factual, fluent, repetitive, creative, or reproducible. Two production systems with the same checkpoint but different decoders behave like different products.

Real-world examples: extraction and classification run at temperature 0 with greedy decoding (one right answer, reproducibility matters); creative writing and brainstorming runs at temperature ≈ 0.7 with top-p ≈ 0.9 (diversity beats determinism); machine translation and structured-output summarisation historically use beam search with k=4k = 4–88 and length normalisation; code completion is almost always greedy or beam, because syntactic errors compound and you want the model's single most confident continuation; chat assistants pick per-task defaults — a hidden routing layer flips between greedy and sampling depending on what the user asked for.

We met temperature and top-p briefly in Prompt Engineering & In-Context Learning. This lesson is the proper NLP-course treatment: every common decoder, the math behind it, the trade-offs, and the determinism caveats that bite production systems.

Greedy decoding

The simplest possible decoder. At every step, emit the argmax of the next-token distribution:

xt+1=arg⁡max⁡i  pθ(xt+1=i∣x1:t).x_{t+1} = \arg\max_{i} \; p_\theta(x_{t+1} = i \mid x_{1:t}).

One forward pass per token, zero hyperparameters, fully deterministic on a fixed kernel path. Greedy is what you want when there is exactly one right answer (classification labels, function-calling JSON, structured extraction). It is also what beam search with $k = 1$ collapses to, so any beam-search code path with k=1k = 1 is, by definition, greedy.

The failure mode is myopia. Greedy commits to whichever token has the highest one-step probability and can never recover. A model that knows "the capital of Australia is Canberra" with p=0.45p = 0.45 but happens to assign p=0.46p = 0.46 to "the capital of Australia is Sydney" will write the wrong answer — even though the rest of the sentence under the Canberra branch is far more likely overall. The next decoder fixes exactly this.

Beam search

Beam search keeps not one but kk partial sequences ("beams"). At each step:

  1. For every beam, score every possible next token. With kk beams and a vocabulary of size ∣V∣|V| that is k⋅∣V∣k \cdot |V| candidates.
  2. Pick the top kk candidates by cumulative log-probability ∑tlog⁡pθ(xt∣x<t)\sum_{t} \log p_\theta(x_t \mid x_{<t}).
  3. Repeat until every beam emits </s> or hits a length cap.

This catches the Canberra / Sydney case: even if "Sydney" wins step 1, both beams are kept; whichever has the higher cumulative log-prob after a few more tokens wins. Beam search dominates greedy on tasks with a single right answer that can only be identified a few tokens later — machine translation, extractive summarisation, structured generation with a known target format.

Step through exactly the Canberra/Sydney case — greedy first, so you can watch it lose, then a width-2 beam recovering the answer:

Beam search — keeping the option greedy threw away

1/9

The prompt is "the capital of Australia is", and the model is *almost* right: it puts 0.45 on Canberra and 0.46 on Sydney. One hundredth of probability separates the correct answer from the wrong one — and greedy decoding is entirely determined by that hundredth.

python
1def beam_search(lm, k, alpha=0.0):
2 beams = [([], 0.0)] # (tokens, logp)
3 done = []
4 while beams:
5 cand = []
6 for toks, lp in beams:
7 for tok, p in lm(toks).items():
8 cand.append((toks + [tok], lp + log(p)))
9 # keep only the k best partial hypotheses
10 cand.sort(key=lambda c: -c[1])
11 beams = []
12 for toks, lp in cand[:k]:
13 if toks[-1] == EOS:
14 done.append((toks, lp))
15 else:
16 beams.append((toks, lp))
17 # alpha = 0 -> raw logp; alpha = 1 -> per token
18 return max(done, key=lambda d: d[1] / len(d[0]) ** alpha)
state
p(next token | prompt)
Sydney
0.46
Canberra
0.45
Melbourne
0.09

The model is not confused about Australian geography — look at what each branch does next. It is the *decoder* that is about to throw the answer away.

The exact failure the lesson describes: a model that puts 0.46 on Sydney and 0.45 on Canberra, where greedy commits to the wrong city on the first token and can never recover. Watch a width-2 beam keep both hypotheses alive and let the continuation settle it. The final step shows the bias that comes free with cumulative log-probability — longer sequences always score worse — and what dividing by length does to the answer.

What to notice as you step:

  • Greedy loses on the first token and never gets another chance. Sydney wins by 0.01, and the branch behind it turns out to be worth far less. The final sequence probability is 0.138 against the beam's 0.279 — the model always knew, the decoder threw it away.
  • The beam does not have to choose yet. That is the entire mechanism: keep kk hypotheses alive until the evidence that separates them arrives.
  • Most beam steps do no work. The trace collapses a five-step stretch where the surviving branch had a single continuation — beam search still pays k⋅∣V∣k \cdot |V| scoring operations for each of them.
  • The last step is the length bias, which the next section fixes.

Length normalisation

Naïve beam search is biased toward short sequences. Each extra token multiplies the joint probability by p<1p < 1, so longer beams accumulate larger (more negative) log-prob and lose. The standard fix is length-normalised scoring:

score(x1:L)  =  1Lα∑t=1Llog⁡pθ(xt∣x<t),\text{score}(x_{1:L}) \;=\; \frac{1}{L^{\alpha}} \sum_{t=1}^{L} \log p_\theta(x_t \mid x_{<t}),

with α∈[0.5,1.0]\alpha \in [0.5, 1.0] — typically α=0.6\alpha = 0.6 in MT systems. α=1\alpha = 1 averages log-prob per token; α=0\alpha = 0 recovers naïve beam.

Why beam search is wrong for open-ended generation

For chat, story-writing, or any open-ended task, beam search mode-collapses. Empirically it produces strangely repetitive, low-diversity, unnatural text — a well-documented finding from the Holtzman et al. "nucleus sampling" paper (2019). The reason is that human language is full of locally low-probability choices that make the overall sequence interesting; beam search optimises away exactly those.

Rule of thumb. Beam search is for tasks with one right answer (translation, summarisation, code, JSON). Sampling is for tasks with many acceptable answers (chat, creative writing, brainstorming).

Beam search vs sampling, in one line

Beam search asks "what is the most likely sequence?". Sampling asks "give me a typical sequence." On open-ended generation, what you want is "typical", not "most likely" — the most-likely string in natural language is the the the the the ....

Temperature

Sampling-based decoders introduce randomness, but raw softmax is usually too peaky (almost greedy) or too flat (gibberish). Temperature TT rescales logits before softmax:

pi  =  softmax ⁣(ziT)  =  exp⁡(zi/T)∑jexp⁡(zj/T).p_i \;=\; \mathrm{softmax}\!\left(\frac{z_i}{T}\right) \;=\; \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}.

Two limit cases pin down what TT is actually doing:

  • T→0+T \to 0^+. All differences zi−zjz_i - z_j are amplified to ±∞\pm\infty. The softmax becomes a one-hot vector at the argmax. Sampling at T=0T = 0 is mathematically identical to greedy decoding.
  • T→∞T \to \infty. All logits collapse to 0/T=00/T = 0 inside softmax. The distribution becomes uniform over the vocabulary — every token equiprobable, output is random noise.

In between, low TT (0.1–0.5) sharpens — useful when you want the model "to be itself but a little freer". High TT (1.0–1.5) flattens — useful for brainstorming. Temperatures above 1.5–2.0 are rarely useful in practice; they make even very implausible tokens samplable.

Temperature does not bound which tokens appear

Temperature reshapes the distribution but never zeroes it. Even at T=2T = 2, the lowest-probability token in a vocabulary of 50 000 still has non-zero probability and can be sampled. This is exactly the problem that top-k and top-p fix.

Top-k sampling

Truncation. Sort tokens by probability, keep only the top kk, renormalise, sample from the survivors:

  1. Compute pp via softmax (with whatever temperature you chose).
  2. Find the indices of the kk largest probabilities Sk\mathcal{S}_k.
  3. Set pi=0p_i = 0 for i∉Ski \notin \mathcal{S}_k and renormalise so ∑i∈Skpi=1\sum_{i \in \mathcal{S}_k} p_i = 1.

kk is typically 40–50 for GPT-style models. The intuition is simple: cap the tail. The catch is that kk is fixed regardless of the shape of the distribution. If the model is very confident (p1=0.95p_1 = 0.95), keeping 40 tokens means 39 of them have a combined probability of 0.05 — fine but wasted. If the model is very uncertain (the top 100 tokens each have p≈0.01p \approx 0.01), keeping only 40 truncates a lot of perfectly reasonable continuations.

Top-p (nucleus) sampling

Adaptive truncation. Instead of fixing the count, fix the cumulative probability mass. Holtzman et al. (2019):

  1. Sort tokens in descending probability.
  2. Take the smallest set Sp\mathcal{S}_p whose cumulative probability is ≥p\ge p.
  3. Renormalise inside Sp\mathcal{S}_p and sample.

A typical setting is p=0.9p = 0.9 — keep the smallest set of tokens that together account for 90 % of the probability mass. The nucleus grows and shrinks with the distribution's confidence: peaky distributions might keep only 1–2 tokens (effectively greedy at that step), flat distributions might keep 50 (high diversity). That adaptivity is why nucleus sampling beats top-k on open-ended generation — it matches the truncation to the model's local uncertainty.

Decoding: Temperature & Nucleus (top-p) Sampling

0.000.100.200.310.41mat41%floor22%sofa14%roof5%table9%bed6%grass2%moon1%
tokens kept8 / 8
nucleus mass100%
entropy (bits)2.36

Next-token distribution after “The cat sat on the ___”. Temperature reshapes the distribution (low → peaky/greedy, high → flat/creative); top-p keeps only the smallest set of tokens whose probability sums to p (greyed-out bars are excluded), then renormalises the survivors.

Why top-p > top-k for open-ended tasks

Top-k fixes the count regardless of whether the model is confident. Top-p fixes the mass, so when the model is sure of the next token, you essentially get greedy; when the model is genuinely uncertain, you sample from a wide nucleus. That dynamic range is exactly what natural-language generation needs to avoid both repetition and gibberish.

Combining the knobs

In practice, samplers compose. The HuggingFace generate() default applies them in this order: repetition penalties → temperature → top-k → top-p → sample. Common recipes:

TaskTypical settings
Extraction, classification, JSONgreedy (or T=0T = 0)
Code completiongreedy, or beam k=4k = 4
Translation, summarisationbeam k=4k = 4–88, α=0.6\alpha = 0.6 length-norm
Chat (general)T=0.7T = 0.7, top-pp = 0.9
Creative writingT=0.8T = 0.8–1.01.0, top-pp = 0.95
Brainstorming, ideationT≈1.0T \approx 1.0, top-pp = 0.95, sometimes top-kk = 50 too

Repetition control

Vanilla sampling (even with top-p) drifts into repetition because once a phrase appears the model's own context biases it toward emitting that phrase again. Three patches show up everywhere:

  • Repetition penalty ρ>1\rho > 1 (Keskar et al., 2019). For any token ii that has already appeared in the context, divide its logit by ρ\rho before softmax (or multiply if negative). Typical ρ=1.1\rho = 1.1–1.31.3. Too large and the model can never reuse common words like "the".
  • No-repeat n-gram constraint. Hard rule: never emit a token that would complete an nn-gram already in the context. Common values: n=3n = 3 for chat, n=4n = 4–55 for translation. Cheap, deterministic, brittle on technical text where repetition is correct.
  • Frequency / presence penalties (OpenAI API). Two-parameter generalisation: subtract αf⋅count(i)\alpha_f \cdot \text{count}(i) and αp⋅1[count(i)>0]\alpha_p \cdot \mathbb{1}[\text{count}(i) > 0] from the logit of token ii. Cleaner than a hard n-gram rule but harder to tune.

Combine sparingly. Stacking aggressive temperature, top-p, repetition penalty and no-repeat-ngram is a common cause of weirdly stilted text.

The determinism caveat

It is tempting to believe that temperature 0 (or greedy decoding) makes generation bit-exact reproducible. It does not — at least not in production. Three sources of nondeterminism survive a greedy decoder:

  1. Non-associative floating-point math. Floating-point addition is not associative: (a+b)+c≠a+(b+c)(a + b) + c \neq a + (b + c) at the bit level. GPU kernels reduce sums in parallel using different orderings depending on tile size, batch size, hardware generation, and the specific kernel chosen by the autotuner. Two greedy decodes of the same prompt on the same model can produce different argmax tokens if the second-place logit is within a few ULPs of the winner.
  2. Batch-size sensitivity. Many inference servers batch concurrent requests for throughput. The same prompt may run in a batch of 1 at 3am and a batch of 64 at peak — different kernels, different reductions, different outputs.
  3. Mixed precision and kernel selection. bf16/fp16 weights, fp8 KV caches, and FlashAttention variants all use different summation orders. cuBLAS / cuDNN sometimes autoselect different kernels based on shapes that depend on dynamic batch composition.

The closest you get to bit-exact in practice is: (a) fix the random seed and the seed parameter (matters only for sampling, not greedy), (b) decode greedily (no sampling), (c) pin batch size and padding, (d) disable autotuning, (e) pin the model version, the driver, and the kernel library versions. Production APIs that advertise a seed argument generally promise "best-effort reproducibility", not bit-exactness, and explicitly warn that infrastructure changes can shift outputs.

Temperature = 0 is not the same as deterministic

"Temperature 0" guarantees that sampling reduces to argmax. It does not guarantee that the argmax itself is identical across machines, batches, or kernel versions. If two of your eval runs give different outputs on the same prompt at T=0T = 0, you have not found a bug. You have rediscovered non-associative float math.

Exercise

You're building a machine-translation system: English source sentences in, German translations out. Which decoder is structurally the right default, and why?

Need a hint?

Translation has essentially one right answer per source sentence, and the best translation is often only identifiable after looking a few tokens ahead.

Exercise

A 7-token next-token distribution has probabilities (sorted descending) $[0.40, 0.25, 0.15, 0.10, 0.05, 0.03, 0.02]$. At top-$p = 0.9$, how many tokens are kept in the nucleus?

1tokens4.00tokens7tokens
Need a hint?

Take tokens in order from highest to lowest, accumulating probability, until the running sum first reaches 0.9.

Exercise

Your eval pipeline runs the same prompt against a hosted LLM with `temperature=0` twice — once during a quiet maintenance window, once during peak traffic. The two outputs differ by a single token in the middle of the response. Which root cause is the most likely?

Need a hint?

Temperature 0 fixes the sampling step. It does not fix what happens at the kernel level when batch composition changes.

Common mistakes

  1. Beam search on open-ended generation. Mode collapse, repetitive output, low diversity. Use sampling. Beam search is for translation/summarisation/code, not chat.
  2. Treating T=0T = 0 as bit-exact reproducibility. It removes sampling randomness, not kernel-path nondeterminism. Pin batch size and kernels too if you really need reproducibility.
  3. Cranking temperature without truncation. Without top-k or top-p, raising temperature is the fastest way to inject implausible tokens. Always pair T>0.7T > 0.7 with p≤0.95p \le 0.95 or k≤50k \le 50.
  4. Stacking every knob. Temperature + top-k + top-p + repetition penalty + no-repeat-ngram + frequency penalty often interact badly. Start from a tested recipe; change one knob at a time.
  5. Forgetting length normalisation in beam search. Naïve cumulative log-prob always prefers shorter sequences; you will produce truncated translations and one-sentence summaries.
  6. Confusing top-k with beam-size kk. Top-k controls sampling truncation per step. Beam kk controls the number of partial sequences kept globally. They are unrelated, despite the shared letter.

Key takeaways

  • A decoder is the algorithm that converts the model's next-token distribution into text. It lives outside the weights; changing it changes the product.
  • Greedy = argmax per step. Deterministic per kernel path, myopic. Use for extraction, classification, code.
  • Beam search keeps kk partial sequences scored by length-normalised cumulative log-prob. Use for translation/summarisation/structured generation. Avoid for open-ended chat.
  • Temperature TT rescales logits: pi=softmax(zi/T)p_i = \mathrm{softmax}(z_i / T). T→0T \to 0 is greedy; T→∞T \to \infty is uniform.
  • Top-k truncates to a fixed count of highest-probability tokens. Top-p (nucleus) truncates to the smallest mass ≥p\ge p — adaptive to the distribution, generally better for open-ended generation.
  • Repetition control (penalty, no-repeat-ngram, frequency/presence) patches a known failure mode of sampling. Use sparingly.
  • Determinism is harder than "temperature 0": non-associative float math, dynamic batch sizes, and kernel autotuning all break bit-exactness. The closest production gets is greedy + fixed seed + fixed batch + pinned versions.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Decoding & Sampling StrategiesRecurrent Neural NetworksAttention & TransformersLLM EvaluationPrompt Engineering & In-C…LLM Model TaxonomyFoundation Models & Scali…Speculative Decoding