StrategyLLM: Large Language Models as Strategy Generators, Executors, Optimizers, and Evaluators for Problem Solving

Thank you for your insightful comments. We address each question as follows:

The intuition explained in the paper relies on generalization and consistency as the main traits of the proposed method. It would have been helpful to use a concrete example showing how alternative methods such as CoT fail to provide the right solution for a given problem while the method succeeds at doing so.

We use an example from the test set of the CP dataset in the MATH benchmark for illustration.

Question: Suppose that I have 6 different books, 2 of which are math books. In how many ways can I stack my 6 books on a shelf if I want a math book on both ends of the stack?

Gold Answer: 48

The CoT prompt for the CP dataset is illustrated in Figure 33 on Page 36 of our paper, while the strategy generated by GPT-3.5 is detailed in Figure 18 on Page 22. The predictions of CoT and StrategyLLM are as follows:

CoT Prediction:

We can treat the two math books as a single entity. So we have 5 entities to arrange on the shelf, which can be done in $5!$ ways. However, within the math book entity, the two math books can be arranged in $2!$ ways. Therefore, the total number of ways to arrange the books is $5! \cdot 2! = \boxed{240}$.
Answer: The answer is 240.

StrategyLLM Prediction:

1. Understand the problem statement:
  - We have 6 different books, 2 of which are math books.
  - We need to stack the books on a shelf in a way that a math book is on both ends of the stack.

2. Identify the counting or probability concept:
  - We need to use the concept of permutations to solve this problem.

3. Break down the problem:
  - We have 6 books, 2 of which are math books.
  - We need to arrange these books on a shelf in a way that a math book is on both ends of the stack.
  - The math books can be arranged in 2 ways (one on the left end and one on the right end).
  - The remaining 4 books can be arranged in 4! = 4 x 3 x 2 x 1 = 24 ways.

4. Calculate the required counting or probability:
  - To calculate the total number of ways to stack the books, we need to multiply the number of ways to arrange the math books with the number of ways to arrange the remaining books.
  - Total number of ways = 2 (ways to arrange math books) x 24 (ways to arrange remaining books) = 48.

5. Simplify or reduce the problem:
  - There are no further simplifications or reductions possible for this problem.

6. Communicate the solution clearly:
  - There are 48 ways to stack the 6 books on a shelf such that a math book is on both ends of the stack.

Answer: The answer is 48.

The CoT prediction fails to account for the requirement of placing a math book at both ends, resulting in an incorrect solution. In contrast, the generalizable strategy employed by StrategyLLM allows for a comprehensive understanding of the problem, effective utilization of relevant concepts, and a breakdown of the task. This approach ensures that critical details are not overlooked, leading to the correct answer. Additionally, consistently applying a strategy across few-shot examples illustrates how that strategy can be utilized in various contexts and ensures that the same strategy will be applied to the test instance.

Beyond accuracy, the solutions derived from StrategyLLM are more detailed, interpretable, and accessible, making them particularly suitable for contexts that demand clarity and comprehensibility, such as educational settings.

Where does the feedback in strategy optimizer come from? Is it automatically generated by LLM? If yes, can you elaborate more on how it's generated? If not, can authors clarify where feedback is coming from?

The feedback in the strategy optimizer is indeed automatically generated by LLMs. Following the execution of a strategy, we can identify which examples yield correct solutions and which do not. We then prompt the LLMs to analyze the incorrect solutions, providing insights into potential reasons for their failures, such as calculation errors, misunderstandings of the problem, or the application of incorrect formulas. The LLM also offers suggestions for enhancing the strategy, which may include adding subtasks, decomposing complex subtasks into simpler components, or revising ineffective subtasks. Subsequently, we utilize the LLM to refine the strategy based on this feedback.

Authors report the biggest gain from their method for symbolic reasoning tasks, but Addendum does not provide any examples of such tasks and the corresponding generated strategies.

We would like to clarify that we have included a strategy and an execution example for the LLC task in Figure 27 on Page 30 of our paper. This example illustrates the application of our method on symbolic reasoning tasks.

How does strategy LLM generate multiple sets of strategies? Is it by asking it to re-run the same prompt multiple times or does it involve changing the original prompt?

StrategyLLM generates multiple strategies by re-running the same prompt multiple times, utilizing temperature sampling to introduce variability in the outputs and allowing for the exploration of diverse strategies.

StrategyLLM might be susceptible to bias by generating discriminating strategies that may perform well on the training set, which is not addressed in the paper.

We emphasize that StrategyLLM is specifically designed to address potential biases present in few-shot prompts and to enhance the generalizability of the prompts through the use of task-level strategies. Our comprehensive results demonstrate that the strategy-based prompts exhibit greater generalizability compared to traditional CoT prompts.

Thank you for your insightful comments. We address each question as follows:

Regarding the actual prompt and text tweak

We appreciate your suggestions. We will incorporate these revisions in the new version of our paper.

Is the Strategy Generator the same LLM as being 'tested' - or is the strategy being generated originally by GPT-3.5?

We would like to clarify that the underlying LLM for the strategy generator, executor, optimizer, and evaluator is the same as the LLM being tested.

Thank you for your insightful comments. We address each question as follows:

A simpler approach that still tests the core idea of the paper would be to keep the strategy generator and inference steps, but skip the intermediate grading and optimization of the strategies. Would the method work without these extra prompting phases, or are they essential to the method?

We would like to emphasize that these phases are indeed essential to the method. Specifically, StrategyLLM relies on the strategy executor to apply the generated strategies to the provided examples. The execution results are necessary for formulating the strategy-based prompts. Additionally, the strategy evaluator plays a vital role in determining the most effective strategy for inference. Without these phases, we would be unable to generate the few-shot prompts necessary for each strategy or to make informed decisions regarding which strategy to employ.

