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
SOTA
State-of-the-art across all 4 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.
Schematic tree of tool calls for a flight-search query: from the user query, candidate tool calls branch out with value scores, the low-scoring branches are drawn dashed as pruned, and one bold path leads to a final answer bar.
Illustrative schematic of the search over tool-call trajectories: each node is a candidate tool call scored by the value estimate, low-value branches are pruned, and the highest-reward trajectory is selected as the final plan.
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
Iterative inferencing on a road-sign query asking for the distance in miles: early iterations read the kilometre figure off the sign and return it unchanged for a low post-evaluation reward; later iterations add retrieval and unit-conversion tools, the reward rises, and the final iteration answers in miles.

The query asks how many miles the journey is, while the road sign in the image gives the distance in kilometres. In early iterations the agent simply reads the kilometre figure off the sign and returns it unchanged, earning a low post-evaluation reward. Across later iterations the search brings in retrieval and unit-conversion tools, the post-evaluation reward rises, and the final trajectory converts the distance and answers in miles.

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}
}