PaperlayerView exact revision on arXiv

Source-linked AI summary

ToolTree: Efficient LLM Agent Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning

Shuo Yang, Soyeon Caren Han, Yihao Ding, Shuhe Wang, Eduard Hoy

arXiv:2603.12740v1cs.AI

TL;DR

LLM tool planners often lack foresight, fail to account for inter-tool dependencies, and can waste computation on brittle trajectories. ToolTree uses MCTS with pre- and post-execution LLM evaluation plus bidirectional pruning, and it consistently outperforms prior planning paradigms across four benchmarks by about 10 percent on average.

  • Problem

    Existing greedy planners make local tool choices without long-term rewards, while search variants may decouple ranking from executed-tool utility and provide weak credit to earlier decisions.

  • Method

    ToolTree is a training-free MCTS-inspired planner that combines pre-execution priors, post-execution rewards, and bidirectional pruning over tool trajectories.

  • Results

    Across four closed-set and open-set benchmarks, ToolTree consistently outperforms state-of-the-art planning paradigms by about 10 percent on average success rate.

  • Takeaways & Limitations

    ToolTree provides robust multi-tool orchestration through efficient search and discovery of high-reward tool trajectories across diverse tasks.

Abstract

from arXiv · show

Large Language Model (LLM) agents are increasingly applied to complex, multi-step tasks that require interaction with diverse external tools across various domains. However, current LLM agent tool planning methods typically rely on greedy, reactive tool selection strategies that lack foresight and fail to account for inter-tool dependencies. In this paper, we present ToolTree, a novel Monte Carlo tree search-inspired planning paradigm for tool planning. ToolTree explores possible tool usage trajectories using a dual-stage LLM evaluation and bidirectional pruning mechanism that enables the agent to make informed, adaptive decisions over extended tool-use sequences while pruning less promising branches before and after the tool execution. Empirical evaluations across both open-set and closed-set tool planning tasks on 4 benchmarks demonstrate that ToolTree consistently improves performance while keeping the highest efficiency, achieving an average gain of around 10\% compared to the state-of-the-art planning paradigm.

1 INTRODUCTION

ToolTree addresses weaknesses in greedy and existing search-based tool planning by combining forward-looking and outcome-grounded search. It evaluates and prunes tool trajectories before and after execution, then achieves strong results across four benchmark settings.

  • Motivation: Greedy planners select tools independently without long-term rewards, while early suboptimal choices can compound errors and single-trajectory search wastes computation.Existing search-based methods also evaluate hypothetical thoughts rather than executed actions, weakening credit assignment for later improvements.
  • Approach: ToolTree combines pre-execution utility prediction, post-execution contribution scoring, and complementary pruning to refine tool selection adaptively.The method uses pre- and post-scoring to eliminate unpromising branches before and after tool execution.
  • Evaluation: ToolTree is evaluated against greedy and search-based planners on four closed-set and open-set tool-use benchmarks.The evaluation targets LLM agent tool-planning ability across diverse tool scenarios.
  • Results: Around 10 percent improvement over baseline is reported, including 66.95 F1 on GTA and a 69.04 pass rate on ToolBench.These results are reported alongside state-of-the-art performance claims in the introduction.

2 PRELIMINARIES

The paper formalizes tool planning as searching for an effective sequence of tool invocations rather than selecting a single tool. It describes tree search and MCTS as frameworks for exploring candidate sequences and maximizing expected reward.

  • Tool Planning: Tool planning decides which tools to use, when to use them, and in what order to accomplish tasks efficiently and accurately.Its objective is to discover an optimal tool sequence that maximizes task success.
  • Formalization: The formal setup defines a tool library, dialogue-context state space, tool-invocation action space, and reward function for sequence quality.Tool cards provide standardized metadata, while states include accumulated intermediate results.
  • Formalization: A policy generates tool actions to maximize expected reward over the resulting sequence.The policy maps states to actions and searches or learns a sequence of admissible tool invocations.
  • Tree Search: Tree-search planning constructs states as nodes and tool actions as edges, evaluating candidate root-to-node sequences and returning the highest-value plan.Partial plans correspond to paths through the search tree, while terminal rewards estimate complete-plan value.
  • MCTS: MCTS repeatedly applies selection, expansion, simulation or evaluation, and backpropagation to balance exploration and exploitation in complex search spaces.The supplied passage introduces MCTS as a heuristic decision-making algorithm for planning and game-playing domains.

3 PROPOSED METHOD: TOOLTREE

