# Determinantal Beam Search

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

## Key facts

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

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

- [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)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Facebook FAIR's WMT19 News Translation Task Submission](https://mlsanity.com/paper/1907.06616/) (2019)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [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)
- [Incremental Sampling Without Replacement for Sequence Models](https://mlsanity.com/paper/2002.09067/) (2020)
- [Efficient Approximation Algorithms for String Kernel Based Sequence Classification](https://mlsanity.com/paper/1712.04264/) (2017)
- [Multiresolution Recurrent Neural Networks: An Application to Dialogue Response Generation](https://mlsanity.com/paper/1606.00776/) (2016)
- [Faster Greedy MAP Inference for Determinantal Point Processes](https://mlsanity.com/paper/1703.03389/) (2017)
- [Efficient Sampling for k-Determinantal Point Processes](https://mlsanity.com/paper/1509.01618/) (2015)
- [COD3S: Diverse Generation with Discrete Semantic Signatures](https://mlsanity.com/paper/2010.02882/) (2020)
- [Towards Diverse and Accurate Image Captions via Reinforcing Determinantal Point Process](https://mlsanity.com/paper/1908.04919/) (2019)
- [Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration](https://mlsanity.com/paper/1707.02757/) (2017)

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

- [Diverse Demonstrations Improve In-context Compositional Generalization](https://mlsanity.com/paper/2212.06800/) (2022)
- [What Comes Next? Evaluating Uncertainty in Neural Text Generators Against Human Production Variability](https://mlsanity.com/paper/2305.11707/) (2023)
- [Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models](https://mlsanity.com/paper/2210.15458/) (2022)
- [Conditional Poisson Stochastic Beam Search](https://mlsanity.com/paper/2109.11034/) (2021)
- [Generating Diverse and High-Quality Texts by Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.05054/) (2024)
- [Semantic-guided Diverse Decoding for Large Language Model](https://mlsanity.com/paper/2506.23601/) (2025)
- [Asking a Language Model for Diverse Responses](https://mlsanity.com/paper/2509.17570/) (2025)
- [Massive-scale Decoding for Text Generation using Lattices](https://mlsanity.com/paper/2112.07660/) (2021)
- [Priority Sampling of Large Language Models for Compilers](https://mlsanity.com/paper/2402.18734/) (2024)
- [Free Lunch for Pass@k? Low Cost Diverse Sampling for Diffusion Language Models](https://mlsanity.com/paper/2603.04893/) (2026)
- [Unused information in token probability distribution of generative LLM: improving LLM reading comprehension through calculation of expected values](https://mlsanity.com/paper/2406.10267/) (2024)
- [Uncertainty-Guided Likelihood Tree Search](https://mlsanity.com/paper/2407.03951/) (2024)
- [Anytime-Valid Answer Sufficiency Certificates for LLM Generation via Sequential Information Lift](https://mlsanity.com/paper/2510.06478/) (2025)
- [UpSkill: Mutual Information Skill Learning for Structured Response Diversity in LLMs](https://mlsanity.com/paper/2602.22296/) (2026)
- [D5P4: Partition Determinantal Point Process for Diversity in Parallel Discrete Diffusion Decoding](https://mlsanity.com/paper/2603.19146/) (2026)
- [Mitigating Over-Optimization in PRM-Guided Search in Mathematical Reasoning by Optimizing the Guide](https://mlsanity.com/paper/2608.30051/) (2026)
- [Improving the Diversity of LLM Outputs without a Trade-off](https://mlsanity.com/paper/2609.33038/) (2026)
- [Self-Repulsive Sampling for Diffusion Language Models](https://mlsanity.com/paper/2609.39560/) (2026)

## Abstract (arXiv)

Beam search is a go-to strategy for decoding neural sequence models. The algorithm can naturally be viewed as a subset optimization problem, albeit one where the corresponding set function does not reflect interactions between candidates. Empirically, this leads to sets often exhibiting high overlap, e.g., strings may differ by only a single word. Yet in use-cases that call for multiple solutions, a diverse or representative set is often desired. To address this issue, we propose a reformulation of beam search, which we call determinantal beam search. Determinantal beam search has a natural relationship to determinantal point processes (DPPs), models over sets that inherently encode intra-set interactions. By posing iterations in beam search as a series of subdeterminant maximization problems, we can turn the algorithm into a diverse subset selection process. In a case study, we use the string subsequence kernel to explicitly encourage n-gram coverage in text generated from a sequence model. We observe that our algorithm offers competitive performance against other diverse set generation strategies in the context of language generation, while providing a more general approach to optimizing for diversity.