Beam Search Explained: How LLMs Pick Tokens

Beam search is a decoding strategy that keeps several of the most promising partial sequences alive at each step of text generation, instead of committing to a single “best next token” the way greedy decoding does. By exploring a small set of candidate paths in parallel — the “beam” — and pruning down to the top ones after each step, it finds sequences that score better overall than picking the locally best token every single time.

The problem with greedy decoding

The simplest way to generate text from a language model is greedy decoding: at each step, pick whichever token has the highest probability, append it, and repeat. It’s fast and simple, but it’s shortsighted — the single highest-probability token right now might lead down a path where every subsequent token is mediocre, while a slightly lower-probability token now could have opened up a much better overall sequence. Greedy decoding has no way to look ahead or reconsider, because it never explores any option other than its single top pick.

How beam search explores more of the tree

Beam search fixes this by tracking multiple candidate sequences — the beam width, often denoted k — simultaneously:

1. At the first step, take the top k most probable next tokens as k separate candidate sequences.
2. At each following step, expand every candidate sequence by considering its next-token possibilities, then keep only the k highest-scoring sequences overall (scored as the cumulative probability, usually log-probability, of the sequence so far).
3. Repeat until each sequence reaches an end token or a maximum length.
4. Return the highest-scoring completed sequence (or all k, depending on the use case).

With k = 1, beam search is identical to greedy decoding — there’s only one candidate to track, so nothing changes. As k grows, more of the possibility space stays open at each step, which generally improves output quality, at the direct cost of k times the compute per step, since every candidate sequence needs its own forward pass through the model.

Beam search vs sampling-based decoding

Modern conversational language models mostly don’t use beam search for open-ended generation — they use sampling methods instead, controlled by parameters like temperature, top-p, and top-k. The reason is a known failure mode: beam search optimizes for the single most probable sequence, which for open-ended text tends to produce bland, repetitive, overly generic output — the statistically safest words, strung together, rarely make for interesting writing. Sampling deliberately introduces controlled randomness, trading some of that “most probable” guarantee for output that reads as more natural and varied.

Beam search remains the better fit for tasks with one clearly correct or near-correct answer, where you want the most probable overall sequence rather than a creative one — translation, transcription, and structured tasks like tool/function calling still lean on beam search or close variants, because there genuinely is a “best” output to converge on rather than many equally valid ones.

Beam search vs greedy decoding vs sampling

	Greedy decoding	Beam search	Sampling (temperature/top-p)
Candidates tracked	1	k (beam width)	1, but with randomness
Compute cost	Lowest	k× higher	Same as greedy
Output tends toward	Locally optimal, sometimes poor overall	Globally higher-probability sequence	Varied, natural-sounding
Best for	Quick, low-stakes generation	Translation, transcription, structured output	Open-ended writing, conversation
Risk	Gets stuck in bad local choices	Bland, repetitive text	Can wander off-topic at high randomness

Why this still matters for understanding LLMs

Even though most user-facing chat products default to sampling, beam search is worth understanding because it clarifies what “generating text” actually is under the hood: a search problem over an enormous tree of possible token sequences, where the model provides probabilities at each branch and the decoding strategy decides how much of that tree to actually explore. It’s the same underlying mechanism referenced whenever tokenization or reasoning models come up — a model produces a probability distribution one token at a time, and everything about output quality, cost, and behavior downstream of that depends on which algorithm decides which tokens actually get chosen. Speculative decoding is a different technique aimed at speed rather than quality, but it operates on the same token-by-token generation loop that beam search and greedy decoding do.

The takeaway

Beam search keeps the top k candidate sequences alive at each decoding step instead of greedily committing to one token at a time, which finds higher-probability overall sequences at the cost of k times the compute. It’s largely been superseded by sampling-based decoding for open-ended chat, where the single most probable sequence tends to read as bland rather than good, but it remains the right tool whenever a task has one genuinely correct answer to converge on, like translation or transcription.