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

ToolSpace reverses data-centric environment synthesis by mining tool-composition graphs from real execution traces and synthesizing replay-verified cross-environment tasks, lifting long-horizon tool-use scores and producing harder Pro benchmark splits.

Existing MCP environment-scaling methods are data-centric: they first synthesize a database and scenario, then derive tools and tasks from them. This causes tool interfaces to diverge from real ones, tool compositions that are not grounded in execution, and tasks that rarely span more than one environment. The paper argues the root cause is that synthesis reverses the dependency that governs real agent execution, where tools are the atomic units and their relations define reachability across environments.

ToolSpace collects a trajectory corpus from real MCP services and open agent corpora, grouped into high/medium/low execution-authenticity tiers with progressively stricter filtering. From adjacent calls it builds a typed tool-composition graph whose nodes are tool-plus-normalized-argument configurations and whose edges are data, state, and retry dependencies extracted by deterministic rules, weighted by witnessed transition frequency and pruned when low-frequency or untraceable. The weighted graph is clustered by connection density into 804 environments; databases are synthesized only for operation environments, state-query environments are initialized from tool outputs as the initial snapshot, and stateless tools replay cached returns. State-aware random walks sample admissible neighbors proportionally to edge weight, roll back on failure or state inconsistency, and retain chains that reach target length and environment count. Each retained chain is decompiled into a natural-language task without tool names or call order, paired with state, trace, and output assertions, and kept only if replay from the initial state passes all checks.

• ToolSpace raises the 35B backbone average across seven long-horizon tool-use benchmarks, with further gains from agent RL. §6.2
• On the 744B scale, ToolSpace-744B-A40B surpasses GPT 5.6 Sol in average score and matches Claude Opus 5. §6.2
• On the Pro splits built by anchoring the pipeline to two benchmarks, all seven frontier models drop, with the largest AutomationBench drop reaching 38.2 points. §6.3
• The reconstructed tool graph and synthesized data are large: 77,760 tool-call-pattern nodes from 2,042 canonical tools, data/state/retry edges at 69%/25%/6%, and 34,376 trajectories of which 21,385 have at least five tool calls. §4.3
• Ablations show that removing structural edge types, rollback, weighted sampling, or replacing witnessed edges with LLM-judged edges degrades all five benchmarks. §6.4
• Environment synthesis cost, proxied by synthesized files over 500 sampled environments, drops because databases are materialized only for operation-bearing environments. §6.4

• Environment synthesis cost savings are measured only with a file-count proxy over 500 sampled environments; the paper states this does not directly measure token, wall-clock, API, or compute cost, so exact savings are not measured (§6.4).
• At the smallest data fraction (1/16) the SFT mixture causes interference: BFCL V4 and OfficeQA Pro fall below the untuned backbone, indicating the trend is only stable once the data fraction increases (§6.4).
• ToolSpace-8B still scores 0.0 on Harvey LAB, so the small-scale setting leaves professional legal workflows unaddressed (Table 1, §6.2).
• Comparison coverage is uneven: several cells are marked '–' as not officially reported (e.g. WorkRover-35B-A3B, Claude Opus 5 and GPT 5.6 Sol on AutomationBench), and external scores are used as published rather than locally reproduced (§6.1, §6.2).

• Data-centric synthesis is argued to cause tool-functionality mismatch, inauthentic tool orchestration, and no cross-environment task synthesis. §1
• Edges are mined by deterministic rules from adjacent real calls, typed as data, state, or retry, and weighted by observed transition frequency w = N_ij / N_i. §4.1.2
• Environments are clustered from the weighted undirected graph projection, yielding K = 804 clusters, with databases synthesized on demand only for operation environments. §4.1.3
• Walk neighbors are kept only if inputs can be filled from earlier returns or the current snapshot, sampled proportionally to edge weight among admissible neighbors. §4.2.1
• Rollback sampling discards failing steps, restores the prior snapshot, and resamples; retained chains are replayed from s0 before acceptance. §4.2.1
• Tasks are written without tool names or call order and verified by state, trace, and output assertions rather than a reference answer. §4.2.2
• Pro benchmark tasks were reviewed by three doctoral-level experts, with Fleiss' kappa = 0.82 and observed agreement of 93.1%. §5
• Environment scale drives performance, with AutomationBench rising from 9.2 to 33.8 between the 1/16 and 1/8 environment fractions, while task embeddings form 42 clusters versus 25, 31, and 34 for prior corpora. §6.4