PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiayu Liu, Qihan Lin, Cheng Qian, Rui Wang, Emre Can Acikgoz, Xiaocheng Yang, Jiateng Liu, Zhenhailong Wang, Xiusi Chen, Heng Ji, Dilek Hakkani-Tür

arXiv:2606.22388v1cs.AIcs.CL

TL;DR

Existing benchmarks rarely test long-horizon planning when agents see only retrieved tools from large, unreliable ecosystems. PlanBench-XL evaluates this setting with interactive retail workflows and retrieval-time blocking, finding that frontier agents remain brittle as blocked tools and longer recovery paths sharply reduce performance.

  • Problem

    Existing benchmarks rarely evaluate whether agents can solve long-horizon tasks with partial tool visibility and unreliable retrieved tools in large ecosystems.

  • Method

    PlanBench-XL benchmarks adaptive planning through 327 multi-step retail workflows over 1,665 tools, with interactive retrieval and simulated tool-access blocking.

  • Results

    Frontier agents remain highly brittle: GPT-5.4 falls to around 30% accuracy when blocking leaves one feasible path and slightly above 10% when only the longest recovery path remains.

  • Takeaways & Limitations

    PlanBench-XL provides a testbed for developing agents that detect unreliable tool access, preserve intermediate evidence, and re-plan under partial observability.

  • Takeaways & Limitations

    The benchmark currently covers only retail, and its blockers represent selected failures rather than the full complexity of real-world tool ecosystems.

Abstract

from arXiv · show

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.

1 Introduction

PlanBench-XL evaluates long-horizon LLM planning when agents must retrieve tools from large, partially observable ecosystems and adapt to unreliable access. Its retail benchmark and blocking environment expose substantial weaknesses in exploration, information exploitation, invocation reliability, and runtime replanning.

  • Planning setting: Agents must discover useful tools during problem solving through retrieval-mediated, partially observable interactions.Long-horizon tasks require exploring intermediate sub-goals, retrieving relevant tools, and adapting plans as the task unfolds.
  • Challenges: Retrieval is unreliable because relevant tools may be missed, while retrieved tools may be damaged, stale, misleading, or unreliable.Existing benchmarks often assume fixed visible tools, explicit intermediate goals, or clean tool descriptions, and therefore do not fully capture this setting.
  • Benchmark: 327 evaluation instances span 1,665 tools and require approximately 25 turns on average in multi-step retail workflows.PlanBench-XL is an interactive, dynamic benchmark rather than a fixed, fully visible toolset.
  • Planning setting: Bi-directional anticipation supports forward searches from accumulated evidence, backward searches from desired outcomes, and bridges between known and hypothesized states.This design mirrors human problem solving by reasoning from both the current state and the desired outcome.
  • Results: GPT-5.4 falls to around 30% when only one feasible path remains and to slightly above 10% when only the longest remaining path is available.Across ten leading open-source and proprietary LLMs, most models remain below two-thirds accuracy in the default setting, while retrieval-time blocking causes sharp performance drops.
  • Contributions: Three blocking events force real-time adaptation and re-planning, while success also requires precise exploitation of discovered information and reliable tool invocation.The environment is designed to simulate real-world unpredictability and can serve as an RL playground for agent training.

2 Related Work

Prior benchmarks and agent designs address large-scale tool selection, long-horizon execution, and task decomposition, but generally assume reliable tool availability. PlanBench-XL targets the unresolved challenge of planning with unreliable, retrieval-limited tools.

3 PlanBench-XL

