Technical Summary: Recursive Synthesis for Long-Horizon Terminal Tasks

Problem Statement

High-quality, long-horizon training data for terminal agents is prohibitively expensive to produce at scale. Creating a single verified task often costs hundreds to thousands of dollars because it requires maintaining strict mutual consistency between the public instruction, the executable environment, the reference solution, and the private verifier. Human authoring does not scale, and direct generation by Large Language Models (LLMs) frequently breaks these dependencies, resulting in tasks that are either unsolvable, unverifiable, or contain "leaked" information where the verifier checks for requirements not stated in the instruction. Existing benchmarks and automated builders have not yet provided a scalable method to generate high-quality, verified terminal-agent data that grows in complexity over time.

Methodology: Recursive Synthetic Terminal Tasks (RST)

The authors propose RST, a recursive verified synthesis framework designed to construct long-horizon terminal-agent tasks at scale. The framework operates on a "solution-first" principle, ensuring every accepted task carries an executable proof of solvability.

Core Workflow

1. Seed Initialization: The process begins with a pool of verified bootstrap tasks (639 tasks from TerminalWorld).
2. Recursive Expansion: For each round, selected tasks from the previous round serve as seeds. The framework executes four stages:
   • Target Selection: The system inspects the seed task (files, tools, dependencies) and selects a rewrite operator from a taxonomy of 40 operators grouped into five families (Configuration, Data/Schema, Filesystem, Build/Cache, Runtime/Diagnostics).
   • Task Contract Generation: A plan is formulated to extend the executable workflow. This plan defines new requirements, updates to the reference solution, and stricter verifier assertions, while explicitly identifying and rejecting potential shortcuts.
   • Rewrite (Grow Solution, then Align):
     • The reference solution (solve.sh) is extended with new operations (e.g., inspecting files, managing state, producing artifacts).
     • The environment (Dockerfile) is modified to support these operations (installing dependencies, initializing services).
     • The private verifier is updated to check the new state transitions and artifacts, rejecting placeholders or hard-coded outputs.
     • The public instruction is revised to state the new objective without leaking private verifier details or solution paths.
   • Validation:
     • Static Filters: Candidates undergo checks for near-duplicates, missing files, and instruction-verifier consistency (ensuring no hidden requirements).
     • Sandbox Oracle: The candidate is executed in a fresh sandbox. The reference solution must pass the private verifier. If failures occur, a bounded repair loop attempts to fix the task using execution logs. Only "oracle-valid" tasks (solvable by the reference) and "contract-valid" tasks (requirements visible to the agent) are accepted.
3. Reseeding: Accepted tasks form the pool for the next synthesis round. Diversity caps are applied to prevent dominance by specific parent lineages, categories, or rewrite families.

Training Integration

The framework simultaneously supports two training paradigms:

• Supervised Fine-Tuning (SFT): Successful rollouts collected by agents (Qwen3.5) on the synthesized tasks are used to fine-tune base models.
• Reinforcement Learning (RL): The verified task pool serves as the environment for verifier-based RL (PPO), where the agent is rewarded based on the task's built-in verifier.

Key Contributions and Results

1. Scalable, Low-Cost Synthesis

• Scale: Over 15 recursive rounds, RST produced 37,484 verified terminal-agent tasks from 639 seeds.
• Cost: The synthesis cost is approximately $0.05 per task, a drastic reduction compared to human-authored costs.
• Stability: The pipeline showed no signs of collapse or saturation. The yield of passed tasks per 1,000 attempts remained stable (498–572) across all 15 rounds, and candidate pass rates remained consistent (74.5%–81.5%).

2. Substantial Growth in Task Difficulty

The framework successfully increased the executable complexity of tasks without merely inflating prompt length:

• Solution Length: Median lines of code grew from 67 (R1) to 374 (R15) (5.6× increase).
• Command Usage: Median number of executed commands grew from 40 to 244 (6.1× increase).
• Instruction Length: Grew only modestly from 85 to 122 words (1.4×), indicating the difficulty stems from workflow complexity, not verbosity.
• Solver Performance: As a result of this growth, the pass@4 rate for DeepSeek-V4-Pro dropped monotonically from 90% (R1) to 2.5% (R15), and mean partial credit fell from 0.970 to 0.170.

3. Training Utility and Performance Gains

The synthesized data demonstrated significant utility for improving agent performance:

• Supervised Fine-Tuning: Fine-tuning Qwen3.5-27B and Qwen3.5-122B-A10B on trajectories from the synthesized tasks improved performance on Terminal-Bench 2, Terminal-Bench Hard, and Long-Horizon Terminal Bench by up to 10 points.
• Reinforcement Learning: Agentic PPO training on the synthesized pool lifted Qwen3.5-27B to 49.44% on Terminal-Bench 2, 32.00% on Terminal-Bench Hard, and 22.07% on Long-Horizon Terminal Bench. These represent relative gains of 20.0%, 41.2%, and 21.9% over the base model, respectively.
• Transferability: The improvements transferred to independently constructed benchmarks (Terminal-Bench Hard), suggesting the model learned generalizable long-horizon behaviors rather than overfitting to specific task distributions.

4. Diversity and Validity

• Domain Diversity: The task pool maintained broad domain coverage (19 domains) with stable entropy (0.821 to 0.817) and no evidence of domain collapse.
• Instruction-Verifier Alignment: Later rounds showed improved alignment, with "hidden-check protection" increasing from 38.2% to 63.5% and "short-instruction risk" decreasing from 41.6% to 7.5%.
• No Contamination: Audits confirmed no overlap between the synthesized tasks and the evaluation benchmarks (Terminal-Bench 2, Hard, LHTB), with maximum pairwise 5-gram Jaccard similarity below 0.009.

Significance

The paper claims that RST demonstrates a viable path to scaling high-quality training data for terminal agents without human authoring. By recursively evolving complete task bundles (workspace, solution, verifier, instruction) and validating them in a sandbox, the framework produces a self-improving dataset where difficulty increases systematically. The results indicate that:

1. Recursive synthesis does not collapse: The process can continue beyond 15 rounds while maintaining yield and diversity.
2. Executable complexity drives difficulty: The framework successfully generates tasks that are genuinely harder for agents to solve, evidenced by the sharp decline in solver pass rates.
3. Synthetic data is effective: Training on these verified, difficult tasks yields substantial performance gains on standard benchmarks, validating the "solution-first" approach for agent training.

The authors conclude that this pipeline depends on no particular seed domain or generation model, suggesting that the approach can continue to scale in both data quantity and quality to support the development of more capable long-horizon terminal agents.