CTRL-CFG: Tractable Constrained Decoding with LL(1) Grammars

Language models often need to generate structured outputs that satisfy a context-free grammar such as JSON or Python. Steering a language model towards satisfying such a grammar requires marginalizing the probability that a future continuation will be grammatical. Hidden Markov models have proven effective as tractable surrogates for this marginalization, but existing methods focused on regular languages. We extend this line of work to LL(1) grammars, a widely used subset of context-free grammars. Unfortunately, even with a tractable surrogate, constrained generation with unambiguous grammars is still cubic time in the sequence length. We hence develop **CTRL-CFG**, a linear-time approximation that marginalizes only over a fixed look-ahead window. Experiments on program synthesis and molecule generation illustrate the potential of this approach as a step towards more broadly usable tractable constrained decoding.