ToolSpace: Scaling Tool-Centric Environment Synthesis for Long-Horizon Agents

AI summary

Overview

Research area: Natural Language Processing / LLM agents — specifically the synthesis of training environments and data for long-horizon tool-using agents built on top of Model Context Protocol (MCP) services.

Technical level: Advanced. The paper includes formal problem framing (tool spaces, state snapshots, graph walks), a multi-stage data pipeline, supervised fine-tuning plus GRPO-based agentic RL, and evaluation across seven benchmarks.

Scope: ToolSpace is a framework that reconstructs a tool-composition graph from real agent execution traces and uses it to synthesize cross-environment, replay-verified long-horizon training tasks — and to "upgrade" two existing agent benchmarks into harder Pro versions.

What This Paper Is About

Existing methods for scaling agent environments are data-centric: they invent a database and scenario first, then derive tools and tasks from it. This means the tools may not match real interfaces, the tool-to-tool links are guessed rather than observed, and tasks rarely cross more than one environment. ToolSpace reverses this order — it starts from real execution traces of tool calls, mines how tools actually connect, and builds tasks out of those witnessed connections so that synthesized agent data follows real tool orchestration.

Key Contributions

1. A diagnosis of data-centric synthesis. The authors identify three limits of the prevailing paradigm: tool–functionality mismatch (synthesized tools diverge from real interfaces), inauthentic tool orchestration (links built by random linking or shallow LLM judgment), and lack of cross-environment task synthesis (tools locked inside single sandboxes).

2. ToolSpace, a tool-centric framework. A two-stage pipeline: Tool Space Exploration builds a typed, weighted tool-composition graph from real traces and clusters it into 804 environments, and Cross-Environment Verifiable Task Synthesis walks that graph with rollback and decompiles chains into natural-language tasks with assertion-based checks.

3. Two harder benchmark variants. Applying the pipeline to AutomationBench and τ³-Bench Banking yields AutomationBench Pro (300 tasks) and τ³-Bench Banking Pro (98 tasks), which exceed the standard splits in difficulty, tool-call turns, and cross-environment breadth; seven frontier models drop by up to 38.2 points on the Pro version.

4. Trained models and scaling evidence across scales. ToolSpace-8B, ToolSpace-35B-A3B, and ToolSpace-744B-A40B (built on Qwen3-8B, Qwen3.6-35B-A3B, and GLM-5.2-744B-A40B) show gains from 8B to 744B, plus ablations on edge provenance and on data/environment scale.

Main Findings

• Large average-score gains on seven long-horizon tool-use benchmarks. ToolSpace raises Qwen3.6-35B-A3B from 23.0 to 41.0 average score (43.2 with RL), and GLM-5.2 from 44.6 to 56.6 — described as on par with Claude Opus 5.

• The 744B variant beats GPT 5.6 Sol on average. ToolSpace-744B-A40B scores 56.6 versus 48.9 for GPT 5.6 Sol, and matches Claude Opus 5's 56.6 average.

