mlsanityData to 14 Oct 2026

Provably Tractable NFA-Constrained Language Generation via HMMs

arXiv 2609.40185 ↗First posted 30 Sep 2026cs.CL cs.FLcited by 0

Not on the map. Why?

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.

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

17 of 31 references.

References · 17

  1. 2023Gorilla: Large Language Model Connected with Massive APIscited by 1,332
  2. 2020RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Modelscited by 1,255
  3. 2021PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Modelscited by 411
  4. 2022COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamicscited by 161
  5. 2023Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programscited by 80
  6. 2023Evaluating Large Language Models on Controlled Generation Taskscited by 73
  7. 2025JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Modelscited by 71
  8. 2023Tractable Control for Autoregressive Language Generationcited by 65
  9. 2022Gradient-Based Constrained Sampling from Language Modelscited by 64
  10. 2023Bounding the Capabilities of Large Language Models in Open Text Generation with Prompt Constraintscited by 31
  11. 2025Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Samplingcited by 21
  12. 2025Constrained Sampling for Language Models Should Be Easy: An MCMC Perspectivecited by 14
5 more
  1. 2025TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generationcited by 8
  2. 2026Mitigating Bias in Locally Constrained Decoding via Tractable Proposalscited by 8
  3. 2026XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMscited by 7
  4. 2019#NFA admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classescited by 1
  5. 2025Towards practical FPRAS for #NFA: Exploiting the Power of Dependencecited by 1

Built on by

Not cited yet.