SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale

SkillDAG introduces a typed directed graph system that models inter-skill relationships for LLM agents, enabling dynamic skill selection and structural learning during execution. The approach significantly outperforms existing baselines on ALFWorld and SkillsBench benchmarks, achieving 67.1% success and 27.3% reward by treating skill selection as a structural problem rather than a similarity-matching one.

SkillDAG addresses a fundamental scaling challenge in LLM agent architecture: as skill libraries grow, traditional retrieval methods fail to capture the complex interdependencies between skills. Rather than relying on static embedding similarity or full enumeration, the system represents skills as nodes in a typed directed graph where edges encode dependencies, conflicts, specializations, and duplications. This structural approach enables agents to navigate skill spaces more intelligently during inference.

The research builds on growing recognition that LLM agent capability plateaus when skill selection becomes a bottleneck. Previous Graph-of-Skills baselines attempted structured retrieval but relied on fixed pipelines determined before execution. SkillDAG's innovation lies in making the graph itself mutable and agent-callable, allowing systems to propose new typed edges and commit them based on execution outcomes. This creates a feedback loop where agent experience directly shapes the skill relationship structure.

The performance gains are substantial: 12.8 percentage points over the strongest baseline on ALFWorld and 8.6 points on reward metrics using MiniMax-M2.7, with results transferring to gpt-5.2-codex. Critically, the candidate ranking mechanism remains robust as skill pools expand 10x, while the prior seeding-diffusion approach degrades. The set-monotone online editing protocol ensures that new edges increase recall without removing previously valuable matches.

For AI practitioners, SkillDAG represents a maturing approach to agent scalability through structural rather than parametric scaling. The findings suggest that future high-capability agents will require dynamic knowledge graph management rather than static retrieval indices, opening new research directions in learning graph topology from agent behavior.

• →SkillDAG models skill relationships as typed directed graphs exposing structural retrieval to agents during execution rather than using fixed pipelines.
• →The system achieves 67.1% success on ALFWorld and 27.3% reward on SkillsBench, exceeding Graph-of-Skills baselines by 12.8 and 8.6 points respectively.
• →Agent-driven graph evolution through propose-then-commit protocols allows skills to accumulate relational structure across episodes based on execution outcomes.
• →Candidate ranking remains robust as skill pools scale 10x while fixed diffusion pipelines degrade, indicating superior scalability properties.
• →The approach treats skill selection as a structural problem rather than similarity-matching, fundamentally changing how large agent skill libraries are organized.