Beam Search: Faster and Monotonic

• URL: http://arxiv.org/abs/2204.02929v1
• Date: Wed, 6 Apr 2022 16:40:13 GMT
• Title: Beam Search: Faster and Monotonic
• Authors: Sofia Lemons and Carlos Linares L\'opez and Robert C. Holte and Wheeler Ruml
• Abstract summary: 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. We also show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs.
• Score: 15.20931404997906
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• On the Depth between Beam Search and Exhaustive Search for Text Generation [3.726173629675064]
  Beam search is limited in both search width and depth, whereas exhaustive search is a global search that has no such limitations. We introduce Lookahead Beam Search (LBS), a multi-step lookahead search that optimize the objective considering a fixed number of future steps. LBS outperforms beam search overall on machine translation tasks.
  arXiv  Detail & Related papers  (2023-08-25T22:57:53Z)
• Deep Learning and Image Super-Resolution-Guided Beam and Power Allocation for mmWave Networks [80.37827344656048]
  We develop a deep learning (DL)-guided hybrid beam and power allocation approach for millimeter-wave (mmWave) networks. We exploit the synergy of supervised learning and super-resolution technology to enable low-overhead beam- and power allocation.
  arXiv  Detail & Related papers  (2023-05-08T05:40:54Z)
• Factorized Inverse Path Tracing for Efficient and Accurate Material-Lighting Estimation [97.0195314255101]
  Inverse path tracing is expensive to compute, and ambiguities exist between reflection and emission. Our Factorized Inverse Path Tracing (FIPT) addresses these challenges by using a factored light transport formulation. Our algorithm enables accurate material and lighting optimization faster than previous work, and is more effective at resolving ambiguities.
  arXiv  Detail & Related papers  (2023-04-12T07:46:05Z)
• Fast Beam Alignment via Pure Exploration in Multi-armed Bandits [91.11360914335384]
  We develop a bandit-based fast BA algorithm to reduce BA latency for millimeter-wave (mmWave) communications. Our algorithm is named Two-Phase Heteroscedastic Track-and-Stop (2PHT&S)
  arXiv  Detail & Related papers  (2022-10-23T05:57:39Z)
• A Call for Clarity in Beam Search: How It Works and When It Stops [125.55175954381991]
  We introduce a patience factor, a simple modification to this beam decoding implementation, that generalizes the stopping criterion and provides flexibility to the depth of search. Empirical results demonstrate that adjusting this patience factor improves decoding performance of strong pretrained models on news text summarization and machine translation over diverse language pairs.
  arXiv  Detail & Related papers  (2022-04-11T22:03:44Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• A Novel Look at LIDAR-aided Data-driven mmWave Beam Selection [24.711393214172148]
  We propose a lightweight neural network (NN) architecture along with the corresponding LIDAR preprocessing. Our NN-based beam selection scheme can achieve 79.9% throughput without any beam search overhead and 95% by searching among as few as 6 beams.
  arXiv  Detail & Related papers  (2021-04-29T18:07:31Z)
• Incremental Beam Manipulation for Natural Language Generation [26.295452668557452]
  It is common to rerank the output of beam search, but this relies on beam search to produce a good set of hypotheses. Other alternatives to beam search require changes to the training of the model, which restricts their applicability. This paper proposes incremental beam manipulation, i.e. reranking the hypotheses in the beam during decoding instead of only at the end.
  arXiv  Detail & Related papers  (2021-02-04T12:26:47Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.