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
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:
- Plan: Select the necessary tools from a large repository.
- 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.
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