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

Abstract

Large skill libraries are now standard equipment for LLM agents, and which subset reaches the prompt decides what the agent can do. Enumeration and top-$K$ embedding retrieval both treat skills as independent documents, assuming relevance is a property of one skill at a time. It is not: skills depend on, conflict with, specialize, and duplicate one another, so the closest match to a task can name it while omitting a prerequisite it needs. Graph retrieval encodes these relations but spends them in a fixed pipeline, handing the agent an opaque bundle. We present SkillDAG, which exposes a typed skill graph to the LLM as an agent-callable interface rather than consuming it for the agent: search returns vector matches, typed-edge neighbors, and conflict signals, and a propose-then-commit protocol lets it register execution-backed edges as it works. Across two benchmarks and three model families, SkillDAG outperforms full-library prompting, vector retrieval, and Graph-of-Skills, gaining +14.3 points of ALFWorld success and tying only at ceiling; its ranking holds flat across a $10\times$ pool expansion that degrades the fixed pipeline. Inter-skill structure, these results suggest, is worth more to an agent that can query and revise it than to a retriever that consumes it.