# Efficient and Asymptotically Unbiased Constrained Decoding for Large Language Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 57 references that are in the map.
- First posted on arXiv 12 Apr 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [MiniGPT-4: Enhancing Vision-Language Understanding with Advanced Large Language Models](https://mlsanity.com/paper/2304.10592/) (2023)
- [FEVER: a large-scale dataset for Fact Extraction and VERification](https://mlsanity.com/paper/1803.05355/) (2018)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [mPLUG-Owl: Modularization Empowers Large Language Models with Multimodality](https://mlsanity.com/paper/2304.14178/) (2023)
- [GPT-NeoX-20B: An Open-Source Autoregressive Language Model](https://mlsanity.com/paper/2204.06745/) (2022)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [ELI5: Long Form Question Answering](https://mlsanity.com/paper/1907.09190/) (2019)
- [KILT: a Benchmark for Knowledge Intensive Language Tasks](https://mlsanity.com/paper/2009.02252/) (2020)
- [Zero-Shot Relation Extraction via Reading Comprehension](https://mlsanity.com/paper/1706.04115/) (2017)
- [Autoregressive Entity Retrieval](https://mlsanity.com/paper/2010.00904/) (2020)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [SafetyBench: Evaluating the Safety of Large Language Models](https://mlsanity.com/paper/2309.07045/) (2023)
- [Recommender Systems with Generative Retrieval](https://mlsanity.com/paper/2305.05065/) (2023)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [CLIMATE-FEVER: A Dataset for Verification of Real-World Climate Claims](https://mlsanity.com/paper/2012.00614/) (2020)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [MasakhaNER: Named Entity Recognition for African Languages](https://mlsanity.com/paper/2103.11811/) (2021)
- [Autoregressive Search Engines: Generating Substrings as Document Identifiers](https://mlsanity.com/paper/2204.10628/) (2022)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [Learning to Tokenize for Generative Retrieval](https://mlsanity.com/paper/2304.04171/) (2023)
- [Can Long-Context Language Models Subsume Retrieval, RAG, SQL, and More?](https://mlsanity.com/paper/2406.13121/) (2024)
- [Improving Entity Linking by Modeling Latent Relations between Mentions](https://mlsanity.com/paper/1804.10637/) (2018)

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

- [Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators](https://mlsanity.com/paper/2602.22647/) (2026)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [Schema-Key Wording as an Instruction Channel in Structured Generation under Constrained Decoding](https://mlsanity.com/paper/2604.14862/) (2026)
- [Autoregressive Ranking: Bridging the Gap Between Dual and Cross Encoders](https://mlsanity.com/paper/2601.05588/) (2026)
- [DecompressionLM: Deterministic, Diagnostic, and Zero-Shot Concept Graph Extraction from Language Models](https://mlsanity.com/paper/2602.00377/) (2026)

## Abstract (arXiv)

In real-world applications of large language models, outputs are often required to be confined: selecting items from predefined product or document sets, generating phrases that comply with safety standards, or conforming to specialized formatting styles. To control the generation, constrained decoding has been widely adopted. However, existing prefix-tree-based constrained decoding is inefficient under GPU-based model inference paradigms, and it introduces unintended biases into the output distribution. This paper introduces Dynamic Importance Sampling for Constrained Decoding (DISC) with GPU-based Parallel Prefix-Verification (PPV), a novel algorithm that leverages dynamic importance sampling to achieve theoretically guaranteed asymptotic unbiasedness and overcomes the inefficiency of prefix-tree. Extensive experiments demonstrate the superiority of our method over existing methods in both efficiency and output quality. These results highlight the potential of our methods to improve constrained generation in applications where adherence to specific constraints is essential.