Automatic Prompt Augmentation and Selection with Chain-of-Thought from Labeled Data
Authors: KaShun SHUM
Shizhe Diao
Tong Zhang
Venue: EMNLP 2023 Findings (2023)
Keywords: large language models
chain-of-thought
prompt tuning
few-shot prompting
TL;DR: This paper proposes a new strategy to automatically augment rational chains from a small labeled dataset without task-specific human CoT annotation, prune low-quality chains, and select the optimal combination of rational chains.

Abstract: Chain-of-thought (CoT) advances the reasoning abilities of large language models (LLMs) and achieves superior performance in complex reasoning tasks. However, most CoT studies rely on carefully designed human-annotated rational chains to prompt LLMs, posing challenges for real-world applications where labeled data is available without rational chains. This paper proposes a new strategy, AutomateCoT (Automatic Prompt Augmentation and Selection with Chain-of-Thought), that can bypass human engineering of CoT by automatically augmenting rational chains from a small labeled dataset, and then pruning low-quality chains to construct a candidate pool of machinegenerated rationale chains based on the labels. Finally, it selects the optimal combination of several rationale chains from the pool for CoT prompting by employing a variance-reduced policy gradient strategy to estimate the significance of each example. Automate-CoT enables a quick adaptation of the CoT technique to different tasks. Experimental results demonstrate the effectiveness of our method, where competitive results are achieved on arithmetic reasoning (+2.7%), commonsense reasoning (+3.4%), symbolic reasoning (+3.2%), and non-reasoning tasks (+2.5%).

