Provably Tractable NFA-Constrained Language Generation via HMMs

Jialiang Sun; Kuldeep Meel

cs.CLSep 30, 2026

Provably Tractable NFA-Constrained Language Generation via HMMs

Authors: Jialiang Sun, Kuldeep Meel

Organizations: University of Toronto

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.

Figures & tables

Panel of Figure 1 — Figure 1: Top : An NFA $A$ over $\Sigma=\{0,1,2\}$ with ordered states $q_{0}\prec\cdots\prec q_{5}$ and final state $q_{5}$ . Bottom : The unrolled NFA $A^{u}$ of $A$ for length $n=4$ .

Family	Constraint	NFA states	DFA states
kth_last	The $k_{1}$ -th token from the end is one of the tracked keywords.	$\Theta(k_{1})$	$\Theta(2^{k_{1}})$
repeat_after_k	Some tracked keyword repeats $k_{1}$ tokens apart.	$\Theta(k_{1}k_{2})$	$\Theta(k_{2}^{k_{1}})$
at_least_k	Some tracked keyword appears at least $k_{1}$ times.	$\Theta(k_{1}k_{2})$	$\Theta(k_{1}^{k_{2}})$
exactly_once	Some tracked keyword occurs exactly once.	$\Theta(k_{2})$	$\Theta(3^{k_{2}})$
left_not_right	Some tracked keyword occurs on the left of the separator but not on the right.	$\Theta(k_{2})$	$\Theta(2^{k_{2}})$
right_not_left	Some tracked keyword occurs on the right of the separator but not on the left.	$\Theta(k_{2})$	$\Theta(2^{k_{2}})$

Table 1: The ten constraint families and their minimum numbers of NFA and DFA states.

Method	Success	Time (s)	Quality
LLM-only
GPT-5.6 Luna	306 (61.2%)	1.9	2.93
Qwen3.5-2B	190 (38.0%)	1.0	1.89
Gemma-4-E2B	227 (45.4%)	1.0	2.70
XGrammar
Qwen3.5-2B	500 (100.0%)	2.8	1.75

Table 2: Overall results of successful constraint-satisfaction, average elapsed time, and quality. The quality score is computed over instances with constraint-satisfying outputs.

Figure 2: Elapsed time (s) of NFA-LM and Ctrl-G versus the number of NFA states for each constraint family. Crosses denote instances that timed out or encountered out-of-memory errors.

Figure 3: Maximum relative error of NFA-LM against exact HMM constraint probabilities for Gemma-4-E2B.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Algorithm 6 $\mathsf{estimateAndSample}(q,j,\ell)$ (oracle-corrected $\mathcal{N}^{*,j}$ )

Explore similar work

Suffix-Constrained Greedy Search Algorithms for Causal Language Models
Mar 1, 2026Ayoub Hammal, Pierre Zweigenbaum, Caio CorroLarge Language Model Generation Data Generation
1Université Paris-Saclay, CNRS, LISN · 2INSA Rennes, IRISA, CNRS, Université de Rennes
Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata
Jul 8, 2026Meihua Dang, Stefano ErmonConstrained Decoding Diffusion Language Models
Stanford University
Mistake-Bounded Language Generation
May 11, 2026Jon Kleinberg, Charlotte Peale, Omer ReingoldConvergence Logarithmic Scaling
Departments of Computer Science and Information Science Cornell University Ithaca, NY · Department of Computer Science Stanford University Stanford, CA

Mar 1, 2026, cs.CLJ/K move · Enter open · S save

Suffix-Constrained Greedy Search Algorithms for Causal Language Models

Ayoub Hammal, Pierre Zweigenbaum, Caio Corro

1Université Paris-Saclay, CNRS, LISN · 2INSA Rennes, IRISA, CNRS, Université de Rennes

Large Language Model Generation Data Generation Context-Free Grammars

Open paper AskPDF arXiv

Large language models (LLMs) are powerful tools that have found applications beyond human-machine interfaces and chatbots. Beside free-form generation, there has been an interest in constrained generation, a setting where LLMs are constrained to generate well-formed outputs with respect to the language defined by a formal grammar. Although appealing, this setting may be over restrictive for downstream applications. For example, many LLM tasks require the model to reason freely before generating its final response in a specific format. In this work, we introduce suffix-constrained generation, a constrained generation setting in which only the end of the response is constrained by a grammar, a scenario that is not supported by existing constrained generation methods. We introduce several suffix-constrained generation algorithms that are based on greedy search. We experiment on several datasets, and show that our approach allows to guarantee suffix constraints without having a negative impact on results, and even improving them in many settings.

Abstract

Explore similar work

Suffix-Constrained Greedy Search Algorithms for Causal Language Models

Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

Mistake-Bounded Language Generation