Beam Search

Definition

Beam search is a heuristic decoding algorithm that generates text by tracking the top-scoring k partial sequences (the "beam width") at each step, expanding each and keeping only the highest-probability overall candidates.

Overview

Beam search sits between two extremes of text generation: greedy decoding, which picks only the single most probable next token at each step and can get stuck in a locally optimal but globally poor sequence, and an exhaustive search over every possible sequence, which is computationally intractable. Beam search approximates a better global solution by maintaining a fixed number of candidate sequences — the beam width, often denoted k — at every generation step. At each step, every candidate in the beam is expanded with all possible next tokens, the resulting sequences are scored by cumulative probability, and only the top k are kept for the next step. A wider beam explores more of the search space and tends to find higher-probability full sequences, at the cost of significantly more computation, since the number of forward passes scales with beam width. Beam search was widely used in earlier neural sequence-to-sequence systems, particularly for machine translation and summarization, where it reliably improved output quality over greedy decoding by avoiding some short-sighted token choices. However, for modern large language models used in open-ended conversational generation, beam search has fallen out of favor relative to sampling-based methods like top-p sampling and temperature-controlled sampling. This is because beam search tends to produce overly generic, repetitive, or bland text — it optimizes for the single highest-probability sequence, which in open-ended generation is often a bureaucratic, safe-sounding continuation rather than an interesting or diverse one. Beam search remains relevant for tasks with a single clearly correct or near-correct output, such as translation, where maximizing likelihood aligns well with output quality, and it is often paired with techniques like length normalization to avoid unfairly penalizing longer sequences.

Key Concepts

• Maintains the top-k highest-scoring partial sequences at each decoding step
• Balances between greedy decoding and exhaustive search
• Beam width (k) controls the trade-off between quality and compute cost
• Commonly paired with length normalization to avoid bias against longer outputs
• Historically dominant in neural machine translation and summarization
• Tends to produce more generic or repetitive text for open-ended generation
• Largely superseded by sampling methods for conversational LLMs
• Computation scales with beam width due to parallel sequence expansion

Use Cases

Frequently Asked Questions

Related in AI Fundamentals