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 AWS Agentic AI [email protected] {pahwakhu,cshuaich,mdkaba,jiarongj,xiaofeim,yizhngn,sunkaral}@amazon.com · 2025

Read Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection by Michelle Yuan, Khushbu Pahwa, Shuaichen Chang Mustafa Kaba , Jiarong Jiang , Xiaofei Ma , Yi Zhang , Monica Sunkara AWS Agentic AI [email protected] {pahwakhu,cshuaich,mdkaba,jiarongj,xiaofeim,yizhngn,sunkaral}@amazon.com (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16499.txt.

Introduction

Michelle Yuan leads seven co-authors in a 2025 study on how to build AI agent teams well. A system must pick agents, tools, and models that fit the job and the budget. Past picks rely on fixed word search, which misses true skill and cost. Their frame casts the pick as a knapsack task. A knapsack task asks what fits best in a fixed budget.

A composer agent tests parts live and weighs skill, cost, and fit. Tests with Claude 3.5 Sonnet span five data sets. The composer hit the best trade-off curve of skill versus cost. Gains in success rate reached up to about 32 percent for solo setups. In team setups, success rose from 37 to 87 percent.

Catalog record

CREATORMichelle Yuan, Khushbu Pahwa, Shuaichen Chang Mustafa Kaba , Jiarong Jiang , Xiaofei Ma , Yi Zhang , Monica Sunkara AWS Agentic AI [email protected] {pahwakhu,cshuaich,mdkaba,jiarongj,xiaofeim,yizhngn,sunkaral}@amazon.com
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16499

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 AWS Agentic AI [email protected] {pahwakhu,cshuaich,mdkaba,jiarongj,xiaofeim,yizhngn,sunkaral}@amazon.com 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. 1 1 footnotetext: These authors contributed equally. 2 2 footnotetext: Work completed while at Amazon. Currently at Oracle AI. 1 Introduction The design of effective agentic systems sits at the frontier of artificial intelligence research, promising autonomous agents capable of sophisticated reasoning, tool manipulation, and collaborative problem-solving. Yet as the ecosystem of AI components expands, with proliferating models, APIs, and specialized agents, a critical bottleneck emerges: the paradox of choice [ 23 ] . While modular reuse offers clear advantages over building systems from scratch, developers face a combinatorial explosion of possible configurations, each with hidden constraints and unpredictable interactions. Traditional approaches relying on manual curation or metadata-based retrieval [ 29 ] struggle with three fundamental limitations: opaque capability descriptions that rarely match real-world performance, myopic selection criteria that ignore cost-utility trade-offs, and static architectures that break down when requirements evolve. In this paper, we introduce agent composition as a knapsack problem, where an AI system designer must select components that deliver optimal performance under cost constraints. We present the composer agent, which is responsible for selecting components through an iterative process of discovery and adaptation. Rather than treating existing tools or agents as fixed building blocks, the composer continuously probes their actual capabilities through targeted testing. The sandbox trials measure not just what a component claims to do, but how reliably it performs under varying conditions and interactions. For single-agent systems, this means assembling the right tools for the task while balancing accuracy against computational expense; for multi-agent teams, it involves orchestrating subagents whose skills complement rather than duplicate one another. What distinguishes our approach is estimating values of agentic components based on real-time performance. Where prior work treated component selection as a one-time decision based on static metadata, the composer refines its choices through empirical validation. When composing an information-seeking agent, for instance, it might initially select a specialized search tool for scientific queries, only to discover through testing that a single, generalized search tool can accommodate queries across various domains. On the other hand, a task might require deep expertise in medical fields, so the scientific search tool would be more useful than a generalized web search. This dynamic estimation capability proves particularly valuable in real-world deployments where requirements and components shift unpredictably. Our work makes three contributions: 1. A formalization of agent composition as a constrained optimization problem that jointly considers capability, cost, and compatibility, bridging gaps between modular AI design [ 10 ] and operations research [ 41 ] . 2. A workflow for the composer agent that parses task descriptions into skills, assesses utility values of agentic components based on real-time testing, and then returns optimal agentic components for a particular domain. 3. Empirical validation across diverse domains showing consistent improvements in cost-adjusted performance (up to 80% performance gains over retrieval-based baselines). Design of machine learning systems is critical as poor organization leads to unstable dependencies, pipeline jungles, and many other types of hidden technical debt [ 28 ] . Our work is a step towards optimizing this process to reduce these issues and maintain a well-composed agentic system. As we explore in subsequent sections, our approach is applicable to composing both single agents and multi-agent systems. 2 Related Work Tool Retrieval The novelty of AI agents stems from the integration of APIs with LLMs [ 27 , 24 ] . Since tools are a critical component of agents, prior works have focused on retrieval approaches to select the most appropriate tools. Qin et al. 2024 collect a large dataset of tools based on RapidAPIs and train a BERT-based tool retriever. Shi et al. 2025 note that tool retrieval is a difficult problem as commonly used retrievers fail to capture user intent and select the most relevant tools. RAG-MCP [ 9 ] combines RAG with the Model Context Protocol (MCP) to improve how LLMs select external tools. Recently, more work has emphasized the vulnerability of agents due to poor selection of tools [ 6 , 22 ] . Agentic System Design and Optimization Hu et al. 2024 introduce the problem of automated design of agentic systems (ADAS), where the goal is to “automatically create powerful agentic system designs, including inventing novel building blocks and/or combining them in new ways”. Conceptually, the building blocks of ADAS includes novel prompts, tool use, and workflows. In our paper, we focus on a subset of ADAS, which is automated composition of agentic systems. Our setting assumes that the underlying building blocks exist and the algorithmic challenge is to select the most optimal subset of those components. Common solutions to this problem include tool retrieval and agent selection. For agent selection, existing works treat the problem as graph optimization where nodes are the individual agents and edges represent communication channels. DyLAN [ 17 ] introduce the agent selection problem and train a feed-forward network to optimize the selection. AgentPrune [ 40 ] extend selection to target improving communication redundancy. Multi-agent Architecture Search [ 39 ] optimizes an agentic supernet and then will sample a multi-agent architecture in a query-dependent manner. Wu et al. 2025 jointly optimize agent prompt and tool descriptions to improve workflow efficiency. The component selection problem also relates to Distributed Constraint Optimization Problems (DCOP) [ 8 ] , where traditional agents assign values to variables to minimize a global cost function subject to constraints. DCOP techniques have been applied to service selection and composition problems, particularly for QoS-aware web service composition [ 4 ] . Knapsack Algorithms The knapsack problem, a classic optimization challenge, has been extensively studied

Read the complete text