• Pro benchmarks are genuinely harder, not just longer. On AutomationBench, average tool calls rise for every model from 26.8–43.6 under Standard to 56.3–60.6 under Pro; on τ³-Bench Banking they rise from 23.1–32.2 to 27.3–36.3. Expert review of the Pro tasks showed strong agreement (Fleiss' κ = 0.82, observed agreement 93.1%).

• Execution-witnessed edges beat LLM-judged ones. The ablation shows edges mined deterministically from adjacent real calls clearly outperform edges produced by LLM judgment. Performance also keeps improving as data scale and environment scale grow.

• The tool space is large and dependency-diverse. The graph 𝒢_TS contains 77,760 tool-call-pattern nodes derived from 2,042 distinct canonical tools, with mean and maximum outdegree of 2.3 and 56. Edges split into 69% data, 25% state, and 6% retry dependencies, showing composition is driven mainly by intermediate-result transfer.

• Most real environments are stateless, which makes synthesis cheap. Of 804 environments, 181 (22.5%) are operational and 623 (77.5%) non-operational; 453 tools (22.2%) are operational versus 1,589 (77.8%) non-operational. Databases are synthesized only for the operational minority.

• Synthesized tasks are long and cross-environment. Across 21,385 trajectories with at least five tool calls: mean/max length 30,466 / 855,386 tokens, average 18.86 tool calls (max 209), average 2.29 environments (max 22), and at least 66.2% of trajectories involving two or more environments.

• Environment coverage is broad. Domains are led by Communication & General Utilities (27.4%), Finance & Markets (11.2%), and Document & Design (10.1%), with an average of 10.86 matched tools per environment and a maximum of 436. Environment types include Gmail, Google Sheets, Slack, Google Drive, Salesforce, and Airtable.

Methodology in Plain English

ToolSpace starts by collecting real evidence of agents using tools. Trajectories come from two families: tasks re-executed against live MCP servers whose tool definitions match the real catalog, and web-sourced trajectories ranked by execution authenticity — real-server interactions (Toucan-1.5M: 495 MCP servers, 2,000+ tools, 1.5M trajectories; ToolBench/ToolLLM: 16,464 RapidAPI interfaces, ~469K API calls), real-workspace interactions from SWE-agent and OpenHands, and synthetic-tool trajectories filtered to only calls matching real tools. Over 200,000 trajectories were collected, with decontamination at both task and trajectory level.

From these traces it builds a graph where a node is a tool together with a specific argument configuration, and edges are typed by deterministic rules rather than LLM judgment: data dependencies (a downstream argument literally reuses an upstream output, with matching field types), state dependencies (one call mutates an object and the next reads or further mutates that same object), and retry dependencies (a call errors, the agent switches tools, and the next call succeeds). Each edge is weighted by how often that transition was actually observed, and low-frequency edges are pruned; for data edges, arguments must be traceable back to the upstream output so that incidental constants like limit=10 don't create false links.

Tools are then grouped into environments by connection density, producing 804 clusters. Only clusters that can modify state need a synthesized database — built by a research agent from a theme derived from the cluster and iteratively expanded, then kept only after unit tests and state-transition checks. State-query tools seed their initial snapshot from real returned records instead of a fabricated database, and stateless tools just replay cached recorded outputs, avoiding live API calls entirely.

To make tasks, the system runs state-aware random walks over the graph: from the current tool it keeps only neighbors whose inputs can be filled from earlier outputs or the current state, samples among them in proportion to edge weight, executes each step, and updates the state. If a step fails or breaks the traversed edge relation, it rolls the environment back to the previous snapshot and resamples; chains that stall after repeated rollbacks are dropped. Each surviving chain is decompiled into a natural-language task that deliberately omits tool names and call order, paired with a verification set checking the final state, key intermediate snapshots, and required output fields. A sample only enters the dataset if replaying the chain from the initial snapshot passes every check. This yields 34,376 SFT samples and 653 RL samples (the latter additionally Pass@16–screened with the 35B model so only candidates with one or two correct rollouts are kept).

For the Pro benchmarks, the same machinery is anchored to an existing benchmark: tools outside the original environment that share data or state relations are linked in, larger walk lengths and more environments are targeted, and tasks are regenerated and verified.

Training uses one epoch of SFT (16 GPUs for 8B/35B, 256 GPUs for 744B) and GRPO for RL, with clipping bounds 0.8 and 1.28, 48 steps, learning rate 2×10⁻⁶, batch size 256, rollout group size 16, and maximum policy staleness of 4. Kimi K3 generates teacher trajectories and reverse-synthesizes tasks. ToolSpace results are averaged over three independent runs.

Why This Matters

Impact on research. The paper reframes the unit of scaling for agent data: instead of scaling environments, it scales tool composition witnessed in real executions. That shift fixes a structural flaw in prior pipelines (tools derived from fabricated databases) and makes the same framework usable to raise the difficulty of existing benchmarks rather than only to generate new training data — a reusable recipe for the agent-data community. The finding that execution-witnessed edges beat LLM-judged edges is a concrete, useful signal for anyone building synthetic agent data.

Real-world applications:

• Workflow automation across SaaS tools — the paper's environments (Gmail, Google Drive, Sheets, Slack, Salesforce, Airtable) mirror real enterprise automations that span multiple services.
• Banking and financial back-office agents — anchored to τ³-Bench Banking, where tool–dialogue interaction and persistent account state must stay consistent.
• Legal agent workflows — represented by Harvey LAB among the evaluation benchmarks.
• Office document question answering and reporting — represented by OfficeQA Pro and job-style professional tasks in JobBench.

Industry relevance. Because ToolSpace reuses real MCP tool definitions and replays cached outputs for stateless tools, it cuts database-synthesis and API costs relative to data-centric pipelines — an economically meaningful property for anyone producing agent training data at scale. The result that a 744B open-weight model trained this way reaches 56.6 average, matching Claude Opus 5 and exceeding GPT 5.6 Sol (48.9), is a direct competitive signal for teams training their own agents. The MCP-centric framing also aligns with the emerging standard for connecting models to external services.

Future Directions

• Broadening beyond the current MCP and API sources. The corpus depends on registries like Smithery, Toucan-1.5M, ToolBench/ToolLLM, and container-based agents; extending witnessed-composition mining to domains with few public traces (or to non-MCP enterprise systems) remains open.

• Scaling RL beyond 653 samples. The RL set is much smaller than the 34,376 SFT samples and required Pass@16 screening to keep only one-or-two-success candidates; how performance scales with far more verified RL tasks is not yet established.

• Verification completeness. Tasks are accepted only if replay from the initial state passes state, trace, and output assertions; how much agent behavior escapes those checks, and whether assertion design limits task diversity, is an open question.

• Extending the "Pro" upgrade recipe to more benchmarks and to difficulty control. Only AutomationBench and τ³-Bench Banking were upgraded here; treating difficulty as a tunable (via chain length, environment count, and share of cross-environment edges) is a natural next step.

Target Audience

Researchers and engineers working on LLM agents, tool use, and agentic data synthesis — particularly those building or training models against MCP services and long-horizon workflows. It is also valuable for benchmark designers who want to increase task difficulty systematically, and for ML practitioners evaluating whether open-weight models (8B to 744B) can be brought to frontier-agent performance with better environment and data construction rather than scale alone. Readers should be comfortable with graph abstractions, execution-state reasoning, and standard SFT/GRPO training setups.

Authors’ abstract

Large language models are deployed as long-horizon agents that compose diverse tools across MCP services into executable workflows. Existing MCP environment-scaling methods are data-centric: they first synthesize a database and scenario, then derive tools and tasks from them. As a result, tool interfaces may not match real ones, tool compositions are not grounded in execution, and tasks rarely span more than one environment. We propose ToolSpace, a tool-centric framework that reverses this order. ToolSpace mines data, state, and retry dependencies from adjacent calls in execution traces of real MCP services and open agent corpora, using deterministic rules rather than LLM judgment, and clusters the resulting weighted tool-composition graph into environments. Databases are synthesized only for state-mutating environments, while query and stateless tools replay recorded returns. ToolSpace then performs state-aware random walks with rollback and decompiles each chain into a natural-language task with assertion-based checks, keeping only samples that replay successfully from the initial state. Applied to AutomationBench and tau3-Bench Banking, the pipeline produces harder Pro versions on which 7 frontier models drop by up to 38.2 points. Across seven long-horizon tool-use benchmarks, ToolSpace raises Qwen3.6-35B-A3B from 23.0 to 41.0 average score (43.2 with RL) and GLM-5.2 from 44.6 to 56.6, on par with Claude Opus 5. Ablations show that execution-witnessed edges clearly outperform LLM-judged ones, and performance keeps improving with data and environment scale.