Grammar Prompting for Domain-Specific Language Generation with  Large Language Models
Authors: Bailin Wang
Zi Wang
Xuezhi Wang
Yuan Cao
Rif A. Saurous
Yoon Kim
Venue: NeurIPS 2023 poster (2023)
Keywords: semantic parsing
large language models
PDDL
AI planning
molecule generation
data efficiency
grammar-based learning
TL;DR: We propose grammar prompting, a simple approach for improving the few-shot DSL generation with large language models.

Abstract: 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.

Grammar Prompting for Domain-Specific Language Generation with Large Language Models
Bailin Wang Zi Wang
Xuezhi Wang
Yuan Cao' Rif A. Saurous Yoon Kim 9
MMsssachusetts Institute of Technology (bailinw, yoonkim)@mit... tt edu, (wangzi, xuezhiw, yuancao, rif)@google.com
Google DeepMind Gooole Research
Abstract
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 (c.g., semantic parsing to complex domain- specific languages). it is challenging for the LLM to generalize from just few exemplars. We propose grammar prompting, a simple approach to enable LLMs use external knowledge and domain-specific constraints, expressed through a grammar in Backus-No Naur Form (BNF), during in-context learning. Grammar prompting augments each demonstration example with specialized grammar that is minimally sufficient for generating the particular output example, where the specialized grammar a subset of the full DSL grammar. For inference, the LLM first predicts BNF grammar given test input, and then generates the output according to the rules of the grammar. Experiments demonstrate that grammar prompting can enable LLMs perform competitively generation tasks, including semantic parsing (SMCalFlow. Overnight, GeoQuery), PDDL planning, and SMILES-basn -bseed molecule generation.
diverse set of DSL
Introduction
Prompting large language models (LLMs) with demonstrations optionally combined with natural language instructions has been shown be effective approach for surfacing their myriad capabili- ties acquired through pretraining [10]. This approach is however inadequate for applications where the task specifications cannot be fully delineated through just a handful of exemplars, for example in semantic parsing where an LLM must translate a natural language utterance to an executable program in a domain-specific language (DSL). DSLs often incorporate commain-specite abstractions and semantics that are difficult to characterize via just a few demonstrations. And unlike general- purpose programming languages, DSLs are by definition specialized and thus unlikely have been encountered often enough (or at all) during pretraining for the LLM to acquire its full syntax.
How draw the few-shot learning capabilities of LLMs to generate structured strings that substantially different from those seen during pretraining? This work explores grammar prompling simple approach for data-efficient generation of structured languages where output string in the language can be derived through a series of symbolic manipulations. We exploit the fact that constraints over a structured output space can often be succinetly described by a context-free free grammar in Backus-Naur Form (BNF), which is commonly used to define the syntax of language. Grammar prompting augments each in-context example (æ, y) with a specialized BNF grammar Gly] that is minimally sufficient for generating y. Given new input, the LLM first predicts the specialized BNF grammar and then generates the answer conditioned on the grammar.
Grammar prompting follows the recent line of work which enhances the few-shot reasoning capa- bilities of L.MS by interleaving intermediate "reasoning" steps between each in-context input and
Code and data available at: https://githu/: http://ggthho...coomeeoaaaaarrrr
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

