🤖 AI

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

SkillDAG introduces a self-evolving, typed directed graph framework that enables LLM agents to dynamically retrieve and structurally reason about inter-skill relationships during execution, significantly outperforming existing baselines in complex task environments by accumulating execution-backed knowledge and maintaining robust candidate ranking as skill libraries scale.

Original authors: Tong Bai, Zhenglin Wan, Pengfei Zhou, Xingrui Yu, Wangbo Zhao, Yang You, Ivor W. Tsang

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tong Bai, Zhenglin Wan, Pengfei Zhou, Xingrui Yu, Wangbo Zhao, Yang You, Ivor W. Tsang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hiring a massive team of specialized workers (skills) to help a robot solve complex puzzles. In the past, when the team was small, you could just read everyone's resume and pick the right people. But now, imagine your team has grown to thousands of workers.

If you try to read all their resumes at once, you run out of time and space. If you just ask a computer to find the "most similar" resume to the task, you might miss the crucial person you actually need because their resume doesn't look like the task, even though they are essential for it.

SkillDAG is a new system designed to solve this "too many workers" problem for AI agents. Here is how it works, using simple analogies:

1. The Problem: The "Flat" List vs. The "Map"

Current AI systems often treat skills like a flat list of names. If you ask for a "cooking skill," the system finds the word "cook." But it might miss that you also need a "chopping skill" (a prerequisite) or that you shouldn't use "cooking" and "freezing" at the same time (a conflict).

The Old Way: It's like trying to navigate a city using only a list of street names. You might know the destination, but you don't know which streets connect to it, which ones are dead ends, or which ones are one-way streets.
The SkillDAG Way: It builds a living map (a graph) where every skill is a city block, and the connections between them are clearly labeled roads. Some roads say "You must take this to get there" (Prerequisite), some say "This is a shortcut" (Specialization), and some say "Do not go here" (Conflict).

2. The Innovation: The Agent Holds the Map

In previous systems, a fixed computer program decided which skills to load based on the map, and the AI agent just received a pre-packaged list. The agent couldn't ask, "Why did you pick this?" or "Can I add a new road?"

SkillDAG flips this.

The Agent is the Navigator: The AI agent itself is given the map. It can look at the connections, ask questions, and decide which skills to load.
The "Search" Tool: Instead of just getting a list of names, the agent asks the map: "Who is close to this task?" (Matches), "Who connects to them?" (Neighbors), and "Who should I avoid?" (Conflicts). This gives the agent three different types of clues to make a smart decision.

3. The "Self-Evolving" Part: Drawing New Roads

The map isn't perfect when it starts. It's built from a "cold start" (reading the resumes), but it misses things that only happen when the robot actually does the work.

The "Propose and Commit" Protocol: If the agent tries a task and realizes, "Hey, I needed Skill A before I could use Skill B," it can propose a new road on the map connecting them.
The Safety Guardrails: Before the new road is drawn, the system checks three rules:
1. No Loops: You can't create a circle where A needs B, and B needs A (that would trap the agent).
2. No Contradictions: You can't draw a road saying "Go here" and another saying "Don't go here" for the same pair.
3. Undo Button: If the agent makes a mistake, the system keeps a log so the road can be erased later.

This means the map gets smarter and more detailed every time the agent solves a puzzle, learning from its own experience.

4. The Results: Smarter and Faster

The paper tested this on two types of challenges:

ALFWorld (Virtual House): The agent had to move objects around a house.
SkillsBench (Coding Tasks): The agent had to write code to solve problems.

The Outcome:

Better Success: The SkillDAG agent solved significantly more puzzles than the previous best methods. It was especially good at picking the right tools when the library of tools was huge.
Better Memory: Even as the number of skills grew 10 times larger, the SkillDAG agent didn't get confused. It kept finding the right skills, whereas other methods started to fail.
Intrinsic Improvement: The system didn't just get lucky; it actually retrieved the correct "ground truth" skills more often, proving the map structure was working.

Summary Analogy

Think of SkillDAG as giving an AI agent a GPS that updates itself.

Old System: You give the agent a static paper map. If the road changes or a new shortcut opens, the agent is stuck with the old map.
SkillDAG: The agent holds a digital GPS. It can see the traffic (conflicts), the connections (dependencies), and as it drives, it draws new shortcuts on the map for future trips. The agent decides where to go, using the map as a tool, not a rule.

The paper claims this approach makes AI agents much better at choosing the right tools from a massive library, leading to higher success rates in complex tasks.

Technical Summary: SkillDAG

1. Problem Statement

As Large Language Model (LLM) agents adopt extensive external skill libraries, the bottleneck shifts from skill authoring to skill selection. When libraries scale to thousands of entries, traditional retrieval methods fail to capture the complex structural relationships between skills.

Flat Retrieval Limitations: Standard approaches (e.g., top- $K$ cosine similarity or BM25) treat skills as independent vectors. This leads to "silent failures" where structurally necessary prerequisites are omitted, redundant or interfering skills are selected, and synergistic pairs are missed.
Static Graph Limitations: Prior work like Graph of Skills (GoS) models inter-skill relationships but relies on a fixed, offline retrieval pipeline (e.g., Personalized PageRank). The resulting skill bundle is opaque to the agent; the LLM cannot query the graph structure, reason about why a skill was chosen, retract a noisy retrieval, or record new relationships discovered during execution.

The core problem is that current systems hide the library's relational structure from the agent, preventing the LLM from making informed structural decisions during inference.

2. Methodology: SkillDAG

