Tractable Hierarchical Control of Autoregressive Language Models
For developers and researchers using LLMs for program synthesis or structured data generation, this work provides a tractable method to enforce syntactic constraints, which is a prerequisite for integrating LLMs into formal systems.
This paper improves the efficiency of constraining autoregressive LLMs to generate syntactically valid output for LR(k) grammars, reducing the time complexity from exponential to polynomial. This enables faster and more reliable generation of code and data formats like SQL and JSON.
Constraining the generation of autoregressive large language models (LLMs) is an important component of integrating language models into formal systems. In the generation of code and data for tasks like program synthesis, ensuring that language models produce syntactically valid output is a prerequisite for processing such output. These languages (such as SQL or JSON) are often designed as $LR(k)$ context-free grammars. By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints, ensuring high quality output that is guaranteed to be valid. This paper demonstrates that the satisfaction of any $LR(k)$ grammar of finite duration can be calculated in polynomial time, an improvement over the exponential time of applying previous methods to such grammars. This result enables efficient constraint and steering of LLM generation towards output that better satisfies formal syntactic constraints.