# SkillGraph: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 32 of its 37 references that are in the map.
- First posted on arXiv 12 May 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- 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 32)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [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)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory](https://mlsanity.com/paper/2504.19413/) (2025)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory](https://mlsanity.com/paper/2509.25140/) (2025)
- [SkillRL: Evolving Agents via Recursive Skill-Augmented Reinforcement Learning](https://mlsanity.com/paper/2602.08234/) (2026)
- [ZeroSearch: Incentivize the Search Capability of LLMs without Searching](https://mlsanity.com/paper/2505.04588/) (2025)
- [SimpleMem: Efficient Lifelong Memory for LLM Agents](https://mlsanity.com/paper/2601.02553/) (2026)
- [EvolveR: Self-Evolving LLM Agents through an Experience-Driven Lifecycle](https://mlsanity.com/paper/2510.16079/) (2025)
- [MemRL: Self-Evolving Agents via Runtime Reinforcement Learning on Episodic Memory](https://mlsanity.com/paper/2601.03192/) (2026)
- [Agent Skills for Large Language Models: Architecture, Acquisition, Security, and the Path Forward](https://mlsanity.com/paper/2602.12430/) (2026)
- [Memp: Exploring Agent Procedural Memory](https://mlsanity.com/paper/2508.06433/) (2025)
- [MemEvolve: Meta-Evolution of Agent Memory Systems](https://mlsanity.com/paper/2512.18746/) (2025)

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

- [Skill0.5: Joint Skill Internalization and Utilization for Out-of-Distribution Generalization in Agentic Reinforcement Learning](https://mlsanity.com/paper/2605.28424/) (2026)
- [Self-Play Meets Skill Evolution: Self-Evolving Search Agents that Pose, Solve, and Remember](https://mlsanity.com/paper/2607.29468/) (2026)
- [Coalition-Aware Skill Reliability for Self-Evolving Agents](https://mlsanity.com/paper/2608.22610/) (2026)
- [SkillGLoW: Procedural-Family Skill Consolidation for Self-Improving Agents on Long-Horizon Task Streams](https://mlsanity.com/paper/2609.02217/) (2026)
- [SkillTrace: Traversing a Query-Skill Graph for Composable LLM Agents](https://mlsanity.com/paper/2608.02356/) (2026)
- [TROVE: Adaptive Agent Skill Orchestration via Trace-Grounded Route Validation and Editing](https://mlsanity.com/paper/2609.05019/) (2026)
- [SE-GoS: Self-Evolving Graph-of-Skills for Skill Library at Scale](https://mlsanity.com/paper/2609.08228/) (2026)
- [GraphSkillAA: Attribution-Guided Skill-Graph Updating with Targeted Validation and Rollback](https://mlsanity.com/paper/2609.20455/) (2026)
- [Trace2Tower: Transition-Aware EigenTrace Induction of Multi-Level Skills for LLM Agents](https://mlsanity.com/paper/2609.05261/) (2026)
- [Who Maintains Agent Skills? A Longitudinal Study of Human-Governed, AI-Assisted Skill Maintenance](https://mlsanity.com/paper/2609.05677/) (2026)
- [RLHarness: Co-evolving Procedural Skills with Reinforcement Learning for Long-horizon Multimodal Reasoning](https://mlsanity.com/paper/2609.32326/) (2026)
- [SkillRubric: Co-Evolving Actor Guidance and Evaluator Rubrics for Multimodal Agents](https://mlsanity.com/paper/2609.34557/) (2026)
- [GenMem: Generative Symbolic Memory for Self-Evolving Harness](https://mlsanity.com/paper/2609.34633/) (2026)
- [SkillFM: Generating Skills for LLM Agents via Latent Flow Matching](https://mlsanity.com/paper/2609.39382/) (2026)
- [UniSkill: Learning Actor-Aligned Skill Proposals for an Evolving Policy](https://mlsanity.com/paper/2610.10164/) (2026)

## Abstract (arXiv)

Skill libraries enable large language model agents to reuse experience from past interactions, but most existing libraries store skills as isolated entries and retrieve them only by semantic similarity. This leads to two key challenges for compositional tasks. Firstly, an agent must identify not only relevant skills but also how they depend on and build upon each other. Secondly, it also makes library maintenance difficult, since the system lacks structural cues for deciding when skills should be merged, split, or removed. We propose SKILLGRAPH, a framework that represents reusable skills as nodes in a directed graph, with typed edges encoding prerequisite, enhancement, and co-occurrence relations. Given a new task, SKILLGRAPH retrieves not just individual skills, but an ordered skill subgraph that can guide multi-step decision making. The graph is continuously updated from agent trajectories and reinforcement learning feedback, allowing both the skill library and the agent policy to improve together. Experiments on ALFWorld, WebShop, and seven search-augmented QA tasks show that SKILLGRAPH achieves state-of-the-art performance against memory-augmented RL methods, with especially large gains on complex tasks that require composing multiple skills.