Reprompting: Automated Chain-of-Thought Prompt Inference Through Gibbs Sampling

We thank the reviewer for the valuable comments and insightful questions. Here are some responses to the weaknesses and questions:

• The assumptions in Eq(1)(2) are based on the empirical findings in [1,2] on a wide range of tasks. Specifically, [1] shows that the test performance does not vary much when increasing the number of supervised examples in the prompt from 8 to 32 or more. Chain-of-Thought (CoT) prompting further reduces the number of demonstrations needed -- the test performance remains similar when there is a varying number (but typically >= 3) of few-shot exemplars. These findings can be expressed formerly in mathematical forms as in Eq(1)(2), and have served as the base of LLM evaluation through few-shot prompting in prior work [3,4] . We have updated Section 2.1 to better explain it.
• The message “Let’s think step by step…” is applied to all the baselines, except for the few-shot baseline where the demonstrations only include the concatenated question answer pairs without intermediate steps, thus we didn’t include the “step-by-step” instruction in the message.
• We have added more experiments on 10 additional tasks and popular benchmarks, including 7 tasks from BigBench Hard (BBH), GSM8K (math word problems) and two from Hendrycks’ MATH (see Table 3 in Appendix). (Many tasks evaluated in self-consistency paper predate GPT3.5 and thus may have data contamination issue. The BBH data contains more recent and more challenging benchmark tasks, e.g. Date Understanding is considered more challenging than StrategyQA [3].) Results show that Reprompting still outperforms zero-shot and few-shot prompting consistently and substantially by 14-17 points on average. Compared with human-written CoT, Reprompting achieves better performance on all these tasks except on Date Understanding, Reasoning About Colored Objects, and MATH Algebra, on which the score differences are very small (<4 point). On average, Reprompting still outperforms CoT by +12.4 point on these tasks.
• We have downplayed the claim for the contribution "Reprompting can transfer knowledge from a stronger model to a weaker model" in the updated paper, as we observed it only on GPT3.5 to text-davinci-003. However, the finding is still interesting and serves as a starting point for further study in future works.
• We further conducted an ablation study on the rejection sampling and recombination process. Results in Table 5 (in Appendix) show that, without rejection sampling, the test performance degrades greatly. Always rejecting solutions that lead to wrong answers also leads to degradation. Additionally, not allowing multiple solutions to be recombined when sampling new solutions at the iterative sampling stage also hurts performance.
• We have conducted additional experiments to compare Reprompting with ComplexCoT (Table 4 in Appendix). On the three commonsense and arithmetic reasoning tasks, our method outperforms the baseline by +5.3 points on average. Note that Complex-CoT relies on a pool of human-written CoT recipes to select from while Reprompting does not. We are still running ComplexCoT+SelfConsistency (which is 8.5x more costly than Reprompting on GSM8K), but we don’t expect it to outperform Reprompting since SelfConsistency improves over CoT by <= 4 point in our previous experiment.
• Rejection sampling is used to simulate the sampling from Eq(5), but is not equivalent to it.
• We showed an example of incorrect solutions evolving into a correct one through iterations in Figure 3. The percentage of incorrect solutions kept in the initialization stage is in Figure 2 (at 0-th iteration), which is around 50-70%.
• The performance does not vary much given different choices of the prompt examples after running Reprompting, which is probably because the solutions learned through Reprompting follow the same reasoning paths.
• Yes, applying Reprompting to optimize the prompt for verification would indeed be a great future direction.

[1] Language Models are Few-Shot Learners. Brown et al., NeurIPS 2020.

[2] Chain-of-thought prompting elicits reasoning in large language models. Wei et al., NeurIPS 2022.

[3] Challenging BIG-Bench tasks and whether chain-of-thought can solve them. Suzgun et al., 2022.

[4] An Empirical Study on Challenging Math Problem Solving with GPT-4. Wu et al., 2023.

We thank the reviewer for the valuable comments and insightful questions.

Due to improved compute access recently, we were able to run more experiments on 10 additional tasks, including 7 tasks from BigBench Hard (BBH), GSM8K (math word problems) and two from Hendrycks’ MATH (see Table 3 in Appendix). On BBH, we intentionally selected the subtasks on which CoT does not improve much or does not improve consistently, such as Formal Fallacies, Movie Recommendation, Ruin Names, Salient Translation Error Detection, and Word Sorting. Results show that Reprompting still outperforms zero-shot and few-shot prompting consistently and substantially by 14-17 points on average. Compared with human-written CoT, Reprompting achieves better performance on all these tasks except on Date Understanding, Reasoning About Colored Objects, and MATH Algebra, on which the score differences are very small (<4 point). On average, Reprompting still outperforms CoT by +12.4 point on these tasks.

