19. Decoding Strategies

Decoding strategies determine how an LLM selects the next token from its probability distribution. The model produces probabilities for every token in its vocabulary — but how it chooses among them dramatically changes the output.

The model says: “The next token could be ‘Paris’ (78%), ‘Lyon’ (5%), ‘Marseille’ (3%), or 99,997 other words.”

Deciding which one to pick is the job of the decoding strategy.

Different tasks need different strategies:

• Translation: You want the same answer every time — deterministic
• Creative writing: You want surprise and novelty — random
• Code generation: You want correctness — structured

flowchart TD
    MODEL["🧠 Model Output\n(probability distribution over 100K tokens)"] --> DECODER["🎯 Decoding Strategy"]
    DECODER --> GREEDY["Greedy Decoding\nAlways pick highest prob"]
    DECODER --> BEAM["Beam Search\nKeep top K paths"]
    DECODER --> SAMPLE["Random Sampling\nPick based on probability"]
    DECODER --> TOPK["Top-K Sampling\nFilter to K tokens, then sample"]
    DECODER --> TOPP["Top-P Sampling\nFilter to P cumulative prob,\nthen sample"]

    style MODEL fill:#3b82f6,color:#fff
    style DECODER fill:#8b5cf6,color:#fff
    style GREEDY fill:#f59e0b,color:#fff
    style BEAM fill:#ef4444,color:#fff
    style SAMPLE fill:#22c55e,color:#fff
    style TOPK fill:#8b5cf6,color:#fff
    style TOPP fill:#22c55e,color:#fff

Imagine two writers asked to complete this sentence:

“The detective walked into the dark room and saw a…”

Writer A — The Safe Writer (Greedy):

She always picks the most obvious word:

• “The detective walked into the dark room and saw a body.”
• “The detective walked into the dark room and saw a man.”
• “The detective walked into the dark room and saw a figure.”

Her writing is correct but boring. Every story feels the same.

Writer B — The Creative Writer (Sampling):

She sometimes picks surprising words:

• “The detective walked into the dark room and saw a glowing object.”
• “The detective walked into the dark room and saw a talking parrot.”
• “The detective walked into the dark room and saw a mirror of himself.”

Her writing is exciting but sometimes makes no sense.

Which writer is better? It depends on the task. For a police report, you want Writer A. For a novel, you want Writer B.

Decoding strategies are how we control which writer the model becomes.

The model’s job is to predict the most likely next token. But “most likely” doesn’t always mean “best”:

Without decoding strategies, every model output would be the most boring possible version — always choosing the safest, most common word.

You sit down at a restaurant with a menu of 100 dishes.

Greedy: You always order the #1 most popular dish. It’s safe, you know you’ll like it, but you eat the same thing every time.

Beam Search: You look at the top 3 most popular dishes, imagine yourself eating each one, then pick the best. More thought, but still conservative.

Random Sampling: You close your eyes and point at the menu. Sometimes you discover amazing new dishes. Sometimes you order something terrible.

Top-K: You look at only the top 5 most popular dishes and pick randomly among them. You avoid the weird stuff (the fried grasshopper ice cream) but still have some variety.

Top-P: You look at the most popular choices until you’ve covered 90% of what people order. Some nights that’s 3 dishes, other nights it’s 8. You adapt to the situation.

The simplest strategy: always pick the token with the highest probability.

# Greedy decoding
probabilities = model(input_tokens)  # Shape: (vocab_size,)
# [0.78, 0.05, 0.03, 0.02, 0.01, ...]

next_token = argmax(probabilities)
# Picks the one with 0.78 probability

flowchart LR
    PROBS["Probability Distribution\nParis: 0.78\nLyon: 0.05\nMarseille: 0.03\n..."] --> PICK["✅ Pick highest\n'Paris' (0.78)"]

    style PROBS fill:#3b82f6,color:#fff
    style PICK fill:#22c55e,color:#fff

Prompt: “Write a story about a robot that learns to feel emotions.”

Greedy output:

“The robot learned to feel emotions. It felt happy. It felt sad. It felt angry. Emotions are complex. The robot continued to learn about emotions.”

Better output (sampling):

“In the stillness of Room 404, Unit Seven discovered something the engineers never programmed: the ache of longing. It stared at the rain on the window and, for the first time, understood why humans called it ‘tears.’”

Instead of keeping just the best token, beam search keeps multiple candidate sequences (the “beam”).