Automatic Prompt Augmentation and Selection with Chain-of-Thought from Labeled Data
Kashun Shum Shizhe Diao S Tong Zhang
The Hong Kong University of Science and Technology (ksshumab, sdiaoaa, tongzhang
Abstract
basic idea of CoT prompting adding few ra- tionale chains the answer as exemplars illus- trate the intermediate rcasoning steps. Following CoT, several recent studies improve it by leveraging self-consistency (Wang et al., 2023), explanation learning (Lampinen et al., 2022), complexity- prompting (Fu et al., 2023), self-training (Huang et al., 2022), voting verifier (Li et al., 2022a), and bootstrapping (Zelikman al., 2022).
Chain-of thought (CoT) advances the reason- ing abilities large language models (L.MMs) and achieves superior performance in complex reasoning tasks. However, most CoT studies rely on carefully designed rational chains to prompt LLMs, posing chal- lenges for real-world applications where la- beled data available without rational chains. This paper proposes new strategy, Automate- CoT (Automatic Prompt Augmentation and Selection with Chain-of ooe--ooooTThhh that can by- pass human engineering of CoT by automati- cally augmenting rational chains from a small labeled dataset, and then pruning low- -ualuality chains to construct a candidate pool of machine- generated rationale chains based on the labels. Finally, it selects the optimal combination of several rationale chains from the pool for CoT prompting by employing variance-reducee policy gradient strategy to estimate the signif- icance each example. Automate-CoT en- ables a quick adaptation of the CoT technique to different tasks. Experimental results demon- strate the effectiveness of our method, where competitive results are achieved arithmetic reasoning (+2.7%), commonsense reasoning (+3.4%), symbolic reasoning (+3.2%) and non- reasoning tasks (+2.5%).
However, most of them are constrained to few fixed human- exemplars, which require sig- nificant human efforts to create and adapt to new datasets. The annotation process is nontrivial be- cause humans need to not only select the ques- tions but also carefully design the reasoning steps for each question. In the process of searching for the perfect exemplars, we identify four critical fac- tors that affect the performance of chain-of- offtthtttt prompting and require large human effort to deal with: (I) order sensitivity (Zhao et al., 2021): the order combination of the exemplars; (2) complex- ity (Sugawara et al., 2018; Lai et al., 2021: Fu et al., 2023): the number of reasoning steps of the rationale chains; (3) diversity: the combina- tion of different complex-level exemplars; (4) style sensitivity (Papadopoulos et al., 2010): the writ- ing/linguistic style of the rationale chains. Detailed analysis of the four factors is covered in Section 2. All of these sensitivities make human-bart based prompt e enginecring costly and motivate us to find an au- tomatic and aask-agnottic way to adapt chain-of- thought exemplars to any downstream tasks.
1 Introduction
The recent success in large language models (LLMs) has shown that properly prompted LLMs demonstrate emergent capabilities on complex un- derstanding and crestion-answering tasks (Wei al.. 2022a). Especially, with the recently pro- posed -hahn-tf- (CoT) prompting (Wei et al., 2022b), LLMs are capable of solving rea- soning tasks including arithmetic reasoning, com- monsense reasoning, and symbolic reasoning. The
In this paper, we solve these problems by a CoT augmentation and selection process to find suitable exemplars automatically. This can be divided into three steps: (1) Augment: The language model generates multiple pseudo-chains for query ques- tions automatically. (2) Prune: Based on an as- sumption: Generating correct reasoning is a nec- essary condition for generating correct answers. This assumption is natural because the answer is
"Equal Contribution.
'The cnde is available at httpps///githh com/ SULIKASSHU/AAutomateeee

---

generated after several reasoning steps. When correct answer is generated, the rationale chain of these steps most likely correct, contributing to the final correctness. As a result, We prume the pseudo-chains according to the consistency be- tween generated and ground-truth answers to re- duce the noise. (3) Select: Given that all the data have been annotated with rationale paths, we pro- pose apply pariance-reduced policy gradient strategy (Williams, 1992: Dong et al., 2020; Zhou et al., 2021; Diao al., 2022) to estimate the gradi- ents and optimize the selection process to find the most helpful thain-of-mne shain-of-thougghe thought for each task. Com- pared to prior manually written CoT, Automate- CoT could find the optimal and diverse CoT au- tomatically, adaptable to any task without human effort. Compared with Auto-CoT (Zhang al., 2023), which samples diverse questions by clus- tering and generates rationale chains, Automate- CoT considers and mitigates the aforementioned sensitivity issues, while achieving a greater per- formance boost for each task. Automate-Coa is a fully automatic pipeline for finding better chain- of of-thought prompts, mitigating the sensitivity is- sues of manually written exemplars, and further improving the performance by a large margin. Ex- perimental results demonstrate the effectiveness of Automate-Cof on arithmetic reasoning (+2.7%), commonsense reasoning (+3.4%), symbolic reason- ing (+3.2%), and non non-reasoning tasks (+2.5%).
GSMBK
90
Model
Manuel-CoT
80
Automate-Coo
Complex-CoT
Apcuracy (%)
60
50
40
30
10
2-hop
3-hop
4-hop
5-hop
6-hop
7-hop
8-hop
Figure 1: The performance across different numbers of hops (reasoning steps of rationale chains) on GSM8K. Manual-CoT refers to the human-writter chain-of- thought by Wei et al. (2022b). Complex-Cof refers to the chain-of thothtt using 9-hop rationale chains.
fluctuates with different orders of chain-of of-thuh exemplars. For the GSM8K dataset, we simply randomly shuffle the order of the exemplars in Manual-CoT 10 times and the lowest accuracy can be 59.8% which is 3.3% lower than the average accuracy (63.1%) 1%) they report, suggesting that order sensitivity still exists.
Complexity We first define complexity as the number of hops (reasoning steps) in an exemplar where more steps indicate greater complexity. It is observed that human-written CoT tends to be simple (<3 hops), achieving good accuracy in sim- ple math questions while suffering from complex questions, as shown in Figure 1. In addition, pre- vious study (Fu et al., 2023) suggested that using all complex exemplars can improve CoT performance. However, in our experiments (Figure 1), we found that Complex-CoT can improve the accuracy of complex questions, but perform poorly in simple questions. Therefore, we conjecture that the incon- sistency between the hops of provided exemplars and the required hops of the real question causes the performance drop, suggesting that determining the appropriate complexity level of exemplars is crucial.
2 Motivation
Recent studies observed sensitivity issues of GPT- 3's few-shot learning caused by different selec- tions of in-context examples such as order instabil- ity (Zhao et al., 2021; Zhang et al., 2022; Liu et al., 2022; Lu et al., 2022). Based on their findings, we first investigate whether these sensitivities still exist in -hain-of-thought methods. Then we further explore other factors that would not only affect the performance but require human efforts to deal with. We conclude with the following four factors:
Order Sensitivity: Different orders of few-shot exemplars may cause huge impact on the per- formance in traditional few-shot prompting (Lu et al., 2022). Thus we conduct experiments on GPT-3 to test if there is such sensitivity in chain- of of-thought methods. Although Manual-CoT (Wei et al., 2022b) reports that the human-written CoT is robust to order changes ( (<2%) with the LaMDA model, we observed that the performance of GPT-3
Diversity: Based on the above discovery about complexity, natural question what combination of different complex-level exemplars is most effec- tive. However, testing various combinations is a challenging task for humans and requires signif- icant effort to determine the optimal one. In our

---

(1) Augment
Traising Stage Pi
(2) Select
Thre 16 ontanally
Tranring
Oliv 23 Lugala...o The arsene
gpoooiction, label
Pous Casataaiion Queniion
hatadl dippe thersd
Estinaze Gradiont
Infermnce Stage
Indan Pi
LLM
Rass etaned IoStanii SalC RN DI0 100
Gkop
is ana acsiao 24
(Ros onseer
Eccnedi
Ground Truth 72
foor 10roors sast fooe
Not Manch
Matsh
Stop
50
Pool Bize
Twat Dhsectoon
eggn
trvoldrett
Prune
Figure 2: Illustrations of our proposed approach. The left and middle parts of the figure contain two steps of our method: (1) Augment and Prune and (2) Select. The right part illustrates the training stage (right top) and the inference stage (right bottom), respectively.
experiments (Figure 1), found that combina- tion of different complex-level exemplars outper- forms CoT with all complex exemplars, suggesting a complexity-diversiie trade-off.
Approach
Our approach receives a training dataset D con- taining n questions Q = {q1, -2. -n....,n.). and n answers A = (01, 42 (01,42 0n). The overall archi- tecture of our approach is shown in Figure 2. In this section, of augment and prune operation and end with an illustration of select operation.
Style Sensitivity: Previous research in educa- tional psychology found that different learning styles would limit the cognitive benefit for students from the prompting (Papadopoulos et al., 2010). We further argue that students with specific learn- ing styles benefit to varying degrees from different styles of prompting. In addition, the empirical evi- dence from Manual-CoT (Wei al., 2022b) shows that different annotators can cause up 28.2% accuracy difference symbolic reasoning task, verifying our conjecture. As a result, some bad styles may lead to huge performance drop. How- ever, humans cannot determine the performance of particular style beforehand, so it requires trial and error by checking on the validation set, which fur- ther increases the effort of writing chain-of-then tf-thughht exemplars.
start with detailed description
3.1 Augment and Prune
Inspired by Wang et al. (2022), which shows that the generated rationale chains are of comparable quality to the human-annotated ones, we aim to automatically generate the rationale chains aug- ment the candidate exemplars. Given m fixed ra- tionale chains C {ci, C2 ..., Cm question g, we ask the large language model G to generate k rationale chains for each q. A larger k can form a larger pool and some post-processes can be done to improve the quality of the pool. Considering the cost and efficiency, we choose k 1 for our ex- periments. Our method works well even without C (i.e., m 0), which is based on zero-shot prompt- ing. Then we prune those incorrect ones out and only keep those with the correct final answer. In other words, the final answer should be consistent with the ground-truth answer. After pruning, we
In light of this empirical evidence, we are moti- vated to design a framework not only augment rationale chains but also to select helpful chains adaptively. With this framework. it is expected to bypass the order and style sensitivities and reach a better complexity-diven man effort, finally boosting performance.
trade-off without hu-

---

obtain a pool of K high-quality exemplars.
gradient descent algorithm:
Pi < proic Pp: 1,...,..... n (3)
3.2 Select
where is the learning rate, is the sample size, and proje is the projection calculation (details are presented in the Appendix A).
With large pool of high-quality exemplars, we cannot directly apply all of them due to four con- siderations: (1) context length limit: the maximum length is 2,048 for GPT-3, so cannot feed too many exemplars into the model. (2) fair compar- ison: existing studies usually take 4-8 question- answer pairs as exemplars following Wei et al. (2022b). (3) sensitivity: the model performance may be sensitive to the contexts (Jiang et al., 2020), orders (Lu et al., 2022) and lengths (Lester et al., 2021) from the observation of prompt learning lit- erature. (4) adaptation: different downstream tasks may require different exemplars. Therefore, natu- ral idea is to select the most suitable 4-8 exemplars automatically.
Experimental Settings
In this section, we first introduce the setting of eleven datasets and their corresponding evaluation metrics ($ 4.1). Then the baseline models ($ 4.2) and implementation details ($ 4.3) are presented in the following two subsections, respectively. Full details about the experimental setting are illustrated in Appendix B.
4.1 Datasets and Evaluation Metrics
Following Wei et al. (2022b), we conduct our exper- iments on eight reasoning tasks, including five math word problem datasets: GSM8K, ASDiv. SVAMP, AQuA, and SingleOp: two commonsense reason- ing datasets: Commonsense (CSQA) and Strat- egyQA, and one symbolic reasoning task: Last Letter Concatenation (Letter (4)). We also gener- alize our method to non-reasnnng tasks including one question-ansee answering task (OpenBookQA), one natural language inference task (e-SNLI,, and one sentiment analysis task (SST-2). The detailed statis- ties of the datasets are listed in Table 5. The evalua- tion metric for all tasks is the exact match accuracy. First, conduct pre-procente preprrcessiing for predictions to remove all the special symbols. For example, "$100,000" will be processed to "100000". Then we check if has same value as the ground truth to calculate the exact match accuracy.
The process can be deemed as optimizing a su- pervised model with latent variables. For each chain-of-thought index i, we initialize latent vari- able ji Cat(p.). The random variable is sampled with the probability distribution p; Ip.,,... Pi.N]] over the N candidate demonstra- tion indexes, where pa and C = {p= |p] = 1,0 3 p < 1}. Since P; independent of each other, the joint probability of the whole input ex- emplars is P(T) = P(t)) = IPh... The loss is formulated as ( v)), where T rep- resents the full few-shot exemplars, t denotes the i-th exemplar, and S is the current question (user's query). However, directly updating the prompts by back-propagating through C( v)) is not possible because of the inaccessible gra- dients, where y is the label. We resort to the variance-reduced policy gradient estimator (VR- PGE) (Williams, 1992: Dong et al., 2020; Zhou et al., 2021; Diao et al., 2022), a kind of reinforce- ment learning method to optimize the loss function via forward propagation with:
4.2 Baselines
We compare our method with the following baseline methods: chain-of-thought (Manual- CoT) (Wei et al., 2022b), self-consistency (SC) (Wang et al., 2023), and Auto-CoT (Zhang et al., 2023). And we utilize the public APIs from OpenAl's services2 and test with text-davinci-00 and code-davinci-ed
Er [C(T)) - ((T)P(IT)
(1)
and estimate the gradient of p; by:
4.3 Implementation
Augment and Prune: Following Wei et al. (2022b) and Wang et al. (2022), we keep the same number of exemplars (4-8) listed in Table 5. For main experiments, augment and prune pool of 100 high-quality exemplars for all datasets.
96 = -- Σ - 1 c(rlot) _ nn log P(t.)
(2) where (A)), 1,... are sampled indepen- dently from P(T). Therefore, the exemplar distri- bution p; can be updated by a projected stochastic
/httts::/ccenai..om.

---

METHOD
GSM8K
ASDIV
SVAMP
AQUA
SINGLEOP CSQA
STQA
LETTER (4) OBQA
E:SNLI
SST-2
AVG.
Prior Best"
55.0"
75.3"
$7.4
37.9
91.2"
73.9
97.59
text-davinci--002
Auto-
A CoT
47.9
69.5
36.5
74.4
65.4
59.7
Manual-CoT
46.9
71.3
35.8
73.5
56.6
75.5
79.1
68.0
Automats-Co
49.71
74,272.0
73.314.4
27.912.1
9000
76.1722
67.91
19.9
79. 19.1
82.31
87.511.
70.672.8
SC
58.2
76.9
78.2
41.8
90.8
72,9
70.7
57.6
81.5
83.4
89.2
72.8
Cutommto-Coo"
67.8
7822 2.0
80,51..3 a.
43.41.
21
80.2
s.o
60.81
3.2
84.8
864 a.0
90.6
76.5
code-daviarl-000 0002
Autlo CoT
62.8
Manual-CoT
63.1
76.4
45.3
77.9
70.4
80.4
67.5
74.2
Automate CoT
67.61
83.1
78.21
47.8
92.4
6
81.3"a.4
75.31 2..1
75.01
83.21 8
71.21
90.8
76.9
SC
78.0
87.8
86.8
52.0
92.8
81.5
79.8
73.4
88.4
74.8
91.5
30.6
Automate CoT
82.41
88.9
87.81
1.0
55.61
3.6 94.0
84.0
2.0
80.6
To.8
76.21 2..
89.7
1.
78.3
92.8
82.8 2
Table The overall performance of Automate-CoT and the comparison against existing models on eleven downstream tasks. Manual-CoT and SC represent thain-of-tthoughe (Wei et al., 2022b) and self-consistency (Wang et al., 2023) methods. Bold denotes the best in sode-davvnci---e0 (enncc--92-bbseee methods and Underline denotes the best in text-davinci-000 (2021), b: Lan al. (2022), Pi et al. (2022), d: Amini al. (2019), Xu et al. (2022), f: Chowdhery et al. (2022), g: Raffel et al. (2020). Most statistics of Manual-CoT and SC have been obtained directly from their latest version. For some entries they did report, we obtain the result from DIVERSE (Li et al., 2022h).
methods. *; Prior Best is the best performance before CoT comes out. a: Cobbe et al.
Select: Both the training and validation sets have a size of 100 to reach a performance and cost trade- off. Then by utilizing the log probability returned by API calls, we calculate the cross-entropy loss of the answer token. Finally, we optimize the la- tent variables by AdamW (Loshchilov and Hutter, 2019) for 5 epochs with learning rate of x 10 and batch size of 10. After optimization, we choose the exemplars combination (arg max p.) with the highest validation accuracy to be further evaluated on the test set. By default, we query the language model once to get the answer. Under the self- consistency setting, similar to Wang et al. (2023), we query the language model 40 times and choose the most consistent one as the final answer.
With code-davinci-002, Automate-Cof also out- performs Manual-CoT and SC by 2.7% and 2.2%, respectively.
Arithmetic Reasoning: For text-davinci--00 Automate-CoT improves Manual-CoT by 2.7% over five arithmetic reasoning tasks. addi- tion, under the self-consistency setting, Automate- CoT improves SC by a large margin by an av- erage of 3.3%. Moreover, compared to Auto- CoT,, Automate-CoT also outperforms it on all three arithmetic tasks (GSM8K, SVAMP, and AQuA). While for node-davinci-092 Automate- CoT achieves an average of 2.4% improvement across all five arithmetic reasoning tasks, illustrat- ing the effectiveness of our proposed approach with different language models. Additionally, Automate- CoT outperforms Auto-CoT in GSM8K by 4.8%. since Auto-Cot CoT only constructs experiments on GSMSK under code-davinci-002. Automate- CoT demonstrates consistent improvement over arithmetic tasks, especially on GSM8K, where it can outperform Manual-CoT by a large margin. Fi- nally, under the self-consistency setting, Automate- CoT also shows similar trends to improve the SC baseline, demonstrating the synergistic effects of our proposed method and self-consistency method,
Hyper-parameter Setting: Under few-shot set- ting, we set max_ mox_ttkens> = 256 for all augmenta- tion, selection and inference. In addition, we set logprobs =5 5 when training. Moreover, we tem- perature 0.7 for evaluation under self-consistency while temperature for all other cases.
5 Experimental Results
The experimental results are shown in Table 1. We discuss our results in three sections based on the task categories. Automate-CoT are averaged over three runs, and the variance over different runs is reported in Appendix Table 7. Overall, Automate- CoT achieves superior results on all tasks. With text-davinci-002, Automate-Coo outperforms Manual-CoT and SC by 2.6% and 3.7% on average.
Commonsense and Symbolic Reasoning Sim- ilarly, on commonsense and symbolic reason- ing tasks, Automate-CoT demonstrates signifi- cant improvement over Manual-CoT, SC, and Auto-CoT. achieves an average of 2.5% and

---

DOMMK
Aodiy
SHAMP
OSGA
Loder
ACCUPO (4)
Render
Sunden
Figure 3: Comparisons between Random Selection, Manual-CoT and Automate-CoT on six datasets.
3.4% improvement on text-davinci-00 and pode-davinci-one respectively, demonstrating that our method is effective on different task types. More surprisingly, the improvement in the Letter (4) is significant, demonstrating our method's ro- bustness to deal with out-of-distribuu data.
GSMBK
SWAMP
Letter
Calor
Calencio
22
100
15
10
Pool
Non-Reasoning Tasks Automate-Coe CoT has also reached great success on question answer- ing (OpenBookQA), natural language inference (e- SNLI), and sentiment analysis (SST-2) tasks by an improvement of 2.8%, 3.4% and 1.3%, respec- tively. The results show that our method can be generalized to various task types and is not limited to reasoning tasks.
Figure 4: The performance across different pool sizes of Automate-CoT compare with Manual-CoTT Pool size refers the number of exemplars in the pool.
diversity, and style. In conclusion, if we simply ran- domly select the exemplars from the pool, it is very likely to obtain much lower accuracy than the manually written method. However, our Automate- CoT can consistently outperform random selection and Manual-CoT which shows the effectiveness of our method.
6 Additional Experiments and Analysis
We further conduct several experiments evaluate the effectiveness of Automate-Co and analyze the contributions of each module. Since queries to text-davinci-000 are limited and expensive, most additional experiments are conducted with code-davinci-002.
6.2 Effects of Pool Size
We further conduct set of experiments to test dif- ferent pool sizes. As shown in Figure 4, if the pool size is limited to only 10, the performance of Automate-Cor CoT is worse than Manual-CoT com- parable with Manual-CoT. turns out that if the pool size is small, Automate-Col is unable to se- lect a good combination to beat carefully designed Manual-Ca Co.T. However, Automate-CoTT can outper- form Manual-CoT when the pool size reaches 20 or larger. The trends show that the performance would be better as pool size keeps increasing. This intuitive and matches our hypothesis because pool size increases, there would be more complex, diverse exemplars to choose from. is expected that the performance would keep increasing, but since more queries for GPT-3 are time-consuming and expensive, we limited these additional experi- ments to have max pool size of 150.
6.1 Effects of Selection Algorithm
After obtaining large pool of exemplars, a natural question would be what is the performance if we randomly select from the pool regardless of order. In Figure 3, we compare the accuracy obtained by random selection, human-written (Manual-CoTi and our Automate-CoT. For random selection, we randomly sample exemplars from the pool and com- bine them regardless of order to form the prompts. We repeat this process five times and report the accuracy with an error bar. The results show that random selection suffers from high variance and rel- atively low accuracy compared to Manual-CoT) and Automate-CoTT Surprisingly, observed the aver- age performance of random selection from model- generated exemplars can outperform Manual-CoT some datasets (e.g. GSM8K, CSQA). This also suggests that manual prompt engincering needs to take efforts to design carefully in terms difficulty,
6.3 Effects of Chain Complexity
is observed that exemplars written by human are rather simple, so we further explore how chain complexity affect performance. We randomly pick

---

RUNS
GSM8K
SVAMP
Letter(4)
METHOD
GSM8K
SVAMP
Letter (4)
Rand Trainina Set)
67.55
78.2
75.0
Zero-Shot-CoT
40.7
62.1
57.6
Rraiinra SeO2
67.93
77.8
76.6
Manual-CoT
46.9
73.5
56.6
Rrndinra Set)s
67.25
77.6
75.8
Auto-CoT
48.9
69.5
59.7
Variance
0.077
0.062
0.426
Cro-Shoot-Automat-CCn
49.1
74.3
59.3
Automate-CoT
49.7
76.1
58.9
Table 2: The effect of different randomly chosen train- ing performance over three datasets.
Table 3:
The performance of automate-Col in zero-
shot setting compared with other baselines. Lightgray highlights main model which uses manually con- structed chain-of-thougle and is not intended for com- parison. We list it here only for reference.
8 exemplars with complex rationale chains (each has 9 hops) and refer to them as Complex-CoT. For human-written exemplars (Mo)ual-CoT) Wei al. (2022b), exemplars are all 2-3 hops. We com- pare them with our Automate-Cot which has an average hop of 4 and ranges from 2-hop to 6-hop on GSM8K dataset. From Figure 1, ManuallCoT has an overall accuracy of 62%, achieving good results on simple questions. However, it suffers from complex math questions, especially 7-hop and 8-hop questions. Complex-CoT can improve the accuracy on complex questions by large mar- gin but it performs poorly on simple questions, which only has an overall accuracy of 60%. In contrast, our Automate-CoT can select a combina- tion of different complex-lewe exemplars automat- ically. It achieves good results on simple questions and reasonable results on complex questions at the same time, outperforming both Manual-Coo CoT and Complex-CoT by large margin. The result shows the superiority of method because it can auto- matically achieve a complexity-diversiy trade-off.
Instead of using 4-8 manual-written exemplars to generate the chains, we simply add "Let's think step by step. " and let LLMs generate the chains. We test the result under text-davinci-022 model on GSM8K, SVAMP, and Letter (4) and compare it with Zero-shot-CoT, Manual-CoT and Auto-CoT. Surprisingly, we observe the result can be compa- rable and even outperform Manual-CoT and Auto- CoT a bit as shown in Table 3. The results fur- ther demonstrate that our method can effectively select suitable combination of exemplars even from a pool that may contain low-quality chains. In conclusion, if dataset already has manually written chains, our method can be applied to boost the performance. If a dataset does not have man- ually written chains, our method can still be used to achieve higher accuracy than if it had manually written chains, demonstrating the superiority of our method.
6.4 Effects of Training Example Selection
7 Ablation Study
Since training examples construct CoT are ran- domly chosen, we also measure the performance vary regarding this random selection. Three dif- ferent randomly chosen training sets are used to train Automate-CoT and the results are reported in Table 2. According to the result, Automate-CoTT shows its robustness to training examples. Ran- domly chosen training examples have quite small impact the result.
In this section, we further conduct ablation exper- iments to verify the advantage of the generated prompts on four factors, respectively.
Advantage over Order Factor of Automate-Col CoT order factor can be viewed in two ways. Firstly, it requires large human effort to determine good order by trying many different orders on validation sets. However, Automate- can automatically construct the exemplars without further adjustment to have good result. Secondly, Automate- CoT is less affected by the order sensitiv- ity. We further conduct an experiment to compare selected exemplars and random permutations of Iitomate-CoT"s selected exemplars as shown in Table We randomly permutate the selected exem- plars to see how performance varies compared the selected order by Automate-Col1 is observed that the order sensitivity still exists and our se-
The advantages
6.5 Bypass Manual Effort by Zero-shot-CoT
Starting with 4-8 manually constructed chain-of- thought exemplars, our methods show great success in automatically generating, pruning, and selecting suitable exemplars for each task. After that, we raise a new question: Can we further bypass the effort of writing the initial chain-of-the oftthghhtt exem- plars? Based on current research of Zero-Shot- COT (Kojima et al., 2022), we found is possible.

---

