Toward Scalable Terminal Task Synthesis via Skill Graphs

1. Problem Statement

Terminal agents (LLMs interacting via command-line interfaces) show promise for autonomous system management but are severely constrained by the scarcity of high-quality, diverse execution trajectories for training.

• Current Limitations: Existing methods for scaling terminal tasks rely on:
  • LLM-generated taxonomies: Often diverge from real-world usage.
  • GitHub repository inversion: Deriving tasks from real codebases but limiting scope to software engineering (e.g., bug fixing) and failing to control the diversity of the execution path (the sequence of scenarios and skills).
• Core Insight: A terminal agent's trajectory is defined by two dimensions: the scenarios it traverses (intermediate states) and the skills it exercises (actions). Training requires data that densely covers the conditional product space of $(\text{scenario}, \text{skill})$ pairs. Current methods exhibit redundancy in these dimensions, leading to suboptimal learning.

2. Methodology: SkillSynth

The authors propose SkillSynth, an automated framework that synthesizes diverse terminal tasks by modeling workflows as paths on a Scenario-Mediated Skill Graph.

A. Skill Graph Construction

The framework builds a directed multigraph $G = (\Omega, K)$ where:

• Nodes ($\Omega$): Scenarios (decision-relevant abstractions of system states).
• Edges ($K$): Skills (directed transitions from a precondition scenario to a postcondition scenario).
• Pipeline:
  1. Skill Filtering: Aggregates skills from ClawHub and public GitHub repos, filtering for executability, structured workflows, and safety (no jailbreaks).
  2. Scenario Inference: Uses LLMs to infer precondition and postcondition scenarios for each skill.
  3. Semantic Deduplication: Clusters and merges scenarios that are semantically identical but lexically different (using hierarchical agglomerative clustering).
  4. Cross-Skill Alignment: Connects skills by matching the postcondition of one skill to the precondition of another via embedding similarity and LLM verification.
  • Result: A graph with ~82k scenarios, ~57k skills, and ~185k verified bridges.

B. Graph-Guided Path Sampling

Instead of random walks (which favor high-degree nodes), SkillSynth uses Inverse-Frequency Path Sampling (Algorithm 1):

• Mechanism: Maintains visit counts for scenarios ($\nu$) and skills ($\mu$).
• Probability: Samples next steps with probability proportional to $(count + 1)^{-1}$.
• Constraint: Enforces monotone progression (no revisiting nodes within a single path) to ensure diversity.
• Goal: Steer the empirical distribution toward uniform coverage of the $(\text{scenario}, \text{skill})$ space.

C. Multi-Agent Synthesis Harness

Sampled paths are instantiated into executable tasks via a multi-agent system:

1. Planner: Converts the abstract path into a structured plan of sub-objectives.
2. Constructor: Generates the full task instance (instruction, initial filesystem, Docker environment, verification scripts, oracle solution).
3. Dual Verification:
   • Oracle Check: Executes the solution in a container to ensure solvability.
   • Rubric Check: Uses an LLM-as-a-Judge to verify instruction-test alignment and ensure no solution leakage.
4. Iterative Repair: Failed instances undergo up to 3 repair cycles using tool-augmented agents before being discarded.

3. Key Contributions

1. Theoretical Modeling: Formulates terminal agent trajectories as sequences of scenarios and skills, identifying the need to maximize diversity in the $(\sigma, \kappa)$ space for effective training.
2. SkillSynth Framework: An end-to-end automated pipeline that constructs a scenario-mediated skill graph and synthesizes tasks without human intervention.
3. Scalable Synthesis: Achieved 3,560 verified task instances from 3,721 sampled paths in a single run, with a 95.7% oracle pass rate at an average cost of $27.3 per task.
4. Empirical Validation: Demonstrated that graph-guided synthesis yields harder, more diverse tasks than single-skill or random multi-skill baselines, leading to consistent performance gains.

4. Experimental Results

• Dataset: 3,560 verified tasks used to train Qwen3 models (8B, 14B, 32B) via Supervised Fine-Tuning (SFT).
• Benchmarks: Evaluated on Terminal-Bench 1.0 and 2.0.
• Performance Gains:
  • Qwen3-32B + SkillSynth achieved 33.8% on TB 1.0 and 29.6% on TB 2.0.
  • This outperformed the much larger Qwen 3 Coder 480B (23.9% on TB 2.0), proving that targeted data diversity is more effective than sheer model scale.
  • Ablation: SkillSynth tasks outperformed "Single-skill" baselines by ~8.4 points and "Random Multi-skill" baselines by ~3.8 points on TB 2.0.
• Task Difficulty: 38% of synthesized tasks were unsolvable by the agent even after 3 attempts (0/3 success), indicating high complexity.
• Diversity: SkillSynth trajectories showed 31% higher unique scenario-skill coverage compared to single-skill baselines.

5. Significance and Future Work

• Paradigm Shift: Moves terminal task synthesis from "volume-based" (generating many similar tasks) to "diversity-controlled" (ensuring coverage of the state-action space).
• Cost Efficiency: Provides a scalable, low-cost method to generate high-quality training data, enabling smaller models to compete with larger proprietary models in terminal tasks.
• Real-World Alignment: By grounding synthesis in real-world skills (ClawHub/GitHub) and scenario transitions, the generated tasks better reflect actual user workflows.
• Future Directions: Scaling to larger data regimes, adapting to cheaper models, and exploring subgraph sampling to enable parallel execution of multiple skills, further increasing task complexity.

Conclusion: SkillSynth effectively bridges the gap between the scarcity of high-quality terminal data and the need for diverse training trajectories, establishing a new standard for scalable, automated terminal agent training.