# Making Grid Beam Search Less Greedy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 25 references that are in the map.
- First posted on arXiv 30 Sep 2026.

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

- [Multitask Prompted Training Enables Zero-Shot Task Generalization](https://mlsanity.com/paper/2110.08207/) (2021)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [TinyLlama: An Open-Source Small Language Model](https://mlsanity.com/paper/2401.02385/) (2024)
- [Sentiment Analysis in the Era of Large Language Models: A Reality Check](https://mlsanity.com/paper/2305.15005/) (2023)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [Controlled Text Generation as Continuous Optimization with Multiple Constraints](https://mlsanity.com/paper/2108.01850/) (2021)
- [TheoremLlama: Transforming General-Purpose LLMs into Lean4 Experts](https://mlsanity.com/paper/2407.03203/) (2024)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [PromptNER: Prompting For Named Entity Recognition](https://mlsanity.com/paper/2305.15444/) (2023)
- [MA-LoT: Model-Collaboration Lean-based Long Chain-of-Thought Reasoning enhances Formal Theorem Proving](https://mlsanity.com/paper/2503.03205/) (2025)
- [Automatic Multi-Label Prompting: Simple and Interpretable Few-Shot Classification](https://mlsanity.com/paper/2204.06305/) (2022)

## Abstract (arXiv)

A common formalism for constraining the output of autoregressive text generation models involves lexical constraints, words or phrases which are required to occur in the generated text. DFA-constrained beam search and grid beam search are two widely used paradigms for decoding from autoregressive models while enforcing lexical constraints. As the former approach requires a number of forward passes exponential in the number of constraint tokens, it is often dispreferred to the latter, which requires only linearly many forward calls. However, while grid beam search achieves an exponential speedup, it does so in a manner which does not treat all of the constraints equally. In this paper, we demonstrate that grid beam search is biased to incorporate easier-to-satisfy constraints first, leaving harder constraints to the end of the sequence. This contrasts with DFA-constrained beam search, which exhibits no such bias. To address this shortcoming, we propose fair grid beam search, a modification to grid beam search which avoids this bias while still requiring only linearly many forward passes. Experimentally, we confirm grid beam search's bias on two constrained generation tasks, finding significant differences in how it orders constraint tokens as compared to DFA-constrained beam search and fair grid beam search. Furthermore, we find that fair grid beam search not only fixes grid beam search's bias, but finds higher-probability strings in the process.