A heuristic search algorithm for finding optimal sequences

Overview

Beam search is a heuristic search algorithm commonly used in sequence-to-sequence models for tasks like machine translation, speech recognition, and text generation. It explores a graph by expanding the most promising nodes while keeping only a limited number of candidates at each level.

How It Works

Beam search uses breadth-first search to build its search tree. At each level:

1. Generate all successors of the states at the current level
2. Sort them in increasing order of heuristic cost
3. Keep only the top \(\beta\) states (the beam width)
4. Expand only those states in the next iteration

The greater the beam width, the fewer states are pruned. With \(\beta = 1\), beam search becomes greedy search. With \(\beta = \infty\), it becomes exhaustive breadth-first search.

Why Use Beam Search?

Beam search maintains tractability in large systems with insufficient memory to store the entire search tree. It provides a balance between:

• Greedy search: Fast but may miss optimal solutions
• Exhaustive search: Optimal but computationally infeasible

Applications

• Neural Machine Translation: Finding the most likely translation
• Speech Recognition: Decoding audio to text
• Image Captioning: Generating descriptions for images
• Text Generation: Producing coherent sequences in LLMs

Limitations

Beam search is not guaranteed to find the optimal solution since it prunes the search space. The choice of beam width \(\beta\) is a trade-off between search quality and computational cost.