Skip to content

Minimal Grammars as Supervision for DSL Generation

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/davidraine907/grammar-solve
Area: LLM Reasoning
Keywords: Domain-Specific Languages, Semantic Parsing, Hardware Description Languages, Minimal Grammars, Retrieval-Augmented Generation

TL;DR

This paper introduces minimal grammars—the exact, non-redundant subset of DSL productions (typically 2%–20% of the full reference grammar) required to derive a target program—as an explicit structural supervision signal for fine-tuning open-weight models, coupled with an inference-time RAG+CoT grammar predictor that delivers massive accuracy leaps across semantic parsing and hardware description languages.

Background & Motivation

Large language models have reached near-saturation on mainstream general-purpose programming benchmarks like HumanEval and MBPP, routinely producing correct executable implementations for Python and standard software routines. However, this success degrades sharply when models are tasked with synthesizing code in domain-specific languages (DSLs), such as semantic parsing formalisms (e.g., SMCalFlow, GeoQuery, Overnight) and hardware description languages (e.g., Verilog, SPICE). Two fundamental obstacles explain this discrepancy: first, paired natural language and code datasets for DSLs are dwarfed by the massive corpora available for general-purpose languages; second, DSLs exhibit rigid, idiosyncratic syntactic constructs and execution semantics that transfer poorly from the statistical priors absorbed during general pretraining.

Prior efforts to inject grammatical structure into language models have primarily explored two contrasting paradigms: in-context grammar prompting with full or specialized reference grammars, and standard unconstrained supervised fine-tuning. Both approaches suffer from intrinsic shortcomings. Full reference grammars contain hundreds of candidate rules, which congest the prompt context and drown the model in irrelevant alternative derivations. Conversely, unconstrained fine-tuning forces the model to implicitly memorize and infer latent compositional grammar rules from sparse end-to-end program strings alone. Crucially, attempting to train models to jointly generate both the grammar and the program (\(x \to G(y) \cdot y\)) in an autoregressive fashion induces catastrophic teacher-forcing brittleness, where sampling errors in early grammar tokens propagate irreversibly into the generated code.

The authors identify a pivotal structural opportunity: while an entire DSL grammar is expansive, any individual target program requires only a tiny fraction of the production rules—typically between 2% and 20% of the complete grammar. By extracting these minimal, derivation-specific rule subsets and supplying them as explicit structural scaffolding during training, the model can learn to ground natural language intents directly into valid DSL derivations. Core idea: augment each training example with its minimal grammar subset as conditioning context while using grammar dropout to maintain robustness, and deploy an inference-time retrieval-augmented reasoning predictor to dynamically provide candidate minimal grammars for test queries.

Method

Overall Architecture

The proposed framework decouples structural grammar prediction from downstream program generation, establishing a two-stage pipeline. During the offline training phase, every training target program \(y\) is parsed against the reference context-free grammar \(G\) to extract its minimal grammar \(G(y)\), comprising only the exact productions utilized in its derivation tree. Open-weight language models are fine-tuned on the concatenated prefix \((x, G(y))\) to generate \(y\), accompanied by a 10% grammar dropout schedule that trains the backbone to treat supplied grammars as suggestive guidance rather than brittle dependencies. At inference time, where gold grammars are absent, a retrieval-augmented generation (RAG) module embeds test query \(x\), retrieves \(k=16\) nearest training exemplars, and prompts a frontier model enriched with chain-of-thought (CoT) traces to predict the candidate minimal grammar \(\hat{G}_x\), which is then fed alongside \(x\) into the fine-tuned generator.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Natural Language Test Query x"] --> B["Stage 1: Dense Retrieval & CoT Grammar Prediction<br/>BGE-large k-NN retrieval + frontier CoT explanation"]
    B --> C["Stage 2: Minimal Grammar & Query Concatenation<br/>Pruned production rules subset (2%–20% |G|)"]
    C --> D["Stage 3: Grammar-Conditioned Fine-Tuning with Dropout<br/>10% dropout for robustness + loss computed solely on y"]
    D --> E["Executable Target Program y ∈ L(G)<br/>Semantic parsing FunQL/λ-DCS or Verilog/SPICE netlist"]

Key Designs

1. Minimal Grammar Extraction & Concrete Literal Instantiation: Pruning Search Spaces to Core Derivation Subsets

To eliminate extraneous candidate productions that distract models during code generation, the method formalizes a minimal grammar \(G(y)\) relative to a full grammar \(G = (N, \Sigma, P, S)\) and a program \(y\). Formally, \(G(y) \subseteq G\) satisfies two conditions: \(y \in L(G(y))\), and for every production rule \(r \in G(y)\), \(y \notin L(G(y) \setminus \{r\})\). In practice, an automated parser traverses the derivation tree of \(y\) and extracts only the active productions, discarding all alternative non-terminal expansions. Furthermore, generic rules that match unbounded literal classes (such as string ::= ESCAPED_STRING in SMCalFlow) are concretely instantiated to the exact literal appearing in \(y\) (e.g., string ::= "Bob"). As evidenced in empirical statistics, the compression ratio \(|G(y)|/|G|\) spans from 2% in GeoQuery (4.7 rules out of 237) to 20% in Verilog (65.2 out of 332). This radical pruning isolates the necessary structural skeleton, transforming an open-ended code generation task into bounded rule composition.

