Decoder Output Sampling: Greedy, Beam Search, Temperature, Top-k, and Top-p Compared

Identity statement: each decoding strategy is a rule for converting a probability distribution over the vocabulary, produced fresh at every generation step, into one selected token (or, for beam search, into a decision about several parallel candidate sequences at once).

Greedy decoding always selects the single highest-probability token at each step, with no randomness and no lookahead. [GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): "Greedy — Always pick the top token — Deterministic, but can loop/repeat." Determinism is the whole property: the same prompt, run twice, produces the identical output every time, because there is no random draw anywhere in the process — but a model that always takes the locally best token has no mechanism for recognizing it has wandered into a repetitive loop, since each individual step still looks locally optimal even while the overall sequence degrades.

Beam search maintains several partial candidate sequences ("beams") simultaneously, extends each by its most promising next tokens, and keeps only the best-scoring subset at every step, ultimately returning whichever completed sequence scored highest overall. [GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): "Beam search — Keep the top-k partial sequences, expand each — Higher-likelihood output (translation, summarization)." This is the one strategy in the list that reasons about the whole sequence's probability rather than one step's, which is exactly why it is grouped with translation and summarization: tasks with something close to one correct output, where finding the globally highest-likelihood sequence is actually the goal.

Temperature rescales the logits (the pre-softmax scores) before converting them into probabilities, sharpening or flattening the resulting distribution. [GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): "Temperature — Reshape distribution sharpness before sampling — Low = focused/factual, high = diverse/creative." This is a reshaping operation applied to every probability in the distribution, not a rule about which tokens are eligible at all.

Top-k restricts sampling to only the k highest-probability tokens, discarding everything else regardless of how those k tokens' probabilities compare to each other. [GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): "Top-k — Sample from the k most probable tokens — Bounds the candidate set."

Top-p (nucleus sampling) instead includes tokens until their cumulative probability crosses a threshold p, so the candidate set's size adapts automatically to how confident the distribution is at that step. [GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): "Top-p (nucleus) — Sample from the smallest set whose cumulative probability exceeds p — Adapts the candidate set to confidence."

L1 — Intuition

Picture the model's output as a hand of cards laid face-up on a table, each card a vocabulary token with its probability written on it. Greedy decoding just takes the card with the biggest number, every time, no exceptions. Beam search deals out several hands in parallel — several possible next few cards each — and only keeps the hands that are winning overall, discarding the rest, so a card that looked mediocre on its own can survive if the hand it is part of turns out strong. Temperature is not about which card you pick at all — it is about redrawing the numbers on every card first, either exaggerating the gap between the biggest and smallest numbers (low temperature) or shrinking that gap so the cards look more evenly matched (high temperature), before anyone picks anything. Top-k and top-p are about which cards are even allowed on the table before a random pick happens — top-k keeps a fixed count of the best cards, top-p keeps however many cards it takes to cross a probability threshold, discarding the rest either way.

L2 — Mechanism

Concretely: a decoder's final layer produces logits — one real-numbered score per vocabulary token. Softmax converts logits into a probability distribution that sums to 1. Temperature intervenes before that softmax, dividing every logit by a temperature value T: lower T (below 1) exaggerates the differences between logits, producing a sharper, more peaked distribution after softmax; higher T (above 1) shrinks those differences, producing a flatter, more uniform distribution. Top-k and top-p intervene after softmax has already produced a distribution: top-k sorts tokens by probability and keeps only the top k, renormalizing their probabilities to sum to 1 among just that subset before sampling; top-p sorts tokens by probability, accumulates them from highest to lowest until the running total exceeds p, and keeps that variable-sized subset, renormalizing the same way. Both then sample randomly from their respective truncated, renormalized subsets — the actual token selection, once the eligible set is fixed, is a random draw weighted by the remaining probabilities, not another deterministic top-pick.

Greedy decoding, beam search, temperature, and truncation are not four unrelated tools competing for the same slot — they answer three different questions asked in sequence. Truncation (top-k/top-p) answers "which tokens are even eligible?" Temperature answers "how sharply should eligible tokens' relative probabilities be weighted?" And the final selection rule (deterministic top-pick for greedy, or a weighted random draw for sampling, or sequence-level scoring across multiple candidates for beam search) answers "which eligible token(s) actually get chosen?" A production system commonly applies top-k or top-p first to trim the distribution, then applies temperature to reshape what remains, then samples — all three cooperating, not competing.

