PaperlayerView exact revision on arXiv

Source-linked AI summary

Grammar Prompting for Domain-Specific Language Generation with Large Language Models

Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, Yoon Kim

arXiv:2305.19234v3cs.CLcs.AI

TL;DR

Few-shot examples can be insufficient for generating structured DSL strings, whose syntax and domain-specific constraints may be difficult to convey. Grammar prompting augments examples with minimal BNF grammars and predicts a grammar before generating each answer; experiments report improvements over standard prompting across several DSL tasks, with limitations in some settings.

  • Problem

    A handful of demonstrations may not convey DSL syntax and domain-specific abstractions adequately, making few-shot generation of structured strings challenging.

    Source: §1 · p. 1, §2.2 · p. 2

  • Method

    Grammar prompting augments each demonstration with a minimally sufficient specialized BNF grammar, predicts a grammar for the test input, and generates an answer conditioned on it.

    Source: §1 · p. 1

  • Results

    Grammar prompting improves on standard prompting baselines across semantic parsing, PDDL planning, and SMILES molecule-generation tasks.

    Source: §1 · p. 2, §7 · p. 11

  • Takeaways & Limitations

    The authors conclude that grammar prompting has potential to assist LLM tool use and support applications in domains that intrinsically depend on DSLs.

    Source: §7 · p. 11

    It yielded no improvements for DSLs likely frequent in pretraining, constrained generation increased API calls, and constraints sometimes reduced molecule diversity or hurt PDDL performance.

    Source: §5 · p. 9

Abstract

from arXiv · show

Large language models (LLMs) can learn to perform a wide range of natural language tasks from just a handful of in-context examples. However, for generating strings from highly structured languages (e.g., semantic parsing to complex domain-specific languages), it is challenging for the LLM to generalize from just a few exemplars. We propose \emph{grammar prompting}, a simple approach to enable LLMs to use external knowledge and domain-specific constraints, expressed through a grammar in Backus--Naur Form (BNF), during in-context learning. Grammar prompting augments each demonstration example with a specialized grammar that is minimally sufficient for generating the particular output example, where the specialized grammar is a subset of the full DSL grammar. For inference, the LLM first predicts a BNF grammar given a test input, and then generates the output according to the rules of the grammar. Experiments demonstrate that grammar prompting can enable LLMs to perform competitively on a diverse set of DSL generation tasks, including semantic parsing (SMCalFlow, Overnight, GeoQuery), PDDL planning, and SMILES-based molecule generation.

1 Introduction

Few-shot demonstrations alone can underspecify DSL syntax and semantics, making structured generation challenging. Grammar prompting adds minimal BNF grammars to demonstrations, predicts a grammar at test time, and improves on standard prompting across several DSL tasks.

1 Introduction

  • DSL generation is difficult in few-shot settings because domain-specific abstractions, semantics, and syntax may not be conveyed by a handful of examples or acquired during pretraining.This challenge is especially relevant to semantic parsing into executable programs.Source: §1 · p. 1
  • The method augments each demonstration with a minimal specialized BNF grammar, then predicts a grammar for the test input before generating the answer conditioned on it.The specialized grammar is minimally sufficient for its example output and is a subset of the full DSL grammar.Source: §1 · p. 1
  • Unlike natural-language intermediate reasoning, the formal grammar focuses on symbolic manipulation, supports syntactic constraints during decoding, and can be derived automatically by parsing the output.The authors also describe a constrained decoding algorithm designed to guarantee syntactic validity while minimizing LLM API calls.Source: §1 · p. 2
  • Grammar prompting improves on standard prompting baselines across semantic parsing, PDDL planning, and SMILES molecule generation.The evaluated semantic parsing tasks include SMCalFlow, Overnight, and GeoQuery.Source: §1 · p. 2

2 Background

The section frames DSL generation as producing application-specific strings from inputs and reviews why few-shot prompting is challenging for these structured outputs. It assumes an expert-defined BNF grammar that specifies DSL syntax.

2.1 Problem Formulation: Domain-Specific Language Generation

  • A DSL generation task maps an input, such as a natural-language command, to an output string in the application’s domain-specific language.The calendar example maps a meeting request to a program.Source: §2.1 · p. 2
  • The formulation assumes an expert-defined context-free BNF grammar G that specifies DSL syntax, with the DSL contained in the grammar’s language; syntactic validity does not guarantee semantic validity.The passage states D ⊆ L(G) ⊆ Σ* and notes that not all syntactically valid programs are semantically valid.Source: §2.1 · p. 2

