Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills
Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu, Shihang Gui, Yongbei Kuang, Lichao Sun, [0.5ex] University of Pennelvenia · 2026
Read Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills by Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu, Shihang Gui, Yongbei Kuang, Lichao Sun, [0.5ex] University of Pennelvenia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-05333.txt.
Introduction
Liu and six colleagues address a growth trap for AI agents whose skill libraries run to thousands. Loading everything swamps the context window, while simple topic search drops skills a task needs as prerequisites. Their Graph-of-Skills layer builds a graph of skill dependencies in advance, then retrieves a bounded bundle by walking dependencies backwards within a context budget. Across two benchmarks and three families it topped full loading in every block, lifting reward by seven points on one test while cutting token use by about 57 percent.
Catalog record
| CREATOR | Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu, Shihang Gui, Yongbei Kuang, Lichao Sun, [0.5ex] University of Pennelvenia |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81435 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.05333
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph of Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills Dawei Liu, Zongxia Li, Hongyang Du, Xiyang Wu, Shihang Gui, Yongbei Kuang, Lichao Sun, [0.5ex] University of Pennelvenia 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 % 43.6\% over the vanilla full skill-loading baseline while reducing input tokens by 37.8 % 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. 1 Introduction Large Language Model (LLM) agents solve complex technical tasks by invoking external tools, APIs, and reusable skills ( 32 ; 22 ) . As these tools and skills grow from dozens of tools to thousands or even tens of thousands of candidates ( 29 ; 13 ; 40 ; 30 ) , the core challenge shifts from deciding whether to use a skill to retrieving the most relevant set of skills that is sufficient for a task. 33 already shows that skill retrieval itself is now a major bottleneck in realistic tool ecosystems. Two common strategies are widely used for handling large skill libraries. Vanilla Skills ( 1 ) prepends the entire skill set to the context window. This can work for small toolsets, but it scales poorly: token cost grows linearly with library size, and critical domain constraints become easy for the model to overlook inside an overloaded context ( 18 ) . An alternative is vector-based retrieval ( 11 ; 39 ) , which improves efficiency by retrieving semantically similar skills. However, semantic proximity does not imply executable sufficiency. In many engineering tasks, the top semantic match is a high-level solver, while the actual solution also requires a lower-level parser, converter, setup utility, or domain-specific preprocessor that is semantically weak but functionally necessary ( 30 ; 28 ; 29 ) (Figure 1 ). Figure 1: Conceptual comparison between flat skill loading, vector retrieval, and Graph of Skills (GoS). Vanilla Skills prepends the full skill library to the prompt, so relevant constraints and prerequisite skills become buried in an overloaded context. Vector Skills improves efficiency by returning semantically similar skills, but it can still miss a functionally required prerequisite outside the retrieved set, creating the prerequisite gap. Graph of Skills starts from hybrid semantic-lexical seeds and then performs structure-aware retrieval to recover prerequisite skills and assemble a compact execution bundle. We present Graph of Skills (GoS), an inference-time structural retrieval layer for large local skill libraries to combat limitations of the previous two approaches. GoS constructs a directed multi-relational graph over local skill packages, where nodes are executable skills and edges encode prerequisite and workflow structure. At query time, GoS uses semantic and lexical signals only to identify a small seed set, then applies reverse-weighted Personalized PageRank (PPR) ( 6 ; 41 ) to recover additional skills that are structurally important for execution. The result is a bounded skill bundle that is both relevant and closer to dependency-complete than isolated top- k retrieval. This problem setting is complementary to repository-scale skill infrastructures such as SkillNet and AgentSkillOS ( 17 ; 12 ) . Those works focus on creating, organizing, evaluating, and orchestrating large skill ecosystems. GoS targets a critical downstream question: if a large local skill library already exists, how should an agent retrieve the smallest and most relevant executable subset that is sufficient for the current task? Rather than exposing only keyword or vector search over repository metadata, GoS parses each skill specification into executable fields such as I/O schemas, tooling, script entrypoints, and stable source paths, constructs typed dependency and workflow edges, and retrieves a bounded bundle through graph diffusion plus reranking. Our contributions are as follows: (1) We introduce GoS, an agentic skill usage pipeline that combines offline graph construction with inference-time structural retrieval to improve skill selection accuracy while reducing input token consumption. (2) We evaluate GoS on the 1,000-skill SkillsBench setting and find that, compared to the full skill-loading baseline, GoS improves average reward by 43.6% and reduces input tokens by 37.8% across two benchmarks and three model families. Additional ablation studies confirm that this pattern holds consistently across skill library sizes ranging from 200 to 2,000 skills. 2 Related Work Tool Use, Tool Discovery, and Tool Retrieval for Agents. Early research on tool-augmented language models focuses on relatively small, fixed toolsets, where the primary challenge is deciding when to invoke a tool and formatting the call correctly ( 32 ; 22 ) . As tool sets grow from dozens of tools to thousands ( 29 ; 13 ; 40 ; 30 ) and context windows continue to expand ( 37 ; 15 ; 3 ) , the problem shifts toward tool discovery and tool retrieval . Systems and benchmarks such as Gorilla 29 , API-Bank 13 , ToolBench-style evaluations 40 , and ToolLLM 30 show that large tool universes require scalable retrieval over API descriptions and tool documentation. ToolNet ( 19 ) introduces graph structure into large-scale tool access, with the objective to connect models to broad tool ecosystems rather than recover dependency-complete local executable bundles. However, 33 shows that tool retrieval is itself a difficult modeling problem and that generic dense retrievers are often poorly aligned with real tool-use needs ( 33 ) . Skill Repositories, Ecosystems, and Benchmarks. Recent systems increasingly treat agent skills as reusable assets rather than ad hoc prompts ( 1 ; 17 ; 12 ) . SkillNet ( 17 ) is a repository-scale skill library in this space, supporting skill creation from heterogeneous sources, multi-dimensional evaluation, ontology construction, and relational analysis over large skill collections. AgentSkillOS ( 12 ) similarly advocates for an ecosystem-level approach, emphasizing that massive skill libraries must be systematically categorized for efficient retrieval and dynamically chained together to execute complex, multi-step tasks. SkillsBench ( 14 ) shows that curated external skills can improve agent performance, while also exposing that simply having many skills available does not guarantee reliable and safe use. Other systems and registries such as SkillsMP, ClawHub, and LangSkills similarly support packaging, discovery, and search over large skill collections ( 38 ; 26 ; 16 ; 10 ) . These skill repository platforms lower the cost of packaging, publishing, browsing, and searching large skill collections, but their primary interface remains entry-level search or distribution over individual skills or bundles. Graph-Based Retrieval and Relational Memory.