TPS-Bench: Evaluating AI Agents' Tool Planning \& Scheduling Abilities in Compounding Tasks

Hanwen Xu, Xuyao Huang, Yuzhe Liu, Kai Yu, Zhijie DengarXiv 2025 · DOI · arXiv

Abstract

As Large Language Model (LLM) agents transition from simple tool-use to complex real-world workflows, the ability to orchestrate multiple tools efficiently becomes paramount. This paper introduces TPS-Bench, a benchmark designed to evaluate agents on "compounding tasks"—requests requiring sophisticated tool planning and the management of parallel versus sequential dependencies. Our evaluation reveals a significant trade-off between task completion rates and execution efficiency. While reasoning models excel at accuracy through sequential execution, they often lack the efficiency found in more aggressive parallelizing models. We further demonstrate that reinforcement learning (RL) can effectively bridge this gap, optimizing both success and speed.

Introduction

Current LLM agents are proficient at executing isolated tool calls, such as searching the web or running code snippets. However, real-world utility often hinges on "compounding tasks" that involve multiple interdependent steps. For instance, a request to "book a trip based on my calendar and the weather" requires an agent to select appropriate tools from a vast repository and determine an optimal execution schedule.

Existing benchmarks often overlook the complexity of dependency graphs and the efficiency of tool orchestration. TPS-Bench addresses this by focusing on two core capabilities: Tool Planning (selection) and Tool Scheduling (ordering).

The TPS-Bench framework illustrates the agent workflow from planning and scheduling to multi-turn tool execution for a compounding task.

The TPS-Bench Framework

The benchmark utilizes the Model Context Protocol (MCP) to integrate 141 tools across 15 diverse servers. The evaluation pipeline measures an agent's ability to:

  1. Plan: Select the necessary tools from a large repository.
  2. Schedule: Decompose the task into subtasks and execute them in an order that respects dependencies while maximizing parallelism.

Performance is assessed via an "LLM-as-a-judge" for task completion and hard metrics for efficiency, including token usage, time, and monetary cost.

Dataset and Tool Distribution

TPS-Bench consists of 200 compounding tasks categorized into two difficulty levels:

  • TPS-Bench-Easy: Up to 5 weakly relevant subtasks, primarily testing parallel execution.
  • TPS-Bench-Hard: Up to 50 subtasks with strict, often implicit, dependency relationships.

The tasks span various domains, including Information Organization, Scientific Research, and Travel Planning, utilizing a wide array of tools from MCP servers.

Subtask distribution by category and the count of tools per MCP server highlight the diversity and scale of the TPS-Bench dataset.

Key Insights and Results

The Scheduling Trade-off

Our analysis identifies a stark behavioral split among top-tier models. Large Reasoning Models (LRMs) like GLM-4.5 and DeepSeek-R1 prioritize reliability, opting for strictly sequential execution. While this prevents cascading errors, it results in high latency and token costs. In contrast, models like GPT-4o attempt aggressive parallelization, which improves speed but often leads to failures when dependencies are overlooked.

Efficiency and "Cost-of-Pass"

We introduce the Cost-of-Pass metric, representing the expected monetary cost to achieve one successful task completion. This metric highlights that tool selection is a major bottleneck; passing entire tool schemas into the context window leads to exponential increases in token consumption and frequent context overflows. GPT-4o, despite its speed, exhibited the highest cost-of-pass ($138.0 \times 10^{-3}$) due to its lower completion rate on hard tasks.

Reinforcement Learning for Optimization

To address the efficiency-accuracy trade-off, we conducted an initial study using Group Relative Policy Optimization (GRPO). By fine-tuning a Qwen3-1.7B model on a small set of 100 compounding tasks with a reward function incentivizing both completion and parallelism, we observed a 6% improvement in task completion and a 14% reduction in execution time.

Conclusion

TPS-Bench exposes the current limitations of LLM agents in handling complex, multi-step workflows. While accuracy is improving, efficiency remains a significant challenge. Our results suggest that explicit scheduling capabilities can be taught through targeted reinforcement learning, paving the way for agents that are both highly reliable and operationally efficient.

Summary updated

Abstract

Large language model (LLM) agents have exhibited strong problem-solving competence across domains like research and coding. Yet, it remains underexplored whether LLM agents can tackle compounding real-world problems that require a diverse set of tools to complete. Given a broad, heterogeneous tool repository, LLM agents must not only select appropriate tools based on task planning analysis but also strategically schedule the execution order to ensure efficiency. This paper introduces TPS-Bench to benchmark the ability of LLM agents in solving such problems that demand Tool Planning and Scheduling. TPS-Bench collects 200 compounding tasks of two difficulty levels, based on a tool repository containing hundreds of model context protocol (MCP) tools. In particular, each task is composed of multiple subtasks, such as web search, map navigation, calendar checking, etc., and each subtask can be completed by a basic tool. Our evaluation emphasizes both task completion rate and efficiency. The empirical studies on popular closed-source and open-source LLMs indicate that most models can perform reasonable tool planning, but differ in scheduling. For example, GLM-4.5 achieves an outperforming task completion rate of 64.72% with extensive sequential tool calls, hence suffering from significantly long execution time. By contrast, GPT-4o prioritizes parallel tool calls but achieves only a 45.08% completion rate. Considering reinforcement learning (RL) can be a viable way to improve the scheduling efficiency without compromising performance, we perform an initial study on Qwen3-1.7B and witness a 14% reduction in execution time alongside a 6% gain in task completion rate based on rarely 100 RL training samples. Our code is available https://github.com/hanwenxu1/mcp-agent.
BibTeX
@misc{xu2025tps,
  author = {Hanwen Xu and Xuyao Huang and Yuzhe Liu and Kai Yu and Zhijie Deng},
  title = {{TPS-Bench: Evaluating AI Agents' Tool Planning \textbackslash\{\}\& Scheduling Abilities in Compounding Tasks}},
  year = {2025},
  eprint = {2511.01527},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.01527},
}
Figure