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

cs.AIMar 13, 2026

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

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

Organizations: School of Computing and Information Systems, The University of Melbourne · School of Physics, Mathematics and Computing, The University of Western Australia

Abstract

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.

Figures & tables

Figure 1: Comparison of ToolTree with greedy search and search-based tool planning. Our ToolTree chooses the optimal tool trajectory and answers correctly with 20.

Figure 2: 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. The Answer Predictor then incorporates the tool trajectories with the highest reward found by the MCTS to produce the final prediction.

Model	Planner	GTA					m&m
		Step-by-step		End-to-End		AVG	Step-by-step		Multi-step		AVG
		Tool	Arg	Plan	Exec	AVG	Tool	Arg	Plan	Exec	AVG
GPT-4o-mini	Zero-Shot	58.73	28.44	60.18	33.85	45.30	72.48	67.44	77.48	67.59	71.25
	ReAct	60.13	29.43	68.26	34.80	48.16	73.55	65.10	82.16	69.42	72.56
	CoT	56.10	25.58	66.47	35.63	45.95	70.13	65.27	76.12	66.96	69.62
	Best–First	58.42	30.13	69.96	34.46	47.99	74.42	66.83	83.58	68.37	73.80

Table 1: Comparison of ToolTree with other baselines across GTA and m&m. The experiment is carried out under both step-by-step and end-to-end mode. ”Tool” stands for tool selection F1 score; ”Arg” stands for argument prediction F1 score; ”Plan” and ”Exec” stand for planning and execution F1 score. Ours achieves the best performance overall.

Figure 3: Progressive efficiency analysis across step limits. (a) Performance vs. step limit ; (b) Runtime vs. step limit ; (c) Efficiency vs. step limit . ToolTree achieves the highest efficiency compared with baselines. mprovements are largest for step limits between 12 and 64.

Model	Method	RestBench–TMDB			RestBench–Spotify			ToolBench
Model	Method	Pass	Win	AVG	Pass	Win	AVG	Pass	Win	AVG
GPT-4o-mini	Zero-shot	33.28	50.00	41.64	26.44	50.00	38.22	28.85	50.00	39.42
	CoT	34.42	54.70	44.56	29.82	53.10	41.46	26.29	55.47	40.88
	ReAct	38.82	61.06	49.94	32.64	59.95	46.30	34.30	58.94	46.62
	DFSDT	46.20	64.26	55.23	35.10	65.47	50.28	38.84	68.29	53.57
	LATS	51.33	66.67	59.00	39.81	72.85	56.33	40.08	65.77	52.92

Table 2: Open-set tool-planning results on RestBench and ToolBench using GPT-4o-mini and GPT-4o as back-end LLMs. Higher values indicate better performance; the best score for each dataset-model pair is highlighted in bold. ”Pass” and ”Win” refer to pass rate and win rate.

Retriever	Method	G1	G2	G3
Contriever	ReAct	61.0	78.0	72.5
	ToT	62.8	79.6	75.2
	Ours	64.5	81.8	78.3
RoBERTa	ReAct	60.5	76.5	73.0
	ToT	63.0	80.0	76.2
	Ours	66.0	83.0	82.8

Table 4: Retriever ablation on ToolBench.

Figure 5: Analysis of Performance with respect to model size on Qwen and LLaMA family.

Figure 6: A Sample Case of ToolTree on GTA.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Domain	Dataset	GPT-4o-mini				GPT-4o
Domain	Dataset	Few-Shot	HuggingGPT	OctoTools	ToolTree (Ours)	Few-Shot	HuggingGPT	OctoTools	ToolTree (Ours)
General Visual	VQAv2	68.82	60.17	69.28	74.47	73.22	67.77	74.18	76.43
	GQA	63.80	65.13	66.14	71.54	66.84	60.33	68.58	74.44
	SQA	76.50	70.82	78.29	84.28	82.15	78.45	84.13	87.33
Medical	MedQA	79.14	84.33	86.18	91.13	83.20	86.73	92.17	93.88
	VQA-Rad	48.10	55.14	60.10	63.27	54.47	58.88	66.42	74.12

Appendix

Table 6: Comparison across 15 datasets in five domains. ToolTree consistently outperforms standard few-shot prompting, HuggingGPT, and OctoTools on both GPT-4o-mini and GPT-4o, achieving highest overall score.

Configuration	VQA-Rad	OK-VQA	MathVista	SQA	HotpotQA	AVG
LangChain	62.18	49.18	54.24	76.59	39.82	56.40
w/o COT-SC	65.14	54.37	56.88	82.17	44.90	60.69
w/o ReAct	66.28	52.33	59.25	80.95	45.18	60.80
w/o ToT	63.04	48.12	65.33	78.33	52.28	61.42
w/o ToolTree	67.72	54.27	65.74	81.33	51.94	64.20
MetaGPT	64.13	53.84	54.88	78.16	37.72	57.75

Appendix

Table 7: Comparison of ToolTree as a plug-and-play module with ReAct, COT-SC and ToT modules. ToolTree achieves highest score on average.

Figure 7: Breakdown comparison for each of the domains.

Figure 8: Breakdown comparison with the few-shot baseline setup under GPT-4o-mini.

Backbone	Method	HuggingFace	TensorHub	TorchHub	Avg. Acc. (%)	Avg. Hallu. (%)
GPT-4o-mini	Zero-shot	68.4	59.2	44.5	57.4	22.1
	ReAct	69.8	61.5	47.2	59.5	18.5
	Tree-of-Thought	71.2	62.8	49.6	61.2	9.3
	ToolTree (Ours)	73.5	65.4	53.1	64.0	7.4