L3 — The exam-relevant edge case: greedy is beam width 1, and temperature 0 approximates greedy

[GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): "Greedy decoding is a special case of beam search with beam width 1." This is worth holding as an exact identity rather than a loose analogy: if beam search's beam width parameter B is set to 1, the algorithm tracks exactly one candidate sequence, extends it by its single best next token at every step, and never has a second beam to compare against — which is precisely greedy decoding's behavior, arrived at as beam search's own degenerate case rather than as a separate, unrelated algorithm. The practical consequence is that "beam search" and "greedy" are not two disjoint categories on an exam item; a question that asks you to identify beam width 1 as a decoding choice is testing whether you recognize it as greedy under another name.

A related but distinct edge case: setting temperature to exactly 0 is often described as producing greedy-equivalent output, because dividing logits by a temperature approaching 0 pushes the post-softmax distribution toward an extreme spike on the single highest-logit token, effectively collapsing sampling into a deterministic top-pick. This is a limit behavior of the temperature formula, not a coincidence — but it is worth keeping the concepts themselves distinct: greedy decoding is a selection rule (always take the top token, no randomness involved at all), while temperature is a reshaping operation on the distribution that a sampling step is then applied to; temperature 0 makes sampling behave like greedy, but greedy decoding, as a named algorithm, involves no temperature or softmax reshaping step in the first place.

Constructed scenario, illustrative only. Suppose, at one generation step, a decoder's softmax output over five candidate next tokens is:

Token:        "the"   "a"    "an"   "some"  "this"
Probability:  0.50    0.25   0.15   0.06    0.04

Greedy: always picks the single highest-probability token.
  -> selects "the" (0.50), every time, no randomness.

Beam search (width 2, illustrating just this one step of a longer sequence):
  -> keeps BOTH "the" (0.50) and "a" (0.25) as two live beams to extend further;
     the eventual choice depends on which beam's FULL sequence scores higher later,
     not on this step's probability alone.

Temperature = 0.5 (sharpening): logits are divided by 0.5 before softmax, which
  exaggerates gaps -- resulting distribution might sharpen to roughly:
  "the" ~0.74, "a" ~0.16, "an" ~0.06, "some" ~0.02, "this" ~0.02
  (illustrative reshaping, not an exact recomputation)

Temperature = 1.5 (flattening): logits divided by 1.5 shrinks gaps -- distribution
  flattens toward roughly:
  "the" ~0.38, "a" ~0.26, "an" ~0.20, "some" ~0.10, "this" ~0.06

Top-k = 2: keep only "the" and "a", discard the rest, renormalize:
  "the" -> 0.50/0.75 ~= 0.667     "a" -> 0.25/0.75 ~= 0.333
  then sample randomly, weighted by these two renormalized values.

Top-p = 0.7: accumulate from highest probability until cumulative > 0.7:
  "the" (0.50) -> cumulative 0.50, still under 0.7 -> keep going
  + "a" (0.25) -> cumulative 0.75, now over 0.7 -> STOP, keep {"the", "a"}
  (same kept set as top-k=2 here, by coincidence of this particular distribution --
   top-p's set size is NOT fixed in general the way top-k's is)

The last line is worth flagging explicitly, because it is exactly the kind of coincidence a scenario question exploits: top-k and top-p happened to keep the same two tokens at this particular step, purely because the distribution's first two tokens' cumulative probability landed just past 0.7. At a flatter step — say five tokens each near 0.20 — top-p=0.7 would need four tokens to cross the threshold, while top-k=2 would still keep exactly two, however flat the distribution got. That divergence is the mechanical reason top-p is described as adapting to confidence and top-k is not: top-p's kept-set size shrinks when the model is confident (one or two tokens dominate) and grows when the model is uncertain (probability spread thin across many tokens), while top-k's kept-set size is fixed at k regardless of how the underlying distribution's shape changes step to step.

The five strategies are not five equally good options for every task; a stated constraint usually points at one clearly. A factual, single-answer lookup task — extracting a date from a document, answering a closed-book arithmetic question — favors low temperature or greedy decoding, because the goal is the model's single most confident answer, and randomness only risks displacing it with a less likely, and therefore less probably correct, alternative. Open-ended creative writing — a story continuation, a brainstorm — favors moderate-to-high temperature paired with top-p, because the goal is genuine variety across generations, and a flatter distribution combined with an adaptive eligible set is what produces that variety without licensing outright incoherent tokens. Machine translation or another near-single-correct-output seq2seq task favors beam search with a modest beam width, because the task rewards finding the globally highest-likelihood full sequence, and there is little legitimate diversity worth preserving when only one translation is actually correct. A chatbot balancing coherence and some variety typically favors a moderate temperature with top-k or top-p, tuned empirically, rather than any of the extremes — pure greedy risks robotic repetition over a long conversation, while very high temperature with no truncation risks incoherent replies.