2. Decoupled Retrieval-Augmented Grammar Prediction: Leveraging Exemplar Geometry & CoT Reasoning

Because gold minimal grammars are inaccessible at test time, the architecture employs a decoupled inference predictor instead of joint generation or multi-label rule classifiers. For a given test query \(x\), the system computes sentence embeddings using BGE-large-en-v1.5 and retrieves the \(k=16\) nearest training queries under cosine similarity along with their associated gold minimal grammars. To maximize predictor faithfulness, training examples are pre-annotated with GPT-5.5-generated chain-of-thought (CoT) traces that explicitly explain why specific productions are mandatory while competing alternatives in the global grammar are rejected. At test time, a frontier LLM (GPT-5.5 or Claude Opus 4.7) ingests these 16 (query, CoT, grammar) in-context exemplars and emits the predicted minimal grammar \(\hat{G}_x\). Decoupling prediction from generation ensures that advancements in frontier reasoning models can immediately upgrade the grammar predictor without requiring retraining of the downstream generation adapters.

3. Grammar Dropout & Asymmetric Autoregressive Supervised Fine-Tuning: Safeguarding against Noise and Teacher Forcing

To address the unavoidable noise in predicted grammars—where test-time grammars may omit necessary rules or include spurious ones—the fine-tuning procedure establishes two critical safeguards. First, loss is computed strictly over the tokens of target program \(y\), avoiding any gradient coupling between grammar tokens and code generation tokens that would otherwise trap the model in fragile teacher-forcing artifacts. Second, a grammar dropout mechanism randomly omits \(G(y)\) with probability \(p = 0.1\) during training, feeding only \(x \to y\). This stochastic omission prevents the policy from collapsing into an inflexible lookup mechanism. Extensive dropout sweeps demonstrate that the fine-tuned model maintains peak generation accuracy under both oracle and noisy predicted grammars across dropout rates from 0.0 to 0.8, while retaining the ability to gracefully fall back to baseline performance when grammars are omitted entirely.

Loss & Training

Open-weight backbones (Qwen-3.5 4B/9B, Gemma-3 27B, Qwen-2.5 7B, Llama-3.1 8B, Gemma-3 12B) are adapted using LoRA (\(r=64, \alpha=128, \text{dropout}=0.05\) targeting all linear layers). Models are trained on a single NVIDIA A100 80GB GPU using AdamW with fused kernels, a learning rate of \(10^{-4}\) with a cosine decay schedule (0.05 warmup ratio), bfloat16 mixed precision, and FlashAttention-2. Maximum sequence length is set to 1024 tokens for semantic parsing and 2048 tokens for hardware description languages. The objective is standard token-level cross-entropy calculated exclusively on program tokens \(y\): $$ \mathcal{L}(\theta) = - \sum_{j=1}^{m} \log P_\theta(y_j \mid x, \tilde{G}(y), y_{<j}) $$ where \(\tilde{G}(y)\) represents the minimal grammar conditioned with 10% dropout.

Key Experimental Results

Main Results

The method was evaluated across five benchmarks spanning semantic parsing (SMCalFlow, GeoQuery, Overnight) and hardware description languages (VerilogEval-Human, SPICE netlists). The primary metrics reported are program exact match accuracy (Prog.), execution accuracy (Exec.), Verilog pass@k, and SPICE normalized Graph Edit Distance (GED) similarity and component F1.

Backbone Model Method SMCalFlow Prog. GeoQuery Prog. GeoQuery Exec. Overnight Prog. Overnight Exec. Verilog pass@1 SPICE GED SPICE F1
Qwen-3.5 4B Baseline 45.0 61.1 74.6 41.1 60.7 25.5 59.4 77.4
Ours (RAG) 72.9 86.8 95.4 47.4 66.4 39.2 72.2 81.8
Ours + Gold 88.2 96.4 97.9 97.2 99.2 49.6 96.7 94.3
Qwen-3.5 9B Baseline 49.0 75.0 84.3 45.6 64.7 32.2 64.3 79.4
Ours (RAG) 85.8 87.5 96.1 47.4 66.7 42.8 72.0 81.9
Ours + Gold 92.6 97.5 98.2 97.2 99.2 53.6 96.7 94.0
Gemma-3 27B Baseline 56.8 71.8 86.1 47.9 64.7 33.5 64.8 79.6
Ours (RAG) 86.1 87.5 95.4 47.4 66.7 42.7 72.0 81.8
Ours + Gold 91.5 96.8 97.5 97.2 99.2 53.5 96.7 94.2

In in-context learning with frontier models (\(k=16\)), minimal grammars predicted via RAG+CoT raised GPT-5.5 program accuracy on SMCalFlow from 46.4% (programs only) and 51.4% (standard grammar prompting) to 94.3%. Similarly, Claude Opus 4.7 jumped from 49.4% to 91.2%.