SkillDAG proposes a fundamental inversion: rather than embedding the graph inside a fixed ranking algorithm, it exposes the typed skill relation graph as an agent-callable structural retrieval interface. The graph is queried, inspected, and evolved by the LLM during execution.

2.1. Typed Skill Relation Graph

The skill library is modeled as a directed graph $G = (V, E, \tau)$ where edges are assigned one of five operational types:

depends_on: Skill $A$ requires prerequisite $B$ .
specializes: Skill $D$ is a narrower, preferred variant of $A$ .
composes_with: Skills $A$ and $B$ have synergistic co-use.
similar_to: Functional redundancy; the agent should pick one, not both.
conflicts_with: Skills $A$ and $B$ should not be co-selected (pruning signal).

Key Design Choice: conflicts_with is treated as a pruning signal, not a traversal edge, to prevent the agent from navigating toward skills it is explicitly told to avoid. The backbone (depends_on, specializes) is constrained to be acyclic.

2.2. Agent-Callable Interface

The agent interacts with the graph via a search function that returns three distinct evidence channels, rather than a single ranked bundle:

Matches: Top- $K$ skills based on query-node embedding similarity.
Neighbors: Skills reached via bounded BFS traversal (depth $D$ ) over the four "positive" edge types (depends_on, specializes, composes_with, similar_to).
Conflicts: One-hop conflicts_with edges incident to any match.

This decomposition allows the agent to drop specific fields under tight context budgets, schedule searches dynamically, and maintain a reasoning trace for selection/exclusion decisions.

2.3. Cold-Start Construction

To initialize the graph before any agent execution, a two-view embedding strategy is employed to recover cross-functional pairs that single-view similarity misses:

$e_{self}$ : Embeds the skill's identifier, description, and body (what it does).
$e_{needs}$ : An LLM generates a HyDE-style summary of what the skill requires (prerequisites) based on imagined invoking tasks, which is then embedded.
Candidate pairs are formed if either ranking exceeds an adaptive threshold, followed by an LLM pair classifier to assign edge types. conflicts_with is excluded from this static phase as it requires execution evidence.

2.4. Online Graph Evolution

SkillDAG introduces a propose-then-commit protocol for online graph updates:

propose-edge: A dry-run where the agent previews a potential edge change and reviews existing history for that skill pair.
edit-edge: The agent commits the change with a natural-language reason and execution trace.

Structural Invariants: To prevent incoherence, every commit must pass three checks:

Acyclicity: Prevents cycles in the depends_on/specializes backbone.
Non-contradiction: Prevents a pair from having both a positive edge (e.g., depends_on) and a conflicts_with edge simultaneously.
Reversibility: An append-only history log enables rollback of spurious edits.

3. Key Contributions

Identification of Structural Failure Modes: The paper identifies that flat retrieval silently omits structurally necessary skills and concatenates redundant ones, a failure invisible to similarity matching alone.
Agent-Callable Interface: SkillDAG exposes a typed relation graph via search/show/propose-edge/edit-edge, replacing fixed ranking policies with structural evidence the agent reasons over directly.
Online Evolution Protocol: A mechanism for agents to grow the graph from single-episode evidence under strict structural invariants, paired with a two-view cold-start constructor to recover cross-functional pairs.
Empirical Validation: Demonstrated improvements on ALFWorld and SkillsBench across different model backbones.

4. Experimental Results

Experiments were conducted on ALFWorld (text-based embodied environment) and SkillsBench (containerized code-generation tasks) using MiniMax-M2.7 and gpt-5.2-codex.

Performance Gains (MiniMax-M2.7):
- ALFWorld: Success rate increased from 54.3% (GoS baseline) to 67.1% (+12.8 points).
- SkillsBench: Reward increased from 18.7% to 27.3% (+8.6 points).
- Intrinsic Retrieval: Ret@K on SkillsBench rose from 65.5% to 78.2%, indicating the retrieval pipeline itself is more accurate before execution.
Performance Gains (gpt-5.2-codex):
- SkillDAG tied the GoS baseline on ALFWorld (93.6%) and improved on SkillsBench (34.4% $\to$ 36.8%).
- The paper notes that the "routing aid" signature is largest where the backbone model cannot reason past a poor bundle and vanishes once the backbone is strong enough to handle opaque bundles.
Scalability: SkillDAG's retrieval quality remained stable (Ret@K $\approx$ 78.2%) as the skill pool expanded 10x (from 200 to 2000 skills), whereas the GoS baseline degraded significantly.
Edit Persistence: Online edits committed during training transferred effectively to held-out test episodes, and the edited graph retrieved more ground-truth skills per query without evicting prior hits (set-monotone property).

5. Significance and Claims

The paper claims that SkillDAG validates the hypothesis that graph structure works best as an interface for routing decisions, not as an opaque policy.

Inversion of Design: By making the graph an agent-callable interface rather than a fixed retriever's substrate, the system allows the LLM to decide how structural evidence affects execution.
Robustness: The approach isolates the retrieval pipeline gain, showing that typed-graph retrieval outperforms diffusion-based ranking (PPR) as the library scales, without relying on the agent's execution to fix a broken retrieval system.
Self-Evolution: The system enables precise, auditable updates to the skill structure based on execution evidence, allowing the graph to accumulate knowledge across episodes without human curation.

The authors acknowledge limitations regarding the long-horizon behavior of single-observation self-evolution, noting that while aggregate edit effects are positive, the stability of such evolution over very long timelines remains an open question for future work.