Decoding Strategies: Greedy to Nucleus

The previous deep dives followed information through transformer internals until the model produced logits. Decoding strategy controls how that final probability distribution becomes one visible completion. This chapter compares greedy decoding, beam search, temperature sampling, top-k, nucleus sampling, and min-p so you can tune output quality intentionally.

Imagine an order-status assistant that hasn't chosen its next token yet. Internally, it may assign a 70% chance to shipped, a 20% chance to delayed, and a 10% chance to refunded. 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. A support bot usually needs stable, factual phrasing. A brainstorming tool needs more variety. A code generator often benefits from determinism, while a story generator may sound lifeless if it picks the highest-probability token every time. 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]

---

How LLMs Choose the Next Token

Before we compare strategies, we need to see 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 carrier scan shows the package is". Here is a 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 (delayed) leads the pack, a few others are plausible, and many individually weak tokens share the tail.

Greedy decoding is like picking the best-looking warehouse route right now. It might lead to a hub cutoff you can't meet. Beam search is like keeping several route plans alive in parallel and picking the one with the best total arrival time at the end. The locally optimal choice isn't necessarily the globally best route.

The question we'll answer in this article 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 delayed. The sentence becomes:

"The carrier scan shows the package is delayed"

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 delayed is most likely, but in followed by transit produces a much more natural and informative completion. Greedy doesn't explore that possibility because it locks in delayed immediately.

This is the greedy trap: the locally best token doesn't imply the globally best sequence. It's like a delivery driver who repeatedly takes the fastest next street and ends up in a traffic jam, while a slightly slower first turn would have opened a clear highway.

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]

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, similar to choosing the next warehouse hop without checking whether the full route can still meet the SLA.

Here is a basic implementation of greedy decoding in PyTorch. It 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: $O(V)$ 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]

---

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 we'll cover in the next subsection:

Length penalty

One common length penalty, used in the Google Neural Machine Translation system, is:^[3]

$\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.

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] In open-ended generation, increasing beam width can reduce output quality because the most probable sequence is often generic and repetitive.

---

Temperature Scaling

What temperature does

Before we add randomness, we 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 carrier scan shows the package is":

Here 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$, delayed 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 routing strictness dial. Low temperature ($T < 1$) keeps the sampler focused on the top choices, like a fulfillment router that picks the safest carrier. High temperature ($T > 1$) spreads probability across more tokens, like 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.

The following 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

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] Let's walk through it with our running example.

Suppose the model gives these probabilities after the prompt "The carrier scan shows the package is":

With top-k where $k = 2$, we keep only delayed 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 order-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 exceeds threshold $p$. This approach, also known as nucleus sampling, addresses the fixed candidate-count limitation of top-k.^[2]

Using the same probability table:

With top-p where $p = 0.8$, we include tokens until the cumulative probability reaches 0.8. That means delayed, in, and on are in the nucleus. broken and the tail are excluded. If the distribution were more peaked and delayed 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.

Here is how nucleus sampling is implemented in PyTorch. The function sorts the logits, computes cumulative probability mass, masks away tokens outside the nucleus, and then samples from the renormalized distribution:

Why many systems start around $p = 0.9$

Top-p adapts to the distribution shape: flatter distributions produce larger candidate sets.

Those counts are heuristics, not guarantees. The actual nucleus size depends on the model, tokenizer, prompt, and temperature.

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. If probability is concentrated in a few actions, the shortlist stays small. If probability is spread out, the shortlist gets long. Min-p instead says "only keep candidates whose probability is at least 10% of the top-ranked candidate." If that candidate is dominant, the bar is high. If it is weak, the bar is lower. 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]

$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] 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] Meanwhile, DeepSeek-R1 reports temperature 0.6 with top-p 0.95 in one published evaluation configuration.^[8] 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 order shipped late. The order shipped late. The order shipped..."

How the penalty works

The repetition penalty originates in CTRL, which applies a penalty greater than 1 to previously generated tokens and uses 1.2 in its reported sampling setup.^[9] A sign-aware multiplicative rule divides positive repeated-token logits and multiplies negative repeated-token logits, moving both downward in preference. The function below implements that rule 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. Apply sampling warpers such as temperature, top-k, top-p, or min-p.
4. Sample the next token, or take argmax for deterministic decoding.

The exact order is implementation-specific. Some stacks apply temperature before truncation, while others place temperature later in the sampler chain. In interviews, the important point isn't memorizing one canonical order. It's knowing that these controls are layered transformations of the logits, and you should check the implementation of the stack you're using.

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

The following 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

Here is a short debugging exercise you can reason through without running code. Read the symptoms, identify the likely cause, and pick a fix.

Scenario 1: Repetitive boilerplate

Symptom: A customer-service chatbot keeps ending every reply with "Please let me know if you need anything else. Please let me know if you need anything else."

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 support bot answering "What is your return policy?" sometimes says "No returns accepted" or "Returns 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.

---

The Complete Comparison

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.

Follow-up questions

A code assistant became repetitive after you lowered temperature from 0.8 to 0.2, but correctness stayed good. What sampler change comes first?

Add a mild repetition or frequency penalty before raising temperature again. The immediate problem is looped phrasing, not loss of task accuracy, so stay in the decoding stack first and only widen temperature if the penalty isn't enough.

A translation benchmark improves with beam width 5, but chat quality gets worse. Why is that not a contradiction?

Translation has a narrow target meaning, so keeping several high-probability candidates helps recover a better full sequence. Chat has many acceptable answers, so larger beams often over-optimize for generic high-likelihood continuations and drain personality from the response.^[4]

High-temperature brainstorming still feels oddly narrow after you set top_k=10. What is wrong with that setup?

Top-k is a fixed cutoff. With a flat creative distribution, k=10 may still exclude many reasonable alternatives. Compare dynamic filters such as top-p or min-p on the target distribution rather than increasing temperature alone.

A new model starts producing nonsense tail tokens at temperature=1.4 and top_p=0.95. Why might min-p help?

At high temperature, many individually weak tokens can enter a top-p nucleus because their cumulative mass adds up. Min-p ties the cutoff to the top token's probability, so if the model still has a clear best candidate, more of the tail gets dropped.

Same sampler knobs, new runtime, different answers. What is your debugging plan?

Log the actual sampler path: penalties, masks, temperature, truncation, and final token choice. Verify operation order, default values, special handling of temperature=0, and any engine-specific processors. Treat the runtime as code to inspect, not a black box that must share another framework's semantics.

What You Should Be Able To Defend

---

Key Takeaways

• 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]
• 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: The right mental model is layered logit transformations, not one universal ordering rule. Check the implementation of the stack you're using.

Common pitfalls

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.

Top-p masked tokens but didn't renormalize survivors

Symptom: Sampling looks biased or unstable even though the nucleus cutoff seems correct.

Likely cause: Tokens outside the nucleus were removed, but the remaining probabilities weren't renormalized before sampling.

Fix: After masking the tail, renormalize the surviving probabilities so the sampler draws from a valid distribution.

---

Going Deeper

The papers behind these techniques are cited throughout the article: Holtzman et al. (2020) on neural text degeneration,^[2] Meister et al. (2020) on beam search paradox,^[4] Fan et al. (2018) on top-k sampling,^[5] Wu et al. (2016) on GNMT beam-search length normalization,^[3] and Nguyen et al. (2025) on min-p as a newer confidence-scaled variant,^[6] along with a 2025 critical reanalysis that questions min-p's reported gains.^[7]

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.