Enterprise AI agents struggle to route subtasks to the correct tools from large skill libraries. SkillWeaver, a new framework, addresses this by creating an execution graph and selecting appropriate skills for each task node. It introduces Skill-Aware Decomposition (SAD), a feedback loop that iteratively refines tool selection. This compositional approach and feedback mechanism differ from one-shot tool-routing frameworks. SkillWeaver is relevant to AI agents orchestrating ecosystems for multi-step business operations. Experiments show SkillWeaver significantly improves accuracy and reduces token consumption by over 99%. The granularity of task decomposition is identified as the primary bottleneck for accurate tool retrieval. Current tool-use frameworks often fail with complex, compositional real-world queries that require multiple skills. SkillWeaver's three stages, Decompose, Retrieve, and Compose, break down queries, identify candidate tools, and plan execution. SAD enhances decomposition by feeding retrieved skills back to the LLM for better vocabulary and granularity alignment. This iterative approach, especially with SAD, dramatically improves decomposition accuracy, particularly for complex tasks. SkillWeaver's retrieve-and-route strategy also drastically cuts token usage compared to exposing an entire tool library at once. Developers can implement SAD and retrieval components using existing libraries, though error recovery mechanisms would need to be built separately for production.