# Beam Search: Faster and Monotonic

arXiv: https://arxiv.org/abs/2204.02929 · HTML: https://mlsanity.com/paper/2204.02929/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 22 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 1 of 1)

- [Conditional Poisson Stochastic Beam Search](https://mlsanity.com/paper/2109.11034/) (2021)

## Built on by (most cited first, 1 of 1)

- [On the Depth between Beam Search and Exhaustive Search for Text Generation](https://mlsanity.com/paper/2308.13696/) (2023)

## Abstract (arXiv)

Beam search is a popular satisficing approach to heuristic search problems that allows one to trade increased computation time for lower solution cost by increasing the beam width parameter. We make two contributions to the study of beam search. First, we show how to make beam search monotonic; that is, we provide a new variant that guarantees non-increasing solution cost as the beam width is increased. This makes setting the beam parameter much easier. Second, we show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs. Together, these results improve the practical effectiveness of beam search.