Complexity-Based Prompting for Multi-step Reasoning
Authors: Yao Fu
Hao Peng
Ashish Sabharwal
Peter Clark
Tushar Khot
Venue: ICLR 2023 poster (2023)
Keywords: Chain-of-Thoughts
Multi-Step Reasoning
Large Language Models
Prompting

Abstract: We study the task of prompting large-scale language models to perform multi-step reasoning. Existing work shows that when prompted with a chain of thoughts (CoT), sequences of short sentences describing intermediate reasoning steps towards a final answer, large language models can generate new reasoning chains and predict answers for new inputs. A central question is which reasoning examples make the most effective prompts. In this work, we propose complexity-based prompting, a simple and effective example selection scheme for multi-step reasoning. We show that prompts with higher reasoning complexity, i.e., chains with more reasoning steps, achieve substantially better performance on math word reasoning tasks over strong baselines. We further extend our complexity-based criteria from prompting (selecting inputs) to decoding (selecting outputs), where we sample multiple reasoning chains from the model, then choose the majority
of generated answers from complex reasoning chains (over simple chains). When used to prompt GPT-3, our approach substantially improves multi-step reasoning accuracy, with an 8.6% absolute improvement on GSM8K, and 6.4% on MathQA. Compared with existing example selection schemes like manual tuning or retrieval-based selection, selection based on reasoning complexity is intuitive, easy to implement, and annotation-efficient. Further results demonstrate the robustness of performance gains from complex prompts under format perturbation and distribution shift.

