Unleashing the Creative Mind: Language Model As Hierarchical Policy For Improved Exploration on Challenging Problem Solving

We sincerely thank you for your constructive feedback! We address the comments and questions below.

When we select the final answer among the groups of reasoning chains explored by our hierarchical policy, is our tournament-based selection approach better than direct majority voting?

We have added an experiment in our revised paper. We demonstrate that our tournament-based reasoning chain selection approach yields better final-answer accuracy over majority voting. Please see Common Response for more details.

Can our approach be effective under the code-interpreter setting?

Thanks for your suggestion and we have cited the paper. We’d like to note that the focus of our paper is to introduce a visionary high-level leader that provides helpful hints to guide the low-level follower during problem solving. On the other hand, the code-interpreter line of works focus on integrating code interpreters into the detailed problem solving processes (which is the role of the low-level follower under our hierarchical policy framework), and these works have not delved into high-level strategies or thinking processes to our best knowledge. Therefore, our paper's focus is orthogonal to using code interpreter to improve challenging problem solving. In particular, code interpreter-enhanced low-level followers can be naturally integrated into our hierarchical policy framework.

To our best knowledge, the API for GPT-4 code interpreter was just released publicly last week for gpt-4-1106-preview (see link here). We are actively working on implementations and experiments. We will try our best to add the results by the end of the rebuttal deadline. If we do not finish by then, we will add the results in final version.

Update Nov. 22

Can our approach be effective under the code-interpreter setting?

We have obtained the results where gpt-4-1106-preview with code interpreter serves as the low-level follower policy in our approach along with the language model in the CoT + Sampling baseline. We adopt $n=4$ groups, each sampling $m=4$ reasoning chains. Results on MATH Level-5 are shown below. We find that our hierarchical policy framework, combined with our tournament-based reasoning chain selection process, also yields better final answer accuracy under the code interpreter setting.

As a reference, we report the MATH Level-5 performance of different language models below, where each model samples a single CoT reasoning chain per problem (without sampling multiple reasoning chains or performing majority voting like in our previous settings). We find that utilizing code interpreter yields about 10% final accuracy improvement for GPT-4 models, while it is not helpful for GPT-3.5.

We sincerely thank you for your constructive feedback! We address the comments and questions below.

Evaluation over more datasets, like GSM8K and PRM800K.

Thanks for your suggestion! We have added additional experiments on GSM8K, and our approach continues to achieve better final-answer accuracy. Please refer to the Common Response for detailed results.

