Renmin University of China · Fudan University
* Equal contribution · † Corresponding authors
Rather than synthesizing a database first and deriving tools from it, ToolSpace starts from how real tools actually compose — and lets environments and tasks emerge from that structure, in two stages:
Mine data / state / retry dependencies from adjacent calls in real execution traces with deterministic rules, building the weighted tool-composition graph \(\mathcal{G}_{TS}\). Tightly-coupled tools are clustered into environments — a database is synthesized only for state-mutating clusters; query tools restore snapshots, stateless tools replay cached returns.
Run state-aware random walks with rollback over \(\mathcal{G}_{TS}\): sample state-compatible successors \(\propto w\), execute step by step, roll back and resample on failure. Each completed chain is decompiled into a natural-language task with assertion-based verification, and kept only if it replays from \(s_0\).
A short walk through tool-centric synthesis — the two stages, then the performance and cost numbers on the same canvas.
Data-centric synthesis presumes a realistic environment and derives tool composition from it — reversing the dependency that governs real agent execution. That inversion causes three failures, and ToolSpace is built to remove each one.
Every retained training sample is a walk that actually executed — step by step, under real state transitions — and replayed cleanly from its initial snapshot.
Collect real MCP & web agent trajectories, then mine adjacent calls with deterministic rules — shared arguments become data edges, state preconditions become state edges, repeated-after-failure calls become retry edges. Cluster the weighted graph into environments; synthesize a database only for operation clusters, restore snapshots for state-query tools, replay cached returns for stateless ones.
From a tool bound to \((𝒟_k, s_0)\), repeatedly sample a state-compatible successor proportionally to edge weight and execute it. Every argument must trace to the task, \(s_0\), or an earlier return. A failed or relation-violating step restores \(s_{t-1}\) and resamples — chains that cannot proceed are discarded.
Each successful walk \(\omega\) is decompiled into a natural-language task \(q\) (no tool names, no call order) plus assertions over final state, intermediate snapshots, and required output fields. The sample enters \(\mathcal{X}_{TS}\) only if re-executing \(\omega\) from \(s_0\) passes every check.
A miniature, executable model of §3.2 — ten environments and 160 tools drawn as a star field. Design the walk on the left, watch a bright walker travel the witnessed edges in the middle, and follow its candidate probabilities, pseudocode and failures on the right.
Click any configuration to inspect it — the same leaderboard pattern as a benchmark site, because ToolSpace is also a benchmark-building machine. Averages are over AutomationBench, SkillsBench, JobBench, τ³-Bench Banking, BFCL V4, Harvey LAB and OfficeQA Pro.
Anchoring ToolSpace to the standard benchmarks — AutomationBench and τ³-Bench Banking — to build AutomationBench Pro and τ³-Bench Banking Pro links in outside tools that share witnessed relations, then walks with larger \(L\) and \(K\). Same protocol, same prompts — longer chains (26.8–43.6 → 56.3–60.6 tool calls on AutomationBench Pro) and real cross-environment breadth. Frontier models drop by up to 38.2 points.
300 tasks · seven frontier models · AutomationBench vs. AutomationBench Pro
98 tasks · seven frontier models · τ³-Bench Banking vs. τ³-Bench Banking Pro
Average tool calls per task
Average tool calls per task
Pro tasks are longer, not just harder to guess: on AutomationBench Pro every frontier model needs roughly 1.4 to 2.1× as many tool calls as on AutomationBench (26.8–43.6 → 56.3–60.6), and τ³-Bench Banking Pro also rises for every model over τ³-Bench Banking (23.1–32.2 → 27.3–36.3). Data read from the paper's tool-call comparison (Figure 6).
Both scaling axes use the same Qwen3.6-35B-A3B backbone, training recipe and evaluation protocols — only the amount of ToolSpace data, or the number of environment clusters it is drawn from, changes. Zero denotes the untuned backbone. Lines below are read directly from the paper's scaling figure (five benchmarks).
Training-data fraction · 0 → 1/16 → 1/8 → 1/4 → 1/2 → full
The full dataset is best on all five benchmarks, and the last doubling (1/2 → full) still adds +4.6 on AutomationBench — the current synthesis scale has not hit its returns ceiling. Each fraction adds newly witnessed tool chains, not more copies of the same ones.
Training-environment fraction · 0 → 1/16 → 1/8 → 1/4 → 1/2 → full
AutomationBench jumps 9.2 → 33.8 between 1/16 and 1/8 environments: new clusters contribute new cross-environment edges, so space breadth is the limiting factor at low coverage (≈ +4 pts per doubling beyond 1/8). τ³-Bench Banking, which relies on a narrower stateful tool set, gains most only at the full environment set (19.6 → 34.0).
@article{dong2026toolspace,
title = {ToolSpace: Scaling Tool-Centric Environment Synthesis
for Long-Horizon Agents},
author = {Dong, Guanting and Sun, Zhichao and Yang, Xinyu and others},
year = {2026},
note = {Renmin University of China and Fudan University}
}
Open PDF ↗