PlanBench-XL evaluates long-horizon agent planning in massive, retrieval-limited tool environments, requiring agents to infer implicit sub-goals and discover tool-use paths. Its interactive design tests exploration, intermediate evidence acquisition, and recovery from disrupted but solvable paths.

  • Benchmark design: PlanBench-XL evaluates agents in massive tool-use environments where they must infer implicit sub-goals and discover useful tool-use paths rather than inspect the full library.The benchmark reflects settings in which tool visibility is limited and agents must explore to uncover intermediate information.
  • Benchmark design: Two evaluation modes combine ordinary retrieval noise with optional blocking that disrupts selected useful paths while preserving solvability.The default mode mixes useful tools with distracting alternatives; block mode tests whether agents can recover and re-plan.
  • Environment construction: The typed tool library represents domain-specific information with datatypes, while generated tools and backend records support systematic executable tool construction and concrete responses.Retail datatypes include examples such as person_name and purchase_status; tool calls match arguments to records and return output datatypes.
  • Interaction protocol: Each query is a multi-turn interaction in which the agent retrieves candidate tools, calls retrieved tools with structured arguments, or returns a final answer.The runtime state tracks the query, discovered tools, and datatypes obtained through successful calls.
  • Retrieval and blocking: Retrieval supports forward, backward, and input-output-conditioned exploration, while blocked candidates may fail explicitly, fail implicitly, or provide semantically misleading functionality.Blocking is hidden from the agent and replaces selected valid-path tools with semantically similar alternatives.

4 Experiment

PlanBench-XL evaluates deterministic proprietary and open-source models on 327 queries over 1,665 tools, using task-completion, exploration, and execution-quality metrics. Results show that successful long-horizon planning depends on model scale, broad bidirectional exploration, relevant exploitation, and reliable tool calls.

  • Experimental setup: The benchmark contains 327 evaluation queries, 1,665 tools, 56 datatypes, a 100-turn interaction budget, and retrieval capped at 30 returned tools.Shortest valid solutions require 5–9 tool calls, and experiments use global random seed 42.
  • Main results: 77.06% accuracy is achieved by Gemini-3.1-Pro, while Qwen3-8B and Llama-3.1-8B-Instruct achieve 0%, demonstrating the difficulty of massive-tool planning.Most other models remain below 60% accuracy, and larger variants outperform smaller counterparts within model families.
  • Exploration: Mean EDT correlates strongly with accuracy at r = 0.902, indicating that broader discovery of intermediate datatypes is associated with greater task success.Mean EDT measures newly uncovered datatypes beyond each query’s initial datatypes.
  • Exploration: Gemini-3.5-Flash uses the most turns on average (57.87) and the highest S/C Ratio (10.44), whereas Gemini-3.1-Pro reaches higher Mean EDT with about one third the turns and one seventh the ratio.Frequent retrieval and long interactions therefore do not guarantee effective exploration.
  • Exploration: Effective tool discovery requires combining forward exploration from current evidence with backward anticipation from the desired outcome.Agents generally issue more input-conditioned than output-conditioned retrievals, indicating a common preference for forward anticipation.
  • Execution quality: EGT Precision correlates with accuracy at r = 0.781, while ITCR correlates negatively at r = −0.443, linking success to relevant execution and valid tool calls.Gemini-3.1-Pro maintains ITCR near zero at 0.68%, while Llama-3.1-8B-Instruct has the second-highest ITCR and the lowest accuracy.

5 Analysis

The analysis shows that blocking harms agents most when failures are silent or recovery requires longer paths. Longer minimal tool-use horizons also reduce accuracy, while additional test-time exploration provides only limited gains.

  • Block Types and Severity: Accuracy worsens as blocking disables a larger proportion of feasible solution paths, with degradation especially pronounced for GPT-5.4.Block ratio measures the proportion of originally feasible solution paths disabled by replacing path-critical tools with block alternatives.
  • Block Types and Severity: Implicit failures produce the lowest accuracy among single-type perturbations for all selected models.Silent failures are especially disruptive because agents cannot readily detect them and recover through alternative planning.
  • Path Length Effects: Accuracy drops sharply when blocking preserves only the longest valid solution path rather than only the shortest path.The result indicates that agents struggle to re-plan effectively through longer recovery paths.
  • Inference-Time Augmentation: Enforced exploration produces quickly saturating gains that remain far below no-block accuracy.The intervention adds continuation prompts after incorrect termination, with budgets from Benf = 0 to Benf = 5.
  • Path Length Effects: Accuracy generally decreases as shortest valid solution-path length L∗ increases, with the decline becoming sharper under blocking.Queries are grouped by L∗, with longer tasks aggregated into the L∗≥8 group.

