From Skills to Stages: Stage-Aware Graph Retrieval for Relevant Skills in Large-Scale Agent Skill Libraries

Agents based on Large Language Models (LLMs) increasingly rely on reusable skills. As these agents become deeply integrated with personal applications, web browsers, and various interactive interfaces, the scale of skill libraries has expanded to thousands of entries. Currently, numerous methods have attempted to address this challenge through skill retrieval. However, existing approaches treat each skill as an opaque monolith, matching solely based on holistic descriptions or global features. Since a skill actually consists of multiple execution stages—each with its own independent goals, preconditions, and execution outcomes—compressing this internal structure into a single representation makes it impossible to distinguish between skills that have similar descriptions but different execution workflows. To address the aforementioned limitations, we propose the Stage-aware Skill Graph (SSG), which explicitly models two node hierarchies during graph construction: the skill level and the internal stage level. During inference, we introduce a stage-aware retrieval mechanism that combines stage seed selection, stage-aware PageRank, and stage-aware query rewriting to retrieve complementary skills for different stages of task execution. Experiments on ALFWorld, SkillsBench, and AgentSkillOS with three representative models demonstrate the effectiveness of our approach. SSG achieves a task success rate of 76.4% on ALFWorld, outperforming the strongest baseline by 8.5 percentage points, and achieves up to a 7.8 percentage-point improvement over the strongest baseline on SkillsBench. Across all three benchmarks and model settings, SSG consistently improves end-to-end task performance, highlighting the benefit of stage-aware skill retrieval for multi-stage task execution.