Beam Search Decoding
Why greedy decoding can be myopic
Greedy decoding picks the single best token at each step, but the locally best choice can lead to a globally worse sequence. A classic example: choosing a slightly lower-probability word early on might open up a much higher-probability continuation later, while the greedy first choice locks the model into a mediocre path. Since checking every possible sequence is exponential — $|V|^N$ for vocabulary size $|V|$ and length $N$ — beam search is a pragmatic compromise between exhaustive search and pure greediness.
How beam search works
Beam search maintains a fixed number of candidate sequences — the beam width $k$ — at every decoding step. At each step, it expands every current candidate by every possible next token, scores all resulting sequences (typically by cumulative log-probability), and keeps only the top $k$ scoring sequences to carry forward. This means the search explores $k$ parallel hypotheses simultaneously rather than committing to one, catching cases where a slightly-worse-looking early token leads to a much better overall sequence, without the combinatorial blowup of tracking every possible path.
import math
def beam_search(get_next_token_probs, start_token, beam_width=3, max_len=5, eos_token="</s>"):
"""get_next_token_probs(sequence) -> dict{token: probability}"""
beams = [([start_token], 0.0)] # (sequence, cumulative log-prob)
for _ in range(max_len):
candidates = []
for seq, score in beams:
if seq[-1] == eos_token:
candidates.append((seq, score))
continue
next_probs = get_next_token_probs(seq)
for token, p in next_probs.items():
candidates.append((seq + [token], score + math.log(p + 1e-12)))
candidates.sort(key=lambda x: x[1], reverse=True)
beams = candidates[:beam_width]
return max(beams, key=lambda x: x[1])
# Toy next-token distribution for illustration
def toy_probs(seq):
return {"cat": 0.4, "dog": 0.35, "</s>": 0.25} if len(seq) < 3 else {"</s>": 1.0}
best_seq, best_score = beam_search(toy_probs, "<s>", beam_width=2, max_len=4)
print(best_seq, round(best_score, 3))Beam search optimizes probability, not quality
Beam search vs sampling: different goals
Beam search is deterministic and optimizes for the highest-scoring sequence under the model's own probability estimates — it's well-suited to tasks with one clearly 'best' answer, like machine translation, where you want the single most faithful translation. Sampling-based decoding (temperature, top-k, top-p) deliberately introduces randomness, which is essential for open-ended generation like creative writing or chat, where there's no single correct continuation and diversity across generations is a feature, not a bug.
Beam search vs sampling-based decoding
| Property | Beam search | Sampling (top-k/top-p) |
|---|---|---|
| Determinism | Deterministic given beam width | Stochastic |
| Goal | Maximize sequence likelihood | Represent the distribution's diversity |
| Typical use | Translation, constrained generation | Chat, creative writing, open-ended tasks |
| Failure mode | Generic/short outputs without length normalization | Occasional low-quality or off-topic tokens |
Where beam search still shows up
Modern LLM chat applications almost never use beam search — sampling dominates because open-ended conversation rewards diversity over strict likelihood maximization. But beam search remains standard in constrained generation tasks: speech recognition transcript decoding, classical machine translation systems, and any setting where you need the single best-scoring sequence under a well-calibrated model rather than a representative sample from its distribution.
What's Next?
Both beam search and sampling choose a path through token space using only the model's own probabilities. The next frontier is using multiple full generations together — not just multiple candidates within one generation — to improve reliability on tasks that benefit from reasoning or self-checking.
I build these systems professionally.
Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.