PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Murong Yue, Wenlin Yao, Haitao Mi, Dian Yu, Ziyu Yao, Dong Yu

arXiv:2410.03864v2cs.AIcs.CLcs.LG

TL;DR

Static reasoning strategies do not account for each question's characteristics or the task-solving LLM's capabilities. DOTS searches for question-specific reasoning trajectories and trains an external or internalized planner to select them. Across diverse reasoning challenges, it consistently outperforms static prompting and vanilla instruction tuning.

  • Problem

    Existing instruction tuning and prompting do not dynamically select strategies for each question and task-solving LLM, although strategy effectiveness varies with both.

    Source: §1 · p. 2

  • Method

    DOTS searches composed atomic reasoning-action trajectories for training questions, then fine-tunes an external planner or the task-solving LLM to plan trajectories.

    Source: §1 · p. 2, §2.1 · p. 3

  • Results

    DOTS consistently outperforms static prompt engineering and vanilla instruction tuning across diverse reasoning challenges and evaluated LLMs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    DOTS reports that LLMs allocate deeper reasoning to harder problems through exploration and learning, without explicit guidance.

    Source: §1 · p. 3

Abstract

from arXiv · show

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 trajectory 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.

1 INTRODUCTION

Static instruction-tuning and prompting approaches do not dynamically select reasoning strategies for each question and task-solving LLM. DOTS searches for question-specific trajectories and trains a planner, either external or internalized, to choose them.

1 INTRODUCTION

  • Existing reasoning actions include step-by-step prompting, executable programs, question decomposition, and solution verification.The introduction describes instruction tuning and prompt engineering as dominant approaches to eliciting reasoning.Source: §1 · pp. 1–2
  • Static fine-tuning can lock models into their training format, while fixed prompts may not suit each question or solver's capabilities.The paper notes that code-pretrained LLMs can be better suited to programming-aided reasoning.Source: §1 · p. 2
  • DOTS composes atomic reasoning actions into candidate trajectories, searches for effective paths, and fine-tunes a planner for the task-solving LLM.The planner can be a separate LLM or the solver itself, depending on solver accessibility and training cost.Source: §1 · p. 2
  • DOTS consistently outperforms static prompt engineering and vanilla instruction tuning across diverse reasoning challenges and evaluated LLMs.The evaluation includes in-distribution, few-shot, and out-of-distribution scenarios.Source: §1 · p. 2
  • DOTS reports adaptive action selection, minimal additional financial costs, and deeper computation for harder problems without explicit guidance.The action distribution analysis considers both question characteristics and task-solving LLM capability.Source: §1 · p. 3

2 DOTS: LEARNING TO REASON DYNAMICALLY

DOTS defines composable reasoning actions, searches for effective trajectories tailored to each training question and solver, then trains planners to select trajectories for new questions. It supports both external planners and planning internalized in the task-solving LLM.

2.1 OVERVIEW

  • DOTS offers external-planner tuning for closed-source or costly-to-train solvers, and internalized-planner tuning for open-source, small-size solvers.The external planner selects actions and the solver generates the reasoning process and answer; the internalized setup trains the solver to plan and perform the task.Source: §2.1 · p. 3

2.2 DEFINING ATOMIC REASONING ACTIONS MODULES

  • The action modules cover query rewriting or decomposition, natural-language CoT or code-generating PoT, and self-verification with feedback-guided retries.Empty actions in the analysis and verification layers let the model bypass those layers for simple questions.Source: §2.2 · pp. 3–4

2.3 SEARCHING FOR OPTIMAL REASONING ACTION TRAJECTORIES

  • For each training question, DOTS searches candidate trajectories using the task-solving LLM, evaluates them against the ground truth, and prunes paths unlikely to be optimal.Candidates are ranked by accumulated success rate and then shorter trajectory length; examples where all paths succeed or all fail are excluded from planner training.Source: §2.3 · pp. 4–5

2.4 LEARNING TO PLAN FOR OPTIMAL REASONING TRAJECTORIES

  • Supervised fine-tuning trains planners on the searched trajectories, with external planners predicting an explanation and trajectory and internalized planners also predicting the solver's reasoning and answer.The internalized setup uses the solver's reasoning process collected while it follows the selected trajectory.Source: §2.4 · p. 5

3 EXPERIMENT

The experiments evaluate DOTS across in-distribution, few-shot, and out-of-distribution settings against prompt-engineering and instruction-tuning baselines. External-planner results report gains on MATH and BBH, with performance depending on task demands.