2.2 Few-shot Learning with Large Language Models

  • Few-shot DSL generation remains challenging because a handful of demonstrations cannot adequately capture the grammar’s structured, combinatorial output space.The background describes in-context learning with demonstration examples and optional natural-language instructions or intermediate reasoning steps.Source: §2.2 · p. 2

3 Grammar Prompting

Grammar prompting specializes a full DSL grammar for each example and uses predicted grammars to guide output generation. The section also describes an Earley-based decoding procedure that repairs invalid predictions into valid continuations.

3 Grammar Prompting

  • BNF is used as the prompting metalanguage because DSL strings may be rare in pretraining, while BNF grammars are standard descriptions of language syntax expected to occur in training data..Source: §3 · p. 3
  • Prepending the full BNF grammar to demonstrations did not improve performance in preliminary experiments.For some experiments with sufficiently small grammars, the authors nevertheless included the full grammar in the instructions after observing small improvements when it was combined with specialized grammars.Source: §3 · p. 3, §3.1 · p. 3

3.1 Specialized Grammars

  • A minimal specialized grammar is a subset of the full grammar’s rules that generates the target output, with no included rule removable while preserving that property.It can be obtained by parsing the output with the full grammar and taking the union of rules used in its derivation.Source: §3.1 · pp. 3–4
  • Demonstrations interleave each input, its minimal specialized grammar, and its output; inference predicts a specialized grammar and then generates a program conditioned on it.The inference procedure uses approximate arg max decoding for grammar prediction.Source: §3.1 · p. 4
  • Grammar prompting treats DSL generation as selecting production rules from the full grammar and then deducing a program from those selected rules.The intermediate grammar is a formal-grammar counterpart to an intermediate reasoning step, though the program can remain uncertain given that grammar.Source: §3.1 · p. 4

3.2 Constrained Decoding

  • Directly restricting each API decoding step to valid continuations is costly because valid terminals can span multiple BPE tokens and the valid set changes over time.The described approach would require an API call at every step with the full prompt, prefix, and disallowed continuations.Source: §3.2 · p. 4
  • Instead, decoding speculatively proposes a full program; when it is invalid, an Earley parser finds the longest valid prefix and valid next terminals for constructing a corrected partial program.The corrected partial program is fed back to the LLM for continuation.Source: §3.2 · pp. 4–5, Figure 3 · p. 5
  • The constraints guarantee syntactic validity, but grammar prompting still meaningfully improves on standard prompting with simple unconstrained decoding.The passage reports this finding in an ablation study.Source: §3.2 · p. 5

4 Experiments

The experiments assess grammar prompting against standard prompting across semantic parsing, class-specific molecule generation, and PDDL planning. They cover few-shot and retrieval-based settings, multiple base LLMs, and three planning domains.

4 Experiments

  • The semantic parsing experiments use complex DSL benchmarks and 16–32 demonstrations, while the planning evaluation uses five in-context tasks and ten evaluation tasks per domain.The experiments are intended to assess improvements over standard prompting, not to surpass state-of-the-art benchmark algorithms.Source: §4.1 · p. 5, §4 · p. 5, §4.3 · p. 9

4.1 Semantic Parsing for Tool Usage

  • Grammar prompting improves few-shot semantic parsing over standard prompting and outperforms derivation-tree prompting, though predicted grammars still trail oracle grammars.Constrained decoding requires roughly three times more API calls than unconstrained decoding.Source: §4.1 · p. 6, Table 1 · p. 6
  • In retrieval-based semantic parsing, gains are less pronounced than in few-shot settings; grammar prompting also improves Template, TMCD, Length, and held-out NewFunc results over standard prompting.For GeoQuery and Overnight-Blk NewFunc tests, the full DSL grammar is prepended even though the functions are withheld from retrieval.Source: §4.1 · pp. 6–7, Table 2 · p. 6
  • Across most tested base-LLM settings, grammar prompting improves on standard prompting, with exceptions for SMCalFlow using GPT-3.5 and GeoQuery using PaLM 2-L.The comparison uses a 100-example subset rather than the full test set.Source: §4.1 · p. 7, Table 3 · p. 7

4.2 Class-Specific Molecule Generation

  • For class-specific molecule generation, the input is empty and specialized SMILES grammars encode class-specific structure, but SMILES does not guarantee valid molecules.The examples comprise 32 Acrylates, 11 Chain Extenders, and 11 Isocyanates.Source: §4.2 · p. 7
  • For molecule generation, grammar prompting improves Acrylates and Chain Extenders over standard prompting across all metrics, but results are mixed for Isocyanates.Both prompting methods exceed the graph grammar baseline on retrosynthesis score.Source: §4.2 · p. 8, Table 4 · p. 8

