# Provably Tractable NFA-Constrained Language Generation via HMMs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 30 Sep 2026.

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

- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [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)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Gradient-Based Constrained Sampling from Language Models](https://mlsanity.com/paper/2205.12558/) (2022)
- [Bounding the Capabilities of Large Language Models in Open Text Generation with Prompt Constraints](https://mlsanity.com/paper/2302.09185/) (2023)
- [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)
- [TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation](https://mlsanity.com/paper/2504.18535/) (2025)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs](https://mlsanity.com/paper/2601.04426/) (2026)
- [#NFA admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes](https://mlsanity.com/paper/1906.09226/) (2019)
- [Towards practical FPRAS for #NFA: Exploiting the Power of Dependence](https://mlsanity.com/paper/2506.23561/) (2025)

## Abstract (arXiv)

Constrained generation aims to sample from language models (LMs) conditioned on hard constraints. Existing constrained-generation techniques for nondeterministic finite automaton (NFA) constraints either distort the distribution or sacrifice efficiency. Theoretically, this task reduces to counting the length-n sequences accepted by an NFA (#NFA), and the exact #NFA problem is #P-complete. Recent work has shown that #NFA admits a fully polynomial randomized approximation scheme (FPRAS). Inspired by this result, we propose NFA-LM, a polynomial-time engine for NFA-constrained generation with theoretical guarantees under mild assumptions. Experiments show that NFA-LM efficiently generates high-quality outputs with theoretically bounded approximation error.