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

PlanBench-XL evaluates LLM agent planning in large, retrieval-mediated, and unreliable tool ecosystems.

How do current LLM agents perform on long-horizon planning tasks in large-scale tool ecosystems when faced with realistic retrieval failures and complex dependencies?

LLM agents often fail to solve long-horizon tasks because they rely on partial, retrieval-mediated tool visibility and struggle to adapt when tool-use paths are disrupted. PlanBench-XL introduces an interactive benchmark where agents must iteratively discover tools, infer sub-goals, and re-plan when faced with missing, failing, or misleading tool functions. Experiments show that while frontier models perform well in clean environments, their accuracy collapses under retrieval-time blocking, revealing a fundamental inability to recover from silent failures or follow longer alternative paths.

Paper Primer

PlanBench-XL models the agent's environment as a state graph where tools are discovered via a retriever rather than being fully visible. The core mechanism hinges on bi-directional anticipation: agents must search forward from current evidence and backward from desired outcomes to bridge gaps, while the "blocking" module forces adaptation by replacing critical tools with failures or distractors.

Frontier LLMs struggle with adaptive planning in large, noisy tool ecosystems.

In the default setting, most models achieve under 60% accuracy; under severe retrieval-time blocking, GPT-5.4's accuracy drops from 51.90% to 11.36%. A performance collapse of over 40 percentage points under environmental stress.

The benchmark reveals that failure is rarely a lack of discovery, but a failure of selection. Agents frequently drift away from valid solution paths even when a progress-capable tool has already been retrieved, showing that the bottleneck is the transition from exploration to reliable execution.

Why does this benchmark use "blocking" instead of just testing on a large tool set?

Standard benchmarks often assume a fixed, reliable toolset. Blocking simulates real-world unpredictability—such as stale or broken APIs—to test if an agent can detect failure signals and re-plan, rather than just selecting tools from a static list.

Is the performance drop under blocking simply due to the task becoming unsolvable?

No. By construction, every blocked instance in PlanBench-XL preserves at least one feasible tool-call path, meaning the drop in accuracy reflects a failure in the agent's adaptive planning logic rather than a lack of available solutions.

The paper identifies "silent failures" (implicit errors) as the most harmful, as they provide weak signals that agents struggle to reject, leading to the propagation of invalid values through the trajectory.

Effective long-horizon planning requires moving beyond broad exploration to precise, bi-directional re-planning; current agents remain vulnerable to "irrecoverable drift" once a primary tool path is disrupted.

Introduction

LLM agents falter on multi-step tool use when retrieval hides or corrupts needed tools.

LLM agents now operate in sprawling tool ecosystems, but they can only see a tiny slice of the toolbox at each step because retrieval limits the context they can ingest.

Planning that spans many interdependent steps, where each step’s output becomes the next step’s input, and the agent must keep a coherent trajectory despite partial information.

Current benchmarks either expose the full tool set or assume clean, deterministic tool behavior, so they never stress the agent to cope with hidden or corrupted tools.

PlanBench‑XL fills this void: it offers 327 retail scenarios built on 1,665 tools, each requiring roughly 25 turns of interaction, and it injects optional blockers that can hide, fail, or mislead tool calls.

In block‑free runs GPT‑5.4 reaches 51.90% accuracy, but under the toughest blocking condition accuracy collapses to 11.36%, showing that massive‑tool planning remains far from solved.

The core gap is the leap from single‑step tool retrieval to robust multi‑step planning across large, imperfect tool ecosystems.

Benchmark Design

We detail the PlanBench‑XL environment, interaction protocol, and retrieval‑time blocking design.

PlanBench‑XL evaluates how LLM agents explore and plan in a large, noisy tool ecosystem, requiring them to discover sub‑goals and recover from retrieval‑time blockers.

PlanBench‑XL is a synthetic benchmark that presents agents with a massive library of typed tools and forces them to retrieve, invoke, and chain tools to answer multi‑turn queries.

How does PlanBench‑XL differ from standard tool‑use benchmarks?

Standard benchmarks usually expose the full tool set and require only a few calls. PlanBench‑XL hides many tools, injects retrieval‑time blockers, and mandates long chains, so agents must both explore and recover from failures.

During retrieval, a subset of tools on the correct solution path are hidden or replaced, forcing the agent to detect and work around unavailable resources.

Why not simply remove the blocked tools instead of substituting them?

Substituting preserves the interaction shape—agents still receive a tool candidate and must interpret its response, which tests their ability to recognize failure signals rather than just handling missing entries.

Define a typed datatype inventory D for the domain (e.g., `person_name`, `purchase_status`).

Generate candidate tools by pairing input and output datatype sets (`D_in`, `D_out`) and prompting a generation LLM.

Filter generated tools with a second LLM to discard vague or redundant entries, yielding the core library T.

Augment T with noisy variants that are semantically similar but flagged as unreliable.

