Provably Tractable NFA-Constrained Language Generation via HMMs
The paper proposes NFA-LM as a polynomial-time method for hard-constrained language generation with bounded approximation error.
The authors frame NFA-constrained generation as a counting problem over length-n accepted sequences, noting exact #NFA is #P-complete. They build on recent FPRAS results for #NFA to argue tractability under mild assumptions. Experiments reported in the abstract say the system generates high-quality outputs efficiently while preserving theoretical approximation guarantees. ArXiv · AI/CL/LG's note
The authors frame NFA-constrained generation as a counting problem over length-n accepted sequences, noting exact #NFA is #P-complete. They build on recent FPRAS results for #NFA to argue tractability under mild assumptions. Experiments reported in the abstract say the system generates high-quality outputs efficiently while preserving theoretical approximation guarantees. ArXiv · AI/CL/LG's note
score 5