And interestingly, on tasks where CoT even underperforms zero-shot prompting, such as Movie Recommendation, Salient Translation Error Detection, and Word Sorting, Reprompting still improves over zero-shot prompting substantially. This suggests that not all CoT recipes improve model performance, and some may even lead to degradation. Reprompting serves as an effective algorithm for discovering and optimizing the CoT prompt to best exploit and compare LLMs.

We thank the reviewer for the valuable comments and insightful questions. Here are some responses to the weaknesses and questions:

• Compared with prompt tuning and fine-tuning approaches, the number of labeled samples required by our approach is much less. Prompt tuning and parameter-efficient fine-tuning approaches require 100 to several thousand labeled samples for training and validation [1,2,3,4,5], which is not suitable for the few-shot setting that we focus on in this paper (e.g. on BigBenchHard, some tasks only contain a few dozen labeled samples apart from the 250 test samples). By contrast, our approach only requires 20 labeled samples, and thus can be tested on these few-shot benchmarks. However, we did add an additional baseline that optimizes the CoT prompt based on human-written solutions (so it’s human effort + optimization) [7]. The results are presented in Table 4 in the updated Appendix. On the three commonsense and arithmetic reasoning tasks, our method outperforms the baseline by +5 points on average.
• The fact that optimized prompts can beat human-written ones on reasoning tasks is not unsurprising. For instance, a recently proposed approach on optimizing/adapting CoT prompts does not outperform human-written CoT on average [6]. However, our method does outperform human-written CoT by large margins on a wide range of reasoning tasks (see Table 1 and the additional results on other tasks in Table 3 in Appendix).
• We further conducted an ablation study on the rejection sampling and recombination process. Results in Table 5 (in Appendix) show that, without rejection sampling, the test performance degrades greatly. Always rejecting solutions that lead to incorrect answers also leads to degradation. Additionally, not allowing multiple solutions to be recombined when sampling new solutions at the iterative sampling stage also hurts performance. Furthermore, since the Auto-CoT baseline in our experiment differs from our method in that it only has the initial sampling step without the iterative sampling step, it also serves as an ablative baseline. The comparison results show that the iterative sampling step brings +11 point improvement on average on the five BBH tasks.

[1] Parameter-efficient transfer learning for NLP. Houlsby et al., ICML 2019.

[2] The power of scale for parameter-efficient prompt tuning. Lester et al., 2021.

[3] P-tuning: Prompt tuning can be comparable to fine tuning across scales and tasks. Liu et al., ACL 2022.

[4] Lora: Low-rank adaptation of large language models. Hu et al., 2021.

[5] Improving Prompt Tuning with Learned Prompting Layers. Zhu et al., 2023.

[6] Better Zero-Shot Reasoning with Self-Adaptive Prompting, Wan et.al., ACL23.

[7] Complexity-Based Prompting for Multi-Step Reasoning. Fu et al., 2022.

We thank the reviewer for the valuable comments and insightful questions. Here are some responses to the weaknesses and questions:

