Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Michelle Yuan, Khushbu Pahwa, Shuaichen Chang, Mustafa Kaba, Jiarong Jiang, Xiaofei Ma, Yi Zhang, Monica Sunkara
2025-10-21
Summary
This paper introduces a new way to automatically build teams of AI 'agents' and tools to solve problems, focusing on finding the best combination while staying within a budget.
What's the problem?
Currently, building these AI systems is difficult because it relies on searching for agents and tools based on descriptions that aren't always complete or accurate. It's hard to pick the right components because the system doesn't consider how well they'll actually work together, how much they cost to use, or how useful they are in a specific situation at that moment. Essentially, existing methods aren't smart enough about choosing the best tools for the job.
What's the solution?
The researchers created a system inspired by the 'knapsack problem' – a classic computer science puzzle about fitting the most valuable items into a bag with limited space. Their system has a 'composer agent' that tries out different combinations of agents and tools, testing them in real-time to see how well they perform. It then selects the best combination that balances performance, cost, and compatibility, building the AI system automatically.
Why it matters?
This research is important because it makes building complex AI systems much more efficient and reliable. By automatically finding the best combination of tools and agents, and doing so while considering cost, it allows for more scalable and adaptable AI solutions. The tests showed significant improvements in success rates and cost savings compared to existing methods, meaning AI systems can be built that are both more effective and more affordable.
Abstract
Designing effective agentic systems requires the seamless composition and integration of agents, tools, and models within dynamic and uncertain environments. Most existing methods rely on static, semantic retrieval approaches for tool or agent discovery. However, effective reuse and composition of existing components remain challenging due to incomplete capability descriptions and the limitations of retrieval methods. Component selection suffers because the decisions are not based on capability, cost, and real-time utility. To address these challenges, we introduce a structured, automated framework for agentic system composition that is 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 and facilitates scalable reuse of resources. Empirical evaluation with Claude 3.5 Sonnet 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, the online knapsack composer shows a success rate improvement of up to 31.6% in comparison to the retrieval baselines. In multi-agent systems, the online knapsack composer increases success rate from 37% to 87% when agents are selected from an agent inventory of 100+ agents. The substantial performance gap confirms the robust adaptability of our method across diverse domains and budget constraints.