2.4.4. Beam Search

Beam search is a heuristic search algorithm widely used in Artificial Intelligence (AI) to efficiently explore a vast search space, particularly in problems where the goal is to find the most optimal sequence of decisions. Originating from the family of graph search algorithms, beam search is best known for its application in sequence prediction tasks, such as natural language processing (NLP) tasks like machine translation, speech recognition, and in the generation of textual or visual content.

Unlike exhaustive search algorithms that aim to explore every possible path in the search space, beam search narrows its focus to a fixed number of the most promising paths at each step of the search process. This number, known as the “beam width,” serves as a crucial parameter that balances the breadth of the search against computational efficiency. A larger beam width allows the algorithm to explore more paths simultaneously, increasing the likelihood of finding the optimal sequence but at the cost of higher computational resources. Conversely, a smaller beam width makes the search process faster and less resource-intensive but risks missing the optimal path.

The core idea behind beam search is to expand the search tree level by level, starting from the root node. At each level, it evaluates and scores all possible extensions of the paths in the current beam based on a predefined scoring function, which could incorporate factors like probability scores from a predictive model or heuristic estimates of path quality. It then selects the top-scoring paths, up to the limit set by the beam width, to carry forward into the next level of the search. This pruning of less promising paths at each step helps to keep the search tractable, even in cases where the complete search space is prohibitively large.

Beam search can operate in either a greedy mode, where it terminates once it finds a solution, or in a more exhaustive mode, where it continues the search until it reaches a specified depth or exhausts the search space, potentially yielding multiple high-quality solutions. While beam search does not guarantee finding the absolute best solution due to its heuristic nature and the potential for early pruning of the optimal path, it often finds solutions that are good enough for practical purposes within a reasonable amount of time and resource usage.

The flexibility to adjust the beam width, the ability to integrate sophisticated scoring functions, and the relative simplicity of its implementation make beam search a powerful tool in the AI practitioner’s toolkit, especially in domains where the search space is vast and the need for efficient exploration is paramount.

Please refer to Section 2.4.3.6 for an example.