Compositional Semantic Parsing with Large Language Models
Authors: Andrew Drozdov
Nathanael Schärli
Ekin Akyürek
Nathan Scales
Xinying Song
Xinyun Chen
Olivier Bousquet
Denny Zhou
Venue: ICLR 2023 poster (2023)
Keywords: large language models
prompting
compositional generalization
natural language processing

Abstract: Humans can reason compositionally when presented with new tasks.  Previous research shows that appropriate prompting techniques enable large language models (LLMs) to solve artificial compositional generalization tasks such as SCAN. In this work, we identify additional challenges in more realistic semantic parsing tasks with larger vocabulary and refine these prompting techniques to address them. Our best method is based on least-to-most prompting: it decomposes the problem using prompting-based syntactic parsing, then uses this decomposition to select appropriate exemplars and to sequentially generate the semantic parse. This method allows us to set a new state of the art for CFQ while requiring only 1% of the training data used by traditional approaches. Due to the general nature of our approach, we expect similar efforts will lead to new results in other tasks and domains, especially for knowledge-intensive applications.

Published as a conference paper at ICLR 2023
COMPOSITIONAL SEMANTIC PARSING WITH LARGE LANGUAGE MODELS
Andrew Drozdov 12
Nathanael Schärli''
Ekin Akyürek!.
Nathan Scales'
Xinying Song'
Xinyun Chen'
Olivier Bousquet'
Denny Zhou'
'Google Research UMass Amherst CICS
MIT CSAIL
"Equal contribution
ABSTRACT
Humans can reason compositionally when presented with new tasks. Previous re- search shows that appropriate prompting techniques enable large language mod- els (LLMs) to solve artificial compositional generalization tasks such as SCAN. In this work, we identify additional challenges in more realistic semantic pars- ing tasks with larger vocabulary and refine these prompting techniques to address them. Our best method is based on least-to-most prompting: it decomposes the problem using prompting trapting--asedddd based syntactic parsing, then uses this decomposition select appropriate exemplars and to sequentially generate the semantic parse. This method allows us to set a new state of the art for CFQ while requiring only 1% of the training data used by traditional approaches. Due to the general nature of our approach. we expect similar efforts will lead to new results in other tasks and domains, especially for mnowledge-intensing applications.
INTRODUCTION
Compositionality is a key part of human intelligence as it allows us to understand and produce a po- tentially infinite number of novel combinations of known components (Chomsky) 1957, Montague 1970 Lake et al. 2017). In contrast, standard neural sequence models, transformers and recurrent neura networks, often fail to capture the compositional structure of the problem domain and thus fail to generalize compositionally (Keysers et al. 2020 Furrer et al. 2020).
Prior efforts to improve compositional generalization primarily rely on specialized architectures or training procedures (Lake 2019 Chen et al. 2020 Nye et al. 2020: (Andreas 2020 Conklin et al.) 2021 Akyürek et al. 202 Liu et al. 2021) ). Although effective, these can be task-specific. Even more general purpose methods that rely on data augmentation are limited in the class of data it can support (Shaw et al. 202 Qiu et al. (002a)). Prompting on the other hand is sufficiently flexible and, with recent ad advancement of large-scale pretrained language models (LLMs), has become an effective and generic approach to address a wide range of language understanding problems (Brown let al. 2020). Prompting now performs on-par better than model finetuning in many cases (Wei
et al. 2022b Chowdhery et al., 2022: Wei et al. 2022a| Kojima et al., 2022 Ahn et al. 2022). and might be suitable for improving language model performance on compositional generalization.
In particular, recent work (Zhou et al. 2022) found that least-to-most prompting shows a lot of
potential for adapting LLMS for compositional generalization, achieving 99.7% accuracy on SCAN, a commonly used compositional generalization benchmark. Least-to-most prompting decomposes each problem into a series of subproblems, then sequentially solves one after another. However, SCAN is an artificial task built upon a synthetic language with tiny vocabulary and is generated from small set of grammar rules, and it is unclear whether strong results transfer more realistic tasks that are based on a larger vocabulary and more complicated grammars (Furrer et al. 2020).
Additional challenges arise when applying least-to-most prompting to more realistic semantic pars- ing benchmarks. Among others, they may require information beyond what fits in single prompt. Also, decomposing a problem is more difficult than with SCAN, exacerbated by constituents that cannot be translated independent of their context. We address these challenges with dynamic least- to-most prompting. a generic refinement of least-to-most prompting that involves the following steps: (1) tree-structured decomposition of natural language inputs through LM-predicted syntactic pars- ing, (2) using the decomposition to dynamically select exemplars, and (3) linearizing the decompo- sition tree and prompting the model sequentially generate answers to subproblems.

---