• Compared with prompt tuning and fine-tuning approaches, the number of labeled samples required by our approach is much less. Prompt tuning and parameter-efficient fine-tuning approaches require 100 to several thousand labeled samples for training and validation [1,2,3,4,5], which is not suitable for the few-shot setting that we focus on in this paper (e.g. on BigBenchHard, some tasks only contain a few dozen labeled samples apart from the 250 test samples). By contrast, our approach only requires 20 labeled samples, and thus can be tested on these few-shot benchmarks. However, we did add an additional baseline that optimizes the CoT prompt based on human-written solutions (so it’s human effort + optimization) [6]. The results are presented in Table 4 in the updated Appendix. On the three commonsense and arithmetic reasoning tasks, our method outperforms the baseline by +5 points on average.
• Sampling ablation: Since the model likelihood is only available for text-davinci-003 (which is 10x more expensive than GPT3.5) but not GPT3.5, and sampling a set of candidates for reweighted sampling at each iteration is time-consuming, it takes much more time to run. But we are still trying to run it and incorporate the results in the updated version.
• Reprompting+Rewriting: This would indeed be an interesting way to further improve the performance of Reprompting, although it remains an open question how to instruct a model so that they can use recipes in a prompt differently (i.e. it should try to recombine the reasoning paths provided by recipes on other questions while improving (but not copying) the previous recipe on the same question).
• We have added more experiments on 10 additional tasks and popular benchmarks, including 7 tasks from BigBench Hard (BBH), GSM8K (math word problems) and two from Hendrycks’ MATH (see Table 3 in Appendix). Results show that Reprompting still outperforms zero-shot and few-shot prompting consistently and substantially by 14-17 points on average. Compared with human-written CoT, Reprompting achieves better performance on all these tasks except on Date Understanding, Reasoning About Colored Objects, and MATH Algebra, on which the score differences are very small (<4 point). On average, Reprompting still outperforms CoT by +12.4 point on these tasks.
• Exposition: The motivation for finding effective CoT recipes using Gibbs sampling is that an effective CoT recipe for solving a set of problems should be the one that can be applied to generating accurate solutions for all these problems, i.e. a common reasoning path. The distribution of such recipes is unknown, but we know how the solutions to these problems should be correlated. Thus, we can use Gibbs sampling to address the problem. Empirically, we found that the CoT solutions produced by Reprompting typically end up following a similar format and reasoning path, which verifies that by applying Gibbs sampling along with other approximations, we are able to discover common reasoning path for solving a set of problems.
• The wall-clock time for running Reprompting largely depends on the rate limit and delay of API calls to these LLMs. In our experiment, it takes 4-10 hours to run Reprompting on a single task.
• The motivation for decoupling initialization and sampling is based on the observation that some LLMs (e.g. GPT3.5) are better at generating more diverse reasoning paths than some others (e.g. text-davinci-003). Thus, using the former ones as the initialization model leads to a higher chance of discovering better CoT recipes for a task.
• The CoT prompts produced by Reprompting typically end up following a similar format and reasoning path. This is beneficial for finding a common, effective reasoning path for a specific type of problem. But for problems where the reasoning paths may vary greatly, it is best to first cluster the problems based on their type (e.g. by prompting LLMs about the category of the problem, whether they belong to dynamic programming, optimization, graph search or other problem types) or the clustering of their zero-shot solutions.

[1] Parameter-efficient transfer learning for NLP. Houlsby et al., ICML 2019.

[2] The power of scale for parameter-efficient prompt tuning. Lester et al., 2021.

[3] P-tuning: Prompt tuning can be comparable to fine tuning across scales and tasks. Liu et al., ACL 2022.

[4] Lora: Low-rank adaptation of large language models. Hu et al., 2021.

[5] Improving Prompt Tuning with Learned Prompting Layers. Zhu et al., 2023.

[6] Complexity-Based Prompting for Multi-Step Reasoning. Fu et al., 2022.

We thank the reviewer for the valuable comments and insightful questions. Here are some responses to the weaknesses and questions:

• In Eq(4), the first proportionality is deduced based on Bayes’ Theorem. The second approximation is based on the in-context learning assumption discussed in Eq(2). This assumption is based on the empirical findings in [3,4] on a wide range of tasks that the test performance remains similar when there is a varying number (but typically >= 5) of few-shot exemplars. We have updated Section 2.1 to better explain it.
• Our method uses 20 examples for CoT prompt generation, and the final prompt contains 5 example CoT. Since 20 labeled samples are used, it satisfies the definition of 20-shot learning. This is slightly different from the K-shot learning in standard few-shot prompting where K is the number of examples in the final prompt. But our comparison with few-shot prompting is still fair, since we are comparing our method with 20-shot prompting. As for the CoT baseline, since the number of CoT demonstrations is limited (and often less than 20) and each individual demonstration takes more tokens, we just take all the available CoT demonstrations that could fit into the prompt under the token limit.
• [1] proposed a novel self-adaptive prompting approach to improve model performance on reasoning tasks in zero-shot settings. In their approach, they generate step-by-step solutions through zero-shot CoT prompting and select demonstration examples from the zero-shot solutions via carefully designed criteria. This is different from our approach in that our approach is iterative so that zero-shot solutions can be recombined (Figure 4) and evolve into better recipes (Figure 3) through iterations. Empirically, since the approach in [1] does not outperform standard CoT (one of our baselines) on average, and their code has not been released yet, we didn’t include [1] as a baseline. But we will incorporate the discussion in paper. [2] proposed a novel prompt tuning method via reinforcement learning. The approach is based on a set of prompt editing operations that are designed for text classification tasks. Such approach is not directly applicable to reasoning tasks where the space of all possible step-by-step reasoning paths is huge, and one needs to explore the space by discovering and recombining new paths for solving the problem rather than simply rephrasing existing ones. We will incorporate the discussion and citations in the paper.

[3] Language Models are Few-Shot Learners. Brown et al., NeurIPS 2020.

[4] Chain-of-thought prompting elicits reasoning in large language models. Wei et al., NeurIPS 2022.