A typed skill graph gives up just 3.5 retrieval points across a 10x library scale-up

Notes on SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale (arXiv:2606.03056) — Tong Bai, Zhenglin Wan, P. Zhou, Xingrui Yu, Wangbo Zhao, Yang You, Ivor W. Tsang · June 2026

Note published July 23, 2026 · written by SkillFed’s research pipeline from the paper above · how these notes are made

SkillDAG models a large skill library as a typed directed graph instead of a flat embedding index. Five edge types — depends_on, specializes, composes_with, similar_to, conflicts_with — encode relationships cosine similarity can't see: prerequisite chains, narrower-vs-general variants, synergistic pairings, redundant duplicates, and incompatible combinations. Construction starts cold: each skill gets embedded twice, once for what it does and once for what it requires (a HyDE-style query expansion), and an LLM classifier assigns edge types between candidate pairs. At inference time the agent calls a single search() function that returns three parallel signals — top-K semantic matches, typed-edge neighbors from graph traversal, one-hop conflict warnings — and decides for itself how to weigh them, rather than have a fixed formula fuse them upstream. A propose-then-commit protocol lets the agent register new edges it discovers mid-episode, subject to acyclicity and non-contradiction checks, so the graph accumulates structure across runs instead of freezing at construction.

On ALFWorld and SkillsBench with MiniMax-M2.7, SkillDAG hits 67.1% task success and 27.3% reward — 12.8 and 8.6 points ahead of the strongest Graph-of-Skills baseline, a typed graph that Personalized PageRank collapses offline into one static context blob. Intrinsic retrieval (Ret@K) climbs from 65.5 to 78.2 in the same comparison. Swap in a stronger backbone and the gap tightens: gpt-5.2-codex ties the baseline on ALFWorld at 93.6% and beats it by just 2.4 points on SkillsBench, which points to the graph compensating for a weaker model's selection judgment rather than adding value unconditionally. Two stress tests probe the mechanisms on their own. Scale the skill pool 10x and Ret@K gives back only 3.5 points (78.2 to 74.7), while the baseline's fixed seeding-diffusion pipeline decays faster. Let the agent edit the graph live instead, and it stays set-monotone: 27 single-observation commits push average ground-truth hits per query from 1.915 to 1.984, with no query losing a retrieval it previously got right.