Published as a conference paper at ICLR 2023
COMPLEXITY-BASED PROMPTING FOR MULTI-STEP REASONING
Yao F "Hoo Long*,Ashist Sabharwal Peter Clark*, Tushar Khot*
Allen Institute for AI yao.fu @c..ac.uk, frop@allenai.org, ashishs @ allenai.org, peterc@allenai.ogg tushark @ @llenai.org
University of Edinburgh
ABSTRACT
We study the task of prompting large-scale language models to perform multi- step reasoning. Existing work shows that when prompted with a chain thoughts (CoT), sequences of short sentences describing intermediate reasoning steps towards a final answer, large language models can generate new reasoning chains and predict answers for new inputs. A central question which reasoning examples make the most effective prompts. In this work, we propose complexity- based prompting, a simple and effective example selection scheme for multi-step reasoning. We show that prompts with higher reasoning complexity, i.c., chains with more reasoning steps, achieve substantially better performance on multi- step reasoning tasks over strong baselines. We further extend our complexity- based criteria from prompting (selecting inputs) to decoding (selecting outputs), where we sample multiple reasoning chains from the model, then choose the majority of generated answers from complex reasoning chains (over simple chains). When used to prompt GPT-3 and Codex, our approach substantially improves multi-step reasoning accuracy and achieves new state-of-the-ar (SOTA) performance three math benchmarks (GSM8K, MultiArith, and MathQA) and two BigBenchHard tasks (Date Understanding and Penguins), with an average +5.3 and up +18 accuracy improvements. Compared with existing example selection schemes like manual tuning or retrieval-based selection, selection based on reasoning complexity is intuitive, easy to implement, and annotation-efficcent. Further results demonstrate the robustness of performance gains from complex prompts under format perturbation and distribution shift.
INTRODUCTION
We consider the problem of prompting large language models for multi-step reasoning. Recent breakthroughs (Wei et al.) [202bb] Wang et al. (022b) show that language models, when large enough (> 100B parameters), exhibit the emergent ability (Wei et al.) (022a) of performing complex multi-step reasoning when provided with only a few reasoning examples. In the regime of large models, prompting achieves comparable or even better performance than full training set finetuning while being substantially more sample-efficient (Wei et al., 2022b Kojima et al. [022 Lewkowycz et al. (022). In particular, Wei et al. (2022b) show that chain-of-thee of-thoughts (CoT) prompts, sequences of short sentences describing intermediate reasoning steps towards final answers (Fig. [T],, can elicit strong reasoning capabilities from large language models for complex tasks such math problems.
This work studies example selection in -fthoughss multi-step reasoning. Example selection is central problem in the prompting literature (Liu et al., 2022 Rubin et al. 2022 Su al. 2022 Lazaridou et al.] (022). asks what instances make the best prompts for solving the tasks of interest.
For CoT prompting, example selection is further related to annotation efficiency, as CoT requires manually-annotated reasoning chains. For datasets where reasoning annotations are easy to obtain, one may want know which annotated chains make the best prompt; if the annotations hard to obtain, one may identify the best cases to annotate, rather than annotating the entire dataset.
Work done during internship Allen Institute for AI, code at https: thub. cotp:/aaa//axaa/////// Complexx exi ty- sed- Prompting

---

Published as a conference paper at ICLR 2023
Asia bought a homecoming dress on sale for $140. was
Angelo and Malanie want to plan how many hours how manty days should they plan to study total over the next week if they take 10-minute break every hour ...?
CoT prompt Question
Question
originally priced $350.
What percentage off did she get the sale?
Semple
Thoughts prompt
Chain
1. Asia saved $350 - $1140 $210 the dress.
1. Angelo and Melanie think they should dedicate 3 hours to each of the chapters...
Pecasoning E, stops, answer - 200
2. That means she saved $210 /
2. the warksheets they hours for each workaheet...
dedicate
Reasoning steps, answer 200
$350 0.60 60% dress.
Ressoning A. steps, anewer = 100
a. Angelo and Melanie need start with planning 12 hours to study, at hours day. 12 4 days.
Rlessoning B, steps, answer
Answar
The answer is 60
Reesening Booopr
more CoT cases
more reasoning steps
Test Question
Olivia has $23. She bought five bagels for $3 each. How much money does have loft?
8. They want to study no more than 4 hours each
day, 15 hours 4 hours each day = 3.75
Majority voting complex chains
They need to plan study days allow for all the time they need.
<GPT3 generates from here
The answer
Majortty 200
A. Workflow of chain thoughts prompting
Example complex chain, 9 reasoning steps
C. Complexity-based consistency
Figure I: A: Chain of thoughts (in blue) are intermediate reasoning steps towards a final answer. The input of CoT prompting is stack of few (often 8) CoT cases before a test question. Then the language model will continue generating an output CoT for the test question. B: Chains of harder reasoning complexity are chains with more reasoning steps (9 steps in this case, v.s. only 2 steps in subfigure A). C: During decoding, we sample N reasoning chains from the language model (N here), and take the majority answer over the K (K 3 here) most complex generated chains.
We propose complexity-based prompting, a new example selection scheme for chain-of-thoughts multi-step reasoning. Existing sample selection methods are usually based on manual tries (Wei al., (2022b), heuristic rules @Wallace et al. 2019). optimization and search (Shin al., 2020). or retrieval from a large training set (Rubin et al. 2022). Different from these schemes, complexity- based prompting chooses examples with complex reasoning chains, i.e., chains with more reasoning steps, as the prompt. Fig. TA shows a simple example with 2 reasoning steps, versus the example in subfigure a complex case with 9 reasoning steps. As we will show in the experiments ($4.2). the reasoning performance of GPT-3 175B (Brown et al. 2220)) clearly improves with the increased input prompt complexity, where complex prompts achieve better performance than simple prompts.
We further extend the complexity-base based selection criteria from the input space (the prompts) to the output space (reasoning chains generated by the language model). Our extension is based on the idea of self-consistency (Wang et al. [2022bja a), where they sample multiple reasoning chains (instead of using greedy decoding) from the model that lead to possibly different answers, then choose the majority of the generated answers. Here we propose complexity-based consistency, where instead of taking a majority vote among all generated chains, we vote over the top K complex chains, as shown in Fig. CC. In 4.2] we will show that complexity-based consistency leads to further performance gains, on top of the existing gain from complexity-bar based prompting.
Putting everything together. our methods achieve new state of the art performance on three math benchmarks (GSM8K, MultiArith, and MathQA) and two BigBenchHard tasks (Date Understanding and Penguins) with substantial performance gains over Wei et al. (022b)) We show that, compared with existing sample selection schemes, complexity-basee based prompting achieves better performance in most cases (see $4.2). Furthermore, performance gains from complex samples are consistent in different prompt distributions (in-distribution, transfer, and noisily-labeled, see $4.2) and are also consistent with regard to alternative proxies for complexity (e.g., question or formula lengths, see (4.3) when the dataset does not contain annotated reasoning chains. A careful analysis shows that the number of reasoning steps is the most prominent factor, over confounders like prompt lengths or the number of input cases ( (4.3) We hope this work will open new research possibilities in in-context learning, large language models, and multi-step reasoning.
RELATED WORK
Emergent Abilities and Multi-Step Reasoning With the recent trend in scaling language models (Brown et al. 2020 Chowdhery et al. 2022). central question is what unique abilities
2

---

Published as a conference paper at ICLR 2023
emerge models become large (Kaplan et al. 2020 Wei et al. 2022a). Generally, the ability to follow the format of given prompts (typically few-shot) thus solving the corresponding tasks (also referred as in-context learning), is something that large language models are particularly skilled at (Shin et al. 2020 Liu et al. 2021). Among the wide language understanding task spectrum, particularly interested multi-step reasoning because of its uniqueness: (1). multi- step reasoning is task where large models substantially outperform smaller models (Wei et al. 20226), versus performance gains on tasks like sentiment classification can be very limited with large models (Shin et al. 2020); (2). multi-step reasoning is where few-shot prompting starts to outperform full training set fine-tuning, even when fine-tuning conducted on the same large model (Lewkowycz et al. 2022). This work takes an important step forward in multi-step reasoning by showing the critical role of prompt complexity.
Shain-of-Thought Reasoning language models thain-of-thouugtt prompting (Fig. [T)), proposed by Wei et al. (20226). They show that the reasoning ability can only be elicited by chain of thoughts, but not standard prompting where an answer directly follows a question without intermediate reasoning steps. Further works show that CoT can be improved by self-consistency (Wang al., 2022b), pretraining the model with latex- formated data (Lewkowycz et al.) 2022), context selection (Creswell et al.) (022). or even adding certain magic phrases like "Let's think step by step" (Kojima et al. 2022). The original CoT paper (Wei et al. (022b) uses 8 manually written examples as the prompt, which are reused by most follow-up works. Our work sits in the context of CoT reasoning, and propose a new complexity- based prompt selection that substantially outperforms the original CO
A prominent work demonstrating the multi-step reasoning of
Designing prompts can be challenging due the instability, as multiple works have shown the performance is sensitive to prompt, task, dataset, and model changes (Zhao et al., 2021; Lu et al., 2022, Su et al.] 2022). Despite works on automatic prompt searching (which is more suitable for smaller models, e.g. SShin et al. 2020) Li & Liang 2021), collective trial and error effort (there is even a prompt marketplace named PromptBase). The difficulty is that it is extremely hard to extract generalizable regularity from empirical observations that can form effective selection criteria. One notable exception is similarity- -bsed prompt selection, which retrieves the most similar training instances as the prompt for a given test case (Rubin et al., 2022). Yet for CoT prompting, retrieving different prompts for different test cases requires reasoning chain annotations for the whole training set, which compromises the advantage of being few-shot. Given this background, our core contribution is identifying complexity an effective and robust selection criterion and in many cases, it outperforms existing prompt selection schemes while being annotation-efficient.
Example Selection for Prompting
currently. prompt engineering for large models (still) a community-we
Relation to Classical Semantic Parsing The procedure of chain of thoughts prompting is conceptually similar to classical semantic parsing where one generates a logical form then executes it upon knowledge base to reach a final answer (Liang 2016 Cheng et al. 2019). The practice of sampling then voting is also similar to marginalizing out semantic parses Yin et al. 2018).
There are further works linking the relationship between in-context learning and classical Bayesian inference (Wei et al. 2021 Xie et al. 2022). From our perspective, we tend to view chain-of- thoughts as flexible, language model styled "logical forms" which are "executed" by the language model itself. We leave further study on connecting classical parsing and CoT to future work.
COMPLEXITY-BASED PROMPTING
We study multi-step reasoning tasks, and use math word problems, mathematical problems expressed in natural language, as our testbed. This task, as measured by solve rate (accuracy), is to predict the answer (typically number) of a given math word problem via intermediate steps. We follow the -fain-of-thoughhs prompting framework and compare all prompting schemes using GPT-3 text- set-dddvviiiiioe and Codex code davinci--00 as the th-tuughtst workflow, is shown in Fig. DA. The input is a stack of few (often 8) CoT cases followed by test question, then the language model continues generating output CoT for the test question. Our goal is to improve the reasoning accuracy by identifying and exploiting more effective input and output reasoning chains.
An example problem, well
3

