Beam search

Beam search is a heuristic search algorithm used in sequence generation tasks to find a probable sequence of tokens. It is an optimized version of greedy search that explores multiple potential paths simultaneously rather than selecting only the single most likely next token at each step.

The algorithm maintains a fixed number of partial hypotheses, known as the beam width ($k$). At each time step, the model calculates the probabilities for all possible next tokens for each of the $k$ paths. The algorithm then keeps only the $k$ sequences with the highest cumulative probability, discarding all other candidates.

In the context of Large Language Models (LLMs), beam search is typically used during the decoding phase for tasks such as neural machine translation, summarization, and speech-to-text. It sits between greedy search (where $k=1$) and exhaustive breadth-first search, which would be computationally prohibitive due to the size of the vocabulary.

For example, if a model is translating a sentence with a beam width of 3, it will track the three most likely partial translations at every step. If a specific word choice initially seems likely but leads to a low-probability sequence later, the algorithm can recover by promoting one of the other two parallel paths that maintained a higher overall score.