# Tractable Hierarchical Control of Autoregressive Language Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 1 Jun 2026.

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

- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Validating Large Language Models with ReLM](https://mlsanity.com/paper/2211.15458/) (2022)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [Fast and Expressive Multi-Byte Prediction with Probabilistic Circuits](https://mlsanity.com/paper/2511.11346/) (2025)
- [Taming Context-Sensitive Languages with Principled Stateful Parsing](https://mlsanity.com/paper/1609.05365/) (2016)
- [ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits](https://mlsanity.com/paper/2604.06559/) (2026)

## Abstract (arXiv)

Constraining the generation of autoregressive large language models (LLMs) is an important component of integrating language models into formal systems. In the generation of code and data for tasks like program synthesis, ensuring that language models produce syntactically valid output is a prerequisite for processing such output. These languages (such as SQL or JSON) are often designed as LR(k) context-free grammars. By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints, ensuring high quality output that is guaranteed to be valid. This paper demonstrates that the satisfaction of any LR(k) grammar of finite duration can be calculated in polynomial time, an improvement over the exponential time of applying previous methods to such grammars. This result enables efficient constraint and steering of LLM generation towards output that better satisfies formal syntactic constraints.