Decoding Strategies: Greedy to Nucleus

Transformer internals eventually produce logits. Decoding strategy controls how that final probability distribution becomes one visible completion. Compare greedy decoding, beam search, temperature sampling, top-k, nucleus sampling, and min-p so you can tune output quality intentionally.

An incident-status assistant that hasn't chosen its next token yet may assign a 70% chance to stable, a 20% chance to degraded, and a 10% chance to rollback. Language models do this at every generation step: they produce raw scores for many possible next tokens, convert those scores into probabilities, then use a decoding policy to pick what appears on screen.

That final choice has real product consequences. Runbook assistants usually need stable, factual phrasing, while brainstorming tools need more variety. Code generators often benefit from determinism; story generators may sound lifeless if they always pick the highest-probability token. Decoding is the control surface that turns the same model distribution into those different behaviors.

For how decoding fits into the broader inference pipeline and techniques like speculative decoding, see those articles. Speculative decoding accelerates generation by asking a draft model to propose tokens that the target model can verify in parallel.^{[1]Reference 1Fast Inference from Transformers via Speculative Decoding.https://arxiv.org/abs/2211.17192}

---

How LLMs Choose the Next Token

To compare strategies, first inspect what happens inside the model at each generation step.

Autoregressive generation

LLMs generate text one token at a time. They predict the next token, append it to the prompt, and repeat. This is called autoregressive generation (auto = self, regressive = predicting the next step from previous ones).

At every step the model outputs a vector of raw scores called logits, one score per token in the vocabulary. A function called softmax converts those logits into probabilities that sum to 1. The decoding strategy then decides which token to emit.

A concrete probability distribution

Suppose the prompt so far is "The canary status is". Use this plausible probability distribution for the very next token:

These numbers are fabricated for clarity. Logits are shown only for named candidates; omitted tail tokens jointly carry the final probability mass. One token (degraded) leads the pack, a few others are plausible, and many individually weak tokens share the tail.

Greedy decoding is like picking the best-looking decode branch right now. It may lead into a dead end after the next token. Beam search keeps several branches alive in parallel and picks the sequence with the best total score at the end. The locally optimal choice isn't necessarily the globally best sequence.

The question is: given this distribution, how do we pick the next token? And how does that choice change the whole sentence?

---

Greedy Decoding and Its Trap

Why the most likely next word isn't the best sentence

The simplest strategy is greedy decoding: at every step, pick the single most probable token and commit to it.

Using the table above, greedy decoding chooses degraded. The sentence becomes:

"The canary status is degraded"

That's a fine sentence. But greedy decoding can fail when the best next word leads to a worse overall sentence. Imagine a slightly different distribution where degraded is most likely, but needs followed by review produces a more useful completion. Greedy doesn't explore that possibility because it locks in degraded immediately.

This is the greedy trap: the locally best token doesn't imply the globally best sequence. A first token with slightly lower probability can lead to a stronger full answer after the next step.

Human-written text often doesn't follow the model's single most likely continuation. Holtzman et al. show that maximum-likelihood decoding can drift toward bland, repetitive text, which is why pure argmax-style decoding often doesn't sound human.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

The algorithm

At each step, select the token with the highest probability:

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

Reading the formula

At each step, look at every possible next token, pick the one with the highest probability, and commit to it. Simple and fast, but myopic: the next-token winner can still start a weak full sequence.

This basic PyTorch implementation assumes a single prompt in the batch, a model whose forward call returns .logits, and an integer EOS token ID. The loop repeatedly takes the argmax token and stops when it reaches EOS or the maximum number of decoding steps:

Strengths

• Deterministic and fast: $<span data-glossary="big-o-notation">O(V)</span>$ per step (single argmax over vocabulary)
• Useful baseline for constrained tasks: classification-style outputs or extraction when output variability is undesirable

Limitations

• Suboptimal globally: The locally best token doesn't imply the best sequence
• Repetitive in open-ended generation: Maximum-likelihood decoding can fall into loops or generic output in evaluated settings.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

---

Beam search

Algorithm

Instead of keeping only the best token, maintain B (beam width) candidate sequences, expanding each by the top-k tokens. This simplified PyTorch snippet assumes batch size 1, a model whose forward call returns .logits, and the highest-scoring partial sequences at every step. For readability, it leaves out batching and length normalization, which appear in the next subsection:

An EOS token finalizes a beam early. Reaching max_length also finalizes every beam that is still active, but labels it as truncated in a full implementation. Selection must compare both sets under the same scoring rule. Returning completed whenever that list is non-empty silently discards active candidates at the cutoff, even when one has the best score.

Length penalty

One common length penalty, used in the Google Neural Machine Translation system, is:^{[3]Reference 3Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.https://arxiv.org/abs/1609.08144}

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

Reading the formula

Without correction, longer sequences receive lower unnormalized probability as each extra token multiplies the sequence probability by a value smaller than 1. The exponent $\alpha$ controls how strongly you compensate for that short-sequence bias. When $\alpha = 0$, there's no correction. Larger values reduce the bias toward short completions.

Tune $\alpha$ on a validation set. It isn't a universal translation or summarization default: the right value depends on model behavior, stopping criteria, and the task metric.

When to use beam search

• Good fit: machine translation. The output usually has one target meaning to preserve.
• Good fit: structured summarization. The output should stay close to source evidence.
• Poor fit: open-ended chat or creative writing. High-likelihood paths often become generic.

Counterintuitively, beam search with larger beams can produce more likely but less interesting text.^{[4]Reference 4If Beam Search is the Answer, What was the Question?.https://arxiv.org/abs/2010.02650} In open-ended generation, increasing beam width can reduce output quality because the most probable sequence is often generic and repetitive.

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

---

Temperature scaling

What temperature does

Before adding randomness, you need a dial that controls how much randomness to allow. Temperature is that dial. It reshapes the probability distribution before we sample from it.

Return to our running example. The raw model gives us these probabilities for the next token after "The canary status is":

This is what happens when we apply different temperatures and then run softmax:

For this worked table only, the tail is treated as one aggregated category and each original probability is reshaped proportionally to $P_i^{1/T}$ before renormalization. A real decoder divides each individual token logit by $T$ before softmax; it never aggregates the tail first. At $T = 0.3$, degraded is so dominant that sampling usually picks it. At $T = 1.5$, the probabilities spread out, and even broken becomes a possible sample. As $T \to 0$, decoding collapses toward greedy argmax. As $T \to \infty$, the distribution approaches uniform.

Temperature controls distribution sharpness like a sampler strictness dial. Low temperature ($T < 1$) keeps the model focused on the top choices. High temperature ($T > 1$) spreads probability across more tokens, allowing less common recovery actions when the situation is ambiguous.

The formula

Temperature modifies the logit distribution before softmax (the function that converts raw model scores into probabilities):

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

Reading the formula

Divide the raw logits by temperature $T$ before applying softmax. When $T < 1$, the division amplifies differences between logits, making the top choice even more dominant. When $T > 1$, it compresses differences, spreading probability more evenly across options. An implementation should special-case temperature=0 as deterministic decoding rather than divide by zero.

This function applies temperature scaling to raw logits. It divides logits by the temperature before they pass through softmax. A temperature below 1.0 sharpens the distribution; a value above 1.0 flattens it:

Mathematical intuition

Entropy measures how spread out a probability distribution is:

$H(P) = -\sum_i p_i \log_2 p_i$

Low entropy means most probability sits on a few candidates. Higher entropy means more candidates carry meaningful mass. The illustration computes entropy over the same five displayed buckets, including the aggregated tail bucket, so its values are directly comparable across temperatures.

Why it works

Dividing logits by $T < 1$ amplifies differences between logits, making the distribution peakier. When $T > 1$, the same operation shrinks differences, making probabilities more similar. This controls the sharpness of the sampling distribution.

Starting sweep candidates

---

Top-k Sampling

Algorithm

Top-k sampling was popularized in neural story generation as a way to restrict sampling to the top $k$ most probable tokens, then renormalize the distribution.^{[5]Reference 5Hierarchical Neural Story Generation.https://arxiv.org/abs/1805.04833} The running example shows how that restriction changes the distribution.

Suppose the model gives these probabilities after the prompt "The canary status is":

With top-k where $k = 2$, we keep only degraded and in, renormalize their probabilities to sum to 1, and sample from that smaller set. on, broken, and the tail are locked out.

This implementation of top-k sampling limits the probability distribution to only the $k$ most likely next tokens. It masks out all other tokens by setting their logits to negative infinity before applying softmax and sampling from the remaining probability mass:

The fixed-k problem

The primary limitation of top-k sampling is its rigidity. A useful value for $k$ varies sharply depending on the context of the generation:

When the distribution is highly peaked, a large $k$ like 50 forces the sampler to include dozens of irrelevant tail tokens. If the temperature is high, those tail tokens can accumulate enough probability mass to be selected, causing off-topic generation. Conversely, when the distribution is flat, a small $k$ like 10 can cut off valid continuations and make the output too narrow. This inability to adapt to distribution shape motivated dynamic truncation approaches.

---

Nucleus (top-p) Sampling

Algorithm

Top-k keeps exactly 50 candidate tokens if $k = 50$, even when only two are plausible or hundreds deserve consideration. Top-p keeps adding candidate tokens until their cumulative probability covers the requested mass. On an easy incident-status reply, only a few candidates qualify; on an ambiguous escalation, the candidate set is much longer. This dynamic threshold adapts naturally to each context.

Instead of fixing $k$, dynamically select the smallest high-probability prefix whose cumulative probability reaches or exceeds threshold $p$. This approach, also known as nucleus sampling, addresses the fixed candidate-count limitation of top-k.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

Using the same probability table:

With top-p where $p = 0.8$, we include tokens until the cumulative probability reaches 0.8. That means degraded, in, and on are in the nucleus. broken and the tail are excluded. If the distribution were more peaked and degraded had 0.85 probability, the nucleus would contain only that one token.

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

where $w_{(i)}$ are sorted by decreasing probability.

Reading the formula

Sort all tokens by probability, then include tokens from the top until their cumulative probability reaches $p$ (e.g., 0.9). On easy predictions where one token has 95% probability, only that token qualifies. On hard predictions where many tokens share probability, a large set is included. The candidate set adapts to the distribution shape.

Nucleus sampling is straightforward to implement in PyTorch. The function sorts the logits, computes cumulative probability mass, masks away tokens outside the nucleus, and then samples from the renormalized distribution:

How distribution shape changes nucleus size

At the same $p = 0.9$ threshold, the number of survivors depends entirely on the probabilities presented at that generation step:

The threshold stays fixed while the candidate count changes. Real nucleus size depends on the model, tokenizer, prompt, temperature, and exact probability shape.

Top-p's weakness: the long tail problem

Top-p has a failure mode to evaluate at high temperatures ($T > 1$): temperature flattening can cause many individually weak tokens to enter the cumulative-mass set. In those settings, a $p = 0.9$ nucleus can expand substantially. This is one motivation for newer confidence-scaled variants such as min-p.

---

Beyond nucleus: min-p

The insight

Top-p ranks candidate next tokens and keeps enough of them to cover 90% of total probability mass. Concentrated probability produces a small shortlist; spread-out probability produces a long one. Min-p instead says "only keep candidates whose probability is at least 10% of the top-ranked candidate." A dominant top candidate sets a high bar. A weak top candidate lowers the bar. The threshold adapts to relative peak probability, not a fixed cumulative cutoff.

Min-p, proposed by Nguyen et al. and published as an ICLR 2025 oral paper, scales the cutoff by the top token's probability instead of using a cumulative-mass threshold:^{[6]Reference 6Turning 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)\}$

Reading the formula

Find the most likely token, then keep tokens whose probability is at least $\rho$ fraction of that top token's probability. If the top token has 80% probability and $\rho = 0.1$, tokens above 8% are kept. If the top token has 5%, the bar drops to 0.5%, adapting to distribution shape.

What min-p changes relative to top-p

The min-p sampling function dynamically calculates a threshold based on the maximum probability in the distribution. It takes raw logits, a min_p scaling factor, and a temperature as inputs. The function applies temperature, zeroes out token probabilities that fall below the dynamic threshold (calculated as min_p times the maximum probability), and renormalizes before returning a sampled token:

When to think about min-p

Min-p is a newer truncation heuristic to evaluate, rather than a universal successor to nucleus sampling. Nguyen et al. propose it for controlling low-probability candidates admitted by top-p at higher temperatures.^{[6]Reference 6Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082} A subsequent critical reanalysis reports that min-p didn't reliably improve quality-diversity tradeoffs against commonly used samplers in its experiments and disputes broad adoption claims.^{[7]Reference 7Min-p, Max Exaggeration: A Critical Analysis of Min-p Sampling in Language Modelshttps://arxiv.org/abs/2506.13681} Meanwhile, DeepSeek-R1 reports temperature 0.6 with top-p 0.95 in one published evaluation configuration.^{[8]Reference 8DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.https://arxiv.org/abs/2501.12948} Treat any of these settings as experiment inputs, not presets for a different model or product.

---

Repetition penalty

The problem

Autoregressive models can fall into degenerate repetition, where the generation process gets stuck in a loop. For example, a model might repeatedly generate the same phrase:

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

How the penalty works

CTRL introduced penalized sampling and reported that a penalty around 1.2 balanced truthful generation against repetition in its experiments.^{[9]Reference 9CTRL: A Conditional Transformer Language Model for Controllable Generation.https://arxiv.org/abs/1909.05858} Common runtimes such as Hugging Face Transformers expose a related sign-aware logit processor: divide positive repeated-token logits and multiply negative repeated-token logits by the penalty, moving both downward in preference. This function mirrors that runtime behavior without mutating its input tensor:

Frequency and presence penalties

A common formulation is:

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

Reading the formula

Two knobs discourage repetition. The frequency penalty $\alpha$ grows with each use: if a token appears 5 times, it gets 5 times the penalty. The presence penalty $\beta$ is a flat one-time penalty the moment a token is used at all, encouraging topic diversity. Exact formulas and defaults vary by stack, but this captures the core idea.

---

Combining Strategies in Production

In practice, production systems stack several logit transformations together. The high-level mental model is stable:

1. Start with raw logits.
2. Apply logit processors such as penalties, masks, or forced-token constraints.
3. Branch by policy. Deterministic decoding takes argmax from the adjusted logits.
4. A sampling path applies warpers such as temperature, top-k, top-p, or min-p, then samples from the surviving distribution.

The exact order is implementation-specific. Some stacks apply temperature before truncation, while others place temperature later in the sampler chain. In interviews, don't memorize one canonical order. Know that these controls are layered transformations of the logits, and check the implementation of the stack you're using.

This concrete stack makes that layered mental model visible on one next-token step.

This tested mini-pipeline shows one common pattern: apply repetition penalty, special-case greedy decoding when temperature=0, otherwise scale logits and sample from a top-p nucleus. Min-p fits into the same slot as top-p in real systems.

Evaluation configurations

The first four rows are candidate sweeps, not recommended defaults. The right settings depend on the model, tokenizer, task, and measured failure costs.

---

Practice: debug this output

Use this short debugging exercise without running code. Read the symptoms, identify the likely cause, and pick a fix.

Scenario 1: Repetitive boilerplate

• Symptom: An incident chatbot keeps ending every reply with the same generic closing sentence, repeated twice.

• Likely cause: The repetition penalty is set to 1.0 (no penalty) or temperature is so low that the model keeps rediscovering the same high-probability closing phrase.

• Experiment: Compare a mild repetition penalty against a slightly wider sampling distribution on held-out replies, tracking task correctness and loop rate.

Scenario 2: Gibberish at high creativity

• Symptom: A brainstorming assistant set to temperature=1.5 and top_p=0.95 occasionally outputs tokens that don't form real words, like "flarble" or "xquz."

• Likely cause: At high temperature the distribution flattens, and top-p's cumulative threshold pulls in a long tail of very low-probability tokens. Some of those are nonsense.

• Experiment: Hold temperature fixed and compare a tighter top-p value against min-p; measure coherence and diversity instead of assuming one filter improves both.

Scenario 3: Factual QA drifts

• Symptom: A runbook assistant answering "What is the rollback policy?" sometimes says "Rollback blocked" or "Rollbacks are unlimited."

• Likely cause: Temperature is too high for a factual task, or top-p is so wide that unlikely but wrong answers get sampled.

• Fix: First improve grounding or output constraints, then compare conservative decoding settings on an accuracy evaluation. Lower temperature can't repair a wrong high-probability answer.

---

Choosing a policy by task

When choosing a decoding strategy for a new application, first determine whether output variance is allowed and which failures matter. Then compare candidate algorithms on task metrics, repetition, format validity, and latency.

What to check before moving on

---

What to remember

• Decoding shapes quality: The choice of decoding strategy (deterministic vs. stochastic) changes whether the model output tends toward precision and repetition or diversity and creativity.
• A useful mental progression: Start with static truncation (top-k), then dynamic mass-based truncation (nucleus/top-p), then newer confidence-scaled variants such as min-p.
• Likelihood isn't generation quality: Holtzman et al. show that maximization-based decoding can produce repetitive, bland open-ended text even when likelihood is high.^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}
• Temperature vs. Truncation: Temperature ($T$) modifies the shape of the distribution (sharpness), while top-p/min-p modify the tail (truncation). They are orthogonal controls used together.
• Sampler order is framework-specific: Treat decoding as layered logit transformations, not one universal ordering rule. Check the implementation of the stack you're using.

Common failures and fixes

Beam search made chat sound robotic

• Symptom: Answers became safer and more repetitive after you increased beam width.

• Likely cause: Beam search is pushing toward the most likely overall continuation, which is often generic in open-ended dialogue.

• Fix: Use beam search for translation or tightly grounded summarization. For chat, switch back to a sampling strategy and tune temperature plus truncation instead.

Temperature tweak didn't fix hallucinations

• Symptom: You lowered temperature, but the model still states wrong facts confidently.

• Likely cause: Temperature changes distribution sharpness, not factual grounding. If the model lacks evidence, it can still choose a wrong but high-probability continuation.

• Fix: Keep decoding conservative for factual tasks, but fix retrieval, prompt grounding, or output constraints rather than treating temperature as a truth knob.

High temperature plus top-p pulled in nonsense tail tokens

• Symptom: Creative mode started producing weird fragments or off-topic words.

• Likely cause: Higher temperature flattened the distribution, so top-p admitted a long tail of individually weak candidates.

• Fix: Lower temperature, tighten top-p, or test min-p so the cutoff tracks the strength of the best token.

Fixed top-k clipped valid options

• Symptom: Outputs stayed narrow in creative prompts and erratic in factual prompts with the same k.

• Likely cause: Top-k doesn't adapt to distribution shape. The same cutoff is too small in flat contexts and too large in peaked ones.

• Fix: Treat top-k as a simple baseline. Compare top-p or min-p when candidate-set size should react to distribution shape.

Same knobs changed behavior after a runtime swap

• Symptom: Another engine gives different outputs even with matching documented settings.

• Likely cause: Sampler order, default values, or special cases such as temperature=0 differ across implementations.

• Fix: Inspect the actual sampler path, log intermediate logits if needed, and validate behavior on representative prompts before blaming the model.

temperature=0 was sent through the sampling math directly

• Symptom: The runtime crashes, returns NaNs, or behaves inconsistently when someone sets temperature to zero.

• Likely cause: The implementation divided logits by zero instead of treating temperature=0 as a greedy special case.

• Fix: Handle temperature=0 explicitly as deterministic decoding, and keep the sampling path only for temperatures greater than zero.

Truncated probabilities no longer sum to one

• Symptom: Logged or returned survivor probabilities sum to less than one after truncation.

• Likely cause: Tail probabilities were set to zero, but code that consumes or reports probabilities still expects a normalized distribution. Some sampling APIs accept unnormalized nonnegative weights, but metrics and probability contracts usually don't.

• Fix: Either mask logits with negative infinity and run softmax again, or divide surviving probabilities by their remaining mass before returning them.

---

Sources and further study

The papers behind these techniques are cited throughout the article: Holtzman et al. (2020) on neural text degeneration,^{[2]Reference 2The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751} Meister et al. (2020) on beam search paradox,^{[4]Reference 4If Beam Search is the Answer, What was the Question?.https://arxiv.org/abs/2010.02650} Fan et al. (2018) on top-k sampling,^{[5]Reference 5Hierarchical Neural Story Generation.https://arxiv.org/abs/1805.04833} Wu et al. (2016) on GNMT beam-search length normalization,^{[3]Reference 3Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.https://arxiv.org/abs/1609.08144} and Nguyen et al. (2025) on min-p as a newer confidence-scaled variant,^{[6]Reference 6Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs.https://arxiv.org/abs/2407.01082} along with a 2025 critical reanalysis that questions min-p's reported gains.^{[7]Reference 7Min-p, Max Exaggeration: A Critical Analysis of Min-p Sampling in Language Modelshttps://arxiv.org/abs/2506.13681}

Related articles

• Inference Mechanics: TTFT, TPS, and KV Cache - How decoding fits into the broader inference pipeline.
• Speculative Decoding - Accelerating generation by drafting tokens with a smaller model.
• Perplexity and Language Model Evaluation - Understanding why human text has high perplexity.

Practice drill

Create a decoding audit table for three production routes: factual policy answer, creative merchandising copy, and code completion.

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.

Good decoding work ends with an eval-backed operating policy, not a favorite temperature.