Ablation Study

Ablations on Qwen-3.5 9B across SMCalFlow and Verilog disentangle the impact of token counts, joint generation, and chain-of-thought traces.

Configuration / Variant SMCalFlow Prog. (%) Verilog pass@1 (%) Insight & Failure Mode
Baseline (1 epoch) 49.0 32.2 Standard supervised fine-tuning without grammars
Baseline (2 epochs) 62.4 36.0 Additional gradient steps close part of the gap but trail Ours by 23.4pp / 6.8pp
Joint generation (\(x \to G(y) \cdot y\)) 42.5 21.5 Training analogue of grammar prompting; teacher forcing collapses test accuracy
RAG without CoT 67.0 41.0 Retrieval alone provides primary structural lift (+18.0pp / +8.8pp)
Ours (RAG + CoT) 85.8 42.8 Full pipeline; CoT reasoning yields critical rule selection precision

Key Findings

  • Compression Ratio Correlates with Gain Magnitude: The performance boost is inversely proportional to the \(|G(y)|/|G|\) ratio. In SMCalFlow, where minimal grammars constitute only ~4.4% of the reference grammar, pruning irrelevant productions delivers an immense +36.8pp surge. In Verilog, where programs use ~19.6% of the rules and circuit correctness heavily hinges on interconnect topology, accuracy improves by +10.6pp.
  • Remarkable Robustness to Imperfect Grammars: In Verilog and SPICE test suites, fewer than 20% of predicted grammars exactly match the gold minimal grammar (17.3% and 18.0%, respectively), with the majority exhibiting missing or extraneous rules. Nonetheless, the fine-tuned generator leverages the partial structural prior to consistently outperform grammar-free fine-tuning.
  • Annotation Ambiguity on Overnight: Overnight exhibits flat test gains under predicted grammars (45.6% to 47.4%) despite a high gold grammar ceiling of 97.2%. The root cause is semantic ambiguity: block spatial relationships possess non-inverse dual representations (e.g., querying above vs. inverting below), causing 91% of retrieved neighbor sets to provide conflicting minimal grammars.

Highlights & Insights

  • Decoupled Structural Supervision: By separating the structural grammar induction task (performed by an in-context frontier retriever) from the syntax-constrained generation task (performed by a fine-tuned open-weight model), the framework combines high accuracy with practical parameter efficiency.
  • The Pitfall of Autoregressive Joint Generation: The failure of training-time joint generation (\(x \to G(y) \cdot y\)) confirms that forcing models to output intermediate symbolic grammars under teacher forcing induces catastrophic fragility when exposed to sampled decoding errors at inference.
  • Grammar Dropout as Soft Scaffolding: Applying stochastic grammar omission during training forces the decoder to internalize grammars as assistive conditioning hints rather than brittle crutches, granting seamless resilience against retrieval noise.

Limitations & Future Work

  • Blindness to Topological Interconnects: Minimal grammars specify the set of active symbols and components but do not encode connection topologies (e.g., netlist wiring in Verilog or node pinouts in SPICE), imposing an upper ceiling on hardware synthesis.
  • Requirement of Formal Reference Grammars: Computing training-time minimal grammars requires an unambiguous, parsable reference grammar, limiting applicability to formal DSLs and excluding loosely structured configuration files or evolving query formats.
  • Inference Dependence on Frontier Models: The inference-time grammar predictor relies on high-tier frontier models (GPT-5.5 / Claude Opus 4.7) for CoT in-context learning. Developing lightweight, dedicated grammar retrieval and filtering models remains a vital open direction.
  • vs. Grammar Prompting (Wang et al., 2023): Wang et al. explored minimal grammars as prompting scaffolding for early code models (Codex-davinci-002), where it provided modest CoT-like benefits; on modern frontier LLMs, standard grammar prompting is largely flat (0–5pp). This work repurposes minimal grammars as an explicit supervision signal for supervised fine-tuning.
  • vs. Synthetic Data Scaling (MG-Verilog, OmniSQL): Prior methods synthesize millions of paired data points to overcome low-resource limits; this paper extracts high-density structural supervisory signals from the existing compact training pool without synthetic token bloat.
  • vs. AST-Aware Masked Pretraining (AST-T5): AST-based pretraining requires specialized masking objectives and immense computational re-training; minimal grammar supervision operates seamlessly atop standard autoregressive transformer weights via lightweight parameter-efficient adapters.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Pioneering the use of non-redundant minimal grammar subsets as training-time supervision while decoupling inference prediction.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous validation across five distinct semantic parsing and hardware description benchmarks, spanning six open-weight and frontier models with precise token-budget ablations.
  • Writing Quality: ⭐⭐⭐⭐⭐ Flawless conceptual exposition, mathematically rigorous formalization, and transparent structural error categorization.
  • Value: ⭐⭐⭐⭐⭐ Offers an exceptionally impactful, practical blueprint for synthesizing high-reliability code in low-resource domain-specific languages.