aiqbench analysis
This research proposes a method to distill large language models into tractable probabilistic systems capable of efficiently satisfying formal syntactic constraints like LR(k) grammars in polynomial time. By enabling efficient steering toward valid code and data generation, the work directly addresses critical reliability challenges for integrating LLMs into automated engineering pipelines.
Tractable Hierarchical Control of Autoregressive Language Models
arXiv:2607.20483v1 Announce Type: new Abstract: 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.
Abstract: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.
Artificial Intelligence (cs.AI)
arXiv:2607.20483 [cs.AI]
(or arXiv:2607.20483v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2607.20483 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 240 words
Related coverage
Runway’s WorldPrompt and the Engineering of Real-Time Worlds
Latent Space · Sep 25, 2026
Fast Plans, Faithful Actions: Closing the Planning-Execution Gap in Hierarchical Vision-Language-Action Models
arXiv · Sep 28, 2026
PIRAMID: Progress and Plans
LessWrong · Jul 27, 2026
Language Generation as Optimal Control: Closed-Loop Diffusion in Latent Control Space
arXiv · Jun 9, 2026