Build a backend database of concrete datatype instances; each tool matches its inputs to a record and returns the requested outputs.

Construct queries by sampling a start datatype set $D$₀, a target set $Y$, enumerating solvable tool‑call sequences, and verbalizing the task as natural language.

Run the multi‑turn interaction loop where the agent retrieves tools, calls them, and updates its state until the answer is produced or `T_max` turns are exhausted.

**Figure 1.** Overview of PlanBench-XL. *Data construction* turns typed retail datatypes into executable tools and backend records, then derives solvable queries with ground-truth answers. *Runtime protocol* evaluates agents as they retrieve and invoke tools via bidirectional exploration, while retrieval-time blockers force re-planning.

Experimental Results

Key performance numbers, exploration analysis, and reliability findings for all evaluated models.

Gemini‑3.1‑Pro outperforms all other models on grounded accuracy and EGT Precision.

Table 3 shows 77.06 % accuracy and 91.47 % EGT Precision, the highest among the ten evaluated models. +27 % over the second‑best model (Gemini‑3.5‑Flash)

All models were evaluated with deterministic decoding (temperature 0.0), an 8192‑token limit, and identical benchmark settings described in §4.1.

**Table 3.** PlanBench-XL main evaluation results in the *default* setting under the grounded accuracy criterion. Scores in **bold** indicate the best performance among all models, and <u>underlined</u> scores denote the second-best performance. For *Mean EDT*, higher values generally indicate broader exploration but are not strictly better in all cases; we still highlight the top two values to aid readability. The metrics in (%) are reported in percentage form.

**Figure 2.** Accuracy under retrieval-time blocking. *Left*: performance across different block types when only one feasible solution path remains, including mixed blockers (*Mixed*), implicit failures (*Implicit*), explicit failures (*Explicit*), and semantic distractions (*Misleading*). *Right*: performance as blocking becomes stronger, ordered from no-block to block ratios of 0.2, 0.4, 0.6, and 0.8, with “1 Path” leaving only a single feasible path.

**Figure 21.** Full inference prompt used in our experiments.

Mean EDT (Expected Decision Trajectory) quantifies how many new datatypes a model discovers beyond the query’s initial inputs.

Performance Analysis

We dissect how blocking, failure types, and exploration affect model accuracy.

We evaluate three dimensions: the proportion of blocked paths, the nature of tool failures, and the amount of enforced exploration after a wrong termination.

Increasing the block ratio reduces accuracy, with GPT‑5.4 losing more than 20 % absolute accuracy.

When the ratio of disabled feasible paths rises, all four models drop, and GPT‑5.4’s accuracy falls from its baseline by >20 %.

When isolating failure‑type effects we kept the blocked tools and block ratio fixed, varying only the replacement tool behavior.

Even with additional interaction, block‑setting accuracy remains far below the no‑block baseline, showing deeper planning limits.

Longer shortest‑path groups correlate with lower accuracy; accuracy declines as the minimal solution length L* grows.

When only the longest valid solution path is kept, accuracy drops sharply (GPT‑5.4 falls to ~10 % versus ~30 % under the standard block).

**Figure 3.** Accuracy (%) on PlanBench-XL under fine-grained blocking. *Shortest* and *Longest* denote runs where blocking preserves the shortest and longest admissible solution paths, respectively; *Random* denotes the basic blocked configuration. Circles, squares, and diamonds mark these three settings.

**Figure 4.** Effect of enforced exploration under blocking. The enforced budget $B_{enf}$ is the maximum number of continuation prompts added after incorrect termination, with $B_{enf} = 0$ denoting the standard block setting and $B_{enf} = 5$ the largest budget tested. Accuracy gains quickly saturate and remain far below the no-block accuracy shown by the dashed line.

**Figure 5.** Accuracy (%) by shortest path length $L^*$ in the default and block settings. Queries are grouped by $L^*$, with longer tasks aggregated into the $L^* \ge 8$ group. Accuracy generally decreases for longer-path groups, and the decline becomes sharper under blocking.

Error Analysis

We dissect why agents drift off solution paths and how they terminate after failure.

LLM agents often drift away from productive tool paths rather than simply failing to retrieve tools.

Drift occurs when an agent continues issuing tool calls that do not advance any known solution path, causing the execution trajectory to leave the region of feasible answers.

How does drift differ from simply picking the wrong tool?

Drift describes a sustained sequence of non‑progress calls after an initial correct step, indicating the agent has left the solution corridor, whereas a single wrong tool is an isolated mistake that may be corrected.

Search exhaustion describes the agent giving up after repeatedly retrieving new tools without ever making another progress call.

Why doesn’t the agent keep searching indefinitely?

Because the evaluation protocol caps the number of retrieval steps; when the cap is reached without a progress call, the agent terminates in search exhaustion.

We now quantify how often agents drift, how they recover, and how different models terminate after failure.

In the default setting, 78.0 % of failed trajectories had at least one valid tool retrieved before the first non‑progress call, versus 71.1 % under retrieval‑time blocking.

