Flexible and Efficient Grammar-Constrained Decoding

This paper focuses on the practical cost of grammar-constrained decoding. Grammar-constrained decoding can guarantee that generated outputs follow a context-free grammar, but efficient implementations must reconcile two different token systems: the grammar’s terminals and the language model’s subword tokenizer.

The work introduces a more flexible and efficient algorithm for computing the token masks needed during decoding. The main improvement is in offline preprocessing, making it faster to prepare common grammars while preserving efficient online mask computation during generation.

This is useful for structured generation tasks such as code, data formats, and other domains where syntax errors are unacceptable. The work appeared at ICML 2025.