DOTS: Learning to Reason Dynamically in LLMs via Optimal Reasoning Trajectories Search

Authors: Murong Yue, Wenlin Yao, Haitao Mi, Dian Yu, Ziyu Yao, Dong Yu
Primary area: foundation or frontier models, including LLMs
Keywords: large language model, reasoning

Abstract:
Enhancing the capability of large language models (LLMs) in reasoning has gained significant attention in recent years. Previous studies have demonstrated the effectiveness of various prompting strategies in aiding LLMs in reasoning (called "reasoning actions"), such as step-by-step thinking, reflecting before answering, solving with programs, and their combinations. However, these approaches often applied static, predefined reasoning actions uniformly to all questions, without considering the specific characteristics of each question or the capability of the task-solving LLM. In this paper, we propose DOTS, an approach enabling LLMs to reason Dynamically via Optimal reasoning Trajectories Search, tailored to the specific characteristics of each question and the inherent capability of the task-solving LLM. 
Our approach involves three key steps: i) defining atomic reasoning action modules that can be composed into various reasoning action trajectories; ii) searching for the optimal action trajectory for each training question through iterative exploration and evaluation for the specific task-solving LLM; and iii) using the collected optimal trajectories to train an LLM to plan for the reasoning trajectories of unseen questions. In particular, we propose two learning paradigms, i.e., fine-tuning an external LLM as a planner to guide the task-solving LLM, or directly fine-tuning the task-solving LLM with an internalized capability for reasoning actions planning. Our experiments across eight reasoning tasks show that our method consistently outperforms static reasoning techniques and the vanilla instruction tuning approach. Further analysis reveals that our method enables LLMs to adjust their computation based on problem complexity, allocating deeper thinking and reasoning to harder problems.

Decision: accept (poster)
Reviewer scores: 8, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1729099780157

thread_type:
official_review

<thread_object>
creator: reviewer_npg3

<content>
summary:
The author creates a planning prompt strategy named DOTS. It can choose the path to solve the problem via a small model (as the planner) and prompt the large model to solve the problem. The path contains 3 parts: the Analysis Layer, the Solution Layer, and the Solution Layer. The experiment shows that both external and internalized planner can help the large model to solve the problem more effectively and efficiently. The ablation study also shows that the searching and explanation in planner's plan is useful.

strengths:
1. The paper is easy to read and follow. Its ideas are presented straightforwardly along with illustrations.

2. It simplifies the planning prompt construction process. 

3. The authors study the DOTS over a wide range of benchmarks.

weaknesses:
1. The comparison between the DOTS and other methods is not fair. The DOTS's prompt contains 3 layers, however, the baselines only contain 1/2 layer. The authors should compare the baseline with 3 layers (for example compulsory use of Decomposition + POT + self-verifications at the same time in MATH) to make the comparison more fair.

2. The method is not generalizable enough. It needs to SFT a new model for each large model / new atomic action in layers / new layers. (Although the authors claim that this is an advantage to make the prompt more suitable for a given model, it is still a limitation for the method.)

3. The improvement of the DOTS is not significant, especially in the OOD dataset. 

4. The ablation study only shows the result in the IND benchmark 

5. The ablation study in Table 6 does not explain the inherent reason that DOTS can improve performance, it's not enough for ICLR. (For example, can a large model have a similar performance with DOTS by only adding prior knowledge in the explanation?). (see question 3,4,6 below for more details)

questions:
1. could you present the distribution of the path the planner will choose in the experiment? (i.e. x% of the path will choose Empty + POT + self-verifications, y % of the path will choose Decomposition + COT + Empty, etc.) (This is different from Table 7 in 2 parts: 1. It shows the distribution of the 12 types of combination of 3 layers in the path, 2. It needs to contain more benchmarks besides the MATH dataset)

2. Can 2 findings in Section 3.7 be generalized to other datasets?  

3. (From weakness 1) The authors should add a comparison with the baseline with 3 layers (and the choice of the layer should be reasonable towards a given benchmark) to make the comparison more fair.

4. From my perspective, the OOD benchmark is more important than the IND benchmark, however, the authors only show the ablation study in the IND benchmark. Why?