---

Published as a conference paper at ICLR 2023
3.1 SELECTING COMPLEX SAMPLES AS PROMPTS
Our method is to simply choose complex prompts over simple ones. We hypothesize that language models' reasoning performance will increase if we use complex instances as in-context "training example," as they intuitively subsume simpler instances (Richardson & Sabharwal (022). We define complex instances as instances with more reasoning steps (Fig. [], as the name "multi- step reasoning" indicates. Note that using reasoning steps as the notion of complexity is also the practice of previous works like (Sugawara et al. 2018 Lai et al. 2021). We further define a step as a line, separated by the linebreak "\n".
There are two aspects that need more discussion: (1) The notion of complexity. There are other complexity indicators than number of steps. such as questions lengths or the length of the underlying formula for solving given problem. We will show that the trend that better performance comes with more complex prompts is consistent across various complexity indicators, such as question lengths and formula lengths. Consequently, for datasets that do not have annotated reasoning chains, we can use questions lengths to identify complex instances, then only annotate the identified few-shot instances, thus reducing the annotation cost. (2) Confounders of number of steps. The increase in performance with more complex examples in the prompt could be explained by correlated factors like the increase in the total number of reasoning steps in the prompts or just the increased length of the prompt. To account for this, we evaluate prompts with simpler examples but the same number of reasoning steps (e.g. 24 cases with 3 steps vs. 8 cases with 9 steps, both of 72 steps in total). We also consider prompts of the longest lengths (but not most steps). We show that the number of steps per example is the most prominent source of performance gains over confounders.
3.2 COMPLEXITY-BASEE CONSISTENCY
Complexity-base prompting can be further enhanced with new output selection method following the same intuition, which we present in this section. Existing evidence shows that the expressive neural models can take shortcuts during reasoning, relying on spurious correlations that inevitably exist in the training data (Mudrakarta et al. [018 Sugawara et al. 2018) Lai et al. (021). This often leads to suboptimal generalization to unseen data. To alleviate this issue, we explicitly promote outputs with more complex reasoning chains at inference time. Specifically, our method follows the self-consistency practice in Wang et al.] (2022b). which samples N reasoning chains for a test question. Different reasoning chains may lead to different answers, and Wang al. (2022b) takes the majority answer as the prediction.
our case, instead of voting among all chains, we only vote among top K (K < N) complex (more steps) reasoning chains, as shown in Fig. [[. We dub our method Complexity-bast baseed Consistency. Note that when K = N we recover the original self- consistency method. In our experiments, we N to 50, and observe that the optimal K is always smaller than N (typically 30-40). This provides clear evidence that voting among more complex reasoning chains generalizes better than voting among all. We also show that if we do the opposite and vote among answers produced by K simplest reasoning chains, the accuracy is always worse than voting among all. This further validates that complex chains, not simple chains, should be considered more during decoding.
4 EXPERIMENTS
We first discuss our experimental settings in $4.1 In $4.2 and $4.3 we present the following
(Wei et al., 2022b). It establishes new state-of-the-an results on three math reasoning datasets (GSM8K; Cobbe et al.
results: (1) our method substantially outperforms the original CoT
2021 MultiArith; Roy & Roth, 2013)] MathQA; Amini et al. 2019). a temporal reasoning task
(Date Understanding; (Suzgun et al.] 2022), and the referential game task (Penguins: [Suzgun et al. 2022). On StrategyQA (Geva et al.) 2021), commonsense reasoning dataset, our approach matches the existing state-of-the-art performance. (2) Performance gains from complex prompts are consistent: no matter what large model we use (GPT-3 or Codex), what distribution the prompt come from oi-distribution, noisy distribution, and distribution shift), or whether there exists prompt format perturbation confounders, complex prompts consistently outperform simpler prompts; (3) Compared with other example selection schemes (random, heuristic and retrieval), complexity- based example selection often achieves the best competitive results with minimal annotation budget. In
4

---

Published as a conference paper at ICLR 2023
the appendix, discuss further experimental results, including performance gain breakdown, results on smaller models, output step distribution, and further experiments on voting
4.1
EXPERIMENTAL SETTINGS
Datasets We use three math word problems datasets (GSM8K, MultiArith, and MathQA) and three non-math reasoning (StrategyQA: Date Understanding, and Penguins) as our testbed. We choose GSM8K and Multi also because they are the datasets used by prior work on Co'Ts (Wei) at. al 2022b Wang et al. 2022b) Kojima et at., [022]. allowing fair comparison to existing methods. MathQA's annotation are much noisier than others, and we use it to evaluate the robustness of our approach. There are 1.3K test instances GSM8K, 600 in MultiArith, and 600 in MathQA. For each dataset, we randomly draw 200 instances from the training data to create validation split. The cost of prompting GPT-3 is proportional to the size of test set. For the non-math datasets, StrategyQA is multi-step commonsense reasoning task with 800 test instances. Date Understanding is temporal reasoning task with 250 test instances. Penguins is a referential game (a referential game asks questions referring different objects, e.g., penguin A older than penguin B and C) with 146 test instances. Both Date Understanding and Penguins are subsets of the BigBench Hard datasets (datasets that previously fine-tuning struggles with, see /uzgun al.] 2022). Evaluating on a 200- instances validation set costs about 6-8 US dolars for greedy decoding (I output chain) and $12-$24 for sampling 50 output chains. Prompting Codex is currently (November 2022) free and we hope OpenAl could continue making it free to the community.
Language Models We consider two paradigms: fine-tuning and prompting. For fine-tuning,
we report the existing SOTA performance: fine-tuned GPT3 with verifier (Cobbe et al., 2021) on GSM8K, relevance and LCCA operation classifier (Roy & Roth 2015) on MultiArith and a customized sequence to sequence model (Amini et al. 2019) MathQA. For prompting,
consider the following language models: (I). LaMDA (Thoppilan et al. [2022). a 137B model
used as the baseline in Wei et al. (2022b); (2). PaLM (Chowdhery et al. [2022), the primary 540B
model used in the CoT papers: (3). Minerva (Lewkowyez et al. 2022). a 540B large model that
trains on ddeta it achieves SOTA performance in math reasoning on GSM8K; (4). GPT-3 175B
(text-davinci-002 from Brrwnn et al.) 2020) (5). Codex (code-davinci-00) from Chen et al., 2021 also 175B). We further consider the VeRSSe (Li al. 2022) method which equips an additional trained verified to GPT-3/ Codex and is the previous SOTA on GSM8K. Our experiments are mostly conducted on GPT-3 and Codex because they are the accessible the public thus more reproducable. LaMDA, PaLM and Minerva are not accessible to the public, and their numbers are from their corresponding papers.
Prompts and Hyperparameters The training sets of GSM8K and MathQA contain human annotated reasoning chains, within which we search for complex prompts. MultiArith does not have annotated reasoning chains, so we consider two strategies.
(1). in-distribution annotation, which uses question lengths as an alternative proxy for complexity, then manually annotates reasoning chains for complex questions; (2). prompts transfer from GSMSK training data. All prompts for math datasets contain cases (a case a question + a chain of thoughts + an answer). For non- math datasets, since they do not have annotated reasoning chain, we again, use question length as the complexity proxy and manually annotates reasoning chains for complex questions. Following Kojima et al. (2022), we add "Let's think step by step" before the reasoning chains for all prompting schemes to improve the performance.
4.2
MAIN RESULTS
Overall Test Performance on Math Datasets Table [ shows the overall performance of models. We consider two decoding strategies: (1) greedy decoding (the first block of Table T and (2) majority vote ($3.2) the second block of Table I]. Note that PaLM and Minerva three times larger than GPT-3 and Codex, the model we use to evaluate our method, and Minerva is additionally pretrained latex data. Therefore, they are by means comparable to the methods based on GPT-3 or Codex. We nevertheless outperform all of them.
more than
We consider three prompting schemes: (1). Handcrafted CoT constructed originally by Wei et al. (202b)) then reused in following-up up works (Wang et al. 22022b) Kojima et al.) 2022) Wang et al. 2022ab. (2). Random CoT: randomly drawing samples from the training set. GSM8K and MathQA
5