ToolTree casts multi-tool use as MCTS over executable trajectories, integrating tool selection, execution, evaluation, and pruning in one loop. Pre-execution priors guide exploration and expansion, while post-execution rewards update values and prune branches using observed outcomes.

  • Overview: The search treats each state as evolving dialogue context and intermediate results, with actions invoking candidate tools under a fixed rollout budget.The objective is to find a trajectory maximizing task utility within the available budget.
  • Overview: ToolTree processes tool planning through iterative MCTS stages including selection, pre-evaluation, expansion, execution, post-evaluation, and backward propagation.An Answer Predictor uses the highest-reward tool trajectories to produce the final prediction.
  • Selection: Selection maximizes a prior-augmented UCT score that combines accumulated post-evaluation value with a pre-execution utility signal.Only schema-compatible actions are admissible, and the prior biases early rollouts toward promising branches while preserving exploration.
  • Pre-Evaluation and Expansion: Pre-pruning expands only actions whose predicted utility exceeds a threshold and whose tool I/O schemas are compatible with the current context.The method can further retain only the top-K predicted actions to reduce the branching factor.
  • Execution: Execution invokes the selected tool, updates the structured context with its output, reuses identical calls through caching, and records persistent failures explicitly.Caching is keyed by the tool and arguments within the current rollout.
  • Backward Propagation: Post-execution rewards are propagated backward to update visit counts and value estimates, allowing later selections to reflect observed utility.The running average of post-evaluation rewards refines the exploitation term.
  • Dual Evaluation and Pruning: ToolTree uses pre-evaluation for foresight and post-evaluation for grounded hindsight, enabling bidirectional pruning of implausible and unproductive branches.Pre-pruning acts before tool calls, while post-pruning marks low-utility executed edges non-expandable.

4 EXPERIMENTS

ToolTree is evaluated across closed-set and open-set tool-planning benchmarks using diverse baselines and efficiency analyses. It achieves strong performance across datasets while maintaining favorable accuracy–time trade-offs.

  • Experimental setup: ToolTree is evaluated on closed-set GTA and m&m tasks and open-set ToolBench and RestBench tasks.The benchmarks cover fixed typed tool sets and large API catalogs requiring retrieval, selection, and argument composition.
  • Closed-set results: 66.95 average score on GTA with GPT-4o exceeds vanilla MCTS by more than 2.2 points, while 88.61 on m&m exceeds zero-shot by more than 8 points.The same pattern holds for GPT-4o-mini with smaller but consistent margins.
  • Closed-set results: ToolTree remains on top of search-based baselines because dual evaluation prunes implausible actions before expansion and unproductive branches after execution.This concentrates computation on promising chains and improves next-action and executed-plan scores.
  • Efficiency analysis: ToolTree dominates performance at every step budget and achieves the highest accuracy-per-second, especially between 16–32 and 32–64 steps.Runtime grows near-linearly; the practical performance–time sweet spot is around 32–64 steps.
  • Open-set results: 69.04 AVG on ToolBench with GPT-4o is about 2.5 points above the strongest baseline, while 74.50 AVG on RestBench–TMDB is about 3.1 points higher.The advantage is largest when branching is high and plans span multiple calls.
  • Robustness analysis: ToolTree remains best across G1–G3 under every tested retriever, with the smallest degradation under weaker retrieval.The analysis evaluates Contriever, RoBERTa, and BM25 on ToolBench.

5 ANALYSIS

The analysis examines pruning, model scale, and representative trajectories to explain ToolTree’s efficiency and behavior. Ablations show that both evaluation stages contribute to search quality and resource control.

  • Ablation: Removing post-evaluation causes the largest accuracy drop, exceeding 7 points under the same step limits and prompts.This indicates that execution feedback is important for steering search.
  • Ablation: Removing pre-pruning reduces median expanded nodes from 95 to approximately 70 by curtailing unpromising branch explorations.The comparison is performed on GTA with GPT-4o.
  • Ablation: Removing post-evaluation pruning reduces median rollouts from 47 to approximately 33 because its rewards provide clearer solution-quality signals.The resulting signal supports earlier confident convergence.
  • Model scale: Performance scales monotonically with model size across LLaMA and Qwen on GTA and ToolBench, with the steepest gains from small to mid models.Returns diminish thereafter, and ToolBench is more size-sensitive than GTA.
  • Case study: ToolTree progressively corrects a GTA trajectory as rollouts increase, using pre-evaluation as a prior and post-evaluation as the dominant reward.The case concerns converting a photographed distance of 343 km into the requested miles.