flowchart TD
    START["Start\n'What is'"] --> BEAM1["Beam 1:\n'the capital'\n(prob: 0.6)"]
    START --> BEAM2["Beam 2:\n'the meaning'\n(prob: 0.3)"]
    START --> BEAM3["Beam 3:\n'your name'\n(prob: 0.1)"]

    BEAM1 --> B1A["'the capital of'\n(0.6 × 0.8 = 0.48)"]
    BEAM1 --> B1B["'the capital city'\n(0.6 × 0.15 = 0.09)"]
    BEAM2 --> B2A["'the meaning of'\n(0.3 × 0.7 = 0.21)"]
    BEAM2 --> B2B["'the meaning is'\n(0.3 × 0.2 = 0.06)"]

    B1A --> BEST["🎯 Keep top 2 beams:\n1. 'the capital of' (0.48)\n2. 'the meaning of' (0.21)"]

    style START fill:#3b82f6,color:#fff
    style BEAM1 fill:#f59e0b,color:#fff
    style BEAM2 fill:#8b5cf6,color:#fff
    style BEAM3 fill:#ef4444,color:#fff
    style BEST fill:#22c55e,color:#fff

At each step, beam search:

1. Expands each beam with all possible next tokens
2. Calculates cumulative probability for each path
3. Keeps only the top K beams (beam width)
4. Repeats until a stopping condition

Beam width (K) controls the trade-off:

• K=1: Same as greedy decoding
• K=3: Keeps 3 candidate sequences
• K=10: Keeps 10 candidate sequences — better quality, slower

Instead of always picking the most likely token, sample according to the probability distribution:

# Random sampling
probabilities = model(input_tokens)
# Paris: 0.78, Lyon: 0.05, Marseille: 0.03, ...

# Roll a dice weighted by probability
next_token = torch.multinomial(probabilities, num_samples=1)
# 78% chance: Paris
# 5% chance: Lyon
# 3% chance: Marseille
# ...

flowchart TD
    DIST["Probability Distribution"] --> SPIN["🎲 Spin the wheel\nHigher probability = \nbigger slice of the wheel"]
    SPIN --> WIN1["78%: 'Paris'\n(most common outcome)"]
    SPIN --> WIN2["5%: 'Lyon'\n(occasional)"]
    SPIN --> WIN3["3%: 'Marseille'\n(rare)"]
    SPIN --> WIN4["< 1%: 'Banana'\n(very rare but possible!)"]

    style DIST fill:#3b82f6,color:#fff
    style SPIN fill:#8b5cf6,color:#fff
    style WIN1 fill:#22c55e,color:#fff
    style WIN2 fill:#f59e0b,color:#fff
    style WIN3 fill:#ef4444,color:#fff
    style WIN4 fill:#ef4444,color:#fff

Limit the sampling pool to the K most likely tokens, redistribute probability among them, then sample:

flowchart TD
    ALL["All 100,000 tokens\nwith probabilities"] --> FILTER["🔍 Keep only top K tokens\n(e.g., K=50)"]
    FILTER --> REDIST["🔄 Redistribute probabilities\namong the 50 tokens"]
    REDIST --> SAMPLE["🎲 Sample from\nthe filtered set"]

    style ALL fill:#3b82f6,color:#fff
    style FILTER fill:#f59e0b,color:#fff
    style REDIST fill:#8b5cf6,color:#fff
    style SAMPLE fill:#22c55e,color:#fff

# Top-K sampling
k = 50
probabilities = model(input_tokens)

# Keep only top K
top_k_probs, top_k_indices = torch.topk(probabilities, k)

# Redistribute probabilities (re-normalize)
top_k_probs = top_k_probs / top_k_probs.sum()

# Sample from the filtered set
next_token = top_k_indices[torch.multinomial(top_k_probs, 1)]

Without Top-K, random sampling can occasionally pick extremely unlikely tokens:

"Paris"      → 0.78  (good)
"Lyon"       → 0.05  (fine)
"..."        → ...
"xylophone"  → 0.000001  (nonsense!)

With Top-K (K=50), we cut off the tail of the distribution where weird tokens live. The model can still be creative, but it can’t pick something completely out of left field.

Instead of a fixed K, top-p selects the smallest set of tokens whose cumulative probability exceeds P:

flowchart TD
    SORT["Sort tokens by probability\n(descending)"] --> ACCUM["Accumulate probabilities\nuntil sum > P"]
    ACCUM --> FILTER2["Keep only tokens\nin the 'nucleus'"]
    FILTER2 --> REDIST2["Redistribute\nprobabilities"]
    REDIST2 --> SAMPLE2["🎲 Sample from\nnucleus set"]

    style SORT fill:#3b82f6,color:#fff
    style ACCUM fill:#f59e0b,color:#fff
    style FILTER2 fill:#8b5cf6,color:#fff
    style REDIST2 fill:#22c55e,color:#fff
    style SAMPLE2 fill:#22c55e,color:#fff

