arXiv：cs.CL· Jialiang Sun, Kuldeep Meel·· 6 小时前AI 评分39
基于 HMM 的可证明可处理 NFA 约束语言生成
Provably Tractable NFA-Constrained Language Generation via HMMs
AI 导读
研究者提出 NFA-LM，一个多项式时间的 NFA 约束生成引擎，在温和假设下具备理论保证。该任务可归约为 #NFA 计数问题，而精确 #NFA 是 #P-complete，近期工作证明其存在 FPRAS。实验显示 NFA-LM 能高效生成高质量输出，且近似误差有理论界。
正文
Abstract: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.
| Subjects: | Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL) |
| Cite as: | arXiv:2609.40185 [cs.CL] |
| (or arXiv:2609.40185v2 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2609.40185 arXiv-issued DOI via DataCite |
Submission history
From: Jialiang Sun [view email]
[v1]
Wed, 30 Sep 2026 17:07:22 UTC (439 KB)
[v2]
Tue, 6 Oct 2026 03:29:48 UTC (439 KB)
来源：arXiv：cs.CL · arxiv.org