# Tractable Control for Autoregressive Language Generation

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 59 references that are in the map.
- First posted on arXiv 15 Apr 2023.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [CIDEr: Consensus-based Image Description Evaluation](https://mlsanity.com/paper/1411.5726/) (2014)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [SPICE: Semantic Propositional Image Caption Evaluation](https://mlsanity.com/paper/1607.08822/) (2016)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Plan-And-Write: Towards Better Automatic Storytelling](https://mlsanity.com/paper/1811.05701/) (2018)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [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)
- [On the Paradox of Learning to Reason from Data](https://mlsanity.com/paper/2205.11502/) (2022)
- [Lexically Constrained Neural Machine Translation with Levenshtein Transformer](https://mlsanity.com/paper/2004.12681/) (2020)
- [Toward Abstractive Summarization Using Semantic Representations](https://mlsanity.com/paper/1805.10399/) (2018)
- [Controllable Text Generation with Neurally-Decomposed Oracle](https://mlsanity.com/paper/2205.14219/) (2022)
- [Neural Extractive Text Summarization with Syntactic Compression](https://mlsanity.com/paper/1902.00863/) (2019)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks](https://mlsanity.com/paper/1901.03704/) (2019)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Zero-shot Sonnet Generation with Discourse-level Planning and Aesthetics Features](https://mlsanity.com/paper/2205.01821/) (2022)
- [Group Fairness by Probabilistic Modeling with Latent Fair Decisions](https://mlsanity.com/paper/2009.09031/) (2020)
- [Scaling Hidden Markov Language Models](https://mlsanity.com/paper/2011.04640/) (2020)
- [Joints in Random Forests](https://mlsanity.com/paper/2006.14937/) (2020)
- [On Tractable Computation of Expected Predictions](https://mlsanity.com/paper/1910.02182/) (2019)
- [Boosted Generative Models](https://mlsanity.com/paper/1702.08484/) (2017)
- [Sparse Probabilistic Circuits via Pruning and Growing](https://mlsanity.com/paper/2211.12551/) (2022)
- [Learning Fair Naive Bayes Classifiers by Discovering and Eliminating Discrimination Patterns](https://mlsanity.com/paper/1906.03843/) (2019)
- [InsNet: An Efficient, Flexible, and Performant Insertion-based Text Generation Model](https://mlsanity.com/paper/2102.11008/) (2021)

## Built on by (most cited first, 30 of 65)

- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [Theoretical Benefit and Limitation of Diffusion Language Model](https://mlsanity.com/paper/2502.09622/) (2025)
- [Can LLMs Follow Simple Rules?](https://mlsanity.com/paper/2311.04235/) (2023)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Large Language Models for Medicine: A Survey](https://mlsanity.com/paper/2405.13055/) (2024)
- [DeepEdit: Knowledge Editing as Decoding with Constraints](https://mlsanity.com/paper/2401.10471/) (2024)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [Diffusion vs. Autoregressive Language Models: A Text Embedding Perspective](https://mlsanity.com/paper/2505.15045/) (2025)
- [A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints](https://mlsanity.com/paper/2312.03905/) (2023)
- [Image Inpainting via Tractable Steering of Diffusion Models](https://mlsanity.com/paper/2401.03349/) (2023)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis](https://mlsanity.com/paper/2405.15880/) (2024)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective](https://mlsanity.com/paper/2506.05754/) (2025)
- [Next Steps for Human-Centered Generative AI: A Technical Perspective](https://mlsanity.com/paper/2306.15774/) (2023)
- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)
- [Breaking the Factorization Barrier in Diffusion Language Models](https://mlsanity.com/paper/2603.00045/) (2026)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [NeSyA: Neurosymbolic Automata](https://mlsanity.com/paper/2412.07331/) (2024)
- [CoDa: Constrained Generation based Data Augmentation for Low-Resource NLP](https://mlsanity.com/paper/2404.00415/) (2024)
- [Scaling Continuous Latent Variable Models as Probabilistic Integral Circuits](https://mlsanity.com/paper/2406.06494/) (2024)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Decoupling Task-Solving and Output Formatting in LLM Generation](https://mlsanity.com/paper/2510.03595/) (2025)
- [Fast and Expressive Multi-Byte Prediction with Probabilistic Circuits](https://mlsanity.com/paper/2511.11346/) (2025)
- [TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation](https://mlsanity.com/paper/2504.18535/) (2025)

## Abstract (arXiv)

Despite the success of autoregressive large language models in text generation, it remains a major challenge to generate text that satisfies complex constraints: sampling from the conditional distribution Pr(text | α) is intractable for even the simplest lexical constraints α. To overcome this challenge, we propose to use tractable probabilistic models (TPMs) to impose lexical constraints in autoregressive text generation models, which we refer to as GeLaTo (Generating Language with Tractable Constraints). To demonstrate the effectiveness of this framework, we use distilled hidden Markov models, where we can efficiently compute Pr(text | α), to guide autoregressive generation from GPT2. GeLaTo achieves state-of-the-art performance on challenging benchmarks for constrained text generation (e.g., CommonGen), beating various strong baselines by a large margin. Our work not only opens up new avenues for controlling large language models but also motivates the development of more expressive TPMs.