Provably Tractable NFA-Constrained Language Generation via HMMs
NFA-LM provides a polynomial-time engine for generating text conditioned on hard constraints defined by Non-deterministic Finite Automata (NFAs). It achieves this by distilling the complex conditional probability into an approximate Hidden Markov Model (HMM) and using precomputed samples to ensure theoretical guarantees on accuracy and running time.