# Best-k Search Algorithm for Neural Text Generation

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

## Key facts

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

## Builds on (most cited first, 30 of 48)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [A Diversity-Promoting Objective Function for Neural Conversation Models](https://mlsanity.com/paper/1510.03055/) (2015)
- [COMET: A Neural Framework for MT Evaluation](https://mlsanity.com/paper/2009.09025/) (2020)
- [DROP: A Reading Comprehension Benchmark Requiring Discrete Reasoning Over Paragraphs](https://mlsanity.com/paper/1903.00161/) (2019)
- [DialoGPT: Large-Scale Generative Pre-training for Conversational Response Generation](https://mlsanity.com/paper/1911.00536/) (2019)
- [SummEval: Re-evaluating Summarization Evaluation](https://mlsanity.com/paper/2007.12626/) (2020)
- [Evaluating the Factual Consistency of Abstractive Text Summarization](https://mlsanity.com/paper/1910.12840/) (2019)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [QAFactEval: Improved QA-Based Factual Consistency Evaluation for Summarization](https://mlsanity.com/paper/2112.08542/) (2021)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [Analyzing Uncertainty in Neural Machine Translation](https://mlsanity.com/paper/1803.00047/) (2018)
- [If beam search is the answer, what was the question?](https://mlsanity.com/paper/2010.02650/) (2020)
- [On NMT Search Errors and Model Errors: Cat Got Your Tongue?](https://mlsanity.com/paper/1908.10090/) (2019)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [High Quality Rather than High Model Probability: Minimum Bayes Risk Decoding with Neural Metrics](https://mlsanity.com/paper/2111.09388/) (2021)

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

- [JustiLM: Few-shot Justification Generation for Explainable Fact-Checking of Real-world Claims](https://mlsanity.com/paper/2401.08026/) (2024)
- [Automatic Metrics in Natural Language Generation: A Survey of Current Evaluation Practices](https://mlsanity.com/paper/2408.09169/) (2024)
- [Generating Diverse and High-Quality Texts by Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.05054/) (2024)
- [Entropy Guided Extrapolative Decoding to Improve Factuality in Large Language Models](https://mlsanity.com/paper/2404.09338/) (2024)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [Prompt Sketching for Large Language Models](https://mlsanity.com/paper/2311.04954/) (2023)

## Abstract (arXiv)

Modern natural language generation paradigms require a good decoding strategy to obtain quality sequences out of the model. Beam search yields high-quality but low diversity outputs; stochastic approaches suffer from high variance and sometimes low quality, but the outputs tend to be more natural and creative. In this work, we propose a deterministic search algorithm balancing both quality and diversity. We first investigate the vanilla best-first search (BFS) algorithm and then propose the Best-k Search algorithm. Inspired by BFS, we greedily expand the top k nodes, instead of only the first node, to boost efficiency and diversity. Upweighting recently discovered nodes accompanied by heap pruning ensures the completeness of the search procedure. Experiments on four NLG tasks, including question generation, commonsense generation, text summarization, and translation, show that best-k search yields more diverse and natural outputs compared to strong baselines, while our approach maintains high text quality. The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.