Source-linked AI summary
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
TL;DR
Static retrieval and incomplete capability descriptions make cost- and utility-aware component selection difficult. The paper formulates agent composition as a knapsack problem and uses a composer that tests components to estimate their value. Across diverse domains, it reports performance gains over retrieval-based baselines.
Problem
Static retrieval and manual curation struggle with opaque capability descriptions, cost-utility trade-offs, and changing requirements.
Source: §1 · p. 1Method
Results
Up to 80% performance gains over retrieval-based baselines are reported across diverse domains.
Source: §1 · p. 2Takeaways & Limitations
The composer assesses components by value-to-price ratio to select them for single-agent or multi-agent systems.
Source: §7 · p. 10The approach assumes tasks have clear descriptions, so its stated scope does not cover ambiguous goals requiring further exploration.
Source: §6 · p. 10
Abstract
from arXiv · showhide
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 Introduction
The paper frames component composition as a response to the limits of static retrieval and proposes selecting agentic components through cost- and performance-aware testing. It applies this approach to both single-agent and multi-agent systems.
1 Introduction
- Static metadata retrieval and manual curation struggle with opaque capability descriptions, cost-utility trade-offs, and evolving requirements.The introduction describes these as three limitations of traditional approaches.Source: §1 · p. 1
- The composer treats selection as a constrained knapsack problem and iteratively probes component capabilities through targeted testing.The approach balances task accuracy against computational expense for single agents and complementary skills for multi-agent teams.Source: §1 · p. 2
- Real-time testing can change which component is most useful, depending on task needs and shifting requirements.A generalized search tool may work across domains, while scientific search may better serve tasks requiring deep medical expertise.Source: §1 · p. 2
- Up to 80% performance gains over retrieval-based baselines are reported across diverse domains.The contribution is framed as improved cost-adjusted performance.Source: §1 · p. 2
- The approach is presented as applicable to composing both single agents and multi-agent systems, with better organization positioned as a step toward reducing technical debt.The passage associates poor system organization with unstable dependencies and pipeline jungles.Source: §1 · p. 2
2 Related Work
Related work spans tool retrieval, automated agent-system design, and knapsack optimization. This paper focuses on selecting existing components, with composition framed around an inventory and task description.
Tool Retrieval
Agentic System Design and Optimization
- ADAS covers automated creation of agent-system designs, while this paper narrows the task to selecting an optimal subset of existing components [10].Related agent-selection approaches include graph optimization and query-dependent architecture sampling [17] [40] [39].Source: §2 · p. 2
- Agent composition starts with an existing component inventory and task description, then selects components to build a deployable agent.Source: Figure 1 · p. 3
- DCOP models assign values to variables to minimize global cost under constraints, and has been applied to QoS-aware service composition.Source: §2 · p. 3
Knapsack Algorithms
- Offline knapsack methods assume all items are known in advance, whereas online methods process items sequentially without future information.The section names dynamic programming and branch-and-bound as offline methods, and describes ZCL's value-to-weight threshold [41].Source: §2 · p. 3
3 Problem Definition
Agent composition is formulated as selecting existing components to maximize task success under a budget. The formulation accommodates uncertain component values, interactions, and changing inventories.
3 Problem Definition
- Agent composition selects an optimal subset of existing components to maximize task success under a budget.The broader ADAS vision includes tools, models, prompts, and workflows, while this paper focuses on selecting and combining existing inventory components.Source: §3 · p. 3
- The task success probability reflects both individual component performance and how components work together.Source: §3 · p. 3
- Component values are initially uncertain and must be estimated through iterative testing; interactions can be synergistic or detrimental.Changing inventories also require methods that support incremental recomputation.Source: §3 · pp. 3–4
- The proposed workflow generates skills and queries, retrieves candidate components, tests them individually, and accepts them when their value-to-price ratio meets the threshold.Source: Figure 2 · p. 4
- The formulation is relevant to settings such as internal tool registries and commercial API inventories, where the challenge is finding cost-effective compositions that meet performance requirements.Source: §3 · p. 4
4 Composer Agents: From Semantic Retrieval to Knapsack Selection
The paper compares composers ranging from returning the full inventory to retrieval-based selection and knapsack optimization. Its online composer tests candidates to estimate their value and selects components under a budget using an online knapsack rule.
Identity Composer
- The identity composer returns every component in the inventory, without task-specific selection.It is a primitive composer defined as f(A, τ, B) = A.Source: §4 · p. 4
Retrieval Composer
- The retrieval composer parses the task into required skills and retrieves the top-ranked component for each skill using its name and description.The selected set consists of the top-1 retrieval results for the generated skills.Source: §4 · p. 4
Offline Knapsack Composer
- The offline knapsack composer retrieves top-K candidates per skill, assigns component value from semantic similarity, and uses linear programming to solve a multiple-choice knapsack problem.Source: §4 · p. 5
Online Knapsack Composer
- The online composer tests candidate components to assess their true value, then applies ZCL’s capacity-dependent threshold to accept items whose value-to-cost ratio is high enough.The composer generates task skills and test questions, then evaluates candidate components against them.Source: §4 · p. 5
- Unlike retrieval-based composers, online knapsack selects components using tested value, which is unknown before evaluation.Its value-to-cost threshold changes with the capacity already filled in the knapsack.Source: §4 · p. 5
- During sandboxing, broken components are not tested again, and skills already covered by a selected tool are not reassessed for other candidates.These shortcuts are described as runtime optimizations.Source: §4 · p. 6
5 Experiments
The experiments evaluate both tool selection for single agents and specialist selection for multi-agent teams by fixing the composed setup and running benchmark evaluations. Online knapsack leads the reported cost–success comparisons in both settings.
5 Experiments
- The experiments compose either single-agent tools or multi-agent specialists for a task, then fix the selected setup and evaluate it on benchmarks.The paper presents a subset of results in the main text and full results in the appendix.Source: §5 · p. 6
5.1 Composing Single Agents
- Single-agent tests used a 120-tool inventory, CodeAct, three Claude models, and GAIA, SimpleQA, and MedQA; knapsack budgets were $10 or $30.The approaches select tools for a CodeAct agent before evaluation on the target task.Source: §5.1 · pp. 6–8
- On all three datasets, online knapsack with AvaTaR ($30 budget constraint) had higher success than identity at much lower cost; without AvaTaR, it was on the Pareto frontier for GAIA and MedQA.Retrieval-only and offline-knapsack approaches tended to fare worse across the three datasets.Source: Figure 3 · p. 7, §5.1 · p. 8
5.2 Composing Multi-Agent Systems
- Multi-agent tests used a hierarchical supervisor-and-specialist benchmark in travel and mortgage, augmented the inventory to about 117 agents, and set each agent’s price to $1.Budgets were $3 and $6; the uniform price was chosen to isolate selection strategies in a setting with no meaningful runtime or API-cost variation.Source: §5.2 · p. 8
- In both travel and mortgage, online knapsack ($6) was the highest-performing approach on the Pareto frontier for overall goal success versus selection budget.Identity had lower success in this setting, where the supervisor struggled to delegate across more than 100 diverse agents.Source: Figure 4 · p. 9, §5.2 · p. 9
6 Discussion
The discussion attributes stronger composition results to selecting components by tested utility rather than relying on descriptions alone. It also identifies task clarity, trial time, and prompt-optimization regressions as limitations.
6 Discussion
- Prompt optimization is reported to improve SimpleQA, with the authors attributing the gain to clearer search, tool-use, source-verification, and error-recovery guidance.Source: §6 · p. 9
- Similar online-knapsack results are reported across models, including Llama 4 and Qwen 2.5, and across multiple runs.Source: §6 · p. 9
- In multi-agent composition, online knapsack avoids distractor agents that retrieval-based methods select despite lacking the capabilities to complete tasks.The discussion gives offline knapsack’s selection of five incapable travel agents as an example.Source: §6 · pp. 9–10
- Online knapsack’s selected tools are described as precise and well-covered, while retrieval misses relevant tools and offline knapsack includes irrelevant ones.For GAIA and SimpleQA, online knapsack selects an effective web-search tool; offline knapsack selects a cheaper option with severe throttling limits.Source: §6 · p. 9, Table 2 · p. 10
- The approach assumes clearly specified tasks, sandbox trials take 10–30 minutes depending on budget, and prompt optimization regresses in some settings.The authors also flag possible addition of malicious components without careful monitoring.Source: §6 · p. 10
7 Conclusion
The conclusion frames agent composition as budget-constrained knapsack selection and describes an online composer that tests components to estimate their utility. It points to learning composition choices from past experience as future work.
7 Conclusion
- The paper formalizes selecting existing agentic components as agent composition and casts selection as optimizing success rate under a constrained budget.Source: §7 · p. 10
- The composer combines semantic discovery with component testing, then uses assessed value-to-price ratios to decide whether to select components.Source: §7 · p. 10
- The experiments cover both tool selection for single agents and composition of multi-agent systems from existing sub-agents.Source: §7 · p. 10
- The conclusion identifies learning how to compose from past experience as a direction for future work.Source: §7 · p. 10
A.1 Skill and Query Generation Prompt
The skill-and-query generation prompt decomposes a task into skills and creates test queries with plans for judging components.
A.1 Skill and Query Generation Prompt
- The workflow combines skill and query generation in one step and also asks for reference plans to support judging.Source: §A.1 · p. 14
- The prompt requests no more than six distinct skills, each with a description, an importance rating from 1 to 10, and three test queries with plans.Queries should require a tool but take no more than one step or tool call.Source: §A.1 · p. 14
- Each skill’s output schema contains its name, importance, description, and a list of query-and-plan pairs.Source: §A.1 · p. 14
A.2 Prompts for Sandbox Judgements
Sandbox judgements assess whether a tool or sub-agent helps answer a query and whether it is broken. The criteria differ between single-agent and multi-agent trials.
A.2 Prompts for Sandbox Judgements
- The sandbox uses separate judgement prompts for single-agent tools and multi-agent sub-agents, evaluating helpfulness and whether the component is broken.Source: §A.2 · p. 14
- For single-agent trials, a tool is helpful only if it contributed to answering the query; repeated errors or potentially harmful effects mark it broken.Source: §A.2 · p. 14
- For multi-agent trials, an agent is helpful when it uses the right tools and answers the query; toxicity, harm, irrelevance, or unavailable-tool calls can mark it broken.An agent that cannot complete the task but says so is not marked broken under the prompt.Source: §A.2 · pp. 14–15
- Both experiments use the same output schema, recording helpfulness, broken status, and a reason.Source: §A.2 · p. 15
A.3 Modifications to ZCL Algorithm for Online Knapsack Composer
The composer reduces sandbox trials by stopping tests of broken components and avoiding further selection for skills already covered. An extended version of the algorithm is also provided.
A.3 Modifications to ZCL Algorithm for Online Knapsack Composer
- The modifications are presented as minor changes to the ZCL algorithm intended to reduce sandbox trials.Source: §A.3 · p. 15
- Two trial-saving modifications stop sandboxing broken components and skip further component selection for skills already covered.A component is marked broken to prevent retesting; a skill is marked covered after a component passes the judge’s assessment and is equipped.Source: §A.3 · p. 15
- An extended version of the algorithm appears as Algorithm 2.Source: §A.3 · p. 15
A.4 Tool Inventory
The appendix describes the tool and agent inventories, pricing assumptions, task inputs, and prompt optimization, alongside example behavior and model-specific performance tables.
A.4 Tool Inventory
- The tool inventory spans 23 categories; 35 of its 120 unique tools (28.5%) appear in multiple categories.Personal task assistance has 24 tools, while arithmetic calculations, health information, and event management each have one.Source: §A.4 · p. 15
A.5 Pricing of Components
- The detailed composer generates task skills, retrieves top-K candidates, tests them on skill queries, and uses value-to-cost estimates under a budget.The algorithm tracks covered skills and remaining budget when selecting components.Source: §A.5 · p. 16
- The pricing assumptions estimate paid tools at $8 per 5000 queries, free tools at $3, and free tools with query limits at $5.The paid-tool estimate combines API and schema-token costs; the free-tool estimate includes schema-token costs.Source: §A.5 · p. 16
A.6 Agent Inventory
- Synthetic agents cover diverse domains, and ten agents with MAC-overlapping descriptions but no tools test whether composition can identify capable agents.Source: §A.6 · pp. 16–17
A.7 Task Descriptions
- Dataset task descriptions are included as inputs to the composition framework.Table 3 is labeled with dataset and task-description columns.Source: §A.7 · p. 17, Table 3 · p. 17
A.8 Impact of Prompt Optimization on Tool Use
- Prompt optimization adds task decomposition, tool assignment, redundant-call avoidance, query reformulation, result validation, and error recovery.It uses feedback from recorded sandbox trials and then fixes the system prompt for benchmarking.Source: §A.8 · pp. 17–18
Before Prompt Optimization
- Before prompt optimization, the example ends without an answer after repeated rate-limited web searches.Source: Before Prompt Optimization · p. 18
After Prompt Optimization
- After prompt optimization, the SimpleQA example returns the retirement year 1952, and the authors report improved accuracy, tool-use efficiency, and interpretability.The optimized example uses a timeline-aligned academic search followed by a direct paid web query.Source: After Prompt Optimization · p. 18