Published as a conference paper at ICLR 2023
We evaluate approach two realistic benchmarks that, like SCAN, designed to measure compositional generalization: CFQ (Keysers et al.] 2020) and COGS (iim & Linzen 2020). On CFQ. our best performing method outperforms previous fully supervised finetuning approaches and achieves a new state-of-the-art accuracy of 95% (averaged across MCD splits) and thereby reduced the error rate by about 45% compared to the previous best result while using about 1% of the training data as candidates for exemplars. On COGS, our approach scores an accuracy of 99.2% when evaluated on the generalization test set, comparable with strong baselines. We also demonstrate robustness of our approach to exemplar pool size, and when using less than 0.1 % of the training data as exemplars, dynamic least-to-moss prompting is still competitive with previous approaches.
2
BACKGROUND AND MOTIVATION
2.1 COMPOSITIONAL GENERALIZATION
Compositionality is the idea that the meanings of complex expressions are constructed from from the meanings of the less complex expressions that are their constituents. -Fodor & Lepore 2002
Given the knowledge of conceptual primitives and a few combinations, compositional generaliza- tion is the capability to use and comprehend unseen combinations. SCAN (Lake & Baroni 2018) Loula et al., 2018)) is one of the earliest benchmarks that shows neural sequence models cannot sys- tematically generalize to novel combinations of the primitive items of the language. The benchmark requires the learner translate simple commands to action sequences, where commands are generated from set of 20 grammar rules and use a vocabulary consisting of about 20 words.
Recent work has achieved perfect generalization accuracy on SCAN by inferring grammar rules in symbolic form (Chen et al.) 2020 Nye et al.) 2020 Liu et al.) 2020) [hha al. (021). Most recently, Zhou et al. (2022) demonstrate that SCAN can be solved by least-to-most prompting, which leverages pretrained large language model (LLM) and prompt consisting of only 14 exemplars, which is less than 0.1 of the training data used by previous approaches.
2.2 LEAST-TO-MOST PROMPTING ENABLES COMPOSITIONAL GENERALIZATION
Least-to-most prompting teaches language model how to solve a complex problem by reducing set of easier subproblems. This is done by constructing prompt tells the language model how to decompose a problem into a list of subproblems, while the second type of prompt describes how sequentially solve the subproblems.
types of prompts. The first type of
As an illustration, consider the application of least-to-most prompting to SCAN. The decomposition of the input "look around right thrice and walk twice" yields the following subproblems: "look right", "look around right", "look around right thrice",, and "walk twice". Since SCAN commands are generated by a simple grammar of only 20 rules, this decomposition task can be performed using prompt consisting of only 8 decomposition exemplars.
This decomposition allows the translation of the original input to be produced sequentially rather than in one step (as would be the case with naive prompting). The first subproblem is translated by passing the language model a prompt context consisting of 14 simple translation exemplars followed by the command "look right". The model's answer is then appended to the prompt such that it is used as additional context when translating the next subproblem "look around right", etc.
Did M1 star M2, star MB, and star a director and editor { ?x0 edited ио ?x0 ext_directed MO
SELECT count (*) WHERE
M1 starred ?x0 M1 starred M2
M1 starred M3
What was produced by art director that MI and M2 employed SELECT DISTINCT WHERE ?x0 produced.by ?x1
7xl a art.director
MO employed 7x1 M1 employed 7x1 }
An example of semantic parsing problems in CFQ, where the input is sentence and the output its formal representation as a SPARQL query.
Figure I:
2

---

Published as a conference paper at ICLR 2023
2.3 LEAST-TO-MOST PROMPTING: LIMITATIONS AND CHALLENGES
While the performance of reast-to-most prompting on SCAN is impressive, it not clear whether and how the same technique can be applied to compositional generalization problems that are based on more realistic subset of natural language. In particular, we identified three challenges that are common for more realistic natural language tasks and need to be addressed in order to apply least-to- most prompting: (1) decomposition is more challenging, (2) the knowledge required for tramslation may be too large to fit into a single prompt, and (3) translation of constituents is context-dependent.
As we consider extending least-to-most to-toott to the more realistic data setting, we have two semantic parsing benchmarks in mind: CFQ (Keysers et al. 2020 and COGS (Kim & Linzen 2020
CFQ is a compositional semantic parsing task where natural language questions need to be translated into SPARQI. commands. Compared to SCAN, CFQ is based on much larger vocabulary well as more complex linguistic structures produced by a unification-based grammar (Shieber (203).. As result, CFQ has proven to be quite challenging for generic ML architectures such as transformers and LSTMs. Even with custom architectures, the best generalization accuracy is less than 91%, achieved by specialized architectures for compositional grammar learning (Liu et al. 202T
COGS is another semantic parsing task where natural language sentences need to be translated into a formal representation. As for CFQ and SCAN, the training data for COGS contains multiple sys- tematic gaps that can only be addressed by compositional generalization; these include new com- binations of familiar syntactic structures and familiar structures. While COGS proves be quite challenging for generic MI. architectures, the best specialized models achieve 99.7% accuracy (Qiu ctt al. 2022a).
Natural Language is Challenging to Decompose SCAN commands are constructed from eight distinct symbols with fixed precedence ("left", "right", "twice", "thrice", "opposite". "around", "and", and "after"). Roughly, the decomposition of SCAN statement resembles that of a mathe- matical expression with standard arithmetic operations. In practice, the decomposition for SCAN can be predicted by a language model using a simple prompt.
CFQ and COGS sentences represent richer subset of natural language, meaning the various com- ponents and their interactions involve grammatical features such as different parts of speech, gram- matical voice, conjunctions, and pronouns. This makes decomposition much more challenging it requires deep understanding of the underlying linguistic structures.
Single Prompt Insufficient to Represent Full Label Space In the case SCAN, the knowledge needed to translate command into a sequence of actions is small enough that it can be captured with about a dozen examples. This is not the case for more realistic semantic parsing problems. For example, CFQ uses more than 50 different Freebase types and relations, and we cannot really expect the model to know the names of those relations without seeing them used in examples. Similarly, COGS uses hundreds of verbs, and their translation depends on details such as whether or not verb is unaccusative or unergative, which are difficult or impossible to determine without seeing corresponding translation examples.
Constituent Translation is Context-Dependent Least-to-ment most prompting has only been applied to domains where constituents can be translated independent of their context. The context-free na- ture of those tasks enables smooth derivation of final output from the solutions to the subproblems. As illustration of the context-free nature of SCAN, consider the expression "walk twice", which always translates to "WALK WALK". The constituents CFQ cannot be translated independent of their context. This is exemplified by the two sentences in Figure I In one, the expression "a art director" translates to "7x0 art directed MO", but translates to "?xl a art director" the other.
As will detail in the next section, this means that we cannot use the traditional approach for least- to-most prompting, where we first ask the model to translate each subproblem in isolation. Instead, need to make sure that the subproblems are provided to the model with enough context.
3

---

Published as a conference paper at ICLR 2023
Problem Reduction (Syntactic Parsing)
What produced art director that and M2 employed and was directed by M3
What was produced by director) that (M1 and M2) employed and was directed by (M3)
LM
What was produced by N1 that N2 employed and was directed by N3
What was produced by (N1 that (N2 employed)) and was directed by
Dynamically Select Exomplars for Each Subproblem
Relrieve using comeliluent from decomposiionn
Selecied exempler
Exemplar
M1 and M2 employed
Who editd film that M1 and M2 produced
Pool
Sequentially Subproblems
Exxemplars
Output
Q: Who edited film that M1 and M2 produced
LM
A: SELECT DISTINCT WHERE { produced ?xt. ?x1 director. M1 employed ?x1 M2 employed ?x1 7x0 directed_
A: <Exemplar Answer? ...
Subproblems
Q: What was directed by M3
A: <Predicted Answer?
was produced by an that M1 and M2 employed and was directed by MB
Figure 2: Our application of least-to-most is similar to Zhou et al. (2022) with the differences that obtain the "problem reduction" via multi-step syntactic parse of the input, and we dynamically select exemplars from fixed pool such that they collectively demonstrate as many parts of the decomposition possible.
DYNAMIC LEAST-TO-MON PROMPTING
In this section, introduce dynamic least-to-most prompting, which is extension of least to most prompting that allows us to overcome the challenges stated above and consequently apply least-to-men prompting more realistic natural language tasks.
We start by giving high-level summary of this approach, which outlined in Figure 2
1. Decomposition using LM-hased syntactic parsing. We series of prompts teach the language model to perform a syntactic parse of all possible input sentences. This pro- vides us with a tree-based decomposition rather than a linear decomposition obtained by traditional least-to-most prompting.
2. Dynamic selection of exemplars based on the decomposition. We sample a small subset of the training set as a pool of candidate exemplars. For each new input sentence to process, we dynamically select exemplars from this pool such that they collectively demonstrate relevant knowledge needed to translate the input sentences. This is done by matching the decomposition tree of the input against the decomposition tree the candidate exemplars.
3. Sequential solution based on the decomposition. We use the tree-based decomposition of the input sentence to generate a linear sequence of other relevant simpler sentences. We then construct prompt including the dynamically selected exemplars and use sequen- tially predict the solutions for the simpler sentences before generating the final output.
3.1 DECOMPOSITION USING LM-BASED SYNTACTIC PARSING
discussed in Section decomposition is more challenging for realistie tasks such as CFQ and COGS than for artificial tasks like SCAN. Indeed, while decomposing SCAN commands is similar to decomposing mathematical expressions with standard arithmetic operations, decomposing sentences corresponding to more realistic subsets of natural language essentially becomes problem of syntactic parsing. We find it natural to decompose problems using a tree structure guided by that syntax (see Figure
To teach LMs to perform decomposition, we divide the syntactic parsing task into multiple steps, such subclause identification, noun phrase identification, verb phrase identification, phrase
4

---

Published as a conference paper at ICLR 2023
What (was produced by ((a director) that (M1 employedj) and (was directed M3))
What (was produced by ((a art director) that (M1 and M2 employed)))
What (was directed by M3)
What (was produced by (a art director))
What (was produced by ((a art director) that (M1 empleyed)))
Figure 3: Syntactic parse of CFQ input and its decomposition into subproblems. Like the input, the subproblems are well-formed sentences.
notation, and verb normalization. For each step, we provide the LM with exemplars that illustrate the task to be performed." 1.2 See Appendix A.1 and Appendix B.1 for detailed description of the decomposition process and prompts used for CFQ and COGS, respectively.
3.2 DYNAMIC EXEMPLAR SELECTION
Prompt size is limited, so rather than attempt to represent all relevant knowledge in single prompt, for each input we dynamically select set of relevant exemplars from a pre-selected exemplar pool.
Choosing the exemplar pool. The exemplar pool is typically a small subset of the available train- ing data. The knowledge required for CFQ is rich and diverse, so we randomly sample 1000 exem- plars from the training data for this purpose (separately for each split). For COGS, it is important include in the exemplar pool translations of as many different verbs and verb phrases as possible. Therefore, we selected from the training data exemplar for each unergative and unaccusative verb, as well as 3 examples for each type of verb phrase (e.g., active, passive, with and without recipient, etc.). This resulted in relatively small exemplar pool consisting of only 89 exemplars (which is used in addition to a static context consisting of 28 exemplars).
Selecting exemplars. The goal of exemplar selection is to provide the LLM with the most relevant information needed to process given input sentence. We do this by making sure that as many nodes possible of the decomposition tree of the input covered by the decomposition trees of the selected exemplars. Specifically, we perform the following bottom-up and top-down matching.
Top-down matching: We begin by anonymizing the decomposition tree of the input. For instance, the example "What was produced by a art director that MI and M2 employed" anonymized to "What V N that M and M V where V stands for verb, N for noun, and M for entity. Starting at the top of the anonymized tree, we use a heuristic approach to find exemplars such that all nodes covered, prioritizing exemplars that match large subtrees.
Bottom-up matching: Then, we try to make sure that all leaf phrases are covered by an ex- emplar. If there is more than exemplar for certain phrase, prefer exemplars where the phrase occurs within a similar anonymized subtree. For instance, for the phrase "MI and M2 employed" (which anonymizes to "M and M V"), would prefer an exemplar containing "M1 and M2 produced" over both "art director employed" and "directed by M1 and M2".
Depending on its complexity, we select for each input between and 35 exemplars for CFQ and between and 3 exemplars for COGS. Full details of the anonymized tree and our heuristic matching algorithms are in Appendix A.2 for CFQ and Appendix B.2 for COGS.
'To better handle compositionality of the input sentences. some prompts may be applied iteratively. For prompt that extracts
instance, sentences in COGS have up 12 nested that-clauses. Therefore, the outer-most that-clause and apply this prompt until all those clauses identified.
'Because of a lack of golden data, we did not directly evaluate syntactic parsing. However, manual inspec- tion reveals desirable outputs for both CFQ and COGS, which speaks for the ability of LMs perform syntactic parsing when the task is broken down into individual steps that illustrated with appropriate prompts.
5

---

Published as a conference paper at ICLR 2023
Chain-of-Thought
Dynamic Least-to-Most
Input
Subproblems
Q: What produced by an art director that
Q: What was directed by M3
M1 employed and was direcctd by M3
A: <Predicted Answer?
Intermediate Steps
Q: What was produced by an director
A: <Predicted Answer>
Type:
1. There DISTINCT
art director (?x1) that produced ?x0 ?ax1 a art director, ?x0 produced by ?xt
Input
2. ?x1 employed by M1 M1 employed ?x1 ?xx directed by
Q: What was produced by an director that employed and directed by M3
?x0 directed_ by
[Output
Output
A: SELECT DISTINCT WHERE
A: SELECT DISTINCT WHERE { ?x0 produced by ?x1 employed ?x1 ?x0 directed by M3
?xx0 produced by ?x1. ?xt art art__ddieee director. employed ?x1 ?x0 directed by M3)
director.
Prompt designs for semantic parsing. Chain-of-thought (left) generates intermediate steps before the final output. Dynamic least-to-most (right) first sequentially predicts solutions to subprob- lems before generating the final output- the subproblems extracted through separate prompt.
Figure 4:
3.3 SEQUENTIAL SOLUTION
This is similar the solution step for traditional least-to-most prompting. The main difference is that we cannot translate the constituents in isolation because they might not be well-formed sen- tences and their translation is context-dependent Instead, linearize the decomposition tree into sequence of increasingly complex subproblems and sequentially predict their solutions.
In Figure 4, we show barebones snapshot of dynamic least-to-man most prompting, immediately before predicting the final output. In previous steps, the model predicted via prompting the solution to the first subproblem, "What was directed by M3", then appended the prediction the prompt before proceeding with. "What was produced by an art director", etc. Not displayed in the figure are dynamically selected exemplars and fixed list of partial exemplars that we prepend to each prompt.
BASELINE: PROMPTING WITHOUT DECOMPOSITION
To demonstrate the effectiveness of dynamic least-to-most prompting, we compare against a strong prompting baseline called chain-of-thought prompting (Wei al. 2022b). Chain-of-thought gener- ates intermediate steps before predicting the final answer and has been shown to improve reasoning capabilities of language models. Unlike least-to-mosi prompting, chain-of-thougl! does not have decomposition step, potentially limiting its effectiveness for compositional generalization tasks.
4.1 CHAIN-OF-THOUGHT PROMPT DESIGN
Our Shain-of-thoughe prompt is shown in Figure It first categorizes the query, then generates quasi-alignments between the text and output statements. This represents synchronicity in the same spirit as other higher performing semantic parsers do (Qiu et al., 2022a), but the intermediate con- stituents and clauses need not map exactly to what is seen in the input and output. The flexibility of chain-of-thought is convenient for data like CFQ where inclusion of variables is not compatible with synchronous grammar training and inference (Wong & Mooney 2007).
4.2 DYNAMICALLY SELECTING EXEMPLARS BASED ON LEXICAL SIMILARITY
Since there is no decomposition with chain-of ofain-of-thought, we rank exemplars by bag-of words simi- larity with the current sentence. To reduce redundancy, we select exemplars one by one, and at each iteration prioritize exemplars with relevant words that have not been found yet. This approach not deterministic-icc. selecting different exemplars in the first iteration can alter results. In prac- tice, when using chain-of offin--f-thuugh we find it is helpful to sample multiple exemplar lists, then use
A partial exemplar is generic and represents fundamental language phenomena (see Appendix A.3.1 Complete details of the prompts for dynamic least-to-most AppendicesAA.3 (CF( and B.3 (COGS).

---

Published as a conference paper at ICLR 2023
temperature- based decoding sample multiple predictions per list, and finally aggregate predictions
by plurality vote using selfscooni [Wang et al. 2022: Shi et al. 2022 ct al. 2022
EXPERIMENTS AND RESULTS
5.1 DATA
Datasets. We empirically measure the effectiveness of prompting on two semantic parsing datasets. CFQ (Keysers al., (020) has three maximum compound divergence splits (MCDI, MCD2, MCD3) for measuring compositional generalization, each with 95743/1 1968/1 1968 sen- tences in their train/validation/tess splits, COGS (Kim & Linzen 2020) has 24155/3000/21000 sentences in their train//alidatton/eeerraizzzzziz splits.
Exemplar pools. Also described in Section 3.2 For each CFQ split, we sampled 1000 training examples to use as potential exemplars (about 1% of the training data). For COGS, we manually selected 89 training examples as potential exemplars (about 0.4% of the training data).
Preprocessing. For CFQ replace freebase identifiers with human-readable strings.* We also remove clauses that are redundant from prediction perspective, which always appear alongside the same properties in both train and evaluation data. For COGS use the variable- free and equivalent outputs introduced by Qiu et al. (2022a). See Appendix D for details.
Evaluation. We measure accuracy using exact match (EM). This is computed as exact string match between ground truth and predict labels, and no partial credit assigned. To make this metric interpretable for CFQ apply normalization to outputs, including sorting properties and applying a deterministic argument ordering (additional details in Appendix D.1.2). For COGS we add any missing closing parentheses the end of the output before computing EM.
5.2 EXPERIMENTAL DESIGN CHOICES
The number of exemplars used in dynamic least-to-most varies based on the complexity of the decomposition tree, does the number of subproblems. Predictions are made with greedy decoding. Since there is single final output, no self-consisteng is needed.
To improve performance with vanilla few-shot prompts (simple input/output exemplars) and chain- of-thought prompts, we sample = 4 different exemplar lists (each consisting of k = 15 exem- plars), then sample 8 outputs per list using temperature-base decoding, yielding n 16 outputs that are aggregated with self-consistency."
We use code pode--davinci-000 hosted by OpenAl for all experiments described in this paper. This is version of InstructGPT (Ouyang et al. 2022) finetuned on code, referred to Codex." Hyperpa- rameters are summarized in Appendix D.3
5.3
RESULTS
Our main results are on CFQ test splits and are reported in Table Not only does this show that prompting enables compositional generalization on a realistic natural language task, dynamic ceast-to-most sets state of the art (95.0% accuracy) while only using about 1% of the training data, whereas traditional approaches are fully supervised.
CFQ
luman-rredabbe We manually mapped 52 properties to a human readable form, which took about one hour to complete. This heavily relies on the original ID, and results in properties that are more feasible to predict. For example, mapping ns : :iimm. f www.rrttdiiettorooooooo
films .art.dd siri.iiree directte ed to
Any specialized preprocessing and evaluation steps we take for CFQ are tailored for prompting and are not necessary for fully supervised training. In order to verify this, we reproduced experiments with ba-base using our same preprocessing and evaluation. The results match previously published exact match within 1-2 points MCDI, MCD2, and MCD3. COGS does not require such steps.
Vaaiilla few-shot and chain-of -hthoughtt "We use code-hased model hecause it outperformed text-based GPT-3 in early experiments. Similar observations have been made in prior work semantic parsing (Shin et al. 2021 Shin Van Durme
worse without self-consistency (see results in Appendix
R.3
2022

---

Published as a conference paper at ICLR 2023
MCD1
MCD2
MCD3
Ave.
Fully Supervised
T5-base
58.5
27.0
18.4
34.6
Vanila Few
T5-large
65.1
32.3
25.4
40.9
Chain-of Thouggh
T5-3B
65.0
41.0
42.6
49.5
Dynamic L2M
HPD
79.6
59.6
67.8
69.0
100
Accuracy (%) on CFO
T5-base IR
85.8
64.0
53.6
67.8
T5-large + IR
88.6
79.2
72.7
80.2
T5-3B IR
88.4
85.3
77.9
83.9
70-
LeAR
91.7
89.2
91.7
90.9
Prompting (Ours) Dyn. 1.2M
200
1000
94.3
95.3
95.5
95.0
Exemplar
Table 1: Test accuracy across the MCD splits for the CFQ
Figure 5: Comparing prompting methods and ablating across ex- emplar pool size.
dataset. T5: Herzig et al. (202I). HPD: Guo et al. (2020),
LeAR: Liu et al. (2021).
Gen.
MCD1
Fully Supervised
Dynamic Least-to-Most
94.6
LeAR (Liu et al. 2021
97.7
Using BoW Exemplars
92.2
T5-base (Quu et al.
2022a
89.8
Using Constant Exemplars
76.4
T5-base + CSL QQu et al.
2022a
99.5
50% Decomposition
88.8
Prompting
2-Step Decomposition
83.2
(Ours) Dynamic Least-to-Most
99.2
No Decomposition
75.2
Accuracy COGS generalization The COGS data is not SQL-like, and has a more diverse lexicon compared with CFQ.
Table 2:
Table 3: Ablating exemplar selection and decomposition for dynamic ceast-to-moss
COGS We experiments COGS with minimal changes approach (Table 2 even though the output space is quite different from CFQ. Dynamic least-to-most prompting scores 99.2% accuracy (using 0.4% of the training data), reinforcing the generic nature of approach.
DISCUSSION AND ANALYSIS
Comparison of prompting methods In Figure vanilla few-shot prompting and chain-of-thought prompting (CoT) enhanced with self-consistency. We measure performance outperforms vanilla (80.8%) and most baselines when extrapolating to the full data, but L2M (94.6%) achieves the best result.
compare dynamic least-to-most (L2M) with
random 500-sentence subset of CFQ's MCD1 test split. CoT (87.2%)
1.2M is both more accurate and more efficient than other prompting methods. 1.2M performs favor- ably across different sizes of the exemplar pool. It is also 2x as fast as CoT despite its sequential nature, since CoT uses self-consistency across multiple exemplar lists and outputs. Without self- consistency, CoT accuracy drops from 87.2% to 75,4% and vanilla drops from 80.8% 69.8%.
Exemplar selection and question decomposition In Table 3 we ablate configurations for dy- namic least-to-most. We measure performance on a random 500-sentence subset of CFQ's MCD1 test split. Performance drops from 94.6% to 92.2% when selecting exemplars according bag-of-words (BoW) algorithm or to 76.4% when using a fixed set of exemplars for examples.
Both exemplar selection and question decomposition are crucial for the best L2M performance. L2M uses a different number of decomposition steps per example. If we reduce the amount of decomposition half as many steps then performance drops 88.8%, or 83.2% when doing most two steps. we skip decomposition entirely then performance drops further to 75.2%. See Appendix E.2 for more ablations together with qualitative analysis of the associated error..
8

---

Published as a conference paper at ICLR 2023
Risk of memorization For pretrained models, leakage of the test data is a potential concern (Kr- ishna et al., 2020 Carlini et al., 2021). However, given the inferior performance of vanilla few-shot prompting, attribute success of prompting to in-context learning rather than memorization. Fur- thermore, least-to-most prompting requires the LM to translate as intermediate steps new subprob- lems that are guaranteed to be unseen during training.
7 RELATED WORK
Compositional generalization Compositional generalization in machine learning has been chal-
lenging problem that attracts attention across fields, including vision (Johnson et al. [017 Bahdanau
et 2al.(2019) Ruis et al.] [2200] Nikolaus al.) (2019) and language domains (Lake & Baroni 2018
Keysers et al. [020] Kim & Linzen 2020 Shaw et al. [022 Yin et al.) 2021; Gan et al. 2022). A
number of approaches have been proposed improve compositional generalization on SCAN (Lake
& Baroni
2018 Loula et al., 2018), including specialized design of neural model architectures
[Chen et al. 2020; Nye et al.) 2020 Liu et al., 2020. Shaw al., [021]] Russin al., [2019] Li
ct al.
2019: Gordon et al. 2020 Herzig& & Berant [2021] and training algorithms (Lake) [2019] Kim
2021
training data augmentation (Andreas) 2020, Akyürek et al. (202T). and prompting (hou
et al.
2022). While 100% accuracy has been accomplished on SCAN (Chen et al. 2020 Nye
cct al., 2020; Liu et al., 2020; [haaw et al. 2021), good performance on SCAN does not necessarily transfer to more challenging compositional generalization problems (Furrer et al. (2220). Notably, although least-to castt prompting has achieved 99.7% accuracy on SCAN (Zhou et al. (2022) ) prior attempts on prompting for semantic parsing still demonstrate limited compositional generalization performance (Qiu et al. 2022b). In this work, we propose prompting schemes to bridge this gap.
To improve compositional generalization for semantic parsing, recent works incorporate latent syntactic component (Qiu et al., [022a] Liu et al. [202]]. Similarly to symbolic grammar learn- ing techniques on SCAN, these approaches achieve impressive performance on several benchmarks, and represent the previous state of the art on CFQ (Keysers et al. (2220) and COGS (Kim & Linzen, 2020). Other lines of work improve the performance on CFQ through specialized decoding algo- rithms, including graph decoding (Gai et al. 2021) and hierarchical poset decoding (Guo et al.) 2020). Yet others exploit correlations between the input and output tokens, e.g. through loss func- tions with attention supervision (Yin et al. 2021 using lexicon (Akyürek & Andreas (021), and reformulating the label space (Herzig et al., 202T). Without relying on specialized model ar- chitectures or training algorithms, our results demonstrate generic prompting schemes based on decomposition demonstrate strong results on CFQ and COGS, and achieve state-of-the-ar results on CFQ.
Prompting The most similar work to ours is SeqZero YYang et al., 2022), but there are key dif- ferences. SeqZero decomposes semantic parsing into generating three parts separately (SELECT, FROM, and WHERE parts of the output), and further decomposes WHERE into generating each clause separately. This means that decomposition is conducted via a fixed, rule-based system. In contrast, our decomposition is automatically accomplished by prompting. We use the syntactic parse of the sentence to create different related sentences, such as by simplifying conjunctions or remov- ing text fragments. This is more general than SeqZero and it is readily applicable to many natural language tasks. For example, we successfully used our approach on COGS even though the output does not resemble SQL. Furthermore, SeqZero is an ensemble of finetuned BART and a zero-shot model, while we use only prompting with large language models and forego finetuning entirely.
8 CONCLUSION
Through dynamic least-to-mos most prompting, we demonstrate state-of-the-art performance on diffi- cult natural language semantic parsing benchmark that measures compositional generalization. Our results are achieved using about 1% of the training data from traditional finetuning approaches. Many machine learning models struggle with compositional generalization, and our findings should facilitate future research that enables this capability through task decomposition. We expect dynamic least-to-man most prompting to have immediate impact in variety of settings. It is flexible and general purpose, enabling quick adaptation to new tasks and domains, especially for knowledge-intensin applications of language models, where precise semantic parsing can be directly leveraged.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
Throughout our work we aim to provide exhaustive details about prompt design and exemplar selec- tion, and we include all the prompts we use in the Appendix. To ease future use, we further outline key details related to reproducibility in Appendix
REFERENCES
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho. Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan. Eric Jang, Rosario Jauregui Ruano, Kyle Jefffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang. Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Mengyuan Yan, and Andy Zeng. Do as I can, not as I say: Grounding language in robotic affordances. arXiv preprint, 2022. URL https: /tctts://azxivi org/ awt.ab/s/22// 01691
Ekin Akyürek and Jacob Andreas. Lexicon learning for few shot sequence modeling. In Proceed- ings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp. 4934-4946, Online, August 2021, Association for Computational Linguistics. doi: 18.18653/v1/ 2021.acl-long.382 http://tsa.///aaaaaoooooo.o..o.p
Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning to recombine and resample data for compositional generalization. In International Conference on Learning Representations, 2021.
Jacob Andreas. Good-enough compositional data augmentation. In Annual Meeting of the Associ- Online, July 2020. Association for Compu-
ation for Computational Linguistics. pp. tational Linguistics. doi: 10. 00.18653/v1/20200 acl main.676. URL httttpss//aclaathholo...
org/ otgg/202..coo 20200.001 676
Dzmitry Bahdanau, Harm de Vries, Timothy J O' O'Donnell, Shikhar Murty, Philippe Beaudoin, Yoshua Bengio, and Aaron Courville. CLOSURE: Assessing systematic generalization of CLEVR models. arXiv preprint
2019,
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Πya Sutskever, and Dario Amodei. Language models few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell. M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URI. htttps://proceeeet/ee neur 1457c0d6bfcb4
neur i ps... httpppaarr2202//111
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voon Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Security Symposium, 2021. URL
https::/arxii. org/ abs 2012 2. 07805
Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. Compositional gener- alization via neural- soural-ymmollic stack machines. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 1690-1701. Curran Associates, Inc., 2020. URL httttttt//:/:reeeee: ngs nwwrips...... cc/ 222.2222222222222222222222222220
Paper.apeeeeeeeeeeeeeeeeeeeeeeee pdf.
Noam Chomsky. Syntactic structures. The Hague: Mouton, 1957.
10

---

Published as a conference paper at ICLR 2023
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao. Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang. Bren- nan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy
Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways. org/ abs 2204 02311
arXiv preprint, 2022. URL atttps://arze
Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. Meta-learning to compositionally gen- eralize. In Annual Meeting of the Association for Computational Linguistics, pp. 3335,,33,, On- line, August 2021. Association for Computational Linguistics. doi: 10.18653/v11200 1/266///12222.allllllll aacl-long. 258. URL aattps://aclantiiiin
2000 acl- acl-iong. 258
Jerry A. Fodor and Eresst Lepore. The compositionality papers. Oxford University Press, 2002.
Daniel Furrer, Marc van Zee, Nathan Scales, and Nathanael Scharli. Compositional generalization in semantic parsing: Pre-training vs. specialized architectures. ArXiv, 0oss/2007.08970 2020.
Yu Gai, Paras Jain, Wendi Zhang, Joseph Gonzalez, Dawn Song, and Ion Stoica. Grounded graph decoding improves compositional generalization in question answering. In Findings of the As-
sociation Computational Linguistics: EMNLP 2021, pp. 1829-1838, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/2011. 2021. http://221....n.......... findings- emnll...nseenn.....
URL https:: /aataa:://allanthooogo.oooo wwtp:/oy...............
157
Yujian Gan, Xinyun Chen, Qiuping Huang, and Matthew Purver. Measuring and improving com- positional generalization in text-to-SQL via component aligmment. In Findings of the Associ- ation for Computational Linguisties: NAACI. 2022, pp. 831-843, Seattle, United States, July 2022. Association for Computational L Linguistics. doi: 10.18653/ hing:22g2.inniinnnnaa...... URI. httpes//aalaantllooooo.oogg/////
findings naacl. 62
Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivari- ant models for compositional generalization in language. In International Conference on Learning Representations, 2020.
Yinuo Guo, Zeqi Lin, Jian-Guang Lou, and Dongmei Zhang. Hierarchical poset decoding for com- positional generalization in language. Advances Neural Information Processing Systems, 33: 6913-6924, 2020.
Jonathan Herzig and Jonathan Berant. Span-based semantic parsing for compositional generaliza- tion. In Annual Meeting of the Association for Computational Linguistics, 2021.
Jonathan Herzig, Peter Shaw, Ming- Wei Chang. Kelvin Guu, Panupong Pasupat, and Yuan Zhang. Unlocking compositional generalization in pre-trained models using intermediate representations. arXiv preprint
2021.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross Girshick. CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 29901-2910 10, 2017.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Mare van Zee, and Olivier Bousquet. Measuring compositional generalization: A com- prehensive method on realistic data. In International Conference on Learning Representations, 2020.

---

Published as a conference paper at ICLR 2023
Najoung Kim and Tal Linzen. COGS: A compositional generalization challenge based semantic interpretation. In Proceedings the the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9087-9105, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1 220.55////2000...mmmmmmmmiii 2020. emm.p-manmmmmm..m i 731
URL https: / ant.oo loyy org/
Yoon Kim. Sequence-to-sevye -equence learning with latent neural grammars. Advances in Neural Infor- mation Processing Systems, 34:26302-2633 2021.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In NeurIPS, 2022.
Kalpesh Krishna, Gaurav Singh Tomar, Ankur P. Parikh, Nicolas Papernot, and Mohit lyyer. Thieves on sesame street! model extraction bert-based apis. In International Conference on Learning Representations, 2020. URL URLnttps:
https: http://://e/peeereee..eeeteeetee http:////////tt//////e/eeeeeeeee www.:/eee//oouottteooeeo. htt.:e/tee/ooouuoooooo//1LL1EE.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In Jennifer Dy and Andreas Krause (eds.), Pro- ceedings of the 35th International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pp. 2882- PMLR, 10-15 Jul 2018. URL https:
//proceedings.. mlr www. wwwpppewsvvi... wwt.//00//aklaaa html
Brenden M Lake. Compositional generalization through meta sequence- learning. Ad- vances in neural information processing systems, 32, 2019.
Brenden M. Lake, Tomer Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman. Building machines that learn and think like people. Behavioral and Brain Sciences, 40:e253, 2017. doi: 1L1017/50140525516001111
Yifei Li, Zeqi Lin. Shizhuo Zhang, Qiang Fu, Bei Chen, GuanG Lou, and Weizhu Chen. On the advance of making language models better reasoners. arXiv preprint, 2022. URL https:
7/arxiv. o abs/ 2206 02336
Yuanpeng Li, Liang Zhao, Jianyu Wang. and Joel Hestness. Compositional generalization for prim- itive substitutions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 0284-4292 2019.
Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. Learning algebraic recombination for compositional generalization.
In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pp. 1129- 1144, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/0021 findings-acl.97 http:ttt:://acaaaaoooooog// org 2020 .inniings-accl..99
Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. Advances in Neural Information Processing Systems, 33:1 1416-1111011 1427, 2020.
João Loula, Marco Baroni, and Brenden Lake. Rearranging the familiar: Testing compositional generalization in recurrent networks. In Proceedings of the 2018 EMNLP Workshop Black- boxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 108-114, Brussels, Belgium, November 2018. Association for Computational Linguistics. doi: 10.18653/v1/W18. 14131 URL
Richard Montague. Universal grammar. Theoria, 36(3):373-398, 1970. doi: 10.1111/..755-2567 1970.tb0044.xx.
Mitja Nikolaus, Mostafa Abdou, Matthew Lamm, Rahul Aralikatte, and Desmond Elliott. Compo- sitional generalization in image captioning. In Proceedings of the 23rd Conference on Computa- tional Natural Language Learning (CoNLL), pp. 87-98, 2019.
Maxwell Nye, Armando Solar- Josh Tenenbaum, and Brenden M Lake. Learning compo- sitional rules via neural program synthesis. Advances Neural Information Processing Systems, 33:10832-10842, 2020.
12

---

Published as a conference paper at ICLR 2023
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kel- ton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. Training language models to follow instructions with human feedback. ArXiv, abs/2203.02155, 2022.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. Improving compositional generalization with latent structure and data augmenta- tion. In Proceedings of the 2022 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, pp. 4341 4362, Seattle, United States, July 2022a. Association for Computational Linguistics. doi: 00118865311/2222 naacl-main.323, URL ptttps://aclantholllo wwtp:/oggyyrg//22222///// http:/2222.aaacl.... naacc maiin. 323
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. ArXiv, abs/2205.12253. 2022b.
Laura Ruis, Jacob Andreas, Marco Baroni, Diane Bouchacourt, and Brenden M Lake. A benchmark for systematic generalization in grounded language understanding. Advances in neural informa- fion processing systems, 33:1 33:19861-19872 2020.
Jake Russin, Jason Jo. Randall C O'Reilly, and Yoshua Bengio. Compositional generalization in deep seq2seq model by separating syntax and semantics. arXiv preprint 19XXi::1904099788, 2019.
Peter Shaw, Ming- Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional general- ization and natural language variation: Can a semantic parsing approach handle both? In Annual Meeting of the Association for Computational Linguistics, 2021.
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang. Natural language to code translation with execution. arXiv preprint, 2022. URL https: org/abs/ 2204. 11454
Stuart M Shieber. An introduction to unification-based approaches to grammar. Microtome Pub- lishing, 2003.
Richard Shin and Benjamin Van Durme. Few-shot semantic parsing with language models trained on code. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5417-5425, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. 0e.1188661112222 1/2022. main. 396. http::///a// http///ccaaattoooogooooooo wr00 nwacc -ma 396
Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 7699-7715, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10. 10.18653/v12222 emnlp-main.60S. 6008.
orgg emn 1p-11p-mm-- ma- in..ninn.... 608
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ArXiv, abs/2203. 11171, 2022.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large lan- guage models. Transactions on Machine Learning Research, August 2022a. URL https: Survey Certification.
//openzeview. www.nneeoooommmdyaameeeemme
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Brian Ichter, Fei Xia, Quoc Le, and Denny Zhou Chain of thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35, 2022b.
13

---

Published as a conference paper at ICLR 2023
Yuk Wah Wong and Raymond Mooney. Learning synchronous grammars for semantic parsing with lambda calculus. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pp. 960-967, Prague, Czech Republic, June 2007. Association for Computational Linguistics. ht.ptt / ac antaaanooooo... www.thoooo..orro.....o.....o wtwp:/ogyooooo/11111110
Jingfeng Yang, Haoming Jiang, Qingyu Yin, Danqing Zhang, Bing Yin, and Diyi Yang. SEQZERO: Few-shot compositional semantic parsing with sequential prompts and zero-shot models. In Findings of the Association for Computational Linguistics: NAACL 2022, pp. 49-60, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/1/202.. maaiing-nnaccl5. URL https: http://aalaattt logy 2022. f Findiigg wwniinggg--ooeeooee nascnaaacl....
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. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp- 2810-2823, Online, June 2021. Association for Computational Linguistics. doi: 18.18633/v// 2021 maact1-miin.225. URL /ttpttss///ccaaatooooooy wwtp://1gg222000 naacl iataiin.225
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. Star: Bootstrapping reasoning with reasoning. arXiv preprint, 2022. URL
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schu- urmans, Olivier Bousquet, Quoe Le, and Ed Chi. Least-to-most prompting enables complex reasoning in large language models. ArXiv, abs/2205. 10625, 2022.
14

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
Least-to-most Prompting for CFQ
16
A.1
CFQ
Decomposition: Details and Prompts
16
A.1.1
Step I: Noun phrase identification
17
A.I.2
Step Subclause identification
A.1.3
Step Verh phrase identification
21
A.1.4
Step Part of speech tagging
25
A.1.5
Step 5: Verb normalization
28
A.2
CFQ Exemplar Sclection: Details
28
A.2.1
Top-down matching
29
A.2.2
Bottom-up matching
29
A.3
CFQ
Solution: Details and Prompt
30
A.3.1
Part 1: Static prompt context.
30
A.3.2
Part 2: Dynamically selected exemplary
31
A.3.3
Part 3: Sequential questions
33
Least-to-most Prompting for COGS
34
B.I
COGS Decompositio:: Details and Prompts
34
B.1.1
Iterative subclause decomposition
36
B.1.2
Phrase identification)
37
B.1.3
Iterative prepositional phrase decomposition and noun phrase annotation
38
B.1.4
Verb phrase normalization
41
B.2
COGS
Exemplar Selection: Details
42
B.2.1
Exemplar pool
42
B.2.2
Exemplar matching
47
B.3
COGS
Solution: Details and Prompts
47
B.3.1
Part I: Static prompt context
48
B33.2
Part 2: Dynamically selected exemplars
49
B.3.3
Part 3: Sequential subproblems
49
C
Chain-of-thought Prompting for CFQ
51
C.I
Bootstrap Prompt
51
Prediction Prompt
................................
53
D Data Preparation, Evaluation, and Hyperparameters
55
D.1 CFQ Processing and Evaluation
55
D.1.1 CFQ Preprocessing
55
D.I.2 CFQ Postprocessing and Evaluation
................................
55
D.2
COGS Postprocessing and Evaluation
................................
56
D.3
Hyperparameters]
56
D.3.1
Prompt Hyperparameters
56
D.3.2
Generation Hyperparameters
57
E
Additional Analysis
E.1
Initial Prompting Attempts for CFQ
57
E.2
Dynamic Least-to most Prompting CFQ: Ablations and Error Analysis
58
F..3
Fair Comparison against Other Prompting Techniques
60
F
Reproducibility Summary
60
15

---

Published as a conference paper at ICLR 2023
Which film editor was influenced by cinematographer that wrote and M5 and influenced by MI 's editor
SELECT DISTINCT ?x0 WHERE ?x0 filmeeditor
influenced.by ?x1
7x0 influenced_by ?x2 ?x1 edited M1 ?x2 cinematographer.
7x2 wrote M3 ?x2 wrote M4 7x2 wrote M5
Figure 6: CFQ example, which we use illustrate the application of dynamic least-to-most prompting to CFQ.
A LEAST-TO-MOST PROMPTING FOR CFQ
In this section, we provide more details on the application of dynamic least-to-most prompting for CFQ. In particular, we detail all the prompts and show how the example in Figure processed step by step.
A.1 CFQ DECOMPOSITION, DETAILS AND PROMPTS
As discussed in Section 3.1 we use prompting- based syntactic parsing to decompose CFQ questions. To teach LMs to perform this kind of decomposition, we divide the syntactic parsing task into the following steps:
1. Noun phrase identification
2. Subclause identification
3. Verb and other phrase identification
4. Part-of-speech tagging and phrase labeling
5. Verb normalization
Consider the question from Figure
Which film editor was influenced by a cinematographer that wrote M3, M4, and M5 and influenced by MI 's editor
The first step, noun phrase identification, yields:
Which (film editor) influenced by (a cinematographer) that wrote (M3, M4, and M5) and influenced by (MI 's editor)
Then, we replace the identified noun phrases with placeholders N1, N2, N3, and N4, which yields:
Which NI was influenced by N2 that wrote N3 and influenced by N4
The next step, subclause identification, uses the form with placeholders and yields:
Which NI influenced by ((N2) that (wrote N3)) and influenced by N4
Then we have another round of applying placeholders, on the subclause this time:
Which N1 was influenced by N5 and influenced by N4
The third step is to identify verb phrases and other miscellaneous phrases, which yields:
(Which) (N1) ((was influenced by N5) and (influenced by N4))
that (wrote N3)
As fourth step, we perform various part-of-speech tagging and phrase labeling. We start with the noun phrases, which yields:
16

---

Published as a conference paper at ICLR 2023
N=(film editor)
[a] N-ccinematographer))
M=(M3 M4, [and], M5)
M=(MI) P=('s) N=(editor)
We continue with verb phrases, which yields:
W=(Which)
V=[[as] influenced by) (N5)
(=iinlueenced by) (N4)
V=(wrote) (N3)
As fifth step, normalize all the verbs: "was" yields "be", "influenced" yields "influence", and "wrote" yields "write". Finally, we run few lines of Python code that puts all these parts back together to obtain a parse tree. Note that the normalized verbs do replace the original ones but are kept in addition, which allows us to obtain higher recall when selecting exemplars.
This yields the following fully decomposed and annotated question:
W=(Which) N=(film editor) ((V=([wa]] influenced by) ([a] N=(cinematographer) that (V=(wrote) N=(M3. M4 [and] M5)))) and (V=(influenced by) (M=(MI) P=('s)
N=(editor)))
Below, we present the exact prompt contexts used for each of the parsing steps.
A.1.1 STEP 1: NOUN PHRASE IDENTIFICATION
Q: Was MO 's producer art director 's sibling
A: Was (MO producer) (a art director sibling)
Q: Did M1 influence French producer and editor 's child 's spouse
A: Did (M1) influence (a French producer and editor child 's spouse)
Q: Which female French costume designer producer and editor of M3 and M4 was M5
parent
A: Which (female French costume designer, producer, and editor of M3 and M4) was (M5 parent)
Q: Was Dutch parent and spouse a editor, producer, and writer of a film 's prequel
A: Was (a Dutch parent and spouse) (a editor, producer, and writer of film prequel)
Q: Who employed met and was influenced by female film director 's Spanish parent and married M1
A: Who employed, met and was influenced by (a female film director 's Spanish parent) and married (M1)
Q: Were M3 and M6 executive produced by written by and directed by a writer 's spouse friend, and employer, and produced by a child A: Were (M3 and M6) executive produced by written by and directed by (a writer 's spouse, friend and employer). and produced by child)
Q: What film director and editor of M1 and M2 married divorced and was kissed by Spanish editor and producer of M5 A: What (film director and editor of MO M1 and M2) married. divorced and was kissed by (a
Spanish editor and producer of M5)
Q: Which child of production company did MO acquire
A: Which (child of production company) did (MO) acquire
17

---

Published as a conference paper at ICLR 2023
Q: Which star of M5 was influenced by person influenced by MO M1 M2 and M3 and influenced by M4 A: Which (star of M5) was influenced by (a person) influenced by (MO M1 M2 and M3), and influenced by (M4)
Q: Was a screenwriter employed by M1 M2 and M3 and employed by M4 M5 and M6 M7 spouse
A: Was (a screenwriter) employed by (M1 M2, and M3) and employed by (M4, M5 and M6) (M7 spouse)
Q: Was M4 produced by a German screenwriter that M1 and spouse of sibling were in- fluenced by
A: Was (M4) produced by (a German screenwriter) that (M1 and spouse of M2 sibling) were influenced by
Q: Was MO M1 sibling and spouse
A: Was (MO) (M1 is sibling and spouse)
Q: Which film did M3 's employer 's Mexican employee produce and M1 direct
A: Which (film) did (M3 employer 's Mexican employee) produce and (M1) direct
Q: Did M3 parent employee influence MO and M1 and influence M2 founder and em- ployee
A: Did (M3 's parent employee) influence (MO and M1) and influence (M2 founder and employee)
Q: What male director of M3 and M4 did MO and M1 influence
A: What (male director of M3 and M4) did (MO and M1) influence
Q: Which female person whose sibling was influenced by M3 and influenced by M4 and
M5 directed M2
A: Which (female person) whose (sibling) was influenced by (M3) and was influenced by (M4 and
M5) directed (M2)
Q: Did MO direct, produce, executive produce edit, and write M1 M2, and M3
A: Did (MO) direct, produce, executive produce edit, and write (M1 M2, and M3)
Q: Was MO executive produced by edited by written by and directed by M2 and
M3
A: Was (MO) executive produced by edited by written by and directed by (M1, M2, and M3)
Q: Who influenced and was influenced by M1 's female actor 's parent
A: Who influenced and was influenced by (M1 's female actor parent)
Q: Did MO 's editor, costume designer star writer and director executive produce and produce M1 A: Did (MO editor costume designer star writer and art director) executive produce and produce (M1)
Q: Which film that was written by M1 M2 directed
A: Which (film) that was written by (M1) (M2) directed
Q: Which director of M3 M4 and M5 was a Japanese screenwriter that M1 employed and was founded by A: Which (director of M3, M4 and M5) was (a Japanese screenwriter) that (M1) employed and was founded by
Q: Did M1 executive producer employ M2 edit M3 employ a film director and employ M4
A: Did (M1 executive producer) employ (M2). edit (M3). employ (a film director). and employ (M4)
18

---

Published as a conference paper at ICLR 2023
Q: Was a film whose star writer cinematograaherr and executive producer executive pro- duced, edited, and wrote MO M1
A: Was (a film) whose (star, writer, cinematographer, and executive producer) executive produced edited and wrote (MO) (M1)
Q: Was M1 film that MO 's editor distributed
A: Was (M1) (a film) that (MO editor) distributed
Q: Was M1 child of a production company 's parent and child
A: Was (M1) (a child production company 's parent and child)
Q: What did a director that M1 influenced and M2 influenced write
A: What did (a director) that (M1) influenced and (M2) influenced write
Q: What was written by MO 's art director and executive producer
A: What was written by (MO art director and executive producer)
Q: Did M1 influence production company influence M2, influence M3 M4 and M5 and influence M6 A: Did (M1) influence (a production company). influence (M2). influence (M3, M4 and M5). and influence (M6)
A.1.2 STEP 2: SUBCLAUSE IDENTIFICATION
Q: What N1 that MO was employed by directed M5
A: What ((N1) that (MO was employed by)) directed M5
Q: What N1 was N2 that M2 influenced
A: What N1 was ((N2) that (M2 influenced))
Q: Did N1 that N2 married meet N3
A: Did ((N1) that (N2 married)) meet N3
Q: Did M2 marry N1 that M1 was edited by directed by and written by
A: Did M2 marry ((N1) that (M1 was edited by, directed by and written by))
Q: Which N1 that was written by M1 M2 directed
A: Which ((N1) that (was written by M1)) M2 directed
Q: Which N1 that N2 influenced was influenced by and married N3
A: Which ((N1) that (N2 influenced]) was influenced by and married N3
Q: Which director of N1 was N2 that M1 employed and founded by
A: Which director N1 was ((N2) that (M1 employed and was founded by))
Q: Was NO that M1 influenced and M2 was influenced by N1
A: Was ((NO) that (M1 influenced and M2 was influenced by)) N1
Q: What N1 that N2 influenced and N3 was influenced by influenced M1
A: What ((N1) that (N2 influenced and N3 was influenced by)) influenced M1
Q: Who was influenced by N1 that wrote N2 and influenced by N3
A: Who was influenced by ((N1) that (wrote N2)) and influenced by N3
Q: Was M4 produced by N1 that N2 were influenced by
A: Was M4 produced by ((N1) that (N2 were influenced by))
Q: Was MO N1 that M2 starre and written by
19

---

Published as a conference paper at ICLR 2023
A: Was MO ((N1) that (M2 starred and was written by))
Q: Was N1 N2 that M2 employed
A: Was N1 ((22) that (M2 employed))
Q: Who was NO that wrote N1 and edited N2
A: Who was ((NO) that (wrote N1 and edited N2))
Q: Did N1 marry and divorce N2 whose N3 wrote M3
A: Did N1 marry and divorce ((N2) whose (N3 wrote M3))
Q: Did N1 whose N2 was employed by M2 and was employed by M3 direct and write M1
A: Did ((N1) whose (N2 was employed by M2 and was employed by M3)) direct and write M1
Q: Did M3 found M4 and found N1 whose N2 wrote M1
A: Did M3 found M4 and found ((N1) whose (N2 wrote M1))
Q: What N1 whose N2 influenced by N3 played M1
A: What ((N1) whose (N2 was influenced by N3)) played M1
Q: Which N1 whose N2 was influenced by M3 and was influenced by N3 directed M2
A: Which ((N1) whose (N2 was influenced by M3 and was influenced by N3)) directed M2
Q: Which N1 was influenced by N2 whose N3 edited M2 and employed by M3
A: Which N1 was influenced by ((N2) whose (N3 edited M2)) and employed by M3
Q: Was N1 whose N2 executive produced, edited, and wrote MO M1
A: Was ((N1) whose (N2 executive produced, edited, and wrote MO)) M1
Q: Was M1 N2 whose N3 directed, produced and wrote N4
A: Was M1 ((N2) whose (N3 directed, produced, and wrote N4))
Q: Was that N2 directed N3
A: Was ((N1) that (N2 directed)) N3
Q: Was N1 whose N2 executive produced M1 and edited MO M3
A: Was ((N1) whose (N2 executive produced M1 and edited MO)) M3
Q: What N1 was N2 whose N3 wrote N4
A: What N1 ((N2) whose (N3 wrote N4))
Q: Which N1 that N2 were written by and were produced by was N3
A: Which ((1)) that (N2 were written by and were produced by)) was N3
Q: Was M2 N2 whose N3 was employed by and founded M1
A: Was M2 ((N2) whose (N3 was employed by and founded M1))
Q: Which was whose N3 produced and executive produced M2
A: Which N1 was ((N2) whose (N3 produced and executive produced M2))
Q: Was NO that N1 were executive produced by were edited by were written by and starred MO
A: Was ((NO) that (N1 were executive produced by, were edited by were written by. and starred MO))
Q: Which NO that M2 employed executive produced M1
A: Which ((NO) that (M2 employed)) executive produced M1
Q: Who was NO that M2 was influenced by and married
A: Who was ((NO) that (M2 was influenced by and married))
20

---

Published as a conference paper at ICLR 2023
Q: Which NO that M1 was edited by did M2 influence
A: Which ((NO) that (M1 was edited by)) did M2 influence
Q: Were NO directed by and produced by N1 that executive produced M1
A: Were NO directed by and produced by ((N1) that (executive produced M1))
Q: What NO that M1 was executive produced by and written by did N1 marry
A: What ((NO) that (M1 was executive produced by and written by)) did N1 marry
Q: Was NO that M1 married N1 that directed and edited N2
A: Was ((NO) that (M1 married)) ((N1) that (directed and edited N2))
Q: What NO influenced by M1 and influenced by N1 that founded N2 edited M2
A: What NO influenced by M1 and influenced by ((N1) that (founded N2)) edited M2
Q: Was NO that N1 were edited, art directed, and produced by MO
A: Was ((NO) that (N1 were edited, art directed, and produced by)) MO
A. 1.3
STEP 3: VERB PHRASE IDENTIFICATION
Verb phrase identification in subclauses Q: that N1 influenced and N2 was influenced by
A: that ((N1 influenced) and (N2 was influenced by))
Q: that was edited by N1 and starred N2
A: that ((was edited by N1) and (starred N2))
Q: whose N1 was influenced by M3 and was influenced by N2
A: whose (N1) ((was influenced by M3) and (was influenced by N2))
Q: whose N1 produced and edited M2
A: whose (N1) (produced and edited) (M2)
Q: whose N1 married M2, met M3,, and played M4
A: whose (N1) ((married M2). (met M3). and (met M3))
Q: that M2 was influenced by and M3 influenced
A: that ((M2 was influenced by) and (M3 influenced))
Q: whose N1 executive produced, edited, and wrote MO
A: whose (N1) (executive produced, edited, and wrote) (MO)
Q: whose N1 was influenced by N2
A: whose (N1) (was influenced by) (N2)
Q: that N1 influenced
A: that (N1) (influenced)
Q: that M1 starred and was written by
A: that (M1) (starred and was written by)
Q: that M1 was edited by directed by and written by
A: that (M1) (was edited by directed by and written by)
Q: whose N1 was employed by M2 and was employed by M3 direct and write M1
A: whose (N1) ((was employed by M2) and (was employed by M3)) (direct and write) (M1)
Q: whose N1 employed by and founded M1
21

---

Published as a conference paper at ICLR 2023
A: whose (N1) (was employed by and founded) (M1)
Q: that M1 influenced
A: that (M1) (influenced)
Q: that directed and executive produced N1
A: that (directed and executive produced) (N1)
Q: that M2 was influenced by and married
A: that (M2) (was influenced by and married)
Q: that N1 were influenced by, M3 was edited by and M4 married
A: that ((N1 were influenced by) (M3 was edited by) and (M4 married))
Q: that N1 were written by
A: that (N1) (were written by)
Q: that founded by and employed N2
A: that (was founded by and employed) (N2)
Q: that was influenced by M2 and was employed by M3 and M4
A: that ((was influenced by M2) and (was employed by M3 and M4))
Q: that N1 married
A: that (N1) (married)
Q: that edited N1 and produced M2
A: that ((edited N1) and (produced M2))
Q: whose N1 edited MO and executive produced N2
A: whose (N1) ((edited MO) and (executive produced N2))
Q: whose N1 edited N2
A: whose (N1) (edited) (N2)
Q: that M1 influenced and employed A: that (M1) (influenced and employed)
Q: that wrote N1 and edited N2
A: that ((wrote N1) and (edited N2))
Q: that edited and wrote N1
A: that (edited and wrote) (N1)
Q: whase N1 was employed by and founded M1
A: whose (N1) (was employed by and founded) (M1)
Q: whose N1 married M2 and married N2
A: whose (N1) ((married M2) and (married N2))
Q: that played M2. played M3 and played M4
A: that ((played M2) (played M3). and (played M4))
Q: that wrote edited, executive produced, and directed N1 A: that (wrote edited executive produced, and directed) (N1)
Q: that N3 were written by and art directed by
A: that (N3) (were written by and art directed by)
22

---

Q: Which N1 was influenced by N2, influenced by N3 and influenced by M4 Published as a conference paper at ICLR 2023
Verb phrase identification in main clauses
Q: Was N1 N2
A: (Was) (N1) (N2)
Q: Did M1 influence N2
A: (Did) (M1) (influence) (N2)
Q: Which N1 was N2
A: (Which) (N1) (was) (N2)
Q: Who employed, met, and was influenced by N1 and married M1
A: (Who) ((employed, met, and was influenced by N1) and (married M1))
Q: Were N1 executive produced by, written by and directed by N2, and produced by N3
A: (Were) (N1) ((executive produced by, written by and directed by N2), and (produced by N3))
Q: What N1 married, divorced and was kissed by N2
A: (What) (N1) (married divorced and kissed by) (N2)
Q: Which N1 did MO acquire
A: (Which) (N1) (did) (MO) (acquire)
A: (Which) (N1) ((was influenced by N2), (influenced by N3). and (influenced by M4))
Q: Was N1 employed by N2 and employed by M4, M5, and M6 N4
A: (Was) ((N1) ((employed by N2) and (employed by N3))) (N4)
Q: Which N1 did N2 produce and M1 direct
A: (Which) (N1) (did) ((N2 produce) and (M1 direct))
Q: Did N1 influence N2 and influence N3
A: (Did) (N1) ((influence N2) and (influence N3))
Q: What did N2 influence
A: (What) (N1) (did) (N2) (influence)
Q: Did MO direct, produce, executive produce, edit, and write N1
A: (Did) (MO) (direct, produce, executive produce, edit, and write) (N1)
Q: Was MO executive produced by, edited by written by and directed by N1
A: (Was) (MO) (executive produced by edited by written by and directed by) (N1)
Q: Who influenced and was influenced by N1
A: (Who) (influenced and was influenced by) (N1)
Q: Did N1 executive produce and produce M1
A: (Did) (N1) (executive produce and produce) (M1)
Q: Did N1 found N1 and found M2
A: (Did) (N1) (ffound N1) and (found M2))
Q: What executive produced by N1 and executive produced N2
A: (What) ((was executive produced by N1) and (executive produced by N2))
Q: Was N1 produced by and written by N2
A: (Was) (N1) (produced by and written by) (N2)
Q: What did N1 produce and write
23

---

Published as a conference paper at ICLR 2023
A: (What) (did) (N1) (produce and write)
Q: Was M1 produced by N1
A: (Was) (M1) (produced by) (N1)
Q: Did N1 edit, N2 direct, and N3 produce M4
A: (Did) ((N1 edit). (N2 direct). and (N3 produce)) M4
Q: Was written by and executive produced by N2 M1
A: (Was) ((N1) (written by and executive produced by) (N2)) (M1)
Q: Which N1 was founded by N2
A: (Which) (N1) (was founded by) (N2)
Q: Which N1 was acquired by N2 and acquired N3
A: (Which) (N1) ((was acquired by N2) and (acquired N3))
Q: Was M2 NO written by M4 and directed by N1
A: (Was) (M2) ((NO) ((written by M4) and (directed by N1)))
Q: What N1 did N2 marry and influence
A: (What) (N1) (did) (N2 marry and influence)
Q: Did N1 influence and marry N2
A: (Did) (N1) (influence and marry) (N2)
Q: Which N1 did M1 marry and M2 marry
A: (Which) (N1) (did) ((M1 marry) and (M2 marry))
Q: What was directed by and edited by N1
A: (What) (was directed by and edited by) (N1)
Q: What did N1 edit and MO executive produce
A: (What) (did) ((N1 edit) and (MO executive produce))
Q: What NO did N1 edit and produce
A: (What) (NO) (did) (N1) (edit and produce)
Q: Was N1 N2 edited by MO
A: (Was) (N1) (N2 (edited by) MO)
Q: Did N1 write film and direct N2
A: (Did) (N1) (wwrite a film) and (direct N2))
Q: Was N1 produced by M1 and executive produced by M2
A: (Was) (N1) ((produced by M1) and (executive produced by M2))
Q: Were written. executive produced, produced, and edited by N2
A: (Were) (N1) (written, executive produced, produced, and edited by) (N2)
Q: Was NO influenced by N1 and influenced by M1 M1
A: (Was) ((N0) (influenced by N1) and (influenced by M1)) (M1)
Q: What was edited by MO and executive produced by NO
A: (What) (wwa edited by MO) and (executive produced by NO))
Q: Did M2 star M3 and star NO
A: (Did) (M2) ((star M3) and (star NO))
24

---

Published as a conference paper at ICLR 2023
Q: Was M1 employed by M2 and employed by NO
A: (Was) (M1) ((employed by M2) and (employed by NO))
Q: What did NO write, direct, edit, executive produce and produce
A: (What) (did) (NO) (write, direct, edit, executive produce and produce)
Q: Was N2 founded N3 and founded by N4
A: (Was) (N1) (N2 ((founded by N3) and (founded by N4)))
Q: Did M2 marry N1 employed by N2
A: (Did) (M2) (influence) (N1 employed by N2)
1.4
STEP 4: PART OF SPEECH TAGGING
Part of speech tagging of noun phrases
Q: M1
A: M=(M1)
Q: (film) A: N=(film)
N2
A: N=(N2)
Q: MO 's producer
A: M-(MO) P=('s) (=(poodueer)
Q: a director sibling
A: [a] (N=(art director) P=('s) N=(sibling))
Q: French producer and editor child 's spouse
A: [a] ((N=(French /A, producer, [and] editor) P=('s) N=(child)) P=('s) N=(spouse))
Q: female French costume designer, producer, and editor of M3 and M4
A: N=(female /A, French /A, costume designer, producer, [and] editor) P=(of) M=(M3, M4)
Q: country of nationality of M3
A: N=(country of nationality) P=(of) M=(M3)
Q: a Dutch parent and spouse
A: [a] N=(Dutch /A, parent, [and] spouse)
Q: a editor, , producer and writer of a film 's prequel
A: [a] (N=(editor, producer, [and] writer) P=(of) ([a] (N=(film) P=('s) N=(prequel)))
Q: female film director 's Spanish parent
A: [a] ((female /A, film director) P=('s) N=((panish /A, parent))
Q: M3 and M6
A: M=(M3, [and] M6)
Q: a writer spouse, friend, and employer
A: [a] (N=(writer) P=('s) N=(spouse, friend, [and] employer))
Q: male Spanish spouse and parent
A: N=(male /A, Spanish /A, spouse, [and] parent)
Q: a person
A: [a] N=(person)
25

---

Published as a conference paper at ICLR 2023
Q: M4, M5, M6 and M7
A: M-(M4, M5, M6, [and] M7)
Q: film director and editor of MO, M1 and M2
A: N=(film director, [and] editor) P=(of) M-(Mo, M1, [and] M2)
Q: a Spanish editor and producer of M5
A: [a] (N=(Spanish /A, editor, [and] producer) P=(of) M=(M5))
Q: child a production company
A: N=(child) P=(of) ([a] N=(production company))
Q: M1 's sibling and spouse
A: M=(M1) P=('s) N=(sibling, [and] spouse)
Q: M3 's employer 's Mexican employee
A: (M=(M3) ('('s) N=(employer) P=('s) N=(Mexican /A, employee)
Q: M3 's parent 's employee
A: (M-(M3) P=('s) N-(parent)) P-('s) N=(employee)
Q: M2 's founder and employee
A: M=(M2) P=('s) N=(founder, [and] employee)
Q: director of M3 M4, and M5
A: N=(director) P=(of) M=(M3, M4, [and] M5)
Q: male director of M3 and M4
A: N=(male /A, director) P=(of) M=(M3, [and] M4)
Q: a child of M4 's male editor 's sibling
A: [a] (N=(child) P=(of) ((M=(M4) P=('s) N=(male /A, editor)) P=('s) N=(sibling)))
Q: spouse of MO sibling 's employee
A: N=(spouse) P=(of) ((M=(M0) P=('s) N=(sibling)) P=('s) N=(employee))
Q: actor 's country of nationality
A: [a] (N=(actor) P=('s) N=(country of nationality))
Q: a female person 's parent sibling
A: [a] ((N=(female /A, person) P=('s) N=(parent)) P=('s) N=(sibling))
Q: a screenwriter French parent
A: [a] (N=(screenwriter) P=('s) N=(French /A, parent))
Q: sibling and friend of a director and actor
A: N=(sibling, [and] friend) P=(of) ([a] (N=(director, [and] actor)))
Q: Mexican American parent
A: N=(Mexican /A, American /A, parent)
Part of speech tagging of other phrases
Q: What
A: W=(What)
Q: Which
A: W-(Which)
26

---

Published as a conference paper at ICLR 2023
Q: Who
A: W=(Who)
Q: (Did)
A: V=(Did)
Q: Was
A: V=(Was)
Q: employed, met and was influenced by N1
A: V=(employed, met, [and] [was] influenced by) (N1)
Q: married M1
A: V=(married) M-(M1)
Q: executive produced by written by and directed by N1
A: (=(executive produced by. V=written by, [and] V=directed by) (N1)
Q: produced by N1
A: (=(pordueed by) (N1)
Q: MO was employed by
A: M=(MO) V=([was] employed by)
Q: N1 married
A: (N1) V=(married)
Q: M4, M5, M6 and M7
A: M=(M4, M5, M6, [and] M7)
Q: was written by M1
A: V=[was] written by) M-(M1)
Q: married, divorced, and was kissed by
A: V=(married, divorced, [and] [was] kissed by)
Q: N1 wrote M3
A: (N1) V=(wrote) M-(M3)
Q: was influenced by N1
A: V=[[as] influenced by) (N1)
Q: influenced by N1
A: (=iinfuuenced by) (N1)
Q: (employed by M1 M2, and M3)
A: V=(employed by) M=(M1, M2, [and] M3)
Q: N1 produce
A: (N1) V=(produce))
Q: influence N1
A: V=(influence) (N1)
Q: M1 employed and founded
A: M=(M)) (=(employed, [and] [was] founded by))
Q: direct, produce, executive produce edit and write
A: (=ddirett, produce, executive produce, edit, [and] write)
27

---

Published as a conference paper at ICLR 2023
Q: executive produced by edited by written by and directed by
A: V-(executive produced by, edited by, written by, [and] directed by)
A.1.5
STEP 5: VERB NORMALIZATION
Q: and
A: and
Q: was
A: be
Q: Was
A: be
Q: were
A: be
Q: Were
A: be
Q: did
A: do
Q: Did
A: do
Q: directed
A: direct
Q: edited
A: edit
Q: met
A: meet
Q: found
A: found
Q: edited by
A: edit by
Q: written by
A: write by
A.2 CFQ EXEMPLAR SELECTION: DETAILS
For CFQ, we use random subset consisting of 1000 examples from the training set as pool of candidate exemplars. For eareach input question to process, we then dynamically select exemplars from this pool such that they collectively demonstrate relevant knowledge needed to translate the input sentences. This is done by making sure that as many nodes as possible of the decomposition tree of the input are covered by the decomposition trees of the selected exemplars. Depending the complexity of the input and the similarity of the candidate exemplars in the pool, we select between 4 and 35 exemplars for any given input.
We provide a general description of this process in Section 3.2 and add the CFQ-specific details here. In Section A.3 we also show the set of all selected exemplars for the example in Figure
28

---

Published as a conference paper at ICLR 2023
A.2.1 TOP-DOWN MATCHING
We want to select exemplars that cover the structure of the input question as well as possible. We do this using the following process:
We first convert the decomposition trees of all the candidate exemplars as well as the concrete input question into syntactic templates by anonymizing concrete leaves and just keeping their types. For instance, the question shown in Figure results in the syntactic template "Which (V (N that (V (M, M, [and] M))) and (V (M 's N))".
Then we try to find exemplars that match the full template of the input question. If we succeed, keep them. Otherwise, reduce the templates by collapsing some of the nodes. For example, we can collapse the node "(M M [and] M)" in the above template and instead just use "M"" We again try find exemplars that match the reduced template, keep them if we succeed, and otherwise continue reducing the templates. We do this until we retrieve exemplars that collectively cover the input template as well as possible.
We wrote small amount of Python code that implements generic version of these heuristics and use for both CFQ and COGS. For the example shown in Figure 66] the top-down matching yields exemplars such the ones shown below. Note that to provide the LM with additional hints, we add to the original question parentheses that indicate the syntactic structure.
Q: Which cinematographer founded (M1 's distributor)
A: SELECT DISTINCT ?x0 WHERE { ?x0 a cinematographer. ?x0 founded ?x1 ?x1 distributed
M1 }
Q: What (film director ((ifluuecced by M1) and (influenced by (a person that (founded (M4 and M5)))))) produced M2 A: SELECT DISTINCT ?x0 WHERE { ?x0 a fim_director ?x0 produced M2. ?x0 influenced by ?xt
?x0 influenced by M1. ?x1 a person. ?x1 founded M4 ?x1 founded M5 }
A.2.2 BOTTOM-UP MATCHING
We also want to select exemplars that collectively cover each of the unanonymized leaves. In our running example, this means that we want to cover the leaves "film editor", "influence", "cinematog- rapher", "write", and "editor". addition, we prefer exemplars where these leaves occur within a similar syntactic template in the input question.
For each leaf, we do this by converting the decomposition trees into a form where everything but this leaf is anonymized. For the leaf "editor"", , this results in "Which N (V (N that (V (M, M., [and] M))) and (V (M editor))". Then we try to find exemplars that share as many subtrees containing "editor" as possible. This yields exemplars such as:
Q: Was a (Dutch film editor) MO
A: SELECT count(") WHERE MO eemter. MO has nationaaay Dutch }
Q: Which actor (was influenced by and influenced) (M1 editor)
A: SELECT DISTINCT ?x0 WHERE { ?x0 a actor. ?x0 influenced ?x1 ?x0 influencedd_by ?x1 ?x1
edited M1
Q: Was a (Chinese cinematographer) MO
A: SELECT count(") WHERE MO cinematographer. MO has_nationality Chinese }
Q: What did (MO 's sibling) write
A: SELECT DISTINCT ?x0 WHERE { ?xx written.by 2x1 ?x1 sibling.of MO
Q: Was M1 (ffounded by (MO editor)) and (founded by M2))
A: SELECT count(") WHERE ?x0 edited MO. M1 founded by ?x0 M1 founded by M2
29

---

Published as a conference paper at ICLR 2023
A.3 CFQ SOLUTION: DETAILS AND PROMPT
As we discussed in Section 3.3 one novelty of dynamic least-to-most prompting is that we cannot translate the constituents in isolation because they might correspond to well-formed questions and their translation may depend on the context. Instead, we linearize the composition tree into sequence increasingly complex subquestions.
This linearization is performed by walk over the parse tree. We keep the most generic variant of each top-level node and then expand these nodes step by step to obtain a linear sequence well- formed subquestions. For each subquestion, we then query the language model using prompt that consists of three parts.
1. Static prompt context for question grounding
2. Dynamically selected exemplars as additional context
3. Sequential questions
These parts are detailed throughout the rest of this section.
A.3.1 PART 1: STATIC PROMPT CONTEXT.
Because we cannot translate constituents in isolation, even the simplest subquestion may be too complex to be translated correctly based on the selected exemplars alone. This is especially the case if the exemplar pool does not contain similar questions.
To teach the language model how to translate the simplest subquestions, we therefore provide with a constant prompt context consisting of 12 grounding examples that illustrate these kinds of subquestions. In addition to the question and its translation, each these grounding examples also provides rationale that tells the model how the translation can be obtained (this resembles our chain-of-thought prompt).
The static prompt context is provided below. Note that Q: instead of "Q:") for these grounding questions. This allows us to encourage the model to perform natonaal-basee reasoning when asking it translate the simplest question of sequence. Also note that we again use parentheses to indicate the syntactic structure of the questions.
slightly different prefix ("Partial
Partial Q: Was (costume designer 's parent) (MO editor)
Rational: Was (h. "costume designer 's parent" { ?x0 parent.of ?x1 ?x1 costume eestume_designer }. "MO editor" ?x0 edited MO ==>> A: SELECT count(") WHERE ?x0 parent ?x1 ?x1
costume.des desiggerr..ee.. ?x0 edited MO]
Partial Q: Was MO (screenwriter 's spouse)
Rationale: Was = (). "MO" replaces ?x0, "screenwriter 's spouse" = { ?x0 married ?x1 ?x1
writer } = A: SELECT count(") WHERE { MO married_to ?x1 ?x1 a writer
Partial Q: Was (sequel of M1) MO
Rationale: Was (). "star M1" ?x0 has pas.uel M1 "MO" replaces ?x0 ==> A: SELECT
count(") WHERE MO has aaaeueel M1
Partial Q: Was M1 executive produced by a (sibling of film producer)
Rationale: Was = (). "M1" replaces ?x0, "executive produced by" { ?x0 executive_pront .ttptiiveeerduuudd...o ?x1 "sibling of film producer" { ?x1 sibling.of ?x2 ?x2 a filmmprodducr ==> A: SELECT count(") WHERE { M1 executive produced by ?x1 ?x1 sibling of ?x2. ?x2 a film producer }
Partial Q: Did (film 's prequel) star M1
Rationale: Did {}, "film 's prequel" = { ?x0 has ?x1 ?x1 film }. "star M1" = { ?x0 starred M1 ==> A: SELECT count(") WHERE { ?x0 has has_sequel ?x1 ?x1 film ?x0 starred M1
Partial Q: Did MO art direct M1
Rationale: Did = (). "MO" replaces ?x0, art direct M1 ?x0 art directed M1 ==>> A: SELECT count(") WHERE { MO art directed M1)
30

---

Published as a conference paper at ICLR 2023
Partial Q: Which person did M1 star
Rationale: Which () "person" ?x0 person ), "did M1 star" M1 starred ?x0 } ==> A:
SELECT DISTINCT ?xO WHERE ?x0 a person M1 starred ?x0)
Partial Q: Which (parent of MO) was a (person 's parent)
Rationale: Which (}. "parent of MO" ?x0 parent of MO }. "costume designer 's parent" { ?x0
parent_of ?x1 ?x1 a costume. costume.designer ==> A: SELECT DISTINCT ?x0 WHERE ?x0 parent.of
MO ?x0 parent.of ?x1 ?x1 costume_desse [estume_designe]]
Partial Q: What was a written by
Rationale: What (). "film written by M1" { ?x0 a film ?x0 written.by M1 ==>> A: SELECT DISTINCT ?x0 WHERE ?x0 a film. ?x0 written.by M1
Partial Q: What (star of M1) was a (cinematographer 's parent)",
Rationale: What = (). "star of M1" ?x0 starred in M1 J. "cinematographer 's parent" { ?x0 parent_of ?x1 ?x1 a cinematographer ==> A: SELECT DISTINCT ?x0 WHERE { ?x0 starred.in in M1 ?x0 parent_of ?x1 ?x1 cinematographer
Partial Q: Who was a (producer of M1)
Rationale: "Who" ?x0 a person }, "executive producer of M1" ?x0 produced M1 SELECT DISTINCT ?xO WHERE ?x0 person ?x0 produced M1
Partial Q: Who employed a person influenced by MO Rationale: "Who" ?x0 person "employed person" { ?x0 employed ?x1. ?x1 person }, "influenced by MO { ?x1 influenced.by MO ==> A: SELECT DISTINCT ?x0 WHERE ?xx person ?x0 employed ?x1 ?x1 person. ?x1 influenced.by MO
A.3.2 PART 2: DYNAMICALLY SELECTED EXEMPLARS
After the constant prompt context, we add as additional context the exemplars that we dynamically selected for the given input using the process described in Section A.2
For our example from Figure 6 this results in the following prompt context, which appended to the static context shown above.
Q: Were (M2 and M3) produced by (a actor that (influenced (M1 's editor)))
A: SELECT count(") WHERE ?xx actor ?x0 influenced ?x1 ?x1 edited M1 M2 produced by
?x0 M3 produced ?x0!
Q: Did M1 ((star (editor of MO)) and (star M2))
A: SELECT count(") WHERE ?x0 edited MO starred ?x0 starred M2
Q: Was M1 (ffounded by (MO editor)) and (founded by M2))
A: SELECT count(") WHERE ?x0 edited MO M1 founded by ?x0 M1 founded by M2
Q: Which actor ((was influenced by (M4 (art director and writer))) (influenced M1) and (influenced (M2 and M3))) A: SELECT DISTINCT ?xo WHERE { ?x0 actor ?x0 influenced M1 ?x0 influenced M2. ?x0 influenced M3. ?x0 influenced.bl ?x1 ?x1 art_directed M4 ?x1 wrote M4
Q: Which actor ((married a film editor) and (was influenced by (M1 's sibling)))
A: SELECT DISTINCT ?x0 WHERE { ?x0 a actor. ?x0 influenced by ?x1 ?x0 married ?x2. ?xt sibling_of M1
?x2 film_editor
Q: Did (film editor 's parent) write MO
A: SELECT count(") WHERE ?x0 wrote MO ?x0 parent.of ?x1 ?x1 film_editor }
Q: Did MO (write, edit, and produce) M1
A: SELECT count(") WHERE MO edited M1 MO produced M1. MO wrote M1
31

---

Published as a conference paper at ICLR 2023
Q: What did (MO sibling) write
A: SELECT DISTINCT ?x0 WHERE ?x0 written by ?xt ?x1 sibling of MO
Q: Was (Chinese cinematographer) MO
A: SELECT count(") WHERE MO cinematographer. MO has nationalyy Chinese }
Q: Who was (a cinematographer that (distributed M2))
SELECT DISTINCT ?x0 WHERE {
?x0 a cinematographer. ?x0 a person ?x0 distributed M2
Q: Who ((was influenced by M1) and (influenced by a (Swedish cinematographer)))
A: SELECT DISTINCT ?x0 WHERE ?x0 person.. ?x0 influenced ?x1 ?x0 influenced_by M1
?x1 cinematographer. ?x1 has.nationality Swedish }
Q: Who ((was influenced by (M1 's star)) and (married (M2 's Sibling))
A: SELECT DISTINCT ?x0 WHERE { ?xx0 person.. ?x0 influenced. by ?x1 ?x0 married.tt to ?x2.
?x1 starred in M1 ?x2 sibling.or of M2]
Q: Who ((was influenced by M1) and (influenced by (a person that (edited M2))))
A: SELECT DISTINCT ?x0 WHERE ?xx0 person ?x0 influenced ?x1 ?x0 influenced by M1
?x1 person ?x1 edited M2
Q: Which actor (was influenced by and influenced) (M1 's editor)
A: SELECT DISTINCT ?x0 WHERE { ?x0 a actor ?x0 influenced ?x1 ?x0 influenced.b. ?x1 ?x1
edited M1
Q: Was (Dutch film editor) MO
A: SELECT count(") WHERE MO film editor. MO has nationality Dutch }
Q: Was M1 (employer of a film editor)
A: SELECT count(") WHERE ?x0 film_editor M1 employed ?x0
Q: Did a (actor M1) edit MO
A: SELECT count(") WHERE ?x0 portrayed M1 ?x0 edited MO
Q: Did M1 ((star M2) and (star (MO 's employee)))
A: SELECT count(") WHERE ?x0 employed by MO M1 starred ?x0 M1 starred M2
Q: Did MO (executive produce (M1 M2, and produce)) M3
A: SELECT count(") WHERE MO executive produced M1 MO executive produced M2 MO produced M3)
Q: What (film director ((iffluenced by M1) and (influenced by (a person that (founded (M4 and M5)])))) produced M2 A: SELECT DISTINCT ?x0 WHERE { ?x0 a film_director ?x0 produced M2. ?x0 influenced.bb ?x1
?x0 influenced by M1 ?x1 person. ?x1 founded M4 ?x1 founded M5)
Q: Which cinematographer founded (M1 distributor)
A: SELECT DISTINCT ?x0 WHERE { ?x0 cinematographer. ?x0 founded ?x1 ?x1 distributed
M1 }
Q: Which character influenced a film editor
A: SELECT DISTINCT ?x0 WHERE { ?x0 fictional character ?xo influenced ?xt ?x1
film editor }
Q: Which film editor founded (M1 's distributor)
A: SELECT DISTINCT ?xo WHERE { ?x0 a film editor ?x0 founded ?x1 ?x1 distributed M1
32

---

Published as a conference paper at ICLR 2023
Q: Which character married screenwriter
A: SELECT DISTINCT ?x0 WHERE { ?xx a fictional.character. ?x0 married.to ?xt ?x1 a writer
A.3.3 PART 3: SEQUENTIAL QUESTIONS
After providing the static and dynamic prompt context, we start by grounding the simplest subques- tion. To encourage the model to use the rationale- -aasd reasoning, we use the prefix "Partial Q:" rather than just "Q:" " for this question. After obtain the translation from the model, to the prompt and then again ask the same subquestion, but this time using the regular "Q:" prefix. In addition, tell the model that it can simply copy the answer from above by adding the comment "# Copy the answer from above""
append it
For the example from Figure this first part of the prompt looks follows. Note that the text that is not bolded corresponds to the answers provided by the model.
Partial Q: Which film editor was influenced by cinematographer
Rationale: Which (}. "film editor" = ?x0 a film_editor }. "was influenced by cinematographer".
{ ?x0 influenced_br by ?x1 ?x1 cinematographer ==> A: SELECT DISTINCT ?x0 WHERE { ?x0
a film editor.. ?x0 influenced by ?x1 ?x1 cinematographer }
# Copy the answer from above. Q: Which film editor was influenced by a cinematographer A: SELECT DISTINCT ?x0 WHERE { ?x0 a film_editor. ?x0 influenced.by ?x1 ?x1 cinematographer
After grounding the simplest question, continue with the next subquestions, which presented to the model one after the other using the ordinary prefix "Q:". Sometimes, a subquestion is strict extension of the previous subquestion. To make that the model does not miss this, add comment of the form "# Extend the answer above. Add: the questions. In other cases, subquestion is almost the as the previous question, except that one constituent is replaced by another.
which highlights the delta between
For each of these subquestions, to the prompt before asking the next question. For our running example, this part of the prompt looks follows. Note that we obtain the correct answer to the original question the end.
perform a request to the language model and append the answer
# Extend the answer above. Add: that (wrote M3)
Q: Which film editor (was influenced by (a cinematographer that (wrote M3)))
A: SELECT DISTINCT ?x0 WHERE { ?x0 a film_editor ?x0 influenced. by 2x1 ?x1 a cinematogra-
pher ?x1 wrote M3)
# Extend the answer above. Add: M5
Q: Which film editor (was influenced by (a cinematographer that (wrote (M3 and M5))))
A: SELECT DISTINCT ?x0 WHERE { ?x0 a film_editor ?x0 influenced.by ?x1 ?x1 a cinematogra- pher. ?x1 wrote M3. ?x1 wrote M5!
Extend the answer above. Add: M4
Q: Which film editor (was influenced by (a cinematographer that (wrote (M3, M4 and M5))))
A: SELECT DISTINCT ?x0 WHERE { ?x0 a film_editor ?x0 influenced ?x1 ?x1 a cinematogra-
pher.
?x1 wrote M3. ?x1 wrote M4. ?x1 wrote M5
Q: Which film editor (influenced by (M1 's editor))
A: SELECT DISTINCT ?x0 WHERE { ?x0 a film editor ?x0 influenced by 2x1 ?x1 edited M1
# Extend the answer above. Add: was influenced by (a cinematographer that (wrote (M3, M4, and M5)))
Q: Which film editor ((was influenced by (a cinematographer that (wrote (M3, M4 and M5))))
and (influenced by (M1 's editor)))
A: SELECT DISTINCT ?x0 WHERE ?x0 film editor ?x0 influenced by ?x1 ?x1 edited M1
?x0 influenced by ?x2. ?x2 cinematographer. ?x2 wrote M3. ?x2 wrote M4. ?x2 wrote M5
33

---

Published as a conference paper at ICLR 2023
B LEAST-TO-MOST PROMPTING FOR COGS
James said that manager liked that Aiden appreciated that Emily believed that the girl posted cake beside a table by Olivia
FARSE:
say agent James ccomp = like
agent manager ccomp appreciate
agent Aiden , ccomp - believe
agent Emily scomp post
recipient girl theme cake
nmod beside = table
agent = Olivia
DONE
The boy shortened the donut beside the bed the car garden the can on the tree.
PARSK: shorten agent boy theme donut
nmod beside bed nmed in
nmod
garden
nmod in = can
nmod
= tree
)
DONE
Figure 7: Two COGS example, which to illustrate the application of dynamic least-to-most prompting to COGS. The first example contains nested subclauses while the second example con- tains nested propositional phrases.
In this section, provide more details the application of dynamic least-to-most prompting for COGS. In particular, we detail all the prompts and show how the example in Figure 7 is processed step by step. Note that this is variation of the application of dynamic-least-to CFQ, which is detailed in Section A Therefore, we mostly focus on highlighting the differences.
prompting for
B.1 COGS DECOMPOSITION DETAILS AND PROMPTS
As discussed in Section 3.1 we use prompting- syntactic parsing to decompose COGS sen- tences. To teach LMs to perform this kind of decomposition, divide the syntactic parsing task into the following steps
1. Iterative subclause decomposition
2. Phrase identification
3. Iterative prepositional phrase decomposition and noun phrase annotation
4. Verb phrase normalization
This is quite similar to the steps used for CFQ (see Section A.I) but there are some important differences. Since the CFQ dataset only contains limited nesting of subclauses and noun phrases, we were able identify them in a single step. As exemplified by the first example in Figure the COGS dataset contains much deeper nesting of subclauses (up to level 12), which we address by performing subclause decomposition iteratively. This means that the prompt for subclause decomposition (step 1) is designed such that only extracts one subclause at time and is applied iteratively until all subclauses are extracted.
As exemplified by the second example in Figure 7 COGS also contains deep nesting of prepositional phrases (up level 12). We again address this by performing prepositional phrase decomposition (step 3) iteratively and designed the prompt such that it only extracts one prepositional phrase at time and applied iteratively until all prepositional phrases are extracted.
Example 1. To illustrate this step-by-step process, begin with the first example from Figure which "James said that a manager liked that Aiden appreciated that Emily believed that the girl was posted a cake beside a table by Olivia ". The first step decomposes the subclauses of this sentence via 4 iterative calls:
P=(James) V=(said) that C=(a manager liked that Aiden appreciated that Emily believed that the girl was posted cake beside table by Olivia)
34

---

Published as a conference paper at ICLR 2023
P=(a manager) V=(liked) that C=(Aiden appreciated that Emily believed that the girl was
posted a cake beside a table by Olivia)
P=(Aiden) V=(appreciated) that C=(mily believed that the girl was posted a cake beside table by Olivia)
P=(Emily) V=(believed) that C=(the girl was posted cake beside table by Olivia)
In the second step, we identify the different phrases for the final subclause "the girl was posted cake beside a table by Olivia", which yields:
P=(the girl) V=(was posted) P=(a cake beside a table) by P=(Olivia)
In the third step, we decompose the propositional phrase, which is not nested and therefore requires only one iteration:
cake) beside P=(a table)
Note that the same prompt is also used to annotate noun phrases by marking the use of the definite article with star. We therefore also apply it to all other noun phrases, which yields:
James
manager
Aiden
Emily
the girl
Olivia
table
In the fourth step, we normalize all the verbs, which means that "said" yields "say", "liked" yields "like", "appreciated" yields "appreciate", "believed" yields "believe", and "was posted" yields "post". Finally, we run few lines of Python code that puts all these parts back together ob- tain a parse tree. Note that the normalized verbs do not replace the original ones but are kept in addition, which allows us to obtain higher recall when selecting exemplars.
This yields the following fully decomposed sentence:
(James) (said [say]) that ((a manager) (liked [like]) that ((Aiden) (appreciated [appreciate]) that ((Emily) (believed [believe]) that ((the * girl) (was posted [post]) ((a cake) (beside) (a table)) by (Olivia))))
We now walk through the step-by-step process using the second example from Fig- ure 7 which is "The boy shortened the donut beside the bed in the car in the garden the can on the tree ". Since this example does not contain any suubclauses, the first step does not apply. In the second step, we identify the different phrases, which yields:
Example 2.
P= boy) V=(shortened) P=(the donut beside the bed the car the garden in the can the tree)
In the third step, decompose the prepositional phrase, which happens to be nested and therefore requires 5 iterations:
(the donut) beside P=(the bed in the car in the garden in the can on the tree)
(the bed) in P=(the car the garden in the can on the tree)
(the * car) in P=(the garden the can on the tree)
(the garden) in P=(the can the tree)
(the can) P=(the tree)
35

---

Published as a conference paper at ICLR 2023
Since the same prompt is also used to annotate noun phrases by marking the of the definite article with star, we also apply to all other noun phrases, which yields:
The boy the tree
In the fourth step, we normalize all the verbs, which means that "shortened" yields "shorten". This yields the following fully decomposed sentence:
(The boy) (shortened [shorten]) ((the donut) (beside) ((the bed) (in) ((the car) (in) ((the garden) (in) ((th * can) (on) (the * tree))))))
Below, we present the exact prompt contexts used for each of the parsing steps.
B.1.1 ITERATIVE SUBCLAUSE DECOMPOSITION
Q: The girl expected that Daniel liked that a weapon was liked
A: P=(The girl) V=(expected) that C=(Dnniel liked that a weapon was liked)
Q: The girl hoped that a donut was returned a cat by a monkey
A: P=(The girl) V=(hoped) that C=(a donut was returned to a cat by monkey)
Q: a teacher thought that a girl liked that cookie was valued by Emma
A: P-(a teacher) V=(thought) that C-(a girl liked that a cookie was valued by Emma)
Q: Benjamin supported that Avery loaned a donut in to frog P=(Benjamin) V=(supported) C=(that Avery loaned donut a cup a frog)
Q: girl liked that a frog liked that Eleanor gave a brush to the professor
A: P=(A girl) V=(liked) that C=(a frog liked that Eleanor gave brush to the professor)
Q: Charlotte expected that Emma liked that the patient lended box a table to Nora
A: P=(Charlottte) V=(expected) that C=(Emma liked that the patient lended a box on table to Nora)
Q: Aiden believed that a mouse hoped that Olivia examined a glue beside the stage beside duck
A: P=(Aiden) V=(believed) that C=(a mouse hoped that Olivia examined glue beside the stage beside duck)
Q: a girl declared that the boy was offered the watch beside the table
A: P=(a girl) V=(declared) that C=(the boy was offered the watch beside the table)
Q: the teacher declared that a donut was given to the student by Noah
A: P=(the teacher) V=(declared) that C=(a donut was given to the student by Noah)
Q: A dog respected that Emma rented the biscuit in a pot beside a nest to the boy
A: P=(A dog) V=(respected) that C=(Emma rented the biscuit pot beside a nest to the boy)
Q: The teacher liked that driver hoped that the girl meant
A: P (The teacher) V=(lked) that C=(a driver hoped that the girl meant to eat)
Q: the giraffe liked that Olivia noticed that the butterfly was given the drink in the garden on
table
A: P=(the giraffe) V=(liked) that C=(Olivia noticed that the butterfly was given the drink in the garden
on a table)
Q: A cat in a box on table tolerated that a professor beside the stage liked dog
A: P=(A cat in box table) V=(tolerated) that C=(a professor beside the stage liked a dog)
36

---

Published as a conference paper at ICLR 2023
Q: the professor on a chair beside a bench in a room expected that a mouse was given present by doctor the stage in house A: P=(the professor on a chair beside bench in a room) V=(expected) that C=(a mouse was given present by doctor on the stage in house)
Q: Joe liked that Fred thought that girl confessed that the chicken meant that Freda liked that Peter hoped that Elizabeth said that professor whished that Anna hoped that Lisa declared that the creature tolerated that a teacher liked that Lily was given the clock beside guitar beside the table by Isabella
A: P=(Joe) V=(liked) that C=(Fred thought that a girl confessed that the chicken meant that Freda liked that Peter hoped that Elizabeth said that a professor whished that Anna hoped that Lisa declared that the creature tolerated that a teacher liked that Lily was given the clock beside guitar beside the table by Isabella)
B.1.2 PHRASE IDENTIFICATION
Q: boy meant to talk
A: P=(a boy) V=(meant) (to talk)
Q: Camila rolled a lamb beside a flower
A: P=(Camila) V=(rolled) P=(a lamb beside a flower))
Q: the hen appreciated the journalist the piano
A: P=(the hen) (=(appreciated) P=(the journalist on the piano)
Q: The chicken on box needed to eat P=(The chicken on box) V=(needed) (to eat)
Q: a king awarded Joe Fred
A: P=(a king) V=(awarded) P=(Joe) P=(Fred)
Q: The drink was snapped by Ava
A: P=(The drink) V=(was snapped) by P=(Ava)
Q: the teacher passed Joe a pen
A: P=(the teacher) V=(passed) P=(Joe) P=(a pen)
Q: the girl offered Fred James
A: P=(the girl) V=(offered) P=(Fred) to P=(James)
Q: A teacher beside the table wanted to hunt
A: P (A teacher beside the table) V=(wanted) (to hunt)
Q: A crayon was handed to the girl on the table
A: P=(A crayon) V=(was handed) to P=(the girl the table)
Q: Aria rented the boy donut in the room
A: P=(Aria) V=(rented) P=(the boy) P=(a donut in the room)
Q: Peter mailed Sawyer the hedgehog in the garage
A: P=(Peter) V=(mailed) P=(Sawyer) P=(the hedgehog in the garage)
Q: a boy froze the sandwich on the stage in the room
A: P=(a boy) V=(froze) P=(the sandwich on the stage in the room)
Q: A donut returned to cat beside the dog by monkey roof
A: P=(A donut) V=(was returned) to P=(a cat beside the dog) by P=(a monkey on roof)
37

---

Published as a conference paper at ICLR 2023
Q: Avery loaned donut in cup frog
A: P=(Avery) V=(loaned) P=(a donut in cup) to P=(a frog)
Q: the patient lended a box on a table to Nora
A: P=(the patient) V=(lended) P=(a box table) to P=(Nora)
Q: The butterfly was given the drink in the garden on table
A: P=(The butterfly) V=(was given) P=(the drink in the garden on table)
Q: Luke gave the cake the windowsill beside a bed under a lamp to teacher pony
A: P=(Luke) V=(gave) P=(the cake on windowsill beside bed under a lamp) P=(a teacher on
pony)
Q: The teacher received a cat in box a table carpet beside window from Joe A: P=(The teacher) V=(received) P=(a cat in a box on a table on a carpet beside a window) (from P=(Joe))
Q: A cat in cage on a table gave present in box dog the floor
A: P=(A cat in a cage on table) V=(gave) P=(a present in a box) to P=(a dog on the floor)
Q: A ring on a pillow in a wrapper was presented to the professor in room by priest on
chair
A: P=(a ring on pillow in a wrapper) V=(was presented) to P=(the professor in room) by P=(a priest on a chair)
Q: Charles posted the pony a barn the drink in a pear on the floor beside the book in the iron brick in the robe in pipe A: P=(Charles) V=(posted) P=(the pony barn) P=(the drink in a pear on the floor beside the book the iron brick in the robe in pipe)
Q: frog was given the apple in school town on stool on sheet on a table on desk on the floor in a room beside building on road in city in the world in the universe by baby A: P=(a frog) V=(was given) P= apple school in a on stool on sheet on a table on desk on the floor in room beside a building on a road in a city in the world in the universe) by P=(a baby)
B.1.3 ITERATIVE PREPOSITIONAL PHRASE DECOMPOSITION AND NOUN PHRASE ANNOTATION
Q: Joe
A: Joe
Q: Liam
A: Liam
Q: lsabelle
A: Isabelle
Q: Benedict
A: Benedict
Q: atom
A: A atom
Q: a helmet
A: a helmet
Q: A camera
A: A camera
38

---

Published as a conference paper at ICLR 2023
Q: a helmet
A: helmet
Q: the atom
A: the atom
Q: The helmet
A: The helmet
Q: the camera
A: the camera
Q: The song
A: The song
Q: the rino A: the rino
Q: The lizzard
A: The lizzard
Q: the plane
A: the plane
Q: The gnome
A: The gnome
Q: the
A: the nose
Q: The adventure
A: The adventure
Q: the undertaking
A: the undertaking
Q: The camera
A: The camera
Q: the sky
A: the sky
Q: The trainer
A: The trainer
Q: the underdog
A: the underdog
Q: The mole
A: The mole
Q: the floor
A: the floor
Q: The stone
A: The stone
Q: the smartphone
39

---

Published as a conference paper at ICLR 2023
A: the smartphone
Q: The hiccups
A: The hiccups
Q: the wine
A: the wine
Q: The dinosaur
A: The dinosaur
Q: the boy
A: the boy
Q: a atom beside a flower
A: (a atom) (beside) P=(a flower)
Q: A song beside roof
A: (A song) (beside) P=(a roof)
Q: the shark in the helmet
A: (the shark) (in) P=(the helmet)
Q: The camera beside the pool
A: (The camera) (beside) P=(the pool)
Q: the floor in the rino
A: (the floor) (in) P=(the rino)
Q: the sky on a ceiling
A: (the sky) (on) P=(a ceiling)
Q: the plane on the piano
A: (the plane) (on) P=(the piano)
Q: A rino in trainer
A: (A rino) (in) P=(a trainer)
Q: The sandwich on the underdog in the camera
A: (The sandwich) (on) P=(the underdog in the camera)
Q: A undertaking in the camera on leg
A: (A undertaking) (in) P=(the camera on leg)
Q: The helmet on the smartphone
A: (The helmet) (on) P= smartphone)
Q: the helmet on the dinosaur beside smartphone under wine
A: (the helmet) (on) P=(the dinosaur beside smartphone under wine)
Q: A stone in trainer on leg helmet beside window
A: (A stone) (in) P=(a trainer on a leg on helmet beside a window)
Q: riffle on the floor the rino on the leg beside the stone on a spear beside the rino on
sofa
A: (a riffle) (on) P=(the floor in the rino on the leg beside the stone on spear beside the rino on sofa)
Q: The referee in a rino beside a official on smartphone the camera beside the trainer in
40

---

Published as a conference paper at ICLR 2023
trainer under the spider on the shingle
A: (The referee) (in) P=(a rino beside a official on a smartphone in the camera beside the trainer in trainer under the spider on the shingle)
Q: Joe in helmet in a vessel the water beside harbor in village beside city in country on continent on earth A: (Joe) (in) P=(a helmet in vessel the water beside harbor village beside city country on continent on earth)
Q: underdog beside foreigner on smartphone in truck in microwave beside rocket on a computer on stool on the surface A: (a underdog) (beside) P=(a foreigner on smartphone in truck in microwave beside a rocket on a computer on stool on the surface)
Q: the rooster over a computer on a board on the spear on leg on the floor beside a rocker under window on shingle beside rino under the clouds on the sky A: (the rooster) (over) P=(a computer on board on the spear on a leg on the floor beside a rocker under window on shingle beside a rino under the clouds the sky)
Q: phone on the helmet in the rino on the wallet beside the knive on floor beside the liz- zard on a underdog in a wardrobe beside the rocket in the bus beside a hut in the village A: (A phone) (on) P=(the helmet in the rino on the wallet beside knive on a floor beside the lizzard on underdog in a wardrobe beside the rocket in the bus beside hut in the village)
leg rocker on the floor a camera beside building on a street a city in the world in the universe A: (the country) (in) P=(a school in town stool a sheet on leg rocker the floor in a camera beside building on a street a city in the world in the universe)
Q: the country in school in town
stool
sheet
B.1.4 VERB PHRASE NORMALIZATION
Q: expected
A: expect
Q: hoped
A: hope
Q: thought
A: think
Q: supported
A: support
Q: liked
A: like
Q: gave
A: give
Q:
A: eat
Q: was snapped
A: snap
Q: was given
A: give
Q: was returned
41

---

Published as a conference paper at ICLR 2023
A: return
Q: was lended
A: lend
Q: was brought
A: bring
B.2 COGS EXEMPLAR SELECTION: DETAILS
We provide general description of the exemplar selection process in Section 3.2 and add the CFQ- specific details Section A.2 Since COGS using the same heuristics with slightly different parameters, we just highlight the differences here.
B.2.1 EXEMPLAR POOT
random subset consisting of 1000 examples from the training set as pool of candidate exemplars. For COGS, we went a different route and manually selected a set of exemplars from the training data. The main reason for this is that COGS contains many different verbs and since unergative and unaccusative are translated differently, it is important to include as many of them in the exemplar pool as possible, certain verb should be treated. Also, since some of those verbs are quite rare in the training data, some of them would not be included reasonably sized random sample.
For CFQ,
would otherwise be hard for the model figure out how
Concretely, we include in the exemplar pool for COGS the following 62 exemplars containing all unergative and unaceusative verbs that occur in the training data. As CFQ, we use for all exem- plars parsed version of the natural language sentence, which contains additional parentheses and other annotations that make it casier for the model to perform the translation.
(The goose) (baked [bake])
PARSE: bake aagent goose DONE
(A bell) (broke [break])
PARSE: break (theme bell DONE
(A molecule) (burned [burn]) PARSE: burn ttheme molecule) ) DONE
(A cat) (called [call))
PARSE: call agent cat) ) DONE
(A cake) (changed [change))
PARSE: change theme cake DONE
(A student) (cleaned [clean])
PARSE: clean agent student DONE
(A pickle) (collapsed [collapse])
PARSE: collapse theme pickle) DONE
(A baby) (cooked [cook])
PARSE: cook ( agent baby DONE
(A dog) (crumpled [crumple])
PARSE: crumple tthem = dog) ) DONE
(A pig) (cried [cry]) PARSE: cry agent pig DONE
(A chicken) (danced [dance])
42

---

Published as a conference paper at ICLR 2023
PARSE: dance agent chicken DONE
(A buyer) (decomposed [decomposel)
PARSE: decompose (theme buyer DONE
(A mandarin) (disintegrated [disintegrate))
PARSE: disintegrate theme mandarin DONE
(A bowl) (doubled [double])
PARSE: double theme bowl DONE
(A cat) (drew [draw]]
PARSE: draw aagent cat) ) DONE
(A monster) (dusted [dust])
PARSE: dust agent monster DONE
(A boy) (ate [eat])
PARSE: eat agent boy DONE
(A boy) (enlarged (enlarge))
PARSE: enlarge theme boy ) DONE
(A boy) (examined [examine])
PARSE: examine agent boy) DONE
(A girl) (floated [float])
PARSE: float (theme girl) ) DONE
(A melon) (froze [freeze])
PARSE: freeze ttheme melon) DONE
(A resident) (frowned [frown]) PARSE: frown agent resident) DONE
(A dog) (gasped [gasp])
PARSE: gasp agent dog ) DONE
(A chicken) (giggled [giggle])
PARSE: giggle agent chicken DONE
(A dog) (grew [grow])
PARSE: grow (theme = dog DONE
(A butterfly) (heard [hear)) PARSE: hear agent butterfly) ) DONE
(A child) (hunted [hunt])
PARSE: hunt agent child) DONE
(A cat) (improved [improve]) PARSE: improve (them = cat DONE
(A boy) (inflated [inflate])
PARSE: inflate theme boy DONE
(A cat) (investigated [investigate])
PARSE: investigate agent cat DONE
43

---

Published as a conference paper at ICLR 2023
(A girl) (jogged [jog])
PARSE: jog agent girl) DONE
(A chicken) (juggled [juggle])
PARSE: juggle agent chicken DONE
(A penguin) (knew [know])
PARSE: know agent penguin DONE
(A mouse) (laughed [laugh])
PARSE: laugh agent = mouse ) DONE
(A mouse) (napped [nap])
PARSE: nap (agent mouse) DONE
(A professor) (noticed [notice])
PARSE: notice agent professor) DONE
(A bee) (nursed [nurse])
PARSE: nurse (agent bee ) DONE
(A dog) (observed [observe])
PARSE: observe agent dog ) DONE
(A frog) (packed [pack])
PARSE: pack agentt = frog ) DONE
(A kid) (painted [paint])
PARSE: paint agent kid) ) DONE
(A dog) (reddened [redden])
PARSE: redden themm dog DONE
(A pig) (rolled [roll])
PARSE: roll theme pig DONE
(A queen) (ran [run])
PARSE: run aagent queen DONE
(A butterfly) (scoffed [scoff))
PARSE: scoff agent= = butterfly) DONE
(A dog) (screamed [scream])
PARSE: scream agent dog DONE
(A boy) (saw [see])
PARSE: see agent boy DONE
(Julian) (shattered [shatter])
PARSE: shatter (theme Julian) ) DONE
(A cookie) (shortened [shorten])
PARSE: shorten tteme cookie DONE
(A boy) (sketched [sketch])
PARSE: sketch agentt boy DONE
(A soldier) (slept (sleep))
PARSE: sleep agent soldier) DONE
44

---

Published as a conference paper at ICLR 2023
(A raisin) (slid [slide])
PARSE: slide ttheme raisin) DONE
(A champion) (smiled [smile])
PARSE: smile agent champion) ) DONE
(A chicken) (smirked [smirk])
PARSE: smirk agent = chicken) DONE
(A donut) (snapped [snap]) PARSE: snap theme donut) DONE
(A tenant) (sneezed [sneeze])
PARSE: sneeze aggent = tenant) DONE
(A student) (snoozed [snooze])
PARSE: snooze agentt student) DONE
(A girl) (snored [snore])
PARSE: snore aggent girl) ) DONE
(A boy) (split (split))
PARSE: split (teme = boy) DONE
(A monster) (studied (studyl) PARSE: study agent monster DONE
(A girl) (stuttered [stutter]) PARSE: stutter ( agent= = girl) DONE
(A crocodile) (talked [talk]) PARSE: talk agentt crocodile ) DONE
(A baby) (walked [walk])
PARSE: walk agent baby DONE
Once the sentences are fully decomposed, COGS only contains only 9 different types of verb phrases. We select for the pool 3 examples for each of them, which adds another 27 exemplars to the pool (see below) and hence results in pool size of 89 exemplars in total.
(The girl) (fed [feed]) (the dog) (the mandarin) PARSE: feed (agent= girl. recipient = dog. theme mandarin DONE
(The cat) (gave (give]) (the host) (the yogurt) PARSE: give (agent cat, recipient host, theme yogurt) DONE
(The mouse) (loaned [loan]) (the turkey) (the chalk)
PARSE: loan agentt mouse, recipient turkey, theme chalk ) DONE
(The creature) (wired [wire]) (the cake) to (the giraffe)
PARSE: wire (ggent "creature, theme cake recipient giraffe ) DONE
(The sailor) (gave [give]) (the bucket) (the chicken)
PARSE: give (agent sailor, theme bucket, recipient chicken DONE
(The chicken) (brought [bring]) (the pen) to (the consumer)
PARSE: bring agent chicken, theme pen, recipient = consumer ) DONE
(The cat) (was awarded [award]] (the pencil)
45

---

Published as a conference paper at ICLR 2023
PARSE: award recipient cat, theme pencil) DONE
(The lion) (was given [give]) (the cake) PARSE: give rrecipient lion, theme cake ) DONE
(The coach) (was lended [lend]) (the balloon) PARSE: lend rrecipient "cachh theme balloon) DONE
(The frog) (was mailed [mail)) (the ball) by (the child) PARSE: mail (recipient frog. theme ball,, agent child) ) DONE
(The dog) (was given [give]) (the cookie) by (the duck)
PARSE: give (recipient dog. theme cookie, agent * duck) DONE
(The prince) (was passed [pass]) (the box) by (the president) PARSE: pass recipient prince, theme box, agent president DONE
(The doll) (was awarded [award]] (the consumer) PARSE: award theme doll, recipient consumer DONE
(The donut) (was given [give]) to (the teacher) PARSE: give (theme donut, recipient teacher DONE
(The balloon) (was wired [wire]) to (the giraffe) PARSE: wire (theme balloon. recipient giraffe DONE
(The bat) (was given [give]) to (the girl) by (the governor) PARSE: give theme = bat, recipient girl, agent governor DONE
(The cake) (was posted [post]) to (the hero) by (the donkey) PARSE: post theme cake recipient hero agent donkey DONE
(The block) (was given [give]) to (the teacher) by (the butterfly) PARSE: give ttheme block, recipient teacher, agent butterfly) ) DONE
(The pig) (liked [like]) (the zebra)
PARSE: like aggent pig theme zebra ) DONE
(The baby) (missed [miss]) (the cake) PARSE: miss agent baby. theme cake DONE
(The creature) (appreciated [appreciate]] (the present) PARSE: appreciate (agent= creature, theme present DONE
(The cake) (was found [find]) by (the teacher) PARSE: find theme cake. agent teacher ) DONE
(The seed) (was eaten [eat]) by (the coach) PARSE: eat tteme seed agent coach DONE
(The donut) (was inflated [inflate]) by (Aiden) PARSE: inflate theme donut, agent Aiden ) DONE
(The shirt) (was liked [like])
PARSE: like theme shirt) DONE
(The rose) (was discovered [discover]) PARSE: discover (them rose DONE
46

---

Published as a conference paper at ICLR 2023
(The raisin) (was frozen [freeze]) PARSE: freeze ( (theme raissn) DONE
B.2.2 EXEMPLAR MATCHING
For matching, we use essentially the same heuristics as we used for CFQ with slightly adjusted pa- rameters. In particular, only look at the inner-most subelause when selecting exemplars. This is sufficient because the handling of the nested subclauses and nested prepositional clauses is demon- strated with static prompt that provide in addition to the dynamically selected exemplars (see Section B.3 below).
If the inner-most subclause has a subject but no object (e.g.. "a donut snapped"), we select the exemplar for the verb of this subclause, which is either unaccusative or unergartive. This tells the model whether the subject should be annotated as the agent the theme (e.g., since "snap" is unaccusative "a donate" is annotated as the theme). If the inner-most subclause has both subject and an object, we select exemplars corresponding to the subclause structure.
Example 1. In our first example "James said that a manager liked that Aiden appreciated that Emily believed that the girl posted cake beside table by Olivia .", the inner-most subclause "the girl was posted a cake by Olivia", which means that we select the following three exemplars:
Q: (The frog) (was mailed [mail)) (the ball) by (the child)
A: PARSE: mail recipient frog. theme ball, agent child) DONE
Q: (The dog) (was given [give]) (the cookie) by (the duck)
A: PARSE: give rreiipient dog theme cookie, agent duck) ) DONE
Q: (The prince) (was passed [pass]) (the box) by (the president)
A: PARSE: pass recipient prince, theme box agent president) DONE
In second example "The boy shortened the donut beside the bed in the car in the garden the can on the tree :" the inner-most subclause is "the boy shortened the donut", which means that select the following three exemplars:
Example 2.
Q: (The pig) (liked [like]) (the zebra)
A: PARSE: like agentt pig theme zebra DONE
Q: (The baby) (missed [miss]) (the cake)
A: PARSE: miss (agent baby, theme cake DONE
Q: (The creature) (appreciated (appreciate)) (the present)
A: PARSE: appreciate (agent = creature, theme present) ) DONE
B.3
COGS SOLUTION: DETAILS AND PROMPTS
we linearize the composition tree into sequence of sentences that correspond to increasingly complex subproblems. Like with CFQ (see Section|A.3. this linearization performed by walk over the parse tree to obtain linear sequence of well-formed sentences. For each sentence, we then query the language model using prompt that consists of three parts.
As we discussed in Section 3.3
1. Static prompt context illustrating the composition of subclauses and prepositional phrases
2. Dynamically selected exemplars as additional context
3. Sequential subproblems.
These parts detailed throughout the rest of this section.
47

---

Published as a conference paper at ICLR 2023
B.3.1 PART 1: STATIC PROMPT CONTEXT
The compositions of subclauses and prepositional phrases are translated very systematically. Fur- thermore, because of the sequential prompting, the model only needs to perform step of comp- position at time. As consequence, it is sufficient to demonstrate this behavior with the following static prompt context that is used for all imputs. Noe that this prompt does not contain any nesting beyond level 2. Note that we again use a parsed version of the natural language sentences, which contain additional parentheses and other annotations that make easier for the model perform the translation.
Q: (the song) (needed [need]] (to help) A: PARSE: need aggent = song, xcomp help ( (agent = =" soong) )) DONE
Q: (The camera) (hoped [hope]) (to run) PARSE: hope agent camera, xcomp run agent camera DONE
Q: (the atom) (wanted [want]) (to hunt)
A: PARSE: wanted agent atom, xcomp hunt agent atom DONE
Q: (a helmet) (preferred (prefer]) (to cook)
A: PARSE: prefer agentt = helmet, xcomp = cook ( aagent = helmet) )) DONE
Q: (Fred) (expected [expect)) (to paint)
A: PARSE: expect agent Fred, xcomp paint agent Fred) DONE
Q: (A camera) (intended [intend]) (to clean)
A: PARSE: intend agent camera, xcomp clean agent camera )) DONE
Q: ((A camera) (beside) (the song)) (intended [intend]) (to clean)
A: PARSE: intend agent = camera ( nmodd.. beside song xcomp clean agent = camera (
nmod. beside song DONE
Q: (Lucas) (liked [like]) (to eat)
A: PARSE: like agent= Lucas xcomp eat agent = Lucas )) DONE
Q: ((Lucas) (in) (the helmet)) (liked [like]) (to eat)
A: PARSE: like agent Lucas (nmod. helmet). ), xcomp eat ( (agent Lucas (nmod. in
helmet) DONE
Q: (the atom) (returned [return]) (a camera) (Louise)
A: PARSE: return agentt atom, recipient camera, theme Louise DONE
Q: ((the atom) (beside) (the rino)) (returned [return]) (a camera) (Louise)
A: PARSE: return agent atom (nmod. beside rino recipient camera, theme Louise)
DONE
Q: (Liam) (returned [return]) (Noah) to (the helmet)
A: PARSE: return aggett Liam, theme Noah recipient helmet) DONE
Q: (Liam) (returned [return]) (Noah) to ((he helmet) (on) (the atom))
A: PARSE: return agent Liam, theme Noah recipient helmet (nmod... on = atomm )) DONE
Q: (the rino) (was returned [return]) (a helmet)
A: PARSE: return recipient rino, theme helmet) DONE
Q: (the rino) (was returned [retum]) ((a helmet) (on) (the camera))
A: PARSE: return ( recipient rino theme helmet (mmod... on ccamera DONE
Q: (Zoey) (was returned [return]) (the song) by (the helmet)
48

---

Published as a conference paper at ICLR 2023
A: PARSE: return ( (recipient Zoey, theme song agent helmet DONE
Q: (Zoey) (was returned [return]) ((the song) (in) (the camera)) by (the helmet)
A: PARSE: return recipient Zoey, theme song ( nmod. in camera ) agent = helmet) )
DONE
Q: (Anna) (was returned [return]] (the * TV)
A: PARSE: return ( theme Anna, recipient tv DONE
Q: (Anna) (was returned [return]) to ((the TV) (beside) (the rino))
A: PARSE: return theme = Anna, recipient tv (nmod. beside rino )) DONE
Q: (A atom) (was passed [pass]) to (Nicole) by (a camera)
A: PARSE: pass theme atom, recipient Nicole, agent camera ) DONE
Q: (A atom) (was passed [pass]) to (Nicole) by ((a camera) (in) (the song))
A: PARSE: pass (theme atom recipient Nicole, agent camera (nmod.. in = > DONE
Q: (A atom) (was wired (wire]) (a TV) by (the song)
A: PARSE: wire recipient atom, theme agent song) DONE
Q: (A atom) (was wired [wire]) ((a TV) (on) (the camera)) by (the song)
A: PARSE: wire recipient atom, theme tv nmod.... on camera agent song DONE
Q: (Noah) (hoped [hope]) that ((a atom) (was wired [wire]) ((a TV) (on) (the camera)) by (the song))
A: PARSE: hope agent Noah ccomp wire recipient atom theme tv (mmod..
camera agent = song DONE
Q: (a song) (ate [eat]) (the atom)
A: PARSE: eat agent song, theme atom) DONE
Q: ((a song) (in) (the camera)) (ate (eat)) (the atom)
A: PARSE: eat agent song ( nmodd... in camera theme atom ) DONE
Q: (The rino) (valued [value]) that (((a song) (in) (the camera)) (ate [eat]) (the atom))
A: PARSE: value agent rino, ccomp eat agent = song nmod in camera ) theme
atom DONE
Q: ((The rino (beside) (the helmet)) (valued [value]) that (((a song) (in) (the camera))
(ate [eat]) (the atom))
A: PARSE: value agent = rino nmodd... beside helmet) ccomp eat agent song (mmod..
in = camera ), theme atom DONE
B.3.2 PART 2: DYNAMICALLY SELECTED EXEMPLARS
After the constant prompt context, we add as additional context the exemplars that we dynamically selected for the given input using the process described in Section We provide these exemplars for both of our runnning examples in Section B.2.2 and do not repeat them here.
B.3.3 PART 3: SEQUENTIAL SUBPROBLEMS
After providing the static and dynamic prompt context, perform the sequential prompting. We start by appending to the prompt the simplest subproblem and send it as request to the language model. We then append the model's 's reply before append the next subproblem and make another request to the language model. This is done until we obtain the result for the final subproblem, which corresponds to the solution of the original problem.
49

---

Published as a conference paper at ICLR 2023
Example 1. For the first example ("James said that manager liked that Aiden appreciated that Emily believed that the girl was posted a cake beside a table by Olivia ")), this part of the prompt looks follows. Note that the not bolded text corresponds to answers provided by the model.
Q: (the girl) (was posted [post]) (a cake) by (Olivia)
A: PARSE: post ( recippentt "girl, theme cake, agent Olivia DONE
Q: (the girl) (was posted [post]) ((a cake) (beside) (a table)) by (Olivia)
A: PARSE: post ( rrecipient girl, theme cake (nmod. beside table ). agent Olivia DONE
Q: (Emily) (believed [believe]) that ((the girl) (was posted [post]) ((a cake) (beside) (a table)) by (Olivia))
A: PARSE: believe agent Emily, ccomp post recipient girl, theme cake Immod beside
table ) agent = Olivia) DONE
Q: (Aiden) (appreciated [appreciate]) that ((Emlly) (believed [belleve]) that ((the girl) (was posted [post]) ((a cake) (beside) (a table)) by (Olivia)))
A: PARSE: appreciate agentt = Aiden, ccomp = believe agent = Emily, coomp = post recippintt girl, theme cake nmodd beside table ) agent Olivia ) DONE
Q: (a manager) (liked [like]) that ((Aide)) (appreciated [appreciate]) that ((Emily) (be- lieved [believe]) that ((the girl) (was posted [post]) ((a cake) (beside) (a table)) by (Olivia)))) A: PARSE: like agent manager ccomp appreciate agentt Aiden ccomp believe aagent Emily, ccomp post recipient girl, theme cake nmood beside table) agent = Olivia DONE
Q: (James) (said [say]) that ((a manager) (liked [like]) that ((Aiden) (appreciated [appre- ciate]) that ((Emily) (believed [believe]) that ((the girl) (was posted [post]) ((a cake) (beside) (a table)) by (Olivia)))))
A: PARSE: say agent James ccomp like agent manager, ccomp appreciate ( agent = Aiden, ccomp = believe agentt Emily, ccomp post recipient girl, theme cake ( nmod.
beside table ). agent Olivia ))) DONE
For the second example ("The boy shortened the donut beside the bed in the car in the garden in the can on the tree ."), the sequential part of the prompt looks as follows.
Example 2.
Q: (The boy) (shortened [shorten]) (the donut)
A: PARSE: shorten agent- boy. theme donnut DONE
Q: (The boy) (shortened [shorten]) ((the * donut) (beside) (the bed))
A: PARSE: shorten aggntt boy, theme donut [mmod. beside bed DONE
Q: (The boy) (shortened [shorten]) ((the donut) (beside) ((the bed) (in) (the car)))
A: PARSE: shorten aagent boy.. theme donut ( nmod.... beside bed (mmod... car )))
DONE
Q: (The boy) (shortened [shorten]) ((the donut) (beside) ((the bed) (in) ((the car) (in) (the garden))))
A: PARSE: shorten agent = boy. theme donut nmodd beside bed nmod. in car (
nmod... in garden )) DONE
Q: (The boy) (shortened [shorten]) ((the donut) (beside) ((the bed) (in) ((the * car) (in) ((he garden) (in) (the * can)))))
A: PARSE: shorten agent = boy. theme donut Imod beside bed ( nmod. in car (
nmod.. = garden (nmod... = can) ) ))) ) DONE
Q: (The boy) (shortened [shorten]) ((he donut) (beside) ((hhe bed) (in) ((he * car) (in) ((the* garden) (in) ((the can) (on) (the tree))))))
A: PARSE: shorten agent = boy theme = donut nmod. beside bed ( Imod in * car (
nmod. in garden (mmod... in can nmod tree )))) DONE
50

---

Published as a conference paper at ICLR 2023
C CHAIN-OF-THOUGHT PROMPTING FOR CFQ
This section includes the chain-of-thought prompts introduced in Section 4 A prompt in chain- of-thought format includes intermediate steps that are processed before predicting the final answer. Although the exemplars include these intermediate steps already, the model must predict the steps for new input. Also, is assumed that the exemplar pool has not previously been annotated with chain- of-thought, so a procedure bootstrap these chain-of-though (also called rationale) is required. In practice, we can do this by annotating a small set of exemplars (in our case 5), then using these to teach the model to predict new shain-of-though through prompting. The prompt we use for bootstrapping is in Appendix C.I
For evaluation, we use prompts including a mix of exemplars, some in chain-of-thought format, and the rest in vanilla format, this allows us to keep the prompt relatively short, since chain-of- tfutughh can be verbose, often the same length or longer than the original exemplar. An example chain-of- thought prompt uused in evaluation is shown in Appendix C.2 Note, the vanilla few-shot prompts we use are similar but only includes exemplars in the vanilla format.
We only evaluate chain-of-thoughh and vanilla sho-shot prompting against CFQ, not COGS.
C.I. BOOTSTRAP PROMPT
This is hybrid prompt containing 15 vanilla input/output exemplars selected by bag-of-worde sim- ilarity with the input, and a static set of 5 exemplars manually annotated in the chain-of-though format. This prompt is used to generate new chain-of-thought for the rest of the exemplar pool. An example is shown below in reduced font size, since the thain-of-though can be verbose.
sQu Dataset:
ingut: Tho was actor that M2 starces, and MS was directed by
output: SELECT DISTINCT Px0 NHERE 280 actor EXO person starsos H2 2x0 dirccted NS
input: Mere M2 and H4 edited by male sibling of MO and dizected by XI
dirested X3 edited axo octput: SELECT count.te] [+] WEERE ! 2x0 has_gendor male 2xo aibling_ot Mt dirsetsd_by N3 KI adited_by FxO )
input: the Swedish
narxied and ra produser influensed
output: SELECT DISTINCT 7x0 NHERE 2X0 actor FXO person . 7x0 intlvencos__by 7x 7x0 has_nationalltt Swedish 7x0 narzied_to X3 FH1 produced 84 )
inpul: Mhat was produced and directed by Logemeoog fa Chinese sibling
octput: SELECT DISIINTT 7x0 WHERE 280 direeted_by 2x1 280 produced_ay 2x1 TH1 has_paticnality Chinese aiblingaf 762 7a2 cimenatoysaphaa:
input: the vas fiin director that H2 was inflecaced by and a founder of H3 and X was inflvenced by
octput: SELECT DISTINCT 7x0 WHERE 240 rsin_director X2 7xl founded 2x1 sounded 8t
parson 1xo influenced 2H1 two inficenced
input: bid H2 and Ke influmnca HI Influence HC 's child and influence a cinamszogragber rs sibling 'o sposss
octput: SELECT countie] WEERE : 7x0 child_od XD fx1 macried_to Fx2 2x2 sibling_of Fx3 Px3 a cineration diionraloggpphi oggeaphee M2 influwnced 7x0 H2 infl unnlo 7xl X2 influenced MS M6 Infl uenced Pxo 84
Influenced Pxi influenced M3
inpul: The nacried influemedd and was inflasnced by a cimenetograppee Chat N2 was disecved by and stassed
outputs SELRCT DISTINTT 7x0 WHRaR, 7x0 persor , 7x0 influenced tx) 7x0 influenced 2xl 7el cinema-ograpler .. 2xl atarsed_in H2 - 2el directed x2
nerried_te
Argutss that was written by and direaced by Fensle sibl ing of nenetoggreheer of M1
octputs SELECT DISTINTT 2xo WHERE 28o dizected_by 7xl v. PND weitten_by txl hxl haa_gendez fonale sibl in 182 . 752 ciinnntt ongatattgraaee...o MI
segut: influenced married
was influenced by a actor that edited and dirreced M3
ouiputs SELECT DISTINCT 2xd WHERE 2x0 parson. 1x0 influsmoed 2x1 v Px0 infleenseilyy tal 2xd mascied 7xl 7xl actor 7xl di rirected M3 7xt edited M2
inputs Nea disected by XB and H4 and weilten by a male wibling of
octputs SELECT count WHFRE 1 2xD hax_gender male 2x0 wibl ing HO. H2 dirested 83 M2 directed
M4 HZ westter_by by 7x0
51

---

Published as a conference paper at ICLR 2023
input: Who was inflaenced by XE influenced by M4 producer sinematographae and disectoz and influenced by H2 and N3
octput: SELECT DISTINCT Pxo WHERE PuO
PaC influenned_by aul ANO inficanced_by NI 7x0
incluenseA_by H2 200 influcncsd_ky N3 txl cinonaccarapher_of 84 7x1 directed Mt Fxll produzed H4
input: Nere
H4
and influenced spanish opouse MI
octput: SELECT count [x] WHERE 1 1x0 ias_nationaais Spantsh txo narried MI , H2 infiuenced_by 2x0 influences_Dy TXO M5 influencsd_Ry 7x0 - HS intluenced__y 7x0 M6 influcnced_By PxC
input: Nere and dirocted by and edited by cinonatographer "a Prench pazent
oulput: SELECT count [x] WBERE I 2x0 pacent_af hel 7x0 basunatioonalty Prench ?xl cinematograplar X22 by
odited_by
83 dizected_by exo MI adited_by 24o
inpul: the was filn produces whose sibling directed NS and edited N2
oulputs SELECT DISTINCT 7x0 WHRRE 7x0 fillpproducer
person 2x0 sibl ing 7xl 7xl directed
7xl adited HZ
44 Example Parsings:
Quarys that was executive produced by i directed by and edited by HL to male apausa Query Type: What => DISTINGT
There La an antity (2x0) 2x0 encity
execut produced by Mi'' male spouse 7x0 execat fvve wetperiieereeooeeeeee produued by 7x1, 7x1 hee..eender malle, Pse1
nessiedioo
2xo is diracted by Nira male spouse e> 240 directed_by 2x1
Px0l is edited by MI'x msle spouze e> 7x0 edited Pxl
Bo the parse of this query is:
Parae: GRIKCT DESPINCT 7x0 WHERE I hhd directed 7x1 7x0 eddted 7tc1 Pxc exeeut ive produced by 7xl
x1 hax_gendes nale 7xl narzied_io M41
Quaay: Ware MD H4 HS KS and H7 directed by NS execut ive produued by X01 and wille by N2
Overy Type: vere/was w> count (-)
is directed by
rectee__
NC, M6. NS, is execut live produced by X0 uc oxeoutive_ producidlby Mi, executive iesuuiiveppoooo producwdd 10, NS excecut ivve produced by HI, 86 exeaut produced by Mi, M0 exemat iive produced by MI
Ne, we, NS, 96 is weltewn X2 so No wrist Na, M6 weittenn 82, MS wristen H2, M6 written_by M2 MC, n9, No, is directed by
directed_by 83, dirested_by 83, rirested_by M3, direcsed_by
to the parsw of this query is:
Parse: SELECT count (x) WHERE
cireated_ M3 executive prosuced by written by 92 directed by MS
writzen_
directed ed M3 execaat iee produced
execut ive produced by directed MB execut ive proppeeh 301 M6
HS we seitter
written_by by M2 M? directed_by by 83 M7 executive wwt.eeeeeeeee_pppppoooo by M11 197 weitten_by M2
Qvery: Mas a Jepanese screenvrster whose pacent played HD and M. M2 Query Type: was/uere wa count (x)
There capanose ecreenwriter 17x0) -> 7x0 writer, txo has_nationality Japanase hx0't parent is Pxl played NO. and => 7xl noytd NO, 7xl portrayed
7xo chillejot
So the of this query i8: Parse: SELECT count WHERE ExO poztrayod EXO postrayed M1 writor M2 bas_nationelityy Capanese 322 child_st 7x6 )
Query: Mae prodused by 30 's editor art director produced by and Mi and cistricated by
Qvery Type: was/vere ex count (+)
Thare is an editor (2x0) of HD 7x0 edited X0
7x0 director 30 =o 7x0 ait_sireeted MC by
distributed by
M1 is produced by 2x0 => MI procuced_bty 7x0
NI ie produeed by M3 => KI produzes, by M)
produced by e> prodised_by
So the parse at this query ie:
Parse: SELECT count (+) WHERE 2w0 edited XO EXD art_dirested MO X1 distributad_Jy N2 MI produced__y 240 produced_by Hi
prosuced_ay M3
Quary: Was a siln producer 's child founded by HO and MI Query Type: wan/were <> count (x)
There child 12x0) film producss (Pd) 7x0 child_ot txt, txi pron_prod
exo zounded by and
Ex0 counded_ay nc, END sounded_ay 80
3o the parse of this query is: Parse: SBLECT count WHERS Exo toundod_by NC ExC boundod_by Hi 7x0 child_ot bxt piidurr
Query: tho Prenich cinemstographer whose sibling disected and Quary Type:
52

---

Published as a conference paper at ICLR 2023
C.2 PREDICTION PROMPT
This is an example of the chain-of-thought prompt used to predict semantic parse output on evalua- tion data. It includes 10 exemplars in the vanilla input/output format, then 5 exemplars in the chain- of-thought format. The example is shown below in reduced font size, since the chain-of-thought can be verbose.
ingul: Weew M2 and NS wiilten by HD 'a producee fa employes ta Counder and edited by suzeenme ilme outputs SELRCT count WHERE i tx0 founced 7xl 7x1 emp loyed 7x2 7x2 produced bdited_by
Pxd writer M22
wristen,ly
editeddby
written,by
irgut: Wax M2 exeruut liw producwd by H3 wdited by film editor and edited by MO fa producer execut Live promucer writer
output: SELECT count le] wHean i 7x0 execut ivv produced HG - 7x0 produced M0 7x0 wroze MC 7x1 film M2 eyy 1x0 H2 editeilyy hxl H2 wewcusive.prrreeee
MB
irgut: Nex founded by a scrmenurionn iser fa French parens and founded by M3
output: SELECT count [e] WHERS i 7x0 pa hhl i 7x0 has_nationalityy French 7xl writer H2 teanded_by 7x0 92 founded M3
irput: Sex a French film producer that was employed by HP MD
output: SELECT countle) WHERS
silm_prosuoer M0 employed MD hes_nationsiitty French
input: Mae H2 executive produced by and written by a ccrcenwriter 's Italian sibling
output: SELECT count WHERS 7x0 has mat.onaiiniii Italian two sialing_of 7x1 7xl xriter N2
peecutiv__produoo__B 2x0 writion_by Exo :
input:
Mere promucer
rounded
and M4 founded by scresnvriter and founded by 's exocutive
output: SELECT count tel WHERE 1. 7x0 a writer 7x] executive produced MI founded by 7x0 founded by x1 H2 bounder_by H2 . H2 bounder_by HI . reundes_by ExO M5 bourded_by TX1 85 tounded_ay NS 145
sounded_ M4
input: bid M2 narry screenwtster marry MS and intluence Mo is preducer octput: SELECI countl+) WHERE Ex0 produced Fxl writer infleanced 7x0 H2 narried_to Fxl narrics_to
input: Mas produced
editod silm producer employes and founder directed
octput: SELECT countie) [e] WHERE 1 1x0 founded 2xl 7xD enployed 2x1 2x1 piln_producer directed_
3H MI editad_by 7x0 Hi produced_by 222
input: was exccutive prodused by a produzer of ta prequel writton by N2
output: SELECT countle] [e] WHERE 1 7x0 produced 7xl 7x1 has_sequel NO ML excoutive_prodtredd.. 7x0 MI by M2
input: Mas HI enoloyed by M2 and eroloyed by a filn 's produces and distributoz
octput: SELECT count [+] WEERS i 7x0 distributed Pxi Ex0 produced PXI 7x1 a ciin MI employod_ay 7x0 by X2
Quexys Nea serounvriter la British parent ta parent N2 Quary Type: was/vore a> count (+)
Thore secocavritor (3x0)
writer Px0's pazent is 2xl wo 1wo parent_of ex! ful is British as tad bas_nacionality British hel's parent H2 H2 pareni_of hel
3o the parse of this query is: Parme: SELECT usant (x) WHERE 7x0 pa Pxl 2xG haagnal iunalily British 7xl writms M2 parent_of x0
Query: Waa H2 edited by Swedish film produces ra spouse and written by K3
Query Type:
count (x)
There Swedial ai film producms (2x0) w> 9x0 pilngpruducer, 2x0 has-mationality Sandish
tao's apouse is txl s> 7x0 macriad_to bxl
NO is edited hel w> 92 editwel 7x]
is
by
writien_hy
So the parse of this query in:
Parwes SELECT usant (x). WHERR 2x0 io 2xl 7xl Frinnproduewe 2x1 bosennaliconllly Saudish N2 written by
edited by
Overys Han H2 In written by and di rected by MO fas male exeecut Five producer
Query Type: was/swew count
There malu executive producer (2x01 of wa ExD wwwoutive_pcod.cod 100, has_ge male N2 is directed by 7x0 wx H2 riressed by 7x0
N2 is weilltnn by M4 wx 322 writteenby M4
in tilm M2. ti
53

---

Published as a conference paper at ICLR 2023
the parse this query
Parso: SELECT coant (+) WHERS Exo exccutive_prosaeed No 7xo bas_gender nale 192 rilm 82 direczed_by 7 XU H2 by Xi
query: was a cilm producer infieenced by costume designer 's sialing and intlaenced by MI and M2
Query Type: Nas/weze e> count (+)
There
prin_prodaeer
influwmeed
vestume dezigner's wibling 19x1) influeneedlly bdl, hel wibling_o? 2x2,
costume_deslapee
2x0 is influenesd by RI e> 7x0 influences__y X1
influenced
influwnced
so the parse of this query 1s:
Zarau: SBLECT coant (x) WHERE 2x0 prodaauee 7x0 influencetLly 7xl 2x0 influenced RI Pac influenseiLby
aiblinguot 1x2 7x2 cestune_designer
Quary: Was H3 produced by Maxisan filn preducer and produced by H2 ts star sponse ro siblind Query Type: vas/swsw
Thare Hexican film produces (2x0) 7xo rild_prodacsr, has-nationalis Mexican 200 is produced by H2ts star's spouse's sibling (2x11 as 7al sibling_of 182, 2x2 merried_to Px3, 2x3 itarred_in 12, XS produced_ly 7x0, NS by 2xt
parse
quary
Parae: SELECT up and (s) WHERE I 7x0 prlnuprdd , 9wo mouunaiionlll Bexican 1x1 wiblinggof ha2 2x2 torried_to 2x3 2x3 itarred NZ X3 prodused_ 3xo XB produced_by 2xl
Query: Maa a screenvricor M2 ra French produces
Qvery Tyge:
nsargunizttin.orragam www.:eaoonnnniiinooooooooo companies axg.picchiscboiinnsssspiiiooocco Jequired
aequired
avargannzzzzooo.ooo organizaioonnnnnnnninoo.m acquired byyln hww.sh/sss...ppsstttoooaauuuuoau company
acquired in
netilmn filmnin performanee film actillu directertiinss art dirested
netfimm film film art dinection by
int direction by child of
pepoople penson parents insfictional fictooal fictional character cinemdoogragheciiii
purentisorgg
cinematarapher.o cinemstogragky by costame, costane_Assinod costume. dosigned. directed
nefilmm cinerotogrrpphy
nedilm./ilmmmanni hifm_nastmeerrr htt__aattmee.eeiiieerr.. bessigeercootuneeeeiii Aesign Jilm
nsitiin dilm wwm.coottumeeece. Jesign
notilm director.filn film
ns nelllnn film filmtiietto
directed by
netfilm Gilm distnbuuurr films dwwtributeddsn film film. film distributor Jentribuorreluuimmhip film
distribuied
film film dittibutrrrnnneeii film film film distribttor relationship distributee nctilln editor
distributed by
nefilmm film eliied.by by
edited by
nechnsiness employer amplayeeshon husiness pomplyymen_joume person
employed
penson employment sesstrrytcchsiieee employment Jenare company netilm producer. films
emploved
produced
executive seccuive.prddued
ne execative eweeatheeeoodeeedd
enceutie.ppoduuee.. bay
nsonganization. rggamizsion.funnee fuunerranaamirriiossooooaa founded
founded
neonaniratioo organization founders
founded by
hepeople person gender
gonder_pf
nefilmaac actor filmln::iilmmmm.. wwt.:n::iim.erfrrrm.e. performance, churacter
portayed has gender
nepeople penson gonder
pepoople penson nutionality
mnnioniionaltyy
Gim prequel
prequel
neffilm aequel
seqael
neinffucece influener_node wndeeeooodennnnnee influenced
influenced
srinflumce.inllence mode influenced by
influenced by
neppople penson sponee amw.n.pooo..eeeporoe pappppplpppppppeecooooooooo mooplloaoo spouse dilciiona__mivveee fictional chamette mamried
mamiedjo
disppepllepema penson.ationality
nationality of
neppoppl penson children instiictionalluiveee universe. fictionll htt.reiiiiiol.ccaaaarerrr.e chhuratter.chikkeenn www.rrgmnccotiooccommm www.aiiiiinnannntiinniimmmm chinso/osorrgg
paremuof Jof
nelilm producer film ns film productionn Jompuny films.
proshueed
pruduced
film pendaction_oompaties
produced.bb
neppoppl penon sibling-cnssppooonn pospppplleeeepeee..mm.p... cebinggrelatiomssppp..o sibling mxc nec.fictioolllnin univene fictional hchrraatersssiiiingg
siblingaif
netfimm film starringss film performance.oss actor
stared
netilm film writen
wristen.by
netilm film
netilm actor
octor
netiil. film aemmanndiiee dirrectrr
art iineirectooo
nettilm cinemsiogragher
cinemalogmapher
alw.costumer.cesiie
cessunedessgnner
netilm director
fim.director
netfilm editor
flmuuiiturr
achusiness.cmmpee coployer
employer
netfictional fictional
fictional charasteer
nethim dilm
film
nsttilm dit.iiittbbutorr
Elm.disczibuturr
nespoople
nctiim producer
fllmgenducer
netilm producion.compuny
production.omppngg
netfilm writer
wrisr
Table 4: Mapping of freebase IDs (truncated to 120 characters) to human-readable strings. We apply this to CFQ make the task more feasible for prompting.
54

---

Published as a conference paper at ICLR 2023
D DATA PREPARATION, EVALUATION, AND HYPERPARAMETERS
D.1 CFQ PROCESSING AND EVALUATION
To make the CFQ benchmark more appropriate for processing with large language models, we use the processing steps and evaluation method detailed below. We verified that these steps do not alter the performance for fully supervised methods by reproducing experiments with T5-base. The results match previously published results within 1-2 points on MCD1, MCD2, and MCD3.
D.1.1 CFQ PREPROCESSING
To prepare the CFQ data we apply two preprocessing steps:
1. We replace excessively long freebase identifiers with human-readable strings (see Table
2. We strip FILTER statements because they always appear with the "sibling-of" and "mar- ried_to" properties, and would be trivial add the output after prediction (i.e., they can be considered to be part of the abbreviated property). For example, if "?x0 married_tt MO" appeared, then so would "FILTER(?x0 != MO)". Essentially, one cannot be married to themselves, nor a sibling of themselves.
D.1.2 CFQ POSTPROCESSING AND EVALUATION
For CFQ, apply the following post-processeee processooeegggggg to both gold and predicted semantic parses.
1. Clause sanitization: We discard any malformed clause. To measure well- folleformedeess we check all of the following. (a) clause should have white-space separated tokens; (b) A clause should either have "a" as its second token or a string, so symbols such as "=" can be safely discarded.
2. Inverse properties: For properties that have an official inverse property in Freebase (e.g. "directed" vs. "directed.by") we deterministically pick one of its variants and flip the arguments needed. However, note that in some error cases the model will predict "se- quel_of", which does not get corrected, since "sequel_of" is not in the original property vocabulary, only "has sequel" and "has prequel".
3. Argument ordering: For clauses that bidirectional ("sibling of", "married. to"), sort the arguments alphabetically.
4. Statement ordering: Since order does not matter in SPARQL statements, we sort statements alphabetically.
5. Variable normalization:
Since variable labels are arbitrary (?x0, ?x1, etc.) in SPARQL,
we re-label the variables so that they appear in increasing order. E.g., "SELECT 7x1 ?x2 directed ?xl ?xl influenced ?x0 }" gets converted to "SELECT ?x0 { ?xl directed 7x0 7x0 influenced ?x2 }". We alternate running variable normalization and statement ordering until no change is detected, since re-labeling variables might impact the sort order clauses.
6. Stripping of implied types: CFQ is constructed such that types that directly implied by accompanied relation are dropped from the SPARQL even if these types are explicitly men- tioned in the natural language question. For example, the clause "?x0 actor" is dropped from the translation of the question "Did male actor play MO and play M1" because the relation "?x0 portrayed MO" implies that 2x0 has type actor. For pretrained language model, this is quite unnatural and hurts accuracy, even though keeping the type leads to SPARQL query that semantically equivalent. We therefore strip implied types when they are predicted by the language model.
After completing these steps, we do the standard approach measuring accuracy using exact string match.
55

---

Published as a conference paper at ICLR 2023
D.2 COGS POSTPROCESSING AND EVALUATION
For longer outputs, the language model sometimes fails to match closing parentheses. When this happens, add closing parentheses at the end of output until all opening parenthesis are matched. This trivial fix improved exact match accuracy on COGS generalization test set from 97.8% to 99.2%.
It is worth noting that 50 examples in the original COGS generalization test set are mislabeled (the authors have since released a new version). We evaluate using the original data in order compare with previous work. As one would not expect model to accurately predict the idiosyncrasies associated with the mislabeled data, an upper bound on performance for the generalization test should be about 99.7% accuracy.
D.3 HYPERPARAMETER
There are two sets of hyperparameters: those for prompts and those for generation. We performed initial minimal hyperparameter tuning using 100-sentence subset of the validation data.
D.3.1
PROMPT HYPERPARAMETERS
Dynamic Least-to-Most
Described in Section 3
Number of Static Exemplars 12 for CFQ. 28 for COGS
Number of Dynamic Exemplars 4-35 for CFQ, between 1-3 for COGS (these are deter- mined automatically based on the decomposition tree)
Number of Exemplar Lists =
Number of Generations per List =
Generation Mode Greedy
Chain-of-Thought Selects exemplars according to bag-of-words similarity (Section 4.2 but to be effective, at least some of the exemplars must use rationale. To keep the prompt compact, we use hybrid approach where 5 exemplars in chain-of-thought format and the rest are vanilla.
As the original data does not have alignments, we need to manually create some chain-of-thought exemplars, which we can then use to generate chain-of-thought for the full exemplar pool (Zelikman) ct al. 2022). In our case, we manually labeled 5 sentences with chain-of -ftto-ugtthh then appended these the 15 exemplars thought for the exemplar pool, and discarded any chain-of- of-thought that did not produce the correct semantic parse. 884 out of 1000 successfully predicted the correct semantic parse. When construct- ing chain-of- prompts, we only represent an exemplar with thain-of-thought succeeded in this previous step, otherwise we use its vanilla format.
already retrieve for each sentence. We did this to predict chain-of-
Bootstrap Pool Size 5
Number of Exemplars List (k) 15
Number of Exemplar Lists (n) =4
Number of Generations per List (8) =
Generation Mode Sample
Number of Chain-of- Chain-of-Thought Thought Exemplars 5 (the other 10 are in vanilla format)
Vanilla Few-Shot Vanilla few-shot is simple input/output exemplar-bass based prompt. The exem-
plars are chosen identically chain-of-thought
Number of Exemplars List (k) 15
Number of Exemplar Lists (n) =4
Number of Generations per List (s)
Generation Mode Sample
56

---

Published as a conference paper at ICLR 2023
D.3.2 GENERATION HYPERPARAMETERS
We did not require any extensive search over these hyperparamters. tried reasonable settings based previously published works, and the only real toggle here is temperature, which wasn't t used at all by dynamic least-to-most.
Model code-davinci-000
Temperature = 0.7 when sampling, or 0.0 when greedy.
Top-P 1.0, Presence Penalty 0, Frequency Penalty =0
E ADDITIONAL ANALYSIS
E.1 INITIAL PROMPTING ATTEMPTS FOR CFQ
We initially tried various prompting attempts for CFQ where we did not provide any examples as part of context. Instead, we provided an instruction along the lines of, "Translate English to SPARQL". While the language model was still able to produce SPARQL-like output, it scored 0% accuracy on CFQ. This indicates that the language model was exposed to SPARQL in pretraining memorized specific CFQ examples.
but has
Translate English to SPAROL.
English: What did production company 's Japanese founder direct cdit and exccutive produce
SPAROL:
SELECT 2di rector ?editor Pexecutive_produeet
WHERK {
?director dbo:Filmbirestor:
?director abo:nationality dbr:Japan
?director abo:birthPlace dbr:Japan
?directer dbo:birthDate ?birthCate
FILTER (?birthDate < "1940-01-01100 00: 008"0 "xs:
?directer dbo:film ?film
?film abo:editor ?editor
?film dbo:executiiveProdiee 2executive_produee,
Wrong property / ttpe
Cartesian product
Property direction
Entity reference
Acc.
Type
Full dynamic L2M (0)
94.6
6
5
3
Delta highlights (a)
93.8
4
Decomposition hints (b)
92.4
14
Question grounding (c)
79.2
12
1
BoW exemplars (d)
92.2
9
Constant exemplars (c)
79,9
2
7
10
50% decomposition (fl)
88.8
12
2
2-step decomposition (f2)
83.2
9
10
No decomposition (f3)
75.2
1
Table The first column is accuracy for various 1-step ablations of dynamic least-to- to-tsst prompt- ing on CFQ, measured on a 500-example subset of MCD1 test set. The other columns show error analysis. For the top row, we look 20 random samples where the model was incorrect, assigning each to a category. The other rows are similar, except measured on errors introduced by the ablation.
57

---

Published as a conference paper at ICLR 2023
E.2 DYNAMIC LEAST-TO-MOST PROMPTING ON CFQ: ABLATIONS AND ERROR ANALYSIS
Here we include 1-step ablations of the most important components of the dynamic least-to-most method (explained in detail in Appendix A.3) These components are:
Delta highlights textual hints (such "# Extend the answer above. Add: ..." and "#
Copy the answer from above.") that highlight the change between subsequent subquestions.
Decomposition hints are parenthesis that we add the natural language questions to indi- cate the syntactic parse.
Question grounding is a constant prompt prefix that illustrates to the model how to trans- late the most basic subquestions.
Exemplar selection. Bag of words (BoW) exemplar selection is alternative method to select relevant exemplars. Instead of using the parse tree, aims to cover with exemplars many words as possible of the target question. Constant exemplars uses static set of exemplars for all questions (i.e., no dynamically selected exemplars).
Decomposition granularity. No decomposition does not decompose the question at all, which means that then use standard prompting rather than cast-to-most prompting. 2- step decomposition decomposes the question into at most 2 steps, while 50% decomposition keeps half the decomposition steps of the most granular decomposition.
The second column of Table 5 shows the accuracies of these ablations 500-example subset of MCDI. It turns out that ablating delta highlights (93.8% accuracy) and decomposition hints (92.4% accuracy) only lead cause relatively small change to the overall prompt. Ablating question grounding on the other hand leads to a much larger regression (79.2% accuracy). The reason for this is that the partial exemplars turn out to be important for the model to correctly translate the first subquestion. The performance of the other ablations are discussed in Section 6
small regression. This matches intuition because these components
In addition to the accuracies, Table Sable5aasse also contains qualitative error analysis. For the baseline (first row), we analyzed 20 random errors. For each of the ablations, we analyzed 20 errors that were caused by the ablation (i.e., the examples were correct in the baseline). We make the following observations:
Delta highlights (a) and BoW exemplar selection (d) have similar error profile as the baseline. Property direction is bit more prominent for BoW exemplar selection, which indicates that we do not always retrieve exemplars that illustrate the property in as much detail as in the baseline.
Decomposition hints (b) mostly help with cartesian products, which makes sense because they make it easier for the model to understand the grouping and connections between the various words of a question.
Question grounding (c) helpw a lot with types, which is the primary reason why we added them.
Using constant exemplars (e) leads to lot of issues with wrong properties/types and prop- erty direction. This makes sense since the constant exemplars cannot illustrate all properties and types that used in the dataset.
Reducing the decomposition granularity (f1, f2, f3) mostly leads to problems with types and cartesian products. Especially the issues with cartesian products are be expected because decomposition allows the model to unfold those incrementally.
Below, we provide a few examples to illustrate the different error buckets.
Unnecessary or missing types
Question: What Dutch spouse of M2 was MO 's employee and founder Answer: SELECT DISTINCT ?x0 WHERE ?x0 person. ?x0 married.to M2. ?x0 founded MO. ?x0 employed by MO ?x0 has nationality Dutch }
Golden:
SELECT DISTINCT ?x0 WHERE ?x0 founded Mo ?x0 employed by MO ?x0
58

---

Published as a conference paper at ICLR 2023
has-nationality Dutch. ?x0 married.to M2)
Who writer, costume designer editor, and star of M1 and M2 Answer: SELECT DISTINCT ?x0 WHERE { ?x0 starred in M1 ?x0 starred M2. ?x0 wrote M1
Question:
?xO wrote M2 ?x0 edited M1 ?x0 edited M2. ?x0 costume costume_designed M1 ?x0 costume_designe
M2
Golden: SELECT DISTINCT ?x0 WHERE ?x0 person. ?xo starred. in M1 ?x0 starred .n M2.
?x0 edited M1. ?x0 edited M2. ?x0 costume costume.designed M1 ?x0 costume costume.desigme designed M2. ?xO wrote
M1 ?x0 wrote M2)
Incorrect cartesian product
Question: Did M1 's costume designer cinematographer
director art director
producer
and editor produce, write, and edit MO
Answer: SELECT count(") WHERE ?x0 directed M1 ?xo executive executive_produuee MO ?xo edited
MO ?x0 wrote MO ?x0 cinematographer..og _of M1 ?x0 costume destigeed M1 ?x0 produced M1
Golden: SELECT count(") WHERE ?x0 ainematographer of M1 ?x0 directed MO ?x0 directed
M1 ?x0 edited MO ?x0 costume designed M1. ?xt executive produccdddddd MO ?xO produced M1
?x0 wrote MO
Question: Did M2 editor
director star art director and cinematographer produce
rect, and edit MO and M1
Answer: SELECT count(") WHERE { ?x0 edited MO ?x0 edited M1 ?xD directed MO ?x0
directed M1 ?x0 produced MO ?x0 produced M1 ?x0 starred in M2. ?x0 art directed M2. ?x0
cinematographer of M2
Golden: SELECT count(") WHERE { ?x0 starred_in in M2. ?x0 cinematographer.oo of M2 ?x0 directed
MO ?x0 directed M1 ?x0 directed M2 ?x0 edited MO ?x0 edited M1 ?x0 edited M2. ?x0
art.directed M2. ?x0 produced MO ?x0 produced M1
Wrong property direction
Question:
Which actor that cinematographer was influenced by was M1 's spouse
Answer: SELECT DISTINCT ?x0 WHERE ?x0 actor ?x0 married.to M1 ?x0 influenced.bt by ?x1 ?x1 cinematographer
Golden: SELECT DISTINCT ?x0 WHERE ?x0 a actor ?x0 influenced ?x1 ?x0 married to M1 ?x1 cinematographer
Question: What prequel of MO was executive produced written directed duced by M1
edited and pro-
Answer: SELECT DISTINCT ?x0 WHERE { ?xx has prequel MO ?x0 executive produced by M1
?x0 produced by M1 ?x0 edited by M1 ?x0 directed by M1 ?x0 written.by M1
Golden: SELECT DISTINCT ?xo WHERE { ?x0 directed_br by M1 ?xo edited by M1 ?x0
Deocutive_producce by M1 ?x0 produced.by M1 ?x0 has_seque MO ?x0 written.by M1
Wrong property/
type
Question: Was a film director 's child MO 's cinematographer Answer: SELECT count(") WHERE ?xx0 child.of ?x1. ?x1 a film_director. ?x0 cinematographed
MO
Golden: SELECT count(") WHERE {
?x0 cinematographer of MO ?x0 child ?x1 ?x1
film_director }
Question: Was company whose employee wrote M2 M1 's employer
Answer: SELECT count(") WHERE ?x0 a company ?x0 employed M1 ?x0 employed ?x1
?x1 wrote M2
Golden: SELECT count(") WHERE { ?x0 a employer. ?x0 employed ?x1 ?x0 employed M1 ?x1
wrote M2] }
59

---

Published as a conference paper at ICLR 2023
Mixing up entity references
Question:
What costume designer was film director Canadian female parent
Answer:
SELECT DISTINCT ?xo WHERE { ?x0 a costume designer ?x0 film director ?x0
has_gender female ?x0 has_ nationatnyyl Canadian. ?x0 parent_of ?x1
Golden: SELECT DISTINCT ?x0 WHERE ?x0 a postume_deiigne ?x0 parent.of ?xt ?x0
has has. ganderndr female ?x0 has nationaliiy Canadian. ?xt film | }
Question: Did a male actor whose spouse married M2 play MO
Answer: SELECT count(") WHERE ?x0 portrayed MO ?x0 married to ?x1 ?x1 married to M2.
?x1 a actor ?x1 has gender male }
Golden: SELECT count(") WHERE {
?x0 portrayed MO ?x0 has.gender male ?x0 married_to
?x1
?x1 a actor ?x1 married.to M2
E.3 FAIR COMPARISON AGAINST OTHER PROMPTING TECHNIQUES
In the comparison in Figure vanilla few-shot and chain-of-thought prompting have an advantage
over least-to-most prompting because we sample multiple exemplar lists (n = 4) and multiple outputs per list which are aggregated using self self-consistency. When using n and with greedy decoding, the comparison between these prompting techniques and dynamic least-to-most is more fair, and the benefits of dynamic least-to-most are more prominent. Chain-of-though achieves 75,4% accuracy (down from 37.2%), and vanilla few-shot achieves 69.8% accuracy (down from 80.8%). Dynamic least-to-most substantially outperforms both of these without using self-consistency, and achieves 94.6% on the same 500-sentence subset of MCD1 I validation data.
using temperature-biic based decoding. This yields
16 outputs per input,
F REPRODUCIBILITY SUMMARY
At all points in this work, we aim to make our methods and experiments easily reproducible, and hope findings will have impact in part through others using the same similar methods for new tasks. Here we summarize critical components of our work and where their relevant details are described:
Main Prompts: In lieu of code, we provide the exact prompts that executed obtain model predictions. Prompts for CFQ: syntactic parsing (Appendix I) dynamic least- to-most (Appendix A.3). Prompts for COGS: syntactic parsing (Appendix B.I). dynamic lcast-to-most (Appendix [B3)). Exemplars are chosen using the methods described in Sec- tion 3.22 and Appendix [f. (Apendix(A.2
CFQ) and Appendix B.2 (for COGS). The prompts include the exemplars found from a concrete input.
Additional Prompts: We only use vanilla few-shot and chain-of tffthughtt to compare against dynamic least-to-most on CFQ. The mfain-of-though, prompt used bootstrap rationale is in Appendix C.1 and the one used for evaluation data is in Appendix C.2) The prompt includes the exemplars found from a concrete input. The vanilla few-shot prompt sim- ilar, but all examples use the vanilla input/output format. Exemplars are chosen using the methods described in Section 4.2
Dataset Preparation and Evaluation: We performed both pre-processing and post- processing output normalization step in order to make semantic parsing with freebase iden- tifers more feasible for prompting. Described in Section 5.1 Appendix [D..1]] D.1.2 D.2
Exemplar Pool: Methodology for constructing exemplar pools is described in Section 3.2
Hyperparameters: We didn't require any extensive hyperparameter search. The hyperpa- rameters we used are described in Section 5.2 and Appendix [D3
3.2
60


Reviews:
[{"review_id": "_dfHr88iI6", "reviewer": "Reviewer_gAic", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors first perform decomposition by dividing the syntactic parsing task into multiple steps and provide LMs with exemplars that illustrate the task to be performed. They then choose an exemplar pool with 1000 examples on CFQ and 89 for COGS. And they select for each input between 4 and 35 exemplars for CFQ and between 1 and 3 exemplars for COGS. They highlight the effectiveness of such compositional ability and set new SOTA results for CFQ while requiring only 1% of the training data used by traditional finetuning approaches. ", "summary_of_the_review": "This paper is working on a natural language semantic parsing benchmark, and the authors provide a dynamic version of least-to-most prompting to show promising generalization ability. ", "strength_and_weaknesses": "S:\n* The paper is well-written, well-motivated, and easy to follow.\n* The Dynamic least-to-most prompting is a good idea that it first sequentially predicts solutions to subproblems before generating the final output, where the subproblems are extracted through different prompts.  \n\nW:\n*There is no obvious weakness in this work, given the improvement and effectiveness of 1% data is very promising. \n* One minor thing could be there is no analysis between task complexity (for example, number of tokens, number of vocabulary, number of decomposed subquestions) and performance. Another minor thing is that there is no study on how sensitive the Codex model is to the data preprocessing used in the work as shown in the Appendix.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "PViJwW-np3P", "reviewer": "Reviewer_P921", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers compositional generalization and proposes a \"dynamic least-to-most prompting\" method to tackle the problem. \"dynamic least-to-most prompting\" consists of three steps: decomposition using syntactic parsing, dynamic exemplar selection, and sequential solution. The experiment results are impressive: on CFQ dataset, the proposed algorithm beats all the existing baselines while using much less training data. On COGS, although the performance is a little bit lower than one of the baseline, the number of training data used is much less.", "summary_of_the_review": "I am not very familiar with this sub-field, and thus based on my evaluation, I think this paper is interesting and make some contribution to compositional generalization. The paper is well written and the comparison with the previous work seems enough to me. Besides, the numerical experiments show the effectiveness of the proposed method.", "strength_and_weaknesses": "Strength:\n\n1. The idea used seems new and interesting.\n2. The experiment results are very good and impressive.\n\nWeakness:\n1. I suggest the authors also include the baseline results using the same number of training data as the proposed methods for a better comparison if possible.\n2. For the syntactic parsing part, although the experiment results of the proposed method is very good, it is not clear why we should use LM to parse instead of the more \"classical\" ways like training a PCFG like model. In fact, the paper from Qiu et al. uses the QCFG model to \"parse\". Is LM perform better? or it is much more sample-efficient? or it is much simpler?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "M5Pl203Ijl", "reviewer": "Reviewer_WSSM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Compositionality is an important ability of a model and in this paper, the authors propose to achieve such capacity by using a novel method inspired by least-to-most prompting. It addresses two practical challenges for applying least-to-most prompting:\n1. how to decompose the questions to generate least-to-most prompting\n2. In practice the uttererances can vary a lot, so how to choose prompt from a large pool\n\nBy addressing the above difficulties, the athors propose an s enhanced least-to-most prompt tuning method; empirically, the authors achieve SOTA/near SOTA performance for two popular compositionality bench marks COGS and CFQ.  ", "summary_of_the_review": "The paper tackles how to achieve semantic parsing compositionality using least-to-most prompt tuning. It addresses two practical challenges that are 1) how to decompose a sentence in this case 2) how to dynamically choose the best examplars. The paper gives clear motivation and intuition about the proposed methods and achieve convincing results for two challenging complex semantic parsing tasks focusing on compositionality. \n\nOn the downside, the paper doesn't study closely for its technical choices, the decomposition alone is quite complicated (i.e. Appendix A.1 and B.1) and the paper doesn't mention how important and why such choices matter for the end performance; I don't see detailed ablation analysis for examplar choosing algorithms either and there are limitations of the methods shown by the implementation (e.g. manually choosing some examplars). \n\nPS: I have read the authors' comments, thanks a lot for authors to give detailed comments as well as new experimental results. My two main concerns (how to choose examples and ablation studies about the decomposition) have been answered in detail. The paper clearly has its own merits; however, I found the paper doesn't dive deep enough in its decomposition choices (e.g. Reviewer P921 mentioned a possiblity to apply syntactic parsing to do decomposition) and I am convinced that the manual step can be applied to other tasks but is also incurs cost so not sure if such appraoches will be easily widely adopted. I would not change my score although I sincerely appreciate the informative and constructive discussions. ", "strength_and_weaknesses": "Strength:\n1. The paper has clear motivations to achieve compositionality for more real-life settings\n2. The proposed method addresses practical concerns\n3. The method shows great performance in two real-life like datasets (compared to SCAN)\n\nWeakness:\n1. The paper consists mainly an application of least-to-most prompt tuning method with relatively standard NLP techniques\n2. The ablations studies of the paper's contribution (sentence decomposition and dynamic prompt selection is missing from the main paper). The question that leave readers are for example: what is an effective sentence decomposition? what is the performance with no setntence decomposition but just some dynamic prompting? What about simpler prompt selection method?\n3. For CFQ dataset, the paper mentions that they use a list of manually chosen examplars (e.g. footnote 3), this limits a bit the applicability of the proposed method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IdknAFkO6we", "reviewer": "Reviewer_e27M", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends the least-to-most prompting technique to solve more realistic semantic parsing tasks. Specifically, the approach works as follows:\n\n1. Prompt a large language model with examples to perform syntactic parsing of the input sentence and decompose it into increasingly simpler parts\n2. Select relevant examples based on the decomposition obtained in 1\n3. Prompt the large language model with the relevant examples obtained in 2 in order to solve the task on all parts of the input (according to the decomposition found in 1), starting from simple parts and ending with the full input sentence.\n\nThe paper shows positive results on the CFQ and COGS datasets while only selecting examples from a small subset of the training data (e.g., 1%).", "summary_of_the_review": "I believe this paper is overall worthy of publication thanks to novelty and good results.", "strength_and_weaknesses": "Strength: this paper introduces a novel extension to least-to-most prompting with several improvements: tree decomposition; example selection to fit more relevant examples into the prompt (in realistic cases, the label space is too large to be able to fit examples for everything); subproblems are solved by giving context to the model. The results shown on CFQ and COGS are very good.\n\nWeakness (addressed in rebuttal): The approach requires dataset-specific prompts (for syntactic parsing) and heuristics (for exemplar selection). It is unclear how much the final performance depends on the details of the prompts/heuristics and how much the reported results overfit to these choices. Also, it looks like a lot of manual effort is needed if one wants to apply this method to a new dataset.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster