Paper Deep-Dive: Recursive Synthesis — Extending Verified Tasks Into 40,000 Long-Horizon Terminal Problems

Long-horizon terminal tasks cost hundreds to thousands of dollars each to author. RST mass-produces them for about $0.05 by recursively extending already-verified seeds. Fifteen rounds yielded 37,484 tasks, with oracle solutions growing from a median of 67 lines to 374, and the resulting trajectories genuinely improved Qwen3.5 under SFT and PPO — a walkthrough of the data-synthesis paper from Tencent and collaborators.

Recursive Synthesis for Long-Horizon Terminal Tasks

Building the problem set costs more than solving it

Training an AI agent takes practice problems it can actually roll up its sleeves and attempt. Yet long-horizon terminal (command-line) tasks — the kind that take tens of minutes of work — cost hundreds to thousands of dollars each to author, the paper reports (§1). The expense is not writing the prompt. A single task is a four-piece set: instruction, execution environment, oracle solution, and grading program — and all four have to agree with one another. Grade against a condition the instruction never states and the task becomes unfair; let the solution reach for a tool the environment doesn't ship and the task becomes unsolvable. Human authoring doesn't scale, and handing the whole bundle to an LLM is precisely what breaks those dependencies. Because fixing any one of the four ripples into the other three, the checking effort does not grow linearly with the length of the problem. For a task that takes tens of minutes to perform, confirming that the pieces agree costs more than writing them did.

The answer from RST (Recursive Synthetic Terminal Tasks, from Tencent HY LLM Frontier and collaborators, arXiv:2608.05466) is to stop building from scratch and instead extend tasks that have already been verified. Fifteen rounds of recursion turned 639 seeds into 37,484 tasks at roughly $0.05 apiece, and the later problems grow hard enough that even a strong model, given four attempts, solves only 2.5% of them (Abstract).

An analogy: adding rooms to a house that passed inspection

Build on an empty lot — generate a task from nothing — and you mass-produce defective houses where the plumbing and the floor plan don't match. RST starts from a house already confirmed livable (a verified task) and then (1) adds a room (extends the oracle solution), (2) redraws the blueprints and the inspection checklist (brings the grader and the instruction back into alignment), and (3) sends an inspector to actually live in it (runs the oracle solution in a fresh sandbox and puts it through the grader). Only houses that pass inspection become the foundation for the next extension. The ordering is the whole trick: rather than starting from the problem statement, you grow the working solution first and let the specification follow. That is why every accepted task ships with an executable proof that it can be solved (§1). Reverse the order — write the impressive specification first — and nobody ever finds out whether a solution satisfying it exists. Nearly all the wasted effort in authoring these tasks — by hand or by model — traces back to exactly that point.

What a task actually is: five files and two acceptance conditions

A task in this paper is a self-contained, executable problem made of five parts (§3): the public instruction instruction.md, the run configuration task.toml, the initial environment in environment/Dockerfile, the oracle solution solution/solve.sh, and the private grader in tests/. The agent works inside an isolated sandbox on a harness called Harbor, with the oracle solution and grader hidden from it. Grading inspects the final state that was achieved, not whether a particular command sequence was issued, so alternative solutions still earn credit. That choice pays off later, when the same tasks are used as reinforcement-learning environments: asking only "did you get the environment into this state?" rewards a route the model found for itself instead of rewarding memorized keystrokes. The flip side is that a request whose success cannot be written down as a state is not a task in this framework at all.

Two conditions govern acceptance (§3). Oracle validity means the oracle solution passes the grader in a fresh sandbox. Contract validity means everything the grader checks is either written in the instruction or discoverable from the working environment. The first guarantees the problem is solvable; the second guarantees there is no unfairness in the form of hidden requirements known only to the grader. The two are different kinds of condition. Oracle validity is empirical — you cannot establish it without standing up a sandbox and actually running the thing — while contract validity is a paperwork check between the grader's assertions and the text of the instruction. Skip the first and unsolvable problems get in; skip the second and problems that are solvable but ungradable get in. As training signal, both are noise in equal measure.

The mechanism: pick seeds, grow the solution, then align

The seed pool starts with 639 tasks derived from TerminalWorld, itself built from real operation logs; the first synthesis pass produces 2,820 tasks as $R_1$ (§4.1). From there, seeds are selected under caps so that no single parent, category, or rewrite lineage takes over (Appendix B uses 1,000 seeds per round and at most 4 from the same parent). The caps exist for diversity, not for yield: left alone, the descendants of whichever parents happen to be easiest to extend multiply fastest, and the diversity audit discussed later falls apart. The direction of each extension is drawn from 40 rewrite operators — five families (configuration and state, data and schema, filesystem, build and cache, runtime diagnostics) times eight each — and before rewriting anything, the system records a plan stating what is preserved, what is newly required, and which shortcuts must be blocked. Plans that amount to cosmetic changes, or that would introduce hidden requirements, are rejected right here (§4.2). The operators themselves are concrete construction techniques — reconciling dependency versions, repairing failing unit tests, diagnosing a root cause from logs — and the five families map onto the places an extension can add difficulty: environment, build, artifacts, state, and diagnosis (Appendix C).