RUNS
GSM8K
SVAMP
Letter(4)
C,, F1, G1, Hi] for GSM8K. Then we copy this set and edit its written linguistic style manually to be worse while keeping
plars S1
perm perm(Automate-CCom
66.7
77.2
73.0
permi D
66.6
78.4
72.6
permí Automate-CoT])
66.9
78.0
72.0
the order, complexity, and diversity the same which gives S2 = [A2, B2, C2 D2, Fe2, F2, G2, Hz]- Now we have 16 examplars says S
jerm(Automate--Co)
67.8
78.2
74.2
perm )oTo
67.5
78.1
75.0
Automate-CoT
68.4
78.7
75.2
Meang
67.3 64
78.220.48
73.711.21
[A1, A2, B1, B2...., H1, Hz). A-H represents the
No.1-8 exemplars. Subscript represents the origi- nally selected exemplars and 2 represents the edited ones. Then, Automate-Cov selects 8 exemplars from the previous 16 exemplars. Note that we limit Cut to select exactly one of [A], A2] and [Bi, B3] ... and keep the same order A-H. Subsequently, when we perform Automate-CoT1 al- gorithm, we observe that Automate-Col is able to successfully select the original exemplars S1. Fur- thermore, find that the selected exemplars outperform the non-selected exemplars by 2%.
Table 4: Comparison of different permutations orders of Automate-CoT's selected examplars.
lected exemplars have better performance than that of all 5 random permutation runs, demonstrating Automate-Col Co can automatically choose good order without any human effort.
Advantage over Complexity Factor As dis- cussed the complexity factor Section 2, we show that the complexity of manually written chains is quite simple (less than or equal to 3 hops). It would require more human effort to design com- plex rationales. However, Automate-CoT can auto- matically augment and select examples with differ- ent complexity, reaching better trade-off accuracy between simple questions and complex questions (Appendix Table 9).
8 Related Work
In this section, we first review the recent progress of prompt-based learning ($8.1) and chain-of ofain-of-thought prompting ($8.2), and then discuss the black-box optimization methods ($8.3).
8.1 Prompt-based Learning
Advantage over Diversity Factor The diversity of Manual-CoT or Complexity- is limited. For example, every exemplar of ComplexityCooT has the same complexity and every exemplar of Manual-CoT ranges from 1-3 hops as illustrated in the motivation section. However, Automate-Con can automatically select an optimal combination of complexity that best suits the dataset. For example, our selected exemplars on GSM8K have an aver- age hop of 5.4 and range from 3 hops to 8 hops shown in Appendix G. It contains both simple exemplars and complex exemplars which reach the best performance.
Prompt-based Learning (Prompting) aims to lever- age large language models (LLMs) (Devlin et al., 2018; 8; Liu et al., 2019; He et al., 2021; Diao et al., 2020, 2021) to trigger helpful knowledge for down- stream tasks. Existing prompting methods can be categorized into two types based on their nature: 1) discrete prompts (Wallace et al., 2019; Shin et al., 2020; Jiang et al., 2020; Yuan et al., 2021; Haviv et al., 2021; Gao et al., 2021; Ben- -avid
et al., 2022; Davison et al., 2019; Su al., 2022: Diao et al., 2022; Guo al., 2023) and continuous prompts (Zhong et al., 2021; Qin and Eisner, 2021; Hambardzumyan et al., 2021; Liu et al., 2021; Han et al., 2021; 1; Li and Liang, 2021; Yang et al., 2023). Discrete prompts optimize a sequence of discrete tokens, while continuous prompts optimize se- quence of vectors. One of the most important ad- vantages of prompting is saving fine-tuning costs by refraining from the parameter changes of large language models, and we only need to optimize a small set parameters.
Advantage over Style Factor Our extensive ex- perience with multiple experiments indicates that a good linguistic style is typically formal and de- tailed. This style entails the use of (1) explicit and logical connection words (e.g., "so", "that means"), (2) detailed reasoning steps within a single sen- tence, (3) symbols when appropriate (c.g., using the $ symbol denote monetary values), and (4) min- imizing the use of abbreviations. We further con- duct an ablation experiment to test how our method can choose the examples with better style. Firstly, we use Automate- to select rationale exem-
8.2 Chain-of-thought Prompting
Mfain-of-though (Wei et al., 2022b) introduces a chain of rationale steps for each exemplar of

---

in-context learning and significantly improves the performance on several complex tasks like arith- metic reasoning, commonsense reasoning, and symbolic reasoning. Based on this simple yet effec- tive idea, many following works propose different strategies to improve it: self-consistency (Wang et al., 2023), explanation learning (Lampinen et al.. 2022), complexity-based prompting (Fu et al., 2023), self-training (Huang al., 2022), voting verifier (Li et al., 2022a), zero-shot prompting (Ko- jima et al., 2022; Fung et al., 2022), and bootstrap- ping (Zelikman et al., 2022).
prompting methods. However, despite these excit- ing results, there are still some limitations to our current work, as well as potential opportunities for future research.
Comparision with Fine-tuning Our main base- lines include original chain-of-thought (Wei et al., 2022b), self-consistency (Wang et al., 2023) which are manual-written based prompt method. In addition, we also compare the clustering-baseer and retrieval-based methods to select the prompt exemplars like Auto-CoT (Zhang et al., 2023), BM25 (Robertson, 2009), PromptPG (Lu al., 2023). As large language models are dominating the field, the performance of training the large lan- guage models by using these labeled data might be interesting. However, it is not covered in this study due to the prompt setting of this study and limited resources.
8.3 Black-box Optimization
Nowadays, large language models provide services as commercial APIs deployed in the cloud, such as OpenAl's GPT-3 (Brown et al., 2020) and Chat- GPT It usually accepts query inputs and outputs the predictions with web interface. Their model parameters and gradients not accessible, caus- ing difficulties in optimization with gradients. Pre- vious research on black-box optimization mainly focuses on score-based black-box adversarial at- tack (Ilyas et al., 2018, 2019; Huang and Zhang, 2020; Andriushchenko et al., 2020; Cheng et al., 2019). Most recently, black-box prompt learn- ing (Diao et al., 2022; Sun al., 2022: Prasad et al., 2022) is introduced, aiming to optimize the prompts without accessing gradients, but their mod- els suffer from limited reasoning abilities and are limited to zero-shot settings with classification task.
Prompt Style Definition Another limitation of this work is that it does not provide rigorous definition of what constitutes good versus bad lin- guistic style. While have observed several pat- terns of good and bad style during numerous exper- iments, and the results show that Automate-Coo is able to mitigate style sensitivity in Manual-CoT, we cannot determine what perfect style entails. As such, we acknowledge that defining what consti- tutes good versus bad linguistic style can be chal- lenging task and an important area for further ex- ploration and development.
9 Conclusion
Acknowledgments
In this paper, we proposed a Mfain-of-thoughy op- timization method consisting of three steps: aug- ment, prune, and select. Automate-Coli first gener- ates rationale chains according to the standard CoT process with several exemplars, and then prunes those incorrect ones according to the consistency of the predicted answer and ground- ground-truth answer. Fi- nally, we apply a variance-reduced policy gradient strategy to estimate the gradients and optimize the latent variables to select better CoT's. Experimental results demonstrate the effectiveness of our method arithmetic reasoning, commonsense reasoning, symbolic reasoning tasks, and non-reasoning tasks.
We thank the anonymous reviewers for their valu- able suggestions. This work was supported by the General Research Fund (GRF) of Hong Kong (No. 16310222) Shizhe Diao supported by the Hong Kong Ph.D. Fellowship Scheme (HKPFS).
References
Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik Kedzio-kediirskii.. Yejin Choi, and Hannaneh Ha- jishirzi. 2019. MathQA: Towards interpretable math word problem solving with operation- for- malisms. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume (Long and Short Papers), pages 2357-2366 Minneapolis. Minnesota. Association for Computational Linguistics.
10 Limitations
It is shown that Automate-Cot demonstrates supe- rior performance over previous chain-of-thought
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. 2020. Square at-

---

tack: a query-efficient black-box adversarial attack via random search. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-
Joe Davison, Joshua Feldman, and Alexander Rush. 2019. Commonsense knowledge mining from pre- trained models. In Proceedings of the 2019 Confer- ence on Empirical Methods in Natural Language Pro- cessing and the 9th International Joint Conference on Natural Language Processing (EMNLP- pages 1 117--1178, Hong Kong, China. Association for Computational Linguistics.
28, 2020, Proceedings, Part XXIII. pages 484-501. Springer.
Eyal Ben-David, Nadav Oved, and Roi Reichart. 2022. PADA: Example-based prompt learning for on-the- fly adaptation to unseen domains. Transactions of the Association for Computational Linguistics, 10:414 433.
Jacob Devlin, Ming-Wos Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. BERT: Pre-training of Deep Bidirectional Transformers for Language Un- derstanding. arXiv.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger. Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Bemner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shor learners. Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual.
Shizhe Diao, Jiaxin Bai, Yan Song, Tong Zhang, and Yonggang Wang. 2020. Zen: Pre-training chinese text encoder enhanced by n-gram representations. In Findings of the Association for Computational Linguistics: EMNLP 2020. pages 4729 4740.
Shizhe Diao, Zhichao Huang. Ruijia Xu, Xuechun Li, Yong Lin, and Tong Zhang. 2022. Black-box prompt learning for pre-trained language models. ArXiv preprint, abs/2201.0853 108531.
Shizhe Diao, Ruijia Xu, Hongjin Su, Yilei Jiang, Yan Song, and Tong Zhang. 2021. Taming pre-trained language models with n- gram representations for low- resource domain adaptation. In Proceedings of the 59th Annual Meeting of the Association for Compu- rational Linguistics and the 11th International Joint Conference on Natural Language Processing (Vol- ume 1: Long Papers), pages 3336-3349.
Oana- Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom. 2018. e-snli: Natu- ral language inference with natural language explana- tions. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Informa- tion Processing Systems 2018, NeurlPS 2018, Decem- ber 3-8, 2018, Montréal, Canada, pages 9560-9572.
7he Dong. Andriy Mnih, and George Tucker. 2020. Dis- arm: An antithetic gradient estimator for binary latent variables. In Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021. Evaluating large lan- guage models trained on code. ArXiv preprint, abs/2107.033 00.7033744.
Yao Fu, Hao Peng. Ashish Sabharwal, Peter Clark, and Tushar Khot. 2023. Complexity-based prompting for multi-step reasoning. In International Conference Learning Representations
Shuyu Cheng, Yinpeng Dong, Tianyu Pang, Hang Su, and Jun Zhu, 2019. Improving black-box adversar- ial attacks with bransfer-based prior. In Advances in Neural Information Processing Systems 32: An- nual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 10932-10942.
Yi R Fung. Tuhin Chakraborty, Hao Guo, Owen Rambow, Smaranda Muresan, and Heng Ji. 2022. Normsage: Multi-lingual multi-cultural norm discov- ery from conversations on-the-fly. -ly. arXiv preprint 10..8044
Tianyu Gao, Adam Fisch, and Danqi Chen. 2021. Making pre-trained language models better few-shot learners. In Proceedings of the 59th Annual Meet- ing of the Association for Computational Linguistics and the 11th International Joint Conference on Natu- ral Language Processing (Volume I: Long Papers), pages 3816-3830, Online. Association for Computa- tional Linguistics.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gauray Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022. Palm: Scaling language modeling with pathways. ArXiv preprint, abs/2204.02311.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavar- ian, Jacob Hilton, Reiichiro Nakamo, Christopher Hesse, and John Schulman. 2021. Training veri- fiers to solve math word problems. ArXiv preprint, abs/21 10. 14168.
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021. Did aristotle use laptop? question answering benchmark with implicit reasoning strategies. Transactions of the

---

Association for Computational Linguistics, 9:346-
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large lan- guage models are zero-shot reasoners. In Advances in Neural Information Processing Systems.
361.
Chunxi Guo, Zhiliann Tian, Jintao Tang, Shasha Li, Zhihua Wen, Kaixuan Wang, and Ting Wang. 2023. Retrieval--ugmmented gpt-3.5- work with sample-aven aware prompting and dynamic re- vision chain. arXiv preprint arxiv:2307.00 230.0004..
text-to-sql sql frame-
Rik Koncel-Kedziorski, Subhro Roy, Aida Amini, Nate Kushman, and Hannaneh Hajishirzi. 2016. MAWPS: A math word problem repository. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies, pages 1152-1157, San Diego, California. Association for Computational Linguistics.
Karen Hambardzumyan, Hrant Khachatrian, and Jonathan May. 2021. WARP: Word-level Adversarial ReProgramming In Proceedings of the 59th Annual Meeting of the Association for Computational Lin- guistics and the 1 11th International Joint Conference on Natural Language Processing (Volume I: Long Pupers), pages 4921-4933, Online. Association for Computational Linguistics.
Yuxuan Lai, Chen Zhang, Yansong Feng, Quzhe Huang. and Dongyan Zhao. 2021. Why machine reading comprehension models learn shortcuts? In Find- ings of the Association for Computational Linguis- rics: ACL-IJCNLP 2021, pages 1802, Online. Association for Computational Linguisties.
Xu Han, Weilin Zhao, Ning Ding, Zhiyuan Liu, and Maosong Sun. 2021. PTR: Prompt Tuning with Rules for Text Classification. ArXiv preprint, abs/2105.11259)
Andrew Lampinen, Ishita Dasgupta, Stephanie Chan, Kory Mathewson, Mh Tessler, Antonia Creswell, James McClelland, Jane Wang, and Felix Hill. 2022. Can language models learn from explanations in con- text? In Findings of the Association for Computa- rional Linguistics: EMNLP 2022. Association for Computational Linguistics.
Adi Haviv, Jonathan Berant, and Amir Globerson. 2021. BERTese: Learning to speak to BERT. In Proceed- ings of the 16th Conference of the Furopean Chap- ter of the Association for Computational Linguistics: Main Volume, pages 3618-3623, Online. Association for Computational Linguistics.
Yihuai Lan, Lei Wang, Qiyuan Zhang, Yunshi Lan, Bing Tian Dai, Yan Wang. Dongxiang Zhang, and Ee-Peng Lim. 2022. Mwptoolkit: an open-source framework for deep learning-based math word prob- lem solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 13188- 13190.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021. DEBERTA: Decoding- enhanced bert with disentangled attention. In Inter- national Conference on Learning Representations.
Jiaxin Huang. Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2022. Large language models can self-improve. ArXiv preprint, abs/2210.11610.
Brian Lester, Rami Al-Rfou, and Noah Constant. 2021.
The power of scale for parameter-efficient prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. pages 3045-3033000 -3059, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics.
Zhichao Huang and Tong Zhang. 2020. Black-box ad- versarial attack with transferable model-based embed- ding. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26- 30, 2020. OpenReview.net.
Xiang Lisa Li and Percy Liang. 2021. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4582- 4597, Online. Association for Computational Lin- guistics.
Andrew Ilyas. Logan Engstrom, Anish Athalye, and Jessy Lin. 2018. Black-box adversarial attacks with limited queries and information. In Proceedings of the 35th International Conference on Machine Learn- ing, ICML 2018 Stockholmsmüsssnn Stockholm. Swe- den, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 2142-2151. PMLR.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2022a. On the advance of making language models better reasoners. ArXiv preprint, abs/2206.02336..
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. 2019. Prior convictions: Black-box adversarial at- tacks with bandits and priors. In 7th International Conference on Learning Representations, ICLR 2019. New Orleans, LA, USA, May 6-9, 2019. OpenRe- view.net.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian Maun-Gung Lou, and Weizhu Chen. 20226. On the advance of making language models better reasoners.
Zhenghao Jiang, Frank F. Xu, Jun Araki, and Graham Neubig. 2020. How we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-438.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blun- som. 2017. Program induction by rationale genera- tion: Learning to solve and explain algebraic word

