Beam Search

Beam Search is a decoding strategy for autoregressive sequence generation that maintains a fixed number (the 'beam width') of candidate sequences at each step, rather than greedily selecting the single most likely token. At each step, the algorithm expands each candidate by all possible next tokens, computes the cumulative probability of each extended sequence, and retains only the top-k candidates. This explores a broader portion of the output space than greedy decoding, typically producing higher-quality outputs.

The beam width k controls the trade-off between search quality and computational cost. A beam width of 1 is equivalent to greedy decoding (always selecting the most probable token). Larger beam widths explore more possibilities but require k× more computation per step and more memory. Beam search is widely used in machine translation, summarization, and other tasks where output quality matters more than generation speed. However, it can produce generic or repetitive outputs, and the highest-probability sequence is not always the most desirable — particularly for open-ended generation.

Beam search can be combined with length normalization (to avoid bias toward short sequences), diversity penalties (to reduce repetition among beam candidates), and temperature scaling (to control the sharpness of the probability distribution). For open-ended or creative generation tasks, sampling-based methods (top-k sampling, nucleus/top-p sampling) are often preferred over beam search, as they produce more diverse and natural-sounding outputs.