A skill graph beats context-stuffing: +25.55% reward, -56.72% tokens

Notes on Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills (arXiv:2604.05333) — Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu, Shihang Gui, Yongbei Kuang, Lichao Sun · April 2026

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

Graph-of-Skills (GoS) builds a typed skill graph offline over a local skill library, linking skills through four edge types: dependency, workflow, semantic, and alternative. Dependency edges come free — induced deterministically from I/O schema overlap between skills, no LLM involved — while the other three relation types are filled in by a sparse, top-k LLM validation pass rather than an exhaustive pairwise check. At query time, GoS blends semantic and lexical retrieval scores to seed the graph, then runs a reverse-aware Personalized PageRank diffusion so upstream prerequisites — a parser here, a format converter there — accumulate relevance even when they share no vocabulary with the query. A final rerank-and-hydrate step packs the top-scoring skills into a token-budgeted bundle.

GoS is benchmarked against two baselines — full-library loading and flat top-k vector retrieval — on SkillsBench (11 technical domains) and ALFWorld (140 embodied household episodes), across three model families: Claude Sonnet 4.5, MiniMax M2.7, and GPT-5.2 Codex. It wins on reward in all six model-benchmark combinations. The peak result — 1,000-skill SkillsBench, GPT-5.2 Codex — puts GoS at 34.4% average reward against 27.4% for full loading and 21.5% for vector retrieval, while total tokens drop 56.72% versus full loading. Vector retrieval is often the weakest of the three baselines: on SkillsBench it trails full-library loading by 5–7 reward points across every model tested, because it fetches the topically obvious skill and skips the unglamorous prerequisite sitting right next to it. A library-size sweep from 500 to 2,000 skills shows full loading's token bill nearly tripling — 1.93M to 5.84M — while GoS holds close to flat, and its reward margin over both baselines widens as the library grows.