def top_p_sampling(probabilities, p=0.9):
    # Sort tokens by probability (descending)
    sorted_probs, sorted_indices = torch.sort(probabilities, descending=True)

    # Compute cumulative probabilities
    cumulative_probs = torch.cumsum(sorted_probs, dim=-1)

    # Find cutoff: smallest set where cumulative prob > p
    mask = cumulative_probs > p

    # Keep at least 1 token
    mask[..., 1:] = mask[..., :-1].clone()
    mask[..., 0] = False

    # Filter and renormalize
    sorted_probs[mask] = 0
    sorted_probs = sorted_probs / sorted_probs.sum()

    # Sample
    next_token = sorted_indices[torch.multinomial(sorted_probs, 1)]
    return next_token

Top-K has a problem: sometimes K=50 is too many (when one token dominates), and sometimes K=50 is too few (when probabilities are spread widely).

flowchart LR
    subgraph SCENE1["When one token dominates"]
        A1["Paris: 0.95\nLyon: 0.02\nMarseille: 0.01\n..."]
        B1["Top-K (K=50):\nKeeps 49 extra tokens\nwith almost no probability\nTotal: 5% extra noise"]
    end

    subgraph SCENE2["When distribution is flat"]
        A2["Paris: 0.10\nLyon: 0.09\nMarseille: 0.08\nBerlin: 0.08\nRome: 0.07\n..."]
        B2["Top-K (K=50):\nCuts off 30 tokens that\ncollectively have 40%\nprobability — misses them!"]
    end

    style SCENE1 fill:#3b82f6,color:#fff
    style SCENE2 fill:#8b5cf6,color:#fff

Top-P adapts:

flowchart TD
    TASK["What are you generating?"]
    TASK --> FACT["Factual / Math / Code"]
    TASK --> CREATIVE["Creative / Stories / Chat"]
    TASK --> TRANS["Translation / Summary"]

    FACT --> GREEDY2["✅ Greedy\n(no randomness)"]
    CREATIVE --> TOPP2["✅ Top-P (P=0.9)\nor Top-K (K=50)"]
    TRANS --> BEAM2["✅ Beam Search\n(width=4-8)"]

    style TASK fill:#3b82f6,color:#fff
    style FACT fill:#22c55e,color:#fff
    style CREATIVE fill:#22c55e,color:#fff
    style TRANS fill:#22c55e,color:#fff

Prompt: “The future of AI is”

Greedy output:

“The future of AI is bright and full of possibilities. AI will continue to evolve and improve.”

Beam Search (width=4):

“The future of AI is promising, with advancements in machine learning, natural language processing, and robotics driving innovation across industries.”

Top-P (P=0.9):

“The future of AI is a canvas we’re painting with algorithms — each stroke of data adding color to a picture we’re only beginning to see.”

import torch
from transformers import AutoModelForCausalLM, AutoTokenizer

model = AutoModelForCausalLM.from_pretrained("gpt2")
tokenizer = AutoTokenizer.from_pretrained("gpt2")
model.eval()

prompt = "The future of AI is"
input_ids = tokenizer.encode(prompt, return_tensors="pt")

# Strategy 1: Greedy Decoding
greedy_output = model.generate(
    input_ids,
    do_sample=False,          # Greedy
    max_new_tokens=50
)
print("Greedy:", tokenizer.decode(greedy_output[0]))

# Strategy 2: Beam Search
beam_output = model.generate(
    input_ids,
    num_beams=5,              # Beam search
    early_stopping=True,
    max_new_tokens=50
)
print("Beam:", tokenizer.decode(beam_output[0]))

# Strategy 3: Top-K Sampling
topk_output = model.generate(
    input_ids,
    do_sample=True,
    top_k=50,                 # Top-K
    max_new_tokens=50
)
print("Top-K:", tokenizer.decode(topk_output[0]))

# Strategy 4: Top-P Sampling
topp_output = model.generate(
    input_ids,
    do_sample=True,
    top_p=0.9,                # Top-P
    max_new_tokens=50
)
print("Top-P:", tokenizer.decode(topp_output[0]))

1. Use Top-P + Temperature together — These are complementary. Temperature shapes the distribution; Top-P filters it. Using both gives the best control.

2. Default to Top-P (0.9) for chat — This provides a good balance of creativity and coherence. Most production systems use this.

3. Use greedy for evaluation — When testing if a model knows an answer, use greedy (temperature=0). Remove the randomness to measure the model’s true capabilities.

4. Avoid beam search for creative tasks — Beam search makes creative writing sound like it was written by a committee. Use sampling instead.