5. The improvement of the DOTS seems to come from the explanation (if you compare the result in Table 6's "-w/o Explanation" line with the second to the last line in Tables 3 and 4). So, does the prior knowledge in the prompt cause the improvement? 

6. (minor) The author claims that "the fine-tuned LLMs are constrained to follow the same reasoning format of the training data (e.g., CoT (Luo et al., 2023)) and lack the flexibility to adopt other reasoning strategies" (in line 53,77-78). However, FireAct[1], shows that the fine-tuned LLMs can change the reasoning strategies (COT or ReAct) by itself without any additional prompt. Maybe training COT and POT at the same time can help the model to be more flexible. The authors should revise this point to make it more accurate.

7. In Internalized setting, I'm curious that if llama3-8b is trained only in the Reasoning Process and Answer (like FireAct), what performance will be, will the trained model choose the Reasoning Process automatically? (It should also be a baseline), although I admit this can't be used in external setting.

8. (minor) In Table 2, "Few-shot" is not a kind of Distribution, maybe 4 columns (add example number column) can be more clear.

[1] FIREACT: TOWARD LANGUAGE AGENT FINE-TUNING
</content>
</thread_object>

</thread>
<thread>
creation date:
1729839657377

thread_type:
official_review

<thread_object>
creator: reviewer_6ppw

<content>
summary:
The paper proposes DOTS, which can dynamically choose prompting methods to do reasoning, by dividing reasoning into analysis, solution, and verification modules, and choosing from recent popular methods for each module.

The dynamic planner can be either external or internal to incorporate various LLMs with difference sizes and openness.

Experiments are conducted on in-distribution, near-distribution, and out-of-distribution settings, and zero-shot and few-shot evaluations, where DOTS outperforms most recent LLM prompting reasoning methods.

strengths:
DOTS unifies many of recent LLM prompting reasoning methods, and can dynamically choose better method for each module for each data sample. It borrows the strength of various solutions in literature, and can possibly incorporate future works.

The paper contains comprehensive experimental results, on various datasets across domain, and in/near/out-of-distribution experiments. The experiments show superior performance of DOT to previous prompting methods consistently.

The paper also includes ablation studies to verify the importance of each of the breakdown modules.

It also includes analysis of preferences of DOTS on different tasks, with insightful explanations. It also includes an analysis of efficiency, showing comparable computing costs to other advanced prompting techniques.

weaknesses:
Although DOTS has higher average performance, DOTS cannot consistently beat baselines in all tasks. This is a little surprising as DOTS should be able to be considered as superset of all baselines. On those dataset DOTS fall behind baselines, it would mean it's not necessary to do dynamical reasoning (as one can choose the baseline instead of choosing different modules for each data sample).

This phenomenon is more often in out-of-distribution settings. The average score on out-of-distribution also shows smaller margin. This means lack of training (in a domain) can lead to much worse performance of DOTS. However, as also mentioned by author, such training set may be not available, casting generalizability concern on DOTS.

It would be beneficial to show the comparison on near-distribution zero-shot settings (e.g. the few-shot datasets in the paper) to verify that only near-distribution training is needed, but the paper only includes few-shot settings on these datasets. (also see questions)

To clarify, the few-shot experiments with consistent outperformance can partly address the point, but I would expect better zero-shot performance since training is involved.

questions:
+ (Type) Equation 2: $T$ has not been defined.
+ (Clarification) For the "few-shot" settings, do you use the planner trained on MATH dataset? If so, they should be "near-distribution + few-shot", since those "few-shot" datasets are math-related.
+ Since DOTS has marginal performance on OOD tasks (despite DOTS need additional training), what's the performance on near-distribution (e.g. the few-shot datasets in the paper) but zero-shot settings?
+ In Table 3, 4, 5, on a few datasets DOTS is not the best among methods. Does it mean in some datasets, it's better to choose one single baseline method instead of choosing modules dynamically as in DOTS?
+ DOTS select one reasoning method (one choice for each module). Would it be better to attempt multiple choices and choose the best one (and this would align more with "trajectory search")?
+ (Minor) It would be beneficial to also include the computing efficiency of external DOTS.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730500425012

thread_type:
official_review

<thread_object>
creator: reviewer_in1a

<content>
summary:
The paper proposes a new way to learn reasoning through two learning paradigms. The paper (DOTS) proposes both a way to FT an planner LLM and in directly FT-ing the task solver.

strengths:
1. Adaptability of the method: The method can be used either on the planner or on the task solver.

2. The method shows lower cost than non-CoT methods.

3. Improved Reasoning ability: The paper demonstrates improved reasoning ability by allowing for dynamic selection for a given question, outperforming static methods as well as self refinement (most but not all scenarios).

weaknesses:
1. The proposed method is complex and involves several steps. It is not clear if the complexity is warranted and ablation studies on the various aspects can help.

2. The paper does not explore decomposition or tool use which would be crucial for complex tasks.

3. The paper glosses over how the atomic trajectories are collected.

questions:
Q1. How many trajectories are required to improve performance substantially at FT-time? A more thorough discussion would be useful.

Q2. How does the proposed approach scale to more complex problems where process rewards would be beneficial?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730649484143

thread_type:
official_review

<thread_object>
creator: reviewer_kuiz

<content>
summary:
This paper proposes DOTS, an approach enabling LLMs to reason dynamically via optimal reasoning trajectories search, tailored to the specific characteristics of each question. DOTS first defines atomic reasoning action modules, then searches for the optimal action trajectory for each training question through iterative exploration and evaluation for the specific task-solving LLM, and uses the collected trajectories to train a model to plan for the reasoning trajectories of unseen questions.

strengths:
1. The authors propose a dynamic reasoning method which can enable the model to decide the appropriate atomic actions based on the characteristics of the input question.
2. The authors conduct comprehensive experiments to prove the effectiveness of the proposed method, containing in distribution, few-shot, and out-of-distribution settings.
3. The proposed method can be used on both open-source and close-source models.

weaknesses:
1. The method proposed in this paper does not show significant improvement on out-of-distribution (OOD) tasks, and it incurs additional computational overhead compared to prompt engineering methods.
2. The baseline for Vanilla SFT only used the training data from CoT. I believe it should be compared with baselines from other reasoning formats to demonstrate the effectiveness of the proposed method, such as using the program reasoning format and mixed training data from CoT and Program.
3. The experiments demonstrating the effectiveness of the Search section are compared with randomly selected reasoning paths. I am curious about how the results would compare if we contrasted it with reasoning paths generated by combining non-empty actions from each layer.
4. Using PoT prompts on non-code models may yield suboptimal results. Would combining PoT with code models improve the results of the PoT baseline?

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732555929619

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Reply

comment:
We appreciate all the reviewers for their valuable feedback and constructive suggestions. In this message, we summarized some common concerns and our response. 
1. Performance of OOD tasks:

Before responding to the shared concern about our OOD result, we would like to clarify the goal of this work. Our goal is to have a planning strategy that universally works well for all kinds of reasoning problems, and the scenario we target is that in an open-world setting, users of an LLM can ask any questions. In other words, we are not building any task-specific planner and do not know the question type before the user asks a question. Therefore, picking a pre-defined reasoning trajectory optimized for a single task intuitively would not be an optimal strategy. Instead, we aim to devise a dynamic reasoning approach that has the flexibility to plan for the optimal reasoning trajectory based on the user question or task at the test time. Under this scope of work, we are more concerned about whether a dynamic reasoning approach can achieve strong performance _consistently across tasks_, rather than beating the state-of-the-art approach on any single task, as we did not introduce new reasoning actions.
  
As for our OOD experimental results, Reviewer 6PPW expressed the concern that DOTS did not outperform the best approaches on all tasks. As our method only plans on the use of existing modules but does not introduce any new reasoning components, we do not expect DOTS to substantially outperform the best pre-defined reasoning path in any single dataset, especially for datasets where the type of questions is not diverse and one single trajectory is much better than all others. In our target scenario, an ideal planner should (1) achieve performance that surpasses any single static trajectory on datasets that require diverse optimal trajectories, such as MATH, and (2) maintain consistently on-par performance with the best static prompting method on datasets where a single trajectory is always optimal, such as Game of 24. Our experiments confirm that our method achieves this goal better than any baseline, demonstrating that DOTS can make the LLM more adaptable to different tasks.

The second common concern is that the improvement of DOTS is not significant compared to baselines. As discussed earlier, our method does not introduce additional components or actions, so significant improvements should not be expected across every single task. However, our approach always obtains a comparable or best result consistently across all tasks. The strongest baseline to us is “self-refine”, which integrates PoT and verification. Because for two out of the four OOD datasets (i.e., DeepMind-Math and MMLU-pro), PoT and verification are mostly sufficient, DOTS’s performance is either comparable or slightly better (in the latter case, it is often a result of additionally applying an analysis component). On the other two datasets (i.e., StrategyQA and DROP), PoT is not a preferable choice, yet DOTS flexibly selects CoT as a better action; as a result, the strong baseline “self-refine” performs 2-3% absolute accuracy lower than DOTS. Overall, DOTS consistently performs better or on par with “self-refine”, which shows the strong advantage of dynamic reasoning.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes to enhance LLM reasoning via dynamically tailoring trajectory search. The proposed method should be generally applicable. The experiments show that its inference cost could potentially be lower than non-CoT methods. The proposed method is intuitive. However, the experiments, especially the setting could be more principled. Some of the comparison may not be completely fair to the baselines when considering the details. Its OOD improvement seems limited, considering it requires SFT before deploying the method. Thanks to some of the added new experiments, some of the concerns is alleviated.