Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees

• URL: http://arxiv.org/abs/2608.05493v1
• Date: Thu, 06 Aug 2026 00:44:46 GMT
• Title: Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees
• Abstract summary: Grammar-constrained decoding can eliminate such failures, but requires syntactic constraints.<n>In this work, we define an agent, called Autogrammar, that automatically learns context-free grammars from documentation and execution data.<n>We evaluate four versions of Autogrammar on three DSLs and find that it generates grammars that achieve near perfect precision on unseen data.
• Score: 5.635931633252131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Weave of Formal Thought [51.56484100374058]
  We introduce Weave of Formal Thought (WoFT), a paradigm uniting rigorous syntactic validation with learned structural representations.<n>We present a latent-variable fine-tuning method training the language model to interleave non-terminal grammar symbols directly into generation.<n>For Python, fine-tuning StarCoder2-3B with our RWS objective reduces per-token cross-entropy by 14.3% relative to a text-only SFT baseline.
  arXiv  Detail & Related papers  (2026-06-24T15:58:11Z)
• Encode Errors: Representational Retrieval of In-Context Demonstrations for Multilingual Grammatical Error Correction [28.920985595976873]
  Grammatical Error Correction (GEC) involves detecting and correcting the wrong usage of grammar.<n>Large language models (LLMs) with in-context learning (ICL) capabilities have shown significant progress on various natural language processing (NLP) tasks.<n>This is mainly due to the challenge of retrieving suitable in-context demonstrations that capture error patterns instead of semantic similarity.
  arXiv  Detail & Related papers  (2026-06-13T18:00:26Z)
• Reasoning over Grammar: Can Synthetic Linguistic Reasoning Traces Enhance Low-Resource Machine Translation? [49.7935995447581]
  We investigate whether low-resource machine translation can benefit from structured intermediate steps of linguistic analysis and grammatical reasoning.<n>We propose a pipeline for automatically generating step-by-step linguistic reasoning traces from Universal Dependencies treebanks, dictionaries, and grammar-rule banks.<n>Our results show that linguistic reasoning traces are most effective as inference-time guidance.
  arXiv  Detail & Related papers  (2026-06-02T15:36:12Z)
• Evaluating In-Context Translation with Synchronous Context-Free Grammar Transduction [17.60599688606413]
  Low-resource languages pose a challenge for machine translation with large language models (LLMs)<n>We construct synchronous context-free grammars which define pairs of formal languages.<n>We measure how well LLMs can translate sentences from one formal language into another when given both the grammar and the source-language sentence.
  arXiv  Detail & Related papers  (2026-04-08T17:35:44Z)
• Doc2Spec: Synthesizing Formal Programming Specifications from Natural Language via Grammar Induction [3.13621719351502]
  Doc2Spec is a framework that automatically induces a specification grammar from natural-language rules.<n>It generates formal specifications guided by the induced grammar.<n>The grammar captures essential domain knowledge, constrains the specification space, and enforces consistent representations.
  arXiv  Detail & Related papers  (2026-01-30T02:58:27Z)
• Automatic Syntax Error Repair for Discrete Controller Synthesis using Large Language Model [8.741815980649667]
  This paper presents an automated approach that leverages Large Language Models (LLMs) to repair syntax errors in DCS models.<n>It equips the LLM with DCS-specific domain knowledge, including formal grammar rules and illustrative examples, to guide accurate corrections.<n>It achieves a speedup of 3.46 times compared to human developers.
  arXiv  Detail & Related papers  (2025-12-08T07:57:15Z)
• Grammar Prompting for Domain-Specific Language Generation with Large Language Models [40.831045850285776]
  Large language models (LLMs) can learn to perform a wide range of natural language tasks from just a handful of in-context examples. We propose emphgrammar prompting, a simple approach to enable LLMs to use external knowledge and domain-specific constraints.
  arXiv  Detail & Related papers  (2023-05-30T17:26:01Z)
• Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
  grammar-constrained decoding (GCD) can be used to control the generation of large language models (LMs) GCD can serve as a unified framework for structured NLP tasks in general. We show that grammar-constrained LMs substantially outperform unconstrained LMs or even beat task-specific finetuned models.
  arXiv  Detail & Related papers  (2023-05-23T11:54:37Z)
• CLSE: Corpus of Linguistically Significant Entities [58.29901964387952]
  We release a Corpus of Linguistically Significant Entities (CLSE) annotated by experts. CLSE covers 74 different semantic types to support various applications from airline ticketing to video games. We create a linguistically representative NLG evaluation benchmark in three languages: French, Marathi, and Russian.
  arXiv  Detail & Related papers  (2022-11-04T12:56:12Z)
• A Syntax-Guided Grammatical Error Correction Model with Dependency Tree Correction [83.14159143179269]
  Grammatical Error Correction (GEC) is a task of detecting and correcting grammatical errors in sentences. We propose a syntax-guided GEC model (SG-GEC) which adopts the graph attention mechanism to utilize the syntactic knowledge of dependency trees. We evaluate our model on public benchmarks of GEC task and it achieves competitive results.
  arXiv  Detail & Related papers  (2021-11-05T07:07:48Z)
• LM-Critic: Language Models for Unsupervised Grammatical Error Correction [128.9174409251852]
  We show how to leverage a pretrained language model (LM) in defining an LM-Critic, which judges a sentence to be grammatical. We apply this LM-Critic and BIFI along with a large set of unlabeled sentences to bootstrap realistic ungrammatical / grammatical pairs for training a corrector.
  arXiv  Detail & Related papers  (2021-09-14T17:06:43Z)
• GATE: Graph Attention Transformer Encoder for Cross-lingual Relation and Event Extraction [107.8262586956778]
  We introduce graph convolutional networks (GCNs) with universal dependency parses to learn language-agnostic sentence representations. GCNs struggle to model words with long-range dependencies or are not directly connected in the dependency tree. We propose to utilize the self-attention mechanism to learn the dependencies between words with different syntactic distances.
  arXiv  Detail & Related papers  (2020-10-06T20:30:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.