Text Decoding Strategies: Greedy, Beam Search, and Sampling

Scenario context

An LLM doesn't "write" text — it generates a probability distribution over all possible next tokens and then uses a decoding strategy to pick one. Greedy, Beam Search, and Sampling are different rules for that choice. Temperature controls the creativity knob.

TLDR: Greedy decoding is fast but repetitive; beam search improves quality at compute cost; temperature + top-p sampling trades determinism for…

This walkthrough focuses on The "Finish the Sentence" Game.

Before making a design choice, clarify:

• Imagine flashing the phrase "The dog jumps over the " to a crowd: - 60% shout "Fence" - 20% shout "Cat" - 15% shout "River" - 5% shout "Moon" The LLM does this for every single token.
• The question is: do you always pick "Fence" (greedy), do you explore multiple branches (beam search), or do you randomly sample from the crowd (sampling)?

Concepts in play: quantization-and-llm-inference, llm-prompt-engineering, sorting-and-searching-algorithms, vector-embeddings-and-similarity

Stage 1 — Core Concepts: Tokens, Logits, and Probability Distributions

• Before diving into how decoding strategies differ, it helps to understand exactly what is happening inside the model at each generation step.
• A token is not the same as a word.
• Modern LLMs use sub-word tokenization — common words become single tokens, but rarer or longer words get split into smaller pieces.
• For example, "unbelievable" might be tokenized as ["un", "believ", "able"] .

Observable outcome: For example, "unbelievable" might be tokenized as ["un", "believ", "able"] .

Stage 2 — The Three Core Strategies

• Greedy Decoding Always pick the single highest-probability token at each step.
• Pros: Fast, deterministic, reproducible.
• Cons: Locally optimal choices lead to globally suboptimal sequences.
• The model can paint itself into a corner — e.g., choosing "fence" first makes "and runs away" the natural continuation, even if "cat and runs away together" would have scored higher as a complete sentence.

Input: "The dog jumps over the"
Step 1: "fence" (highest probability token)
Output: "The dog jumps over the fence."

K=3 beams after step 1:
  Beam 1: "... fence" (log-prob: -0.5)
  Beam 2: "... cat"   (log-prob: -1.2)
  Beam 3: "... river" (log-prob: -1.8)

After step 2 (expand each beam):
  Beam 1a: "... fence and ..."  (-0.5 + -0.3)
  Beam 1b: "... fence to ..."   (-0.5 + -0.6)
  Beam 2a: "... cat and ..."    (-1.2 + -0.2)  ← might beat 1b!
  ...

Observable outcome: The model can paint itself into a corner — e.g., choosing "fence" first makes "and runs away" the natural continuation, even if "cat and runs away together" would have scored higher as a complete sentence.

Stage 3 — Temperature: The Creativity Dial

• Temperature $T$ reshapes the probability distribution before sampling: $$P i = \frac{\exp(z i / T)}{\sum j \exp(z j / T)}$$ Where $z i$ are the raw logit scores.
• Numerical example at $T = 0.5$ vs $T = 2.0$ for two tokens A (logit 2.0) and B (logit 1.0): This flowchart shows the three-step temperature pipeline: raw logits are divided by T (sharpening or flattening the distributio…
• Temperature is applied before sampling, which means it amplifies or suppresses the effect of top-p and top-k filtering downstream.
• At T→0 the softmax output collapses to a one-hot vector (greedy); at T 1 the distribution flattens and even low-probability tokens become viable candidates.

flowchart LR
    Logits[Raw Logits z_i] --> Temp[Divide by T]
    Temp --> Softmax[Softmax  Probabilities]
    Softmax --> Decode["Decoding Strategy (greedy / top-k / nucleus)"]
    Decode --> Token[Selected Token]

Observable outcome: At T→0 the softmax output collapses to a one-hot vector (greedy); at T 1 the distribution flattens and even low-probability tokens become viable candidates.

Stage 4 — Decoding Strategy Selection: Pipeline Flow

• Each token generation step applies the selected decoding strategy to transform raw logits into the next output token.

flowchart LR
    A[LLM Logits] --> B{Decoding Strategy?}
    B -->|Greedy| C[argmax token]
    B -->|Beam Search| D[Expand k beams]
    B -->|Sampling| E[Apply Temperature]
    E --> F{top-p or top-k filter}
    F --> G[Sample from distribution]
    D --> H[Prune to k beams]
    C --> I[Next Token]
    G --> I
    H --> I[Best-beam token]

Observable outcome: Each token generation step applies the selected decoding strategy to transform raw logits into the next output token.

Stage 5 — Real-World Applications of Decoding Strategies

• Different applications sit in very different parts of the decision tree above.
• Here is how major production use cases map to strategies: A note on production APIs: Most hosted LLM APIs (OpenAI, Anthropic, Google Gemini) do not expose beam search as a parameter.
• Their defaults are top-p sampling with temperature tuning.
• Beam search remains dominant in offline pipelines — machine translation frameworks (MarianMT, fairseq) and speech recognition (Whisper) — where running K beams is acceptable and sequence-level optimality is paramount.

flowchart TD
    Token[Next Token Position]
    Greedy["Greedy: argmax(logits)  one token, fastest"]
    BeamK[Beam Search: K=5  K parallel sequences K slower, best quality]
    TopK[Top-K: sample from K  balanced diversity/speed]
    TopP[Top-P: nucleus 0.9  dynamic vocab, diverse]
    Temp[Temperature T  reshapes distribution applied before sampling]

    Token --> Greedy
    Token --> BeamK
    Token --> TopK
    Token --> TopP
    TopK --> Temp
    TopP --> Temp

Observable outcome: Beam search remains dominant in offline pipelines — machine translation frameworks (MarianMT, fairseq) and speech recognition (Whisper) — where running K beams is acceptable and sequence-level optimality is paramount.

Stage 6 — Exploring Decoding Strategies in Practice

• Sampling Side-by-Side Use the HuggingFace transformers library to compare strategies on the same prompt: Run this five times.
• The greedy output is identical every run; the sampled output varies.
• Greedy outputs often start looping or repeating phrases after a few sentences — the classic symptom of locally optimal but globally poor token choices.
• Exercise 2 — Temperature Spectrum Generate five completions at T=0.1, T=0.7, and T=1.5 for the prompt "The future of AI is" .

from transformers import pipeline

gen = pipeline("text-generation", model="gpt2")
prompt = "The future of renewable energy is"

# Greedy decoding — deterministic, same result every run
greedy = gen(prompt, max_new_tokens=50, do_sample=False)

# Top-P nucleus sampling — varied output each run
sampled = gen(prompt, max_new_tokens=50, do_sample=True, top_p=0.9, temperature=0.8)

print("Greedy:", greedy[0]["generated_text"])
print("Sampled:", sampled[0]["generated_text"])

Observable outcome: Exercise 2 — Temperature Spectrum Generate five completions at T=0.1, T=0.7, and T=1.5 for the prompt "The future of AI is" .

End-to-end outcome

Imagine flashing the phrase "The dog jumps over the " to a crowd: - 60% shout "Fence" - 20% shout "Cat" - 15% shout "River" - 5% shout "Moon" The LLM does this for every single token.

Alternatives considered

Decision Guide: Decoding Strategy Selection

Choosing the right decoding strategy depends on three questions about your task: Does it need creativity?

Failure and degraded modes

Trade-offs & Failure Modes: When Strategies Go Wrong

• Detection: Each strategy has failure patterns worth knowing before you deploy:
• User or operator impact: Each strategy has failure patterns worth knowing before you deploy: