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.
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.
The 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.
The 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.
A few details could be made clearer, if space is available, see below.
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?
Q2) Which Codex model is being used in the experiments here?
Minor clarification questions/points (don't need to address in author response):
- Be more consistent with the bolding of numbers in results tables, e.g. in Table 5
- The limitations mentions a lack of improvement for regexes, were these in experiments not reported in this paper?
- I didn't fully understand the Macro experiments on the PDDL tasks (although I did not check the appendix carefully).
- spelling of "conditioned" in Fig 2 caption
- 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
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The paper's limitation section did a good job, I think.
One 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.