# Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 64 of its 103 references that are in the map.
- First posted on arXiv 7 Apr 2025.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [GeDi: Generative Discriminator Guided Sequence Generation](https://mlsanity.com/paper/2009.06367/) (2020)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data](https://mlsanity.com/paper/2405.14333/) (2024)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Natural Language to Code Translation with Execution](https://mlsanity.com/paper/2204.11454/) (2022)
- [Correcting Length Bias in Neural Machine Translation](https://mlsanity.com/paper/1808.10006/) (2018)

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

- [Sample More to Think Less: Group Filtered Policy Optimization for Concise Reasoning](https://mlsanity.com/paper/2508.09726/) (2025)
- [Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective](https://mlsanity.com/paper/2506.05754/) (2025)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo](https://mlsanity.com/paper/2604.16453/) (2026)
- [Auditing Pay-Per-Token in Large Language Models](https://mlsanity.com/paper/2510.05181/) (2025)
- [Constrained Adaptive Rejection Sampling](https://mlsanity.com/paper/2510.01902/) (2025)
- [Ensembling Language Models with Sequential Monte Carlo](https://mlsanity.com/paper/2603.05432/) (2026)
- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [How Open Must Language Models be to Enable Reliable Scientific Inference?](https://mlsanity.com/paper/2603.26539/) (2026)
- [Adaptive Multilevel Twisted Sequential Monte Carlo for Rare Events Estimation in Language Models](https://mlsanity.com/paper/2608.21736/) (2026)
- [Bootstrapping Fuzzers for Compilers of Low-Resource Language Dialects Using Language Models](https://mlsanity.com/paper/2512.05887/) (2025)
- [Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration](https://mlsanity.com/paper/2603.22273/) (2026)
- [Large Databases Need Small, Open-Weight Language Models](https://mlsanity.com/paper/2606.31808/) (2026)
- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)
- [Greedy or not, here I come: Language production under vocabulary constraints in humans and resource-rational models](https://mlsanity.com/paper/2605.15365/) (2026)
- [We Hebben Een Serieus Translatie: Modeling Intercomprehension as Probabilistic Inference](https://mlsanity.com/paper/2607.12169/) (2026)
- [Generative Compilation: On-the-Fly Compiler Feedback as AI Generates Code](https://mlsanity.com/paper/2607.13921/) (2026)
- [The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding](https://mlsanity.com/paper/2608.10137/) (2026)
- [GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning](https://mlsanity.com/paper/2609.39869/) (2026)
- [Provably Tractable NFA-Constrained Language Generation via HMMs](https://mlsanity.com/paper/2609.40185/) (2026)

## Abstract (arXiv)

The dominant approach to generating from language models subject to some constraint is locally constrained decoding (LCD), incrementally sampling tokens at each time step such that the constraint is never violated. Typically, this is achieved through token masking: looping over the vocabulary and excluding non-conforming tokens. There are two important problems with this approach. (i) Evaluating the constraint on every token can be prohibitively expensive -- LM vocabularies often exceed 100,000 tokens. (ii) LCD can distort the global distribution over strings, sampling tokens based only on local information, even if they lead down dead-end paths. This work introduces a new algorithm that addresses both these problems. First, to avoid evaluating a constraint on the full vocabulary at each step of generation, we propose an adaptive rejection sampling algorithm that typically requires orders of magnitude fewer constraint evaluations. Second, we show how this algorithm can be extended to produce low-variance, unbiased estimates of importance weights at a very small additional cost -- estimates that can be soundly used within previously proposed sequential Monte Carlo algorithms to correct for the myopic behavior of local constraint enforcement. Through extensive empirical evaluation in text-to-SQL, molecular synthesis, goal inference, pattern matching, and JSON domains, we show that our approach is superior to state-of-the-art baselines, supporting a broader class of constraints and improving both runtime and performance. Additional theoretical and empirical analyses show that our method's runtime efficiency is driven by its dynamic use of computation, scaling with the divergence between the unconstrained and constrained LM, and as a consequence, runtime improvements are greater for better models.