Decoding Strategies: Greedy to Nucleus

A status assistant has one small-looking decision: finish The canary status is without turning a plausible token into a misleading incident update. A transformer gives its decoder a score for every next token, not a sentence.

Once those scores exist, decoding decides what reaches the user, one token at a time. That decision trades reproducibility, variety, and serving cost.

Keep this running example in view. Treat each word below as a single token. One model step might look like this:

Greedy decoding writes degraded because it wins this step. A sampling policy might write in and continue into in recovery; on could lead to on track.

Same model, same prompt, different policy, different sentence. The decoder is choosing how much uncertainty to let through.

For top-p sampling at p = 0.90, the first three tokens reach exactly 0.45 + 0.30 + 0.15 = 0.90. Sampling then renormalizes that retained mass, so degraded, in, and on have probabilities 0.50, 0.333..., and 0.166....

The boundary matters: a cutoff that drops the token that reaches the threshold changes both candidate set and draw probabilities.

The earlier decoding algorithms lesson built stable softmax from raw next-token scores (logits) and covered baseline greedy, sampling, truncation, and beam mechanics. This lesson turns those mechanics into product decisions. We will predict a policy's next move, inspect a small implementation, then use its failure mode to choose a setting.

Speculative decoding is a serving trick that drafts tokens for the target model to verify. It isn't a sampling policy, so it doesn't replace the choices below.^{[1]Reference 1Fast Inference from Transformers via Speculative Decoding.https://arxiv.org/abs/2211.17192}

Greedy decoding

Why can greedy decoding be bad even when it always picks the most likely next token?

Answer

The most likely next token is a local choice. It can lead the model into a generic or repetitive path even when a slightly less likely token would make the full answer more useful. In a status reply, that can mean writing "degraded." instead of entering "in recovery".

Greedy's weakness appears when a first-step winner leads to a weak continuation. Keep the same two leading tokens and give each a single continuation:

Argmax at step one writes degraded and never looks at the other prefix. Multiply each pair to inspect what that commitment hides: in recovery is the better two-token sequence.

The rule

Now name the policy. At each step, select the token with the highest probability:

$w_t = \arg\max_{w} P(w | w_{<t})$

The decoder scans the vocabulary, picks the winner, and commits. That costs $O(V)$ per step: one pass over $V$ candidates. There is no search or random draw. If the local winner starts a weak sentence, decoder has no route back.

Use greedy when variability is a bug: extraction, classification-style labels, or a tightly constrained status enum. Open-ended chat has a different objective.

Holtzman et al. show that maximum-likelihood decoding can drift toward bland, repetitive text, while human-written text often sits at higher perplexity than those high-likelihood beams.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751} DeepSeek-R1 reported a similar failure on long reasoning traces: greedy decoding raised repetition and varied across checkpoints, which is why its published pass@1 setup samples instead.^{[3]Reference 3DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.https://arxiv.org/abs/2501.12948}

Beam search

Greedy keeps one prefix. Beam search keeps B scored prefixes and expands each of them. That extra memory is useful when a slightly weaker first token may unlock a stronger continuation.

Exact search considers the full vocabulary (or a very large candidate set) at every beam, then retains the top-B extended sequences. A cheaper pruned expansion lets each beam propose only its own top-$B$ next tokens before global reselection. That shortcut can miss a high-scoring path that starts with a lower-ranked token, so it isn't exhaustive search.

Run width 2 on the same two-step status reply. Predict first: which prefix survives step one, and which full sequence should win after step two?

The result keeps degraded (0.45) and in (0.30) after step one, drops on (0.15), and returns in recovery at 0.27 after step two. Beam search recovered the path greedy discarded because it kept that second prefix alive.

Beam candidates can finish in two ways. An EOS token finalizes one early; hitting max_length finalizes every beam that is still active.

At the cutoff, compare completed and still-active candidates under the same score. A non-empty completed list can silently discard a truncated hypothesis that may be better.

Production decoders usually keep a finished flag on beams that remain in the active set and apply length normalization continuously, rather than only when a beam is moved aside.

Length penalty

Without a correction, longer sequences lose. Every extra token multiplies sequence probability by a value smaller than 1, making its log-probability more negative.

Google's Neural Machine Translation system divides sequence log-probability by a length term:

$\text{score}(Y) = \frac{\log P(Y)}{(5 + |Y|)^\alpha / 6^\alpha}$

When $\alpha = 0$, denominator is 1 and you are back to raw log-probability. Larger $\alpha$ reduces short-sequence bias.

Wu et al. first tried dividing by $\text{length}^\alpha$ and often landed near $0.6$ to $0.7$ on development data. The formula above is the later GNMT term.

In reported experiments they used $\alpha = 0.2$ with a separate coverage penalty $\beta = 0.2$ unless noted otherwise. Neither number is a universal default. Tune $\alpha$ on validation data for your model, stopping rule, and metric.^{[4]Reference 4Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.https://arxiv.org/abs/1609.08144}

The arithmetic below uses $\alpha = 0.6$ only to show ranking flip, not as a recommended setting. Watch which candidate wins before reading output.

A summarization model with beam width 8 keeps returning clipped one-line outputs instead of complete summaries. Which scoring term do you inspect first?

Answer

Inspect length normalization or length penalty first. Without it, beam search over-rewards short sequences because every extra token lowers sequence probability, so the beam prefers prematurely ending outputs.

When a wider beam hurts

Beam search fits outputs with a constrained target meaning: translation, structured summarization, and some structured extraction. Open-ended chat is usually a poor fit. Holtzman et al. show that high-likelihood paths in open-ended generation are often generic and repetitive.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

There is a second warning even for machine translation. Meister et al. find that under a plain maximum a posteriori (MAP) objective, quality can drop as beam width grows. Searching farther into high-probability sequences can move you closer to a mode that is not the text people prefer.^{[5]Reference 5If Beam Search is the Answer, What was the Question?.https://arxiv.org/abs/2010.02650}

Width also has a serving cost. A width-$B$ search keeps up to $B$ active continuations. Efficient runtimes batch those hypotheses and reorder their KV-cache state, but larger beams still increase decoder work and memory relative to greedy.

For how that cache sits in the inference pipeline, wait until that later chapter. The practical rule is simple: pay for a wide beam only when the task wants sequence search.

Temperature scaling

Beam search asks which sequence scores highest. Sampling asks a different question: how much uncertainty should survive at each step?

Return to The canary status is. The original probabilities are 0.45, 0.30, 0.15, 0.02, and 0.08. Temperature $T$ changes their shape by acting on logits $z$ before softmax:

$P(w_i) = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}$

If you already have probabilities, renormalizing each individual $P_i^{1/T}$ is equivalent. It is not equivalent if you first glue the tail into one bucket and then raise that bucket to $1/T$.

The table and figure below aggregate the tail on purpose so you can compare five readable numbers across temperatures. A real decoder never aggregates the tail first; it divides each token's logit by $T$.

Read the columns as a prediction about variance. At $T = 0.3$, sampling usually still writes degraded; at $T = 1.5$, on and even broken are in play.

As $T \to 0$, the draw collapses toward greedy. As $T \to \infty$, it approaches uniform over the vocabulary.

As a separate edge case, zero is not a valid divisor. Route temperature=0 to deterministic decoding instead of sending it through sampling math.

Dividing logits by $T < 1$ stretches differences, so the top token takes more mass. Dividing by $T > 1$ compresses those differences. Temperature is a global sharpness knob.

Temperature sees neither retrieved evidence nor factual support, and it leaves the tail in play. Put a temperature sweep beside task metrics, not in their place:

Why should one global temperature be questioned in evaluation?

Answer

Different endpoints tolerate different variance. Status lookup and rollback eligibility prioritize grounded accuracy; creative drafting may value variety. Evaluate sampler settings per task slice rather than accepting a single preset without measurements.

Top-k sampling

Temperature still leaves the whole vocabulary in play. Top-k sampling, popularized for neural story generation, keeps only the $k$ most probable tokens, then renormalizes and samples.^{[6]Reference 6Hierarchical Neural Story Generation.https://arxiv.org/abs/1805.04833}

On the canary-status step, $k = 2$ keeps degraded and in, then drops on, broken, and the tail. Their 0.45 and 0.30 weights become 0.60 and 0.40 after renormalization.

The fixed count is both top-k's appeal and its weakness. Ask how peaked each context is before choosing $k$:

When the distribution is peaked, $k = 50$ drags in dozens of irrelevant tail tokens. A high temperature can give that tail enough mass to be drawn.

When distribution is flat, $k = 10$ can cut off valid continuations. The count ignores confidence, which is why later methods moved to a dynamic cutoff.

Why does top-k fail differently on peaked and flat distributions?

Answer

Top-k always keeps the same number of tokens. On a peaked distribution, a large k admits irrelevant tail tokens. On a flat distribution, a small k cuts off valid alternatives. The fixed count ignores how confident the model is.

Nucleus (top-p) sampling

Top-k with $k = 50$ keeps fifty tokens even when two are plausible or when hundreds deserve a look. Nucleus sampling, also called top-p, changes the question from “how many?” to “how much mass?”

It keeps adding highest-probability tokens until cumulative mass reaches threshold $p$.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

Using the same canary-status table, $p = 0.80$ includes degraded, in, and on (cumulative 0.90) and excludes broken plus the tail. If degraded had 0.85, nucleus would be one token.

$$V_p = \{w_{(1)}, \ldots, w_{(m)}\}, \qquad m = \min \left\{j : \sum_{i=1}^{j} P(w_{(i)}) \ge p \right\}$$

Here $w_{(i)}$ are sorted by decreasing probability. After truncation, divide each kept probability by kept mass so nucleus sums to 1.

At fixed $p = 0.90$, survivor count is a function of distribution shape, not a hidden constant:

Real nucleus size also depends on model, tokenizer, prompt, and temperature. The threshold stays fixed; candidate count moves with confidence.

The long-tail failure at high $T$

Top-p has a failure mode to measure at high temperatures ($T > 1$). Flattening gives many weak tokens enough combined mass to enter the cumulative set.

A $p = 0.9$ nucleus can therefore get large even when no individual tail token is a good next word. That is one motivation for confidence-scaled cutoffs such as min-p.

Why can top-p admit too much tail at high temperature?

Answer

High temperature flattens the distribution, so many weak tokens gain enough combined probability mass to enter the cumulative top-p set. The nucleus can become large even though many individual tokens are poor choices.

Beyond nucleus: min-p

Top-p asks how many ranked tokens are needed to cover a chosen mass. Min-p asks a different question: is each token strong enough relative to the best token? Keep tokens whose probability is at least a fraction $\rho$ of that peak.

A dominant top token sets a high bar; a weak top token lowers it. The cutoff follows relative confidence, not a fixed cumulative sum. Nguyen et al. (ICLR 2025 oral) define the kept set as:^{[7]Reference 7Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082}

$V_{\min\text{-}p} = \{w : P(w) \geq \rho \cdot \max_v P(v)\}$

If the top token has probability 0.80 and $\rho = 0.1$, anything below 0.08 is dropped. If the top token has only 0.05, the bar falls to 0.005, so more alternatives survive.

Use the figure as a prediction test. On a peaked split, which rule should keep the fewest candidates? On a flatter split, which rule should expand its set? The same token names make the three answers easy to compare.

Run the small implementation after making that prediction. It returns survivors before any renormalization, so the threshold is visible in isolation.

Min-p is a newer truncation heuristic to evaluate, not a settled replacement for nucleus sampling. Nguyen et al. propose it for the high-temperature tail that top-p can admit.^{[7]Reference 7Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082}

A later critical reanalysis reports that min-p did not reliably improve quality-diversity tradeoffs against commonly used samplers in its experiments, and disputes broad adoption claims.^{[8]Reference 8Min-p, Max Exaggeration: A Critical Analysis of Min-p Sampling in Language Modelshttps://arxiv.org/abs/2506.13681}

Treat any published setting, including DeepSeek-R1's temperature 0.6 with top-p 0.95 pass@1 configuration, as an experiment input for that model, not a preset for yours.^{[3]Reference 3DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.https://arxiv.org/abs/2501.12948}

Repetition penalty

When a generated answer loops, the sampler is reusing tokens that remain too attractive:

"The deploy rolled back. The deploy rolled back. The deploy rolled..."

CTRL introduced penalized sampling: discount logits of tokens already in the generated list. Keskar et al. reported that near-greedy sampling with $\theta \approx 1.2$ balanced truthful generation against repetition in their experiments.^{[9]Reference 9CTRL: A Conditional Transformer Language Model for Controllable Generation.https://arxiv.org/abs/1909.05858}

Their original rule scales the logit of a seen token through a temperature multiplier $\theta$. Modern runtimes expose related variants; inspect the transform instead of inferring it from the name.

Common runtimes such as Hugging Face Transformers expose a related sign-aware processor.

For a repeated token, divide a positive logit by the penalty and multiply a negative logit by it. Both move down in preference rather than toward zero. See RepetitionPenaltyLogitsProcessor.

The function below mirrors that runtime behavior:

Token 0 was positive, so the penalty divides it (2.4 / 1.2 = 2.0). Token 1 was negative, so the penalty multiplies it (-0.5 × 1.2 = -0.6). Token 2 never appeared, so its logit stays unchanged.

A naive “divide every seen logit” rule would move -0.5 toward zero and make that token more likely. The sign branch is the important detail.

Frequency and presence penalties

A different pair of controls changes how often a token has appeared:

$\text{logit}_{\text{adjusted}} = \text{logit} - \alpha \cdot \text{count}(\text{token}) - \beta \cdot \mathbb{1}[\text{count}(\text{token}) > 0]$

The frequency penalty $\alpha$ grows with each reuse: five copies of a token cost $5\alpha$. The presence penalty $\beta$ is a one-time hit after first appearance, which pushes the model off a topic rather than off a word.

Exact formulas and defaults vary by stack. Neither knob repairs a missing fact. They only make already-seen tokens less attractive.

Combining strategies in production

At each generation step, a production system may stack several logit transforms, then branch into deterministic or stochastic selection. Before reading the diagram, predict where a temperature=0 request should go.

1. Start with raw logits.
2. Apply processors such as penalties, banned-token masks, or forced-token constraints.
3. If the policy is deterministic, take argmax on the adjusted logits.
4. If the policy samples, warp with temperature, then truncate with top-k, top-p, or min-p, then draw.

That list is a conceptual path, not a universal contract. Exact order is implementation-specific.

Some stacks apply temperature before truncation; others place temperature later. Don't memorize one canonical chain. Know that these controls are layered transforms, and read the stack you are shipping.

You move a chat product to a new inference engine and outputs change even though temperature and top-p stayed the same. What sampler detail do you verify first?

Answer

Verify the exact order of penalties, masks, temperature, truncation, and sampling. There is no universal sampler order across frameworks, so the same knobs can behave differently when those transformations are applied in a different sequence.

Use the next figure as a dry run of that stack. degraded already appeared in the prompt, so a 1.2 penalty drops it from 2.4 to 2.0, below in at 2.1. Greedy now emits in.

After softmax, the penalized logits are approximately in 0.404, degraded 0.365, on 0.164, and broken 0.067. A $p = 0.90$ nucleus keeps the first three (cumulative 0.933) and drops broken.

The illustrated sample is on, inside the nucleus but not the mode. That is the point of a sampling path: its draw need not be argmax.

Runnable code uses that same conceptual order: penalty, then a greedy branch at temperature 0, otherwise temperature plus nucleus sampling.

random.Random(0) makes the sampled token reproducible in this lesson.

With seed 0, the sampled path lands on on, matching the figure. Nucleus sampling can redraw the mode or another kept token.

on is one legal draw from this nucleus, not a second deterministic answer.

Evaluation configurations

The first four rows are candidate sweeps, not recommended defaults. Compare them on held-out prompts. The right settings depend on model, tokenizer, task, and measured failure costs.

Choosing a policy by task

Choose a policy from the output contract, not from a favorite knob. First decide how much output variance the endpoint can tolerate and which failures cost most. Then compare candidates on task metrics, repetition, format validity, and latency.

The first five rows choose how candidates are searched or sampled. Temperature and repetition penalty modify that choice. A modifier can improve one symptom while making another worse, so evaluate the stack together.

What to check before moving on

Use these pass bars as predictions you can defend from examples, not as settings to memorize.

Common failures and fixes

Beam search made chat sound robotic

Answers became safer and more repetitive after you increased beam width. Inspect the objective first: beam search is pushing toward a most likely overall continuation, which is often generic in open-ended dialogue.

Keep beam search for translation or tightly grounded summarization, where several candidate paths can help. For chat, switch back to sampling and tune temperature plus truncation against a quality and latency target.

Temperature tweak didn't fix hallucinations

You lowered temperature, but the model still states wrong facts confidently. Temperature changes distribution sharpness, not factual grounding. If the model lacks evidence, a wrong continuation can still be high probability.

Keep decoding conservative for factual tasks, but fix retrieval, prompt grounding, or output constraints. Temperature is not a truth knob.

High temperature plus top-p pulled in nonsense tail tokens

Creative mode started producing weird fragments or off-topic words. Higher temperature flattened the distribution, so top-p admitted a long tail of individually weak candidates.

Lower temperature, tighten top-p, or test min-p. Min-p makes the cutoff track strength of the best token instead of only cumulative mass.

Fixed top-k clipped valid options

Outputs stayed narrow on creative prompts and erratic on factual prompts with the same k. Top-k uses the same cutoff in every shape: too small in flat contexts and too large in peaked ones.

Treat top-k as a simple baseline. Compare top-p or min-p when candidate-set size should react to model confidence.

Same knobs changed behavior after a runtime swap

Another engine gives different outputs even with matching documented settings. Sampler order, defaults, or special cases such as temperature=0 can differ across implementations.

Inspect the actual sampler path and log intermediate logits if needed. Validate representative prompts before blaming model weights.

temperature=0 was sent through the sampling math directly

The runtime crashes, returns NaNs, or behaves inconsistently when someone sets temperature to zero. The implementation divided logits by zero instead of treating temperature=0 as a greedy special case.

Handle temperature=0 explicitly as deterministic decoding. Keep sampling path only for temperatures greater than zero.

Truncated probabilities no longer sum to one

Logged or returned survivor probabilities sum to less than one after truncation. Tail probabilities were set to zero, but downstream code still expects a normalized distribution. Some sampling APIs accept unnormalized nonnegative weights; metrics and probability contracts expect normalized probabilities.

Mask logits with negative infinity and run softmax again, or divide surviving probabilities by remaining mass before returning them.

Practice drill

Create one decoding audit table for three production routes: a factual status answer, a creative incident narrative, and code completion. Each route has a different cost for variance, so run its experiment separately instead of letting one global preset decide.

1. Pick baseline settings for temperature, top-p or top-k, repetition penalty, and stop conditions.
2. Write two failure examples per route: one too deterministic, one too random or unsupported.
3. Compare outputs under at least three setting changes, then mark accuracy, diversity, latency, and parseability.
4. Choose one launch setting per route and write the rollback trigger that would force you to change it.

Finish by recording an evaluation-backed decoding policy for each task, model, and tokenizer. The record should explain which failure the setting is meant to prevent and which measurement would make you revisit it.