# Beam search **AI Engineering Visualised** · Inference · Interactive explainer · Updated 2026-08-16 Beam search is a decoding strategy that keeps the k most probable partial sequences at each step instead of only the single best token. It finds sentences that greedy decoding cannot, at k times the cost. > Play beam search over a token tree built to trap greedy decoding. The most probable first word is not on the best sentence, and width two is enough to prove it. Greedy decoding answers a slightly wrong question. It picks the most probable next token, every step, but what you usually want is the most probable whole sequence, and those are not the same thing. A word can be the single best continuation right now while everything that follows it is mediocre. This tree is built so that happens immediately. The first token "cat" has probability 0.5 against "dog" at 0.32, so greedy takes it, and everything under "cat" turns out flat and indecisive. Under "dog" hides a spine of high-probability continuations whose product beats anything "cat" can reach. Play the search at width 1 and watch it walk into the trap; widen to 2 and the runner-up stays alive just long enough for its subtree to win. The mechanism is worth watching step by step. Every live beam proposes all of its children; the pool of candidates is ranked by cumulative log-probability, which is where a strong past can subsidise a weak present; and only the best k survive. The crossed-out boxes are real candidates that were considered and pruned, which is exactly what a finished-looking diagram of beam search hides. Widths three and four are on the slider too: on a tree this small they converge on the same answer as width two, which is itself a lesson in diminishing returns. Two honest limits. Beam search is not exhaustive: even here, a width of 2 explores a fraction of the tree, and there exist trees that fool any fixed width. And in open-ended generation, maximising sequence probability is often not what you want at all: the highest-probability continuation of a chat prompt is repetitive and dull, which is why beam search rules translation and speech recognition, where there is a right answer, and sampling rules creative generation, where there is not. ## The maths ### The objective ```latex \mathbf{y}^* \;=\; \arg\max_{\mathbf{y}} \sum_{t} \log P(y_t \mid y_{