6 Error Analysis

Failures usually occur after partial progress, when agents drift from valid solution paths and rarely recover, even though useful tools may remain available. Blocking exposes additional weaknesses: silent, plausible-looking failures contaminate downstream decisions, while models adopt distinct termination policies after navigation failure.

  • Drift and recovery: Irrecoverable Drift accounts for 72.4% of GPT-5.4’s and 71.3% of Gemini-3.5-Flash’s default failure categories, remaining dominant across four models.Weak Recovery accounts for only 3.0% of reported default failure categories when aggregated across models.
  • Drift and recovery: 78.0% of default cases and 71.1% of block cases had already retrieved at least one valid tool before a failed-run non-progress call.Non-progress calls used tools from recent retrieval windows in 74.1% of default cases and 63.6% of block cases, despite clean progress-capable tools sometimes being older.
  • Drift and recovery: Progress-capable tools re-appeared after drift in 42.5% of default cases and 53.4% of block cases, yet agents still failed to select them reliably.Recovery therefore requires retaining earlier candidates and re-ranking previously seen and newly retrieved tools by their expected progress toward the final target.
  • Blocking failures: Semantic misleading tools account for at most 3% of invoked block alternatives and are never selected by GPT-5.4 or Llama-3.3-70B-Instruct.Models more often struggle with executable-looking alternatives that appear schema-compatible or return concrete values.
  • Blocking failures: Value Reused follows 55.9% of GPT-5.4’s and 75.5% of Llama-3.3-70B-Instruct’s implicit-failure cases, versus 42.2% across models and 0% for explicit failures.Explicit errors prevent direct propagation of invalid values but do not always stop downstream search from the failed branch.
  • Termination policies: GPT-5.4 explicitly surrenders in 77.3% of default noninteraction failures and 80.6% under blocking, while DeepSeek-V4-Flash and Llama-3.3-70B-Instruct commit wrong tool values in 58.8% and 81.7% of default failures.Under blocking, DeepSeek-V4-Flash commits wrong tool values in 65.9% of failures and Llama-3.3-70B-Instruct in 71.7%.

7 Conclusion

PlanBench-XL evaluates long-horizon adaptive planning in large-scale, retrieval-mediated tool ecosystems and shows that current LLM agents remain brittle under tool disruptions and extended recovery requirements.

  • Benchmark contribution: PlanBench-XL is an interactive benchmark for evaluating long-horizon adaptive planning in large-scale, retrieval-mediated tool ecosystems.It was introduced to assess agent behavior in massive-tool environments.
  • Key findings: Current LLM agents remain brittle in massive-tool environments.The reported brittleness appears even among frontier models.
  • Key findings: Relevant-tool blocking, silent corruption, and longer recovery paths cause sharp performance declines.These disruptions expose failures in adaptive planning.
  • Key findings: Longer test-time interaction provides only limited gains.Additional interaction does not substantially resolve the reported planning brittleness.

Limitations

PlanBench-XL offers a scalable framework for evaluating adaptive planning under massive, retrieval-mediated tool access, but its current scope is limited. In particular, the benchmark is instantiated only in the retail domain, despite covering diverse multi-step workflows.

  • Domain scope: PlanBench-XL is currently instantiated in the retail domain, which may not capture the full breadth of real-world tool-use scenarios.Its queries nevertheless cover diverse multi-step workflows.
  • Extensibility: The benchmark can be extended to additional domains through its scalable generation pipeline over typed datatypes, executable tools, and backend databases.

Ethics Statements … B.8.1 Metrics Formulation