⭐ THE EARNED INSIGHT Every decoding strategy is answering one of three separable questions — which tokens are eligible, how sharply should eligible tokens be weighted, and which eligible token actually gets picked — and the exam's favorite trap is conflating two of those questions into one. Temperature and truncation feel like they should be the same knob because both make output "more focused" or "more diverse" in casual language, but one reshapes every probability and the other discards tokens outright, and knowing which question each strategy actually answers is what separates recognizing the mechanism from just recognizing the vocabulary.

[GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md): output sampling is covered under objective 1.4, "(d) Output Sampling for Decoders," within Domain 1 (LLM Architecture) — 6% of the blueprint, the smallest domain but foundational to how every later domain frames decoder behavior. The source states both of this lesson's central traps explicitly: "Temperature ≠ top-k/top-p. One reshapes, the others truncate," and "Beam search is not for diversity ... Greedy decoding is a special case of beam search with beam width 1."

Expect a mechanism-discrimination item: "You need the smallest token set whose cumulative probability exceeds a threshold. Which sampling method is this?" with top-p as the keyed answer against greedy, beam search, or temperature as distractors — [GROUND TRUTH] (Sources/ncp-genl/domain-1-llm-architecture.md) states this exact self-check item. Expect a reshape-vs-truncate item asking which of temperature, top-k, or top-p changes every probability in the distribution versus which discards tokens outright. Expect a beam-search-scope item testing whether beam search's likelihood-maximizing goal is mistaken for a diversity goal, particularly in an open-ended generation scenario where the keyed answer rejects widening the beam as a fix.

What the distractors typically look like

The standard traps in this lesson's style are: offering "increase the beam width" as a fix for repetitive or generic open-ended output, when wider beams search harder for likelihood and produce more of exactly that problem; describing temperature as truncating the candidate set, or top-k/top-p as reshaping every probability, swapping which operation belongs to which mechanism; and presenting greedy decoding and beam search as unrelated, competing methods rather than the same algorithm at two different beam widths.

Generally no, for the mechanical reason stated above: chatbot responses are open-ended, with many acceptable continuations rather than one near-correct target, and beam search's strength — finding the globally highest-likelihood sequence — tends to surface the most typical, least surprising continuation, which reads as flat or repetitive in open-ended text specifically because genuinely interesting human writing is not maximum-likelihood writing. Beam search remains a good fit for tasks closer to translation, where a near-single correct output does exist and sequence-level likelihood is a reasonable proxy for correctness.

No — they answer different questions and a very high temperature can make the truncation step more important, not less. A high temperature flattens the distribution, which means many more tokens end up with meaningfully non-trivial probability than at a lower temperature; without a top-k or top-p cutoff, that flattened distribution can hand real sampling weight to tokens that were only barely plausible to begin with, increasing the chance of an incoherent pick. Truncation and temperature are typically used together specifically because a very flat distribution is exactly the situation where bounding the eligible candidate set matters most.

• Decoding turns a per-step probability distribution into an actual token — five named strategies do this in five distinct ways.
• Temperature reshapes; top-k and top-p truncate — complementary operations, commonly applied together, never interchangeable.
• Beam search maximizes sequence-level likelihood, not diversity — it fits near-single-answer tasks like translation, and tends to flatten open-ended generation.
• Greedy decoding is beam search with beam width 1 — an exact identity, not a loose comparison.
• Top-p's eligible-set size adapts to the model's confidence at each step; top-k's does not — the mechanical reason the two are not simply interchangeable truncation rules.

Module 1 has now covered what a transformer layer computes (M1-01, M1-02), how its layers are arranged into architecture families with matching training objectives (M1-03), how to pull a usable numeric representation out of either family (M1-04), and how a decoder turns its output distribution into actual generated tokens (this lesson). None of that required changing a single weight or writing a single word of instruction to the model. The next module picks up exactly there: what a prompt, a few worked examples, or a decoding constraint can buy you without touching the weights at all, and when the honest answer is that you have exhausted what prompting can do and should fine-tune instead.