ML//inference//beam search

Beam search is a decoding strategy that keeps the \(K\) most probable partial sequences at each step instead of committing to a single token. At each decoding step it expands all \(K\) candidates by one token, scores them and keeps the best \(K\).

Beam search is a decoding strategy that keeps the KKK most probable partial sequences at each step instead of committing to a single token. At each decoding step it expands all KKK candidates by one token, scores them and keeps the best KKK.

It is the middle ground between greedy decoding (K=1K=1K=1, always pick the highest-probability token) and exhaustive search (explore all possibilities, computationally impossible). Beam width KKK controls the trade-off.

Greedy decoding fails because the locally best token is not always globally best. After the cat sat on the, greedy decoding could pick mat while the best full sequence starts differently. Beam search explores multiple paths simultaneously.

It dominated machine translation and seq2seq tasks for years. For open-ended text generation, however, beam search produces repetitive, generic text: it optimizes for probability, which favors safe continuations.

For LLM generation it has largely been replaced by sampling-based methods (temperature, top-k, top-p), whose randomness produces more creative and diverse text. Beam search is still used for tasks with a single correct answer (translation, ASR).

It is easily confused with tree search in reasoning models. Beam search works at the level of tokens and explores by probability (which token is most likely); tree search works at the level of thoughts and explores by validity (which reasoning step is most correct, scored with PRMs).