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

Rongzhe Wei; Ge Shi; Min Cheng; Na Zhang; Pan Li; Sarthak Ghosh; Vaibhav Gorde; Leman Akoglu

cs.AIApr 13, 2026

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

Authors: Rongzhe Wei, Ge Shi, Min Cheng, Na Zhang, Pan Li, Sarthak Ghosh, Vaibhav Gorde, Leman Akoglu

Organizations: Georgia Institute of Technology · Amazon

Abstract

Large Language Models (LLMs) have significantly advanced tool-augmented agents, enabling autonomous reasoning via API interactions. However, executing multi-step tasks within massive tool libraries remains challenging due to two critical bottlenecks: (1) the absence of rigorous, plan-level evaluation frameworks and (2) the computational demand of exploring vast decision spaces stemming from large toolsets and long-horizon planning. To bridge these gaps, we first introduce SLATE (Synthetic Large-scale API Toolkit for E-commerce), a large-scale context-aware benchmark designed for the automated assessment of tool-integrated agents. Unlike static metrics, SLATE accommodates diverse yet functionally valid execution trajectories, revealing that current agents struggle with self-correction and search efficiency. Motivated by these findings, we next propose Entropy-Guided Branching (EGB), an uncertainty-aware search algorithm that dynamically expands decision branches where predictive entropy is high. EGB optimizes the exploration-exploitation trade-off, significantly enhancing both task success rates and computational efficiency. Extensive experiments on SLATE demonstrate that our dual contribution provides a robust foundation for developing reliable and scalable LLM agents in tool-rich environments.

Figures & tables

Figure 1: Overview of the Entropy-Guided Branching (EGB) framework. Phase 1 iterates over a fixed plan, using an entropy estimation module (black-box sampling or white-box logit-based) to quantify tool selection uncertainty at each step and execute the majority-voted tool. If the final output does not match the reference, Phase 2 branches at high-entropy steps in descending order, substituting alternative tools from the Phase 1 vote distribution and re-executing downstream steps with updated observations. Tool execution results are produced by a deterministic simulator to enable exact-match success evaluation.

Benchmark	Large Tool Spaces (1,000+ Tools)	Long-Horizon Execution (10+ Steps)	Step-wise Deterministic Outcomes	Plan-Level Grounded Evaluation
SLATE (Ours)	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
TRAJECT-Bench ( He et al., 2025 )	$\checkmark$	$\checkmark$	$\checkmark$	$\times$
Toolathlon ( Li et al., 2026a )	$\times$	$\checkmark$	$\checkmark$	$\checkmark$
ToolLLM ( Qin et al., 2023 )	$\checkmark$	$\times$	$\checkmark$	$\times$
Gorilla ( Patil et al., 2024 )	$\checkmark$	$\times$	$\checkmark$	$\times$
UltraTool ( Huang et al., 2024 )	$\checkmark$	$\times$	$\times$	$\times$

Table 1: Comprehensive Comparison of Agent Tool-Call Datasets.

Figure 2: Illustration of the SLATE dataset structure.

Total Tools	1000	Relevant Tools in Plans	253
Avg. Arguments/Tool	3.05	Avg. Calls/Tool	6.30

Table 2: SLATE Dataset Statistics

Figure 3: SLATE Tool Library category distribution.

Figure 4: Comparison of different paradigms.

Method	Plan-level	Step-wise
Method	Execution Success Rate	Tool Match Rate	Action Identification Accuracy
Baseline-LLM	$\backslash$	65.2 $\pm$ 0.8	$\backslash$
ReAct	29.3 $\pm$ 1.2	66.4 $\pm$ 0.4	85.7 $\pm$ 0.1
Reflexion	44.7 $\pm$ 2.3	61.5 $\pm$ 1.6	83.4 $\pm$ 0.5
LATS	36.5 $\pm$ 2.5	63.4 $\pm$ 1.3	87.3 $\pm$ 0.5
EGB-Sampling (Ours)	54.0 $\pm$ 2.0	68.5 $\pm$ 1.5	87.9 $\pm$ 0.2

