# Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills

arXiv: https://arxiv.org/abs/2604.05333 · HTML: https://mlsanity.com/paper/2604.05333/

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- Placed in Agent skill learning and evolution, one of 16 directions in LLM agents and tool use.
- Builds on 35 of its 51 references that are in the map.
- First posted on arXiv 7 Apr 2026.

## Placed in

- LLM agents and tool use / [Agent skill learning and evolution](https://mlsanity.com/agents/agent-skill-learning-and-evolution/)

## Builds on (most cited first, 30 of 35)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [OpenAI GPT-5 System Card](https://mlsanity.com/paper/2601.03267/) (2025)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [Augmented Language Models: a Survey](https://mlsanity.com/paper/2302.07842/) (2023)
- [SkillsBench: Benchmarking How Well Agent Skills Work Across Diverse Tasks](https://mlsanity.com/paper/2602.12670/) (2026)
- [TextWorld: A Learning Environment for Text-based Games](https://mlsanity.com/paper/1806.11532/) (2018)
- [HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models](https://mlsanity.com/paper/2405.14831/) (2024)
- [Query Rewriting for Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2305.14283/) (2023)
- [SkillWeaver: Web Agents can Self-Improve by Discovering and Honing Skills](https://mlsanity.com/paper/2504.07079/) (2025)
- [On the Tool Manipulation Capability of Open-source Large Language Models](https://mlsanity.com/paper/2305.16504/) (2023)
- [Inducing Programmatic Skills for Agentic Tasks](https://mlsanity.com/paper/2504.06821/) (2025)
- [Self-Rewarding Vision-Language Model via Reasoning Decomposition](https://mlsanity.com/paper/2508.19652/) (2025)
- [Organizing, Orchestrating, and Benchmarking Agent Skills at Ecosystem Scale](https://mlsanity.com/paper/2603.02176/) (2026)
- [ToolNet: Connecting Large Language Models with Massive Tools via Tool Graph](https://mlsanity.com/paper/2403.00839/) (2024)
- [ControlLLM: Augment Language Models with Tools by Searching on Graphs](https://mlsanity.com/paper/2310.17796/) (2023)
- [SkillNet: Create, Evaluate, and Connect AI Skills](https://mlsanity.com/paper/2603.04448/) (2026)
- [A Survey of State of the Art Large Vision Language Models: Alignment, Benchmark, Evaluations and Challenges](https://mlsanity.com/paper/2501.02189/) (2025)

## Built on by (most cited first, 30 of 55)

- [Harness Updating Is Not Harness Benefit: Disentangling Evolution Capabilities in Self-Evolving LLM Agents](https://mlsanity.com/paper/2605.30621/) (2026)
- [SkillOps: Managing LLM Agent Skill Libraries as Self-Maintaining Software Ecosystems](https://mlsanity.com/paper/2605.13716/) (2026)
- [From Skill Text to Skill Structure: The Scheduling-Structural-Logical Representation for Agent Skills](https://mlsanity.com/paper/2604.24026/) (2026)
- [SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale](https://mlsanity.com/paper/2606.03056/) (2026)
- [OpenSkill: Open-World Self-Evolution for LLM Agents](https://mlsanity.com/paper/2606.06741/) (2026)
- [Group of Skills: Group-Structured Skill Retrieval for Agent Skill Libraries](https://mlsanity.com/paper/2605.06978/) (2026)
- [AutoResearch AI: Towards AI-Powered Research Automation for Scientific Discovery](https://mlsanity.com/paper/2605.23204/) (2026)
- [SKILLC: Learning Autonomous Skill Internalization in LLM Agents via Contrastive Credit Assignment](https://mlsanity.com/paper/2605.27899/) (2026)
- [SkillRAE: Agent Skill-Based Context Compilation for Retrieval-Augmented Execution](https://mlsanity.com/paper/2605.10114/) (2026)
- [SkillCAT: Contrastive, Assessment-Augmented and Topology-AwareSkill Self-Evolution for LLM Agents](https://mlsanity.com/paper/2606.13317/) (2026)
- [SkillsInjector: Dynamic Skill Context Construction for LLM Agents](https://mlsanity.com/paper/2605.29794/) (2026)
- [Generative Skill Composition for LLM Agents](https://mlsanity.com/paper/2606.32025/) (2026)
- [COMFYCLAW: Self-Evolving Skill Harnesses for Image Generation Workflows](https://mlsanity.com/paper/2607.01709/) (2026)
- [Dynamic Agent Skills: A Lifecycle Survey and Taxonomy of Evolving Skill Libraries](https://mlsanity.com/paper/2607.10113/) (2026)
- [Skill-as-Pseudocode: Refactoring Skill Libraries to Pseudocode for LLM Agents](https://mlsanity.com/paper/2605.27955/) (2026)
- [Right Family, Wrong Skill: Evaluating Risk Exposure in Agent Skill Retrieval](https://mlsanity.com/paper/2606.10388/) (2026)
- [Task Decomposition-Guided Reranking for Adaptive Agent Skill Retrieval](https://mlsanity.com/paper/2607.06283/) (2026)
- [SkillSight: Calibrating Generic Content Bias for Skill Retrieval](https://mlsanity.com/paper/2607.18785/) (2026)
- [Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective](https://mlsanity.com/paper/2608.18104/) (2026)
- [RS-Claw: Progressive Active Tool Exploration via Hierarchical Skill Trees for Remote Sensing Agents](https://mlsanity.com/paper/2605.13391/) (2026)
- [SKILL-KD: Contrastive Skill Distillation for LLM Agents](https://mlsanity.com/paper/2607.28048/) (2026)
- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [CaSKG: Counterfactual-Causal Skill Graphs for Scalable Agent Skill Retrieval](https://mlsanity.com/paper/2608.25500/) (2026)
- [Skill or Skip? Learning Selective Skill Invocation in Agentic Tasks via Dual-Granularity Preference Learning](https://mlsanity.com/paper/2606.00510/) (2026)
- [SkillCorpus: Consolidating and Evaluating the Open Skill Ecosystem for Real-World LLM Agents](https://mlsanity.com/paper/2607.15557/) (2026)
- [Progressive Agent Skill Generation via Reinforcement Learning](https://mlsanity.com/paper/2608.01678/) (2026)
- [SkillReason: Reasoning-Enhanced Agent Skill Retrieval for Implicit User Requests](https://mlsanity.com/paper/2608.08640/) (2026)
- [From Relevance to Execution Utility: Reward-Aware Dynamic Execution Gating for Skill-Based LLM Agents](https://mlsanity.com/paper/2608.09168/) (2026)
- [Skill2Query: Exploiting Skill Structure to Generate Pseudo-Queries for Agent Skill Retrieval](https://mlsanity.com/paper/2608.16071/) (2026)
- [Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees](https://mlsanity.com/paper/2608.19993/) (2026)

## Abstract (arXiv)

As LLM agents act across personal applications, web browsers, and other interfaces, their reusable skill libraries can scale to thousands of skills. This scale introduces two challenges. First, loading the full library saturates the context window, driving up token costs, hallucination, and latency. Second, semantic retrieval surfaces topically relevant skills but can miss upstream and downstream prerequisite skills, creating a prerequisite gap that leaves the retrieved bundle insufficient for execution. 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 retrieves a bounded, dependency-aware bundle through hybrid semantic-lexical seeding, reverse-aware Personalized PageRank, and context-budgeted hydration. Across SkillsBench and ALFWorld, with three model families (Claude Sonnet 4.5, MiniMax M2.7, and GPT-5.2 Codex), GoS attains the highest average reward in all six model-benchmark blocks, at a fraction of the token cost of loading the full library. On SkillsBench with GPT-5.2 Codex it raises average reward by 7.0 absolute points over full skill loading, a 25.6% relative gain, while cutting total tokens by 56.7%. Ablations isolate the mechanism: replacing reverse traversal with forward propagation costs 9.1 reward points, a larger loss than removing the graph altogether. The gain thus comes from traversing dependencies backwards, not from graph diffusion as such. A budget-matched retrieval study holding seeding, reranking, hydration, and context budget fixed reproduces the same ordering, with dependency-pair co-recovery falling from 0.654 to 0.362. Code is available at https://github.com/davidliuk/graph-of-skills