# Controllable Generation via Locally Constrained Resampling

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 56 references that are in the map.
- First posted on arXiv 17 Oct 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [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)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Challenges in Detoxifying Language Models](https://mlsanity.com/paper/2109.07445/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (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)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [Evaluating Large Language Models on Controlled Generation Tasks](https://mlsanity.com/paper/2310.14542/) (2023)
- [Exploring the Limits of Domain-Adaptive Training for Detoxifying Large-Scale Language Models](https://mlsanity.com/paper/2202.04173/) (2022)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Controllable Text Generation with Neurally-Decomposed Oracle](https://mlsanity.com/paper/2205.14219/) (2022)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [Neuro-Symbolic Entropy Regularization](https://mlsanity.com/paper/2201.11250/) (2022)

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

- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective](https://mlsanity.com/paper/2506.05754/) (2025)
- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [Fast and Expressive Multi-Byte Prediction with Probabilistic Circuits](https://mlsanity.com/paper/2511.11346/) (2025)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [Semantic Probabilistic Control of Language Models](https://mlsanity.com/paper/2505.01954/) (2025)
- [ABS: Enforcing Constraint Satisfaction On Generated Sequences Via Automata-Guided Beam Search](https://mlsanity.com/paper/2506.09701/) (2025)
- [Calibrated Predictive Lower Bounds on Time-to-Unsafe-Sampling in LLMs](https://mlsanity.com/paper/2506.13593/) (2025)
- [Entropy-Aligned Decoding of LMs for Better Writing and Reasoning](https://mlsanity.com/paper/2601.01714/) (2026)
- [Norm-Q: Effective Compression Method for Hidden Markov Models in Neuro-Symbolic Applications](https://mlsanity.com/paper/2509.25439/) (2025)
- [GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning](https://mlsanity.com/paper/2609.39869/) (2026)

## Abstract (arXiv)

Autoregressive models have demonstrated an unprecedented ability at modeling the intricacies of natural language. However, they continue to struggle with generating complex outputs that adhere to logical constraints. Sampling from a fully-independent distribution subject to a constraint is hard. Sampling from an autoregressive distribution subject to a constraint is doubly hard: We have to contend not only with the hardness of the constraint but also the distribution's lack of structure. We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint. Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods. Starting from a model sample, we induce a local, factorized distribution which we can tractably condition on the constraint. To generate samples that satisfy the constraint, we sample from the conditional distribution, correct for biases in the samples and resample. The resulting samples closely approximate the target distribution and are guaranteed to satisfy the constraints. We evaluate our approach on several tasks, including LLM detoxification and solving Sudoku puzzles. We show that by disallowing a list of toxic expressions our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification. We conclude by showing that our approach achieves a perfect accuracy on Sudoku compared to <50% for GPT4-o and Gemini 1.5.