Table 3: Evaluation of search methods on the SLATE synthetic dataset with Claude-Sonnet-4.

Method	Plan-level	Step-wise
Method	Execution Success Rate	Tool Match Rate	Action Identification Accuracy
Baseline-LLM	$\backslash$	23.2 $\pm$ 0.7	$\backslash$
ReAct	29.3 $\pm$ 1.2	30.0 $\pm$ 0.5	78.2 $\pm$ 0.4
Reflexion	44.2 $\pm$ 2.1	25.2 $\pm$ 0.7	82.9 $\pm$ 2.9
EGB-Sampling (Ours)	51.3 $\pm$ 6.0	33.6 $\pm$ 2.4	83.0 $\pm$ 0.6
EGB-Logits (Ours)	67.8 $\pm$ 4.5	36.4 $\pm$ 0.8	85.1 $\pm$ 0.4

Table 4: Evaluation of search methods on the SLATE synthetic dataset with Qwen2.5-7B-Instruct.

	Claude-Sonnet-4	Qwen2.5-7B-Instruct
Method	Running Time (seconds)	Running Time ∗ (seconds)	Input Tokens	Output Tokens	LLM Invokes
Baseline-LLM	77	138	$1.83\times 10^{5}$	$3.8\times 10^{3}$	32.0
ReAct	195	150	$1.95\times 10^{5}$	$4.0\times 10^{3}$	32.0
Reflexion	766	707	$8.90\times 10^{5}$	$2.41\times 10^{4}$	122.2
LATS	620	$\backslash$	$\backslash$	$\backslash$	$\backslash$
EGB-Logits (Ours)	$\backslash$	254	$(1.61+4.86)\times 10^{5}$ †	$6.4\times 10^{3}$	44.6 + 149.6 †

Table 5: Comparison of computational cost per case across different search methods on SLATE synthetic dataset.

Entropy Range	#Steps	#Errors	Error Rate
$[0.000,0.640)$	365	184	50.7%
$[0.640,1.281)$	116	79	68.1%
$[1.281,1.921)$	67	52	77.6%
$[1.921,2.561)$	21	20	95.2%
$[2.561,3.202]$	15	14	93.3%

Table 6: Entropy-error relationship on SLATE using EGB-Logits.

Figure 5: Cross-benchmark validation on adapted UltraTool with GPT-OSS-120b.

Figure 6: Evaluation of EGB search with Claude-Sonnet-4 on the SLATE synthetic dataset with varied configurations: (a) number of samplings,

m

, used to estimate entropy, and (b) budget,

b

, as the maximum number of branch trials.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: Example of plan generation and tool execution.

Panel of Figure 8 — Figure 8: Deterministic simulation dictionary for tool calls.

Method	Plan-level	Step-wise Evaluation
Method	Execution Success Rate	Tool Match Rate	Action Identification Accuracy
ReAct	29.3 $\pm$ 1.2	66.4 $\pm$ 0.4	85.7 $\pm$ 0.1
Reflexion	44.7 $\pm$ 2.3	61.5 $\pm$ 1.6	83.4 $\pm$ 0.5
EGB-Sampling (Ours)	54.0 $\pm$ 2.0	68.5 $\pm$ 1.5	87.9 $\pm$ 0.2
ReAct-with-Memory	86.3 $\pm$ 0.6	92.7 $\pm$ 0.3	98.7 $\pm$ 0.1
Reflexion-with-Memory	91.0 $\pm$ 1.5	92.7 $\pm$ 1.1	98.4 $\pm$ 0.3

Appendix

Table 7: Evaluation of search methods with vs. without memory on the SLATE synthetic dataset with Claude-4-Sonnet.

Entropy Range	#Steps	#Errors	Error Rate
$[0.000,0.640)$	365	184	50.7%
$[0.640,1.281)$	116	79	68.1%
$[1.281,1.921)$	67	52	77.6%
$[1.921,2.561)$	21	20	95.2%
$[2.561,3.202)$	15	14	93.3%

Appendix

Table 8: Entropy-error relationship on SLATE using Qwen-logits.

