# GraSP: Graph-Structured Skill Compositions for LLM Agents

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

## Key facts

- Cited by 26 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 30 of its 45 references that are in the map.
- First posted on arXiv 20 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 30)

- [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)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [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)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Describe, Explain, Plan and Select: Interactive Planning with Large Language Models Enables Open-World Multi-Task Agents](https://mlsanity.com/paper/2302.01560/) (2023)
- [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (2022)
- [SkillRL: Evolving Agents via Recursive Skill-Augmented Reinforcement Learning](https://mlsanity.com/paper/2602.08234/) (2026)
- [InterCode: Standardizing and Benchmarking Interactive Coding with Execution Feedback](https://mlsanity.com/paper/2306.14898/) (2023)
- [AdaPlanner: Adaptive Planning from Feedback with Language Models](https://mlsanity.com/paper/2305.16653/) (2023)
- [SkillWeaver: Web Agents can Self-Improve by Discovering and Honing Skills](https://mlsanity.com/paper/2504.07079/) (2025)
- [Inducing Programmatic Skills for Agentic Tasks](https://mlsanity.com/paper/2504.06821/) (2025)
- [Behavior Trees in Robotics and AI: An Introduction](https://mlsanity.com/paper/1709.00084/) (2017)
- [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)
- [CUA-Skill: Develop Skills for Computer Using Agent](https://mlsanity.com/paper/2601.21123/) (2026)
- [Search-P1: Path-Centric Reward Shaping for Stable and Efficient Agentic RAG Training](https://mlsanity.com/paper/2602.22576/) (2026)
- [Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning](https://mlsanity.com/paper/2405.01649/) (2024)
- [AD-Bench: A Real-World, Trajectory-Aware Advertising Analytics Benchmark for LLM Agents](https://mlsanity.com/paper/2602.14257/) (2026)
- [Towards Faithful Industrial RAG: A Reinforced Co-adaptation Framework for Advertising QA](https://mlsanity.com/paper/2602.22584/) (2026)

## Built on by (most cited first, 26 of 26)

- [SkillOps: Managing LLM Agent Skill Libraries as Self-Maintaining Software Ecosystems](https://mlsanity.com/paper/2605.13716/) (2026)
- [SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale](https://mlsanity.com/paper/2606.03056/) (2026)
- [Group of Skills: Group-Structured Skill Retrieval for Agent Skill Libraries](https://mlsanity.com/paper/2605.06978/) (2026)
- [SkillCAT: Contrastive, Assessment-Augmented and Topology-AwareSkill Self-Evolution for LLM Agents](https://mlsanity.com/paper/2606.13317/) (2026)
- [Not All Skills Help: Measuring and Repairing Agent Knowledge](https://mlsanity.com/paper/2606.15390/) (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)
- [Task Decomposition-Guided Reranking for Adaptive Agent Skill Retrieval](https://mlsanity.com/paper/2607.06283/) (2026)
- [Skill Drift Is Contract Violation: Proactive Maintenance for LLM Agent Skill Libraries](https://mlsanity.com/paper/2605.10990/) (2026)
- [Understanding Rollout Error in Graph World Models](https://mlsanity.com/paper/2606.27780/) (2026)
- [CaSKG: Counterfactual-Causal Skill Graphs for Scalable Agent Skill Retrieval](https://mlsanity.com/paper/2608.25500/) (2026)
- [Harnessing Agent Skills: Architectural Patterns and a Reference Architecture for Skill-Mediated LLM Agents](https://mlsanity.com/paper/2606.20631/) (2026)
- [From Cognitive Architectures to Language Agents: A Mechanism-Level Review of Lineage, Convergence, and Migration Gaps](https://mlsanity.com/paper/2607.23942/) (2026)
- [HiSkill: Empowering LLM Agents with Hierarchical Skill Graphs](https://mlsanity.com/paper/2607.25853/) (2026)
- [SkillZip: Contract-Preserving Graph Compression for Scalable Agent Skill Libraries](https://mlsanity.com/paper/2608.05604/) (2026)
- [SkillAligner: Treating Retrieved Skills as Adaptable Drafts at Execution Time](https://mlsanity.com/paper/2608.06880/) (2026)
- [TROVE: Adaptive Agent Skill Orchestration via Trace-Grounded Route Validation and Editing](https://mlsanity.com/paper/2609.05019/) (2026)
- [TTSE: A Two-Track Online Self-Evolution Framework](https://mlsanity.com/paper/2609.24289/) (2026)
- [Experience Memory Graph: One-Shot Error Correction for Agents](https://mlsanity.com/paper/2607.13884/) (2026)
- [Towards a Systems Foundation for Agentic Skills: Architecture, Lifecycle, and Security](https://mlsanity.com/paper/2608.29596/) (2026)
- [Trace2Tower: Transition-Aware EigenTrace Induction of Multi-Level Skills for LLM Agents](https://mlsanity.com/paper/2609.05261/) (2026)
- [SkillAlign: Aligning Skill Interfaces for LLM-based Agents](https://mlsanity.com/paper/2609.07255/) (2026)
- [GraphSkillEvo: Evolutionary Optimization of Graph-Structured Agent Skills](https://mlsanity.com/paper/2609.21749/) (2026)
- [ControlScope: Workflow Revision and Reliability in LLM Agents](https://mlsanity.com/paper/2609.34313/) (2026)
- [Retrieval-Augmented Skill Optimization via Cross-Harness Adaptation](https://mlsanity.com/paper/2609.38024/) (2026)
- [An Empirical Study of Agent Skills' Downstream Utility](https://mlsanity.com/paper/2610.08875/) (2026)

## Abstract (arXiv)

Skill ecosystems for LLM agents have matured rapidly, yet recent benchmarks show that providing agents with more skills does not monotonically improve performance -- focused sets of 2-3 skills outperform comprehensive documentation, and excessive skills actually hurt. The bottleneck has shifted from skill availability to skill orchestration: agents need not more skills, but a structural mechanism to select, compose, and execute them with explicit causal dependencies. We propose GraSP, the first executable skill graph architecture that introduces a compilation layer between skill retrieval and execution. GraSP transforms flat skill sets into typed directed acyclic graphs (DAGs) with precondition-effect edges, executes them with node-level verification, and performs locality-bounded repair through five typed operators -- reducing replanning from O(N) to O(d^h). Across ALFWorld, ScienceWorld, WebShop, and InterCode with eight LLM backbones, GraSP outperforms ReAct, Reflexion, ExpeL, and flat skill baselines in every configuration, improving reward by up to +19 points over the strongest baseline while cutting environment steps by up to 41%. GraSP's advantage grows with task complexity and is robust to both skill over-retrieval and quality degradation, confirming that structured orchestration -- not larger skill libraries -- is the key to reliable agent execution.