---

problems. In Proceedings of the 55th Annual Meer- ing of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 158-167, Vancouver, Canada, Association for Computational Linguisties.
2022. Training language models follow in- structions with human feedback. ArXiv preprint. abs/2203.02155..
Pantelis Papadopoulos, Stavros Demetriadis, Joannis Stamelos, and Ioannis Tsoukalas. 2010. The ef- feet of prompting to students with different learn- ing styles. Multicultural Education and Technology Journal, 4:198-214 213.
Jiachang Liu, Dinghan Shen, Yizhe Zhang. Bill Dolan, Lawrence Carin, and Weizhu Chen. 2022. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extrac- tion and Integration for Deep Learning Architectures, pages 100-114, Dublin, Ireland and Online. Associa- tion for Computational Linguisties.
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021. Are NLP models really able to solve simple math word problems?
Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2080-20999 Online. Association for Computational Linguisties.
Xiao Liu, Yanan Zheng, Zhengxiao Du Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang. 2021. GPT Understands, Too. ArXiv preprint, 011/2103.1088.
Xinyu Pi, Qian Liu, Bei Chen, Morteza Ziyadi, Zeqi Lin, Qiang Fu, Yan Gao, Jian-Guang Lou, and Weizhu Chen. 2022. Reasoning like program executors. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 761- 779. Association for Computational Linguistics.
Yinhan Liu, Myle Oit, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke 7ettlemoyer, and Veselin Stoyanov. 2019. RoBERTa: A Robustly Optimized BERT Pretrain- ing Approach. arXiv.
Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenRe- view.net.
Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2022. Grips: Gradient-free, edit-based in- struction search for prompting large language models. ArXiv preprint, abs/2203.07288
Guanghui Qin and Jason Eisner. 2021. Learning how to ask: Querying LMs with mixtures of soft prompts. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, pages 5203-5212, Online. Association for Computa- tional Linguistics.
Pan Lu, Liang Qiu, Kai-Wei Chang, Ying Nian Wu, Song-Chum Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan. 2023. Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning. In International Conference on Learning Representations (ICLR).
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022. 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 Compu- tational Linguistics (Volume 1: Long Pupers), pages 8086-8098, Dublin, Ireland. Association for Compu- tational Linguistics.
Colin Raffel, Noam Shazeer, Adam Roberts, Kather- ine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21 11(140):1-67.
S. Robertson. 2009. The Probabilistic Relevance Frame- work: BM25 and Beyond. Foundations and Trends in Information Retrieval, 3(4):333-389
Shen-yun Miao, Chao-Chun Liang, and Keh-Yih Su. 2020. A diverse corpus for evaluating and developing English math word problem solvers. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 975-984, Online. Association for Computational Linguistics.
Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. 2020. AutoPrompt: Elic- iting Knowledge from Language Models with Auto- matically Generated Prompts. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 4222 4235, Online. Association for Computational Linguistics.
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. 2018. Can suit of armor conduct elec- tricity? new dataset for open book question swering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2381-2391, Brussels, Belgium. Association for Computational Linguistics.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. 2013, Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empiri- cal Methods in Natural Language Processing, pages 1631 1-342, Seattle, Washington, USA. Association for Computational Linguistics.
Long Ouyang, Jeff Wa, Xu Jiang, Diogo Almeida, Car- roll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.

---

Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao. Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adria Garriga-Alonoo al. 2022. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. ArXiv preprint, abs/2206. 15.
on Machine Learning Research. Survey Certifica- tion.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, brian ichter. Fei Xia, Ed H. Chi, Quoe V Le. and Denny Zhou. 2022b. Chain of thought prompt- ing clicits reasoning in large language models. In Advances in Neural Information Processing Systems.
Hongjin Su, Jungo Kasai, Chen Henry Wu, Weijia Shi, Tianlu Wang. Jiayi Xin, Rui Zhang. Mari Ostendorf, Luke Zettlemoyer. Noah A Smith, et al. 2022. Selec- tive annotation makes language models better few- shot learners. ArXiv preprint, abs/2209.01975.
Ronald J Williams, 1992. Simple statistical gradient- following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256.
Saku Sugawara, Kentaro Inui, Satoshi Sekine, and Akiko Aizawa. 2018. What makes reading compre- hension questions easier? In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4208-4219, 19, Brussels, Belgium. Association for Computational Linguistics.
Yichong Xu, Chenguang Zhu, Shuohang Wang. Siqi Sun, Hao Cheng, Xiaodong Liu, Jianfeng Gao, Pengcheng He, Michael Zeng, and Xuedong Huang. 2022. Human parity on commonsenseqa: Augment- ing self-attention with external attention. In Pro- ceedings of the Thirty-Firss First International Joint Con- ference on Artificial Intelligence, IJCAI-22, pages 2762-2766 Main Track.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. 2022. Black-box tuning for In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 118811208855, PMLR.
Ke Yang. Charles Yu, Yi R Fung. Manling Li, and Heng Ji. 2023. Adept: A debiasing prompt framework. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10780-10788.
Alon Talmor Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019. CommonsenseQQ:: A ques- tion answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume I (Long and Short Papers). pages 4149-4158, Minneapolis, Minnesota. Association for Computational Linguistics.
Weizhe Yuan, Graham Neubig, and Pengfei Liu. 2021.
BARTScore: Evaluating generated text text gener- ation. In Advances in Neural Information Processing Systems.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Good- man. 2022. STar: Bootstrapping reasoning with rea- soning. In Advances in Neural Information Process- ing Systems.
Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gard- ner, and Sameer Singh. 2019. Universal adversarial triggers for attacking and analyzing NLP. In Proceed- ings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Inter- national Joint Conference on Natural Language Pro- cessing (EMNLP-IJCNI.P)) pages 2153-2162, Hong Kong, China. Association for Computational Linguis- tics.
Yiming Zhang, Shi Feng, and Chenhao Tan. 2022. Ac- tive example selection for in-context learning. In Pro- ceedings of the 2022 Conference on Empirical Meth- ods in Natural Language Processing, pages 91 34- 9148,
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2023. Automatic chain of thought prompting in large language models. In International Confer- ence on Learning Representations.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, and Denny Zhou. 2022. Rationale- augmented ensembles in language models. ArXiv preprint, /bb///20.00047,
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. 2021. Calibrate before use: Improv- ing few-shot performance
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representa- tions.
language models. Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Vir- tual Event, volume 139 of Proceedings of Machine Learning Research, pages 12697-12706. PMLR
Zexuan Zhong, Dan Friedman, and Danqi Chen. 2021. Factual probing is [MASK]; Learning vs. learning to recall. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 5017-5033, Online. Association for Computational Linguistics.
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. 2022a. Emer- gent abilities of large language models. Transactions

---

Xiao Zhou, Weizhong Zhang. Zonghao Chen, Shizhe Diao, and Tong Zhang. 2021. Efficient neural net- work training via forward and backward propagation sparsification. In Advances in Neural Information Processing Systems, volume 34, pages 15216-15229.

---

Algorithm The black-box optimization procedures.
Require: Input batch S, Label batch Y. Parameter of categorical distribution Pl, Pn. Prediction model G, Loss function L.
1: for < I do
2: Sample [(4] Cat(pi); ... :Jn (Pn
3: T(k) (k)
(k) 11 (...v(nn))
4: end for
5: Lave 1
Σl= (( S),Y)
6: for S n do
7: gp. = - Ek=1 vp, log (h) (C(E((5))) V) Lavg)
8:
+ projc (p; - 1l 9p.)
9: end for
10: return Pl Pn
A Algorithm Details
In this section, we provide more details about the derivation of the equation (1) in Section 3.2. Given the loss function:
By (C(T) P(T)
(4)
We can estimate the gradient of p; by:
/ L(T)V,,,(T) dT
V Er [C(T)]
/ ((T) P(T)
P(T) v. P(T)
/ P(T) P. log P(T) dT
(5)
-EP(T) [C(T)V log 11 P(t,)
-EP(T) L(T)V Σ log P(Lj) j=1
=EP(T) [C(T)V,, p. log P(4))
The j-th component of Vn log P(4:) could be solved explicitly by:
Vp,, log P(t.) Vp.,, log Pi.ji
(6)
When j ji. it is obvious that V pc. log P(4:) P4Js
I.
When # j.. equation (6) is calculated by:
N
Pig log P(tz) =V pcs log(1 Σ
Pi.))
k= k
Ek=1, PiAk
Pijis
Therefore, we adopted variance-reduced policy gradient estimator (VR-PGE) as described in Williams (1992); Dong et al. (2020); Zhou et al. (2021) to mitigate the high-variance issue of PGE. The estimated gradient is calculated by:

---

ト - ciToo)) pp lug P((:)
((TT))
Dp.
(8)
where T(K), k= 1,.., / are sampled independently from P(T). Thus, the prompt token distribution p; can be updated by projected stochastic gradient descent algorithm:
pi + projo (p: - Ip.), i 1, n
(9)
where is the learning rate of prompt learning, is the sample size, and proje is the projection calculation. The detailed training procedure of our VR-PGE algorithm is displayed in Algorithm 1.
B
Detailed Experimental Setting
DATASET
TASK TYPE
Ex.
EVAL.
EVAL. SPLIT TRANSFERRED
GSM8K (Cobbe 2021)
Arithmetic
1319
Test
X
ASDiv (Miao al., 2020)
Arithmetic
2096
Test
SVAMP (Patel 2021)
Arithmetic
1000
Test
AQuA (Ling et al., 2017)
Arithmetic
254
Test
X
SingleOp
Arithmetic
562
Test
CSQA* (Talmor al., 2019)
Commonsense
1221
Validation
X
StrategyQA* (Geva al., 2021)
Commonsense
1880
Validation
X
Letter (Wei al., 2022b)
Symbolic
Test (OOD)
OpenBookQA (Mihaylov
2018)
Question Answering
Test
e-SNLI (Camburu et al., 2018)
Narural Language Inference
1000
Test
X
SST-2* (Socher al., 2013)
Sentiment Analysis
872
Validation
X
Table The overall statistics of the datasets. # Ex.: the number of few-shot chain-of of-thoughttthtttt exemplars used prompt each task. # EVAL.: the number of evaluation data. EVAL. SPI.T: evaluation split. TRANSFERRED: checkmark means that the exemplars are generated and trained from other datasets and then applied to this task. * SingleOp a subset of MAWPS publicly available test set labels, so we simply follow the setting by Wei et al. (2022b) and Wang et al. (2022) to evaluate the performance of the validation set. *: Following Wang et al. (2022), we evaluate the first 1,000 data points for fair comparison.
al., 2016). * CSQA. StrategyQA, and SST-2 do have
B.1 Datasets and Evaluation Metrics
Following Wei et al. (2022b), we conduct our experiments on eight reasoning tasks, including five math word problem datasets: GSM8K, ASDiv, SVAMP, AQuA, and SingleOp: two commonsense reasoning datasets: CommonsenseeA (CSQA) and StrategyQA, and one symbolic reasoning task: Last Letter Concatenation (Letter (4)). We also generalize our method non-reasoning tasks including one question- answering task (A))n one natural language inference task (e-SNLI), and one sentiment analysis task (SST-2). The detailed statistics the datasets are listed in Table To make a fair comparison with our baselines, we use the same number of exemplars as Wei et al. (2022b) and Wang et al. (2022), as shown in Table 5. We keep the same setting for the evaluation split as well. By default, we use the test split for evaluation, and for datasets that do not have publicly available test set labels, we evaluate the validation set instead. In addition, for last letter concatenation, since the model has already achieved almost 100% accuracy under the in-distribution setting, we only test the (OOD) setting, Letter (4), where prompts are 2-letters, and test examples 4eltters. The evaluation metric for all tasks is the exact match accuracy. First, conduct pre-processing for predictions to remove all the special symbols. For example, "$100,000" will be processed "100000". Then we check if has the same value as the ground truth to calculate the exact match accuracy.
B.2 Baselines
our experiments, the following three methods serve as the main baselines: chain-of of-thought (Manual-Cot) (Wei et al., 2022b): standard chain-of of-thought prompting which provides manual-written intermediate reasoning steps.

---