Methods	Execution Success Rate	Input Tokens	Output Tokens
DirectLLM	67.3 $\pm$ 4.7	$2.65\times 10^{4}$	$7.17\times 10^{2}$
ReAct	69.0 $\pm$ 2.0	$2.87\times 10^{4}$	$8.68\times 10^{2}$
Self-Consistency	69.3 $\pm$ 1.3	$2.87\times 10^{5}$	$8.65\times 10^{3}$
Reflexion	77.3 $\pm$ 3.7	$1.56\times 10^{5}$	$4.85\times 10^{3}$
EGB-Sampling	79.7 $\pm$ 0.7	$1.69\times 10^{5}$	$5.36\times 10^{3}$
EGB-Logits	82.0 $\pm$ 1.0	$3.75\times 10^{4}$	$1.79\times 10^{3}$

Appendix

Table 9: Evaluation of different methods on adapted UltraTool with GPT-OSS-120b.

Methods	Accurate Plan	Inaccurate Plan
ReAct	69.0 $\pm$ 2.0	65.0 $\pm$ 5.0
Self-Consistency	69.3 $\pm$ 1.3	65.3 $\pm$ 0.7
EGB-Sampling	79.7 $\pm$ 0.7	72.0 $\pm$ 2.0

Appendix

Table 10: Execution success rate under accurate vs. inaccurate plans on adapted UltraTool with GPT-OSS-120b.

Panel of Figure 9 — Figure 9: Prompt to generate diverse e-commerce cases from different user perspectives. Example Variable Values: user_type alternates between “buyer” and “seller” based on query ID; focus is randomly selected from buyer focus areas (“product search with multiple conflicting requirements”, “order tracking for multiple items with shipping complications”, “complex product return with partial refund request”, etc.) or seller focus areas (“updating complex product variations and attributes”, “inventory management across multiple warehouses”, “implementing tiered pricing strategy with conditions”, etc.); complexity is one of “SIMPLE”, “MODERATE”, “COMPLEX”, or “ADVANCED” with weighted distribution of 0%, 10%, 80%, 10% respectively.

Panel of Figure 10 — Figure 10: Prompt for creating specialized tool plans (Part 1). Example Variable Values: user_type is either “buyer” or “seller”; complexity is one of “SIMPLE”, “MODERATE”, “COMPLEX”, or “ADVANCED”; query is the actual query text generated in stage 1. existing_tools_text: Dynamically generated list of top 30 most relevant tools from global tool library. plan_requirements: SIMPLE (2-3 high-level steps, 1-2 substeps each, 3-5 total); MODERATE (3-4 high-level steps, 1-3 substeps each, 6-8 total); COMPLEX (4-5 high-level steps, 2-3 substeps each, 8-12 total); ADVANCED (5-7 high-level steps, 2-4 substeps each, 12-16 total).

Panel of Figure 11 — Figure 11: Prompt for creating specialized tool plans (Part 2). Focus on tool selection, reuse strategy, avoiding repetition, and establishing sequential dependencies between steps.

Panel of Figure 12 — Figure 12: Prompt for creating specialized tool plans (Part 3). Format response as JSON object with “plan” array (high-level steps with “tool”: “null”, and substeps with tool calls or “No tool required”) and “tools” array (defining all tools with “name”, “description”, “arguments”, and “results” fields). Complexity Guidelines: SIMPLE (1-2 tool calls, linear, minimal dependencies); MODERATE (2-4 tool calls, at least one dependency and conditional step); COMPLEX (4-7 tool calls, multiple dependencies, validation, branching paths); ADVANCED (7+ tool calls, multi-stage workflow, complex dependencies, edge case handling, maximum tool diversity).