GPT-4o	Zero-shot	76.5	69.8	62.3	69.5	7.8
	ReAct	77.2	71.0	63.5	70.6	5.1

Appendix

Table 8: APIBench results (BM25 retriever) for GPT-4o and GPT-4o-mini with different planning strategies. We report AST-based overall accuracy (%) on HuggingFace, TensorHub, and TorchHub, as well as the macro-average accuracy and hallucination rate across the three subsets.

Backbone	Configuration	Judge error rate	Task success (%, $\Delta$ )
GPT-4o	ToolTree (baseline)	25.8%	51.9% (—)
	+ Fix false positives	7.4%	52.5% (+0.6)
	+ Fix false negatives	18.4%	54.1% (+2.2)
	Oracle (perfect judge)	0.0%	54.7% (+2.8)
GPT-4o-mini	ToolTree (baseline)	39.4%	49.5% (—)
	+ Fix false positives	16.3%	50.8% (+1.3)

Appendix

Table 9: Restoration analysis of LLM-judge errors on ToolBench. “Judge error rate” is the fraction of incorrect pre-/post-evaluation decisions. “Task success” is the overall pass rate;

\Delta

denotes the absolute difference (in percentage points) relative to the actual ToolTree baseline for each backbone.

Figure 9: Effect of different LLM for post evaluation.

Internal judge	Benchmark evaluator	ToolBench	RestBench
GPT-4o	GPT-4o	69.04	72.48
Gemini-2.5-Flash	GPT-4o	72.71	73.12
LLaMA-3.3-70B	GPT-4o	46.48	50.17
LLaMA-3.3-70B	LLaMA-3.3-70B	38.11	41.64

Appendix

Table 10: Cross-vendor / cross-judge robustness of ToolTree on ToolBench and RestBench (pass rate %). We vary the internal judge used during planning and the external benchmark evaluator.

Panel of Figure 10 — Figure 10: Two qualitative case studies showcasing ToolTree’s iterative tool orchestration on (a) a radiology image question and (b) a multi-hop knowledge reasoning task.

Added distractors	Total tools	Selection strategy	Avg. F1 (%)	Rel. drop
0 (baseline)	14	Direct context	55.89	/
+10	24	Direct context	55.74	$-0.15\%$
+100	114	Retrieval (Top-20)	55.15	$-0.74\%$
+1,000	1,014	Retrieval (Top-20)	54.82	$-1.07\%$
+10,000	10,014	Retrieval (Top-20)	54.27	$-1.62\%$

Appendix

Table 11: Stress test on tool library size. We start from a 14-tool baseline and progressively add distractor tools. “Avg. F1” denotes average task performance, and “Rel. drop” is the relative performance decrease compared to the 14-tool baseline.

Field	Type	Description / Example
tool_name	string	"Medical_Object_Detection"
description	string	A tool that detects the organs within a given medical image, such as CT, MRI, X-Ray and pathology images.
input	image: str	Path to the image file (e.g. "lung_cancer_Image.png" )
input	prompt: str	Prompt to guide detection (default: “Detect the organs in the given image.”)
output	dict	Detected organs with their bounding box, organ name, and confidence score.
example	input	{ "lung_cancer_Image.png" }

Appendix

Table 12: Metadata schema for the Medical_Object_Detection tool.

Explore similar work

PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems
Jun 21, 2026Jiayu Liu, Qihan Lin, Cheng Qian +8Long-Horizon Agent Evaluation AI Agent Benchmarks
University of Illinois Urbana-Champaign
HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agents
Jul 31, 2026Zian Zhai, Xingyu Tan, Gaowang Zou +2LLM Tool Use Graph-Based Planning
University of New South Wales
Long-Horizon Plan Execution in Large Tool Spaces through Entropy-Guided Branching
Apr 13, 2026Rongzhe Wei, Ge Shi, Min Cheng +5LLM Agent Planning Long-Horizon LLM Agents
Georgia Institute of Technology · Amazon

Jun 21, 2026J/K move · Enter open · S save

PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems

Jiayu Liu, Qihan Lin, Cheng Qian, Rui Wang+7

University of Illinois Urbana-Champaign

Long-Horizon Agent Evaluation AI Agent Benchmarks LLM Agent Planning LLM Agent Reliability

Open paper AskPDF arXiv

LLM agents increasingly operate in large tool ecosystems, where real-world tasks require discovering relevant tools, inferring implicit sub-goals, and adapting to dynamic environments over long horizons. However, existing benchmarks rarely evaluate planning under retrieval-limited tool visibility. To address this gap, we introduce PlanBench-XL, an interactive benchmark of 327 retail tasks over 1,665 tools that tests whether agents can iteratively retrieve usable tools, invoke them to uncover intermediate evidence for subsequent calls toward the final goal. PlanBench-XL further features an optional blocking mechanism that simulates real-world unpredictability through missing, failing, or distracting tool functions, forcing agents to detect disrupted paths and adapt at runtime. Experiments on ten leading LLMs show that massive-tool planning remains challenging: while GPT-5.4 achieves 51.90% accuracy in block-free settings, it collapses to 11.36% under the most severe blocking condition. Further analysis shows that agents are especially vulnerable when failures lack explicit error signals or when recovery requires longer alternative tool-use paths. These results establish PlanBench-XL as a testbed for diagnosing agentic planning failures and highlight the need for robust adaptive planning in long-horizon tasks with large, imperfect tool environments.

Abstract

Explore similar work

PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems

HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agents

Long-Horizon Plan Execution in Large Tool Spaces through Entropy-Guided Branching