Beam Search: Definition and Examples

Beam Search is a heuristic decoding strategy used when generating text with language models. Instead of selecting only the most likely word at each step (greedy approach), the algorithm maintains multiple partial hypotheses in parallel called "beams", allowing exploration of a wider solution space.

The process is as follows: at each generation step, the model calculates the probabilities of all possible tokens for each active beam. It then retains only the k most likely sequences, where k is the "beam width". This parameter controls the trade-off between output quality and computational cost. A width of 1 is equivalent to greedy search, while an infinite width would correspond to exhaustive search.

In practice, Beam Search produces more coherent and grammatically correct texts than greedy decoding, as it avoids locally optimal choices that lead to dead ends. However, it tends to generate more generic and repetitive texts than stochastic sampling methods like top-k or top-p sampling, because it systematically favors high-probability sequences.

This algorithm is particularly used in tasks where accuracy matters over creativity, such as machine translation, text summarization, or speech recognition. In the context of prompt engineering, understanding Beam Search helps in choosing the right generation parameters depending on the desired goal.