Is it the data-driven validation of the prompt (in this case, a strategy) that is the main advantage of StrategyLLM, or is it specifically that the strategies are not instance-specific? An experiment that compares with a prompt selection approach analogous to StrategyLLM's (i.e. generating multiple prompts, grading them on a validation set, refining them as needed, using a validation set to select between them, and finally employing SC or ZC to get a final answer), but generating e.g. few-shot prompts instead of strategies would yield a fairer comparison.

We appreciate your valuable suggestion. In response, we implement a baseline approach, which involves initially generating $n$ prompts, retaining $k$ of these for validation, and subsequently selecting the prompt with the highest validation accuracy for inference. The results of Meta-Llama-3-8B-Instruct on the CP, StrategyQA, and MA datasets are presented in the table below. We can observe that StrategyLLM significantly outperforms this baseline across all datasets, highlighting the benefits of integrating generalizable strategies.

Regarding the SolutionLLM baseline

A solution is a step-by-step reasoning path. In this baseline, we utilize LLMs to generate a solution for each example in the prompt, which is the same as the examples used in the CoT prompt. These examples, along with their respective solutions, are then combined to formulate a few-shot prompt for inference, analogous to the CoT approach.

Regarding the evaluator and constructing the few-shot prompt

Unlike other agents, the strategy evaluator does not utilize a specific prompt. Instead, to assess the effectiveness of a strategy, the evaluator constructs a few-shot strategy-based prompt tailored to that particular strategy. An illustrative example of the strategy-based prompt is depicted in Figure 3 of our paper. This prompt is structured as follows: Strategy + (Question_1, Solution_1, Answer_1) + … + (Question_n, Solution_n, Answer_n). The solutions, Solution_1 through Solution_n, are derived during the strategy execution phase by applying the strategy to the $n$ examples in the prompt. The strategy evaluator then infers using each prompt on the validation set and calculates its validation accuracy.

In the paper, the execution and validation are presented as separate phases of the StrategyLLM method with different type signatures and different descriptions. Clarity-wise, I fear this might be obscure the fact they represent two rounds of validation and filtering.

Thank you for your observation. We acknowledge that these phases represent two rounds of validation. However, they differ in their approach to obtaining solutions. During the execution phase, we directly prompt the LLM to generate a solution for a specific example by following the strategy. Next, in the validation phase, the strategy and the examples with their solutions are utilized to construct the strategy-based prompt. LLMs use this strategy-based prompt to infer solutions for each validation example. We will clarify these distinctions in the revised version of our paper to enhance understanding.

Do you have evaluation of relative value of the presence of the strategy vs the presence of the consistent few-shot prompts.

We conduct experiments to assess inference performance without the presence of the strategy, utilizing only the consistent few-shot prompt. The results for Meta-Llama-3-8B-Instruct are summarized in the table below. The findings indicate that omitting the strategy leads to a decrease in performance. This is because the consistent prompt merely illustrates how to apply the strategy to specific examples and may not encapsulate all the nuances of the strategy itself.

I would encourage you to write out what StrategyLLM is in contrast with StrategyLLM-SC and StrategyLLM-ZS; my assumption is that StrategyLLM employs only one selected strategy, but I don't see this stated explicitly.

Yes. StrategyLLM employs the most effective strategy identified during our experiments. We will state this clearly in the revised version of our paper.

Why do you describe your approach as involving multiple LLM agents?

We follow the terminology used in existing popular agent frameworks such as BabyAGI (https://github.com/yoheinakajima/babyagi). Multiple agents collaborate to accomplish a task, with each agent assigned a subtask of the task. While the underlying LLMs for these agents can differ, our experiments utilize the same LLM across all agents to ensure a fair comparison.

Thank you for your insightful comments. We address each question as follows:

The paper says that a strategy is applied when it passes an accuracy threshold, which is <1. Does it mean that when using the few-shot prompt constructed by StrategyLLM, some examples have wrong solutions?

Yes, we would like to clarify the following points: (1) In most scenarios, we set the accuracy threshold at 0.75, and the number of examples used is fewer than 8, there can be at most 1 example with an incorrect solution in these scenarios. (2) These incorrect examples may not largely degrade the performance. As pointed out by existing research (e.g., [1]), the relevance of the solution to the question and the presentation of intermediate reasoning steps can be more critical than the correctness of the final answer.

[1] Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters. ACL 2023. https://aclanthology.org/2023.acl-long.153/

Have the authors tried self-consistency with a single strategy? How much performance gain is from aggregating multiple strategies compared to sampling from a single strategy?

We have explored self-consistency using a single strategy. The performance of Meta-Llama-3-8B-Instruct on the CP, StrategyQA, and MA datasets is summarized in the table below. "StrategyLLM-Single-SC" refers to self-consistency applied with the best-performing strategy identified, which generates a set of solutions via temperature sampling to obtain multiple answers. The results indicate that StrategyLLM-Single-SC underperforms compared to StrategyLLM-SC and even StrategyLLM, highlighting the advantages of aggregating multiple strategies.

Have the authors tried constructing a single prompt for all MATH problems, and how does it compare to baselines?

Thank you for your suggestion. We would like to clarify that constructing a distinct prompt for each subject may be more appropriate as the strategy can be more specific to the subject and incorporate more domain-specific knowledge of it.

Additionally, to address your question, we conduct experiments using a single CoT prompt and a strategy-based prompt, both utilizing the same 7 examples, with each example drawn from a different subject in the MATH benchmark. Both the StrategyLLM and CoT prompts were evaluated on the test sets across all MATH subjects. The results for Meta-Llama-3-8B-Instruct are presented in the table below. The findings indicate that StrategyLLM consistently outperforms CoT across all subjects, demonstrating the advantages of our framework.