6 RELATED WORK

Prior work includes prompt-based reactive planning and tree-search approaches for tool-using agents. ToolTree differs by making tool selection explicit in a search process with feedback from both before and after execution.

  • Tool planning for LLM agents: Prompt-based methods use LLM world knowledge and in-context strategies such as chain-of-thought and ReAct to select tools.These methods represent a major direction in dynamic tool planning.
  • Tree-search-enhanced planning: Tree-search methods add a deliberate planning layer to address reactive agents’ limitations on tasks requiring lookahead.Existing approaches include greedy search, A* Search, and related search-based methods.
  • Tree-search-enhanced planning: ToolTree contrasts with prior methods by combining explicit tree search for tool selection with dual environmental feedback for verification and plan refinement.Toolchain* is identified as a notable related work with additional comparisons provided in the appendix.

7 CONCLUSION

ToolTree is presented as a training-free, plug-and-play MCTS-based framework for multi-tool orchestration. Across four datasets spanning closed- and open-set planning, it consistently outperforms state-of-the-art planning methods by 10 percent on average success rate.

  • Conclusion: ToolTree integrates a plug-and-play MCTS-based planning module for robust multi-tool orchestration across diverse tasks.The framework is training-free and uses dual feedback with strategic pruning.
  • Conclusion: 10 percent average success-rate improvement is reported across four datasets covering closed-set and open-set tool planning.The conclusion frames ToolTree as a foundation for future tool orchestration and reasoning research.
  • Scope and ethics: The study uses public benchmarks and reports no human subjects, personally identifiable data, private user data, or production-system access.Potential risks include automation bias, model-bias amplification, and misuse of automated tool-calling.
  • Reproducibility: The paper provides detailed problem specifications, algorithms, experimental protocols, prompts, evaluator configurations, and an anonymized repository plan for reproducibility.These materials cover datasets, metrics, budgets, baselines, retrieval settings, and hyperparameters.

A.1 RESULTS ON AGENT FRAMEWORKS

Across five domains and multiple agent frameworks, ToolTree consistently achieves the strongest overall performance against prompting, orchestration, and reasoning baselines. Its gains are especially pronounced on domain-specialized and challenging tasks.

  • Cross-domain results: ToolTree outperforms Few-Shot, HuggingGPT, and OctoTools across 15 datasets in five domains with both GPT-4o-mini and GPT-4o.The evaluation covers general visual, medical, external knowledge, math, and text/document tasks.
  • Cross-domain results: 68.65% average accuracy under GPT-4o-mini exceeds Few-Shot and HuggingGPT by over 11.7 points and OctoTools by 5.71 points.With GPT-4o, the corresponding average margins exceed 11.1 points and 4.9 points.
  • Plug-and-play module comparison: ToolTree-Module achieves the highest overall average accuracy and beats COT-SC, ReAct, and ToT on four of five benchmarks across LangChain and MetaGPT.It improves by 3–8 points on each dataset and by 7 points on average over the unaugmented agent.
  • Plug-and-play module comparison: HotpotQA is the sole exception, where Tree-of-Thought excels through structured hidden-state reasoning and diverse evidence-linking pathways.ToolTree performs substantially better than internal-state search on domain-specialized tasks requiring external tools.
  • Domain breakdowns: In GPT-4o-mini Math, ToolTree reaches 63.4%, exceeding Few-Shot by 19.3%, HuggingGPT by 22.2%, and OctoTools by 11.2%.It also leads the other domains, with notable medical gains and roughly 5–7% improvements in General Visual and Text/Document tasks.
  • Few-shot baseline comparison: ToolTree improves over the GPT-4o few-shot baseline on every benchmark, with PathVQA exceeding twenty points and Game of 24 and HotpotQA reaching the mid-teens.VQA-Rad, A-OKVQA, VQAv2, and TextVQA also show positive gains.

A.5 RESULTS ON APIBENCH

ToolTree’s dual evaluation mechanism also applies to open-set tool invocation, where it identifies and prunes invalid candidates on unseen libraries without domain-specific fine-tuning.

  • APIBench applicability: ToolTree successfully identifies and prunes invalid tool candidates in zero-shot APIBench settings on completely unseen libraries.The APIBench results report AST-based accuracy and hallucination rate across HuggingFace, TensorHub, and TorchHub subsets.
  • APIBench applicability: APIBench evaluates planning strategies using AST-based overall accuracy and macro-average accuracy alongside hallucination rate across three subsets.The subsets are HuggingFace, TensorHub, and TorchHub.