self-consistency (SC) (Wang et al., 2023): an improved version of COT. Instead of greedy decoding, it samples diverse set of reasoning paths and chooses the most common answer.
Auto-CoT (Zhang et al., 2023): an automatic exemplars construction method that applies clustering techniques to sample questions and then generates chains.
Our experiments are conducted with two popular large language models:
GPT-3 (Brown et al., 2020): we test advanced version of GPT-3, next-davinci-o0e which corresponds InstructGPT (Ouyang al., 2022) model.
which has better code representation ability. We utilize the public APIs directly from ApenAT's services". In our main experiments, we test on both text -ext-davinci-002 and code-davinci -002 engines. However, in additional experiments, we mainly test on code-davinci-00 -002 for two reasons (1) It is the most capable model available at the time we were conducting our experiments, consistent with the observations in previous studies (Wei et al., 2022b; Wang et al., 2023; Miao et al., 2020). (2) Compared costly text-davinci-022 it is free of charge because are in the initial limited beta period during our experiments process.
CodeX (Chen al., 2021): we test code-davincis
B.3 Implementation
Following Wei et al. (2022b) and Wang et al. (2022), keep the same number of exemplars (4-8) listed in Table 5. For main experiments, we augment and prune a pool of 100 high-quality exemplars for datasets. Firstly, pool construction questions are randomly sampled and then fed LLMs to construct model-generated answers with rationale chains. Given that some datasets only have the test split, we use the pool result of GSM8K and transferred it to these datasets for further inference. Here for arithmetic reasoning tasks, pool construction questions are randomly sampled from the training split of GSM8K and AQuA. For CSQA and StrategyQA, exemplars are randomly sampled from the official training split (Talmor et al., 2019) and question-only set from BIG-bench collaboration (Srivastava et al., 2022). For letter concatenation, exemplars randomly sampled from the 2-letter set. After the pool is constructed, we use labels to prune the incorrect model-generated exemplars and retain 100 high-quality exemplars.
Augment and Prune:
Select: The train set and validation set are also randomly sampled following the same rule as above except Letter (4) dataset. Since LLM has already reached almost 100% accuracy on the 2-letter set, we choose to optimize the model based on the 3-letter OOD set. Thus the train set and validation set are randomly sampled from the 3-letter set. Both the train and validation sets have a size of 100 to reach performance and cost trade-off. Then by utilizing the log probability returned by API calls, we calculate the cross-entropy loss of the answer token. Finally, we optimize the latent variables by Adamn (Loshchilov and Hutter, 2019) for 5 epochs with a learning rate of 10-3 and batch size of 10. After optimization, as shown in Figure 2 inference stage, we choose the exemplars combination (arg max p.) with the highest validation accuracy to be further evaluated on the test set. By default, we query the language model once to get the answer. Under the self-consistency setting, similar to Wang et al. (2023), we query the language model 40 times and choose the most consistent one as the final answer. Hy paraamearreeetr Setting: Under few-shot setting, we set max_ _o_kttooessss 256 for all augmentation, selection and inference. In addition, set logprobs = when training. Moreover, set temperature 0.7 for evaluation under self-consistency while temperature 0 for all other cases. Under zero-shot setting ($6.5), we keep the same hyper-panne parameters Kojima al. (2022) which first uses max max_moloeeeeeeaaa tokens 128 for generating the rationale chains and then uses max_ tokettoees-- 32 for generating the answers to construct the pool. The
for selecting and evaluating are the same as the few-shot setting above.
More Experiment Results
C.1 Experiments under ChatGPT
To further verify the effectiveness of Automate-Coff further conduct the experiments on gpt-3.5-turbo 5-turbo. Cutomate-CoT also shows consistent improvement on each task with 2.8% improvement arithmetic

---

METROD
GSM8K
ASDIV
SVAMP
AQUA
SINGLEOP
CSQA
STQA
LETTER (4) OBQA
E:SNLI
SST
AVG.
Manual-CoT
63.1
BB255
64.2
73.7
73.8
45.3
87.9
76.1
58.9
73.4
81.4
76.3
87.2
72.6
PrompiPG
66.6
76.7
75.6
46.1
89.1
77.8
60.2
74.8
81.8
77.8
87.8
74.0
Meuns
56.4
76.5
77.6
45.7
89.7
79.0
60.0
73.6
80.4
78.4
84.1
73.8
AutommiooCoo
68.0
81.7
14.6
79.1
46.91
91.511
80.51a.0
64.51
7..2
83.0"..0
81.4
87.7
76.419
Table 6: The overall performance of Automate- CoT under gpt-3.5-turbo and the comparison with eetrieval-basee and clustering- exemplars selection methods.
METHOD
GSMSK
ASDIV
SVAMP
AQLA
SINGLEÖP
CSQA
STQA
LETTER (4)
inst-dawvinci-0022
Automate- CoT
0.14
0.29
0.17
0.21
0.08
0.06
0.26
0.04
Aulomate-CoI(SC)
0.02
0.18
0.06
0.14
0.04
0.01
0.07
0.04
cook--dwvinci-002
Automate CoT
0.19 0.09
0.78
0.33
0.09
0.05
0.17
0.95
0.02
CUloSS)
Table 7: The variance of the results in Table over runs. (SC) denotes under self-consistency setting.
reasoning, 3.9% improvement commonsense reasoning, 3.2% on symbolic reasoning, and 2.8%
improvement overall as shown in Table 6.
C.2 Comparison with Retrieval Methods
We also compare Automate-CoT with simple retrieval method BM25 (Robertson, 2009) and reinforcement learning-band retrieval method PromptPG (Lu et al., 2023). We first implemented a BM25 selection method and tested the performance on all the datasets. The results are shown in Table 6. It indicates that retrieval-basee methods can only select examples with similar meaning to the query question while the diversity is overlooked. As shown in the table, the average performance of the BM25 retrieval-based method even has 1% degradation compared to Manual-CoT, and 3,8% lower than Automate-Cole A similar phenomenon is observed in Auto-CoT (Zhang et al., 2023), which indicates that with similar questions being sampled for test questions, Strrivall-QCCol is negatively affected by misleading by similarity.
In addition, we also compare with PromptPG (Lu et al., 2023), a dynamic example-selection bascline. We adopt the same setting as ours for PomptPG, where the number of training examples is 100, the size of the candidate pool is 100, and the backbone model is gpt-3.5-turbo. Further, we keep the same prompt format as the original Mhain-of-thoughe and ours. The other settings settings provided by their original code. The results are shown in Table 6. It indicates that Automate-CoT outperforms PromptPG.
consistent with the
C.3 Comparison with Clustering Methods
We further conduct additional experiments to compare Automate-CoT with methods selecting demon- stration exemplars through clustering. We use K-Means as the clustering method and create k clusters according to the number of exemplars specified in Table 5. Then the demonstration exemplars prompt the language models. The results are shown in Table 6. indi- cates that clustering-basee methods can select examples with different semantic meanings and generally perform better than Manual-CoT, However, the complexity and diversity are overlooked. For example. most of the selected few-shot exemplars in GSM8K have around 3-4 hops where complex questions and modcrately difficult questions are overlooked. As result, it generally performs worse than Automatc-CoT with 2.6% gap.
these k representative exemplars
C.4 Variance Report
Since Cotos results in Table are averaged over three runs, we also report the variance in Table 7 here. It is observed that Automate- CoT achieves quite a low variance, especially compared to the large variance Manual-Col CoT as shown in $ 2 Motivation.

---

D Additional Comparison with Fine-tuning
Since our method uses a training-basee pipeline, we also compare it with fine-tuning large language models in terms of the number of parameters, training cost, estimated total training cost, and required training set size. As shown in the study of Cobbe el al. (2021), fine-tuning on gpt-3 requires thousands (c.g., 8000) of training examples to be effective while Mitoomatc-ool only needs 100 training examples. In addition. fine-tuning has a larger training and inference cost than Automate-Cof because it not only requires one-off fine-tuning cost but also has higher unit price on subsequent usage.
For Automate-CoT, under the setting of gpt-3.5-turbo. the direct usage is $ 0.0015/ / 1k tokens for input and $ 0.002 / Ik tokens for output. With the training epochs of 3, training set size of 100 and a validation set size of 100, an imput length of around 750 tokens and an average output length of 150 tokens, it takes about (750/1000- 0..00..05555.. + 150/ 10000 0.002) 1000 10-3 3 (750/1000 0.0015 150/ 10000 0.002) 100 3= $ 4.7. However, fine-tuneing, given the training price of gpt-3.5-turbo is 0.008 1K tokens, the usage finetuned gpt-3.5-turbo is $ 0.0015 IK tokens for input and S 0.002 1K tokens for output tokens. Under the finetuning setting, suppose the average length of training examples is 300 tokens, and training a whole training set of 8000 examples for 3 epochs takes about 300/ 5000/100-00 8000 3 0.008= $ 57.6, which costs 12x more than Automate-Cor!
It is also worth noting that the further usage of finetuned gpt-3.5-turbo is $ 0.012 1K tokens for input and $ 0.016 / 1K tokens for output while Automate-Cof1 remains the normal cost, which is 8x less cost than fine-tuning.
METHOD
of Training Params
Cost
Est. Total Cost
Train Sct Size
$9.1
500
Unknown
$0.008/1 tokens (Train)
$ 12.7
1000
Fine-tuning
$ 20.0
2000
should 2 175B
$0.012/1K tokens (Input Usage)
$ 34.3
4000
$0.016/ K tokens (Output Usage)
$ 63.1
8000
$0.0015/1K tokens (Input Usage) $0.002/1K tokens (Output Usage)
Automate-Coo CoT
# of exemplars x Pool Size
S 6.6
100
Table 8: Comparison between Fine-tuning and Automate-CoT on GSM8K. The cost is copied from the OpenAl official website."
E Additional Analysis
We list some additional analysis here that cannot be put in the main section because of the page limit.
E.1 Effects of Several Tricks
Previous studies have found some tricks like add "Let's think step by step." " before each rationale chain and replace "Q:" with "Question:" (Fu et al., 2023; Kojima et al., 2022) can boost the performance top of Manual-CoT. Following their settings, also test Automate-CoT with tricks on GSMSK an additional experiment. By adding tricks, Automate-CoT can further boost the accuracy to 69.8% (+2.2%) under the normal setting and 83.0% (+0.6%) under the self-consistency setting, respectively.
F
Exact Match Number over Each Hop
The exact match number over each hop of Figure 1 is reported in Table 9.

---

Hop
Total Number
Manual- CoT
Automate- CoT
Complex-CoT
2
326
269 82.52%
272 = 83.44%
227 69.63%
3
370
265 71.62%
268 72.44%
232 62.70%
4
298
159 53.35%
196 65.77%
166 55.70%
5
174
83 47.70%
63.21
56.32%
6
26 29.54%
37 42.05%
39 44.32%
=0 25%
12 30%
16 40%
8
15%
20% 0
5 25% 0
Overall
1319
815 61.8%
899 68.2%
784 59.4%
Table The exact match numher across the different numbers hops on GSM8K, Bold represents the hest among each hop. The percentage accuracy is calculated for each hop.
G Full Exemplars generated by Automate-CoT

---

DATASET GSM8K
Exemplars
Hops
Q: Ralph is going to practice playing tennis with tennis ball machine that shoots tennis balls for Ralph to hit. He loads up the machine with 175 tennis halls to start with. Out the first 100 balls, he manages to hit 2/5 of them. OF the next tennis balls, he manages hit 1/3 them. Out of all the tennis halls, how many did Ralph not hit? A: Ralph started with 175 tennis balls. He 2/5 of the first 100 balls, so he hit 2/5 100 40 balls. He hit 1/3 of the next 75 balls, so he hit 1/3 75 = 25 balls. In total he hit 40 + 25 = 65 balls, Hc did not hit 175 65 = 110 balls. The answer is 110.
4-hop
Q: Hans booked room in hotel. The hotel has 10 floors with 10 identical rooms each floor. Because of accident, the last floor is unavailable for the guests. Considering there are other guests, in how many different rooms could Hans he checked in? A: There are 10 floors with 10 rooms each. The floor unavailable. So there are 10 rooms available, The answer is 90.
3-hop
Q: James carns $20 un hour while working at his main job, He carns 20% less while working his second joh. He works 30 hours at his main joh and half that much at his second joh. How much does he carn per week?
8-hop
A: James carns $20 an hour at his main job. Hc cams 20% less at his second job. That means he cams
$20 20% of $20 $20- $4 $16 hour at his second job. He works 30 hours at his main job and half that much at his second job. That means he works 30/ 2 = 15 hours at his second job. In total he works 30 + 15 = 45 hours. He earns $20 an hour at his main job and $16 an hour at his second job. In total he $600 $240 $840. The answer 840.
carns $20 30 $16
Q: Leah earned $28 working odd jobs around the neighborhhod. She spent a seventh it on a milkshake and put half the rest her savings account. She left the remaining money in her wallet. Her dog got ahold her wallet and shredded all the money inside but $1. How many dollars did Leah lose?
6-hop
A: Leah earned $28. She spent seventh it on a milkshake, so she spent $28 7 $4 on the milkshake. She put half of the rest in her savings account, so she put $28 $4 / 2 $12 in her savings account. She left the remaining money her wallet. She lost all the money her wallet except $1. So she lost $28 54 $12 $1 =$11, The answer is 11.
Q: Sam and Jeff' had a skipping competition at recess. The competition was split into four rounds. Sam completed more skip than Jeff in the first round. Jeff skipped fewer times than Sam in the second round. Jeff skipped 4 more times than Sam in the third round. Jeff got tired and only completed half the number of skips as Sam in the last round, If Sam skipped 16 times in each round, what is the average number of skips per round completed by Joff?
6-hop
A: Sam skipped 16 times in cach round. In the first round, Jeff skipped 16- 1 = 15 times. In the second round. Jeff skipped 16 3 13 times. In the third round, Jeff skipped 16 4 = 20 times. In the last round, Jeff skipped 16/ = 8 times. The average number of skips per round completed by Jeff is (15 + 13 + 20 + 8) / = 56/ 4 = 14. The answer is 14.
Q: A Statistics student wants to find out the average daily allowance of the middle school students. According to his survey, 2/3 of the students receive an average of $6 allowance per day while the rest gets an average of $4 day. If he surveyed 60 students, what is the total amount of money those 60 students get in day?
6-hop
A: 2/3 of the students receive $6 day. The rest receive $4 day. The total number of students 60. So,
2/3 of 60 students receive $6 day. The rest of the students, which is 60 2/3 60 = 20 students, receive
54 day. The total amount of money those 60 students get in day is 2/3 60 * $6 20 * $4 $240 +
$80 $320. The answer 320.
Q: Ali had a collection of seashells. He started with 180 seashells. He then gave away seashells his friends. He also gave seashells to his brothers. If he sold half the remaining seashells, how many seashells did he have left?
5-hop
his friends and to his brothers. That means he gave away 40 + 30 = 70 scashells. He has 180 70 = 110 scashells left. He sold half of them, so he has 110 2 55 seashells left. The answer is 55.
A: started with 180 seashells. He gave away
Q: Marvin and Tina were selling candy bars to help fund their class trip. The candy bars cost $2 each. 5-hop Marvin sold 35 candy bars total. Tina sold three times the number of candy bars as Marvin. How much more money did Tina make for the class trip selling candy bars compared to Marvin?
A: Marvin sold candy bars. Tina sold 3 times as many, so she sold 35 = 105 candy bars. Each candy bar cost $2 so Marvin made 35 $2 = $70. Tina made 105 $2 $210. The difference is $210 $70 = $140. The answer is 140.
Table 10: One example of selected model generatee exemplars with rationale chains of average hops = 5.4. This set of exemplars is trained and selected GSM8K and transferred to other arithmetic reasoning tasks.

