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

Shuo Yang, Caren Han, Yihao Ding, Shuhe Wang, Eduard Hovy

The University of Melbourne · The University of Western Australia

ICLR 2026

~10%
Average gain over existing methods
Across both closed-set and open-set tool planning scenarios
4 / 4
State-of-the-art on all four benchmarks
GTA · m&m · ToolBench · RestBench
#1
Highest efficiency (performance gain per second)
Compared with all baselines across step limits

Overview

ToolTree is a novel Monte Carlo tree search-inspired planning paradigm for LLM agent tool planning. It 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.

Concept comparison on a street photo asking how many wheels are in total: greedy-based planning commits to a single tool chain and answers incorrectly; search-based planning explores more tool branches but still returns a wrong count; ToolTree prunes branches before (pre-pruning) and after (post-pruning) execution and answers correctly.
Comparison of ToolTree with greedy search and search-based tool planning. ToolTree chooses the optimal tool trajectory and answers correctly with bidirectional pruning.

Efficiency

Three line charts across step limits comparing ReAct, Best-first, ToT, LATS, and ToolTree: performance versus step limit, running time versus step limit, and efficiency (performance gain per second) versus step limit — ToolTree sits highest on the performance and efficiency panels at every step limit.
Figure 3: Progressive efficiency analysis across step limits. ToolTree achieves the highest efficiency (performance gain per second) compared with all baselines.

Method

ToolTree pipeline: an input query enters a repeated loop over the tool tree — selection, pre-evaluation of a candidate tool against a threshold before execution, expansion, execution, post-evaluation of the observed output, and backward-propagation — after which the answer predictor produces the final answer.
Architecture overview of ToolTree. An input query is processed sequentially via iterative dual evaluation-guided Monte Carlo Tree Search, including selection, pre-evaluation, expansion, execution, post-evaluation and backward-propagation.
Search tree reconstructed from a logged 11-rollout run: from the user query on the left, candidate tool calls branch rightward with pre- and post-evaluation score badges; pre-pruned drafts are dashed with a cross, a failed call is post-pruned in red, duplicate drafts are shown as skipped, and the bold path leads to the final answer bar.
Search over tool-call trajectories on a real logged run (11 rollouts): each node is a candidate tool call with its pre-/post-evaluation scores, pruned and duplicate drafts are shown as encountered, and the highest-reward trajectory (bold) is selected as the final plan. Click to view full size.
1

Pre-Evaluation

A fast predictive signal that estimates the utility of a tool before execution, filtering schema- or slot-incompatible calls before expansion.

2

Post-Evaluation

Assesses the actual contribution of a tool after execution based on observed outcomes, pruning unproductive branches using real feedback.

3

Bidirectional Pruning

Combines pre- and post-evaluation to eliminate unpromising branches, concentrating computational budget on promising tool chains.

4

Answer Predictor

Incorporates the tool trajectories with the highest reward found by the MCTS to produce the final prediction.

Case Study

Qualitative case studies from the paper
Case study (a): a radiology image question about lung cancer risk — greedy search relies on generic image captioning and heuristic search on shallow heuristics, both missing the finding, while the MCTS-planned trajectory orchestrates domain-specific imaging tools and detects the risk. Case study (b): a multi-hop knowledge reasoning question about the building seen behind an amusement area — greedy search and heuristic search answer from broad scene cues and the most prominent text, while the MCTS-planned trajectory chains recognition and search tools to identify the building correctly.
Two qualitative case studies showcasing ToolTree’s iterative tool orchestration on (a) a radiology image question and (b) a multi-hop knowledge reasoning task.

Results

ToolTree achieves state-of-the-art performance across 4 benchmarks spanning both closed-set and open-set tool planning scenarios, with an average gain of ~10% over existing methods.

BenchmarkSettingTasks & ToolsOfficial source
GTAClosed-set229 real-world tasks, 14 executable toolsopen-compass/GTA · HF dataset
m&mClosed-set882 human-verified multi-step multimodal tasks, 33 toolsRAIVNLab/mnms · HF dataset
ToolBenchOpen-set16,464 real-world REST APIs (RapidAPI)OpenBMB/ToolBench
RestBenchOpen-setTMDB & Spotify REST scenariosYifan-Song793/RestGPT

This repository ships no benchmark data; each benchmark is downloaded from its official source.

Pruning Ablation

Two box plots comparing ToolTree against variants without pre-pruning, without post-pruning, and without both: the number of rollouts and the number of expanded nodes are lowest for full ToolTree and grow as pruning stages are disabled.

Disabling pre-pruning, post-pruning, or both consistently increases the number of rollouts and expanded nodes, confirming that bidirectional pruning concentrates the computational budget on promising tool chains.

BibTeX

@inproceedings{yang2026tooltree,
title={ToolTree: Efficient {LLM} Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning},
author={Shuo Yang and Caren Han and Yihao Ding and Shuhe Wang and Eduard Hovy},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=Ef5O9gNNLE}
}