Recursive Synthesis for Long-Horizon Terminal Tasks

High-quality long-horizon training data for terminal agents is prohibitively expensive to produce manually, often costing hundreds to thousands of dollars per task because instruction, environment, reference solution, and verifier must remain mutually consistent. Direct LLM generation tends to break these dependencies. The paper proposes RST, which starts from verified seed tasks and iteratively extends the reference solution, realigns the verifier and instruction to the new workflow, validates the result in a fresh sandbox, and reuses accepted tasks as seeds for subsequent rounds.

Across fifteen recursive rounds, RST synthesized 37,484 terminal-agent tasks at roughly $0.05 per task. Task difficulty increases substantially: median reference solution grows from 67 to 374 lines, median executed commands grow from 40 to 244, and DeepSeek-V4-Pro pass@4 drops from 90% at round 1 to 2.5% at round 15. To demonstrate training utility, the authors collected rejection-sampled Qwen3.5 trajectories on the synthesized tasks and used them for supervised fine-tuning, improving Qwen3.5-27B and Qwen3.5-122B-A10B by up to 10 points on Terminal-Bench 2, Terminal-Bench Hard, and Long-Horizon Terminal Bench. Agentic PPO additionally lifted Qwen3.5-27B to 49.44%, 32.00%, and 22.07% on the three benchmarks, corresponding to relative gains of 20.0%, 41.2%, and 21.9% over the base model. The recursion shows no ceiling after 15 rounds: synthesis yield and validation rates remain stable while difficulty keeps climbing, suggesting the approach can scale well beyond the reported results.