# What Do You Get When You Cross Beam Search with Nucleus Sampling?

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 24 references that are in the map.
- First posted on arXiv 20 Jul 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Beam Search Strategies for Neural Machine Translation](https://mlsanity.com/paper/1702.01806/) (2017)
- [Scaling Neural Machine Translation](https://mlsanity.com/paper/1806.00187/) (2018)
- [Sparse Sequence-to-Sequence Models](https://mlsanity.com/paper/1905.05702/) (2019)
- [Correcting Length Bias in Neural Machine Translation](https://mlsanity.com/paper/1808.10006/) (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)
- [compare-mt: A Tool for Holistic Comparison of Language Generation Systems](https://mlsanity.com/paper/1903.07926/) (2019)
- [How Decoding Strategies Affect the Verifiability of Generated Text](https://mlsanity.com/paper/1911.03587/) (2019)
- [Smoothing and Shrinking the Sparse Seq2Seq Search Space](https://mlsanity.com/paper/2103.10291/) (2021)
- [Why Neural Machine Translation Prefers Empty Outputs](https://mlsanity.com/paper/2012.13454/) (2020)

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

- [PLeak: Prompt Leaking Attacks against Large Language Model Applications](https://mlsanity.com/paper/2405.06823/) (2024)
- [Quality-Aware Decoding for Neural Machine Translation](https://mlsanity.com/paper/2205.00978/) (2022)
- [Why don't people use character-level machine translation?](https://mlsanity.com/paper/2110.08191/) (2021)
- [Non-Exchangeable Conformal Language Generation with Nearest Neighbors](https://mlsanity.com/paper/2402.00707/) (2024)
- [Predictive Querying for Autoregressive Neural Sequence Models](https://mlsanity.com/paper/2210.06464/) (2022)
- [GaLLoP: Gradient-based Sparse Learning on Low-Magnitude Parameters](https://mlsanity.com/paper/2510.19778/) (2025)
- [Towards Probabilistically-Sound Beam Search with Masked Language Models](https://mlsanity.com/paper/2402.15020/) (2024)

## Abstract (arXiv)

We combine beam search with the probabilistic pruning technique of nucleus sampling to create two deterministic nucleus search algorithms for natural language generation. The first algorithm, p-exact search, locally prunes the next-token distribution and performs an exact search over the remaining space. The second algorithm, dynamic beam search, shrinks and expands the beam size according to the entropy of the candidate's probability distribution. Despite the probabilistic intuition behind nucleus search, experiments on machine translation and summarization benchmarks show that both algorithms reach the same performance levels as standard beam search.