Progress‑call analysis on PlanBench‑XL.

Non‑progress calls reuse a tool from the most recent retrieval window in 74.1 % of default cases and 63.6 % under blocking.

Tool‑selection timestamps.

When a useful tool is older than two retrieval windows, it is ignored in 44.7 % of default cases and 43.2 % under blocking.

Age‑distribution of selected tools.

After drift, a previously useful tool re‑appears in the recent window in 42.5 % of default cases and 53.4 % under blocking, yet agents still fail to select it.

Re‑appearance statistics.

Irrecoverable Drift dominates GPT failures, accounting for 72.4 % of its failed trajectories.

Figure 6.

Irrecoverable Drift dominates Gemini failures, accounting for 71.3 % of its failed trajectories.

Weak Recovery accounts for only 3.0 % of default failures.

Failure‑category breakdown.

GPT explicitly surrenders in 77.3 % of default failures.

Termination analysis.

Under retrieval‑time blocking, GPT’s surrender rate rises to 80.6 %.

Blocked‑setting termination analysis.

DeepSeek commits wrong tool values in 58.8 % of default failures.

Value‑reuse statistics.

In the blocked setting, DeepSeek’s wrong‑value rate increases to 65.9 %.

Blocked‑setting value‑reuse statistics.

Llama commits wrong tool values in 81.7 % of default failures.

Under blocking, Llama’s wrong‑value rate is 71.7 %.

Gemini exhausts its search budget in 90.8 % of default failures.

Termination pattern analysis.

Under blocking, Gemini’s search‑exhaustion rate is 85.1 %.

**Figure 6.** Trajectory Failure Category Distribution under the default setting (%). A tool call is counted as a progress call if it produces a new intermediate value required by at least one ground-truth tool-use path toward the final answer. We abbreviate GPT-5.4, Gemini-3.5-Flash, DeepSeek-V4-Flash, and Llama-3.3-70B-Instruct as GPT, Gemini, DeepSeek, and Llama.

**Figure 7.** Distribution of invoked block alternatives under *mixed* blocking. For each model, the horizontal bar normalizes all invoked block alternatives to 100%. Colors indicate whether the invoked block alternative is an explicit failure, implicit failure, or semantic misleading tool. We abbreviate *GPT-5.4*, *Gemini-3.5-Flash*, *DeepSeek-V4-Flash*, and *Llama-3.3-70B-Instruct* as *GPT*, *Gemini*, *DeepSeek*, and *Llama*.

**Figure 8.** Follow-up behavior after agents invoke block alternatives under *mixed* blocking. Each column corresponds to one model and one block type. The row length shows the ratio of all invoked block alternatives for that model, and colored segments denote *Unused*, *Search Reused*, and *Value Reused*. *GPT* denotes GPT-5.4, *Gemini* denotes Gemini-3.5-Flash, *DeepSeek* denotes DeepSeek-V4-Flash, and *Llama* denotes Llama-3.3-70B-Instruct.

Existing Benchmarks

We compare existing tool‑use benchmarks and introduce PlanBench‑XL’s full‑trait coverage.

This section surveys existing tool‑use benchmarks, highlights their trait coverage, and positions PlanBench‑XL as the only benchmark addressing all seven key capabilities.

ToolBench evaluates how well agents can retrieve and invoke a fixed set of APIs within a scripted task.

PlanBench‑XL places agents in a retrieval‑mediated setting with bi‑directional anticipation and optional retrieval‑time blockers, exposing weaknesses that other benchmarks miss.

Related Work

Related work on benchmarks and agent designs for large-scale tool planning.

Existing benchmarks evaluate tool selection over broad collections, but they typically assume explicit task goals. Large-scale tool-use and retrieval benchmarks (e.g., Qin et al., 2023a) focus on selecting tools from extensive libraries, while long-horizon benchmarks address stateful execution and multi-hop chaining. Robustness-oriented benchmarks introduce noisy users or imperfect tools, yet they rarely combine adaptation with active search over large tool spaces.

Our benchmark targets adaptive planning under partial tool observability and unreliable tool access, requiring agents to explore bi-directionally and to replan when tool-use paths are disrupted. This setting captures the core difficulty of retrieval-time blocking and tests grounded accuracy of the planning process.

Prior agent designs for large-scale tool planning fall into single-agent and multi-agent families. Single-agent frameworks emphasize modular tool invocation, reasoning–acting control, and scalable selection from large libraries, whereas multi-agent systems reduce cognitive load through communication and role-based task decomposition. However, these approaches still lack mechanisms for actively exploring implicit sub-goals and adapting plans as observations emerge.

Conclusion

We reflect on the broader impact and ethical considerations of our approach.

We summarize the contributions, acknowledge limitations, and outline responsible deployment guidelines for LLM agents in tool‑rich environments.

Read the original paper

Open the simplified reader on Paperglide

Browse all simplified papers