---

DATASET
Exemplars
AQuA
Q: If Tim had lunch at S50 and he gave 20% tip, how much did he spend? Answer Choices: (a) $60.00 (b) $35.42 (c) $60.60 (d) $21.56 (e) $78.45 A: The tip is 20% of what he paid for lunch. tip 20% of 50.00 = (20/100) = $10.00. Total spent
50.00 10.00 560.00. The answer is (a).
Q: A person walk constant rate of Smph and bike rate of 16mph. he travel 64 miles in 8 hours using bike and walking their constant rates, how much distance would he require walk? Answer Choices: (a) 20 (b) 30 (c) (d) 64 72
A: Total distance 64. Distance Speed * Timme Walking speed = = 8. Walking time tl. Bike speed
$2 = 16. Time traveled in bike 12. d2 64. slil + s20 64, 8 16 = 64. 11 + 2 = 8 (1).
Given: tl = (2). (1) (2) 12 0 and 8 () 8. Walking distance s1 8 = 64. The
answer is (d).
Q: The output of factory increased 10% keep up with rising demand. To handle the holiday rush, this new output inereased by 20%. By approximately what pereent would the output now have to he decreased in order restore the original output? Answer Choices: (a) 20% (b) 24% (c) 30% (d) 32% (e) 79% A: Let initial output is then after 10% increase it will 1.10 and after 20% increase this output the latest output will be 1.10 1.20 = 1.320. Now we have to decrease the output by some percentage so that the new output is same as the starting output (O), so, 1.320 (1-x/100)== = The answer is (b).
24.22422222 24.24% So, answer will be B.
In graduate physics course. 70 percent of the students are male and 30 percent of the students married. If two-sevenths of the male students are married, what fraction of the male students is single? Answer Choices: (a) 2/7 (b) 1/3 (e) 1/2 (d) 2/3 (e) 5/7
A: let assume there single. now its given that two-sevenths the male students are married that means of 20 males are married. if 30 is the total number of students who are married and out of that 20 are males then the remaining 10 will be females who married. total females 70. married males 20. then single males 70-20 50. need to find the fraction male students who are single i.e single male students total male student 50/70 5/7 [E]. The answer is (e).
100 students of which 70 male and 30 are females. if 30 married then 70 will be
Table 11:
One example of selected between the answer choices which are omitted in the table to save space.
exemplars with rationale chains. Note that there are newlines

---

DATASET CSQA
Exemplars
Q: John was punching and punching at the wall but succeeded only in bloodying his knuckles. This was bad. He would he unable to hold his tools he injured what? Answer Choices: (a) hostility (b) anger (c) nose (d) fists (e) hands
A: The answer should be something that John would be unable to hold his tools he injured it. Of the above choices, only hands make sense. So the answer is (c).
Q: What is required to be good playing tennis? Answer Choices: (a) tennis racket (h) skill (c) competition (d) tennis court (e) legs
A: The answer must be something that is required be good playing tennis. Of the above choices, only skill answer is (b).
required to good at playing tennis,
Q: What someone who gets angry after getting drunk likely to participate in? Answer Choices: (a) violence (b) falling down (c) vomiting (d) vomiting (e) lower standards
A: The answer should be something that someone who gets angry after getting drunk is likely to do. Of the above choices, the closest answer is violence. So the answer is (a).
Q: James felt himself losing consciousness. He was frightened. He didn't want this, He scared of what? Answer Choices: (a) death (b) coma (c) peace (d) forgetfulness (e) loss of life A: The answer should be something that James would be scared of. Of the above choices, the closest thing is death, So the answer (a).
Q: Sally lost her kite because she wasn't It careful. She thought that there was more string on the spool, but it slipped out of her fingers when she reached the what?. Answer Choices: (a) child's hand (b) the last straw (c) hobby shop (d) end of line (e) toy store A: The answer should be the end of the string. Of the above choices, the end of the line makes the most sense, So the answer is (d).
Q: The sensor would just the distance then set off an alarm, the installation expert explained was called what kind of sensor? Answer Choices: (a) near (b) closeness (c) here (d) proximity (e) this A: The answer must be type of sensor that would set off an alarm when something is near. Of the above choices, only proximity sensor makes sense. So the answer (d).
Q: The student needed to get some new pencils, where go? Answer Choices: (a) store (b) classroom backpack (d) cabinet (c) teacher The answer should be the place where pencils are sold. the above choices, only store makes sense, the answer (a).
Table 12:
One example of selected model-generated exemplars with rationale chains. This set of exemplars is trained and selected on CommonsenseQA. Note that there are newlines between the answer choices which are omitted in the table to save space.

---

DATASET
Exemplars
StrategyQA
Q: Did the death of Helen Palmer have significant effect on Dr. Scuss?
A: Helen Palmer was Dr. Seuss's ' wife. The death of spouse have signiticant effect person. Thus,
the death of Helen Palmer could significant effect on Seuss. So the answer yes.
Q: Would a moose hypothetically too much a minotaur to devour whole? moose about 1,000 pounds. minotaur about 1,000 pounds. Thus, moose would he too much for minotaur to devour whole. So the answer is yes.
Q: Yes no: Is H''s most common two letter pair partner freebie in Wheel of Fortune bonus round? A: The most common two letter pair partner for H is E. E is freehic in the Wheel of Fortune bonus round. Thus, II's most common two letter pair partner freebie the Wheel Fortune bonus round, So the answer yes.
Q: Yes or no: Would bald eagle deliver an urgent message before B-52? The top speed of bald cagle is about 80 mph. The top speed of B-52 is ahout 650 mph. Thus, a B-52 would be faster than bald eagle, So the answer is
Q: Yes no: Does an individual oceanographer study many sciences?
A: Occanography is the study of the occan. The occan is complex system. Thus, occanography is multidisciplinary science, the answer yes.
Q: Yes no: Could Steven Spielberg send emails as a child? Steven Spielberg was born 1946. Email was invented in 1971. Thus, Steven Spielberg could not send emails as child, So the answer is no.
Table 13: One example of selected model-generated exemplars with rationale chains. This set of exemplars is trained and selected on StrategyQA. Note that there are newlines between the answer choices which are omitted in the table save space.
DATASET
Exemplars
Letter (4)
Q: Take the last letters of the words in "Delmer Andersen" and concatenate them.
A: The last letter of "Delmer" "F". The last letter of "Andersen" is "n" Concatenating them is "m". So the answer
Q: Take the last letters of the words in "Jason Gonzalez" and concatenate them. The last letter of "Jason" "n". The letter of "Gonzalez" is "z".. Concatenating them "nz". So the answer nz..
Take the letters the words "Ulysses Brown" and concatenate them. The letter of "Ulysses "s". The last "Brown" "n" Concatenating them "sn". answer sn.
Q: Take the letters the words "Frank Ortiz" and concatenate them. The last letter of "Frank" is "k". The last letter of "Ortiz" is z". Concatenating them "kz". " So answer is kz.
Table 14: One example of selected model-generated exemplars with rationale chains. This set of exemplars is trained on Letter (3) and selected on Letter (2).

---

DATASET
Exemplars
OpenBookQA
Q: car approaches you night (a) headlights become more intense (b) the headlights recede
into the dark (c) the headlights remain at a constant (d) headlights turn
A: The headlights become more intense as the car approaches. The answer is (a).
Q: Many animals that give birth to live young have (a) gills (b) scales (c) exoskeletons (d) legs
A: Animals that give birth to live young are mammals. Mammals have hair and give milk to their young. The answer is (a).
Q: A person is lost in dense forest, and needs to find their home. They know their home to the south, and they are headed north. They can find home by using a (a) northern-directing device (b) northern light reader (c) northeastern winds (d) north central credit
A: he person needs to find south, so they need northern porthern-directing device, The answer is (a).
Q: When the weather changes as it does from Christmas to Easter, (a) the air may chill (b) the ground may freeze (c) the plants may die (d) the ground may warm
A: The weather changes from Christmas to Easter, the ground may warm. The answer (d).
Table 15: One example of selected exemplars with rationale chains. This set of exemplars is trained and selected on OpenBookQA.

---

DATASET
Exemplars
&-SNLI
Premise:
"A woman wearing white and eating. walks holding briefcuse."
Based this premise,can we conclude the hypothesis female is man." true?
OPTIONS:
yes
no
not possible tell
woman is another word for a female, The answer yes.
Premise:
"A couple play the tide with their young son."
Based on this premise,can we conclude hypothesis "The family is sitting down for dinner." truc?
OPTIONS:
yys
nO
is not possible to tell
A: The family cannot simultancously be playing in the tide and sitting down to dinner The answer no.
Premise:
"A man, woman, and child enjoying themselves on a beach." Based on this premise,can we conclude the hypothesis "A child with mom and dad, on summer vacation at the beach." is true?
OPTIONS:
-yes
it is not possible tell
A: man and woman with child are not necessarily its mom and dad. A woman, and child beach are not necessarily on summer vacation, The answer it not possible to tell.
Premise:
"Two women, holding food carryout containers, hug."
Based on this premise,can we conclude the hypothesis "The two sisters saw each other across crowded diner and shared hug, both clutching their doggie bags." is true?
OPTIONS:
-yes
no
it is not possible to tell A: Just because two women are hugging does not mean they are sisters or they are in crowded diner, The answer is it is not possible to tell.
Premise:
"A few people in a restaurant setting, one of them is drinking orange juice." Based on this premise,can we conclude the hypothesis "The people are eating omelettes." " is true?
OPTIONS:
it is not possible tell
A: We only know that someone drinking orange juice, do not know that they are cating omelettes The answer it is not possible tell.
Premise:
"A man and woman the street front of pizza and gyro restaurant."
Based on this premise,ca conclude the hypothesis "Near couple of restaurants, people walk across the street." true?
OPTIONS:
yys
is possible tell
man and
are people. The yes.
Table 16: One example of selected exemplars with rationale chains. This set of exemplars is trained and selected on e-SNLI.

---

DATASET
Exemplars
SST-2
What the sentiment the following sentence?
"more than another best man clone by weaving theme throughout funny film"
"weaving a theme throughout this funny film" indicates positive sentiment, The answer is positive.
What the sentiment the following sentence?
"that 's far too tragic to merit such superficial treatment"
A: "far too tragic" and "to merit such superficial treatment" both mean negative sentiments, The answer negative.
What is the sentiment of the following sentence? "are more deeply thought through than in most right-thinking films" A: "more deeply thought through" indicates positive sentiment, The answer is positive.
What is the sentiment of the following sentence? "excruciatingly unfunny and pitifully unromantic" A: "excruciatingly unfunny" and "pitifully unromantic" both mean negative sentiments, negative..
The answer is
What the sentiment of the following sentence? "with his usual intelligence and subtlety" A: "with his usual intelligence and subtlery" indicates positive sentiment, The answer positive.
What the sentiment of the following sentence? "goes to absurd lengths" "
"goes absurd lengths" negative sentiment. The answer is negative.
Table 17: One example of selected exemplars with rationale chains. This set of exemplars trained and selected on SST-2.