PlanBench-XL is designed as a retrieval-mediated, long-horizon benchmark whose tools, tasks, runtime, ground truth, and metrics enforce multi-step interaction with imperfect external environments. Its appendices specify ethical safeguards, realistic tool construction, executable-state evaluation, and measures of completion, exploration, and execution quality.

  • Ethics Statements: Ethics Statements: The benchmark minimizes societal risk through retail-domain data validation, responsible co-author annotation, license compliance, and locally hosted or API-accessed models.The code uses MIT licensing, the benchmark uses a Creative Commons license, and model access follows each model’s deployment mode.
  • A Comparison Traits: A Comparison Traits: The benchmark characterizes realistic agents through tool use, retrieval, implicit sub-goals, bi-directional exploration, unreliable tools, long horizons, and scalable generation.Long-horizon tasks involve around 25 turns or more, while retrieval addresses ecosystems containing hundreds or thousands of APIs.
  • B.2.3 Tool Filtering Details: B.2.3 Tool Filtering Details: Candidate tools must have deterministic dependencies, tool-grounded information access, plausible retail semantics, and non-trivial information gain.The filters exclude redundant inputs, pure computation shortcuts, implausible relations, and outputs that merely rename, format, or echo existing values.
  • B.2.4 Why Tool Calls Are Necessary: B.2.4 Why Tool Calls Are Necessary: Tool invocation is required because hidden backend values cannot be inferred from user queries and action-like operations reveal their resulting values.Tools expose either direct database lookups or operations through search-style interfaces.
  • B.8.1 Metrics Formulation: B.8.1 Metrics Formulation: Evaluation reports accuracy, EGT Precision, average turns, explored datatype count, search-to-call ratio, invalid tool-call ratio, and untrusted input rejection rate.These metrics respectively capture answer completion, ground-truth overlap, interaction cost, exploration breadth, retrieval activity, protocol violations, and propagation of noisy-tool values.

B.8.2 Illustrative Examples for Metrics … C Additional Experiment Results

The paper illustrates seven metrics on a synthetic trajectory and formalizes blocking as hidden retrieval-time replacement of selected tools. Blocking preserves solvability while testing recovery from explicit failure, silent invalid outputs, and semantically misleading alternatives.

  • B.8.2 Illustrative Examples for Metrics: The illustrative trajectory yields 100% Accuracy, 100% EGT Precision, 10 turns, 3 explored datatypes, an S/C Ratio of 0.50, an ITCR of 16.7%, and a UIRR of 16.7%.It follows U → O → R → S, while including one invalid call, one noisy call, and one later untrusted-input rejection.
  • B.8.2 Illustrative Examples for Metrics: Trusted successful outputs determine EGT Precision, so invalid and noisy behavior can coexist with perfectly on-path trusted execution.The noisy return is excluded from the executed datatype set, while trusted calls remain on the ground-truth path.
  • B.8.2 Illustrative Examples for Metrics: The evaluation averages Accuracy, EGT Precision, Avg. Turns, and Mean EDT over queries, but computes S/C Ratio, ITCR, and UIRR from global trajectory totals.This distinguishes query-level outcome and exploration measures from globally aggregated interaction measures.
  • B.9 Blocking Details: Blocking replaces selected retrieved tools with additional tools, while the agent sees an ordinary-looking retrieval result and cannot observe the hidden blocked set.Unselected tools remain unchanged, whereas selected baseline tools are removed and replaced by their perturbation-specific alternatives.
  • B.9.2 Additional Tool Construction: Additional tools preserve the original retrieval-facing form for explicit and implicit failures, whereas semantic misleading tools remain related but implement a different function detectable from their descriptions.All additional tools are generated with GPT-5.2 from the original tool’s name, description, input datatypes, and output datatypes.
  • B.9.3 Selection of Blocked Tools: The blocker selects hidden tool sets before interaction, preserves at least one feasible solution path, and uses n⋆= 1, δ = 1, and nmin = 1, requiring ni(C) ∈{1, 2}.Candidate sets are drawn from a finite enumerated pool, with seeded tie-breaking for reproducibility; all experimental task instances are resolved successfully.
  • B.9.4 Practical Relevance and Significance of Blocking: The main block setting uses three perturbations—explicit failure, implicit failure, and semantic misleading—to test visible unavailability, silent misinformation, and fine-grained tool understanding.Together, these conditions evaluate whether agents can maintain reliable planning under complementary sources of tool unreliability.
  • C Additional Experiment Results: Accuracy variations across seeds for DeepSeek-V4-Flash and Llama-3.3-70B-Instruct do not exceed 3%.Figure 10 reports low variation across different seeds.

