Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Michelle Yuan, Khushbu Pahwa, Shuaichen Chang, Mustafa Kaba, MONICA SUNKARA, Jiarong Jiang, Xiaofei Ma, Yi Zhang
Designing effective agentic systems requires the seamless composition and integration of agents, tools, and models within dynamic and uncertain environments. Most of the existing methods rely on static, semantic retrieval approaches for the tool or agent discovery. However, effective reuse and composition of existing components remain challenging due to incomplete capability descriptions and the limitations of such retrieval methods as they overlook component capability, cost, and real-time utility; which are crucial factors for adaptive and efficient system composition. To address these challenges, we introduce a structured, automated framework for agentic system composition, inspired by the knapsack problem. Our framework enables a composer agent to systematically identify, select, and assemble an optimal set of agentic components by jointly considering performance, budget constraints, and compatibility. By dynamically testing candidate components and modeling their utility in real-time, our approach streamlines the assembly of agentic systems, facilitating scalable, adaptive and cost-effective reuse of resources while overcoming the bottlenecks of conventional discovery techniques. Empirical evaluation with Claude 3.5 Sonnet v2 across five benchmarking datasets shows that our online knapsack based composer consistently lies on the Pareto frontier, achieving higher success rates at significantly lower component costs compared to our baselines. In the single-agent setup, we observe a success rate improvement of up to 31.6% in comparison to the top performing retrieval baseline. Our online knapsack composer achieves comparable success rates to the setting wherein agent is equipped with all the tools in the tool inventory, but with 98.5% reduction in costs. Our approach also applies to the composition of multi-agent systems, boosting the success rate from 37% (top performance among the retrieval baselines) to 87%, when agents are selected from an agent inventory of 100+ agents. These results demonstrate that our approach significantly outperforms retrieval-based approaches. The substantial performance gap confirms the robust adaptability of our method across diverse domains and budget constraints.