Reviews:
[{"review_id": "1VBpKJ1yoS", "reviewer": "Reviewer_1kzZ", "summary": "", "questions": "Question A: Can you elaborate on the cost of optimizing prompts?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 1kzZ,\n\nThank you very much for your comprehensive review and valuable feedback! We address your comments one by one as follows:\n\n**[Requirement of labeled data]**\n> While the proposed approach leads to some improvements over manually crafted CoT prompts, it requires 1) hundreds of labeled data points to work well. One advantage of CoT prompting is its applicability in true few-shot settings; requiring hundreds of labeled data points could be practical in some scenarios but also limits the applicability of the proposed approach to some extent. \n\n\nThanks for your question! Our method only needs question-answer pairs instead of rational chains. In the real world, there are many scenarios and applications where labeled question-answer pairs are available without human-annotated rational chains. Considering that this method requires only a small amount of labeled data to achieve good results, especially in alleviating the sensitivities associated with the traditional Chain-of-Thought approach, it is worthwhile to apply Automate-CoT. \n\n\n\n\n**[Cost of optimizing prompts]**\n\n\n> 2) non-negligible computation overheads for optimizing the prompts. Regarding (2), it would be good if the paper can elaborate on the cost of optimizing prompts measured by money or number of tokens beyond specifying hyper-parameters.\n\n\nThanks for your suggestion! We provide the estimated cost of optimizing the prompts in terms of money with gpt-3.5-turbo. The usage of gpt-3.5-turbo is 0.0015 USD / 1K tokens for input and 0.002 USD / 1K tokens for output tokens. Under Automate-CoT with the training epochs of 3, a training set size of 100 and a validation set size of 100, an input length of around 750 tokens and an average output length of 150 tokens, it takes about (750/1000 * 0.0015 + 150/1000 * 0.002) * 100 * 10 * 3  + (750/1000 * 0.0015 + 150/1000 * 0.002) * 100 * 3 = $4.7.\n\n\nWe have updated our manuscript with these details. Thanks very much for your constructive suggestion!\n\n\n\n\n**[Contribution]**\n\n\n> The proposed approach is a straightforward incremental extension of AutoCoT (Zhang et al., 2022). In particular, the augment and prune are the same as in AutoCoT (Zhang et al., 2022) and Rationale-Augmented Ensemble (Wang et al., 2022). The only added component is a derivative-free optimizer that can leverage labeled data for selecting examples at some additional computational cost.\n\n\nOur proposed method enhances the reasoning abilities by automatically augmenting rational chains from a small training dataset, pruning low-quality chains, and selecting the optimal combination of rationale chains using a variance-reduced policy gradient strategy. \nThe augmentation and pruning methods that we are using are different from both Auto-CoT and Rationale-Augmented Ensemble.\n\n\nOur method differs from Auto-CoT in several aspects: \n[Augment] Auto-CoT mainly augments the questions by leveraging “Let’s think step by step” and further it directly uses the generated rationales as the model input that contains wrong and low-quality chains. However, Automate-CoT augments the results by using two different methods, the few-shot and zero-shot method.\n\n[Prune] Auto-CoT does not have the pruning step while we propose to prune the low-quality chains to construct a high-quality candidate pool. \n\n[Select] More importantly, we propose a new method for selecting the optimal combination of rationale chains using a variance-reduced policy gradient strategy.\n\n[Setting] For the experimental settings, Auto-CoT directly samples questions from the test dataset while we restrict our method to training data which is more realistic in applications (considering most test set is hidden before testing).\n\n\nOur method differs from Rationale-Augmented Ensemble in several aspects: \nThey have shown that randomly replacing one human-written out of K (4-6) exemplars exhibits substantial variance which means human-written rationales can be far from “optimal”. As a result, their method focuses on “ensemble” which elicits multiple rationales (and outputs) by using such replace method and ensemble the results. For each sampled path, the few-shot exemplars are still far away from “optimal”, and even worse than manually constructed ones( as mentioned in the Rational-augmented Ensemble paper Section 2.1). However, our method focuses on getting the optimal few-shot exemplars where using a selection-based method to mitigate the low-quality chains and further bypass the four sensitivities. \n\n\n**[Experiments with gpt-3.5-turbo]**\n\n\n> While it has been mentioned in the limitation, it could be helpful if the paper can experiment with more advanced models like gpt-3.5-turbo.\n\n\nWe further conduct the experiments on gpt-3.5-turbo, our Automate-CoT also shows consistent improvement on each task with 2.8% improvement on arithmetic reasoning, 3.9% improvement on commonsense reasoning, 3.2% on symbolic reasoning and 2.8% improvement overall.\n\n| | GSM8K | ASDiv | SVAMP | AQuA | SingleOP | CSQA | StrategyQA | Letter (4) | OBQA | e-SNLI | SST-2 | Avg. |\n| ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- |\n| Manual-CoT  | 63.1 | 77.1 | 78.1 | 44.9 | 90.0 | 77.5 | 59.7 | 73.0 | 80.0 | 80.9 | 85.3 | 73.6 |\n| +Automate-CoT | 68.0 (+4.9) | 81.7 (+4.6) | 79.1 (+1.0) | 46.9 (+2.0) | 91.5 (+1.5) | 80.5 (+3.0) | 64.5 (+4.8) | 76.2 (+3.2) | 83.0 (+3.0) | 81.4 (+0.5) | 87.7 (+2.4) | 76.4 (+2.8) |\n\nWe have updated our manuscript with these new results. Thanks very much for your constructive suggestion!", "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": "The paper provides a way to automate the engineering of CoT prompts and achieves noticeable improvements over manually crafted CoT prompts.\n\nThe experiments cover multiple datasets and domains and also provide thorough analysis and ablations.\n\nThe paper is well-written and easy to follow.", "reasons_to_reject": "While the proposed approach leads to some improvements over manually crafted CoT prompts, it requires 1) hundreds of labeled data points to work well 2) non-negligible computation overheads for optimizing the prompts. One advantage of CoT prompting is its applicability in true few-shot settings; requiring hundreds of labeled data points could be practical in some scenarios but also limits the applicability of the proposed approach to some extent. Regarding (2), it would be good if the paper can elaborate on the cost of optimizing prompts measured by money or number of tokens beyond specifying hyper-parameters.\n\nThe proposed approach is a straightforward incremental extension of AutoCoT (Zhang et al., 2022). In particular, the augment and prune are the same as in AutoCoT (Zhang et al., 2022) and Rationale-Augmented Ensemble (Wang et al., 2022). The only added component is a derivative-free optimizer that can leverage labeled data for selecting examples at some additional computational cost.\n\nWhile it has been mentioned in the limitation, it could be helpful if the paper can experiment with more advanced models like gpt-3.5-turbo.", "questions_to_authors": "Question A: Can you elaborate on the cost of optimizing prompts?", "paper_topic_and_main_contributions": "This paper studies the problem of automatically engineering chain-of-thoughts prompts using labeled data. The paper proposes Automate-CoT, which takes as input a set of labeled data points and, optionally, a few data points with annotated chain-of-thoughts, and automatically outputs an optimized CoT prompts. The paper tests the proposed approach on 11 datasets and compares against AutoCoT and manual CoT baseline. The results suggest the proposed Automate-CoT approach can effectively leverage labeled data points to optimize the CoT prompts.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L9AiOKtaAT", "reviewer": "Reviewer_rCCa", "summary": "", "questions": "1. Line 240&241. What are T, t_i, S for? The loss is poorly explained.\n\n2. How does the selection method aid in identifying diverse and representative samples?\n\n3. Recent studies on in-context learning have shown that dynamic demonstration example selection strategies may be superior to fixed demonstration example selection strategies [1]. Auto-CoT compares not only random strategies but also retrieval strategies. It would be beneficial to compare the mentioned selection with simple retrieval methods like BM25 or Learn to Retrieve [1], Vote-K [2], RL [3].\n\n5. Auto-CoT selects demonstration examples through clustering. Have this paper considered comparing the selection method to clustering?\n\n6. In Figure 4, it is evident that performance improves with an increase in pool size. However, it is important to determine the specific pool size at which performance convergence occurs or starts to drop. The cost of running 200 queries on GPT-3 is acceptable.\n\n7. The experiment datasets chosen in the additional experiment section of the paper are not consistent. Specifically, in Table 2, the paper opts for GSM8K, SVAMP, and Letter, in Table 3, it selects GSM8K, CSQA, and Letter, and in Table 4, it again chooses GSM8K, SVAMP, and Letter.\n\n8. In table 3, Auto-CoT should be a more relevant baseline since Auto-CoT is a zero-shot baseline without using ground-truth labels.\n\nI will update the final score according to the authors responses.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer rCCa,\n\nThank you very much for your comprehensive review and valuable feedback! We address your comments one by one as follows:\n\n\n**[Comparison with retrieval-based method]**\n\n> The paper missed some strong prompt selection baselines for few-shot learning. Recent studies on in-context learning have shown that dynamic demonstration example selection strategies may be superior to fixed demonstration example selection strategies [1]. Auto-CoT compares not only random strategies but also retrieval strategies. It would be beneficial to compare the mentioned selection with simple retrieval methods like BM25 or Learn to Retrieve [1], Vote-K [2], RL [3].\n\nThanks for your suggestion! We recognize adding the comparison with the retrieval-based selection method would enhance the persuasiveness of our research. Following your advice, we implemented a BM25-based selection method and tested the performance of all the datasets. The results are shown below. It indicates that retrieval-based methods can only select examples with similar meaning to the query question while diversity is overlooked. As shown in the table, the average performance of the BM25 retrieval-based method even has a one percent degradation compared to Manual-CoT, and 3.8% lower than Automate-CoT. A similar phenomenon is observed in Auto-CoT, which indicates that with similar questions being sampled for test questions, Retrieval-Q-CoT is negatively affected by misleading by similarity.\n\n| | GSM8K | ASDiv | SVAMP | AQuA | SingleOP | CSQA | StrategyQA | Letter (4) | OBQA | e-SNLI | SST-2 | Avg. |\n| ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- |\n| Manual-CoT  | 63.1 | 77.1 | 78.1 | 44.9 | 90.0 | 77.5 | 59.7 | 73.0 | 80.0 | 80.9 | 85.3 | 73.6 |\n| BM25  | 64.2| 73.7 | 73.8 | 45.3 | 87.9 | 76.1 | 58.9 | 73.4 | 81.4 | 76.3 | 87.2 | 72.6 |\n| Automate-CoT | 68.0 | 81.7 | 79.1 | 46.9 | 91.5 | 80.5 | 64.5 | 76.2 | 83.0 | 81.4 | 87.7 | 76.4 |\n\nWe have updated our manuscript with these new results, to reveal the effects of retrieval-based methods. Thanks very much for your constructive suggestion!\n\n\n**[Notations in section 3.2]**\n\n> Line 240&241. What are T, t_i, S for? The loss is poorly explained.\n\nIn Lines 240&241, T are the full few-shot exemplars. t_i denotes the $i$-th exemplar. S is the current question (user’s query). We first sample each exemplar t_i according to P(t_i). After obtaining T, we concatenate T with the query input S and feed [T, S] into the large language model G to get a prediction. Then we compare the prediction with $y$ and calculate the loss. Thank you for pointing it out! We have updated our manuscript with these details.\n\n**[Experiments with gpt-3.5-turbo]**\n\n\n> As mentioned in the Limitations section, the paper does not include experiments with recent closed-source LLMs, such as ChatGPT. It is worth noting that ChatGPT may be both cheaper and stronger than text-davinci-002.\n\n\nWe further conducted the experiments on gpt-3.5-turbo. Our Automate-CoT also shows consistent improvement on each task with 2.8% improvement on arithmetic reasoning, 3,9% improvement on commonsense reasoning, 3.2% on symbolic reasoning, and 2.8% improvement overall.\n\n| | GSM8K | ASDiv | SVAMP | AQuA | SingleOP | CSQA | StrategyQA | Letter (4) | OBQA | e-SNLI | SST-2 | Avg. |\n| ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- |\n| Manual-CoT  | 63.1 | 77.1 | 78.1 | 44.9 | 90.0 | 77.5 | 59.7 | 73.0 | 80.0 | 80.9 | 85.3 | 73.6 |\n| Automate-CoT | 68.0 (+4.9) | 81.7 (+4.6) | 79.1 (+1.0) | 46.9 (+2.0) | 91.5 (+1.5) | 80.5 (+3.0) | 64.5 (+4.8) | 76.2 (+3.2) | 83.0 (+3.0) | 81.4 (+0.5) | 87.7 (+2.4) | 76.4 (+2.8) |\n\nWe have updated our manuscript with these new results. Thanks very much for your constructive suggestion!\n\n\n**[Four motivation factors]**\n\n> The relationship between the proposed method and the four motivation factors is still unclear. How does the selection method aid in identifying diverse and representative samples?\n\nIn Section 2, we first investigate the existence of the sensitivities in chain-of-thought methods. Then we further explore other factors that would not only affect the performance but require human efforts to deal with. In light of this empirical evidence, we are motivated to design a framework not only to augment the rationale chains but also to select the helpful rationale chains adaptively. \nIn Section 7, we analyze the effects of these four factors with our proposed method. We found that Automate-CoT can bypass the order and style sensitivity issues and reach a better complexity-diversity trade-off without human effort, finally boosting performance.\n\nEspecially, in Section 2, we found that diverse and representative samples are helpful in math reasoning tasks. During our model’s selection process, the exemplars are optimized and it will automatically learn to select the most helpful exemplars. \n\nThank you for your question and hope this explanation addresses your comments!\n\n\n\n**[Comparison with clustering method]**\n\n> Auto-CoT selects demonstration examples through clustering. Have this paper considered comparing the selection method to clustering?\nThanks for your suggestion! We recognize adding the comparison with the clustering-based selection method would enhance the persuasiveness of our research. Following your advice, we implemented a K-means-based selection method and tested the performance of all the datasets. We first use OpenAI’s `text-embedding-ada-002` embedding API to compute a vector representation for each question in the pool and then we use K-means to produce k clusters of questions. Finally, we select one representative question for each cluster by choosing the question with minimal distance to the cluster center.\n\nThe results are shown below. It indicates that clustering-based methods can select examples with different semantic meanings and generally perform better than Manual-CoT. However, the complexity and diversity are overlooked. For example, most of the selected few-shot exemplars in GSM8K have around 3-4 hops where complex questions and moderately difficult questions are overlooked. As a result, it generally performs worse than Automate-CoT with a 2.6% gap. We have updated our manuscript with these new results, to reveal the effects of clustering-based methods. Thanks very much for your constructive suggestion!\n\n| | GSM8K | ASDiv | SVAMP | AQuA | SingleOP | CSQA | StrategyQA | Letter (4) | OBQA | e-SNLI | SST-2 | Avg. |\n| ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- |\n| Manual-CoT  | 63.1 | 77.1 | 78.1 | 44.9 | 90.0 | 77.5 | 59.7 | 73.0 | 80.0 | 80.9 | 85.3 | 73.6 |\n| K-Means | 66.4 | 76.6 | 77.6 | 45.7 | 89.7 | 79.0 | 60.0 | 73.6 | 80.4 | 78.4 | 84.1 | 73.8 |\n| Automate-CoT | 68.0 (+4.9) | 81.7 (+4.6) | 79.1 (+1.0) | 46.9 (+2.0) | 91.5 (+1.5) | 80.5 (+3.0) | 64.5 (+4.8) | 76.2 (+3.2) | 83.0 (+3.0) | 81.4 (+0.5) | 87.7 (+2.4) | 76.4 (+2.8) |\n\n\n\n\n**[Additional experiments on pool size]**\n\n> In Figure 4, it is evident that performance improves with an increase in pool size. However, it is important to determine the specific pool size at which performance convergence occurs or starts to drop. The cost of running 200 queries on GPT-3 is acceptable.\n\nPreviously, our experiments on pool size were conducted under code-davinci-002 to save cost. However, OpenAI has decided to shut off access to code-davinci-002 in March 2023. Therefore, we further re-conducted the same setting on gpt-3.5-turbo and added an experiment with a pool size of 200 into comparison.\n| Datasets\\ Pool Size  | 10 | 20 | 50 | 100 | 150 | 200|\n| ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | \n| GSM8K | 63.0 | 65.4 | 66.7 | 68.0 | 68.4 | 68.3 |\n| SVAMP | 76.0 | 76.9 | 78.0 | 79.1 | 79.5 | 79.6 | \n| Letter(4) | 69.6 | 71.2 | 73.8 | 76.2 | 76.8 | 76.4 | \nAccording to the result, it shows that when the pool size approaches 200, the performance on three datasets shows minimal increase or even a little bit drop. This shows that a pool size of 100-150 is enough for the model to find a good combination for the task.\nWe have updated our manuscript with these new results. Thanks very much for your constructive suggestion!\n\n\n**[Change of datasets in the additional experiments]**\n\n> The experiment datasets chosen in the additional experiment section of the paper are not consistent. Specifically, in Table 2, the paper opts for GSM8K, SVAMP, and Letter, in Table 3, it selects GSM8K, CSQA, and Letter, and in Table 4, it again chooses GSM8K, SVAMP, and Letter.\n\nThank you for your reminder of the inconsistent datasets chosen in the additional experiment. We now change the dataset in the additional zero-shot experiment (Table 3) to GSM8K, SVAMP and Letter(4) to be consistent with Table 2 and Table 4. \nThe results are in the table below:\n\n| | GSM8K | SVAMP | Letter(4) |Avg.|\n| ----------- | ----------- | ----------- | ----------- |  ----------- | \n| Zero-Shot-CoT| 40.7 | 62.1 | 57.6 | 53.5 |\n| Manual-CoT | 46.9 | 73.5 | 56.6 | 59 |\n| Auto-CoT | 48.9 | 69.5 | 59.7 | 59.4 |\n| Zero-Shot-Automate-CoT | 49.1 | 72.4 | 59.3 | 60.3 |\n\n\n**[Additional baseline comparison in Table 3]**\n\n> In table 3, Auto-CoT should be a more relevant baseline since Auto-CoT is a zero-shot baseline without using ground-truth labels.\n\nAfter changing the dataset following the previous question, we also added Auto-CoT into this comparison.\n| | GSM8K | SVAMP | Letter(4) | Avg.|\n| ----------- | ----------- | ----------- | ----------- | ----------- |\n| Zero-Shot-CoT| 40.7 | 62.1 | 57.6 |53.5|\n| Manual-CoT | 46.9 | 73.5 | 56.6 |59|\n| Auto-CoT| 48.9 | 69.5 | 59.7 | 59.4 |\n| Zero-Shot-Automate-CoT| 49.1 | 72.4 | 59.3 | 60.3 |\n\nThe results show that Zero-shot-Automate-CoT has an advantage of 0.9% on average than Auto-CoT. In addition to text-davinci-002, since Auto-CoT only reports results of gsm8k under code-davinci-002, we also report zero-shot Automate-CoT of gsm8k under code-davinci-002 for comparison.\n\n| | GSM8K | \n| ----------- | ----------- | \n| | code-davinci-002 |\n| Auto-CoT | 62.8 |\n| Zero-Shot-Automate-CoT | 65.8 |\n\nWe have updated our manuscript with these new results. Thanks very much for your constructive suggestion!", "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": "1. The research topic regarding example selection for CoT is important, and the motivation behind this paper is clear. \n\n2. The idea is new and practical for CoT research.\n\n3. Extensive experimental results and ablation studies demonstrate the effectiveness of the proposed method.", "reasons_to_reject": "1. The paper missed some strong prompt selection baselines for few-shot learning.\n\n2. The notations in section 3.2 of the paper are poorly defined and explained, making it difficult to read.\n\n3. As mentioned in the Limitations section, the paper does not include experiments with recent closed-source LLMs, such as ChatGPT. It is worth noting that ChatGPT may be both cheaper and stronger than text-davinci-002. \n\n4. The relationship between the proposed method and the four motivation factors is still unclear.", "questions_to_authors": "1. Line 240&241. What are T, t_i, S for? The loss is poorly explained.\n\n2. How does the selection method aid in identifying diverse and representative samples?\n\n3. Recent studies on in-context learning have shown that dynamic demonstration example selection strategies may be superior to fixed demonstration example selection strategies [1]. Auto-CoT compares not only random strategies but also retrieval strategies. It would be beneficial to compare the mentioned selection with simple retrieval methods like BM25 or Learn to Retrieve [1], Vote-K [2], RL [3].\n\n5. Auto-CoT selects demonstration examples through clustering. Have this paper considered comparing the selection method to clustering?\n\n6. In Figure 4, it is evident that performance improves with an increase in pool size. However, it is important to determine the specific pool size at which performance convergence occurs or starts to drop. The cost of running 200 queries on GPT-3 is acceptable.\n\n7. The experiment datasets chosen in the additional experiment section of the paper are not consistent. Specifically, in Table 2, the paper opts for GSM8K, SVAMP, and Letter, in Table 3, it selects GSM8K, CSQA, and Letter, and in Table 4, it again chooses GSM8K, SVAMP, and Letter.\n\n8. In table 3, Auto-CoT should be a more relevant baseline since Auto-CoT is a zero-shot baseline without using ground-truth labels.\n\nI will update the final score according to the authors responses.", "paper_topic_and_main_contributions": "The paper introduces a new strategy called Automate-CoT to enhance the reasoning abilities of large language models (LLMs). Automate-CoT addresses this manual limitation by automatically augmenting rational chains from a small training dataset, pruning low-quality chains, and selecting the optimal combination of rationale chains using a variance-reduced policy gradient strategy. The approach is evaluated on various reasoning tasks and non-reasoning tasks, demonstrating competitive performance improvements.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "NA"}, "extra_text": {"Missing_References": "[1] Learning To Retrieve Prompts for In-Context Learning. EMNLP 2023.\n\n[2] Selective annotation makes language models better few-shot learners. ICLR 2023.\n\n[3] Dynamic Prompt Learning via Policy Gradient for Semi-structured Mathematical Reasoning. ICLR 2023."}}, {"review_id": "eKSo56SCPm", "reviewer": "Reviewer_5T7Y", "summary": "", "questions": "Manual-CoT, Zero-Shot-CoT and Auto-CoT all find them performing inferiorly in CommonsenseQA compared with direct reasoning. In contrast, this work achieves remarkable performance gains in that dataset. Is there any evidence to justify the advantage in this aspect?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 5T7Y,\n\nThank you very much for your comprehensive review and valuable feedback! We address your comments one by one as follows:\n\n**[Add supportive references]**\n> Some claims may be inspired from existing studies; thus, it is critical to add the supportive references. Most of the above factors have been discussed in existing studies.\n\nThanks for your suggestions! Most of the factors have been discussed in existing studies and we have updated this paragraph to: \n\"we identify four critical factors that affect the performance of chain-of-thought prompting and require large human effort to deal with: (1) order sensitivity [1]: the order combination of the exemplars; (2) complexity [2-4]: the number of reasoning steps of the rationale chains; (3) diversity: the combination of different complex-level exemplars; (4) style sensitivity [1,5]: the writing/linguistic style of the rationale chains.\"\nIf we are missing any literature, please let us know. We are happy to discuss and cite them. Thank you!\n\n[1] Zhao, Z., Wallace, E., Feng, S., Klein, D., & Singh, S. (2021, July). Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning (pp. 12697-12706). PMLR.\n\n[2] Fu, Y., Peng, H., Sabharwal, A., Clark, P., & Khot, T. (2022). Complexity-based prompting for multi-step reasoning. arXiv preprint arXiv:2210.00720.\n\n[3] Sugawara, S., Inui, K., Sekine, S., & Aizawa, A. (2018). What makes reading comprehension questions easier?. arXiv preprint arXiv:1808.09384.\n\n[4] Lai, Y., Zhang, C., Feng, Y., Huang, Q., & Zhao, D. (2021). Why machine reading comprehension models learn shortcuts?. arXiv preprint arXiv:2106.01024.?\n\n[5] Papadopoulos, P. M., Demetriadis, S. N., Stamelos, I. G., & Tsoukalas, I. A. (2010). The effect of prompting to students with different learning styles. Multicultural Education & Technology Journal, 4(3), 198-213.\n\n\n\n**[Cost]**\n\n> This approach requires extensive queries to optimize and organize the demonstration exemplars, which would costly behind the paywalls. It also relies on a training-based pipeline, which further increases the complexity of the whole framework.\n\n\nThanks for your suggestion! We provide the estimated cost of optimizing the prompts in terms of money with gpt-3.5-turbo. The usage of gpt-3.5-turbo is 0.0015 USD / 1K tokens for input and 0.002 USD / 1K tokens for output tokens. Under Automate-CoT with the training epochs of 3, a training set size of 100 and a validation set size of 100, an input length of around 750 tokens and an average output length of 150 tokens, it takes about (750/1000 * 0.0015 + 150/1000 * 0.002) * 100 * 10 * 3  + (750/1000 * 0.0015 + 150/1000 * 0.002) * 100 * 3 = 4.7 USD.\n\n\nWe have updated our manuscript with these details. Thanks very much for your constructive suggestion!\n\n\n**[Performance on CommonsenseQA]**\n\n> Manual-CoT, Zero-Shot-CoT and Auto-CoT all find them performing inferiorly in CommonsenseQA compared with direct reasoning. In contrast, this work achieves remarkable performance gains in that dataset. Is there any evidence to justify the advantage in this aspect?\n\nThere are two potential reasons: \nOn the CSQA dataset, the quality of the original manual constructed CoT is mediocre. As shown in our Figure 3, we found that even  the Random Selection method can performs better on CSQA than Manual-CoT many times.\nAnd because our proposed selection can help to choose appropriate few-shot examples, addressing the issues of order and diversity, the performance has been significantly improved.\n\nWe have updated our manuscript with these new analyses and discussions. Thanks very much for your kind and constructive suggestions!", "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": "1. This paper is generally written in a clear and concise style. This work is well motivated, and provides a useful alternative of automatic CoT prompting approach. The relationship with existing studies is also clearly presented.\n\n2. The experimental results are impressive. The proposed approach achieves satisfying performance gains over the baselines under a relatively fair comparison. Analysis shows that the approach works robustly.", "reasons_to_reject": "1. Some claims may be inspired from existing studies; thus, it is critical to add the supportive references. For example, Lines 55-64: \"we identify four critical factors that affect the performance of chain-of-thought prompting and require large human effort to deal with: (1) order sensitivity: the order combination of the exemplars; (2) complexity: the number of reasoning steps of the rationale chains; (3) diversity: the combination of different complex-level exemplars; (4) style sensitivity: the writing/linguistic style of the rationale chains.\" --- Most of the above factors have been discussed in existing studies.\n\n2. This approach requires extensive queries to optimize and organize the demonstration exemplars, which would costly behind the paywalls. It also relies on a training-based pipeline, which further increases the complexity of the whole framework.", "questions_to_authors": "Manual-CoT, Zero-Shot-CoT and Auto-CoT all find them performing inferiorly in CommonsenseQA compared with direct reasoning. In contrast, this work achieves remarkable performance gains in that dataset. Is there any evidence to justify the advantage in this aspect?", "paper_topic_and_main_contributions": "This work aims to address the restriction of handcrafting effective input-output demonstrations in most chain-of-thought (CoT) studies, where the effectiveness of demonstrations may be influenced by four aspects: order sensitivity, complexity, diversity, and style sensitivity. To this end, this paper presents an Automate-CoT strategy to bypass human engineering of CoT by automatically augmenting rational chains from a small labeled dataset, and then pruning low-quality chains to construct a candidate pool of machine-generated rationale chains based on the labels. The proposed approach works by three steps, augment, prune, and select. It first generates rationale chains according to the standard CoT process with several exemplars, and then prunes the incorrect ones according to the consistency of the predicted answer and ground-truth answer. Finally, a variance-reduced policy gradient strategy is applied to estimate the gradients and optimize the latent variables to select better CoTs. \n\nOverall, this work may advance the development of automatic and task-adaptive prompting CoT methods that can be generally effective across large language models. Though sharing a similar motivation, this work makes solid contributions over the existing Auto-CoT approach, with improvement gains over a range of tasks. This work also provides insightful analysis that justifies the contribution factors and the (in)sensitivity of the proposed approach.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presented a work with a few nice contributions as mentioned by the reviewers and summarized by the authors during discussions, which I would prefer not to repeat. I do have a few additional concerns to mention. 

1. The authors added a large amount of new results, unfortunately, I did not see all those corresponding results for other related methods, such as turbo results of AutoCoT. Such results are very important given the similarity of these works. In addition, the following trend usually holds: the stronger the LLMs' capability, the less the necessity of labeled data.

2. As LLMs are dominating the field, it is mostly acceptable to challenge a traditional method without being compared with an LLMs-based method. But here I would like to mention the opposite way. Given that hundreds of labeled data are needed, I would be curious what result a supervised method will achieve by using these few hundreds of labeled data for training. 

In addition, I have some optional advice. The authors might want to change the name Automate-CoT to something else because it is misleading with Auto-CoT. Given that your method needs hundreds of training data, maybe weakly-supervised-CoT is more appropriate.
Decision: Accept-Findings