Recursive Synthesis for Long-Horizon Terminal Tasks
Zhongzhi Li, Yucheng Shi, Zongxia Li, Ruhan Wang, Anhao Li, Zixun Huang, Junyao Yang, Lei Ke, Ninghao Liu, Haitao Mi, Leowei Liang
cs.AI, cs.LG
2026-08-06
RST recursively extends 639 seed terminal tasks into 37,484 verified ones over 15 rounds at about $0.05 each; SFT and agentic PPO on them lift Qwen3.5-27B by 20 to 41 percent relative across three terminal benchmarks.
Training a terminal agent that runs dozens of command-line steps in a row is bottlenecked by data. A high-quality long-horizon task must keep four things mutually consistent: instruction, environment, reference solution, and verifier. Human authoring runs hundreds to thousands of dollars per task, and asking an LLM to generate them directly usually breaks those dependencies. The Tencent Hunyuan team asks how to mass-produce verified, increasingly hard long-horizon terminal tasks cheaply.
RST is recursive verified synthesis. Each round picks seeds from the previous round's verified tasks. The core move is to extend the reference solution first, adding steps and stricter assertions to solve.sh, then realign the verifier and public instruction to the new workflow, and finally run it in a fresh sandbox. The reference solution must pass the private verifier (oracle validity), and every requirement the verifier checks must be stated in the public instruction or inferrable from the workspace (contract validity). Accepted tasks seed the next round and feed the reinforcement-learning pool; successful rollouts become SFT data. The team defines 40 rewrite operators across five families and caps parent lineage, category, rewrite family, and cohort so a few patterns cannot dominate.
Over 15 rounds, 639 seeds yield 37,484 tasks at about $0.05 each (about $50 per thousand). Difficulty genuinely climbs:
| Metric | R1 | R15 |
| Median solution lines | 67 | 374 (5.6x) |
| Median commands | 40 | 244 (6.1x) |
| DeepSeek-V4-Pro pass@4 | 90% | 2.5% |
| Median partial credit | 0.97 | 0.17 |
Instruction length only grows from 85 to 122 words (1.4x); what grows is executable workload, not prompt length. Downstream training pays off. SFT on self-collected Qwen3.5 trajectories lifts Qwen3.5-27B on Terminal-Bench 2 from 41.2% to 47.9% and on Terminal-Bench Hard from 22.7% to 28.3%. Agentic PPO then takes Qwen3.5-27B-RL to 49.44%, 32.00%, and 22.07% on the three benchmarks, relative gains of 20.0%, 41.2%, and 21.9%. The largest relative gain lands on the independently built Terminal-Bench Hard, evidence of transfer.
It answers a common worry, that synthesized training data collapses into useless repetition. Across 15 rounds, yield and validation rates hold steady, and domain spread, rewrite-family entropy, and operator coverage stay stable rather than collapsing onto a few parents or operators. For agent-training teams this is a reusable data pipeline: seed tasks and generator model are both swappable. It also shows a counterintuitive point: task difficulty can be raised by adding executable work rather than by lengthening the instruction, which is friendlier to automatic grading.
Synthesis relies on DeepSeek-V4-Pro as the generator, so the difficulty ceiling is bounded by its ability. Pass@4 falls to 2.5% at R15, but the paper does not say whether further rounds hit a wall; the authors claim no observed ceiling, yet that is only a 15-round observation. Later rounds grow more alike: median nearest-neighbor similarity rises from 0.22 to 0.46, with a thickening high-similarity tail (p95 of 0.70) that the authors themselves flag for deduplication. The trained gains still trail DeepSeek-V4-Pro, which scores 51.68/36.00/30.00 on the three benchmarks, so headroom remains large.