(Note: The PRM800K also employs the MATH dataset, which is the same dataset our paper's experiments are based on.)

Is our improvement coming from the hierarchical policy framework or the "self-evaluation" process when choosing the better reasoning chains?

Thanks a lot for your suggestion. We have added two ablation experiments in our revised paper. In the first experiment, we investigate whether the baseline CoT + Sampling performance can be improved through our tournament-based evaluation process. Results are shown in Table A below. We find that adding our tournament selection process to the baseline does not ourperform our approaches that adopt the hierarchical-policy framework, demonstrating that our hierarchical policy plays a significant role in enhancing LLM's ability to solve challenging problems.

In the second experiment, we investigate the effect of majority voting vs. our tournament selection on the final answer accuracy of our hierarchical policy approaches. Results are shown in Table B below. We find that for our hierarchical policy approaches, adopting our tournament selection process yields better final answer accuracy than using majority voting, so our tournament selection process is also helpful. Intuitively, this is because not all of the tactics and hints produced by our high-level leader are helpful, and some of them might mislead the low-level follower, potentially causing it to generate a consistent but wrong answer under a misleading high-level guidance. By evaluating reasoning chains using our tournament-based selection approach, we effectively remove those that exhibit reasoning mistakes and keep those that are more trustful.

Table A: Effect of our tourament-based reasoning chain selection approach on the CoT + Sampling baseline. For the baseline, we randomly partition the 64 sampled reasoning chains per problem into $n=4$ groups, each having $m=16$ reasoning chains. We use GPT-3.5 as the language model for our low-level follower and the CoT Sampling Baseline.

Table B: Effect of majority voting and our tournament-based reasoning chain selection on the final-answer accuracy of CoT + Sampling baseline and our hierarchical policy approaches. For "Majority Voting", we directly perform majority voting over the 64 sampled reasoning chains per problem. For "Majority Voting over Groups" and "Tournament", we adopt $n=4$ groups, each having $m=16$ reasoning chains. We use GPT-3.5 as the language model for our low-level follower and the CoT Sampling Baseline.

What's the motivation of the "Grouped-Majority Recall" metric?

The motivation of our Grouped-Majority Recall metric is presented in the second and the fourth paragraph of Sec. 4.1, along with Figure 4. We have also made our motivation more clear in our revised paper.

In detail, the purpose of our metric is to assess the “visibility” of the correct answers among solutions generated along the exploration process. A correct answer is “visible” if it not only exists in at least one of reasoning chains, but also occupies a substantial proportion of them, even though it might not be the majority answer. We find that standard metrics like accuracy and recall do not perfectly align with our goal. This is because standard recall poorly correlates the prominence of correct answers, and standard accuracy does not reflect the scenario where LLM identifies correct solutions by a reasonable chance (and more than once), but the correct solutions are submerged during majority voting. On the other hand, our Grouped-Majority Recall metric allows correct answers that are identified by a reasonable chance but become obscured in majority voting to emerge, while ensuring that all correct answers recognized by our metric take up the majority in at least one reasoning group and are represented in more than one reasoning chains.

A more intuitive idea may be the percentage of questions whose ground truth answer exists in at least one of the answers.

The percentage of questions whose ground truth answer exists in at least one of the answers is the "standard recall" metric referred in the last comment. From our analysis, we find that the standard recall metric is not an ideal metric to assess the visibility of correct answers, because as the number of reasoning chain samples increases, the standard recall steadily improves, but the standard accuracy quickly plateaus after a few reasoning chain samples (as shown in Fig. 4a of the paper). Thus, the standard recall metric does not correlate well with the prominence of correct answers.

In GPT-3.5 based approaches, is the "tournament" based on GPT-4 or GPT-3.5 (you mentioned that the GPT-4 is prompted to compare the current chains with (i+1)-th chain (Section 3) )?

In our tournament-based reasoning chain selection process, we use GPT-4 to compare the current reasoning chain with the $(i+1)$-th chain, where the reasoning chains can be generated by either GPT-3.5 or GPT-4.

We further add an ablation study in Table 5 of the revised paper to compare using GPT-3.5 or GPT-4 to conduct our tournament-based reasoning chain selection process. We observe that GPT-4 demonstrates stronger performance as a reasoning chain selector than GPT-3.5 with a limited number of comparison repetitions (e.g., $k = 1$). Additionally, with only $k=1$ comparison repetition, GPT-4 already leads to a noteworthy enhancement of final answer accuracy over the CoT Sampling baseline.

We sincerely thank you for your constructive feedback! We address the comments and questions below.

Is our approach novel? I would like to refer to the opinions from other reviewers.

We'd like to kindly highlight the comments from two reviewers, vZb3 and ufPr, both of whom acknowledge the novelty of our framework and approach.

We’d also like to clarify our paper's contribution and novelty below:

• Framing large language models (LLMs) as a hierarchical policy that encompass both “high-level” and “low-level” cognitive processes, thereby allowing LLMs to effectively explore expansive solution spaces in complex problems. To our best knowledge, this line of work is underexplored in the field of LLM problem solving.
• Proposing two effective approaches for the high-level leader policy to generate tactics and hints that guide the low-level follower policy. These approaches include generating concise and relevant techniques and concepts along with retrieving relevant problems.
• Proposing a novel tournament-based approach to efficiently and effectively select the final reasoning chain.

Clarification of Equation 1

Thanks for your suggestion. The answer, hint, and question spaces are all discrete, so we have replaced the integral sign with the sum sign and changed our equation (1) to

$\mathrm{Pr}(A|Q) = \sum_{h}\mathrm{Pr}(A|h, Q) \cdot \text{Unif}(h\in H)\cdot \mathrm{Pr}(H|Q)$

in our updated paper.

(As a side note, we originally used the integral sign as we were using a more general measure theory-style notation, under which one could use the integral sign to integrate over any measurable space, such as discrete spaces with counting measure and $\mathbb{R}^n$ with Lebesgue measure. In our original Equation 1, the integral was with respect to the counting measure over our discrete hint space, i.e., $\mathrm{Pr}(A|Q) = \int_{h}\mathrm{Pr}(A|h, Q) \cdot \text{Unif}(h\in H)\cdot \mathrm{Pr}(H|Q) d\mu(h)$ and $\mu$ is the counting measure. In our original paper, we omitted $d\mu(h)$ for brevity, which possibly caused the confusion.)

Core message of our "Probabilistic Interpretation" Section

Thanks for your suggestion. As suggested, we have highlighted the sentence our strategy samples all the different hints returned by $\pi_{high}$ with equal probabilities in our updated paper.

We'd like to also clarify that the purpose of our "Probabilistic Interpretation" section is to provide an intuition of why our proposed hierarchical policy approach endows LLMs with better exploration ability in solving challenging reasoning problems, compared to previous approaches that directly sampling multiple reasoning chains to explore the solution space. Our analysis reveals that directly sampling reasoning chains is prone to stucking in a single or a few high-probability tactics, while our hierarchical approach allows tactics to be more uniformly sampled, which is beneficial for solving challenging math problems that require out-of-the-box thinking.

Improve the writing organization for our motivation of "Grouped-Majority Recall"

Thanks for your suggestion. We have revised our paper and added multiple boldface highlights to make the core messages clear when we describe the motivation of our Grouped-Majority Recall metric.

In detail, the goal of our metric is to assess the “visiblity” of the correct answers among solutions generated along the exploration process. A correct answer is “visible” if it not only exists in at least one of reasoning chains, but also occupies a substantial proportion of them, even though it might not be the majority answer. The second paragraph of Sec. 4.1, along with Figure 3, demonstrates why standard metrics like accuracy and recall are not suitable for our goal. The third paragraph of Sec. 4.1 explains the definition of our Grouped-Majority Recall metric. The fourth paragraph of Sec. 4.1 demonstrates why our Grouped-Majority Recall metric better measures the visibility of correct answers compared to the standard accuracy and recall metrics.

When we select the final answer among the groups of reasoning chains explored by our hierarchical policy, is our tournament-based selection approach better than direct majority voting?

We have added an experiment in our revised paper. We demonstrate that our tournament-based reasoning chain selection approach yields better final-answer accuracy over majority voting. Please see Common Response for more details.

Clarification on retrieval-based hint generation

After the high-level leader retrieves a relevant problem along with its step-by-step solution, the problem and the solution directly serves as the hint for the low-level follower to carry out the problem-solving process (see Table 10 in Appendix for an illustration). There are no further prompting to generate (more concise and high-level) hints using the retrieved problem and solution.

Thanks for your feedback! We've revised the introduction and methodology sections, using bold and italic formatting to emphasize our core motivations and key contributions more clearly and directly. We hope that combined with our revisions in the later experiment and analysis sections, we have enhanced the overall clarity and understanding for our readers. Should you have any further suggestions, please let us know.

Dear Reviewer qX4Z,

Thanks for your feedback! Could you please suggest further revisions (if any) that would make our work more satisfactory to you and potentially improve our rating in your evaluation? Your guidance would be greatly appreciated.

We sincerely thank you for your constructive feedback! We address the comments and questions below.

Evaluation over GSM8k

Thanks for your suggestion! We have added additional experiments on GSM8K, and our approach continues to achieve better final-answer accuracy. Please refer to the Common Response for detailed results.

Version of GPT-3.5/GPT-4 along with their hyperparameters

We use GPT-3.5-turbo-0613 and GPT-4-0613 for all the experiments. For hyperparameter details, we set the decoding temperature to 0.3 for tournament-based reasoning chain selection and 0.7 otherwise (i.e., for hint generation from the high-level leader, reasoning chain generation from the low-level follower, along with the baselines). These hyperparameters were briefly mentioned in the first paragraph of our experiment setup. For clarity purposes, we have added an additional section (Appendix B in the updated PDF) to describe the GPT-3.5/4 settings used in the paper.

Effect of Different Model Configurations

Thanks for your suggestion. We have added an experiment in Table 5 and 6 of the revised paper, where we perform ablations on different models (GPT-3.5 / GPT-4), different comparison repetitions $k$, and different temperatures $T$ used to perform our tournament-based reasoning chain selection process (in our previous paper's experiments, we used GPT-4 model, $k=1$, and $T=0.3$ for tournament selection). We copy the results below for convenience. We find that GPT-4 demonstrates stronger performance as a reasoning chain selector than GPT-3.5 with a limited number of comparison repetitions (e.g., $k = 1$). In particular, with only $k=1$ comparison repetition, GPT-4 already leads to a noteworthy enhancement of final answer accuracy over the CoT Sampling baseline. Additionally, when $0<T<1$, different temperatures during tournament selection have little effect on the final answer accuracy.

Table 5: Ablation on using different models to conduct our tournament-based reasoning chain selection process, along with using different k, i.e., different numbers of comparison repetitions, during this process. We compare our retrieval-based method with the CoT Sampling baseline. We use GPT-3.5 as the language model for our low-level follower and the CoT Sampling Baseline.

Table 6: Ablation on using different temperature (T) in our tournament-based reasoning chain selection process. Results are obtained using GPT-4 as our tournament selection model with $k=1$ comparison repetition. We use GPT-3.5 as the language model for our low-level follower and the CoT Sampling Baseline.

Cost analysis comparison.

Thanks for your suggestion. We compare the cost between our approach and the CoT + Sampling Baseline below (unit in dollars; tournament performed with GPT-4; a total of 64 reasoning chains are generated per question). We also add this table in Appendix Section C. While our approach is slightly more expensive than the CoT baseline when GPT-3.5 serves as the low-level follower, it is more cost efficient than the baseline when GPT-4 serves as the follower, and moreover yields better final answer accuracy.

Additionally, we also compare the average number of input and output tokens between the baseline and our approach. The number of output tokens is calculated over the sum of 64 reasoning chains sampled per question. (For both GPT-3.5 and GPT-4, input tokens cost half as much as output tokens.)