Panel of Figure 13 — Figure 13: Prompt for generating diverse e-commerce tools with unique names. Example Variable Values: batch_size is configurable (typically 10 or 20, default 10). names_str is a comma-separated string of 20 random existing tool names to avoid duplication (e.g., “get_order_details, validate_return_window, calculate_refund, search_products, update_inventory, generate_shipping_label, process_payment, send_notification, track_shipment, analyze_sales, manage_promotions, verify_address, calculate_tax, check_stock, create_invoice, update_customer, generate_report, schedule_delivery, process_return, validate_coupon”). name_pattern_text consists of 4 randomly selected naming patterns from: “feature_specific_domain, domain_specific_action, specialized_task_handler, domain_analyzer, action_target_generator, domain_insight_provider, specialized_workflow_automation, target_specific_optimizer”. domains_text is a numbered list of specific domains (one per tool) from 100 predefined diverse domains covering: Product management (catalog, variants, bundling, photography assessment, competitive analysis, recommendations, sourcing, limited editions, warranties, etc.), Shipping & logistics (delivery, warehousing, returns, tracking, etc.), etc. sample_tool is a randomly selected existing tool or default structure containing: name , description , query_id , arguments (with type, properties, and argument details), and results (with type, properties, and result field details).

Panel of Figure 14 — Figure 14: Prompt for categorizing e-commerce tools into functional domains. Example Variable Values: batch_tools is a batch of 10-20 tools to categorize, each containing name , description , arguments , and results fields (e.g., “get_order_details”, “calculate_shipping_cost”, etc.). self.categories is a predefined list of 15 functional domain categories: “Order Management”, “Product Management”, “Inventory Management”, “Shipping & Logistics”, “Payment Processing”, “Customer Management”, “Returns & Refunds”, “Pricing & Promotions”, “Analytics & Reporting”, “Search & Discovery”, “Reviews & Ratings”, “Notifications & Communication”, “Authentication & Security”, “Marketplace Integration”, and “Content Management”.

Panel of Figure 15 — Figure 15: Prompt for generating tool simulation outputs. Example Variable Values: context[’query’] is the original e-commerce query text; context[’step’] is the current step description from the plan; tool_name is the name of the tool being called; tool_def is the tool definition object containing description and other metadata; args is a JSON object containing the arguments passed to the tool; context[’previous_outputs’] is a JSON object or array containing outputs from previously executed tools (null or empty if no previous outputs); result_props is a JSON schema object defining required output properties with types and descriptions; example_output is a sample JSON object showing the expected output format; complexity is one of “SIMPLE”, “MODERATE”, “COMPLEX”, or “ADVANCED”; complexity_guidance is text providing specific guidance for generating outputs at the given complexity level; is_final_step is a boolean indicating whether this tool is the final step in the plan (affects instruction 5).

Explore similar work

Jun 21, 2026

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

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.

Jiayu Liu, Qihan Lin, Cheng Qian +8

University of Illinois Urbana-Champaign

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

Ask PDF

Mar 13, 2026

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

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.

Shuo Yang, Soyeon Caren Han, Yihao Ding +2

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

Tool-Use Planning Tree Search Monte Carlo Tree Search

Ask PDF

Jun 3, 2026

Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents

Planning is central to LLM agents: before acting, an agent must decompose goals, select tools, reason over constraints, and decide when a task is infeasible. Yet existing agent evaluations often report only end-to-end success, making it difficult to determine whether failures stem from planning or execution. We introduce Agent Planning Benchmark (APB), a planning-specific diagnostic benchmark with 4,209 multimodal cases across 22 domains and five settings, covering holistic planning, feedback-conditioned step-wise planning, and robustness under extraneous tools, broken tools, and unsolvable tasks. Across 12 MLLMs, APB reveals systematic weaknesses in long-horizon planning, tool-noise robustness, calibrated refusal, and inference-time refinement. We further validate APB on 200 ToolSandbox tasks and 200

τ^2

-bench tasks, where APB-guided refinement consistently improves plan correctness, plan grade, and downstream execution metrics across three representative models. APB thus serves as an upstream diagnostic complement to execution benchmarks. The APB benchmark and code are available in this URL.

Haoyu Sun, Wenxuan Wang, Mingyang Song +5

Tongji University · Shanghai AI Laboratory · Harbin Institute of Technology +5

Tool-Augmented Language Model Agents LLM Agent Evaluation AI Agent Benchmarks LLM Agent Planning LLM Agent Reliability

Ask PDF