A.6 ROBUSTNESS TO LLM-AS-JUDGE NOISE.

ToolTree remains effective despite noisy LLM judgments because its evaluation signals act as soft guidance rather than irrevocable decisions. More powerful post-evaluators further improve accuracy, while conservative errors are more harmful than permissive ones.

  • Limitation: ToolTree’s reliance on LLM-based pre- and post-evaluation remains a potential vulnerability despite empirical tolerance to judge noise.The restoration analysis directly quantifies this risk rather than assuming perfect judgments.
  • Judge-noise restoration: Judge error rates of 25.8% for GPT-4o and 39.4% for GPT-4o-mini produce only modest oracle gaps of at most 2.8 and 4.1 points.The restoration analysis compares false-positive correction, false-negative correction, and an oracle judge.
  • Judge-noise restoration: Correcting false negatives yields most of the improvement, indicating that overly conservative judgments are more harmful than permissive ones.ToolTree repeatedly revisits and reevaluates actions during search.
  • Judge-noise restoration: ToolTree avoids collapse under noisy judgments because bounded pre- and post-scores are aggregated across many rollouts as soft MCTS guidance.This aggregation statistically smooths isolated misjudgments instead of fixing them into a single greedy trajectory.
  • Post-evaluation model: Accuracy rises from 54.2% without post-evaluation to 60.8% with Gemini 2.0 as judge.The largest improvements occur in vision and text/document tasks, where nuanced output verification matters most.

A.9 CROSS-VENDOR CHECK ON POTENTIAL METRIC COUPLING

Cross-vendor evaluation suggests that ToolTree’s performance primarily benefits from high-quality reasoning signals rather than exploiting a particular evaluator. Separate stress tests further indicate resilience to very large tool libraries.

  • Cross-vendor judge coupling: Decoupling ToolTree’s internal judge from the external evaluator can improve performance, while using LLaMA-3.3-70B for both degrades pass rate.The cross-vendor check varies GPT-4o, Gemini-2.5-Flash, and LLaMA-3.3-70B as internal judges and GPT-4o or LLaMA-3.3-70B as evaluators.
  • Cross-vendor judge coupling: These cross-vendor patterns suggest that ToolTree benefits from higher-quality reasoning signals rather than exploiting a specific evaluator.The conclusion is supported by results across ToolBench and RestBench.
  • Tool-library scale: Performance degradation remains below 2% when distractor tools expand the library from 14 to 10,014 tools.The stress test reports average F1 and relative drop against the 14-tool baseline.
  • Tool-library scale: The pre-evaluation module filters irrelevant tools at scale because it scores semantic relevance rather than raw frequency.The authors report that fixed pruning thresholds continue to function reliably across library sizes.

B.4 MODEL AND EVALUATION PROTOCOL

The evaluation uses shared model and retrieval settings, reports closed-set and open-set metrics, and evaluates tool calls with separate pre-execution and post-execution judges. These judges score calls using task consistency, correctness, relevance, constraint satisfaction, and incremental contribution.

  • Model and task settings: All baselines use GPT-4o and GPT-4o-mini with shared APIs for closed-set tasks and fixed Top-K retrieval with K=20 for open-set tasks.Prompt formats are identical across models.
  • Evaluation metrics: Closed-set evaluation reports Tool F1, Argument F1, Plan F1, and Execution F1, while open-set evaluation reports Pass Rate and Win Rate.Open-set metrics are averaged over three instruction templates.
  • Hyperparameter setting: ToolTree uses λ = 1.4, at most Rmax = 60 roll-outs, and pre- and post-pruning thresholds of rpre < 0.3 and rpost < 0.4.Search stops early when the best Q value increases by less than 10^-3 over 10 consecutive roll-outs.
  • Pre-execution judging: The pre-execution judge scores a syntactically valid candidate call from 0.0 to 1.0 based on its expected usefulness as the next action.Its prompt includes the user query, planning context, tool card, schemas, examples, and argument draft, and prohibits simulating tool output.
  • Judging criteria: Judge prompts penalize calls that mismatch the required domain or modality, violate schemas, duplicate prior calls without benefit, or act speculatively when a more direct tool exists.The scoring guidance also considers task consistency, correctness, relevance, and constraint satisfaction.
  • Post-execution judging: The post-execution judge scores an executed call’s grounded utility from 0.0 to 1.0 using the actual arguments and raw tool output.It evaluates correctness, relevance, progress toward the final answer, and the call’s incremental contribution rather than re-evaluating the entire plan.
Loading 2603.12740v1…