Beam Search: Finding Good Sequences Without Brute Force

The trouble with greedy decoding

The simplest way to generate a sequence from a language model is greedy decoding: at every step, pick the single token with the highest probability and move on. It is fast and easy to implement, but it is also short-sighted. A model might assign the highest probability to a perfectly reasonable first word that nonetheless leads into a linguistic dead end, forcing awkward or low-quality choices later simply because the greedy path already committed to it. Because greedy decoding never reconsiders a decision once made, one locally optimal token can quietly wreck the overall sequence, even when a slightly less likely first word would have opened the door to a far better sentence overall. The core problem is that the best sequence is a property of the whole path, not of any single step, and greedy decoding only ever looks one step ahead.

Why brute-force search is a non-starter

The natural fix is to consider every possible sequence and pick the one with the highest total probability. But the space of possible sequences explodes combinatorially: with a vocabulary of size V and a target sequence length T, there are roughly V^T possible sequences to evaluate. Even a modest vocabulary of 30,000 tokens and a sentence of just 20 tokens produces a number of candidate sequences vastly larger than the number of atoms in the observable universe. Exhaustive search is therefore computationally impossible for any realistic language task, which means practical decoding always has to be an approximation — the real question is how to approximate intelligently rather than blindly.

Keeping the top-k candidates alive

Beam search strikes a middle ground between greedy decoding's tunnel vision and brute force's impossibility. Instead of keeping only the single best partial sequence, it keeps a fixed number of the most promising partial sequences, called beams, at every step. At each step, the algorithm expands every current beam by every possible next token, scores all of these extended candidates by their cumulative log-probability, and then prunes the list back down to just the top-k highest-scoring sequences before moving to the next step. This means a sequence that looked slightly suboptimal early on can still survive in the beam and later prove to be part of the best overall path, something pure greedy decoding could never recover from. The search ends when the beams reach a maximum length or all produce an end-of-sequence token, and the highest-scoring completed beam is returned as the final output.

The beam width trade-off

The number of beams kept at each step, the beam width k, is the algorithm's central dial. Setting k=1 collapses beam search back into plain greedy decoding, while increasing k lets the search explore more alternative paths, generally improving output quality by reducing the chance that a good sequence gets pruned too early. But that improvement is not free: both the memory and computation required grow roughly linearly with k, since every beam must be expanded and rescored at every step. Beyond a certain point, larger beam widths also yield diminishing or even negative returns on quality, since overly wide search can favor generic, high-probability-but-bland sequences over more distinctive ones, a phenomenon researchers have documented in tasks like machine translation. Choosing k is therefore a practical balancing act between output quality, latency, and hardware budget rather than a matter of simply maximizing search breadth.

Where beam search lives today

Beam search became a workhorse of neural machine translation, speech-to-text systems, and image captioning, where the goal is a single, well-formed, high-probability output and modest beam widths of around 4 to 10 typically suffice. It remains common in these deterministic-style tasks because it reliably improves on greedy decoding without the cost of exhaustive search. For open-ended text generation, however — chatbots, stories, creative writing — beam search has largely been supplanted by sampling-based methods like top-k sampling, nucleus (top-p) sampling, and temperature-controlled sampling, which deliberately introduce randomness because pure probability-maximizing search tends to produce repetitive, generic text when there is no single 'correct' answer to converge on. The choice between beam search and sampling ultimately reflects the nature of the task: beam search shines when there is a best answer to be found, while sampling shines when variety and creativity matter more than probability rank.

Frequently asked questions

Try it live

Everything above runs in your browser — open Beam Search: Finding Good Sequences Without Brute Force and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.