4.3 Action Subset Selection for Efficient PDDL Planning

  • In guided PDDL planning, the predicted grammar restricts the action space, its generated plan initializes GBFS, and search then finds a final plan within that restricted space.The evaluation uses Blocks, Depot, and Satellite tasks with primitive or macro actions, alongside standard prompting, full-action planning, and a domain-specific Min Macro baseline.Source: §4.3 · pp. 8–9, Figure 5 · p. 9
  • In PDDL planning, grammar prompting improves Blocks efficiency at 100% success, raises Depot success by 20% with macro actions, and cuts Satellite expanded nodes by 57% with primitive actions.The Satellite comparison is against the No LLM baseline; these experiments do not target state-of-the-art planning speed.Source: §4.3 · p. 9, Table 5 · p. 9

5 Discussion and Limitations

Grammar prompting has limits across tasks: it may not help DSLs likely encountered during pretraining, can increase API calls, and can reduce molecule diversity or hurt PDDL planning. The authors also point to metalanguage generation and specialized-grammar finetuning as directions for further work.

Limitations

  • Grammar prompting did not improve DSLs likely encountered frequently during pretraining, and its constraints could increase API calls or hurt performance beyond semantic parsing.In molecule generation, constraints sometimes lowered diversity; in PDDL planning, object-pruning constraints sometimes negatively affected performance.Source: §5 · p. 9

Future work

  • The authors suggest exploring whether finetuning moderately sized LLMs with specialized grammars can improve grammar-based DSL generation.This is presented as a possible direction for future work.Source: §5 · p. 10

Metalanguages and scientific applications

  • Grammar prompting demonstrates LLM capacity to understand and generate metalanguages, and manually adding natural-language comments to grammar rules slightly improved semantic-parsing results.The authors connect DSLs to scientific problems by noting that they can encode hypotheses, human prior knowledge, and scientific principles.Source: §5 · p. 10

6 Related Work

The related work situates grammar prompting among reasoning prompts, program generation, neural grammars, molecule generation, and planning. It distinguishes the approach through its use of formal grammars as an intermediate prompt representation and its reliance on LLM in-context learning.

Chain-of-thought prompting

  • Grammar prompting extends chain-of-thought work requesting explicit reasoning steps [51] [24] [86] [80] [14] [94], using formal grammars as its intermediate reasoning step; the authors know of no prior work doing so.Source: §6 · p. 10

LLMs for program generation and semantic parsing

  • The work extends LLM program-generation research to DSL programs, which the authors describe as intrinsically scarce.Related work includes LLM code generation, tool use, semantic parsing, and constrained decoding.Source: §6 · p. 10

Neural grammars

  • For semantic parsing, grammar prompting defines a quasi-synchronous grammar whose rules depend dynamically on the source sentence, with LLM in-context learning as the learning component.Unlike the cited neural grammar work, its conditional grammar does not explicitly align rules to source-sentence parts.Source: §6 · p. 10

Grammar-based molecule generation

  • For molecule generation, the approach integrates grammar into an LLM without additional training, aligning with work that combines generic SMILES grammars and neural networks.Other related work induces grammars from data.Source: §6 · p. 10

LLMs for planning

  • In PDDL planning, grammar prompting is presented as a strategy for augmenting classical planners with LLMs, against findings that LLMs underperform classical planners on very long action sequences.Related efforts include translating problems to PDDL, corrective re-prompting, and learning actions, skills, macro-actions, rules, and guidance strategies.Source: §6 · p. 10

7 Conclusion

The conclusion presents grammar prompting as a way to improve few-shot DSL generation with LLMs. Across semantic parsing, PDDL planning, and molecule generation, the experiments show improvements over standard prompting baselines and suggest potential applications where DSLs are intrinsic.

Conclusion

  • Across semantic parsing, PDDL planning, and SMILES molecule generation, grammar prompting can improve upon standard prompting baselines.The semantic-parsing tasks include SMCalFlow, GeoQuery, and Overnight.Source: §7 · p. 11
  • The authors identify potential for grammar prompting to assist LLM tool use, based on encouraging semantic-parsing results.Source: §7 · p. 11
  • Promising results in other domains suggest potential for applying LLMs where tasks intrinsically depend on DSLs.Source: §7 · p. 11

A.1 Semantic Parsing