output [51, 24, 86, 80, 73]. The key difference in our approach is that the intermediate variable in the form of formal grammar rather than natural language, which focuses on eliciting the symbolic manipulation capabilities of L.LMs. 'hee use of a formal grammar moreover makes it possible to impose constraints during incremental decoding such that syntactic validity guaranteed. Finally, unlike chain-of- -it-ooof-oogg--ttyllllo prompts [86] which typically require manual verbalization of the intermediate reasoning steps, in our approach the specialized grammar G[y] can be derived automatically by parsing the output y with the full (unspecialized) DSL grammar.
To summarize,
We propose grammar prompting as a simple approach for enabling LLMs to generate highly structured languages from just a few exemplars.
We design a constrained LLM decoding algorithm tailored to grammar prompting, which guaran- tees syntactic validity while minimizing the number of L.LM API calls.
We apply grammar prompting to various domain specific languages for semantic parsing (SM- CalFlow, Overnight, GeoQuery), Al planning (PDDL), and molecule generation (SMILES), and find that it can meaningfully improve upon standard prompting baselines in the few-shot setting.
2
Background
In this section, we define our problem and review the few-shot learning method that we build on.
2.1 Problem Formulation: Dumain-Specifie Language Generation
Let E' be the set of all finite strings over an alphabet Σ, and further let D S E" be a domain-specific language (DSL) for an application of interest. Given input æ (e.g., natural language command) we are interested in generating y E D (e.g., program in a DSL fulfilling the command), as shown by the following calendar assistant example from SMCalFlow [6]:
x: Add meeting with Jean's manager on Wednesday at 3PM.
y: CreateEvent (start_" ? WedueesdayMuubberP((3)) (attendee__d Xaaorr/raaaaaaoooooae/aaaaaaaaaa (FnddManager(Ieann))
DSLs are crafted by experts who use their domain-specific knowledge to incorporate higher-level abstractions than are typically found in general-purpose programming lan- guages. We assume access to an expert- defined grammar G that fully specifies the DSL's syntax. As is the case with many DSLs, we further assume that G is a context-free grammar in Backus-Naur Form (BNF). See Figure for simple ex- ample adapted from SMCalFlow [6]. Let- ting L(G) be the language generated by G, we have D _ L(G) ç Σd (not all syntacti- cally valid programs are semantically valid).
event
"CreateEvent(" constraint """
"QueryEvent(" constraint ")"
constraint
"(8" constraint constraint ")" "(start_?" date time? ")" " "(attendee_?" attendee* ")"
date
"Wednesday" "Monday"
number
("0"... "9")+
time
(MMmmbeAAM" number ")"
"NumberPM(" number ")"
attendee
"Bob" "Carol" "Jean" "FindManager"
Figure 1: A simple BNF grammar for a calendar DSL.
2.2 Few-shot Learning with Large Language Models
In-context learning with large language models (LLMs)) has been shown to be effective approach for few-shot learning [10]. Under this approach, a pretrained LLM conditioned on N demonstration examples (z()), y ( y followed by test example æ, and the output is given by decoding from the prompted LLM, i.c., PL æx (z) y ( The demonstration examples can be optionally preceded by natural language instructions to further improve performance or even enable zero- shot learning [85, 62). Recent work has additionally shown that interleaving natural language verbalizations of intermediate reasoning steps between each (i) and ( can greatly improve few-shot performance on complex reasoning tasks [51, 86, 80, 73, 16).
The effectiveness of few-shot in-context learning depends both how useful the implicit knowledge acquired through pretraining is for the task, and on how effectively the task specifications can be conveyed through the demonstrations. For DSL, the structured nature of combinatorial output space (i.e., the DSL. grammar G) cannot be adequately captured through just a handful of demonstrations. Thus, few-shot generation of strings of DSL remains challenging for LLMss.

---

LLM Prompt
You are an expert programimer, and you need to write a program for the given natural language query. First, you should write grammar that contains all the necessary BNF rules. Then, you should write programs that conform to your predicted rules.
(optional) G: [BEGIN RULES]
[END RULES]
a find the meeting on Wednesday with Bob and Carol
event constraint
"QueryEvent(" constraint ")"
(&" constraint constraint ")"
"(start_? date ")"
"attendee_?" attendee attendee ")" "Wednesday"
date
attendee
"Bob" "Carol"
QueryEvent(& (start Wwdneeday ( Bob Carol))
a: Add meeting with Jean's manager on Wednesday at 3PM
LLM Output
G:
event
"CreateEvent(" constraint ")"
constraint
(&" constraint constraint ")" "(start_?" date time ")"
"(attendee_"" attendee ")"
date
"Wednesday"
time attendee
"NumberPM(3)"
"FindManager(" attendee ")" "Jean"
T. CreateEvent(&& (start_? Wednesday NimberrK(3)) [iunor/rPPPiottttmeeeeeeee/aaeaa FindManager(Jean)))
Figure Example of grammar prompting for a calendar DSL. interleave the minimal specialized grammar " between the demonstrations (*) and " During decoding, the LLM first predicts the specialized grammar G, and then predicts the program ÿ conditioned on G. The blue portion is not part of the actual prompt and only shown for illustrative purposes.
3 Grammar Prompting
Grammar prompting exploits the fact that while the actual strings of a DSL may not have been encountered frequently enough (or at all) during pretraining for the LLM to implicitly acquire its syntax, the LLM will likely have encountered many instances of metalanguages (languages used to describe other languages). BNF grammars are standard metalanguage for specifying a language's 's syntax, and expected occur in the LLM training corpus with some frequency (e.g., in computer science textbooks). We thus focus on using BNF grammars for few-shot DSL generation.
Let G - (ry} be an extended BNF grammar where each rule ry is of the form
<symbol>
<exprı>
<expr>>
Here <symbol> is nonterminal symbol and each <expr,> > is sequence of nonterminal and terminal symbols.' A straightforward approach for incorporating a BNF grammar during in-context learning simply prepend the string representation of the full grammar G to the demonstration examples, along with an instruction to use the grammar. However in preliminary experiments, we found that this did not yield any improvements.
3.1 Specialized Grammars
We propose use specialized grammars to enable better use of domain-specifis knowledge and constraints. A specialized grammar G' C G is grammar obtained from taking subset of the rules of the full grammar G. We further define Gly)), minimal specialized grammar of y. be BNF
For brevity we forgo the formal suple-based definition of G' and instead define G' to be equivalent to its context-free rules. We also freely go back and forth between this set definition of G and its string representation. "However, when combined with specialized grammars we did observe small improvements by appending the full DSL grammar to the instructions. Hence, for all experiments where G is small enough (GeoQuery, Ovemight-B B. SMILES), we include G as part of the instruction. See Figure 2.

---

grammar with the following properties: (1) E L(G[y)), and (2) Vr E Glyl, & L(G(y) (r)).) We can readily obtain a minimal specialized grammar by using to parse y and then taking the union of rules that were used in the derivation of y.
Grammar prompting feeds sequence of (ax(*, Gl y ( along with prompt to L.M.M For inference we first obtain the specialized grammar with an (approximate) arg max decoding
G arg max PL ar, (ax() Gly (0) G'GG
We then obtain the program conditioned on G
arg max PL (x, 1, MEL(G)
We discuss how to perform constrained decoding with & S G and y E L(G) in the next section. Grammar prompting views DSL program generation as grammar specialization process where given a natural language specification æ, a set of production rules, G, is selected from G, and then a program ÿ is deduced according to the selected rules. Grammar prompting can also be viewed as an instance of tf-ttuggttt prompting [51, 86] where the intermediate thought is in the form of a formal grammar. However, unlike typical -hthouhf prompting where the answer is (usually) deterministic given the intermediate reasoning steps, in our case there is still some uncertainty with respect to ÿ given G (e.g., L(G) could still be infinite).
3.2
Constrained Decoding
Algorithm 1 Earley-based Constrained Generation
The use of formal grammar as an inter- mediate variable makes it possible to force grammatical constraints during au- toregressive LLM decoding. We first dis- cuss how we enforce the constraint y E L(G). One approach to constrained de- coding is to use G to obtain a left-to-right Earley parser [18] and only decode from valid continuations each decoding step. However this simple strategy poses several practical challenges when working with API-only LLMs. For one, a valid terminal
Input: Test input æ, predicted grammar G Output: Program ý E L(G)
1: < e
>> initialize to empty string
2: while True do
3:
ÿ f decode (RIM(-) x G. ...)...))
4:
ÿ ÿ y
concatenation
5:
if ý E L(G) then
D try parsing with G b return if successful
6:
return ú
7:
else
if parsing fails, need correct G)
8:
Yprefix:
Ely
continuation in G may consist of multiple BPE tokens. Moreover, while we can sam- plc a valid continuation at each time step by disallowing invalid tokens,* since the set of valid continuations changes at each time step, this strategy would require calling the LLM API at each time step with the full prompt and prefix along with the disallowed continuations, which is prohitively expensive."
9:
w f-
arg max PLM yprefix....)
10:
ÿ Ypreeix 20"
I1:
end if
12: end while
13: return ý
While there are many methods for grammar-conssrained LM decoding [68, 64, 26], we present a simple strategy which speculatively decodes from the LLM to look ahead for multiple tokens. The pseudocode is shown in Algorithm 1. At each prediction step, we ask the LLM to speculatively decode the full program conditioned on the current prefix (lines 4-5). If the resulting continuation leads to valid program, we return it (lines 6-7). Otherwise, we consult an Earley parser to extract the longest valid prefix from the current prediction (yprelix), along with set of valid terminals that can
'Note that y may have more than one minimal specialized grammar due the potential instantiation of extended BNF rules. For instance, the expression "(attendee_?" attendee+ ")" depicted in Figure I implicitly defines all occurrences of tenenee greater than this expression is incorporated into a program, either the concrete rule "(attendee_2 specialized grammar. In most applications we consider the rules of the minimal specialized grammar will be concrete, and thus there will only be one parse associated with y. See appendix A. for further details.
attendee ">" or the original rule could be included in the minimal
4 'For example by using the logit_biar argument from OpenAl's LLM API.
'These costs might be mitigated in the future if LLM APIs allow for cheaper use of cached prompts.

---

Earley-based Constrained Decoding
7( CreateEvent(&& (start_? Wednesday VumberPM(3))atttendee, Jean's 's Manager))
Extract the longest valid prefix, and possible fixes (i.e., next terminals) baxed Earley parsing:
Mpeetx QueryEvent(& (start_? Vednesdayy/atttendes
Elyyeens:: (Jean, FindManager()
Find the best candidate and concatenate it with the prefix:
y(o) + QueryEvent(&K (start_? ? Weddnedday FindManager(
Figure 3: Illustration of how an predicted program is corrected in our proposed Earley- based constrained decoding. The final partial program will be subsequently fed into the LLM for continuation.
follow the prefix (E(gprex)). Finally, we rely on the LLM's probabilities to decide which terminal to use, with which new partial program can be constructed (lines 10-11). Figure 3 illustrates one prediction step where the predicted program corrected into a new valid partial program. Note that ur can consist of multiple BPE tokens, e.g., "FindManager (" in Figure 3. By scoring over multi-token terminals, the search procedure implicitly augmented by looking ahead for a few tokens.
We use a similar procedure to operationalize the constraint G' C G. except that Earley Parse (used at Algorithm line 9) is constructed with melagrammar (i.e., the grammar of G) for grammar prediction. See appendix A.1 for more details. In our ablation study we find that while these constraints are helpful insofar they guarantee syntactic validity, grammar prompting still meaningfully improves upon standard prompting with even with simple unconstrained decoding.
4 Experiments
We apply grammar prompting to diverse domains: DSL.s for semantic parsing (SMCalFlow, Overnight, GeoQuery), action DSL (PDDL planning). and molecule generation DSL (SMILES). These experiments are not necessarily intended to improve upon the state-of-the-an on these benchmarks but rather intended to assess whether LLMs can improve upon standard prompting for few-shot DSL generation by learning to predict and use grammars during in-context learning.
4.1 Semantic Parsing for Tool Usage
Software tools are typically accompanied by collection of human-interpretable APIs which provide platform for developers to interact programmatically with the tools. These APIs constitute DSL, where each production rule of the grammar specifies the input and output types for specific API call (see Figure 1 for an example). These tools demonstrate broad spectrum in terms of DSL com- plexity, ranging from single-function tools such as Google wuuser_qurry Translate (sentence, language) to more complex tools such as the entirety of Wolfram language. 7 Enabling LLMS to use external tools via APIs is an important step towards enhancing their capabilities [63, 56, 53, 72, 47].
We test our approach on standard semantic parsing benchmarks involving complex DSLs: SM- CalFlow [6], which features human-generated utterances about calendar management (see Figure 2); GeoQuery [99] which features queries against US Geography database; and Overnight-Blocke [81], 1. which features queries about blocks in a synthetic block world. See appendix for examples of input-output pairs along with the specialized grammars. The original benchmarks target the train- ing of conventional semantic parsers and thus contain hundreds/thousandd of training examples. Even prompting-baid based approaches on these benchmark rely on retrieval-based in-context learning which first retrieves exemplars from large training set of examples (n >> m) based on some similarity measure (e.g., BM-25), and then performs in-context learning with the retrieved exem- plars [57, 95, 68, 46]. In contrast, we target the true few-shot setting where we only assume access to 16-32 demonstration examples.
Our baselines here include: (1) standard prompting, (2) standard prompting with constrained decoding based the full DSL grammar G [68, 64], and (3) derivation tree-based prompting baseline which imbues more structural information to the exemplars by feeding the lincarized derivation
'In rare cases the set Σ [[Mpee was too large to feed to LLM APIs. In these cases we used Sentence- BERT [59] to compute the similarity between the encoding of yprettx w and (t)) and took the top 16 candidates as 2 [pens)] 'tttps: //www. wolfram. com/language/
5

---

GeoQuery
SMCalFlow Prog.
Overnight-Blk
Approach
Prog.
Exec.
Prog.
Exce.
Standard Prompting (unconstrained decoding)
60.7
81.5
46.4
29.3
54.7
w. constrained decoding (Ū L(G))
61.1
81.8
49.2
29.3
54.7
Linearized Derivation Tree Prompting
58.6
77.5
50.0
27.3
56.4
Grammar Prompting (unconstrained decoding)
67.1
87.3
50.8
34.8
57.4
grammar constraint (G G)
67.9
88.6
51.3
37.1
60.4
w. grammar and program constraint (Ú L(G))
69.6
88.9
52,4
37.6
60.9
w. oracle grammar (G = G
95.7
96.1
80.0
73.9
94.2
w. oracle grammar program constrain!
95.7
96.8
83.6
74.4
96.5
Table 1: Results few-shot semantic parsing with Codex with various decoding strategies. GeoQuery and Overnight- use 32 in-context examples, and SMCalFlow uses 16 examples. We show both program (Prog.) and execution (Exec.) accuracy when possible.
Retrieval-based ICL
GeoQuery Dut-of-Distribution
Model
GeoQuery SMCalFlow Ovemight-Blk
Template
TMCD
Length NewFunc
esamples retriesal set)
(32/560)
(161128)
(32/1
(32/41)
(22440)
(32443)
Previous Work
86.
60.7
65.2
Standard Prompting
96.8
60.0
69.4
93.2
77.1
86.4
63.3
Grammar Prompting
97.9
62.8
70.2
95.7
86.6
88.6
90.8
W. oracle grammar 98.6
88.9
97.2
97.9
95.0
95.7
96.2
Table 2: Results on retrieval-based in-context learning (left) and compositional generalization (right) with Codex. GeoQuery and OverighttBlk show execution accuracy while SMCalFlow shows program accuracy. The numbers with and taken from Herzig and Berant [31], Ye al. [95] and Cao al. [1]], respectively.
tree instead of the surface form program. We use -ovex-davinci-002 [13] as the base LLM for these main experiments. Language models trained on code (such as Codex) have shown to be particularly effective on semantic parsing benchmarks [67]. We evaluate according to program accuracy (matching the predicted and reference programs) as well execution accuracy (same execution in both programs) if possible.
Few-shot results. The main results are shown in Table 1. We find that grammar prompting can meaningfully improve upon the standard prompting baseline even without constrained decoding, Interestingly, grammar prompting outperforms derivation tree prompting which actually provides more information than the minimal specialized grammar Gly] (since the derivation tree explicitly shows how the rules are actually applied obtain the program). This potentially indicates that
having the LLM "plan out" the program by forcing it to predict the specialized grammar G first an effective strategy. We also analyze the effect of constrained decoding the number of LLM API calls in Table 7 of appendix A.I, where we observe that constrained decoding requires roughly three times more API calls than unconstrained decoding. However, despite the promising performance of grammar prompting, there is a large gap between using the predicted grammar versus using the oracle grammar (i.e., setting G = Gly)), indicating opportunities for further work in this area.
Retrieval- based in-context learning. While our core target application is few-shot semantic parsing, we also apply grammar prompting for retrieval-based in-context learning to test whether it can still improve performance in the data-rich regime and also compare against prior work these benchmarks. Results in Table 2 (left) show that grammar prompting can improve results even in this setting, although the improvements are less pronounced than in the few-shot setting.
-istrribbtnn generalization. We experiment to see whether grammar prompting can im- prove compositional generalization on GeoQuery. Specifically, test grammar prompting the compositional splits of GeoQuery split from Shaw et al. [66]. These splits feature structural divergence between training and test examples, e.g., programs have different templates length. Results in Table 2 (right) shows that grammar prompting can improve upon standard prompting, across all splits (Template, TMCD, Length).
*For example, the derivation tree of a subprogram (attendee_? FindManager (Jean)) is linearized to [constraint "(attendee_r" _ [attendee "F "FindManager(" [attendee "Jean" "}"] "]"]. which uses square brackets to encode richer hierarchical information than just the surface form program.

---

We next assess whether grammar prompting can enable LLMs to make zero-shot use of un- seen functions (NewFune) that are not even part of the retrieval set. We set aside 8 func- tions (smallest, shortest, most, highest, sum, population_1, count, major) and re- move them from the retrieval set, simulating a scenario where new functions are supported in the backend yet no NL-program paired data is available for adapting semantic parser. Note that for GeoQuery (and Overnight-Bie BBkkg, we always prepend the full DSL grammar G-which includes the in-context exemplars. Table 2 (right-most column) shows that
the held-out functions- heamaar-prompter LLMs achieve significantly better performance than standard prompting. Our results suggest that the explicit prediction of specialized grammars elicits understanding and rea- soning at the grammar level, thereby enabling generalization to unseen functions. We also found that without constrained generation, LLMs were often able to guess functions that did not exist but were nonetheless sensible. An interesting direction is to explore whether L.LMs can tackle DSI -open benchmarks such as LARC [1].
Different base LLMs. We finally ex- periment with grammar prompting across different base LLMs. Since GPT- 3.5's 4K token limit is smaller than Codex's (8K) and GPT-4's (8K) limits, we use fewer exemplars in these exper- iments than before (24/8/16 exemplars for Geoouerr/SMCaalloooOoveee
Base
Method
GeoQuery
SMCalFlow Overnight-
Codex
Stundard
83
27
63
Grammar
95
35
GPT-3.5
Stundard
75
9
49
Grammar
86
5
67
GPT-4
Standard
85
32
56
Grammar
98
36
62
re- spectively). Due to API cost, we limit our experiments to a smaller subset of 100 test examples instead of the full test set.
PaLM 2-L
Standard
90
14
59
Grammar
87
17
62
Table 3: Results with different base LLMs on a subset of 100 examples sampled from the original test set. GeoQuery and Overnight-Blk show execution accuracy, while SMCalFlow shows program accuracy.
Table 3 shows that grammar prompting im- proves upon standard prompting in the ma- jority of the settings. The exceptions are SMCalFlow with GPT-3.5 where both methods performed poorly, and GeoQuery with PaLM 2-L(7], where standard prompting already performed well.
4.2 Class-Specific Molecule Generation
We next demonstrate an application of grammar prompting beyond language parsing problems with molecule generation task. Existing methods for molecule generation typically focus training specialized neural models using large training sets [45, 37, 15, 2. 79, 61, 19]. We instead follow Guo et al. [29] and explore a few-shot setting where the task is to generate class-specife molecules given a small number of exemplars of that class. Formally, given a small set of molecules {uē ( j belonging to a particular molecule class c E (Acrylates, Chain Extenders, Isocyanates] J. our goal is to generate novel molecules Ye of the same class that can be synthesized using existing molecules. Since the in-context examples in this case will only consist of molecules of the same class, the "input" (.(") is the empty string in this case. The data contains 32 Acrylates, Chain Extenders, and 11 Isccyanates (see appendix G of Guo et al. [29]).
While molecules can be more faithfully represented with 3D graph structure, the SMILES string representation [87] remains popular due to its ease of use." The specialized grammars G[ye] (which are specialized from the SMILES grammar) encode various structural properties of the molecule that are specific to the molecule class. Figure 4 shows an example of a specialized grammar and the corresponding molecule in SMILES format. In this example, ring_closure :: "1" specifies the number of rings, and branch : "(" smiles ">" specifies whether there is branch.
We test our approach by generating 100 molecules for each class and assessing the quality of the generated molecules. In addition to the standard prompting baseline, we also run the graph grammar baseline from Guo et al. [29] which learns hypergraph grammar [38] from the given molecules. We use four metrics: Vulidity (V), the percentage of chemically valid molecules; Diversity (D), average pairwise Tanimoto distance over Morgan fingerprints [60]; Retrosynthesis score (R), the percentage
fingerpring
"Note that SMILES does not guarantee that a generated string corresponds to valid molecule. Using our approach on more advanced string representations such as SELFIES [44] (which guarantee validity) remains an interesting avenue for future work.
7

---

Specialized SMILES Grammar for Molecule Generation
C'yl:
smiles atom
atoom chain branch chain chain atom chain organic_syymb
organic_symmol chain
"C" "N" "0"
atom ringuclosuuee bond atom bond atom bond atom ring_closure atom
aoom bond atom bond atom
bond atom bond atom
ring_closure bond branch
"1"
"="
"(" smiles ")"
y: CC c= DjOCCoC1 = CC CC
C1
Figure 4: Example of a specialized grammar for generating a molecule from the Acrylates class.
Acrylates
Chain Extenders
Isocyanates
Model
V
D
R
M
D
R
M
D
R
Graph Grammar [29]
100 0.83 79.0
30.3
100
0,86
72.7
98.3
100
0.93 52.2 82.7
Standard Prompting
87.7
0.73
80.0
76.7
60.3
0.89
72.7
55.7
94.7
0.82
78.0
92.2
Grammar Prompting
98.0
0.74
91.0 93.3
96.3
0.90
86.7
94.0
97.7
0.79
78.0 96.3
Table 4: Results few-shot molecule generation GPT-3.5. The metrics are validity (V), diversity (D),
retrosynthesis score (R) and membership (M). Higher is better for all metrics.
of molecules that are synthesizable from existing molecules, which is computed approximately via the Retro model [12]; Membership (M), the percentage of molecules that belong the desired monomer class. We use GPT-3.5 as the base LLM and sample from the LLM without constrained decoding, as constrained decoding found to decrease the diversity of samples. See appendix A.2 for the full experimental setup.
Results. Table 4 shows that, compared with standard prompting, grammar prompting significantly improves the synthesis of Acrylates and Chain Extenders across all metrics, while yielding mixed results for Isocyanates. Notably, both prompting- based methods outperform the graph grammar baseline in terms of Retro score, possibly due to that LLMs may have been pre-trained on existing datasets of molecules, enabling them to effectively generate synthesizable molecules. In contrast, the baseline method cannot incorporate any external knowledge beyond the 11 or 32 molecules provided, Our preliminary results indicate that LLMs can serve as useful tool for generating string representations of chemical structures (and potentially other biological/chemical structures).
4.3 Action Subset Selection for Efficient PDDL Planning
Our final experiments show how grammar prompting can improve the efficiency of classical AI planners. Classical planning is the problem of finding a sequence of actions (i.e., plan) that goes from an initial state $u to goal state sg. An action is represented by ground operator (e.g.. unstack block1, block2) which consists of an operator unstack along with two object arguments). We additionally consider macro-operte operators which can potentially speed up planning [9]. Planning tasks, along with actions, are represented in Planning Domain Definition Language (PDDL) [27]. We explore how grammar prompted L.MMs can help guide classical planning algorithms.
We design specialized grammars to provide guidance to the classical greedy best-first search (GBFS) algorithm [5] by selecting set of relevant actions. Figure 5 illustrates an example of such specialized grammar, which captures all the necessary actions for the final plan y that solves the given task. The process of the guided planning consists of the following steps: (1) given a task, predict specialized grammar Gly); ; (2) use the specialized grammar G [y] subsequently generate a plan within the restricted action space derived from Gly]; ; (3) initialize GBFS's 's priority queue with the LLM-ggnnrated plan, and (4) search for the final plan the restricted action space. Our setup builds upon the idea of using an simpler two-step process: (1) given a task, predict a plan via standard prompting. and (2) utilize this plan to guide GBFS. We use their method as our baseline.
plan to initialize GBFS from Silver et al. [69], which has
Following Silver et al. [69], we create similar few-shot setting for LLM planning, using 5 tasks as in-context examples and 10 tasks for evaluation from Pyperplan [5]. We test our approach on classic
For example, sickup-and-stacke B) is combination of pickup(A) and stack(A, B).

---

Specialized Action Grammar for PDDL Planning
B
B
A
C
D
A
D
so:
G[y]]:
plan
ground_operre operator+
ground_operator
"pick_up -nd---u--nnd--taaaaddd block block ")"
"unstack-and-put_doa block block ")"
block
"A" "B" "C"
y: unstack-and-put_ A); pick__u-and-stactee A); pick_up-and-stackke C)
Figure 5: Example specialized grammar for PDDL planning the Blocks domain, Given an input
a (So sg). the specialized grammar G[y) only includes necessary actions for solving this task.
Blocks Expanded
Depot Expanded
Satellite Expanded Success
Approach
Created
Success
Created
Success
Created
GBFS Prim. (No LLM)
360
188
1.0
18047
3870
0.4
8205
150
1.0
Standard Prim.
348
180
17597
4039
0.4
6686
Grammar Prim.
251
124
15033
3641
0.4
5162
Standard Macro.
850
1460
0.4
4003
Grammar Macro.
170
2917
127
3665
Standard Min Macro.
228
1.0
1903
0.6
3483
0.8
Table 5: Results PDDL planning. Created/Expanded refer to the number of nodes during planning (lower better). Success refers to success rate (higher better). Numbers are averaged over three runs using GPT-3.5.
domains in PDDL planning, including Blocks, Depot and Satellite. For the action space, we use either a set of primitive actions (Prim) or augmented set with macro actions (Macro). In addition to standard prompting, we add two more baselines: (1) No LLM: planning with the entire set of actions; (2) Min Macro: where construct minimal set of macro actions for each domain by selecting actions from existing plans for the training tasks. The Min Macro baseline is a domain-speciin method to reduce the action space. By comparing to Min Macro, we can verify the effectiveness of instance-specific v.s. domain-specific action selection. See appendix A.3 for more details.
Results. We evaluate the efficiency of planning in terms the number of search nodes created/- expanded, as well as the success rate. Table 5 shows the promising performance of L.I L.LM-guded planning via grammar prompting. while maintaining 100% success rate. In Depot, grammar prompting with macro actions improves the success rate by 20% over the best competing baseline. In Satellite, using primitive actions yields the best performance with 100% success rate and reduction of 57% expanded nodes comparing to the No LLM baseline. While our experiments are not intended to complete with the ttate-of-the-ar algorithms for fast planning [20-22, 20--22,55 32, 25, 84], they indicate the promise of LLMs for improving existing planning algorithms.
Blocks, grammar prompting significantly improves efficiency
5 Discussion and Limitations
We discuss several limitations of our approach including some negative results. Grammar prompting did not yield any improvements for DSLs that were likely to have been frequently encountered during pretraining (e.g., regular expressions, SQL). Moreover, constrained generation based on specialized grammars led to increased API calls, and was not always beneficial for tasks beyond semantic parsing. For instance, in molecule generation we discovered that enforcing constraints can sometimes result in lower diversity, Additionally, in PDDL planning we observed that the constraints applied to prune objects can sometimes negatively impact performance, suggesting that relevant object selection is still very challenging for LLMs. It may be interesting to explore whether finetuning of moderately LLMs using specialized grammars can lead better grammar-bars based models for DSL generation.
On the positive front, our work demonstrates that LLMs have capacity to understand and generate metalanguages. Working in this "metalanguage space" can be combined with chain-of- offthooghtt-tyle (86) prompts by, for example, manually providing natural language comments to the rules of the specialized grammars. We found this to improve results slightly on semantic parsing (see Figure

---

of appendix A.1). Moreover, many scientific problems can be formally approached by representing hypotheses as DSL programs [71], and DSLs can enable casier encoding of human prior knowledge and scientific principles, providing a foundation for scientific discovery. Recent work shows that state-of-the-ar I.LMs can follow previously unseen formal systems [75]. Techniques like grammar prompting can widen the scope of scientific problems for which LLMs could be effectively applied by more explicitly accounting for external knowledge and constraints.
Related Work
Chain-of-thought prompting, Grammar prompting extends a recent line of work on improving reasoning capabilities by requesting explicit reasoning steps as part of the prompt [51, 24, 86, 80, 14, 94]. Our approach is closely related to concurrent work on employing symbolic variables as part of the prompt [30, 50, 33, 97, 52], though we are not aware of any existing work that uses formal grammars as the intermediate reasoning step.
LLMs for program generation and semantic parsing. Generating programs from natural lan- guage specificationss a task often referred to as semantic parsing, is a sub-problem of program synthesis; for surveys, see Kamath and Das [39] and Gulwani et al. [28]. Recent works [8, 89] have explored using L.LMs for generating code in general- purposse programming languages (e.g.. Python). Our work further extends this line by examining whether L.LMs can generate DSL, programs, which are intrinsically scarce. There has also been work on using L.LSs for tool usage via further training [63] or prompting [56, 77], investigating how model scales [57] and retrievers [96, 46] affect in-context learning for semantic parsing, and constrained decoding [64, 68, 55] for program generation.
Neural grammars. Grammar prompting can also been seen as a "fully LLM" instantiation of line of work on neural parameterizations symbolie grammars [35, 17, 43, 42, 36, 100, 92, 91, 93]. Indeed, our approach to semantic parsing essentially uses prompt-based learning to define quasi- synchronous grammar [70, 78] whose rules dynamically depend on the source sentence. Concretely, in contrast to recent works which embed learnable neural components within synchronous grammars [41, 23, 76], grammar prompting relies on the implicit in-context learning capabilities of LLMs for the learning component. (However unlike these works, our conditional grammar does not explicitly align its rules to the subparts of the source sentence).
Grammar-based molecule generation. Grammar-based methods have gained significant interest in the realm of molecule generation, offering advantages in interpretability, data-efficiency, and controllability. One line of research involves integrating generic SMILES grammars with neural networks to generate syntactically correct molecules [45, 15]. Another approach centers on data- driven induction of grammars for generation [29, 38). Our work aligns with the former, viewing grammar prompting as a straightforward method for integrating grammar into an LLM without the need for additional training.
LLMs for planning. Recently, LLMs have been increasingly studied the context of planning for autonomous agents. When given goals expressed in natural language in household environments, earlier works [3, 65, 34, 48] directly prompted LLMs to predict exccutable actions. However, in PDDL domains, recent works [69, 74] showed that LLMs underperform classical planners if the desired action sequences are very long. Grammar prompting represents a promising strategy for augmenting classical planners with I.LMs get the best of both worlds. Other related efforts include translating between problems and PDDL models [49] and corrective re-prompting [58]. Besides using LLMs, integrating learning and planning has been extensively studied in the past literature, e.g., learning actions [4, 82], skills [84], macro-actions [9], rules [88] and guidance strategies [90, 83, 40] for more efficient planning.
7 Conclusion
We propose grammar prompting as a simple approach for improving few-shot DSL generation with large language models. Experiments across range of structured languages including DSLs for semantic parsing (SMCalFlow, GeoQuery, Overnight), PDDL planning (action DSL), and molecule generation (SMILES). show that grammar prompting can improve upon standard prompting baselines. The encouraging results in semantic parsing indicate its potential to assist LLMs with tool usage, and the promising results in other domains indicate that grammar prompting can enable application of LLMs in domains that intrinsically depend on DSLs.
10

---

Acknowledgments
We thank Jacob Andreas, Gabriel Grand, Linlu Qiu, Tom Silver, and Hunter Lang for helpful discus- sion and feedback. This study was supported by funds from the Google-MIT research collaborations program and the GIST-MIT joint research program.
References
[1] Sam Acquaviva, Yewen Pu, Marta Kryven, Theodoros Sechopoulos, Catherine Wong, Gabrielle Bcanow, Maxwell Nye. Michael Tessler, and Josh Tenenbaum. Communicating natural programs to humans and machines. Proceedings of NeurlPS, 35:3731-3743, 2022.
[2] Walid Ahmad, Elana Simon, Seyone Chithrananda, Gabriel Grand, and Bharath Ramsundar. Chemberta-2: Towards chemical foundation models. arXiv preprint arXiv:2209.01772,, 2022.
[3] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, et al. Do as I can, not as I say: Grounding language in robotic affordances. arXiv preprint 2rX1v:2204.01691,, 2022.
[4] Diego Aineto, Sergio Jiménez, and Eva Onaindia. Learning STRIPS action models with classical planning. In Proceedings the International Conference on Automated Planning and Scheduling, volume 28, pages 399-407, 2018.
[5] Yusra Alkhazraji, Matthias Frorath, Markus Grüttnnr, Malte Helmert, Thomas Liebetraut, Robert Mattmüller, Manuela Ortlieb, Jendrik Seipp, Tobias Springenberg, Philip Stahl, and Jan Wülfing. Pyperplan (v1.3), 2020. URL https:///ol: 100 5281/zenoda 3701337009 399.
[6] Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christopher H. Lin, llya Lintsbakh, Andy McGovem, Alcksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, Andrei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. Task-oriented dialogue as dataflow synthesis. Transactions of the Association for Computational Linguistics, 8:556-571, 2020. doi: 10. a 00333. URL https: //aclanthology, org/2020/ tacl-1.
[7] Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. PaLM 2 technical report. arXiv preprint arXiv:230S. 10403, 2023.
[8] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry. Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.077.. 107.0733, 2021.
[9] Adi Botea, Markus Enzenberger, Martin Müller, and Jonathan Schaeffer. Macro-ff: Improving Al planning with automatically learned macro-operators. Journal of Artificial Intelligence Research, 14:581-621. 2005.
[10] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Proceedings of NeurIPS, 2020.
[11] Ruisheng Cao, Zhu, Chen Liu, Jieyu Li, and Kai Yu. Semantic parsing with dual learning. In Proceedings of ACL, pages 51-64, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v//P19 1007. URL
wwt.oorggg////.... [12] Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro Learning retrosynthetic planning with neural guided search. In Proceedings of ICML., pages 1608-1616. PMIR, 2020.
11

---

[13] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray. Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philiippe Tillet, Felipe Petroski Such, Dave Cummings. Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang. Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, llya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. 2021.
[14] Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211. 12588. 2022.
[15] Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song. syntax-directed variational autoencoder for structured data, arXiv preprint 1802. 08786, 2018.
[16] David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A. Saurous, Jascha Sohl-dickstein, Kevin Murphy, and Charles Sutton. Language Model Cascades. 22Kiv:2207.103422 2022.
[17] Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. In Proceedings of NAACL, 2016.
[18] Jay Farley. An efficient context-free parsing algorithm. Communications of the ACM, 13(2): 94-102, 1970.
[19] Carl Edwards, Tuan Lai, Kevin Ros, Garrett Honke, and Heng Ji. Translation between molecules and natural language. arXiv preprint 11X11:2204.11817 2022.
[20] Richard E Fikes and Nils J Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial intelligence, 2(3-4):189-208, 1971.
[21] Maria Fox and Derek Long. PDDL2. 1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20:61-124, 2003.
[22] Maria Fox and Derek Long. Modelling mixed discrete- continuuo domains for planning. Journal of Artificial Intelligence Research, 27:235-299 297, 2006.
[23] Dan Friedman, Alexander Wettig, and Danqi Chen. Finding Dataset Shorteuts with Grammar Induction. In Proceedings of EMNLP, 2022.
[24] Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang. Jamie Callan, and Graham Neubig. PAL: Program-aided Language Models. arXhv:2211.10435 2022.
[25] Caelan R. Garrett, Tomas Lozano- Perez, and Leslie P. Kaelbling. PDDLStream: Integrating symbolic planners and blackbox samplers. In International Conference on Automated Planning and Scheduling (ICAPS), 2020. URL https: //ap:v/////ivvv//// org aas/ /at./ 08777087052....
[26] Saibo Geng, Martin Josifosky, Maxime Peyrard, and Robert West. Flexible Grammar- Crammar-Based Constrained Decoding for Language Models. 20X1v:2305.13971, 2023.
[27] Malik Ghallab, Adele Howe, Craig Knoblock, Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins SRI, Anthony Barrett, Dave Christianson, et al. PDDL- - the planning domain definition language. Technical Report CVC TR98003/DCS 165. New Haven, CT: Yale Center for Computational Vision and Control., 1998.
[28] Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends@ in Programming Languages, 4(1-2):1-119, 2017.
[29] Minghao Guo, Veronika Thost, Beichen Li, Payel Das. Jie Chen, and Wojciech Matusik. Data-efficient graph grammar learning for molecular generation. In Proceedings of ICLR, 2022.
12

---

[30] Joy He- Yueya, Gabriel Poesia, Rose E Wang, and Noah D Goodman. Solving math word prob- lems by combining language models with symbolic solvers. arXiv preprint arXiv:2304.09102 2023.
[31] Jonathan Herzig and Jonathan Berant. Span-based semantic parsing for compositional generalization. In Proceedings of ACL, pages 921, Online, August 2021. Associ- ation for Computational Linguisties. doi: 10. 10.18653/v1/2021. 1aw.s///oo/................ URL https:
/ //aclanthology. org/2021. http//2111..l.ooooo... acl-long..7, 74.
[32] Jörg Hoffmann. The metric-ff planning system: Translating"ignoriin delete lists"to numeric state variables. Journal of Artificial Intelligence Research, 20:291-341, 2003.
[33] Hanxu Hu, Hongyuan Lu, Huajian Zhang, Wai Lam, and Yue Zhang. Chain-of -f-symbll prompting elicits planning in large langauge models. arXiv preprint axiv:2305.100276 2023.
[34] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. In Proceedings of ICML, pages 9118-9147. PMLR, 2022.
[35] Yong Jiang, Wenjuan Han, Kewei Tu, et al. Unsupervised neural dependency parsing. Associ- ation for Computational Linguistics (ACL), 2016
[36] Lifeng Jin, Finale Doshi-Velez. Timothy Miller, Lane Schwartz, and William Schuler. Unsu- pervised learning of PCFGs with normalizing flow. In Proceedings of ACL, Florence, Italy, July 2019. Association for Computational Linguisties.
[37] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of ICML, pages 2323-2332. PMLR, 2018.
[38] Hiroshi Kajino. Molecular hypergraph grammar with its application to molecular optimization. In Proceedings of ICML, pages 3183-3191. PMLR, 2019.
[39] Aishwarya Kamath and Rajarshi Das. A survey semantic parsing. arXiv preprint 1rXi0:8812.00978, 2018.
[40] Beomjoon Kim, Zi Wang, Leslie Pack Kaelbling, and Tomás Jozano-Péree Learning to guide task and motion planning using score-space representation. The International Journal of Robotics Research, 38(7):793-812, 2019.
[41] Yoon Kim. Sequence-to-sequeene learning with latent neural grammars. In Proceedings of NeurIPS, pages 2,,17,666,2200
[42] Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilistic context-free grammars for grammar induction. In Proceedings of ACL, Florence, Italy, July 2019. Association for Computational Linguistics.
[43] Yoon Kim, Alexander Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. Unsupervised recurrent neural network grammars. In Proceedings of NAACL, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
[44] Mario Krenn, Florian Häse, AkshatKumar Nigam, Pascal Friederich, and Alan Aspuru-Guzik. Self-referencing embedded strings (selfies): A 100% robust molecular string representation. Machine Learning: Science and Technology, 1(4):045024, oct 2020.
[45] Matt J Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In Proceedings of ICML, pages 1955-1954. PMLR, 2017.
[46] Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compositional generalization. arXiv preprint arXiv:2212.06800 2022.
[47] Yaobo Liang, Chenfei Wu, Ting Song, Wenshan Wu, Yan Xia, Yu Liu, Yang Ou, Shuai Lu, Lei Ji, Shaoguang Mao, Yun Wang. Linjun Shou, Ming Gong, and Nan Duan. TaskMatrix.AN AI: Completing Tasks by Connecting Foundation Models with Millions of A APIs. arXiv:2303. 16434, 2023.
13

---

[48] Bill Yuchen Lin, Chengsong Huang, Qian Liu, Wenda Gu, Sam Sommerer, and Xiang Ren. On grounded planning for embodied tasks with language models. arXiv preprint XXiv:220.000663. 2022.
[49] Bo Liu, Yuqian Jiang. Xiaohan Zhang. Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Llm+ p: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304. 1477, 2023.
[50] Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apid- ianaki, and Chris Callison-Burch Burch.. Faithful chain-of chain-of-thooghtt reasoning. arXiv preprint arXiv:2301.13379, 2023.
[51] Maxwell Nye, Anders Andreassen, Guy Gur-Ari, Henryk Witold Michalewski, Jacob Austin, David Bieber, David Martin Dohan, Aitor Lewkowycz, Maarten Paul Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate compu- tation with language models. arXiv:21 14, 2021.
[52] Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. Logic-LM: Em- powering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning. arXiv:2305. 12295, 2023.
[53] Bhargavi Paranjape, Scott Lundberg anbd Sameer Singh, Hannaneh Hajishirzi, Luke Zettle- moyer, and Marco Tulio Ribeiro. ART: Automatic multi-step reasoning and tool-use for large language models. wxXiv:2303000044 2023.
[54] Emmanouil Antonios Platanios, Adam Pauls, Subhro Roy. Yuchen Zhang, Alexander Kyte, Alan Guo, Sam Thomson, Jayant Krishnamurthy, Jason Wolfe, Jacob Andreas, and Dan Klein. Value-agnostic conversational semantic parsing. In Proceedings of ACL, August 2021.
[55] Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable Code Generation from Pre-trained Language Models. Proceedings of ICLR, 2022.
[56] Yujia Qin, Shengding Hu, Yankai Lin, Weize Chen, Ning Ding, Ganqu Cui, Zheni Zeng, Yufei Huang, Chaojun Xiao, Chi Han, et al. Tool learning with foundation models. arXiv preprint arXiv:2304. 08354, 2023.
[57] Linlu Qiu, Peter Shaw, Panupong Pasupat. Tianze Shi, Jonathan Herzig, Emily Pitler, Fei Sha, and Kristina Toutanova. Evaluating the impact of model scale for compositional generalization in semantic parsing. In Proceedings of EMNLP, December 2022.
[58] Shreyas Sundara Raman, Vanya Cohen, Eric Rosen, Ifrah Idrees, David Paulius, and Stefanie Tellex. Planning with large language models via corrective re- re-prompting. arXiv preprint 1xXiv:2211.09933 2022.
[59] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. arXiv preprint arXiv: 1et.i.1000..000 2019.
[60] David Rogers and Mathew Hahn. Extended-connectivig fingerprints. Journal of chemical information and modeling, 50(5):742-754, 2010.
[61] Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Proceedings of NeurIPS, 33: 12559-12571 2020.
[62] Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, et al. Multitask prompted training enables zero-shot task generalization. In Proceedings of ICLR, 2022.
[63] Timo Schick, Jane Dwivedi-Yoa Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettle moyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language Models Can Teach Themselves to Use Tools. 27X1v:2302.04771, 2023. 2023.
14

---

[64] Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of EMNLP. Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
[65] Pratyusha Sharma, Antonio Torralba, and Jacob Andreas. Skill induction and planning with latent language. arXiv preprint arXiv:2//0.01555 2021.
[66] Peter Shaw, Ming- generalization and natural language variation: Can semantic parsing approach handle both? Pruceedings of ACL, August 2021.
Ming-Wei Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional
[67] Richard Shin and Benjamin Van Durme. Few-shot semantic parsing with language models trained on code. In Proceedings of NAACL, pages 5417-5425, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. (15553/112222.mmcclmaiiaa URL https: / https:://aaaattt/t hatp///caaaattoooyoooooooooo wwt.orgg//22 1ttp:/2222.aaccmmaiiii.. www.c-aaainnnnnae.emmmm 396.
[68] Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Anto- nios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. In Proceedings of EMNLP. Association for Computational Linguistics, November 2021.
[69] Tom Silver, Varun Hariprasad, Reece Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez, and Leslie Pack Kaelbling, PDDL plamning with pretrained large language models. In NeurlPS 2022 Foundation Models for Decision Making Workshop, 2022.
[70] David Smith and Jason Eisner. Sunch-SSynh Grammars: Alignment by Soft Projection of Syntactic Dependencies. In Proceedings on the Workshop Statistical Machine Translation, 2006.
[71] Jennifer Sun, Megan Tjandrasuwita, Atharva Sehgal, Armando Solar-Lezama, Swarat Chaudhuri, Yisong Yue, and Omar Costilla-Reyes Reyes. Neurosymbolic programming for science. arXiv preprint arXiv:2210.05055 2022.
[72] Didac Suris, Sachit Menon, and Carl Vondrick. ViperGPT: Visual Inference via Python Execution for Reasoning. wrXiv23303.0812,, 2023.
[73] Mirac Suzgun, Nathan Scales, Nathanael Scharli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoe V. Le, Ed H. Chi, Denny Zhou, and Jason Wei. Chal- lenging big-bench tasks and whether Mlain-of-thought can solve them. arXiv:2210.09261, 2022.
[74] Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can't plan (a benchmark for llms on planning and reasoning about change). arXiv preprint arXiv:2206. 10498, 2022.
[75] Gregor vom Scheidt. Experimental results from applying GPT-4 to an unpublished formal language. 2rXiv:2305.12/96 2023.
[76] Bailin Wang, Ivan Titov, Jacob Andreas, and Yoon Kim. Hierarchical Phrase-based Sequence- to-Sequence Learning. In Proceedings of EMNLP, 2022.
[77] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint arXiv:2305. 16291, 2023.
[78] Mengqiu Wang, Noah A. Smith, and Teruko Mitamura. What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA. In Proceedings of EMNLP, 2007.
[79] Sheng Wang, Yuzhi Guo, Yuhong Wang, Hongmao Sun, and Junzhou Huang. Smiles-bert: large scale unsupervised pre-training for molecular property prediction. In Proceedings of the 10th ACM international conference on bioinformatics, computational biology and health informatics, pages 429-436, 2019.
15

---

[80] Xuezhi Wang, Jason Wei, Dale Schaurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In Proceedings of ICLR, 2023.
[81] Yushi Wang, Jonathan Berant, and Percy Liang. Building semantic parser overnight. In Proceedings of ACL, Beijing, China, July 2015.
[82] Zi Wang. Stefanie Jegelka, Leslie Pack Kaelbling, and Tomás Lozano Pérez.. Focused model- learning and planning for non-Gaussian continuous state-action systems. In 2017 IEEE International conference on robotics and automation (ICRA), pages 3754-3761. IEEE, 2017.
[83] Zi Wang. Caelan Reed Garrett, Leslie Pack Kaelbling, and Tomás Lozano-Péret Active model learning and diverse action sampling for task and motion planning. In 2018 JEFE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4107-4114. IEEE, 2018.
[84] Zi Wang, Caelan Reed Garrett, Leslie Pack Kaelbling, and Tomás Lozano-Pérez, Learning compositional models of robot skills for task and motion planning. The International Journal of Robotics Research, 40(6-7): 2021.
[85] Jason Wei, Maarten Paul Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew Mingbo Dai, and Quoc V. Le. Finetuned language models are zero-shot learners. In Proceedings of ICLR, 2022.
[86] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Proceedings of NeurIPS, 2022.
[87] David Weininger. Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules. Journal of chemical information and computer sciences, 28 (1):31-36, 1988.
[88] Victoria Xia, Zi Wang, and Leslie Pack Kaelbling. Learning sparse relational transition models.
In International Conference Learning Representations, 2019.
[89] Frank F Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoomn. A systematic evaluation of large language models of code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, pages 1-10, 2022.
[90] Ryan Yang, Tom Silver, Aidan Curtis, Tomas Lozano-Perez, and Leslie Pack Kaelbling. Pg3: Policy-guided planning for generalized policy generation. arXiv preprint arXiv:2204. 10420, 2022.
[91] Songlin Yang, Yanpeng Zhao, and Kewei Tu. Neural bi-lexicalized PCFG induction. In Proceedings of ACL, Online, August 2021. Association for Computational Linguisties.
[92] Songlin Yang, Yanpeng Zhao, and Kewei Tu. PCFGs can do better: Inducing probabilistic context-free grammars with many symbols. In Proceedings of NAACL, 2021.
[93] Songlin Yang, Roger P Levy, and Yoon Kim. Unsupervised discontinuous constituency parsing with mildly context-sensitive grammars. arXiv preprint arXiv:2212.09140, 2022.
[94] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint ar3vv:2305. 10601, 2023.
[95] Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. Compositional exemplars for in-context learning. arXiv preprint arXiv:2302.05698, 2023.
[96] Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett, Benchmarking multimodal regex synthesis with complex structures. In Proceedings of ACL. Association for Computational Linguisties, July 2020.
[97] Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett, Satisfiability-aide language models using declarative prompting, arXiv preprint arXiv:2305.0663 2023.
16

---

[98] Pengcheng Yin, Hao Fang, Graham Neubig, Adam Pauls, Emmanouil Antonios Platanios, Yu Su, Sam Thomson, and Jacob Andreas. Compositional generalization for neural semantic parsing via span-level supervised attention. Proceedings of ACI., 2021.
[99] John M Zelle and Raymond J Mooney. Learning to parse database queries using inductive logic programming. In Proceedings of the national conference on artificial intelligence, pages 1050-1055, 1996.
[100] Hao Zhu, Yonatan Bisk, and Graham Neubig. The return of lexical dependencies: Neural lexicalized PCFGs. Transactions of the Association for Computational Linguistics, 8, 2020.
17

---

Few-Shol
Retrieval-based
GeoQuery Out-of-Dist.
GeoQuery
SMCalflow Overnight-Hi
GeoQuery
SMCalflow Overnight-Bit
Template TMCD> Length NewFune
Train
32
560
128
1436
440
453
Test
280
360
399
280
360
399
439
440
440
447
Table Statistics of the splits used for experiments on semantic parsing,
Approach
GeoQuery
SMCalFlow
Overnight-B
Standard Prompting (unconstrained decoding)
81.5 (1.0)
46.4 (1.0)
54.7 (1.0)
w. construined decoding (Ø E L(G))
81.8 (4.3)
(5.66
54.7 (1.6)
Linearized Derivation Tree Prompting
77.5 (1.0)
50.0
56.4 (1.0)
Grammar Prompting (unconstrained decoding)
(1.0
(0.0)
(7.4
w. grammar constrains (G C G)
88.6 (3.0)
53.0)
60.4 (1.4)
w. grammar and program constraint (Ø E L(G))
88.9 (3.3)
(3.3)
60.9 (2.8)
w. oracle grammar (G = Gly))
96.1 (1.3)
80.0 (1.0)
94.2 (1.0)
w. oracle grammar program constraint
96.8 (2.1)
83.6 (2.6)
96.5 (1.0)
Table 7: Extended results which show the number of Codex calls example on few-shot semantic parsing in brackets. Columns in grey show program accuracy, while white columns others indicate execution accuracy.
A Experiment Details
A.1 Semantic Parsing
Statistics and Splits.
We show the statistics for the splits used for the experiments in Table 6.
For GeoQuery, we utilize the standard split from Zelle and Mooney [99] in the retrieval-based setting and the Template, TMCD, and Length splits from Shaw al. [66]. We randomly sample 32 examples from the training set of the standard split to create the few-shot split. To generate the NewFunc split, we designate examples utilizing the following eight functions as test examples: smallest, shortest, most, highest, sum, population_1, count, major; the remaining examples are incorporated into the training set.
For SMCalFlow, we adopt the 16-shot and 128-shot cross- settings from Yin et al. [98] as our few-shot and retrieval- bassdd settings, respectively. It is noteworthy that the training set of the original splits contains approximately 25k in-domain training examples. Previous work [96, 57] utilized these examples their retrieval set. However, in experiments, found that incorporating in-domain examples did not enhance performance. Consequently, we use 16/128 cross-domain examples as our SMCalFlow, training set in the few-shot and retrieval settings, respectively. For all experiments we used the preprocessed version from Qiu et al. [57]. which employs a more concise LISPRESS format [54] than the original version [98]. This format aligns with Ye et al. [96] for a fair comparison.
For Overnight- - we employ the standard split from Wang et al. [81] in the retrieval setting. We randomly sample 32 examples from the training set of the standard split to create the few-shot split.
Scoring Functions for Constrained Generation. For each candidate continuation E Σ [pectx]] for correction, we first form a partial program via concatenation yprefix w and then feed it into Codex to obtain the score for the candidate via
log PL G. x. Yprefxx (, 1
In the case where uo consists of multiple BPE tokens, e-g., FindManger tokenized into Find, Manager, and (, we average the token-level log-liieli to obtain a candidate-level score. However, when the size of Σ Epetts exceeds 16, invoking Codex for each candidate becomes too expensive. To address this issue, we employ BeRT to select 16 most plausible candidates first via dot product,
(SentenceBERT (T SSentenceBERT(ypcss w)),
where SentenceBERT yields the embeddings for the incorrect prediction ý. and a candidate of corrected partial program 3ppefix
18

---

Molecule Class
Temperature
Presence Penalty Frequency Penalty
Sampling specialized grammars
Acrylates
0.6
0.1
0.1
Chain Extenders
0.6
0.1
0.1
Isocyanates
0.6
0.4
0.4
Sampling molecules
Acrylates
0.6
0.1
Chain Extenders
0.6
0.1
0.1
Isocyanates
0.3
0,4
0,4
Table 8: Hyperparameters for sampling specialized grammars G (top) and the molecules ÿ in grammar prompting for molecule generation. Standard prompting uses the same hyperparameters for
The functionality of obtaining the log-likelihood for a candidate continuation given prefix is applicable via Codex APIs II via setting logprobs=True and echo=True. Unfortunately, subsequent models (e.g., GPT-3.5 and GPT-4) disable such functionality, As a workaround, we simply use the scoring function based on SentenceBERT to directly select the best candidate in our PDDL planning experiments.
Cost Efficiency. We assess various decoding strategies for their cost efficiency, focusing on the number of API calls. The number of Codex calls resulting from the few-shot semantic parsing experiments is presented in Figure 7, alongside the corresponding accuracy metrics. The results indicate that standard prompting under constrained decoding leads to a significantly higher number of Codex calls. Similarly, grammar- grammar-ppompting with constraints also results in increased number of Codex calls. However, when employing both grammar and program constraints, the number calls decreases meaningfully in comparison to standard prompting under constrained decoding. Future work might consider exploring strategies for more cost-efficient constrained decoding.
Grammar Prompting with Annotated Rules. We have additionally experimented with enhancing BNF rules by appending natural language comments. As illustrated in Figure 6, we pair each BNF rule with its corresponding natural language phrases extracted from the given query æ. These manually annotated comments yield an explicit correspondence between natural language phrases and their corresponding BNF rules, thereby better facilitating interpretation and application of the grammars for generating programs. When employing the augmented grammar prompting, we noticed marginal improvements on SMCalFlow (+1.0%) and Ovemight-Blen Blockks (0.5%), with no observed enhancement on GeoQuery. While the gains might not appear significant, this predicted alignment could potentially contribute improved interpretability and further constraints on generation. For instance, the phrase "somcone's manager" should consistently trigger the function F FindManager (. We leave the exploration of utilizing the augmented rules for future work.
A.2 Molecule Generation
Sampling Procedure Different from semantic parsing and PDDL planning, where the most proba- ble program y needs be found via arg max inference, molecule generation has empty specification and requires sampling from a prompting-baie based distribution. The sampling procedure for grammar prompting consists of three stages: (I) we randomly sample permutation of given molecules.
denoted as ग, (2) based on prompt formed by the permutation, we sample a specialized grammar G via
G ~ PL æ. (TI)) (
iii) we finally obtain the molecule conditioned G.
ÿ ~ PL G (Gly (+1)) (m )
We list the hyperparameters used for the sampling procedure in for (2) in Table 8 (top) and for (3) in Table 8 (bottom).
htttps: //learn www.err.miirosof........... wicrrsof..co/eeer///aaae/////r/p ait.rstt..oorrrooaaacceeeeeeeeee
19

---

LLM Prompt
are an expert programmer, and you need to write program for given natural language query. First, you should write grammar that contains all the necessary BNF rules. Then, you should write programs that conform to your predicted rules.
( find the meeting on Wednesday with Bob and Carol "
event constraint
"QueryEvent(" constraint ")"
find the meeting
(&" constraint constraint ">"
(start_?" date ")"
"atteende_ attendee attendee ")" "Wednesday"
with Wednesday
date at attendee
"Bob" "Carol"
Bob and Carol
QueryEvent(& && (start Weddesdayy/atteeddee Bob Carol))
Add meeting with Jean's manager Wednesday at 3PM
LLM Output
Ō:
event constraint
"CreateEvent(" constraint ")" "(8" constraint constraint ")" "(start_ date time ")" "(attendee_? attendee ")"
Add meeting
... at
with
date time attendee
"Wednesday"
Wednesday
"NumberPM(3)"
3PM
"FindManager(" attendee ")" "Jean"
Jean's manager
y: CreateEvent(&& (start_ Wednesday HumberPK(3)
(indMMnaage((eean))
Figure 6: Example of grammar prompting where BNF grammars additionally annotated with natural language comments (shown green). These manually curated comments provide detailed mapping between natural language phrases and their corresponding BNF rules, thereby better facilitating interpretation and application of the grammars for generating programs. We manually craft and add these comments to the few-shot prompts (top). The model predicts this during inference (bottom).
In comparison, the sampling procedure for standard prompting only consists of two stages: (1) we randomly sample permutation of given molecules, denoted n, (2) based prompt formed by the permutation, we directly sample a molecule via
T ~ Pu (y (
The hyperparameters used for Step (2) is the same in grammar prompting and shown in Table (bottom).
While observed that Earley- based constrained generation enhances grammar prompting in terms of improving validity, other metrics, such as the retrosynthesis score, decreased significantly. This discrepancy could be attributed to the fact that existing LLMs, due to their limited exposure to molecules represented in SMILES format, struggle with comprehending and applying the BNF grammar rules of SMILES.. Overall, prompting can tap into the capacity of LLMs to understand and apply BNF rules. However such capacity still remains limited in text-focused LLMs.
current findings
preliminary evidence that grammar
A.3 PDDL Planning
Restricted Action Space The specialized grammar defined for PDDL planning essentially delin- eates constrained action space that includes necessary actions and their associated objects. Our empirical results found that limiting the classical GBFS planner to the objects selected by a spe- cialized grammar proved too restrictive, yielding beneficial results only within the Blocks domain. Therefore, we decided to remove this limitation, thus expanding the action space of GBFS to contain the actions predicted from the grammar with an unrestricted range of objects.
20

---

B Prompts
Figures 7, and 9 demonstrate the prompts with grammars, based on actual examples in the SMCalFlow, GeoQuery, and Overnight datasets respectively. Because the general grammar of SMCalFlow is long (around 4k tokens), do not include within the prompt. For GeoQuery and Overnight, the general grammar is integrated part of the instruction within the prompt. In the context of molecule generation, general grammar for SMILES!2 is also included. Figures and 11 demonstrate the prompts with action DSLs for PDDL planning.
21

---

LLM Prompt
are an expert programmer, and you need to write program for given natural language query. First, you should write grammar that contains all the necessary BNF rules. Then, you should write programs that conform to your predicted rules.
query: need meeting with Elli and her team Wednesday afternoon
BNF grammar rules:
call
(Yield" event ")"
event
" "CratterrelnghhEEnttaaarrrr wwent__costrriiiii ")"
event_constraint
"(&" event_constraimt event_constraint ")"
"(Event.start_ datetime_ooe seeetimmcoosttrinnt ")"
" (Evenn..tttendees_.
")"
detetiine_constraint
" " time date ")"
time
" "(Afternoon)"
date
day
day
"NNextDow" day ")" DAY
DAY
" (Wednesday))
attendee_constrainng
"(&" ceattedde__cosstrre attendee attendee_constraile ")"
"(Attendeel piint person ")"
(AttendeeListttaseeellll person ")" recipient "(FindTeamnf" person ")"
person
recipient
" (Execute (refer (extensionConstraiin" recipient ")))"
" "(Recipientwi thNamel ike (PersonName. apply" string "))² "EEli""
string
program based on BNF grammar rules:
(aaaaa/rrrateeellgghheeeeetette (&veett.tt stwent.sstat....
((ttieeeess((Attttittaatta hatpr//enneeeeeec/aattteeeeeeeee /|cl//ttemeeeLisstssccccppeeee/p (Execute
http://iiilllnoooeeoeeroooaaaaaa "E11i")))))
(itt (Bxecuterrefer orgpap/eeeeeeaaaateeeeeeeeeeeeer (eeeeeeeeeeeeeeeeesssssssaaaaaaa
query: Create a meeting tomorrow with the staff
LLM Output
BNF grammar rules:
call
(Yield" event ")"
event
EereattPreelighhtEeettraaa event_ cepet__onsttaintt ")"
event_constraiint
"(8" event__constriit ween_ccosttriigg ")"
"(Event.start_3 patetime_constraa ")"
"(Event.attendees_. attendee constraint ")"
constrime_consrraint
"DDateTime date_?? tenetimmcconstaiitt ")"
"(?" OP datetime ")" "="
OP
datetime
date day DAY (Tomorrow)"
date
day
DAY
Extendee_constralle
serenddeeListHsseeppll person ")"
person
(FindReports" per ")" recipient
recipient
"(toRecipient (CurrentUser)))
program based on the BNF grammar rules:
(Yield(Cresse
(DateTime.da)) date = http:a/)eeecoee.ttteeeeeeeeettte (FindReports cecpleeporttttRecipppp (toRecipient (CurrentUseer)))))) (tw.eeeeppeeeetttrreetttee)))))e
Figure 7: Prompt with real examples from the SMCalFlow datasct.
22

---

LLM Prompt
You are an expert programmer, and you need to write a program for given natural language query. First, you should write grammar rules by choosing from the following BNF rules. Then, you should write programs that conform to predicted rules.
[BEGIN RULES]
query
"answer(" answer ")" city state num place river country "city(" city ")"
answer_tye
city
"cityid("" CITYNAME ",, "" STATEABBREV "!)"
"cityid("" CITYNAME " _)"
"capital(" city ")"
"major(" city ")"
"capital_1(" state ")"
"loc_2(" state ">"
"lac_2(" country ")"
"largest(" city ")"
"smallest(" city ")"
"intersection(" city ", city ")"
"exclude(" city city ")"
"largest_one (population_1G 1(" city "))"
"largest_one (densityyyy city "))"
Smmallees_commeoouuatiiiio city "))"
smmaleest_ooeedeesiieeeee city "))"
ALL_CITY
[END RULES]
query: what states border hawaii ?
BNF grammar rules:
query
"answer(" answer_type ")" state
answer_type
state
"state(" state ")"
"next_to_2(" state ")"
"stateid(" STATENAME "*"" "hawali"
STATENAME
program based on the BNF grammar rules: ansver(state to 2attaee ((aaa((aaaa)))
query: how many major cities in arizona
L.M Output
BNF grammar rules:
query answer_type
"answer(" answer_type ")"
"count(" city ")"
city
"major(" city ")"
"city(" city ")"
"loc_2(" state ")"
state STATENAME
"stateid(" STATENAME ">)"
"arizona"
program based the BNF grammar rules: answer oo (attaaaaaaidaarrraaaaaaa
il (rrizztn ()))))
Figure 8: Prompt with real examples from the GeoQuery dataset.
23

---

LLM Prompt
You are an expert programmer, and you need to write program for the given natural language query. First, you should write grammar rules by choosing from the following BNF rules. Then, you should write programs contorm to your predicted rules.
[BEGIN RULES]
list_value
"(listvalue" list_value ")"
"(filter" list_value PROPERTY ")"
"(filter" vist_value PROPERTY OP list_value ")"
"(superlative" list_value AGGREGATE
(ensureeMumericrroperryy PROPERTY "))"
"ccountSuperlative" list_value AGGREGATE PROPERTY ")"
"[_siee" list_value ")"
"aggregate" AGGREGATE list_ value ")"
"gettPoopetty" 1ist_value PROPERTY ">"
"ggetProperty (singleton" SINGLETON ETOL_VALUE ") !type)"
"(concat" _NTITY_VALUS ENTITY_VALLE ")"
"(concat" NUMBER_ NUMBER_VALUE ")"
ENTITY_VALLE NAMBER_VALLLE
PROPERTY
"shape" "color" "length" "is_special" "width"
"height" "left" "right" "above" "below"
"(reverse left)" "(reverse right)"
"(reverse above)" "(reverse below)"
SINGLETON_ VALUE ENTITY_VALLE VVLUEE
ETOUEVALUE
"en. "en.block" "'en.shape"" "en.color"
"en. "en.block. blockkblock1" "ee..block.bbll
"en. shape. shape.pyramid
"en. shape. cube" |enn.ooorr red" "en.color "3 en. inch" "6 en.inch" "2"
con.coo.rggeen green"
NUMBER_VALE VALUE
OP
"=" ">" "<" ">=" "<=" "!="
AGGREGATE
"sum" "max" "min" "avg"
[END RULES]
query: which brick is taller than brick
BNF grammar rules:
list_value
(listValue" list_value ")"
(aggregate" AGGREGATE List_value ")"
"ggetPropert"" list_value PROPERTY ")"
"ggePPropert (singleton" SINGLETON_VALUE ") !tyee)
AGGREGATE
"avg"
SINGLETON. VALUE
en. block" "width"
PROPERTY
program based on BNF grammar rules: (ListValu(agggreaat avg geetrpprtyieetrrpprtyyysgggaaa en.block) Itype) width)))
query: look right of block and get the special block
LLM Output
BNF grammar rules:
list_value
(listValue" list_value ")"
"ffilter" list_value PROPERTY OP list_value ")"
"(filter" list_value PROPERTY ")"
"(getProperty (singleton" SINGLETON_ VALUE ") !type)
ENTITY_ VALUE
SINGLETON_ BOOILETTONVVLLLL VALUE PROPERTY
"en. "locblock"
"ss is_special"
" (rreeerse left)"
"="
UNTITY_VALUU
*en block.block1"
program based on the BNF grammar rules:
(astValueffiltrrff1lll www.ltteergeerropeeeeeoooe weeePooorttyssinglttee.. en ml.lkok) !type) is_special) (reverse left) en www.block..lll block)))
Figure Prompt with real examples from the Overnight dataset. Some long rules are omitted fit the space.

---

LLM Prompt
Q:
(sobjects b block) (iinit (clear d) (clear e) (ontable d) (ontable a) (on e e) (on b) (on b a) (handempty))
(goal (on e) (on (on d) (on d c))
DSL:
plan
action+
action
(unstack" object object ")"
"putt-down" object ")"
(pick-up-and object object ")"
(uustack-and-sttac) object object object ")" "c" | "e" "d" "b" "a"
object
A:
(unstack c e) (put-down c) (pick-up-und-stack d c) (unstack b) (put-down e) (unstack-amd-stack b a d) (pick-up- and-stack e b) (pick-up-and-stack e)
Q:
(:objects b block)
(iinit (clcar a) (clear <) (clcar d) (ontable a) (ontable b) (ontable d) (on b) (handempty))
(ggoal (on b) (on b e) (on
DSL.:
plan
action+
action
= Luunttak-and-staade object object object ")"
(pick-up-and-steee object object ")
object
"c"
A: (unstack-and-stack (pick-up-and-stack e) (pick-up-and-stace
Q:
(cojeets a b d block) (iinit (clear с) (clear a) (clear h) (elcar d) (ontable e) (ontable (ontable b) (ontable (handempty)) (goal (on c) (on e b) (on h a))
LLM Output
plan action object
actiont
waick--u-add-ssaae stacckkk object object ">" "b "a" "c" "d"
anid--up-and-stack a) (pick-up-and-stad) e h) hiik--u--and-sackk c)
Figure 10: Prompt with real examples in the Blocks domain from Pyperplan. The prompt template follows [69].
25

---

LLM Prompt
Q:
(cojeccss crateO) cratel crate2 crate3 crate4 crate5 depott) distributorO) distributorl hoistO hoistl hoist2 palleto palletl pallet2 pallet3 palletd pallet5 truckO truck1 object)
(init (pallet pallet0) (surface pallet0) (at palletò depot0) (clear crate5) (paller pallett) (surface pallett) (at pallet! distributorO) (clear palletl) (pallet pallet2) (surface pallet2) (at pallet2 distributorI) (clear crate3) (pallet pallet3) (surface pallet3) (at pallet3 distributorU) (clear pallet3) (pallet pallet4) (surface pallet4) (at pallet4 distributor()) (clear crate4) (pallet pallet5) (surface pallet5) (al palletS distributorl) (clear cratel) (truck truck0) (at truck0 dis- tributorl) (truck truck1) (at truckl depotU) (hoist hoist0) hoistO depott) (available hoistU) (hoist hoistl) (at hoist distributorO) (available hoistl) ) (hoist hoist2) (at hoist2 distributorl) (available hoist2) (crate crateO) (surface crateO) crateO distributorO)
crated palletd) (crate cratel) (surface cratel) (at cratel distributor) pallet5) (crate crate2) (surface crate2) (all crate2 distribuiorl) (on crale2 palle(2) (crate crate3) (surface crate3) (al crate3 distributorl) (on crate3 crute2) (crate crute4) (surface crate4) (at crate4 distributorU) (on crate4 cratel) (crate crate5) (surface crate5) (at crate5 depot() (on crate5 pallett) (place depott) (place distributorU) (place distribu- torl))
cratel
(ggoal (on crateO pallet3) (on cratel crate4) (on crate3 palletl) (on crate4 pallet5) (on crate5 cratel)
DSL:
plan
==
actiont
action
(lift-and-drive) object object object object object object ")"
(dr ieri-vvdd-load object object object object ")"
s'drive-and-lfff object object object object object ">"
(lift" object object object object ")"
(dr sarriveand-unlose undddd" object object object object object ">"
(drop" object object object object ")"
object
"truck1* "hoist0" "crate5" "pallets" "depotø" "truckØ" "hoistz" "crated" "cratel" "distributor!" "hoist1" "pallet4" "distributore" "crate1" "pallet5" '"crate3" "ccrate"" "palleti" "pallet3"
A:
alif--and-drive truck1 hoistO crate5 pallet0 depott depot0) (drive-and-load truck1 hoistO crate5 depot() (drive-and- lift truckO hoist2 crate4 crateO distributorI) (lift hoistl crateO pallet4 distributorO) (drive-and-lifi truck1 hoistO cratel pallet5 deputO) (drive-and-load truck1 hoistO cratel depolO) (drive-and-lift truck1 hoistO crate3 crate2 de- pott) (drive-and-load truckl hoistD crate3 depotO) (drive-and-unlow) truckl hoist0 crate3 palletl depotO) (drop hoist2 crate4 pallet5 distributorl) (drive-and-unloat truckl hoistO cratel crate2 depoto) (drive-and-lit truck0 hoist2 cratel crate2 distributorl) (drop hoist2 cratel crate4 distributorI) (drive-and-unloal truckl hoistO crate5 cratel depot() (drup hoistl crateO pallet3 distributor()
Q:
(cobjects crateO cratel crate2 crate3 depotO distributorO) distributorl hoistO hoistl hoist2 pallet0 pallett pallet2 truck) truck1 object) (init (pallet pallett) (surface palletO) (at palleto depott) (clear crate() (pullet palletl) (surface palletl) (at palletl distributorO) (elear crate3) (pallet pallet2) (surface pallet2) (at pallet2 distributor (clear crate2) (truck truck0) (at truck0 depor0) (truck truckl) (at truckl depott) (hoist hoist() (at boistO depotO) (available hoist() (hoist hoistl) (at hoistl distributort) (available hoistl) (hoist hoist2) (at hoist2 distributorl) (available hoist2) (crate crate0) (surface cratel) erateO depotO) (on crateO pallett) (crate cratel) (surface cratel) (at cratel distributorl) (on cratel pallet2) (crate crate2) (surface crate2) (at crate2 distributorI] (on crate2 crate I) (crate crate3) (surface crate3) (at crate3 distributorO) (on crate3 palletl) (place depot() (place distributorO) (place distributorl)) )) (goaa (on crateO) pallet2) (on cratel crate3) (on crate2 pallett) (on crate3 pallet!)) DSL:
LLM Output
plan action
action+
(lift-and-drrive" object object object object object object ">"
" "(lift" object object object object ")"
"(drive" object object object ")"
"(drive-and-lift" object object object object object "y"
"ddrop" object object object object ")"
(drive-and-Load) object object object object ")"
o "truck0" "hoist8" "crate0" "palleto" "depot8" "hoist2" "cratez" "cratel" "distributori " "distributore" "hoisti" "pallet2" "crate3" "truck1"
(drive-and-unloadd object object object object object ")"
object
A:
(lift-an--drive truckO hoist0 crateO palletO depott depotO) (lift hoist2 crate2 cratel distributorl) (drive truck0 depotU distributort) (drive-and-lif) truck0 hoistl cratel pallet2 distributorU) (drop hoistl cratel crate3 distributorU) (drive-and-load truckl hoistO crateU depot0) (drive-and-unload truckl hoistO cratel) pallet2 depott) (drive truckl depotO distributorl) (drive-and-load truck hoist2 crate2 distributorI) (drive-and-unlond truck1 hoist2 crate2 palleto distributor!)
Figure 11: Prompt with real examples in the Depot domain from Pyperplan. The prompt template follows [69].
26


Reviews:
[{"review_id": "1jRtSmLhlZ", "reviewer": "Reviewer_qhZ7", "summary": "This work explores grammar prompting as a simple approach for enabling LLMs to use external knowledge and domain-specific constraints, expressed through a grammar expressed 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. \n\nThe authors apply grammar prompting to various domain specific languages for semantic parsing (SMCalFlow, Overnight, GeoQuery), AI planning (PDDL), and molecule generation (SMILES), and find that it can meaningfully improve upon standard prompting baselines in the few-shot setting.", "questions": "See above.", "limitations": "See above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\nThis paper is interesting and well-written. \n\nThis work is an efficient prompting generation algorithm for LLM. \n\nExperimental results show that the proposed method seems effective in generating sequences with grammars. ", "weaknesses": "\n\n\nIn experiment part, how do you ensure the results are enough to verify the proposal? For example, the superiority in molecule generation is not well established compared with the other graph-based generation methods.  \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and the recognition of the strengths of our work.\n\n> “In experiment part, how do you ensure the results are enough to verify the proposal? For example, the superiority in molecule generation is not well established compared with the other graph-based generation methods.”\n\nIn molecule experiments, we focus on low-data class-specific molecule generation, as opposed to general molecule generation with massive amounts of data. In the low-data regime, recent work [29] has verified that current graph-based models fall short significantly compared with their grammar-based model, in the same settings as our molecule experiments. Our grammar prompting further improves upon [29] and thereby outperforms graph-based models in the specific low-data regime. \n\nFurthermore, our research reveals the initial success of applying LLMs in molecule generation tasks, suggesting a potentially fruitful avenue for future exploration.\n"}, {"review_id": "BaPOkLl42Y", "reviewer": "Reviewer_rfkJ", "summary": "This paper presents an approach for improving few-shot prompting of LLMs for tasks that produce structured outputs, where the structure can be described by a grammar in BNF form. The approach is similar to chain-of-thought prompting: for a given input x, the LLM is prompted to generate the minimal subset of grammar rules that can produce the corresponding output G[y], then conditions on x and G[y] to produce y. Decoding can be done in the standard way (e.g. greedy decoding), but the paper also presents an improved version that uses a modified Earley parsing algorithm to ensure that the outputs y conform to the predicted grammar G[y]. All variants of the approach are effective, providing substantial benefits over reasonable baselines (e.g. standard few-shot prompting and constrained decoding) across a range of tasks, including realistic semantic parsing benchmarks, SMILES molecule generation, and plan initialization for PDDL planning.", "questions": "Q1) How are the examples being retrieved in the retrieval-based ICL experiments? Do they use similarity of the generated grammar as well, or just the inputs?\n\nQ2) Which Codex model is being used in the experiments here?\n\nMinor clarification questions/points (don't need to address in author response):\n- Be more consistent with the bolding of numbers in results tables, e.g. in Table 5\n- The limitations mentions a lack of improvement for regexes, were these in experiments not reported in this paper?\n- I didn't fully understand the Macro experiments on the PDDL tasks (although I did not check the appendix carefully).\n- spelling of \"conditioned\" in Fig 2 caption\n- while the semantic parsing experiments are well-motivated by tool use, they aren't really tool use IMO, so renaming 4.1 might be appropriate \n", "limitations": "The paper's limitation section did a good job, I think.\n\nOne additional potential limitation, though, is that, like in chain-of-thought prompting, the approach effectively introduces a pipeline: the model needs to first predict the grammar rules for an example, then condition on these rules to predict the output. This could lead to error propagation if the first step is wrong. However, the results are strong enough to indicate this probably isn't happening, and if it did it could be addressed with self-consistency / consensus decoding or another MBR-like approach.\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The approach is elegant and seems simple to implement, treating the LLM as a black box and needing only knowledge of the output grammar. While the constrained generation procedure is a bit more complex (and requires multiple LLM calls), it's also well-motivated and elegant, and isn't required for strong performance. I could definitely see the overall approach being practically useful in tasks that require DSLs that were low-resource in pre-training, such as tool use.\n\nThe experiments are thorough, with strong results across a range of tasks and datasets. The compositional generalization results on GeoQuery were especially interesting to me, as they indicate that the grammar examples in the prompt don't need to fully cover the grammar rules used in the output.\n\nThe paper is very clearly written, especially given the number of experiments presented and space constraints (but see below for a few questions). ", "weaknesses": "One minor weakness is that it would benefit the paper to also show results on other LLMs to give evidence that the approach is broadly applicable, especially since of the three models evaluated, GPT-3.5 derives from Codex (I believe, if the paper is using code-davinci-002) and GPT-4's training data is unknown. StarCoder-15B could be one such model, although it may not be few-shot promptable. \n\nA few details could be made clearer, if space is available, see below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and the recognition of the strengths of our work.\n\n\n> “One minor weakness is that it would benefit the paper to also show results on other LLMs …” \n\nIn our recent experiments with PaLM2-Large using grammar prompting, we utilized the same 100 examples mentioned in Table 3. Our results indicate that grammar prompting outperforms the standard prompting baseline in two of the three benchmarks, though the performance improvement is less than was the case with the GPT family of models. \n\n\n| | GeoQuery | SMCalFlow | Overflow-Blk |\n|:------:|:-----:| :-----:|:-----:|\n| Standard Prompting | 90 | 14 | 59 |\n| Grammar Prompting | 87 | 17 | 62|\n\n\n> Q1) How are the examples being retrieved in the retrieval-based ICL experiments? Do they use similarity of the generated grammar as well, or just the inputs?\n\nFollowing prior work (e.g., Qiu et al. ’22), examples are retrieved based on their BM25 scores, using only the input natural language (NL) questions to calculate these scores. Although employing generated grammar for retrieval might enhance the quality of the examples obtained, it necessitates a minimum of two calls of an LLM per instance. In comparison, relying on NL questions for retrieval usually demands just a single call of LLM.\n\n> Q2) Which Codex model is being used in the experiments here?\n\nWe used code-davinci-002 in the experiments.\n\n> Minor clarification questions\n\nThank you for pointing out, and we will clarify these in our revised version."}, {"review_id": "dofmBAemyk", "reviewer": "Reviewer_pwxh", "summary": "The authors investigate the effectiveness of grammar prompting as a simple approach to help LLMs utilize external knowledge and domain-specific constraints. This approach is motivated by the goal of enabling LLMs to generate DSL outputs that differ significantly from those encountered during pretraining. The authors achieve this by using a BNF grammar during in-context learning. In their framework, the LLM first predicts a BNF grammar based on a test input and then generates output constrained by the rules of the grammar. The experiments conducted demonstrate that grammar prompting enables LLMs to perform competitively on a diverse range of DSL generation tasks, such as semantic parsing, PDDL planning, and molecule generation.\n", "questions": "Have you explored other grammar forms?\n", "limitations": "No negative societal impacts\n", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Novel method for prompting and constraining LLM generation using BNF grammar.\n- Strong experimental results.\n- The method is described clearly and is sound.\n- The method is relatively simple yet effective. The framework is refreshing and is expected to have a significant impact on the semantic parsing community.\n", "weaknesses": "Minor: The contributions and novelty should be stated at the end of the introduction section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and constructive suggestions.\n\n> Minor: The contributions and novelty should be stated at the end of the introduction section.\n\nWe will make the contributions/novelty clearer in the introduction.\n\n> Have you explored other grammar forms?\n\nWe explored only the BNF meta-syntax formalism and did not consider alternatives (e.g., Wirth syntax notation), which are less commonly used in practice to describe syntaxes. However, this is a very interesting avenue and we hope to explore this direction in our future work.\n"}, {"review_id": "fmCkBKVTKK", "reviewer": "Reviewer_8y4i", "summary": "This paper studies generating strings from highly structured languages for large language models (LLMs). The authors propose grammar prompting to enhance LLMs to use external knowledge and domain-specific constraints, expressed through a grammar expressed in Backus–Naur Form. Serving as intermediate reasoning steps, these grammars (metalanguage) enhance the model's performance in generating highly structured languages in domains such as semantic parsing and molecule generation. The idea is simple and effective, and the experimental results well support the claim.", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "+ The paper is well-written and easy to follow.\n\n+ A simple and effective method was presented, leading to improved downstream performance compared with simple prompting.", "weaknesses": "- The idea is not that novel, which uses metalanguage as the bridge that leads to the ultimate structured language. The method is an intuitive extension of the standard prompting (or chain-of-thought prompting) method.\n\n- Improvements over simple prompting methods are validated, but whether the method can beat more sophisticated algorithms (e.g., the recent tree-of-thought reasoning [3]) is unknown. However, as the authors claimed, the focus of this paper is not to achieve SOTA in downstream tasks.\n\n- The proposed constrained generation method is applied at the sub-sentence level, instead of the token level. Besides, the idea of constrained decoding has been explored in previous works [e.g., 1,2], which in turn challenges the novelty of this paper.\n\n\n[1] Hokamp, Chris, and Qun Liu. \"Lexically constrained decoding for sequence generation using grid beam search.\" arXiv preprint arXiv:1704.07138 (2017).\n[2] Huang, Wenlong, et al. \"Grounded decoding: Guiding text generation with grounded models for robot control.\" arXiv preprint arXiv:2303.00855 (2023).\n[3] Yao, Shunyu, et al. \"Tree of thoughts: Deliberate problem solving with large language models.\" arXiv preprint arXiv:2305.10601 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and helpful comments.\n\nWe would like to emphasize the contribution and novelty of our work: (1) We focus on enabling LLMs to generate highly structured languages from just a few exemplars, a task where neither the standard nor the chain-of-thought prompting proves sufficient.  (2) Our method, grammar prompting along with the constrained decoding algorithm, is a novel and practical method that efficiently solves the grammar and program generation problem. (3) Our experiments on tool use, molecule generation, and PDDL planning are the first extensive set of empirical studies on the general capabilities of LLMs for data-efficient generation across a broad range of structured languages. We will make the novelty and contributions clearer in the new version of this paper.\n\n> The idea is not that novel, which uses metalanguage as the bridge that leads to the ultimate structured language. The method is an intuitive extension of the standard prompting (or chain-of-thought prompting) method.\n\nWhile our method can be viewed as “an intuitive extension of the standard prompting”, our motivation, problem (as mentioned above), and ideas are very different from those of standard prompting. To solve the grammar and program generation problem, we drew inspiration from programming language design, where BNF has been a standard protocol, but its use as an intermediary form for DSL generation was never unexplored in the machine learning and natural language processing literature (to the best of our knowledge). Moreover, by generating specialized grammar and programs constrained to the grammar, we can effectively detect the compliance of the program to the grammar, and potentially provide a diagnosis on the validity of the generated program. While chain-of-thought prompting generates the intermediate “thought”, the validity of the answer cannot be directly verified from the “thought” process.  \n\n> Improvements over simple prompting methods are validated, but whether the method can beat more sophisticated algorithms (e.g., the recent tree-of-thought reasoning [3]) is unknown.\n\nThe problem that our grammar prompting method targets are those with a combinatorial output space characterized by domain-specific grammars. Although the \"tree-of-thought\" approach is gestured toward broad problem-solving capabilities, instantiating it for more complex search challenges is nontrivial. For instance, grammar prompting employs the Earley algorithm for efficient traversal and potential backtracking within the search space. In comparison, naive usage of BFS or DFS in the tree-of-thought would require a significantly higher number of LLM calls for exploration and backtracking. And please kindly note that the preprint of the tree-of-thought reasoning paper was released after the NeurIPS deadline.\n> The proposed constrained generation method is applied at the sub-sentence level, instead of the token level. Besides, the idea of constrained decoding has been explored in previous works [e.g., 1,2], which in turn challenges the novelty of this paper.\n\nGenerating specialized grammar and constrained programs at the sub-sentence level is a major strength of our work, instead of a limitation. Prior studies typically assume unrestricted access to smaller models (e.g., NMT models in 1), whereas our approach focuses on scenarios with limited and costly access to much larger blackbox models like GPT-3.5 and Codex. Constraining at the sub-sentence level can significantly reduce the number of LLM calls, thereby reducing the associated costs of employing LLMs.\n\nThe constraints discussed in [2] are much simpler than the DSL constraints we specify using context-free grammars. And unfortunately, their constrained decoding cannot generalize to problems examined in this paper.\n\nThank you again for bringing to our attention that we can make our contributions and novelty clearer. We will make sure to include the above discussions in the paper. We also really appreciate the pointers to the related work and we will cite in the paper.\n"}]

Author rebuttal:
We appreciate all reviewers' time and efforts in reviewing our paper. We are glad to find that reviewers generally recognized our key contributions and clear presentation of our paper:

**Method**: “The approach is elegant and seems simple to implement” [rfkj], “Novel method for prompting and constraining LLM generation using BNF grammar.” [pwxh], “This work is an efficient prompting generation algorithm for LLM.” [qhz7], “A simple and effective method was presented,” [8y4i]

**Experiment**: “The experiments are thorough, with strong results across a range of tasks and datasets.”[rfkj], “Strong experimental results.” [pwxh]

**Presentation**:  “The paper is very clearly written” [rfkj], “The method is described clearly” [pwxh], “The paper is well-written and easy to follow.” [8y4i], “This paper is interesting and well-written.” [qhz7]

Also, we thank all reviewers for their valuable and constructive suggestions. We reply to each reviewer individually below.


Meta-review: The paper considers few-shot prompting. It demonstrates that using a specialized grammar (under which the correct output can be generated) as an intermediate step instead of natural language thoughts can yield an improvement on domain-specific text generation such as semantic parsing, planning, and molecule generation. The paper develops a novel scheme for constrained decoding based on an Earley parser. The improvement is very clear. The reviews are mainly positive and the authors' response is adequate. The paper, as in the case with many papers on prompting, does come with a certain risk of being model-specific (i.e., results are tied to specific LLMs) and in this case domain-specific, thus arguably narrow in scope. But under the risk, the results are sufficiently positive to justify an acceptance.
Decision: Accept (poster)