Beam Search

Every time a language model finishes your sentence, translates a paragraph, or writes a caption for a photo, it faces the same impossible-sounding challenge: pick one sequence of words from an astronomically large space of possibilities. A vocabulary of 50,000 tokens and a sentence of twenty words yields 50,$000^{20}$ candidates — more arrangements than atoms in the observable universe.

The naive fix is greedy search: at each step, pick the single most likely next token and commit. It is blazing fast, but it is myopic — a locally brilliant choice can trap the decoder in a globally mediocre sentence.

Beam search is the middle path. At every step it keeps not one but K candidates (the "beam"), extending each by every possible next token and then keeping only the K best-scoring continuations. When the beam width K = 1 you get greedy search; as K grows you approach exhaustive search — but even with K = 5 or 10, the algorithm is orders of magnitude cheaper than brute force.

The price is optimality: beam search is not guaranteed to find the highest-probability sequence. The cost is also diversity: a narrow beam can produce repetitive, over-confident output. Yet this controlled approximation has been the dominant decoding strategy in neural machine translation and large language models since around 2015 — a pragmatic bet that the best K candidates carry most of the probability mass.

The tree below has branch factor 3 and depth 3. Each edge carries a cost (lower is better). Beam search keeps only the top-K paths by cumulative cost at each level, discarding the rest.

Change the beam width with the buttons, then press Run to watch the algorithm step through the tree. Notice how a narrow beam misses the globally optimal path while a wider beam finds it — at the cost of considering more nodes.

<div class="controls">
  <span class="label">{{beam_width_label}}</span>
  <button class="bw-btn active" data-k="1">1</button>
  <button class="bw-btn" data-k="2">2</button>
  <button class="bw-btn" data-k="3">3</button>
  <button id="run-btn" type="button">{{run_btn}}</button>
  <button id="reset-btn" type="button" class="ghost">{{reset_btn}}</button>
</div>
<div class="step-info" id="step-info">{{press_run}}</div>
<svg id="tree-svg" viewBox="0 0 540 320" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="result" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
.label { font-size: .85rem; color: #555; }
.bw-btn { font: 600 14px system-ui; padding: .3rem .7rem; border: 1.5px solid #1d3557;
          background: #fff; color: #1d3557; border-radius: 6px; cursor: pointer; }
.bw-btn.active { background: #1d3557; color: #fff; }
button { font: 600 14px system-ui; padding: .35rem .8rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.step-info { font-size: .88rem; color: #444; min-height: 1.5em; margin-bottom: .3rem; }
#tree-svg { width: 100%; height: auto; display: block; }
.result { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .4rem; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }

// Code not found

With beam width 1 (pure greedy) the algorithm always follows the cheapest local edge and may end up at a worse final node. With width 3 it keeps all branches at this scale and always finds the optimal path. Real language models operate with K = 4–10 over vocabularies of tens of thousands — still an approximation, but a very effective one.

Why not just find the best sequence exactly?

• Exact decoding is intractable. For a vocabulary of size V and a sequence of length L, exhaustive search considers Vᴸ complete sequences — infeasible for any realistic L. Even with dynamic programming tricks, finding the globally highest-probability sequence under a neural language model requires exponential time in general.
• Beam search runs in $O(K \cdot V \cdot L)$ time. At each of L steps, it scores V extensions for each of K candidates. This is polynomial in all parameters — fast enough for real-time use.
• But it gives up optimality. Beam search can and does miss the highest-scoring sequence. This is not a minor theoretical quibble: studies on neural machine translation have found that the exact optimal sequence (found by exhaustive decoding on small vocabularies) is often worse perceptually than what beam search returns — a phenomenon called the beam search curse or optimal-is-bad paradox. Models trained with maximum-likelihood objectives learn to spread probability widely, making the exact MAP sequence degenerate.
• Wider beams are not always better. Beyond a certain width, the quality of output plateaus or even degrades. Modern large language models often prefer sampling strategies (nucleus sampling, temperature scaling) over beam search for open-ended generation, precisely because beam search under-generates diversity.
• The complexity class picture. Deciding whether a sequence with score above a threshold exists is NP-hard for certain model families. Beam search sidesteps this by returning a good sequence rather than a provably optimal one — a pattern that appears throughout combinatorial search, from branch and bound to greedy graph coloring.

Beam search is the silent engine behind an enormous fraction of modern AI output:

• Neural machine translation: systems like those behind Google Translate and DeepL have used beam search (K ≈ 4–10) since the sequence-to-sequence revolution of 2014–2015. Each translated sentence is the top-K race.
• Speech recognition: acoustic models decode phoneme sequences with beam search, balancing acoustic likelihood against a language model prior. The beam keeps plausible transcripts alive even when acoustics are ambiguous.
• Image and video captioning: a visual encoder feeds a language decoder that beam-searches for the best descriptive sentence.
• Code generation: models like GitHub Copilot generate code token by token; beam search (or close relatives) selects among continuations scored by a code-tuned language model.
• Protein structure prediction: AlphaFold and related systems use beam-like strategies when assembling structural hypotheses across complex search spaces.
• Summarization and dialogue: abstractive summarizers and chatbot response generators use beam search or sampling variants to produce fluent, coherent text.

The P vs NP question lurks in the background: if P = NP we might decode optimally; since we strongly believe P ≠ NP, heuristics like beam search are not just a convenience — they may be the best we can ever do in practice.

Beam search is a bet: keep the K most promising partial sequences at every step and hope the best answer survives the pruning. Most of the time, it does. The algorithm is fast, predictable, and tunable — shrink K to go faster, grow K to improve quality up to a point.

What it cannot promise is perfection. The globally best sequence may be pruned early; wider beams can paradoxically produce worse human-perceived output; and for certain model families exact decoding is computationally intractable. Beam search lives in the pragmatic middle: not guaranteed optimal, but empirically excellent.

That trade-off — tractability over optimality — is the defining motif of algorithms at scale. From greedy graph coloring to simulated annealing, the most useful algorithms are often the ones that settle for a very good answer very quickly. Beam search is the version of that wisdom that speaks to us every time a language model completes a thought.