Compositional Skill Routing for LLM Agents: Decompose, Retrieve, and Compose

LLM agents increasingly rely on external skills—reusable tool specifications—but real-world tasks often require composing multiple skills, not just selecting one. We formalize this as the Compositional Skill Routing problem: given a complex user query and a large skill library, decompose the query into atomic sub-tasks, retrieve the appropriate skill for each sub-task, and compose an executable plan. We present SKILLWEAVER, a decompose-retrievecompose framework combining an LLM task decomposer, a bi-encoder skill retriever with FAISS indexing, and a dependency-aware DAG planner. To support evaluation, we introduce COMPSKILLBENCH, a benchmark of 300 compositional queries over 2,209 real MCP server skills spanning 24 functional categories, sourced from the public MCP ecosystem. Our experiments reveal that task decomposition quality is the primary bottleneck: standard LLM decomposition reaches only 34.2% category recall at the step level. To address this, we propose Iterative Skill-Aware Decomposition (SAD), a retrieval-augmented feedback loop that iteratively aligns decomposition with available skills.

Introduction. The agent paradigm for large language models (LLMs) has evolved beyond single-turn generation to encompass tool use, planning, and multistep task execution (Schick et al., 2023; Qin et al., 2023; Patil et al., 2024). A key architectural pattern emerging in modern LLM agents is the use of skills: modular, reusable tool specifications that define specific capabilities along with instructions for when and how to invoke them (Anthropic, 2025). We use skill following Anthropic’s SKILL.md specification; skills differ from traditional APIs in their emphasis on structured natural language documentation and composability metadata. As agent skill libraries grow—with repositories already containing thousands of communitycontributed skills—a fundamental routing question arises: given a user query, which skill(s) should the agent invoke?

Discussion / Conclusion. Cascading bottleneck. Our DA-conditioned analysis (§7.5) reveals a cascading structure: decomposition granularity gates retrieval, with correct DA raising CatR@1 from 34% to 41%. SAD acts as a granularity corrector, not a vocabulary-alignment learner—∼75% of its CatR@1 gain comes from queries where vanilla produces the wrong step count, and on DA-matched queries SAD’s per-step gain is statistically zero (p=0.97). The step-countconstrained oracle baseline confirms this: pinning K to ground truth recovers DA=99.3% but only CatR@1 = 39.8% (a 36-pp residual gap to the @10 ceiling), establishing representation-level reranking, not better decomposition, as the next bottleneck. Reranking as a validated lever. A pilot in which a Qwen2.5-7B listwise reranker re-orders SAD’s top-10 candidates (Appendix K) lifts CatR@1 from 37.1% to 40.9% (+10.3% relative, p<0.01; 53/300 improved vs. 25 degraded), shifting cross-encoder reranking from speculative future work to a validated lever that composes with SAD’s structural generalization (+35.6% relative DA under category transfer, §7.9). A 50-query BGE-base spot-check (Appendix L) further raises CatR@1 to 45.1%, confirming encoder choice as an orthogonal axis.