C.1 Evaluation Robustness

Robustness analyses indicate that default-setting results have generally narrow bootstrap confidence intervals and that blocked-evaluation conclusions remain consistent across random seeds. These checks support the stability of the reported findings under statistical resampling and seeded blocker variation.

  • Theoretical Bounds: 10,000 bootstrap resamples over evaluated queries produced generally narrow 95% confidence intervals across models.The intervals quantify statistical uncertainty in the default-setting results.
  • Theoretical Bounds: 2.94 percentage points was the average confidence-interval radius for Accuracy across evaluated models.The corresponding average radii were 3.70 percentage points for EGT Prec. and 2.10 tu…
  • Empirical Results: Blocked evaluations of DeepSeek-V4-Flash and Llama3.3-70B-Instruct were highly consistent across seeds 1000, 2000, and 3000.Model and other configuration choices were held fixed, and the small fluctuations suggest conclusions were not sensitive to the seeded blocker configuration.

C.2 Retriever Robustness · D Case Study

The retriever and runtime protocol perform reliably in single-step tool retrieval, indicating that Qwen3-8B’s weaker full-benchmark performance primarily reflects multi-step planning, state tracking, and execution challenges.

  • C.2 Retriever Robustness: The robustness check creates one-step tasks mapping each tool’s input datatypes to its output datatype, yielding an exactly one-call solution after retrieval.Each task uses the main benchmark’s query-construction pipeline, executable backend instances, and tool execution for the gold answer.
  • C.2 Retriever Robustness: The evaluation tests Qwen3-8B, a relatively weak benchmark model, on identifying and invoking the correct tool in single-step queries.The ideal trajectory comprises one retrieval request, one tool call, and one final answer.
  • C.2 Retriever Robustness: 85.95% accuracy was achieved over 185 single-step queries, while the ground-truth tool appeared in 92.43% of returned retrieval lists.These results directly assess retrieval and execution in the one-step setting.
  • C.2 Retriever Robustness: 3.18 average turns and a 0.95 search-to-call ratio remained close to the ideal three-turn trajectory.The ideal consists of retrieval, tool call, and final answer.
  • C.2 Retriever Robustness: 0.00% invalid tool-call rate indicates reliable tool invocation under the single-step evaluation.The evaluation’s target is to retrieve and execute the corresponding tool correctly.
  • C.2 Retriever Robustness: The large gap between single-step and full-benchmark performance is therefore attributed more to multi-step planning, state tracking, and execution decisions than retriever failure.The authors frame the single-step evaluation as a conservative sanity check because Qwen3-8B performs poorly on full multi-step tasks.

D.1 Error Case Study … F.3 Future Work