3.1 EXPERIMENTAL SETUP

  • Evaluation covers in-distribution MATH, few-shot BBH, Game of 24, and TheoremQA, and OOD DeepMind Math, MMLU-Pro, StrategyQA, and DROP.The few-shot training examples include four examples from each BBH category and four each from Game of 24 and TheoremQA.Source: §3.1 · pp. 5–6
  • External-planner tuning uses Llama-3-8B-Instruct as planner and GPT-4o-mini or Llama-70B-Instruct as the task-solving LLM.Table 3 reports accuracy for in-distribution and few-shot datasets, with L and P denoting language and program reasoning formats.Source: §3.1 · p. 6, Table 3 · p. 6

3.2 BASELINES

  • Baselines include CoT, PoT, Least-to-most, Self-refine, PromptAgent, and vanilla supervised fine-tuning.PromptAgent and vanilla SFT use training data from the same source as DOTS.Source: §3.2 · p. 6

3.3 EXTERNAL PLANNER TUNING RESULTS

  • 57.7% accuracy with Llama-3-70b-Instruct and 75.4% accuracy with GPT-4o-mini on MATH are reported for external-planner DOTS.The results are presented in Table 3 alongside in-distribution and few-shot evaluation.Source: §3.3 · p. 6, Table 3 · p. 6
  • On BBH, DOTS improves over the best static methods by 3.5% with Llama-3-70B-Instruct and 3.1% with GPT-4o-mini.On Game of 24 and TheoremQA it shows slight improvements or performs similarly to the best static method.Source: §3.3 · p. 7

3.4 INTERNALIZED PLANNER TUNING RESULTS

Internalized planner tuning outperforms existing methods on average, while DOTS maintains high accuracy across diverse OOD tasks. Ablations and trajectory analyses indicate the importance of search and explanations and show adaptation to question type and solver capability.

3.4 INTERNALIZED PLANNER TUNING RESULTS

  • Internalized DOTS outperforms prompt-engineering methods and vanilla SFT on average, with an 8.7% increase over vanilla SFT on BBH.The authors attribute the performance boost to jointly optimizing trajectory planning and problem-solving; Table 4 reports in-distribution and few-shot performance.Source: §3.4 · p. 7, Table 4 · p. 7

3.5 OUT-OF-DISTRIBUTION EXPERIMENTAL RESULTS

  • Across OOD challenges, DOTS maintains high accuracy across datasets and models, while static methods fluctuate and can sharply decline on DeepMind Math.CoT has a slight advantage over DOTS on MMLU-Pro and StrategyQA with Llama-3-70B-Instruct, but not on DeepMind Math.Source: §3.5 · p. 7, Table 5 · p. 8

3.6 ABLATION STUDY

  • Ablations indicate that optimal-trajectory search and explanation generation are both important for reliable trajectory prediction.Without search, the planner did not consistently select PoT for Game of 24; without explanations, suitable trajectory prediction was less reliable.Source: §3.6 · pp. 7–8, Table 6 · p. 8

3.7 OPTIMAL TRAJECTORY ANALYSIS FOR DIFFERENT TASKS

  • On MATH, DOTS selects more PoT for number theory and more CoT for geometry, and shifts action distributions with the solver’s capabilities.GPT-4o-mini performs better with CoT on MATH and receives a higher proportion of CoT actions, whereas Llama3-70B-Instruct performs better with PoT and receives more PoT actions.Source: §3.7 · pp. 8–9, Table 7 · p. 9
  • Question rewriting and decomposition are selected infrequently on MATH, where problems are precise and strong solvers’ CoT can include decomposition.Source: §3.7 · p. 9

3.8 ADDITIONAL ANALYSES

Additional analyses examine few-shot evaluation, output-token efficiency, and computation by problem difficulty. DOTS outperforms baselines in few-shot evaluation and uses longer trajectories for harder MATH problems.

Few-shot In-context Learning Setting

  • In few-shot evaluation, DOTS continues to outperform baseline models, while static prompting with demonstrations does not improve consistently except on BBH.Game of 24 is excluded because knowing the task in advance allows it to be solved with a straightforward program.Source: §3.8 · p. 9

How efficient is DOTS?

  • DOTS consumes fewer output tokens on average than other advanced approaches and more only than CoT.The comparison uses average output token count for Llama-3-8B-Instruct; the authors link lower use to avoiding redundant reasoning actions.Source: §3.8 · p. 10, Table 9 · p. 10

