Steering a language model towards satisfying a constraint requires marginalizing the probability that a future continuation will be valid. Hidden Markov models have proven effective as tractable surrogates for such marginalization, but existing methods only handle constraints expressible as 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. We demonstrate the effectiveness of CTRL-CFG on chemistry-grammar conditioned molecule generation.

@inproceedings{MaeneTPM26,
  title     = {Tractable Constrained Generation with LL(1) Grammars},
  author    = {Maene, Jaron and Van den Broeck, Guy},
  booktitle = {Proceedings of the UAI Workshop on Tractable Probabilistic Modeling (TPM)},
  url       = "https://starai.cs.ucla.edu/papers/MaeneTPM26.pdf",
  month     = 7,
  year      = {2026},
  keywords  = {workshop}
}