Imagine you're playing Scrabble, but instead of just finding any valid word, you need to find words that a particular player would plausibly choose — matching both the dictionary constraint AND the player's style. You could enumerate every legal word and rank them by likelihood, but the dictionary is exponentially large. What if you could build a fast approximation of the player-dictionary intersection that's provably close to the real thing? That's what NFA-LM does for language models. The committed claim: NFA-LM is the first polynomial-time constrained generation engine for NFA constraints that provides theoretical approximation guarantees without distorting the target distribution. Prior approaches either used DFA-based methods that blow up exponentially when converting from NFAs, or used heuristic NFA techniques (like GeLaTo) that sacrifice distributional fidelity. The key insight is that approximate #NFA counting — known to admit an FPRAS — can be operationalized as a practical generation engine by leveraging Hidden Markov Models as the approximation substrate. The architecture sits at the intersection of formal language theory and probabilistic generation. NFA-LM treats the constrained LM distribution as a product of the language model's token probabilities and an NFA acceptance indicator. Since exact computation of the partition function (counting accepted sequences) is #P-complete, the paper uses HMM-based approximation to estimate next-token probabilities under the constraint. The HMM acts as a tractable proxy for the NFA's state-tracking, converting a combinatorially hard counting problem into a sequence of matrix operations. On the ladder: the paper positions itself against GeLaTo (the recent FPRAS-based approach for #NFA) and DFA-based constrained decoding. The key comparison is distributional accuracy — NFA-LM claims bounded total variation distance from the true constrained distribution, whereas GeLaTo provides counting approximations but doesn't directly translate to generation with distributional guarantees. Against DFA methods, the win is efficiency: NFA-to-DFA conversion can be exponential, while NFA-LM stays polynomial. The paper reports experiments showing efficient generation with bounded approximation error, though specific speedup numbers and benchmark scales are not detailed in the abstract. Integrity-wise, we're looking at a theory-first paper. The guarantees are mathematical — polynomial time under 'mild assumptions' (a phrase that always deserves scrutiny; the specific assumptions matter enormously for practical relevance). The experimental validation appears to be the authors' own benchmarks rather than community-standard constrained generation tasks. The #P-completeness of exact #NFA is well-established classical complexity theory, so the theoretical foundation is solid. The question is whether the 'mild assumptions' hold for real LMs and real constraints at production scale. The milestone to watch is whether NFA-LM (or its descendants) can handle production-scale constrained generation — think 100K+ token vocabularies, constraints with thousands of NFA states, and latency requirements under 100ms per token. The gap between polynomial-time theoretical guarantees and wall-clock practical performance at scale is where most theory-to-practice translations stall. The obvious experiment not run: scaling to large transformer LMs (GPT-scale) with complex real-world NFA constraints like regex patterns over full vocabularies. My read is (a) — compute and engineering effort. Building a production-grade HMM approximation layer that interfaces with a 70B-parameter model's token distribution is a significant systems challenge, and this paper is establishing the theoretical machinery first. The follow-up paper will likely be the scaling story.