Do we need more reasoning steps for difficult questions?

  • On MATH, harder problems have longer average reasoning trajectories, and the planner increases verification-step proportion as difficulty rises.Trajectory length counts EMPTY as zero and every other action as one; difficulty comes from annotated MATH levels.Source: §3.8 · p. 10

4 RELATED WORK

Prior work elicits reasoning through prompting and searches over reasoning paths, but DOTS treats reasoning actions rather than individual CoT steps as the atomic search component. The paper also contrasts its adaptive action selection with automated prompt approaches that still produce static prompts.

Prompt engineering for LLM reasoning

  • CoT prompts step-by-step reasoning, while PoT uses code as an intermediate reasoning step (Chen et al., 2022).Source: §4 · p. 10
  • Automated prompt optimization methods described here still produce static prompts, while DOTS selects reasoning actions for question and solver characteristics.The passage contrasts this with instance-level prompt optimization as a passive expert-designed workflow lacking exploration and evaluation.Source: §4 · p. 10

Searching for boosting LLM reasoning

  • Unlike prior search methods that use CoT reasoning steps as atomic components, DOTS searches over reasoning actions.The cited examples of prior search include Tree-of-Thought, Graph-of-Thought, and MCTS (Qi et al., 2024; Xie et al., 2024).Source: §4 · pp. 10–11

5 CONCLUSION

DOTS trains LLMs to plan reasoning trajectories by searching for optimal action sequences, enabling adaptation to questions and solver capabilities. Experiments support the effectiveness of this approach and its external and internalized planner-tuning paradigms.

5 CONCLUSION

  • DOTS defines atomic reasoning actions, searches for optimal trajectories, and trains LLMs to plan for reasoning questions.The conclusion says this enables dynamic adaptation to specific questions and the task-solving LLM’s inherent capability.Source: §5 · p. 11
  • External planner tuning and internalized planner tuning provide two paradigms for adapting DOTS to different LLMs.Source: §5 · p. 11
  • Experiments show DOTS’s effectiveness and the promise of using exploration and evaluation to turn LLMs into reasoning planners.Source: §5 · p. 11

A TRAINING IMPLEMENTATION

The implementation uses a fixed search configuration to generate planner-tuning examples, then fine-tunes the planner with specified sampling and training settings.

A TRAINING IMPLEMENTATION

  • Search uses K=2 iterations, Neval=4 evaluations, retained-path counts N1=8 and N2=3, and sampling temperature 0.4.Source: A TRAINING IMPLEMENTATION · p. 14
  • The search yields 1722 GPT-4o-mini, 1624 Llama-3-70B-Instruct, and 2140 Llama-3-8B-Instruct planner-tuning examples.Source: A TRAINING IMPLEMENTATION · p. 14
  • Planner fine-tuning uses 8× up-sampling for few-shot examples, learning rate 2e-5, batch size 64, sequence length 4096, and 4 epochs.The implementation uses the LitGPT library.Source: A TRAINING IMPLEMENTATION · p. 14

B CASE STUDY

The case study illustrates the planner selecting programming for two questions; the reported examples include different outputs from the model and the programming solver.

B CASE STUDY

  • The tuned internal planner selects programming for both the strawberry-character count and page-renumbering questions.The passage describes the first as numerical reasoning suited to Python and says the second prompted code after GPT-4o tended to err.Source: B CASE STUDY · p. 14
  • For reversed page numbering, the prose derives 5 matching pages, but the reported program execution returns 0.Source: B CASE STUDY · p. 15
  • In the “strawberry” example, GPT-4o-2024-08-06 incorrectly answered that the word contains 2 r’s, whereas after execution the result was 3.Source: B CASE STUDY · p. 16

C SUB-TASK PERFORMANCE OF BBH

BBH examples show task-dependent action selection and identify a date-understanding exception related to output formatting.

C SUB-TASK PERFORMANCE OF BBH

  • On BBH sub-tasks, the planner uses code for word sorting and requests verification for Dyck languages, where the method outperforms CoT and PoT.Source: C SUB-TASK PERFORMANCE OF BBH · pp. 16–17
  • Date understanding is the exception: choosing programming yields lower accuracy when the code fails to follow the required output format.The passage notes that Python’s datetime library can solve this task type, but formatting is often not followed.Source: C SUB-TASK PERFORMANCE OF BBH · p. 17

D PROMPTS USED IN EXPERIMENTS

The appendix supplies prompts for selecting reasoning actions and for query rewriting, decomposition, step-by-step reasoning, programming, and self-verification.

D PROMPTS USED IN EXPERIMENTS

Related papers

Loading 2410.03864v2…