The appendix reports semantic-parsing decoding costs and annotated-grammar results alongside split, hyperparameter, and candidate-scoring details. It describes reduced API calls when grammar and program constraints are combined, and small or absent gains from manually annotated rules.

Data splits

  • For GeoQuery, the experiments use standard and Template, TMCD, and Length splits, with 32 sampled training examples for the standard few-shot split.The NewFunc test split contains examples using eight designated functions; remaining examples form training data.Source: §A.1 · p. 18
  • SMCalFlow uses 16-shot and 128-shot cross-domain settings, and the authors report that adding in-domain retrieval examples did not enhance performance.They use the preprocessed LISPRESS format for comparison with prior work.Source: §A.1 · p. 18
  • Overnight-Blocks uses the standard retrieval split and a few-shot split sampled from 32 training examples.The appendix also points to tables listing experiment split statistics and molecule-generation hyperparameters.Source: §A.1 · p. 18, Table 8 · p. 19

Scoring Functions for Constrained Generation

  • When candidate continuations exceed 16, SentenceBERT first selects 16 plausible candidates; later Codex models lack the log-likelihood functionality used for candidate scoring.For PDDL planning, the authors use SentenceBERT to select the best candidate as a workaround.Source: §A.1 · pp. 18–19

Cost Efficiency

  • Combining grammar and program constraints meaningfully reduces Codex calls compared with standard prompting under constrained decoding.Standard prompting and grammar prompting with constraints each result in increased calls; the passage gives no exact call counts.Source: §A.1 · p. 19

Grammar Prompting with Annotated Rules

  • Annotated BNF rules yield marginal gains of 1.0% on SMCalFlow and 0.5% on Overnight-Blocks, with no observed enhancement on GeoQuery.The comments pair rules with natural-language phrases extracted from the query; the authors suggest this alignment may aid interpretation and further constrain generation.Source: §A.1 · p. 19

A.2 Molecule Generation

Molecule generation samples a specialized grammar from a prompt built from a random permutation of examples, then samples a molecule conditioned on that grammar. Constrained generation improves validity, but other metrics can decline.

A.2 Molecule Generation

  • Grammar prompting samples a specialized grammar from a prompt built using a random permutation of the given molecules, then samples a molecule conditioned on that grammar.The authors list hyperparameters for grammar sampling and molecule generation in Table 8.Source: §A.2 · p. 19
  • The illustrated grammar prompts add manually curated natural-language comments mapping phrases to BNF rules; the model predicts such comments at inference.These comments are included in few-shot prompts.Source: Figure 6 · p. 20
  • Standard prompting uses a two-stage procedure that directly samples a molecule from a prompt formed by a random permutation of the given molecules.Its sampling hyperparameters are the same as those for grammar prompting’s molecule-generation stage.Source: §A.2 · p. 20
  • Earley-based constrained generation improves validity, while metrics such as retrosynthesis score decrease significantly.The authors attribute the discrepancy possibly to text-focused LLMs’ limited exposure to SMILES and difficulty applying its BNF rules.Source: §A.2 · p. 20

A.3 PDDL Planning

For PDDL planning, the specialized grammar defines a constrained action space, but restricting the planner to its selected objects proved too restrictive outside Blocks, so the restriction was removed.

A.3 PDDL Planning

  • Restricting GBFS to objects selected by the specialized grammar proved beneficial only in the Blocks domain.The restriction was judged too restrictive in the other tested setting(s), so the authors removed it.Source: §A.3 · p. 20
  • The specialized PDDL grammar delineates a constrained action space containing necessary actions and their associated objects.Source: §A.3 · p. 20
  • After removing the object restriction, GBFS could use grammar-predicted actions with an unrestricted range of objects.Source: §A.3 · p. 20

B Prompts

The prompt examples cover three semantic-parsing datasets and PDDL action DSLs. Prompt contents vary: some include general grammars, while the long SMCalFlow grammar is omitted.

B Prompts

  • The prompt figures show grammar-based examples for SMCalFlow, GeoQuery, and Overnight, and action-DSL examples for PDDL planning.The figures use actual dataset examples; the Overnight figure omits some long rules to fit.Source: B Prompts · p. 21, Figure 7 · p. 22, Figure 8 · p. 23
  • The general SMCalFlow grammar, about 4k tokens, is omitted from its prompt; GeoQuery and Overnight include their general grammars in the instructions.Source: B Prompts · p. 21
  • The molecule-generation prompt includes the general SMILES grammar.Source: B Prompts · p. 21

Related papers

Loading 2305.19234v3…