mlsanityData to 7 Oct 2026

Best-First Beam Search

arXiv 2007.03909 ↗First posted 8 Jul 2020cs.CL cs.DScited by 40

Not on the map. Why?

Abstract (arXiv)

Decoding for many NLP tasks requires an effective heuristic algorithm for approximating exact search since the problem of searching the full output space is often intractable, or impractical in many settings. The default algorithm for this job is beam search -- a pruned version of breadth-first search. Quite surprisingly, beam search often returns better results than exact inference due to beneficial search bias for NLP tasks. In this work, we show that the standard implementation of beam search can be made up to 10x faster in practice. Our method assumes that the scoring function is monotonic in the sequence length, which allows us to safely prune hypotheses that cannot be in the final set of hypotheses early on. We devise effective monotonic approximations to popular nonmonontic scoring functions, including length normalization and mutual information decoding. Lastly, we propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance, but runs in a fraction of the time.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 8; 2023: 9; 2024: 6; 2025: 6; 2026: 1.

40 papers.

Sort:

By area:

  1. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  2. 2023Self-Evaluation Guided Beam Search for Reasoningcited by 195
  3. 2021NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristicscited by 153
  4. 2022Mutual Information Alleviates Hallucinations in Abstractive Summarizationcited by 67
  5. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  6. 2021Machine Translation Decoding beyond Beam Searchcited by 55
  7. 2024DeAL: Decoding-time Alignment for Large Language Modelscited by 55
  8. 2023Faithfulness-Aware Decoding Strategies for Abstractive Summarizationcited by 31
  9. 2021Defending Against Backdoor Attacks in Natural Language Generationcited by 30
  10. 2023Why do Nearest Neighbor Language Models Work?cited by 29
  11. 2022CTC Alignments Improve Autoregressive Translationcited by 25
  12. 2021Searchable Hidden Intermediates for End-to-End Models of Decomposable Sequence Taskscited by 24
28 more
  1. 2023Constructing Tree-based Index for Efficient and Effective Dense Retrievalcited by 15
  2. 2021Conditional Poisson Stochastic Beam Searchcited by 11
  3. 2024FLAP: Flow-Adhering Planning with Constrained Decoding in LLMscited by 11
  4. 2022A Call for Clarity in Beam Search: How It Works and When It Stopscited by 10
  5. 2022SentBS: Sentence-level Beam Search for Controllable Summarizationcited by 10
  6. 2024CT-AGRG: Automated Abnormality-Guided Report Generation from 3D Chest CT Volumescited by 10
  7. 2021Massive-scale Decoding for Text Generation using Latticescited by 8
  8. 2025Mitigating Image Captioning Hallucinations in Vision-Language Modelscited by 7
  9. 2022Best-k Search Algorithm for Neural Text Generationcited by 6
  10. 2023A Method to Automate the Discharge Summary Hospital Course for Neurology Patientscited by 6
  11. 2023Accented Speech Recognition With Accent-specific Codebookscited by 6
  12. 2022Twist Decoding: Diverse Generators Guide Each Othercited by 4
  13. 2023Parameter Efficient Audio Captioning With Faithful Guidance Using Audio-text Shared Latent Representationcited by 4
  14. 2024Uncertainty-Guided Likelihood Tree Searchcited by 4
  15. 2025WavefrontDiffusion: Dynamic Decoding Schedule for Improved Reasoningcited by 4
  16. 2021Searching for Search Errors in Neural Morphological Inflectioncited by 2
  17. 2023On the Depth between Beam Search and Exhaustive Search for Text Generationcited by 2
  18. 2024A Framework for Real-time Safeguarding the Text Generation of Large Language Modelcited by 2
  19. 2025SDA: Steering-Driven Distribution Alignment for Open LLMs without Fine-Tuningcited by 2
  20. 2021Searching for More Efficient Dynamic Programscited by 1
  21. 2022Don't Be So Sure! Boosting ASR Decoding via Confidence Relaxationcited by 1
  22. 2023DREAM: Debugging and Repairing AutoML Pipelinescited by 1
  23. 2025ZhiFangDanTai: Fine-tuning Graph-based Retrieval-Augmented Generation Model for Traditional Chinese Medicine Formulacited by 1
  24. 2021Exploiting Beam Search Confidence for Energy-Efficient Speech Recognitioncited by 0
  25. 2024Improving Autoregressive Training with Dynamic Oraclescited by 0
  26. 2025LFD: Layer Fused Decoding to Exploit External Knowledge in Retrieval-Augmented Generationcited by 0
  27. 2025Unified Interactive Multimodal Moment Retrieval via Cascaded Embedding-Reranking and Temporal-Aware Score Fusioncited by 0
  28. 2026A Generalized Formalism of Auto-Regressive Decoding for Speech Processingcited by 0