# SE-GoS: Self-Evolving Graph-of-Skills for Skill Library at Scale

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

## Key facts

- Cited by 1 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 42 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Placed in

- LLM agents and tool use / [Agent skill learning and evolution](https://mlsanity.com/agents/agent-skill-learning-and-evolution/)
- Synthetic data and self-improvement for LLMs / [Self-evolving LLM agents](https://mlsanity.com/synth/self-evolving-llm-agents/)

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [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)
- [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)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [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)
- [Agent Workflow Memory](https://mlsanity.com/paper/2409.07429/) (2024)
- [SkillsBench: Benchmarking How Well Agent Skills Work Across Diverse Tasks](https://mlsanity.com/paper/2602.12670/) (2026)
- [HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models](https://mlsanity.com/paper/2405.14831/) (2024)
- [TextGrad: Automatic "Differentiation" via Text](https://mlsanity.com/paper/2406.07496/) (2024)
- [SkillWeaver: Web Agents can Self-Improve by Discovering and Honing Skills](https://mlsanity.com/paper/2504.07079/) (2025)
- [CRAFT: Customizing LLMs by Creating and Retrieving from Specialized Toolsets](https://mlsanity.com/paper/2309.17428/) (2023)
- [On the Tool Manipulation Capability of Open-source Large Language Models](https://mlsanity.com/paper/2305.16504/) (2023)
- [SkillRouter: Skill Routing for LLM Agents at Scale](https://mlsanity.com/paper/2603.22455/) (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)
- [Graph-of-Skills: Dependency-Aware Structural Retrieval for Massive Agent Skills](https://mlsanity.com/paper/2604.05333/) (2026)
- [Retrieval Models Aren't Tool-Savvy: Benchmarking Tool Retrieval for Large Language Models](https://mlsanity.com/paper/2503.01763/) (2025)
- [ToolRerank: Adaptive and Hierarchy-Aware Reranking for Tool Retrieval](https://mlsanity.com/paper/2403.06551/) (2024)
- [Towards Completeness-Oriented Tool Retrieval for Large Language Models](https://mlsanity.com/paper/2405.16089/) (2024)
- [Efficient Algorithms for Personalized PageRank Computation: A Survey](https://mlsanity.com/paper/2403.05198/) (2024)

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

- [Retrieval-Augmented Skill Optimization via Cross-Harness Adaptation](https://mlsanity.com/paper/2609.38024/) (2026)

## Abstract (arXiv)

LLM agents use large libraries of reusable skills. At thousands of skill entries, retrieval becomes the bottleneck. Graph-of-Skills (GoS) retrieves dependency-aware bundles from a typed skill graph, and SkillDAG shows that such a graph can accumulate execution-backed structure online. Neither asks whether execution traces can be distilled into a better retrieval graph that generalizes to unseen tasks. We present Self-Evolving Graph-of-Skills (SE-GoS), which treats the retrieval graph as an index rather than a learned representation: the graph is maintained from execution traces while the retrieval pipeline, the skill library, and the model stay fixed. SE-GoS applies three updates: (1) topology, which induces relations from execution evidence and retracts an avoid edge only after repeated successful co-use; (2) edge-weight, which softly attenuates unsupported semantic edges and reinforces incoming edges to used skills; and (3) node-description, which updates retrieval-facing descriptions stored on graph nodes ranked too low. On SkillsBench, one evolution round lifts average reward from 52.4% to 59.4%, above full-library loading, vector retrieval, static GoS, and SkillDAG, and this ordering repeats on all three backbones. Retrieval over the evolved graph spends about two-thirds of the input tokens that loading the full library costs. Repeating the round does not help. The same graph improves a held-out split it never saw from 52.9% to 58.3%, so what it accumulates transfers rather than memorizes traces. Skill graphs can therefore be improved from execution experience without model training, retrieval-algorithm changes, skill-content modifications, or a model judging which skills are related.