# Conditional Poisson Stochastic Beam Search

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 22 Sep 2021.

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

- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Scaling Neural Machine Translation](https://mlsanity.com/paper/1806.00187/) (2018)
- [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)
- [Minimum Risk Training for Neural Machine Translation](https://mlsanity.com/paper/1512.02433/) (2015)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [Estimating Gradients for Discrete Random Variables by Sampling without Replacement](https://mlsanity.com/paper/2002.06043/) (2020)
- [Rao-Blackwellized Stochastic Gradients for Discrete Distributions](https://mlsanity.com/paper/1810.04777/) (2018)
- [Incremental Sampling Without Replacement for Sequence Models](https://mlsanity.com/paper/2002.09067/) (2020)
- [Determinantal Beam Search](https://mlsanity.com/paper/2106.07400/) (2021)
- [Multiresolution Recurrent Neural Networks: An Application to Dialogue Response Generation](https://mlsanity.com/paper/1606.00776/) (2016)

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

- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [Selectively Answering Ambiguous Questions](https://mlsanity.com/paper/2305.14613/) (2023)
- [Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models](https://mlsanity.com/paper/2210.15458/) (2022)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Semantic-guided Diverse Decoding for Large Language Model](https://mlsanity.com/paper/2506.23601/) (2025)
- [Massive-scale Decoding for Text Generation using Lattices](https://mlsanity.com/paper/2112.07660/) (2021)
- [AutoPrompt: Automated Red-Teaming of Text-to-Image Models via LLM-Driven Adversarial Prompts](https://mlsanity.com/paper/2510.24034/) (2025)
- [Predictive Querying for Autoregressive Neural Sequence Models](https://mlsanity.com/paper/2210.06464/) (2022)
- [Beam Search: Faster and Monotonic](https://mlsanity.com/paper/2204.02929/) (2022)
- [Agentic AI: The Era of Semantic Decoding](https://mlsanity.com/paper/2403.14562/) (2024)
- [Stochastic Estimation of Transduced Language Models](https://mlsanity.com/paper/2608.27428/) (2026)

## Abstract (arXiv)

Beam search is the default decoding strategy for many sequence generation tasks in NLP. The set of approximate K-best items returned by the algorithm is a useful summary of the distribution for many applications; however, the candidates typically exhibit high overlap and may give a highly biased estimate for expectations under our model. These problems can be addressed by instead using stochastic decoding strategies. In this work, we propose a new method for turning beam search into a stochastic process: Conditional Poisson stochastic beam search. Rather than taking the maximizing set at each iteration, we sample K candidates without replacement according to the conditional Poisson sampling design. We view this as a more natural alternative to Kool et. al. 2019's stochastic beam search (SBS). Furthermore, we show how samples generated under the CPSBS design can be used to build consistent estimators and sample diverse sets from sequence models. In our experiments, we observe CPSBS produces lower variance and more efficient estimators than SBS, even showing improvements in high entropy settings.