Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills
| Authors | Dawei Li et al. |
| Year | 2026 |
| HF Upvotes | 19 |
| arXiv | 2604.05333 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
Skill usage has become a core component of modern agent systems and can substantially improve agents' ability to complete complex tasks. In real-world settings, where agents must monitor and interact with numerous personal applications, web browsers, and other environment interfaces, skill libraries can scale to thousands of reusable skills. Scaling to larger skill sets introduces two key challenges. First, loading the full skill set saturates the context window, driving up token costs, hallucination, and latency. In this paper, we present Graph of Skills (GoS), an inference-time structural retrieval layer for large skill libraries. GoS constructs an executable skill graph offline from skill packages, then at inference time retrieves a bounded, dependency-aware skill bundle through hybrid semantic-lexical seeding, reverse-weighted Personalized PageRank, and context-budgeted hydration. On SkillsBench and ALFWorld, GoS improves average reward by 43.6% over the vanilla full skill-loading baseline while reducing input tokens by 37.8%, and generalizes across three model families: Claude Sonnet, GPT-5.2 Codex, and MiniMax. Additional ablation studies across skill libraries ranging from 200 to 2,000 skills further demonstrate that GoS consistently outperforms both vanilla skills loading and simple vector retrieval in balancing reward, token efficiency, and runtime.
Engineering Breakdown
Plain English
This paper addresses a critical scaling problem in agent systems: when skill libraries grow to thousands of reusable functions (for controlling apps, browsers, APIs), loading them all into the LLM context window becomes prohibitively expensive in tokens, latency, and hallucination rates. The authors propose Graph of Skills (GoS), a retrieval system that builds a dependency graph of skills offline, then at inference time intelligently selects only the relevant subset of skills needed for the current task. The approach combines structural graph reasoning with hybrid retrieval to keep context bounded while maintaining task performance, enabling agents to work with very large skill libraries that would otherwise be impractical.
Core Technical Contribution
The core novelty is framing skill selection as a graph traversal and retrieval problem rather than treating all skills as flat candidates for context inclusion. GoS constructs an executable skill dependency graph offline—mapping which skills call which other skills and their input/output relationships—then uses this structure at inference time to retrieve only task-relevant skills along with their necessary dependencies. This dependency-aware retrieval is the key insight: by understanding skill relationships, the system can guarantee that selected skills will actually work together and have their prerequisites available. The hybrid retrieval component likely combines semantic matching (finding skills related to the task) with structural constraints (ensuring the selected bundle is executable), which is a departure from prior work that treated skill selection as pure semantic ranking.
How It Works
At the high level, GoS operates in two phases: offline graph construction and online retrieval. During offline phase, the system ingests a skill package (potentially thousands of skills with descriptions, signatures, and dependencies) and builds a directed graph where nodes are skills and edges represent dependencies (skill A calls skill B). At inference time, given a user task, the system performs hybrid retrieval: it identifies candidate skills semantically relevant to the task using embedding similarity or LLM ranking, then performs a bounded traversal of the dependency graph to collect all prerequisite skills needed to execute those candidates. The 'bounded' constraint is critical—it limits the total number of skills retrieved to prevent context window saturation. Finally, the retrieved skill bundle (skill definitions, signatures, and call patterns) is injected into the LLM context, allowing the agent to generate executable skill compositions that respect the actual dependencies in the system.
Production Impact
For teams building multi-tool agent systems (RPA, autonomous browsing, API orchestration), this directly solves the skill scaling bottleneck. Without GoS, you hit a hard ceiling: with 100+ skills, context becomes unusable; with thousands, it's economically infeasible. Adopting this approach means you can confidently scale your skill library to 5000+ functions without exploding token costs or latency—a real multiplier for agent capability. The trade-off is infrastructure complexity: you need to maintain accurate skill dependency metadata, build and validate the skill graph offline, and ensure the graph stays in sync as skills are added or modified. There's also a subtle reliability risk: if the dependency graph is incorrect or incomplete, the agent may be given skills that don't actually work together. In production, this requires robust skill metadata validation, automated graph consistency checks, and careful testing of new skill additions before they enter the retrieval system.
Limitations and When Not to Use This
The approach assumes skills have well-defined dependencies and clear metadata—in messy real-world systems with implicit side effects or version-dependent behavior, the dependency graph can become inaccurate or incomplete, breaking the retrieval guarantees. The paper doesn't address how to handle dynamic skill sets where skills are added/removed frequently or how to update the graph in real time without offline recomputation. There's also an inherent brittleness: if a skill's actual behavior diverges from its metadata (e.g., a skill changes what APIs it calls), the retrieved bundle could still fail despite being 'dependency-correct' according to the graph. The bounded retrieval mechanism needs careful tuning—select too few skills and you lose necessary capabilities; select too many and you're back to the original context saturation problem. Follow-up work likely needs to address automatic metadata extraction, graph updates under skill evolution, and recovery mechanisms when retrieved skill bundles fail at runtime.
Research Context
This paper builds on the growing body of work in agent architectures and tool use, building from foundation model agents (Toolformer, ReAct) that use external skills. Prior work has treated skill selection as a pure retrieval problem (ranking skills by semantic relevance), but GoS brings structural/graph reasoning into the picture, similar to how knowledge graphs and structured retrieval have improved RAG systems. The work also relates to recent scaling challenges in context windows—as models get larger and systems more complex, the naive approach of dumping all available information into context becomes untenable, driving research into learned retrieval (ColBERT, DPR) and structured selection mechanisms. This paper likely opens directions in graph-aware retrieval, skill composition planning, and hierarchical agent design where agents reason about tool dependencies rather than just relevance.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::