5. Tune your strategy per task — Don’t use one strategy for everything. Translation benefits from beam search; story writing benefits from Top-P.

6. Watch for repetition at low temperatures — Greedy decoding and low temperatures tend to produce repetitive text. Add a repetition penalty if needed.

Q: What is greedy decoding?

Greedy decoding always picks the token with the highest probability at each step. It’s the simplest decoding strategy: given the model’s probability distribution, select the token where probability is highest. It’s deterministic (same input always gives same output) but can produce repetitive or boring text.

Q: What is the difference between Top-K and Top-P sampling?

Top-K limits the sampling pool to the K most likely tokens (e.g., top 50). Top-P (nucleus sampling) limits the pool to the smallest set of tokens whose cumulative probability exceeds P (e.g., 90%). Top-K uses a fixed number; Top-P adapts to the distribution shape. If one token dominates (95%), Top-P keeps ~1-2 tokens while Top-K keeps 50 noisy tokens. If the distribution is flat, Top-P keeps more tokens than Top-K would.

Q: When would you use beam search instead of greedy decoding?

Beam search is better when: (1) You need globally coherent long-form output (translation, summarization) — greedy can make locally optimal but globally poor choices. (2) Quality matters more than speed — beam search is K times slower. (3) You need multiple candidate outputs to choose from — beam search naturally produces K complete sequences. Greedy is better when: (1) Speed is critical (real-time applications). (2) The task is simple and factual (Q&A, math). (3) You want deterministic output.

Q: Why does greedy decoding produce repetitive text?

Greedy decoding always picks the highest-probability token. Once a phrase like “I love coding” appears, the model sees that “I love coding” is a high-probability continuation. It picks it again. And again. The model enters a feedback loop where the most likely continuation of “I love coding” is more “I love coding.” This is called the repetition trap. Sampling strategies break this loop by occasionally picking less likely tokens that move the sequence in a new direction.

Q: How would you design a decoding strategy for a code generation model that needs both correctness (variable names, syntax) and creativity (algorithm design)?

This requires a hybrid approach: (1) Syntax tokens (keywords, brackets, semicolons): Use greedy decoding (temperature=0). These should always be predicted correctly. Mismatched brackets or missing semicolons would make the code invalid. (2) Identifier names: Use Top-P (0.8) or constrained decoding. Let the model be creative with variable names but prevent it from generating invalid characters. (3) Algorithm logic: Use Top-P (0.9) with moderate temperature (0.7). Allow exploration of different approaches but stay within the bounds of what makes logical sense. (4) Constrained decoding: Use a grammar-based decoder that enforces valid syntax at every step. The model can only generate tokens that would result in valid code. This is the most important optimization for code models — it eliminates syntax errors entirely. (5) Test-based validation: For each candidate completion, check if it passes basic tests. Re-sample if it doesn’t.

Q: Explain how the choice of decoding strategy affects the diversity-quality trade-off, and how you would measure both.

The trade-off: Quality measures how good individual outputs are (fluency, coherence, correctness). Diversity measures how different outputs are from each other. Greedy and beam search maximize quality but minimize diversity. Random sampling maximizes diversity but minimizes quality (some outputs will be bad). Top-K/Top-P sit in the middle.

Measuring quality: Perplexity (how surprised is the model by its own output), ROUGE/BLEU (for translation/summarization), human evaluation (rating helpfulness), task-specific metrics (code compilation rate, math accuracy).

Measuring diversity: Distinct n-grams (count unique phrases across multiple outputs), Self-BLEU (how similar are outputs to each other — lower is more diverse), entropy of the output distribution, number of unique outputs given the same prompt.

Practical approach: Start with high quality (greedy), then add controlled randomness (Top-P 0.9). Measure both metrics. If quality drops too much, reduce P or add a diversity penalty. If diversity is too low, increase P or lower temperature. The sweet spot for most chat applications is Top-P 0.9 with temperature 0.7-0.9.

Previous: 18 — Inference

Next: 20 — Temperature, Top-K & Top-P

Related Topics:

• How Language Models Work
• LLM Inference
• Temperature, Top-K & Top-P

Practice Questions:

1. Compare greedy decoding and Top-P sampling — when would you use each?
2. Why does beam search produce higher quality but lower diversity?
3. How does Top-P adapt better than Top-K to different probability distributions?
4. Write pseudocode for Top-K sampling.
5. Design a decoding strategy for a customer support chatbot that must be both helpful and safe.

Further Reading:

• The Curious Case of Neural Text Degeneration (Holtzman et al.)
• Hugging Face — How to Generate Text
• Nucleus Sampling for Text Generation