Definition
Beam search is a heuristic for decoding sequences. At each step, it expands the partial sequences still under consideration, scores the resulting candidates, and keeps only the best fixed number, called the beam width. The score is often cumulative log probability, sometimes adjusted for length or task-specific constraints.
Discarding a partial sequence makes the search affordable, but also makes it incomplete. A prefix that looks weak early cannot return even if it would have led to the best complete sequence. A wider beam examines more candidates and uses more compute and memory. It can reduce search error, but it does not guarantee a better answer under a human quality measure.
Origin and usage
Bruce Lowerre's 1976 HARPY dissertation described a speech recognizer that searched only a few of the best syntactic and acoustic paths in parallel. Carnegie Mellon later identified that work as an early demonstration of beam search. Lowerre called the procedure a "locus model of search," so the dissertation does not establish who coined the later phrase "beam search."
Modern language systems use the same bounded-search idea for translation, transcription, and other tasks where several sequence hypotheses are worth retaining. Open-ended chat more often uses sampling because ordinary beam search tends to concentrate on similar high-probability continuations.
Distinguish it from nearby terms
- Greedy decoding keeps one candidate. In the usual formulation, a beam width of one reduces to greedy decoding.
- Sampling draws from a probability distribution and can produce different continuations from the same prefix.
- Exact search retains enough of the search space to prove an optimum under the scoring rule. Ordinary beam search cannot make that guarantee.
Check your understanding
A decoder raises its beam width from 4 to 32 and receives a higher model score but a worse human evaluation. Explain why the larger search did what it was asked to do without proving that the model's scoring rule matched human judgment.