Greedy vs Beam Search vs Sampling
Three ways to decode tokens from a language model
Greedy is fastest but repetitive; beam is best for closed-ended tasks like translation; sampling with temperature and top-p is the default for open-ended generation.
Greedy Decoding
Glossary →Pick the highest-probability token at every step. Deterministic and fastest, but prone to repetition and blandness on open-ended tasks.
Best for: Deterministic short outputs (classification, extraction).
Beam Search
Glossary →Track the top-k partial sequences ('beams') and expand each at every step, keeping the best k by cumulative log-prob. Better for closed-ended tasks with a single correct answer.
Best for: Closed-ended generation like translation and summarization.
Sampling (temperature, top-p, top-k)
Glossary →Draw the next token from the model's distribution, usually after truncating to top-k or top-p and scaling logits by temperature. The modern default for creative or open-ended chat.
Best for: Open-ended chat and creative generation.
At a glance
| Dimension | Greedy Decoding | Beam Search | Sampling (temperature, top-p, top-k) |
|---|---|---|---|
| Determinism | Deterministic | Deterministic (fixed k) | Stochastic |
| Cost | 1× per token | k× per token | 1× per token |
| Diversity | None | Low | Tunable |
| Repetition risk | High | Medium | Low with top-p / top-k |
| Best task | Extraction, classification | Translation, summarization | Chat, creative writing |
| Default in practice | Rare (except deterministic tests) | Uncommon in LLMs | Standard for chat |
Key differences
- 1Greedy is deterministic; sampling is stochastic; beam is deterministic but multi-hypothesis
- 2Beam search is expensive (k× compute) and produces bland output on open-ended tasks
- 3Temperature scales probability mass; top-p and top-k truncate the tail
- 4Modern chat almost always uses sampling with temperature ~0.7 and top-p ~0.9
- 5Greedy is beam search with k=1
In the interview
- Recommending beam search for open-ended chat
- Confusing temperature with top-p (they compose but do different things)
- Ignoring that greedy is deterministic and useful for evaluation reproducibility
How to choose
Short and deterministic → greedy. Closed-ended → beam. Chat or creative → sampling.
Common misconceptions
Myth: Beam search always produces better outputs.
Reality: For open-ended generation it often produces shorter, blander text because higher log-prob is not the same as better output.
Myth: Temperature 0 is the same as greedy.
Reality: In practice yes at the sampling boundary, but numerical issues at temperature ~0 can differ from a true argmax; APIs that expose greedy explicitly are safer for reproducibility.
Memory aid
Greedy: always the top choice. Beam: keep k parallel drafts. Sampling: roll dice weighted by the model.
Can you combine them?
You can chain: sample the first N tokens for diversity then switch to greedy; or use beam sampling variants like nucleus-constrained beam search. Contrastive decoding blends greedy with an anti-model to reduce repetition.