---

Published as a conference paper at ICLR 2023
Table 1: Complexity-based prompting, when applied Codex (code-davinci-0002, achieves new state-of-the-art performance GSM8K, MultiArith, and MathQA. i models are not publicly accessible, and the numbers are from their papers. Our performance gain (+blue) is computed over the original handcrafted CoT used in Wei et al. (2022b,, which is our primary baseline. Our methods substantially increase the performance over Wei al. (2022b), with an average +5.3 gain on GPT-3 and +6.2 Codex.
#Params
GSM8K
MultiArith
MathQA
Previous finetuning SOTA
<175B
57.0
60.5
37.4
Greedy decoding (Wei al.
20226
LaMDA (Thoppilan et al. 2022
137B
17.1
51.8
PaLM (Chowdhery et al. 2022)
540B
58.1
94.7
Minerva (Lewkowycz et al. 2022)
540B
58.8
Text-davinci-002
Handcrafted CoT
175B
48.1
90.8
30.1
Random CoT
175B
49.7
89.5
34.8
Complex CoT
175B
55.4 (+7.3)
94.2 (+3.4)
36.0 (+5.9)
Code-davinci-O00 Handcrafted CoT
175B
61.0
95.8
29.3
Random CoT
175B
60.4
97.3
40.5
Complex CoT
175B
66.6 (+5.6)
95.8 (+0.0)
47.3 (+18.0)
Voting among multiple outputs
WWag al.;
20226)
LaMDAt (Thoppilan et al.
2022
137B
27.7
75.7
DiVeRSe (Li al. 2022))
2022)
175B
82.3
99.8
PaLM (Chowhhery et al.
2022
540B
74.4
99.3
Minerval (Lewkowycz et al.
2022
540B
78.5
Text-davinci-002
Handcrafted CoT
175B
64.0
98.2
43.8
Random CoT
175B
62.0
95.2
48.5
Complex CoT
175B
71.5
97.3
49.5
+ Vote Complex
175B
72.6
(+8.6)
98.7 (+0.5)
50.2 (+6.4)
Code-davinci-O00 Handcrafted CoT
175B
74.6
99.7
55.0
Random CoT
175B
77.3
99.3
58.2
Complex CoT
175B
82.6
99.7
58.6
Vote Complex
175B
82.9 (+8.3)
99.8 (+0.1)
60.0(+5.0)
training data have reasoning chain annotations, have reasoning annotations, so we randomly sample eight training cases then annotate the chains manually. (3). Complex COT. For GSM8K and MathQA, choose eight training cases with the most numbers of reasoning steps; For MultiArith, we use the question length as the proxy for complexity, and manually annotate reasoning chains for the eight training questions. Complex prompt selection results in substantially more reasoning steps: averages 9,0 steps on GSMSK, while the handcrafted and random schemes yield 3.4 and 2.8 steps respectively. The trends are similar on the other two datasets. The handcrafted prompts uses the same fixed prompt for all three datasets but the cases within the prompt does not come from any of the datasets (so they are in sense, out of distribution). Complex prompts and random prompts all come from their corresponding training sets (so these two are sense, in-distribution).
directly use them. MultiArith does not
with the longest
As Table shows, our method achieves substantially better performance than the baselines. Besides, our proposal of voting among complex chains outperforms voting among (last two lines in Table [ Furthermore,
performance using GPT-3 is close to PaLM and Minerva, two language models that are more than three times larger than GPT-3 and are not publicly accessible. These results directly demonstrate the effectiveness of methods.
Consistent Performance Improvements on Different Reasoning Tasks Table 2 shows that the advantage of complex prompts holds for different types of reasoning tasks. When prompted with complex examples, GPT-3/ Codex achieves new SOTA performance on Date Understanding and Penguins datasets where complex prompts consistently improves performance over simpler prompts.

---

Published as a conference paper at ICLR 2023
Table 2: Complex prompts give comparable performance PaLM on StrategyQA (commonsense reasoning), and achieve new state of the art performance on Date Understanding (temporal reasoning), and Penguins (referential game) datasets. Accuracy gain (+blue) is computed over the original handcrafted CoT used in Wei et al. 2002bb a All results use greedy decoding.
Prompt
#Params
StrategyQA
Date Understanding
Penguins
PaLM
Handcrafted
540B
77.8
79.2
65.1
Text-davinci-002
Handerafted
175B
66.9
82.8
76.7
Simple
175B
71.1
76.4
61.0
Complex
175B
77.0 (+10.1)
82.4 (-0.4)
79.5 (+2.8)
Code-davinci-022
Handcrafted
175B
73.1
86.0
78.1
Simple
175B
74.4
83.2
69.8
Complex
175B
73.9 (+0.8)
86.8 (+3.6)
80.8 (+2.7)
GSMBK In-distribution
MathQA Nolsy-labeled 41
MultiArith Transfered prompt
58.5
41.8
93
52.5
52
86
43
36
82
83,5
Simple
Complex
Simple
Complex
Simple
Complex
5
10
9
Figure 2: Validation set performance. X-axis means reasoning steps and y-axis means accuracy. More reasoning steps in prompts overall achieve higher accuracy when prompts are in in-distribution (left), noisily labeled (middle), and out of distribution (right).
Consistent Performance Improvements in Different Prompt Distributions We investigate the performance of our complexity- prompting when the prompts are: (1) from clean in- distribution training set (GSMSK); (2) from noisy annotation (MathQA); (3) are transferred from another dataset (MultiArith). Here as MultiArith does not have annotated reasoning chains, and their questions are similar the ones in GSM8K; we use (transfer) prompts from GSM8K for MultiArith. Figure (hoows that in general, more complex prompts achieve better performance, and this trend consistent in all the three settings, except for one particular case on MultiArith.
As we view the reasoning complexity as the basis of new example selection scheme, we compare it with existing selection schemes. We consider: (1) random selection; (2) Centroid, where we select examples whose question embeddings (produced by a pretrained sentence encoder Reimers & Gurevych] 2019) are the closest Reiiees to the embeddings of all other questions, i.c., questions at the center part of the dataset. The intuition that centroid examples may be the most typical or representative cases of a dataset; (3) Retrieval, where we retrieve questions from training set whose embeddings in Euclidean distance. Notably, there are important differences between retrieval and other methods: retrieval uses different prompts for different test cases, while other methods use fixed prompts for all. Therefore, the annotation cost of retrieval scales with the size of the test set, and is usually about the full-training-ser -eisiiddd annotation (more than 10K cases), while others only require few-shot annotation (in our cases, only 8 examples).
Comparison to other Example Selection Schemes
closest test question measured
As shown in Table [3] complexity- and MultiArith. On MathQA, although strievallbased selection outperforms complexity-basee selection, has two importance restrictions that we not have: (1) as mentioned, retrieval requires substantially more CoT annotation, while we only requires few-shot; (2) the performance of retrieval critically determined by how similar the test cases and the training questions are to each other, and the similarity may not always hold. We further note that MathQA, many dev. questions are quite similar to their retrieved training questions (some them only have minor changes like "8 apples plus 9 bananas" to "10 apples plus 5 bananas" while the underlying computations the same). So in general, complexity-base based prompting has the advantage of good performance while being annotation efficient.
selection outperforms all other methods on GSM8K

---

Published as a conference paper at ICLR 2023
Table Comparison other prompt example selection schemes (validation accuracy). On GSM8K and MultiArith, complexity-base selection outperforms all the baselines. On MathQA, although retrieval performs better than complexity, requires substantially more annotation.
#Annotations
GSM8K
MultiArith
MathQA
Random
Few-shot (8)
52.5
86.5
33.0
Centroid
Few-shot (8) Full training set (2 10000)
52.0
92.0
32.0
Retrieval
56.0
88.0
69.5
Complexity (ours)
Few-shot (8)
58.5
93.0
42.5
total cases
343
total cases
300
correct simple prompt
300
correct simple prompt
239
GSMBK
222
MathQA
200
154
200
179
129
100
78
100
101
87
30
0
Figure 3: X-axis means reasoning steps of dev set cases and y-axis frequency. The direction of generalization on the two datasets is intriguing and show different patterns: on GSM8K, simple prompts perform better for simple cases (S 3 steps) while complex prompts perform better for complex cases; on MathQA, simple prompts do not have advantages for simple case and complex prompts seem perform better most of the groups.
Table Alternative complexity measure: Q Len. question length. F Len. formula length. More complex prompts consistently outperform simpler ones.
Step
Per-
Step
Step
step
Stop
Q Len.
GSM8K
F Len.
MathQA
Per strsstep longth
Simple
70
49.0
7.5
37.5
Case length = number of step per-step length
Mid
226
51.0
55
33.5
Figure 4: Relationship between confounders.
Complex
815
52.5
165
43.5
Intuitively, one may attribute the improvements of complexity- based prompting accuracy gains on complex test cases. Yet interestingly. our analysis suggests the opposite. Fig. 3 compares the validation set accuracy of complex and simple prompts, varying number of reasoning steps the gold annotation. We observe a clear trend on both GSMSK and MathQA: complex prompts perform on par with simple prompts on hard cases, while achieving more clear gains on cases with fewer number of reasoning steps. This finding suggests that complexity-basee prompting generalizes to simpler test cases. We conjecture that this is because the reasoning capabilities elicited by complex prompts may cover simple questions better. Further investigation into the underlying mechanism definitely interesting, and is left to future work.
Direction of Generalization
4.3 ANALYSIS
In this section, we develop in-depth analysis supporting our claims. All experiments in this section are performed on validation sets. We first show that the performance improvements with more reasoning complexity is consistent in terms of: (1). different proxies for complexity and (2). different step formatting. Then we show that the number of reasoning step is the most prominent factor for performance improvements over its confounders. Finally, strengthen conclusion of complexity- based consistency, and show that the optimal performance is always achieved by majority voting over complex chains, not simple chains.
8

---

Published as a conference paper at ICLR 2023
Confounder analysis. Although there exist confounders like number of cases or total prompt length, the number of reasoning step is the most prominent factor for performance gain given moderate per-step length.
Table 5:
More number of simple cases v.s. less but complex cases
GSM8K
MathQA
Total reasoning step
72
72
45
45
Number of cases in prompt
24
8
19
8
Per-case reasoning step
9
2.25
5.625
Accuracy
51
58.5
37.5
42.5
Most number of reasoning steps longest prompt
GSM8K
MathQA
Number of cases in prompt
8
8
8
Length of prompt
12.6k
8.4k
7.6k
4.9k
Number of total reasoning step
59
72
32
45
Per-step length Accuracy
112
74
137
52
57
58.5
31
42.5
Shorter per-step length v.s. Longer per-step length
GSM8K
MathQA
Number of total reasoning step Number of cases in prompt
72
72
45
45
8
8
8
Per-step length Accuracy
36
74
37
52
51.0
58.5
30.5
42.5
Alternative Proxies for Complexity Complexity prompting is equally applicable when the data does not come with reasoning chain annotations, as we have already shown that selecting cases with longest questions also improves performance ($4.2). In Table 4, confirm that in addition to number of steps, either using questions length or formula length as the measure of complexity, the optimal performance is achieved with complex prompts. These results mean that the effectiveness of complex prompts are consistent with regard to the notion of complexity.
All experimente so far keeps the number of instance be 8 all prompts. Yet when choosing complex examples with more reasoning steps, we observe that the following factors are correlated (also illustrated in Fig. 4p: (I). when per-case reasoning step increases (for example, in GSM8K we choose cases with 9 reasoning steps), the total number of step in the whole prompt also increase (in GSM8K, we have cases the prompt, so there are 9 72 steps in total). This might be compensated by using more number of simple cases (e.g.. 24 simple cases, each with steps, can also make 72 steps in total). These factors are shown the upper part of Table (2). when per-case step increases, the full length of the prompt (= number of characters) also increases, which may be compensated by longer (more characters) but less step examples. These factors shown in the lower part of Table
Confounder Analysis
From the accuracy results can see that: (1). keeping full number of reasoning steps the same, using more number simple cases does not outperform less number of complex cases; (2). longest prompts does not outperform complex prompts. (3). yet we do need a moderate per-step length because keeping total number of step 72, moderate per-step length prompts outperforms shorter per-step length prompts. This means that despite the existence of confounders, the number of reasoning steps per example is the most prominent factor for performance gain given moderate per-step length.
CONCLUSION
This paper proposes new complexity-based instance selection scheme for prompting language models to perform multi-step reasoning. In addition to substantial performance improvements math word reasoning tasks. methods exhibit multiple advantages such as being intuitive, annotation efficcent,, and robustly effective in different in-context learning settings. We hope this work will open research possibilities in prompting, language models, and multi-step reasoning.

---

Published as a conference paper at ICLR 2023
REFERENCES
Ekin Akyurek and Afra Feyza Akyurek. Notes on teaching gpt-3 adding numbers, 2022. URL https: csail mit. wdw//dlulsls/eeeeee het//arittttttt _epaamteeitea_____
Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik Koncel-Kedziorsse Yejin Choi, and Hannaneh Hajishirzi. MathQA: Towards interpretable math word problem solving with operation-based formalisms. Proceedings of the 2019 Conference of the North American Chapter of
the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 2357-2367, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: (0.18653/11/111-122224 URL https:/ httss///acaatthoooo
org/ /1 9-445
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler. Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few- shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL https: https://proceednngg nwwrips..p.... wttpppppppppc/////////// Pap.oeaaaaapppppppppe.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, al. Evaluating large language models trained on code. arXiv preprint arXiv:2/07.03374, 2021.
Jianpeng Cheng, Siva Reddy, Vijay Saraswat, and Mirella Lapata. Learning an Executable Neural Semantic Parser. Computational Linguistics, 45(1):59 -4449999499999999 03 2019. ISSN 0891-2017. doi:
10. 2011662cooiiaa003444 URL https: //dp::///d33 /oo../////////////////////./ wrg/orrggo/..o /00. 11 62111/cco /ol//ollo cow.looo..oo...o. 1a00l1l__0004440 0_00342)
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.023111 2022.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14168, 2021.
Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. arXiv preprint arXiv:2205.09712, 2022.
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did aristotle use laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346-361, 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. arXiv preprint Sttiv:2205.119110 2022.
Yuxuan Lai, Chen Zhang, Yansong Feng, Quzhe Huang, and Dongyan Zhao. Why machine In Findings of the Association for Computational Linguistics: ACI-IJCNLP 2021, pp. 989-1002, Online, August 2021. Association for Computational Linguistics. doi: 10.18553/v1/2011
reading comprehension models learn shortcuts?
htw.0022i.nnngg-aa........ URL. https://
aclanthology wrw.o/////o...... /0gg/2021.0m http//22....nnnngg...e findings-----i. a51.85
Angeliki Lazaridou, Elena Gribovskaya, Wojciech Stokowiec, and Nikolai Grigorev. Interne- augmented language models through few-shot prompting for open-domain question answering. arXiv preprint 22X35:2203.05//5 2022.
10

---

Published as a conference paper at ICLR 2023
Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Juuman-Solle et al. Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206. 14858, 2022.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4582 4597, 2021.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. On the advance of making language models better reasoners. arXiv preprini arXiv:2206.0233:5 2022.
Perey Liang. Learning executable semantic parsers for natural language understanding.
Communications of the ACM, 59(9):68-76, 2016.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration
for Deep Learning Architectures, pp. 100-114, Dublin, Ireland and Online, May 2022.
Association for Computational Linguistics. doi: 10. 10.18663111/0222ddeoolllll URL https:
//aclant wwwp:tthooooooy..o..22..2.. /ttp////2222.2/. deelio-1.10
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. arXiv preprint arXiv:2107.13555
2021.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 8086-808 8098, 2022.
Pramod Kaushik Mudrakarta, Ankur Taly, Mukund Sundararajan, and Kedar Dhamdhere. Did the model understand the question? In Proceedings the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1896-19999999 1906, Melbourne, Australia, July 2018. Association for Computational Linguisties. doi: 10. 10.11863//1/P11-111 1176. URL https:
PromptBase. Promptbase. settss:/proopttaeet
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP), pp. 3982-3992, 2019.
Kyle Richardson and Ashish Sabharwal. Pushing the limits of rule reasoning transformers through natural language satisfiability. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 11209 11219, 2022.
Frieda Rong. Extrapolating to unnatural language processing with gpt-3's in-context learning: The good, the bad, and the mysterious. sttp://odd.tttfood....o edu/blog/
in context in-oontxt--Learne learning/
Subhro Roy and Dan Roth. Solving general arithmetic word problems. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1743-1752, Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10.18653/v1/
D15- 1202. /tll:ttts/////ccttttttt http:////cccclaaooooooooooooo//. wtg/D15-1200000
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning to retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2655-2671, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/v1/ 2022. n022.naacl-no main. URI www.t:ttpp...... ogg wgw..oyg..oo00222 naacl -ma n. n..9. 191

---

Published as a conference paper at ICLR 2023
Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 4222-4235, Online, November 2020, Association for Computational Linguistics. URL https: /tttps://acllanthclog..../
doi: 1211665//10022..mmmmmmmaaaa
em. main. 346
Hongjin Su, Jungo Kasai, Chen Henry Wu, Weijia Shi, Tianlu Wang, Jiayi Xin, Rui Zhang, Mari Ostendorf, Luke Zettlemoyer, Noah A Smith, al. Selective annotation makes language models better few-shot learners. arXiv preprint arXiv:2209.01975. 2022.
Saku Sugawara, Kentaro Inui, Satoshi Sekine, and Akiko Aizawa. What makes reading comprehension questions easier? In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2208-4219, Brussels, Belgium, October-November 2018. Association for Computational Linguistics. doi: 10.18653v1/D18-- 1453. URL https://
ac sallanhhoogg. wot.hhllog..orr//BB----5.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261, 2022.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng. Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint arXiv:2201.082. 2022.
Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. Universal adversarial triggers for attacking and analyzing NLP. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural
Language Processing GEMNLP-IJCNEL pp. 2153-2162, Hong Kong, China, November 2019.
Association for Computational Linguistics. doi: 10.18653/1//11- 1221
URL https://
aclanthology www.eyyorg/11911111
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. Rationale- augmented ensembles in language models. arXiv preprini arXiv:2207.007: 007477 2022a.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11177 2022b.
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning. Advances in Neural Information Processing Systems, 34:16158-16170, 2021.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.00 076622 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint 1rXiv:2201.11900 2022b.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2022. URL https::/
tameet/forrmm wtt.://rrmmmooooooooo (d= JUMI
Pengcheng Yin, Chunting Zhou, Junxian He, and Graham Neubig. StructVAE: Tree-structured latent variable models for semi-supervised semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 754-765, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 18653v1/l P18-1070 URL htt a/c http://///.cnnooooooooooro/////
12

---

Published as a conference paper at ICLR 2023
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12697-12706. PMLR, 18-24 Jul 2021. URL https:://proceednng... /tt.://ss....pra........////aae. c.hmll]
39/
13

---

Published as a conference paper at ICLR 2023
Table 6: GSM8K validation set performance improvements broken down on various design choices. More than half of the accuracy improvements can be attributed to our complexity-based prompting and output selection (indicated by t).
Greedy Decoding
Acc.
Majority Vote
Acc.
CoT Original
43.5
CoT Original
55.5
Add "Let's think step by step"
Add "Let's think step by step" and change "Q: to "Question:"
48.5 (45.0)
61.0 (+5.5)
(Kojima et al. 2022)
Use complex prompt
54.0 (+5.5)
Use complex prompt
67.0 (+6.0)
Change "Q: to "Question:" "
58.0 (+4.0)
Voting within complex sample
71.0 (+4.0)
Table 7: Complexity prompting is emergent ability of large models. If applied to smaller models, complex prompts cannot induce significant performance gain (recall in Table complex prompts induces average +6.2, maximum +18.0 accuracy gain on Codex).
MultiArith
GSM8K
text-curie-001 6.7B
Flan-T5 11B
Flan-T5 11B
Handcrafted
3,8
51.5
19.5
Random
2.0
53.3
21.0
Complex
3.3
51.3
21.0
A
-0.5
-0.2
+1.5
simple prompt complex prompt
simple prompt
complex prompt
GSMBK
60
MathQA
200
40
100
20
2
20
32
Figure 5: Output step distribution. X-axis means reasoning steps and y-axis means frequency. As sanity check, complex prompts indeed induce complex outputs than simple prompts.
A
APPENDIX
Below we list some additional experimental results.
Performance Improvements Breakdown Improving prompting performance commonly requires prompt engineering. A common scepticism or criticism towards performance improvements on leaderboards like Table is whether the accuracy gains are from the proposed method other independent engineering efforts. Here we list all the efforts we made for leaderboard climbing on
Table While techniques like adding "Let's think step by step" (Kojima al.. (022) improves the accuracy, the performance gains can be primarily attributed to complexity baasee prompting, validating the effectiveness our methods.
Does smaller models also enjoy the performance gain from complex prompts? Unfortunately, this seems to be not the case. As is shown in Table 7 complex prompts cannot induce meaningful performance gain over the original or random prompts. This indicates that, like the chain-of th-ouuhsss prompting itself, complexity- based prompting also an emergent ability that exist only when the model scale is large enough.
Performance on Small Models
As a sanity check, in Fig. 5 we show that complex prompts induce complex reasoning than simple prompts (Codex outputs GSM8K and MathQA). This means that complex prompts are indeed discouraging the model from taking easier reasoning path, thus potentially avoiding shortcuts.
Output Step Distribution
14

---

Published as a conference paper at ICLR 2023
Table 8: Sensitivity analysis on step formatting. Complex prompts consistently lead better
performance with regard to different step formatting.
Linebreak "In"
Period "!"
Explicit "step 1"
Semicolon "
GSM8K- GSM8K-Complex 58.5
54.5
52.0
54.0
GSM8K-Simple
43.0
40.5
42.0
41.0
MathQA-Compler
42.5
39.0
36.0
39.5
MathQA-Simple
34.0
34.5
33.5
37.0
GSM8K
MathQA
71.5
51.5
50.5
Voting over complex generation
69
69
48.5
49
49
Accunaay
67
48.5
65
42.5
46
Voting simple generation
55
/3..5
Top
Figure 6: Majority voting over top K complex simple generated samples. The optimal performance is achieved on selecting complex samples over simple samples.
Sensitivity Analysis on Step Format A common concern with prompting that the performance can be sensitive the format of the input (Shin et al. 2020 Liu al. (022 and may change with input perturbations. Here we study one important perturbation: the splitter of steps, which is an existing concern of CoT-styled prompting As alternatives to the linebreak "\n" we use, we consider two more types of splitters: (I). explicit phrases "step i" (2). two punctuation marks, period "." and semicolon "." The performance is shown in Table 8 Although these perturbations do have an influence on the performance, complex prompts consistently lead to better performance with regard to different step formatting.
Rong Akyurek & Akyurek (2022).
Voting among Complex Chains Outperforms Voting among All Now we analyze the properties of complexity-based consistency, which generalizes the reasoning complexity selection criteria from the input space (prompts) to the output space (sampled solutions from the language consistency first sample reasoning chains from the model, then take
model). Complexity-basee the majority answer voted from the top K complex chains. Here we set N = 50, and control K 10, 20, 30, 40, 50. Note that when K = 50 we recover the original self-consistency (no complexity- bassed selection). As further comparison, of voting over top K complex samples, we vote over top K simple samples. As shown in Fig. 6 (1). voting over simple samples always underperform full sample; indicating this is not correct direction for performance; (2). both datasets achieve the best performance on some K** < N with complex voting. These results again, validate the choice of complex samples.
consider the other way around: instead
15


Reviews:
[{"review_id": "wQmupTk4lu", "reviewer": "Reviewer_QWaf", "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 investigates the example selection problem which is selecting reasoning examples that make the most effective prompts when prompting large language models with a chain of thoughts (CoT) prompt. The authors apply their approach at both prompting and decoding time. Evaluating on multi-step reasoning task, they observe improvements over the baselines.", "summary_of_the_review": "This work is well-motivated, clearly explained, and sufficiently supported by analysis. There are some questions for the authors (see section Strength And Weaknesses), however overall it's a valuable contribution to the field. \n", "strength_and_weaknesses": "- The idea is nice, focusing on the instance selection problem by looking at the complexity is interesting. \n\n- The authors define a step as a line, separated by the linebreak “\\n”. They do look at the length of the input at some point but I am wondering if there are some side effects from defining a step like this. Do the authors know whether processing steps together would provide additional context or is it too difficult to learn from? \n\n- From the results (e.g., Table 1) it looks like the number of parameters is an important factor in the overall performance. Have the authors looked into the effectiveness of their proposed approach with language models of different sizes?\n\n- Typo: section 3.1: the n. umber of", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "p-W6D8p5yx0", "reviewer": "Reviewer_ZkDK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 studies the task of prompting large-scale language models to perform multi-step reasoning, and proposes a simple and effective example selection scheme for multi-step reasoning based on reasoning complexity. The proposed method is to select prompts with higher reasoning complexity, according to the author's definition of complexity. The proposed method is evaluated on math word reasoning tasks, and is shown to outperform baseline CoT construction methods. The method is also robust to format perturbation and distribution shift.\n", "summary_of_the_review": "In this work, the authors study the task of prompting large-scale language models to perform multi-step reasoning, and propose a simple and effective example selection scheme for multi-step reasoning based on reasoning complexity. The proposed method is evaluated on math word reasoning tasks, and is shown to outperform baseline CoT construction methods.  There are some concerns about the novelty of this work. In addition, the proposed method is only evaluated on GPT-3 and a few reasoning tasks, and it would be interesting to see if the proposed method also works on smaller language models and more tasks.\n", "strength_and_weaknesses": "Strength: \n- The proposed method is intuitive and easy to implement, as claimed by the authors. \n- The paper is well-written and easy to follow. The authors provide detailed experimental results and analysis.\n- The proposed method is a simple and effective example selection scheme for multi-step reasoning, which is an improvement over existing methods that require hand-engineering.\n\nWeaknesses: \n- The proposed method is only evaluated on GPT-3, and it would be interesting to see if the proposed method also works on smaller language models. \n- The proposed method is only evaluated on math word reasoning tasks. It would be interesting to see if the proposed method also works on other tasks, such as the Big-Bench tasks.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KYDJb-eTCU", "reviewer": "Reviewer_D9Jd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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 paper proposes a simple complexity-based prompting method for chain-of-thought prompting. The idea is to prompt with more complex questions: The authors use example questions with more reasoning steps (9 per question). When combining the predictions from multiple prompts, they choose the top K predictions with the most reasoning steps. Results show consistent improvement on 3 maths reasoning datasets, across various complexity of questions and formats of the prompts, and perform better than other prompt example selection methods.", "summary_of_the_review": "Questions:\n1. How does changing the complexity in input change the complexity in output? I did not find an answer in the paper. Does it often result in more reasoning steps in output?\n2. For the \"retrieval\"-based method in Table 3, how did you get all the annotations for the whole dataset? The CoT annotation is probably different from the original rationales in the dataset.\nTypo: Page 2 second paragraph: \"n. umber\".\n\nOverall, I think the paper is nicely written and good for ICLR.", "strength_and_weaknesses": "The proposed method is very simple and it shows consistent improvement over the previous methods. It substantially improves the GPT-3 performance on chain-of-thoughts reasoning. The ablation study shows the method is very robust across many different angles.\n\nWeakness: The experiments are only carried out on GPT-3, and the performance is generally inferior to those of PaLM and Minerva. The authors probably cannot get the performance on that two models, it would be great if they can illustrate on other large models, like OPT and Codex.\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "F7T1p_uWam", "reviewer": "Reviewer_Gum9", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 paper proposed complexity-based prompting for multi-step reasoning and it showed prompts with more reasoning steps, achieving substantially better performance on math word reasoning tasks over strong baselines. Their experimental results show that such sample selection and voting over top-k complex output samples improve the accuracy.", "summary_of_the_review": "The paper proposed a simple example selection that improves the existing results. The paper also mentioned that rather than majority voting over the output sample voting over top-k complex outputcsamples (those with more number of steps) contributes to the accuracy improvement. The paper still needs to clarify/justify the results in Figure 5 since it conflicts with these statements.", "strength_and_weaknesses": "Strength:\n1- The paper considered example selection for a multi-step reasoning task and it picked examples with complex reasoning chains, i.e., chains with more reasoning steps, as the prompt.\n\n2- In comparison to existing example selection schemes like manual tuning or retrieval-based selection, complexity-based prompting sounds intuitive, easy to implement.\n\n3- The paper also proposed complexity-based consistency, where instead of taking a majority vote over all generated chains, we vote over the top K complex chains. Their experimental results also show that voting among more complex reasoning chains generalizes better than voting among all.\n\n\nWeakness:\n1- The paper mentioned that majority voting over top K complex generated samples.performs better than the top-k simple generated samples. However the results in Figure 5 for the MathQA are different. Is there any explanation for that?\n\n2- The generalization results are not clear.  According to Figure 3 complex prompts improve the performance on simple cases, however the accuracy of the complex prompts is very low. I think some statistics on the dataset where how many examples are there in each bucket may make it more clear. For example in GSM8k, for how many samples the number of reasonings are 8, etc.\n\n3- I understand the paper focused on generalizability based on the number of steps. However, I am wondering if the accuracy error is because of the ask complexity or the complexity of the numbers (length of the digits)\n", "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