Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees
On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks
Abstract (arXiv)
Language models (LMs) are increasingly used to interact with external services via programs written in domain-specific languages (DSLs). Unfortunately, since DSLs are often low-resource and esoteric, LMs frequently produce syntactically invalid programs in these languages. Grammar-constrained decoding can eliminate such failures, but requires syntactic constraints. These are usually in the form of a context-free grammar for the target language, an artifact that is hard to come by for third-party DSLs. In this work, we define an agent, called Autogrammar, that automatically learns context-free grammars from documentation and execution data. Autogrammar is formalized as a Kripke structure whose nondeterministic choices are resolved by a language model, enabling declarative control of agent behavior via linear temporal logic constraints. We evaluate four versions of Autogrammar on three DSLs (i.e., Amazon CloudWatch Logs Insights, Dynatrace Query Language, and Datadog Search Syntax) and find that it generates grammars that achieve near perfect precision on unseen data; that temporal restrictions reduce execution time by 3.8x without incurring statistically-significant loss in precision; that execution data is crucial while documentation is dispensable; and that grammar-constrained decoding using Autogrammar-generated grammars significantly improves end-to-end LM performance on eight out of ten real tasks, matching or exceeding the performance of a professionally-maintained grammar. In comparison, the context-free grammars generated by existing LM baselines and a state-of-the-art formal technique perform significantly worse over the same evaluation.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. Builds on 15 of its 37 references that are in the map. First posted on arXiv 6 Aug 2026.
Builds on
15 of 37 references.
Closest ancestors · 1
Same direction, newest first
Other references · 14
- 2023MemGPT: Towards LLMs as Operating Systemscited by 1,389
- 2023DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correctioncited by 477
- 2023Grammar-Constrained Decoding for Structured NLP Tasks without Finetuningcited by 197
- 2023ProofNet: Autoformalizing and Formally Proving Undergraduate-Level Mathematicscited by 192
- 2024A Survey on LLM-based Code Generation for Low-Resource and Domain-Specific Programming Languagescited by 66
- 2026Solver-Aided Verification of Policy Compliance in Tool-Augmented LLM Agentscited by 16
- 2024Synthetic Programming Elicitation for Text-to-Code in Very Low-Resource Programming and Formal Languagescited by 6
- 2021Learning Highly Recursive Input Grammarscited by 4
- 2023Regexes are Hard: Decision-making, Difficulties, and Risks in Programming Regular Expressionscited by 4
- 2026Early Diagnosis of Wasted Computation in Multi-Agent LLM Systems via Failure-Aware Observabilitycited by 4
- 2016Synthesizing Program Input Grammarscited by 3
- 2025HyGenar: An LLM-Driven Hybrid Genetic Algorithm for Few-Shot Grammar Generationcited by 2
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
- 2025The Ann Arbor Architecture for Agent-Oriented Programming
- 2025Putting It All into Context: Simplifying Agents with LCLMs
- 2024AutoGRAMS: Autonomous Graphical Agent Modeling Software
- 2026Diagnosing CFG Interpretation in LLMs
- 2026Learning and Enforcing Context-Sensitive Control for LLMs
- 2025A Self-Improving Coding Agent
- 2025AutoPDL: Automatic Prompt Optimization for LLM Agents