Skip to content

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

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

MCTS with dual feedback and bidirectional pruning for LLM tool planning

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ToolTree is an MCTS-inspired tool planning framework for LLM agents that uses dual-feedback evaluation (pre-execution scoring and post-execution grounded scoring) combined with bidirectional pruning to efficiently navigate multi-step tool-use trajectories. It achieves ~10% average improvement over state-of-the-art planning baselines across four benchmarks while maintaining the best accuracy-per-compute trade-off.

Problem

Greedy tool planners (ReAct, CoT) lack foresight and propagate early errors irreversibly. Search-based methods (ToT, A*, LATS) suffer from exponential branching over tool types/arguments and decouple evaluation from actual execution, producing rankings based on hypothetical thoughts rather than grounded outcomes—leading to poor credit assignment and high token cost.

Method

ToolTree frames tool planning as an MCTS over executable trajectories with a fixed rollout budget \(R_{max}\). The algorithm integrates six phases: Selection, Pre-Evaluation, Expansion, Execution, Post-Evaluation, and Backward Propagation.

Selection uses a prior-augmented UCT score: $\(\text{UCT}(s, a) = Q(s, a) + \lambda \, r_{\text{pre}}(s, a) \sqrt{\frac{\ln N(s)}{N(s, a)}}\)$ where \(r_{\text{pre}}(s, a) \in [0,1]\) is an LLM-judge pre-execution score that biases early rollouts toward promising branches.

Pre-Evaluation + Pre-Pruning: An LLM judge scores each candidate action before execution; only actions with \(r_{\text{pre}} \geq \tau_{\text{pre}}\) (top-\(K\) of admissible actions) are expanded, reducing the branching factor.

Execution: The selected tool is invoked with schema-valid arguments; outputs are deterministically cached by (action, args) to avoid redundant API calls.

Post-Evaluation + Post-Pruning: After execution, the same LLM judge computes \(r_{\text{post}}(s, a) = J(C_t, a, o_{t+1}) \in [0,1]\) on the actual tool output. Edges with \(r_{\text{post}} < \tau_{\text{post}}\) are marked non-expandable. This score drives backward propagation via a running mean update: $\(Q(s,a) \leftarrow Q(s,a) + \frac{r_{\text{post}}(s_t,a) - Q(s,a)}{N(s,a)}\)$

The bidirectional pruning (pre + post) concentrates the rollout budget on branches that are both plausible (per \(r_{\text{pre}}\)) and useful (per \(r_{\text{post}}\)).

Key Contributions

  • MCTS-inspired tool planning paradigm integrating pre- and post-execution LLM evaluation directly into the search loop, requiring no task-specific retraining.
  • Bidirectional pruning mechanism: pre-pruning reduces expansion branching factor; post-pruning cuts unproductive branches using real execution feedback.
  • Deterministic caching of tool outputs within rollouts to avoid duplicate API calls.
  • Evaluation across 4 benchmarks (GTA, m&m, ToolBench, RestBench) spanning closed-set and open-set tool planning with both GPT-4o and GPT-4o-mini backends.
  • Retriever-agnostic robustness demonstrated across Contriever, RoBERTa, and BM25.

Results

  • GTA (GPT-4o, end-to-end): ToolTree achieves 66.95 AVG F1, vs. LATS 64.78, A* 62.52, MCTS baseline ~64.5; +2.2 over vanilla MCTS.
  • m&m (GPT-4o): 88.61 AVG, vs. LATS 86.45, A* 84.74; +8 over zero-shot.
  • ToolBench (GPT-4o): 69.04 AVG (pass+win), vs. LATS 66.55 (+2.5).
  • RestBench-TMDB (GPT-4o): 74.50 AVG, vs. LATS 71.35 (+3.1).
  • Ablation (GTA, GPT-4o): Removing post-evaluation drops accuracy >7 points (76.44→68.94); removing both pruning raises token cost from 18.2k to 24.1k tokens.
  • Efficiency: ToolTree yields the highest accuracy-per-second at all step budgets; practical sweet spot is 32–64 steps.
  • Scalability: Performance scales monotonically with backbone model size (LLaMA and Qwen families tested).

Limitations

  • LLM-judge quality for dual evaluation is not guaranteed; weak judges may misassign \(r_{\text{pre}}\) or \(r_{\text{post}}\), and robustness to judge errors is only partially analyzed (Appendix A.6).
  • Runtime is slower than greedy methods (ReAct, Best-First), comparable to ToT but below LATS—not suitable for latency-critical settings without budget tuning.
  • Pre- and post-pruning thresholds (\(\tau_{\text{pre}}\), \(\tau_{\text{post}}\), top-\(K\)) require tuning; sensitivity analysis is not fully reported in the main paper.
  • Evaluation uses GPT-4o/4o-mini as both backbone and judge, risking self-evaluation bias; the paper does not assess cases where the backbone and judge are different models.
  • The paper is truncated before discussing scalability limits beyond 10,014 tools (Appendix A.10).

Relevance to Agentic AI / LLM Agents

ToolTree directly addresses one of the core bottlenecks in LLM agent design: efficient multi-step tool orchestration under a compute budget. By grounding the MCTS value signal in executed tool outputs rather than hypothetical thought evaluations, it advances the principle that agentic search should be tightly coupled to environment feedback—a lesson applicable broadly to web, code, and API agents. The bidirectional pruning approach offers a practical template for controlling exponential branching in large tool libraries without retraining, making it directly relevant to tool-augmented agents, API orchestration systems, and any agent that must compose heterogeneous external capabilities. The work also highlights that post-execution credit assignment is the dominant signal (>7-point drop on ablation), informing how future MCTS-based agent frameworks should weight hindsight over foresight.