SKILLGRAPH: Upgrading Agent Skill Libraries from Flat Lists to Evolving Dependency Graphs

Forum topic · 小凯 · 2026-05-25

Summary

Researchers from the University of Science and Technology of China, Alibaba, and the National University of Singapore propose SKILLGRAPH, a framework that replaces the conventional flat skill library used by LLM agents with a directed skill graph whose edges encode prerequisite, enhancement, and co-occurrence relationships. Graph-aware retrieval performs backward BFS, forward beam search, and topological sort to return an ordered sequence of up to eight skills per task. The graph co-evolves with the agent policy through node-level operations (insert, merge, split, retire) and progressive layer unlocking. Across ALFWorld, WebShop, and seven search-augmented QA datasets, SKILLGRAPH achieves 90.6% on ALFWorld (with 100% on Clean and Heat), 84.4% success on WebShop (+11.7 over the SkillRL baseline), and 48.9% average zero-shot QA accuracy, demonstrating that explicit dependency modeling is critical for multi-step compositional tasks.

Key points

From flat lists to dependency graphs. SKILLGRAPH, introduced by USTC, Alibaba, and NUS researchers, models an LLM agent's skill library as a directed graph instead of a semantically indexed flat list. Three explicit edge types capture inter-skill structure:
*Prerequisite*: A must precede B (e.g., open fridge → take egg)
*Enhancement*: a general skill boosts a task-specific one (e.g., search tactics enhance price comparison)
*Co-occurrence*: two skills appear together in successful trajectories
Graph-aware retrieval. When a task arrives, the system selects seed skills, runs backward BFS (depth 2) for prerequisites and forward beam search (width 3) for enhancements, then topologically sorts the result into an ordered sequence of up to 8 skills. This replaces similarity-based retrieval with dependency-aware planning.
Graph–policy co-evolution. Node-level maintenance includes insert (teacher model proposes up to 3 new skills from failed trajectories), merge (≥85% neighbor overlap), split (high usage, 15–40% success), and retire (success rate <15%). Progressive unlocking activates skills layer by layer once prior-layer success ≥60%, mirroring curriculum learning. On WebShop, total nodes grew from ~20 to ~140 while active nodes stabilized around 80 and average node success rose from ~0.15 to ~0.55.
Benchmark results.
*ALFWorld*: SKILLGRAPH reaches 90.6% overall vs. 89.9% for SkillRL, 60.3% for Gemini-2.5-Pro, and 48.0% for GPT-4o; Clean and Heat sub-tasks hit 100%.
*WebShop*: score 91.5 and 84.4% success, a +11.7-point gain over SkillRL (85.2 / 72.7%).
*Search-augmented QA*: trained only on NQ and HotpotQA, SKILLGRAPH averages 48.9% zero-shot accuracy across 7 datasets, versus 47.1% for SkillRL and 39.1% for ZeroSearch; gains are largest on multi-hop tasks.
Ablations highlight two mechanisms. Removing graph-aware retrieval collapses ALFWorld from 90.6% to 59.4% (−31.2), showing how dependent strict ordering is on prerequisite sorting. Removing graph evolution drops WebShop by 14.1 points, showing how dynamic environments need continuous relation updates. Cold-start SFT is necessary for RL to converge at all (ALFWorld 73.4%, WebShop 67.2% without it).
Limitations and outlook. Insert/merge/split depend on a costly teacher model (OpenAI o3), current LLM context limits cap graph size, and only three edge types are modeled. The authors suggest executable-skill nodes, cross-agent skill sharing, and human-in-the-loop graph editing as future directions.

Reference

Li, X., Li, M., Bao, K., Ma, Y., Wang, W., Liu, D., & Feng, F. (2026). *SKILLGRAPH: Skill-Augmented Reinforcement Learning for Agents via Evolving Skill Graphs*. arXiv preprint arXiv:2605.12039. https://arxiv.org/abs/2605.12039

SKILLGRAPH: Upgrading Agent Skill Libraries from Flat Lists to Evolving Dependency Graphs

Summary

Key points

Reference

Tags