The paper illustrates how agents fail when trajectories drift, tools mislead, or recovery paths are blocked, while positioning PlanBench-XL as a controlled testbed for adaptive planning. It argues that robustness requires diverse exploration, response verification, explicit backtracking, and blocker-aware training.

  • D.1 Error Case Study: Representative trajectories expose irrecoverable drift, search exhaustion, and silent-failure contamination as distinct ways tool-use paths lose grounding.These cases separate where trajectories break, how corrupted outputs affect later decisions, and how models terminate afterward.
  • D.2 Data Case Study: A representative task requires moving from fulfillment clues through order, return, and payment records before reaching the requested account field.The path demonstrates that failures can occur before useful evidence, after drift, or when executable-looking outputs are mistaken for grounded evidence.
  • E Justifications and Design Choices: PlanBench-XL uses datatype-grounded retrieval to control discoverability, feasible paths, and blocking effects, enabling reproducible evaluation while abstracting away realistic retriever noise.The retriever is intended to isolate exploration, planning, and recovery rather than benchmark retrieval systems themselves.
  • E Justifications and Design Choices: Each retained task requires at least five distinct tool calls on its shortest valid solution, enforcing non-trivial multi-step reasoning beyond direct lookup.Task complexity is controlled by the underlying state graph rather than surface-level linguistic difficulty.
  • F.1 Beyond Simple Search Problem: Agents must infer latent goals, formulate natural-language retrieval requests, interpret imperfect evidence, and recover, so blocking cannot be reduced to explicit graph search or simply more interaction.The internal typed graph is hidden during evaluation, and enforced exploration tests whether additional turns resolve degradation.
  • F.2 Evaluation Fairness: The same blocked tools, replacements, perturbation types, and induced solution-space changes are applied across models, making remaining feasible paths identical for fair comparison.Observed differences therefore reflect failure detection, misleading-tool avoidance, and adaptive recovery abilities.
  • F.3 Future Work: Future work proposes diversity-aware retrieval, failure-aware verification, backtracking recovery, and training on trajectories containing explicit, implicit, and semantic tool failures.These approaches target repeated local searches, untrusted outputs, brittle replanning, and missing adaptive behavior.
  • F.3 Future Work: Blocker-aware training directly teaches agents to recognize blocked paths, avoid repeated failed calls, discard suspicious observations, and recover rather than merely receive more test-time turns.The proposed trajectories include retrieval misses, explicit errors, implicit errors, and semantic distractions.

F.4 Significance and Generalization

PlanBench-XL evaluates implicit sub-goal exploration and adaptive recovery under dynamic tool blocking, using dedicated exploration and exploitation metrics beyond final accuracy. Its domain-general design supports studying robust multi-turn planning across tool-use settings beyond retail.

  • Significance: PlanBench-XL requires agents to infer missing information, retrieve relevant tools, and construct valid multi-step paths rather than receiving tools or intermediate steps in advance.This explicitly evaluates exploration of implicit sub-goals in large-scale tool ecosystems.
  • Significance: Dedicated exploration and exploitation metrics distinguish the breadth of intermediate information uncovered from the ability to use discovered tools along task-relevant paths.These metrics complement final accuracy by separating exploration from exploitation capabilities.
  • Significance: Dynamic blocking tests whether agents detect unavailable, unreliable, misleading, or silently faulty tools and recover instead of following the first plausible path.The mechanism models removed online skills, API errors, misleadingly similar tools, and unreliable retrieved capabilities.
  • Significance: Together, implicit sub-goal exploration and dynamic blocking make PlanBench-XL a framework for adaptive planning in large, partially observable tool ecosystems.The benchmark targets discovering useful capabilities, exploiting them coherently, and recovering when environments change.
  • Generalization: 4.32 was the average score for generated tools, while annotated datatypes averaged 4.56, indicating high quality aligned with realistic retail scenarios.These averages summarize evaluation of the annotated tools and datatypes.
  • Generalization: The benchmark’s core design generalizes beyond retail by replacing domain-specific datatypes, tools, and backend data while preserving exploration and dynamic blocking protocols.The input-to-output structure also applies to travel, enterprise workflows, customer support, healthcare administration, finance, and software engineering.

G Human Annotation

The tool library and datatype inventory were validated through a human annotation study involving five experienced annotators. They rated sampled tools and datatypes on 1–5 Likert scales for reasonableness and realism.

  • Study design: Five annotators with relevant research experience evaluated 10 tools and 5 datatypes each.The study therefore included 50 annotated tools and 25 annotated datatypes in total.
  • Study design: 50 tools and 25 datatypes were rated from 1 to 5 using standard Likert-scale conventions.Ratings assessed each item’s reasonableness and realism.
Loading 2606.22388v1…