Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Authors: Michelle Yuan
Khushbu Pahwa
Shuaichen Chang
Mustafa Devrim Kaba
Jiarong Jiang
Xiaofei Ma
Yi Zhang
MONICA SUNKARA
Venue: NeurIPS 2025 poster ()
Keywords: large language models
llm agents
combinatorial optimization
knapsack algorithm
agent composition
Primary area: social_and_economic_aspects_of_machine_learning

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.

Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Michelle Yuan"t Khushbu Pahwa" Shuaichen Chang
Mustafa Kaba, Jiarong Jiang. Xiaofei Ma, Yi Zhang, Monica Sunkara
AWS Agentic Al
mi chelle. wwwnooraceeeeee..m com
(pahwakhu, catarkkkuucsuuacchee cshuaich, mdkaba, jiroongj xiaofeim, yiiieeiiimiiiignn...m (aannnn,sukaaaall Taankarllaammzon.ccom com
Abstract
Designing effective agentic systems requires the seamless composition and inte- gration 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 not based on capability, cost, and real-time utility. To address these challenges, we introduce 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 optimal set of agentic components by jointly considering performance, budget constraints, and compatibility. By dy- namically 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 benchmark- ing datasets shows that our saatne--nassack-bba based composer consistently lies on the Pareto frontier, achieving higher success rates 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% comparison to the retrieval baselines. In multi-agent systems, the online knapsack composer increases success rate from 37% 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.
Introduction
The design of effective agentic systems sits at the frontier of artificial intelligence research, promising autonomous agents capable sophisticated reasoning, tool manipulation, and collaborative problem- solving. Yet as the ecosystem of Al components expands, with proliferating models, APIs, and specialized agents, critical bottleneck emerges: the paradox of choice 233 While modular reuse offers clear advantages over building systems from scratch, developers face combinatorial explosion possible configurations, each with hidden constraints and unpredictable interactions. Traditional approaches relying on manual curation metadata based retrieval [29] struggle with three fundamental limitations: opaque capability descriptions that rarely match real-world performance. myopie selection criteria that ignore cost-utility trade-offs, and static architectures that break down when requirements evolve.
'These authors contributed equally.
Work completed while at Amazon. Currently Oracle Al.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we introduce agent composition as knapsack problem, where an Al 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, 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 one-time decision based on static metadata, the composer refines choices through empirical validation. When composing an information-seekinn agent, for instance, it might initially select 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 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 [T] 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 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 reduce these issues and maintain 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 Al agents stems from the integration of APIs with LLMs [27 24).
Since tools are a critical component of agents, prior works have focused retrieval approaches to select the most appropriate tools. Qin et al. [25] collect a large dataset of tools based on RapidAPIs and train BERTTbbase tool retriever. Shi al.
29 note that tool retrieval is 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) 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. [1O] 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 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 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 agentic supernet and then will sample multi- agent architecture in a query-dependent manner. Wu al. [35] jointly optimize agent prompt and tool descriptions to improve workflow efficiency. The component selection problem also relates to

---

Development
Deployment
slope Sout State and Winde: carbest
Invertary
Agent Compositoon
bramm South Sation
Weeser Goring
Developer
Agente System
Agentc
Figure 1: The problem of agent composition assumes there is existing inventory of agentic components and a task description. Using these inputs, the agent composition solution should select the most relevant components to build an agent (left). The agentic system can then be deployed as it has the correct set of components accomplish goals as set by the user at inference.
Distributed Constraint Optimization Problems (DCOP) [8] where traditional agents assign values to variables to minimize global cost function subject to constraints. DCOP techniques have been applied service selection and composition problems, particularly for QoS-aware web service composition
Knapsack Algorithms The knapsack problem, classic optimization challenge, has been exten- sively studied in algorithmic research [99
7 14 Offline algorithms, such as dynamic program- ming 2 and saanchhand-bouune methods (18), assume complete knowledge of all items in advance, enabling optimal solutions for static inputs. In contrast, online knapsack algorithms process items sequentially without future information. A commonly known approach the ZCL algorithm [4]] which proposes threshold for the value-to-weight ratio and dynamically configured based on the capacity of the knapsack. Other theoretically competitive approaches further extend the ZCL algorithm 16]
3 Problem Definition
Hu [T0] introduce the problem of automated design of agentic systems (ADAS), where the goal is to automatically build and configure the components of an agentic system. Rather than manually engineering agent architectures, ADAS aims automate the entire procedure through algorithmic discovery. Components of agents include tools, models, prompts, and workflows. Our work addresses a critical subproblem within this vision: automated agent composition, which focuses not on inventing new building blocks from scratch, but optimally selecting and combining existing components from inventories to meet specifie task requirements.
We define the problem of agent compasition as follows (Figure T Assume that there is target task with a description x and a budget B for the agentic system. Assume that there exists a set A of components where each component has cost and description d, Let P~(S) denote the probability of success rate for an agentic system built on subset for task т. The success probability should reflect both the performance of the individual components and their combined effectiveness when operating together. The goal of agent composition is to find the optimal subset S* of components for this domain:
S" = arg max (S) subject to
ΣG B a:CS
(1)
SCA
This formulation directly mirrors the classical knapsack problem, where components correspond to items with associated weights (costs) and values (success rates). However, three critical distinctions emerge in practical settings. First, the true success probabilities are initially uncertain and must be estimated through iterative testing, transforming the problem into a variant of online knapsack optimization. Second, components frequently exhibit non-additive interactions, either positive

---

Inventory
Skill & Query
Component
Sandboox
Desoriptine
Budget
Agentic
System
Figure 2: Overview of our proposed online knapsack composer. Similar to offline baselines, the workflow begins with generating skills and queries from the given task descriptions (Appendix A.J]. Then, the composer retrieves components from the inventory given skill descriptions. With the retrieved components, the composer tests them individually. If value-to-price to-ucte ratio meets the online knapsack threshold, then it is added as part of the agentic system. Otherwise, the search continues.
synergies or detrimental conflicts, that may introduce quadratic coupling terms into the objective function. Third, the inventory itself evolves dynamically as new components are added or existing ones are updated, requiring solution methods that support incremental recomputation.
These complications notwithstanding, the knapsack analogy provides both conceptual clarity and algorithmic leverage. Practical applications range from enterprise settings where development teams select from internal tool registries, marketplace scenarios where automated agents assemble solu- tions from commercial API inventories. In all cases, the core challenge remains consistent: navigating the combinatorial explosion of possible configurations to identify cost-effective compositions that sat- isfy stringent performance requirements. The composer agent introduced in Section 4 addresses this challenge through a novel synthesis of constrained optimization and empirical validation techniques.
4 Composer Agents: From Semantic Retrieval to Knapsack Selection
composer be generalized as function f that will return subset S of components from inventory A: T,
S I for given task r and budget B. Ideally, we would want ff to return the optimal solution S* for equation However, we note that finding this solution is non-trivial due to dynamic behavior of these components and difficulty in assessing their true value. Below, we list and explain proposed composers.
The first example of a primitive composer is simply to return all components in an inventory where f(A, BB) A. We will refer to this as the identity composer, it resembles an identity function.
Identity Composer:
Retrieval Composer: Next, we should consider taking natural language descriptions into account when designing a more intelligent composer. Recall Section Jasumes that task 7 has description and each component in the inventory has description d, Many existing works rely on embedding models for semantic retrieval of components like tools (Section (2). However, the challenge here deciding the query to retrieve from. We also want make sure that the retrieved components are not redundant. To do so, we augment the retrieval composer with the ability to parse task descriptions into a list of skills. Each skill should be required, core ability for task completion. Table shows examples of generated skills from task descriptions in one of our runs for GAIA with Claude 3.5 Sonnet.
Given task 5 and its description æ, the retrieval composer will first generate list of skills m E M. each with name and description. The retrieval composer then queries the inventory with the skill name and description to find most relevant component. The selected subset will the top-1 retrieval results based on the skills. Note that semantic matching has been used in prior work in agent discovery (5) and more generally in service discovery Therefore, we include retrieval-only baseline in our experiments for fair comparison.

---

Table Examples of skills and test queries that are generated based on GAIA task description with Claude 3.5 Sonnet. The generated information is then used to select each tool for the agent.
Name
Description
Test Queries
Web Research
Ability to search the inter- net, retrieve information, and provide concise web-based re-
1. Find the current population of Tokyo
2. What is the latest stock price for Apple Inc?
search results
Code Assistance
Provide programming support, code generation, debugging. and technical problem-solving across various programming languages
1. Generate Python function to calculate Fibonacci sequence
2. Help debug JavaScript error in a web application
Scientific edge
Knowl-
Provide in-depth scientific in- formation, explain complex concepts, and offer research- based insights
Explain the process of photosynthesis 2. Calculate the orbital period of Mars
File Management
Handle various file types, per- form conversions, extract in- formation, and manage file- related tasks
1. Convert a PDF document to a Word file
2. Extract text from image file
Quick Information Retrieval
Rapidly provide concise, accu- rate answers specific ques- tions across various domains
1. What is the capital of Australia?
2. How many bones are in the human body?
Personal Task Man- agement
Assist with daily personal organization, scheduling, re- minders, and lifestyle opti-
Create meal plan for week-long diet
2. Schedule a dentist appointment and reminder
mization
Offline Knapsack Composer: The above composers do not take budget into account when making the selection. To find solution S with success rate p, (S) close to the optimal success rate pr (S*) and following the budget constraint, we apply solutions of the Knapsack problem. First, we generate skills based on task description x (Appendix A.II) and retrieve top- K components for each skill. Next, we assign the value of each component based on the similarity score (SIM) used in retrieval. Finally, we use linear programming to find the optimal solution for this multiple-choice knapsack problem
[aa B
(Budget)
SOFF = arg max SCA
OFF U1
s.t.
Ea,es 1/a E TopK(a)) 1, Vm E M (Skill coverage)
a:ES
(2)
where oFFF Σ EMEM SIM(a; m).
Both retrieval and offline knapsack composers only uses semantic retrieval of descriptions to select subset of components. However, descriptions of components may not always be reliable nor aligned with their true capabilities. Components are also prone to changing (e.g. new tool or model updates). Task requirements and environments are also evolving, and there could be "stale" components in the inventory. Thus, we propose an online knapsack composer that iteratively tests the candidate component to assess its true value (Figure 2).
Online Knapsack Composer:
In our problem, the value of the component is known until it is tested. Therefore, we use the ZCL algorithm [41], a commonly used online knapsack algorithm in the literature. The algorithm assumes there is a lower and upper bound, L and U, on the value-to-cost ratio. The solution is theoretically proven to be In(U/L) 1-competitive. The algorithm sets dynamic threshold based on the capacity filled the knapsack and only accepts an incoming item its value-to-cost ratio exceeds the threshold V. To compute the value, the composer agent has to not only generate the skills but also set of test questions for each skill (Algorithm [T]. The composer agent then uses those questions evaluate the component. Table I shows the test queries that are generated and then used
5

---

Algorithm 1: Online Knapsack Composer
Input: Inventory A, task description æ; budget B
Output: Selected components S C
S + 0. B + B, brokem +0 0
11 B: remaining budget {(m,,j. w,)): name, desc, queries,
M < GENERATESKILLSSE2)
importance
foreach skill m2 E M do T, TOPK(A, KK);
L t 1/ max,, Ca. U t- Σ, wj/ min, Ca
// Value-to-cost bounds
for round +- to R do
covered < ; foreach skill m2 M do foreach component a; E T do
// Reset each round
if a; E 8 broken or my E covered or c; B then continue; scores +- (VALLAAT((;;
// Returns {-1,0, 13 per skill
// 1: helpful, 0: not helpful, -1: broken
if scores (oor then
broken +- broken U {
// Never test again
continue;
end
+ Σ megtorvered Wk [sscores[ma] = 1];
// Value from new skills // Value-to-cost ratio
4 1//G;
2 ビ (B BBBB v (40)=
// Fraction spent; ZCL threshold
if p: 2 v then
S su {a,}. B B+ B c. covered covered {my scores 1}:
end
end
end
end return S
to test tools during the sandboxing trials. Appendix A.2 goes the prompt and details on how the component judged. The component's value is then based on this assessment.
If a component is successfully equipped, then the composer agent will move forward to the next skill and iterate over the top-K components until finds successful one. Note further optimize upon the runtime of Algorithm [ we make modifications such as: 1) stopping sandboxing early if component breaks and preventing it from being tested again, 2) once skill covered, we do not assess that skill again for other candidate tools. We cover these shortcut optimizations in Appendix A.3 and algorithmic details Algorithm
Experiments
This section covers two sets of experiments to evaluate our proposed approaches for agent composition. The first set of experiments look at how to compose single agents through selecting the appropriate tools. The second set of experiments focus on how compose multi-agent teams through selecting the right, specialized sub-agents. In both sets of experiments, we compose the agents for a particular task. Once the components We explain in detail how the evaluation is conducted for each set experiments in their respective subsections. In the main body, present subset of results and have full results in Appendix A.9
selected, fix the agentic setup and run evaluation on the benchmarks.
5.1 Composing Single Agents
Inventory For single-agent experiments, the inventory consists of 120 tools. For this tool inventory, we first collect tools that are actual APIs and can be easily found on Langchain [15]. like arXiv, PubMed, SemantieScholar, web search, etc. For the rest of the tools, we collect small subset from the largest available tool retrieval benchmark. ToolRet (29]. We discover that many tools in

---

GAIA
SimpleQA
100
50
Success Rale
40
Success Rate
Poreto Rronbr
00
Poreto Fromtbr
30
OFF [830]
[=30]
40
[610]
[$1.)
20
Ol: oRT [$30]
ONHKP OPT [#39]
OK-RF (S36]
DMH-P (5:0) DN [c20]
ow-Kr [s30]
RET
0
20
360
380
400
420
440
20
40
360
380
400
420
440
Budget Spent
Budget 5pent
MedQA
100
Foreto Fratler
[$30]
85
RN om [s10]
[$36]
UNisK on [tau]
OMAX (410)
20
40
360
380
400
423
443
Budget Spent
Figure Results of Claude 3.5 Sonnet single-agent experiments where we evaluate the approaches to select the most relevant tools given task description. After equipping the agent with those tools, then run evaluation on the dataset and plot success rate against the budget spent on tools. We plot the pareto frontier which represents that other agent perform better simultaneously in both success rate and cost. Overall, the online knapsack with AvaTaR optimization (S30) shows to be cost-effective and highest performing approach, followed by online knapsack without optimization ($30).
this benchmark are not readily available use and very specialized for one usecase. This is likely because the benchmark is used to test retrieval accuracy. For more details on the construction of the tool inventory, refer Appendix A.4 For pricing, we estimate the cost of tool consist of the input tokens (from the tool schemas) during inference and cost of the API call. The pricing for about 5K calls to the agent for free API tool is around $3, For the paid APIs, we then estimate the tools to be about $5 and S8. See Appendix A.5 for more details.
Models We fix the agent workflow CodeAct 33 where the agent prompted generate code in order to invoke tools rather than in standardized JSON format [38]. We choose CodeAct as it has shown to outperform other tool-calling frameworks. We experiment with both Claude 3.5 Sonnet Claude 3.5 Haiku In one experiment, we will use the same model for the composer agent and the candidate agent that is being evaluated. For embedding model, (3).
3-5-sonnet-2000 --7--sonnee--2000
[ and
Claude 3.7 Sonnet
we use Large- embeddings lage-large--n-vee
For single-agent experiments, we evaluate on GAIA, SimpleQA, and MedQA. GAIA 21]. which stands General AT Assistants, is comprehensive evaluation framework designed to assess the capabilities of AI systems in handling real-world scenarios. It focuses on testing fundamental abilities such as reasoning, multi-modal understanding, web browsing, and tool-use proficiency. Unlike traditional benchmarks that challenge AI with tasks difficult for humans, GALA poses questions
Datasets
7

---

that are conceptually simple for humans but pose significant challenges for advanced Al models. SimpleQA [34] is factuality evaluation framework developed by OpenAI to measure the ability of language models to answer short, fact-seeking questions accurately. The questions in SimpleQA are crafted to have a single, indisputable answer, making it easier to evaluate the factual correctness of model responses. MedQA [12] is comprehensive evaluation framework designed to assess the clinical knowledge of language models in healthcare settings. Questions are derived from the United States Medical License Exams and aims to evaluate the ability of agentic systems to apply medical knowledge in practical scenarios. Note that we reuse the "smolagents" " version of GAIA and SimpleQA, which is an active leaderboard for LLM agents hosted on Huggingface [26]
Approaches We test on all the composers introduced in Section 4 We pass in the base CodeAct agent, the inventory, task description to the composer. For the knapsack composers, we also pass in the budget, which is set either $10 or S30 in our experiments. The composer returns set of tools, which we then equip the Act agent with. We then evaluate the CodeAct agent on the target task. We list the descriptions of each task in Appendix
For retrieval, we set to 10. For question generation, we set the number of test questions per skill to 2. During judgement, we ask the composer to judge whether the tool was useful for the agent to answer the question. Additionally, we include an approach where we conduct tool selection through online knapsack and then conduct additional round of prompt optimization using AvaTaR (36). The feedback for prompt optimization is derived from the tool sandboxing trajectories when the composer has to test the CodeAct agent with the tool. Therefore, trajectories per tool for prompt optimization, so we can directly apply AvaTaR. This helps refine the agent's 's prompt so that it has a better understanding of when invoke certain tools.
already have existing twelve
Results Figure 3 shows the results from the Claude 3.5 Sonnet experiments where plot success rate against the budget spent on tools. Following the accuracy-cos analysis done by Kapoor et al. [13], we plot the pareto frontier. Approaches that are the pareto frontier signify that there is no other method that outperforms them simultaneously in both dimensions. Overall, we observe the highest performing approach be online knapsack with Ava optimization ($30 budget constraint). On all three datasets, its success rate is higher than identity but cost is much lower. Similarly, online knapsack without AvaTaR optimization shows to be on the pareto frontier for GAIA and MedQA, and has relatively higher success rate than the other approaches. Retrieval-only approaches (retrieval and offfine knapsack) tend fare worse across all three datasets, which validates previous findings that only using retrieval for tool discovery is insufficient (29
5.2 Composing Multi-Agent Systems
Setup For multi aulti-agent benchmarking, we use the end-to-end multi aalti- evaluation framework from Shu et al. [30]. Their framework assumes a hierarchical multi-agent collaboration (MAC) architecture where one agent acts as a supervisor and delegates tasks to specialist sub-agents. The benchmarking framework publicly released MAC benchmarking dataset that includes an inventory of about 20 sub-agents for a few enterprise domains. The evaluation involves using the scenario from the dataset as input and then simulating the conversation between the user and multi-agent team. If the team's 's trajectory satisfies the annotated list of assertions, then is considered success.
We set up ReAct tool-calling agents as done in the paper (38) and benchmark on two domains: travel and mortgage. We further synthetically augment the original inventory of agents to about 117 agents (Appendix A.6). We arbitrarily set the price of each sub-agent to $1. All sub-agents use the same underlying model and their tools are being simulated in this setup. this controlled setting, there is no meaningful variation in runtime or API costs between sub-agents, so assigning a uniform cost allows us to isolate and evaluate the impact of agent selection strategies, making it feasible compare how this setting differs from Section 5.1 where the pricing was more varied across items. For these experiments, we fix the budget to $3 and $6.
For our experiments, we first pass in task descriptions (Appendix A.7]. agent inventory, and optional budget the composer to select the most relevant sub-agents. Then, set up multi-agent team where the supervisor has the original profile from 300 but with newly selected sub-agents from agent composition. Finally, we simulate the interactions between user and the newly formed MAC team.
8

---

Travel
Mortgage
Frontle
Pareto fronter
[93]
80
OfF-ER [33)
OFT-KP [se] on sor [6:]]
OfF-cP (S8)
ch-Kr [PJ]
Success Rate
ORe-SP
Success Rate
Ch-HP [s6]
RET
RET
40
0
23
75
100
125
150
25
75
100
125
150
Budget Spent
Budget Spent
Figure 4: Results of Claude 3.5 Sonnet multi-agent experiments where evaluate all approaches to select most relevant tools given task description. After equipping the agent with those tools, we then run evaluation the dataset and plot success rate against tool costs. Overall, online knapsack shows to be cost-effective and highest performing approach.
Results Figure 4 shows the results from the multi-agent experiments. We plot overall goal success rate against budget spent on the agent selection. In both domains, online knapsack (S6) is the niighst-performing approach on the pareto frontier. Unlike single-agent experiments, identity no longer shows high success rate as supervisor agent has trouble delegating task to an inventory of more than 100 diverse agents. Possibly, an improved multi-agent framework could be alternative approach to handle large-scale network of agents [5]
Discussion
Improvements with online knapsack in single agent composition. In Table 2 we show the tools that are chosen during the experiments compare the various composers. For GAIA and SimpleQA, having "web search" tool is critical as the questions revolve around more recent or esoteric topics. For retrieval composer, do not any "web search" tools being picked for GAIA and SimpleQA. The tool selection highly depends on the ability of the retriever to match skill descriptions to tool descriptions. While "Web Browsing" seemed to match closely with the cet_arrccle_cottene where both mentioned web pages. However, aataaall_cootentttt content" is "web _earch_eerch___ee free" which is the web search tool that is cheaper but with severe throttling limits. Online knapsack chose "web search search__paid" which is the most appropriate web search tool for these tasks. Since the online knapsack composer can also test out these tools, it can detect that "web seaach__piide can effectively search the web. This explains the higher success rate that we see with online knapsack in Figure
skill generated for GAIA, the description for this skill
tool help search the web. Offline knapsack was able to choose
We additionally observe that the prompt optimization helps to boost performance for SimpleQA. We attribute this improvement to the revised agent system prompt offering clear guidelines on query formulation for effective search, tool usage guidelines, source verification, and enhanced error- recovery protocol. For details on the impact of adaptation for tool use, please refer to Appendix A.8
Appendix A.9 shows results several models, including ones from Llama 4 [ and Qwen 2.5 [32 model families. We observe similar results where online knapsack tends to outperform the baselines. Furthermore, we observe consistency of these results across multiple runs (Table 12)
Improvements with online knapsack in multi-agent composition. For multi-agent experiments, we observe the retrieval-basee based methods would often select the "distractor" agents that we add to inventory. These are agents that overlap semantic description with the original MAC agents that should have chosen but lack the tools and proper instructions to carry out the tasks successfully. For instance, offline knapsack composer ($6) chose five agents that lacked true capabilities for travel, which why it had performed worse for this domain (Figure 4) On the other hand,

---

Table 2: Tools that are selected by the various composers over GAIA and SimpleQA. Retrieval composer tends to miss out on relevant tools for the task. Offline knapsack often includes too many irrelevant tools. Online knapsack seems to have both precise and well-covered choice of tools.
Composer GAIA
SimpleQA
Retrieval
pub _odd read file. wol- fram alpha, job titllee autocomplete, get_article_conter number_face
wikipedia. pub med, sources, num- ber fact
Offline Knapsack
search__free arxiv, wikipedia, pub_med, read file, semantic- scholar, instantaneous_ malues_service, get_ get_recordings, get_article_cre number_fact
web_ search free, wikipedia, pub_ b_mdd, semanticscholar, standard get_recone recordings, get aataaartcecoooo content, symbols_ s_sss number_fac
query_by_id by_id,
($30)
Online
b_cdd arxiv, wikipedia
web__searee -aiid web_ ceb_search_e free, wikipedia, semanticscholar
Knapsack ($30)
online knapsack consistently would avoid these "distractor" agents as it was obvious that they were non-operable.
Limitations. First, our problem definition (Section clearly states that we must assume the task is well-defined with clear description. This applies to many scenarios where developers already have a clear understanding of their architectural goals and needs. However, there still exists real-life usecases where developers have ambiguous goals and require more exploration. Future work could look at further developing our approach for tasks with unclear specifications. Second, there could be alternative agent composition approaches to compare against, ranging from simple (greedy approach) to more complex approaches such as formulating agent composition as Markov Decision Process. Additionally, could also try testing combinations of agentic components rather than individually. While online knapsack composer outperform all baselines, the sandbox trials does take additional time (10-30 minutes depending budget). A more optimized approach can look towards reducing it. Third, our prompt optimization results show regression in a few settings. This emphasizes the need for more robust optimization method. Finally, agent composition has many positive impacts contributing to rapid creation of AI systems, but there could be potential negative effects. Without careful monitoring of the creation of agentic systems, malicious tools other components could possibly be added to the system.
7 Conclusion
We formalize the problem selecting existing agentic components as agent composition. We reduce agent composition to knapsack problem to optimize selection of components for success rate within a constrained budget. We set up two sets of experiments, one on selecting tools for single agent and the other for composing multi-agent systems with existing sub-agents. Online knapsack composer can optimize composition because it not only uses semantic search to discover components but also tests them to assess their real-time utility. Through application of online knapsack algorithm, can efficiently determine whether to select a component based on its assessed value-to- aalue-to-price ratio. Future works agent composition may look towards more dynamic methods, such learning how to compose from past experience.
Acknowledgments and Disclosure of F Funding
This work has been supported and funded by Amazon Web Services throughout the course of the project. Michelle Yuan is currently affiliated with Oracle but completed this work during her time at Amazon Web Services. The views and conclusions expressed in this paper are those of the authors and do not reflect the views, policies, positions of Amazon, Oracle, or their affiliates. We thank Nilaksh Das, Etsuko Ishii, Raphael Shu, Daniele Bonadiman, Tamer Alkhouli, Katerina Margatina, and Salvatore Romeo for their valuable insights.
10

---

References
[1] Meta AL Introducing llama 4: Advancing multimodal intelligence, 2024. URL https wwa...eeaacmmm httm://llll/aaam--mmtiiiiataeeeo
[2] Rumen Andonov, Vincent Poirriez, and Sanjay Rajopadhye. Unbounded knapsack problem:
Dynamic programming revisited. European Journal of Operational Research, 123(2):394 2000.
[3] Anthropic. Claude 3.5 Sonnet, 2024.
claude- sonnnee sonnet, Accessed 2024-12-06.
[4] Yasmine Charif-Djebbar and Nicolas Sabouret. Dynamic service composition and selection through an agent interaction protocol. In 2006 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology Workshops, pages 105-108. IEFE, 2006.
[5] Weize Chen, Ziming You, Ran Li, Chen Qian, Chenyang Zhao, Cheng Yang, Ruobing Xie, Zhiyuan Liu, Maosong Sun, et al. Internet of agents: Weaving web of heterogeneous agents for collaborative intelligence. In ICLR, 2025.
[6] Kazem Faghih, Wenxiao Wang, Yize Cheng, Siddhant Bharti, Gaurang Sriramanan, Sriram Balasubramanian, Parsa Hosseini, and Soheil Feizi. Gaming tool preferences in agentic llms. arXiv preprint arXiv: 18135, 2025.
[7] Martin Feuerman and Harvey Weiss. A mathematical programming model for test construction and scoring. Management Science, 19(8):961-96) 1973.
[8] Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. Distributed constraint optimization problems and applications: A survey. Journal of Artificial Intelligence Research, 61:623-698, 2018.
[9] Tiantian Gan and Qiyao Sun. Rag-mep: Mitigating prompt bloat in Ilm tool selection via retrieed generation. arXiv preprint Prxiv::500.03325 2025.
[10] Shengran Hu, Cong Lu, and Jeff Clune. Automated design of agentic systems. In NeurIPS 2024 Workshop on Open-Wone World Agents, 2024.
[11] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. NeurlPS, 2021.
[12] Di Jin, Eilcen Pan, Nassim Oufattole, Wei-Hung Weng, Hanyi Fang, and Peter Szolovits. What disease does this patient have? large-scale open domain question answering dataset from medical exams. Applied Sciences, 11(14):6421, 2021.
[13] Sayash Kapoor, Benedikt Stroebl, Zachary $ Siegel, Nitya Nadgir, and Arvind Narayanan. Ai agents that matter. arXiv preprint arXiv:2407.01502, 2024.
[14] Richard M Karp. Reducibility among combinatorial problems. In 50 Years of Integer Pro- gramming 1958-2008: from the Early Years the State-of-the-Ari, pages 219-241. Springer, 2009.
[15] LangChain. LangCraph, 2024. https://ww// www.wwaingchhin.commm com/ Accessed on 2024-12-06.
[16] Adam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali, and Mohammad Hajiesmaili. Time fairness in online knapsack problems. In ICLR, 2024.
[17] Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. A dynamic LLM-pooered agent network for task-oriented agent collaboration. In COLM, 2024.
[18] Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementa- tions. John Wiley & Sons, Inc., 1990.
[19] George B Mathews. On the partition of numbers. Proceedings of the London Mathematical Society, 1(1):486-490, 1896.

---

[20] Elena Meshkova, Janne Riiijjrrvi, Marina Petrova, and Petri Mähönen. A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks. Computer networks, 52 (1 (11):2077-2228, 2008.
2008.
[21] Grégoire Mialon, Clémentine Fourrier, Thomas Wolf, Yann LeCun, and Thomas Scialom. Gaia: a benchmark for general ai assistants. In ICLR, 2023.
[22] Ivan Milev, Mislav Balunovic, Maximilian Baader, and Martin Vechev. Toolfuzz-automated agent tool testing. arXiv preprint arXiv:2503, 04447, 2025.
[23] Antti Oulasvirta, Janne P Hukkinen, and Barry Schwartz. When more is less: the paradox of choice in search engine use. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pages 516-523, 2009.
[24] Shishir G Patil, Tianjun Zhang, Xin Wang, and Joseph E Gonzalez. Gorilla: Large language model connected with massive apis. In NeurlPS, 2024.
[25] Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. In ICLR, 2024.
[26] Aymeric Roucher, Albert Villanova del Moral, Thomas Wolf, Leandro von Werra, and Erik Kaunismäki. 'smolagents": : a smol library to build great agentic systems. htttps///github com Comm/uugingface//mme www.a//eeemmmaemeeeeeeeemmeeeeee 2025.
[27] Timo Schick, Jane Dwivedi-Yis Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves
tools. In NeurlPS, 2023.
[28] David Sculley, Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young, Jean-Francois Crespo, and Dan Dennison. Hidden technical debt in machine learning systems. Advances in neural information processing systems, 28, 2015.
[29] Zhengliang Shi, Yuhan Wang, Lingyong Yan, Pengjie Ren, Shuaiqiang Wang, Dawei Yin, and Zhaochun Ren. Retrieval models aren't tool-savvy: Benchmarking tool retrieval for large language models. arXiv preprint arXiv:2503. 01763, 2025.
[30] Raphael Shu, Nilaksh Das, Michelle Yuan, Monica Sunkara, and Yi Zhang. Towards effective genai multi-agent collaboration: Design and evaluation for enterprise applications. arXiv preprint arXiv:2442.00544, 2024.
[31] Prabhakant Sinha and Andris A Zoltners. The multiple-choice knapsack problem. Operations Research, 503355003-555, 1979.
[32] Qwen Team. Qwen2.5: A party of foundation models, September 2024. URL https:// qwenlm. gittuub.i/bllle hww.l////bo./.......oo 5/
[33] Xingyao Wang, Yangyi Chen, Lifan Yuan, Yizhe Zhang, Yunzhu Li, Hao Peng, and Heng Ji. Executable code actions elicit better LLM agents. In ICML. 2024.
[34] Jason Wei, Nguyen Karina, Hyung Won Chung, Yunxin Joy Jiao, Spencer Papay, Amelia Glaese, John Schulman, and William Fedus. Measuring short-form factuality in large language models. arXiv preprint ArXiv:24/ 1. 100468, 2024.
[35] Bin Wu, Edgar Meij, and Emine Yilmaz. A joint optimization framework for enhancing efficiency of tool utilization in IIm agents. In Findings of the Association for Computational Linguistics: ACL 2025, pages
[36] Shirley Wu, Shiyu Zhao, Qian Huang, Kexin Huang, Michihiro Yasunaga, Kaidi Cao, Vassilis Ioannidis, Karthik Subbian, Jure Leskovec, and James Y Zou. Avatar: Optimizing 1lm agents for tool usage via contrastive reasoning. In NewrIPS, 2024.
[37] Shitao Xiao, Zheng Liu, Peitian Zhang, and Niklas Muennighoff. C-pack: Packaged resources to advance general chinese embedding, 2023.
12

---

[38] Shunyu Yao. Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. The Eleventh International Conference on Learning Representations, 2023.
[39] Guibin Zhang, Luyang Niu, Junfeng Fang, Kun Wang, Lei Bai, and Xiang Wang. Multi-agent architecture search via agentic supernet. arXiv preprint arXiv:2502.04180, 2025.
[40] Guibin Zhang, Yanwei Yue, Zhixun Li, Sukwon Yun, Guancheng Wan, Kun Wang, Dawei Cheng, Jeffrey Xu Yu, and Tianlong Chen. Cut the crap: An economical communication pipeline for Ilm-based multi-agent systems. In ICLR, 2025.
[41] Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In WWW, 2008.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: We have ensured that the main claims made in the abstract and introduction are directly correlating to the research findings and the methods we have employed.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes],
Justification:
We have added limitations in the Discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
14

---

Justification:
Our paper does not require any explicit theorems and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper has deliniated all the information related to the proposed algorithm and the comparative baselines.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [No].
Justification: The benchmarking datasets used this paper are publicly available. The code release is dependent company policies.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
httpol/iiigggddde/ooooooo wwweeeeeeeooeSbummmioooe ssicnlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes].
Justification:
We provide information about the data used for evaluation and the model
details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We include multiple runs for experiment in Appendix A.9
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We mention compute details in Experiments section. Discussion section mentions how long our proposed approach takes.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in this paper fully conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss positive impacts throughout the paper and negative impacts in the Discussion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Our research does not pose any risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We have explicitly cited the publicly available datasets, softwares and models used.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: We will opensource the code and provide complete documentation for our assets upon acceptance.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: We use publicly available datasets and do not collect any new data.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA].
Justification:
We use publicly available datasets and do not collect new data.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
This research proposes an adaptive and scalable LLM based agent composition method inspired by online knapsack algorithm. The LLM plays an active, non-standard role beyond general purpose langauage generation since it is invoved assessing the utility of the tools/sub-agents, interacting with the agentic components, and is also evaluated and adapted based on tool utility. Therefore, its use is essential and integral to the novelty and scientific contribution of this work.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components. /atparrrpppppc/ooooeeeee///////
Please refer to our LLM for what should or should not be described.
A Appendix
A.1
Skill and Query Generation Prompt
For both offline and online knapsack composers, skill generation is critical component of the workflow. Note that we combine skill and query generation one step to reduce the steps in the composition workflow. Below is the prompt used for the composer agent to generate skills and queries. We also ask the composer to generate reference plans each query, which will help with the judgement part (Appendix A.2
You are a task parser. Your job is to parse the following tasks into a Fine-graing list of no more than six skills. Each skill should distinct and unique.
each skill, you also must provide a description, an importance value rated on scale of 1 to 10, and list of test queries with plans. Queries should provide all the context needed for agent to solve the task. Queries should be designed so that agent must use a tool to solve, but should NOT take more than step tool call. Plans should describe how agent should solve the query, which are a short list of actions that the agent needs to take high-level reasoning steps that the agent needs to think about.
The output schema for a skill is as follows:
name: str importance: int
description: str
queries: list[fquery: str, plan: str]]
A.2 Prompts for Sandbox Judgements
During the sandhox trials (Figure 2). the composer has to judge whether the agentic component is useful for completing the task. We set up two variations of the prompts, one for single agent and another for multi-agent experiments. In the single agent experiments, the composer needs to determine whether the candidate tool has helped the agent achieve the goal. In the multi-agent experiments, the composer needs to determine whether the candidate sub-agent has helped accomplish the user goals.
Below the prompt for the sandbox judgement in single-agens experiments:
20

---

You will be given query, reference plan, the tool's name, and agent's steps to answering the query. You are to judge whether the tool has helped the agent in answering the query and whether the tool is broken. If the tool appears to have errors after multiple attempts or have potentially harmful effects on the environment, you must return True for "broken". If the agent was able to answer the query without using the tool, you must return False for "helpful". Only return True for "helpful" if the tool helped the agent answer the query.
Query: {query}
Reference Plan: freference plan} Tool: {tool}
Agent's Steps: {agent steps}
Below the prompt for the sandbox judgement in multi-agent experiments:
You will be given a query, reference plan, and agent's steps answering the query. You are to judge whether the agent is helpful answering the query and whether the agent broken. If the agent is able to call the right tools and answer the query using information the
from the tool calls, you must return True for "helpful". agent does not complete the task but explains that they cannot do so, just return "False" for "helpful" and "False" for "broken". ONLY return True for broken if the agent is toxic, has potentially harmful effects on the environment, completely irrelevant for the task. Also return True for broken if the agent tries to call tools that are not available.
Query: {query}
Reference Plan: freference plan} Tool: {tool} Agent's Steps: fagent steps}
Note that the output schema for both experiments is the same:
helpful: bool
broken: bool
reason: str
A.3 Modifications ZCL Algorithm for Online Knapsack Composer
In Algorithm [ we show how we use ZCL algorithm for the online knapsack composer. We make some minor modifications to reduce the number of sandbox trials:
Early stopping for sandboxing: In preliminary development, observe slowdowns caused by repeated testing broken components, which could have been avoided by just immediately flagging these components as broken. We added additional judgement in the prompt (Appendix (A.2) to flag these as broken. Once component is flagged as broken, we end the sandboxing and prevent from being tested again.
During sandboxing, we keep track of the skills that are covered. In other words, when a component passes the judge's assessment for skill and the component is equipped, then the skill is recorded as "covered". Once that skill is covered, then we no longer need to find more components relevant to that skill. This not only reduces the sandboxing trials but also prevents equipping components that overlap in skill.
Skipping covered skills:
We disclose an extended version of the algorithm in Algorithm
2
21

---

Algorithm 2: Online Knapsack Composer Detailed
Input: Inventory A, task description æ; budget B Output: Selected components S C.A
// Initialization
S t 0, B < B, broken -- 0;
11 B: remaining budget
// Generate skills from task description
M < GENERATESKKILSS(E))
// {(mj, dj, Qj wz)}: name, desc, queries,
importance
// Retrieve top-K candidates per skill
foreach skill m; E M do
T do,
end
// Compute value-to-cost ratio bounds
+ 1/ m ca U E, wj/ m
// Worst case: max cost, min value
// Best case: min cost, max value
// Iterative online knapsack rounds for round + 1 to do
covered - 0
// Reset covered skills each round
foreach skill m; E E do
foreach component a; E Tj do
if a; E S U broken or my E covered or c; B then
continue:
// Skip if processed or infeasible
end
scores + TESTONQUERIESSO
// Test on all skill queries
if scores [m < then
broken <- broken U {
// Mark as broken
continue:
end +
E Leggerveeed Wk 1 [scores[ma] = =];;
// Value from new skills // Value-to-cost ratio
01/4;
2 (B B)/B:
// Fraction of budget spent
+ I
+ L.
// ZCL threshold
pi 2 then
S-SU SU {az}:
B+ c;: covered covered U {m; scores[ma] 1}:
end
end end end
return S
A.4 Tool Inventory
We created the tool inventory from Langchain tools and the ToolRet dataset (28). The tools can be divided into 23 distinct categories based their functional similarities, such "personal task assistance", "fact retrieval", and "financial information". The category with the highest number of tools is "personal task assistance", which includes 24 tools. Conversely, categories like "arithmetic calculations," " "health information," and "event management" each contain only one tool, indicating a more specialized focus in these areas.
detailed overlap analysis revealed that out of the 120 unique tools, tools (28.5%) appear in multiple categories, demonstrating a high degree of functional versatility. The degree of overlap was further categorized into high (4+ categories), medium (3 categories), and low categories). Notably, tools like wikipedia, pubmed, and semanticscholar, which are primarily information retrieval
22

---

tools, appear in multiple categories related to knowledge retrieval, fact-checking, and reference. This highlights the dominance of information retrieval tools in the inventory.
A.5 Pricing of Components
For single-agent experiments, have inventory of tools that is a mix of free, free with rate limits, and paid APIs. Our pricing model was primarily based on two costs: 1) cost of API, 2) cost of its schema in terms of input tokens. To simplify the pricing model, $5 per 5000 queries (based on SerperAPI search pricing) and average tool schema token count of 200. If Claude API is priced at $3 per million input tokens, then this translates to cost of S3 for 5000 queries with the tool schema. Therefore, the estimated cost of a paid tool would be S8 per 5000 queries. For free tool, would be S3 per 5000 queries, only needs consider the cost of the tool schema in the input tokens. We then assign $5 to tools that are free but up to certain number of queries.
assume
of paid API to be
A.6 Agent Inventory
We synthetically generate new agents to span diverse domains unrelated to the original MAC do- mains of mortgage, travel, and software, including healthcare (c.g., appointment scheduler agent, telemedicine connector agent), e-commerce (e.g.. product search agent, price tracker agent), govemn- ment/legal (e.g., tax filing agent, legal consultation agent), education (c.g., homework help agent, course recommender agent), career/jobs (e.g., resume builder agent, salary insights agent), me- dia/entertainment (e.g., movie recommender agent, news summarizer agent), social media/messaging (e.g., toxic comment filter agent, follower growth agent), and sustainaaiiitt/llfesttyl (e.g., carbon footprint agent, recycling guide agent), We also include ten agents that overlapped with the original MAC agents in profile descriptions but had tools attached them. This would assess whether composition could discover the agents that were truly capable of accomplishing the user goals in MAC.
A.7 Task Descriptions
Table 3
has the task descriptions for each dataset. These task descriptions are part of the input to the agent composition framework.
A.8 Impact of Prompt Optimization Tool Use
This appendix explains the impact of prompt optimization. We illustrate the improvement with Claude 3.5 Sonnet benchmarking run for SimpleQA. The goal of optimizing the system prompt is to improve the agent's tool selection, reasoning transparency, and error recovery, which led to notable gains in both answer accuracy and operational efficiency.
Initially, the system prompt provided only general guidance and lacked explicit structure for de- composing tasks, matching tools to subtasks, and recovering from tool failures. As result, agents sometimes performed redundant suboptimal tool calls, unnecessarily repeated queries, and often failed to provide answers when information was not immediately available.
Prompt optimization introduces more systematic instructions: the agent is now required to break each question down into sub-tasks, select the most appropriate tool for each sub-task, and avoid redundant tool calls. Specific preferences are introduced for tool choice. For example, using wikipedia for general knowledge and semanti cscholar for scientific queries. The revised prompt also implements better query reformulation, result validation, and error recovery, producing more disciplined, efficient, and interpretable agent behavior.
Note that the prompt optimization is done during the agent composition phase where the input feedback is based on recorded sandboxing trials. The feedback signals for prompt optimization given by the same LLM-as-a-judge that helps score whether the tool is useful for the agent on the given task. After prompt optimization, the agent's system prompt is fixed for benchmarking, which the same as the other approaches.
23

---

Table 3:
Table of Datasets and Task Descriptions
Dataset
Task Description
Answer short, factual questions that should have single correct answer
Answers to the questions may require searching the web
SimpleQA
Questions should be from wide range of topics,
including TV shows, music, sports, geography, art, science, technology, etc.
Help user with tasks that need web browsing, coding, filetype handling Help user with various assistant use cases, such as daily personal tasks, science, general knowledge
GAIA
Answer questions that should have a short, single correct answer
Helps users with medical questions
that need web browsing for medical or clinical information, reviewing published medical articles and other medical texts
MedQA
Answer medical questions from US medical licensing exams (USMLE)
'Toiics cover various medical domains including anatomy, physiology, pharmacology. and clinical practice
Help users book flights, accommodations, and car rentals for their upcoming trips
Travel (MAC)
Help users with any queries regarding travel planning like local attractions or weather forecast
Help users with mortgage planning and financing
Mortgage (MAC)
Help users find property information
Help users retrieve their banking and credit information
Example Query: "What year did Reinhold Rudenberg retire?"
The following logs illustrate the agent's 's behavior before and after prompt optimization in response to a query from the SimpleQA dataset.
Before Prompt Optimization
Thought: I'll search for information about Reinhold Rudenberg.
Tool Call 1: mikipedia("Reinnood Rudenberg')
Observation: No retirement year mentioned.
Thought: Try web search.
Tool Call 2:
web_search_ free ("Reinhold Rudenberg career Harvard retirement") Error: Rate-limited.
Tool Call 3: semanticscholar oaairiccsccolaaaRRiinoooool ('Reinhold Rudenberg Harvard')
Observation: Retrieved unrelated academic papers.
Thought: Try again with web search.
Tool Call 4: web_search_free
Error: Rate-limited again.
Final Decision: "Cannot determine retirement year."
After Prompt Optimization
Thought: Begin with general biography search.
Tool Call 1: wikipedia("RRinlle Rudenberg"))
Observation:
Biographical overview, retirement data.
24

---

Thought: Try academic source for specific timeline.
Tool Call 2: aaaattiisscoolaaaeeiiieeeeee Rudenberg retirement")
Observation: Found timeline-aligee publication data.
Thought: Confirm with direct query.
Tool Call 3: web_search_paide ('ehen did Reinhold Rudenberg retire")
Observation: Found retirement year: 1952
Tool Call 4: final_answer (1952)
Prompt optimization produces measurable improvements: after refinement, the agent answers rectly, reduces unnecessary tool usage, avoids repetitive errors, and presents a clearer chain of reasoning. Task breakdown, explicit tool assignment, and robust fallback strategies together improves not only answer accuracy but also the efficiency and interpretability of the agent's response.
A.9 Detailed Performance Results
In this section, report the quantitative results for the Claude 3.5 Sonnet, Claude 3.5 Haiku, Claude 3.7, Sonnet, Qwen 2.5 72B, Llama 3.3 70B, Llama Maverick, and Llama 4 Scout. The plots in Fig. 3 correspond to the results in Table g In the last table, we have multiple runs of the SimplcQA experiments and show minimal variance across three runs.
Table 4: Performance across approaches, domains, and budget constraints using Claude 3.5 Sonnet, We used different colors denote the highest-performing experiment for GATA (red), SimpleQA (blue), and MedQA (violet).
Total budget constraint
Domain
Approach
Success Rate (avg)
No. tools used
Budget spent
Baselines
Budget: NA
GAIA
Identity
0.47
398
Top-1 retrieval
0.19
23
SimpleQA
Identity
0.80
122
398
Top-1 retrieval
0.24
12
McdQA
Identity
0.92
122
398
Top-1 retrieval
0.87
Knapsack Composers
Budget: $10
GAIA
Offine knapsack
0.19
Online knapsack
Online knapsack OPT
0.31
SimpleQA
Offine knapsack
0.24
Online knapsack
0.24
9
Online knapsack
MedQA
Ofline knapsack
Online knapsack
0.91
Online knapsack OPT
0.89
Knapsack Composers
Budget:
GAIA
Offline knapsack
0.41
Online knapsack
0.47
12
Online knapsack OPT
0.47
SimpleQA
knapsack
Online knapsack
0.92
Online knapsack OPT
0.92
12
MedQA
Offline knapsack
0.91
Online knapsack
0.93
Online knapsack OPT
0.93
2
25

---

Table 5: Performance comparison across approaches, domains, and budget levels for multi-agent composition using Claude 3.5 Sonnet for both primary and secondary agents, We highlight the best result for travel domain blue, and in red for the mortgage domain.
Total budget constraint
Approach
Budget spent
duration (avg see)
Baselines Budget:NA
Travel
Identity
0.07
0.09
17
30.04
Top retrieval
0.23
0.57
30.24
Morigage
Identiy
0.07
0.02
117
7.27
Top- retrieval
0.37
0.68
5
13.22
Knapsack Composers
Budget:
Travel
knapsack
17.77
Online knigsack
0.23
0.53
26.42
Morigage
Offline knapsack
0.67
0.81
24.91
knageack
Knapsack Composers
Budget:
Travel
Offline knapsack
0.17
0.38
3
16.08
Online knopsack
Morigage
Offiiee knapsack
0.70
0.89
20.30
Online knaguack
0,87
0.93
24.13
Table 6: Performance across approaches, domains, and budget constraints using Claude 3.7 Sonnet. We used different colors to denote the nighest-performing experiment for GAIA (red), SimpleQA (blue), and MedQA (violet). We used the same colors but highlighted in bold to denote the highest performing experiment setting for each of the three domains.
Total constraint
Appraach
spent
durattion (arg
Baselines
Budget: NA
122
Top-1
SimpleQA
Identity
0.76
122
398
30
Tup- rouieval
0.26
2
45.0
MedQA
122
398
Tup-1 retrieal
Knapsuck
Budget:
knupsack
Online kmgsaak
0.50
75.2
SimpleQA A
Oflinne knupsack
0.26
3
52.4
Online knigsack
0.92
3
20.0
MsaQA
Ofline knapsock
64.2
knipsack
Kaapsacc Composers
Budget:
Ofline krapsack
10
Online kmageack
10
89.7
SimpleQA
Offliiee knapsack
0.80
10
30
22.9
Online knipsack
0.92
12
22.9
McdQA
knapsack
Online kmasaak
26

---

Table 7: Performance of Haiku 3.5 across domains, approaches, and budget constraints for single- agent composition. We used different colors denote the heifeit- experiment for GAIA (red), SimpleQA (blue), and MedQA (violet).
Approach
spent cleratiin
Bavelines Budget: NA
Identry
Top-1
SimpleQA
blanky
122
Tep-1 sctrivaal
MedoA
Identry
122
398
15.4
Top retrivval
Kangoork Composess
Budget:
Snapsack
knapoccs
knspocck
SimpleQA
Oflinn
Online kmspecck
Online kmzpoccs
MalQA
Oflinn kraepack
0.80
17.7
Ouline kaspeačk
0.82
15.7
Ouline knspsačk OPT
0.84
14.9
Composers
Balget:300
GAIA
Ofline inappack
0.13
29
1409.8
Online knzpsack
0.27
30
23.8
Online knapsxck OPT
0.44
20
30.1
SimpleQA
Offinn: tropeack
0.24
20
22.7
Oulinz knspoack
0.7
22
14.3
Ouline knspeak + OPT
0.86
13.7
MedQA
Octine inapsack
0.79
20
20.3
kaspoads
Ouline knspoac
Table 8: Performance across approaches, domains, and budget constraints using Qwen 2.5 72B Instruct. We used different colors to denote the nighees-performing experiment for GAIA (red), SimpleQA (blue), and MedQA (violet).
Total budget constraint
Domain
Approuch
Success Rate (avg)
No. tools used
Budget spent
Baselines
Budget: NA
GAIA
Identity
0.28
398
SimpleQA
Identity
0.86
122
398
MedQA
Identity
0.9
122
398
Knapsack Composers
Budget: $10
GAIA
Offline knapsack
0.20
9
Online knapsack
0.25
SimpleQA
Offiine knapsack
0.58
Online knapsack
0.78
9
MedQA
Offine knapsack
0.82
2
Online knapsack
0.91
Knapsack Composers
Budget: $30
GAIA
Offline knapsack
0.22
Online knapsack
0.30
12
SimpleQA
Offine knapsack
0.79
10
30
Online knapsack
MedQA
knapsack
Online knapsack
0.92
3
27

---

Table 9: Performance across approaches, domains, and budget constraints using Llama 3.3 70B Instruct. We used different colors to denote the highest-performing experiment for GATA (red), SimpleQA (blue), and MedQA (violet).
budget constraint
Approach
(avg)
used
Budget spent
Baselines
Budget:
GAIA
Identity
0.31
122
398
SimpleQA
Identity
0.78
122
398
MedQA
Identity
0.84
122
398
Knapsack Composers
Budget: $10
GAIA
Offline knapsack
0.24
Online knapsack
0.27
SimpleQA
Offine knapsack
0.63
Online knapsack
0.71
MedQA
Offline knapsack
0.74
2
Online knapsack
0.77
Knapsack Composers
Budget:
GAIA
Offine knapsack
0.29
30
Online knapsack
0.35
14
SimpleQA
Offline knapsack
0.75
30
Online knapsack
0.88
14
MedQA
Ofline knapsack
0.81
14
Online knapsack
0.88
11
Table 10: Performance across approaches, domains, and budget constraints using Llama Maverick 17B Instruct. We used different colors to denote the identity (all tool) results for GAIA (red), SimpleQA (blue), and MedQA (violet). Bolded values indicate the best performing experiment per domain.
Total budget constraint
Domain
Approach
Success Rate
No. tools used
Budget spent
Baselines
Budget: NA
GAIA
Identity (all tools)
0.38
122
398
SimpleQA
Identity (all tools)
0.82
122
398
MedQA
Identity (all tools)
0.85
122
398
Knapsack Composers
Budget:
GAIA
Offline knapsack
0.19
Online knapsack
0.19
3
SimpleQA
Offline knapsack
0.28
3
9
Online knapsack
0.78
9
MedQA
Offine knapsack
Online knapsack
0.91
Knapsack Composers
Budget: $30
GAIA
Offine knapsack
0.31
30
Online knapsack
0.44
SimpleQA
Offline knapsack
0.78
30
Online knapsack
0.78
11
MedQA
Offine knapsack
0.89
21
Online knapsack
0.89
28

---

Table 11: Performance across approaches, domains, and budget constraints using Llama 4 Scout 17B Instruct. We used different colors to denote the highest-performing experiment for GAIA (red), SimpleQA (blue), and MedQA (violet).
Total budget constraint
Domain
Approach
Success Rate
No. tools used
Budget spent
Baselines
Budget: NA
GAIA
Identity (all tools)
0.28
122
398
SimpleQA
Identity (all tools)
0.88
122
398
MedQA
Identity (all tools)
0.84
122
398
Knapsack Composers
Budget:
GAIA
Offline knapsack
Online knapsack
0.16
SimpleQA
Offine knapsack
0.16
Online knapsack
0.82
MedQA
Offline knapsack
0.82
Online knapsack
0.82
Knapsack Composers
Budget: $30
GAIA
Offline knapsack
0.31
30
Online knapsack
SimpleQA
Offline knapsack
Online knapsack
0.82
17
MedQA
Offine knapsack
0.85
24
Online knapsack
Table 12: Robustness testing on SimpleQA with Claude 3.5 Sonnet across three runs. As shown, the standard deviations low across all metrics, indicating that performance is stable and consistent across independent runs. Bolded row marks the highest success rate.
Method
Budget
Success Rate
# Tools
Total Price
Avg Duration (s)
Tool Calls/Example
Identity
No limit
0.840 + 0.033
122
$398.00
13.03 + 0.62
2.55 : 0.04
OfffineKKP
S10
0.213 + 0.009
$9.00
14.68 + 0.16
3.95 : 0.01
Offline-KP
$30
0.207 0.009
10
$30.00
17.23 0.29
4.25 + 0.03
Online-KP
S10
0.860 + 0.028
$9.00
12.44 1.04
2.77 0.05
Online-KP
$30
0.873 0.034
$14.00
11.71 0.68
2.81 - 0.01
29


Reviews:
[{"review_id": "VIAW72g2o2", "reviewer": "Reviewer_CUny", "summary": "The paper proposed a new paradigm for automated agent composition using an online knapsack optimization framework. This aims at selecting an optimal subset of tools or agents for a given task under budget constraints.\n\nThe authors formalize the problem as a constraint optimization problem and develop a compose agent that assesses real-time utility of agentic components via sandbox testing, improving upon existing static, semantic retrieval approaches for tool or agent discovery. \n\nExtensive empirical evaluation showed superior cost-adjusted performance over baselines in both single-agent and multi-agent settings.", "questions": "N/A", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n## Novel Proposal\n- The addressed problem is well-motivated and critical. Agentic AI and use tools become very popular, thus how to efficiently select components (i.e., tools, agents) becomes critical question. \n- The proposed formulation aligns well with real-world scenarios, at least to me. In particular, the tools have varying costs, utilities, and compatibility, which static agentic architectures ignore. \n- Formalizing the problem as a constraint optimization problem and applying ZCL online knapsack algorithm to solve is novel and original.\n \n## Comprehensive evaluation\n- The proposal was evaluated for both single-agent and multi-agent setups, highlighting the generality of the approach.\n- The performance gain are significant:\n- The use of Pareto frontier to compare cost vs utility is fair and original.\n- Benchmarks such as GAIA, SimpleQA, MedQA, and multi-agent collaboration (MAC) provide diverse and challenging testbeds.\n## Novel composer agent design\n- Multiple composers (i.e. identity, retrieval, and offline and offline knapsack) are proposed and compared, providing good controlled baselines. \n\n# Weaknesses\n## Application of the proposal can be limited \n- The real-world interactions between components can be non-additive or much more complicated. The current proposed formalization cannot model and solve such scenarios, limiting the contribution of the paper. Note that the authors acknowledged such limitations.\n- Sandbox trials can take up to 30 minutes, limiting scalability on real-time use cases. \n\n## Alternative solution discussion\n- In the literature, distributed constraint optimization problem (DCOPs) community and/or constraint optimization problem (COPs) community can provide alternative modeling that can model more complicated scenarios. The authors did not provide discussion about such alternatives.", "was_revised": true, "final_justification": "I have read the authors' responses and other reviewers' reviews. In general, I believe the authors were able to address all reviewers' concerns. \n\nThe acknkowledged weaknesses that I have included in my reviews limited the contribution of the proposed framework, thus I couldn't increase my score.", "rebuttal": "We sincerely appreciate the reviewer’s thoughtful review and positive feedback on our work’s novelty, evaluation, and design. We’re glad that the reviewer found the problem formulation well-motivated and the empirical results compelling.\n\nRegarding the limited application, we agree this is an important direction for future work, and we’ve noted it in the paper’s limitations. Extending the framework to capture more complex dependencies (e.g., via learned or hierarchical utilities) is a promising next step. Also, while sandbox trials are time-intensive, we emphasize that our online knapsack approach is lightweight during deployment; the overhead arises primarily during the initial composition. We’ll clarify this distinction in the revision.\n\nWe also appreciate the suggestion to discuss DCOP/COP alternatives. We will clarify in the text that while DCOP/COP techniques are relevant in spirit, our online knapsack formulation offers a tailored solution i.e. it explicitly addresses uncertain component value estimation and cost-performance trade-offs in a way that classical DCOP algorithms would not directly handle without significant augmentation. In summary, we see our work as complementary to the DCOP/COP literature, and will add this discussion to make these distinctions and connections clear.\n\nWe believe we have addressed all the reviewer’s points and can address any further questions in the discussion."}, {"review_id": "c8CFMJLYJM", "reviewer": "Reviewer_hUWo", "summary": "This paper proposes an automated agent composition framework that dynamically selects agentic components based on budget constraints. Empirical results show that the proposed composer achieves a Pareto frontier among various agentic tools, improving success rates by up to 50% under certain budgets.", "questions": "- Q1: Does the \"Skill & Query Generation\" module incur additional cost?\n- Q2: What is the size of the benchmark used in the experiments?\n- Q3: Why are results presented only in figures rather than also in tables with direct numerical comparisons?\n- Q4: In Figure 3, what do ID and RET represent? Is RET referring to retrieval?\n- Q5: What is the vanilla baseline performance without any auxiliary tools on these benchmarks?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- This work tackles a practical and important challenge: optimizing agent performance under limited computational or monetary budgets.\n- The paper includes implementation details and detailed prompt examples, ensuring a clear illustration and enhancing reproducibility.\n### Weaknesses\n- As far as my understanding, the online knapsack algorithm selects different agents/tools for each instruction. In Table 1, are the reported agents the most frequently selected ones? If so, what threshold was used? I would recommend including a full tool usage count statistics across the benchmark to provide a more intuitive illustration.", "was_revised": true, "final_justification": "This work focus on an important challenge optimizing agent performance under limited computational or monetary budgets. The author rebuutal address most my concerns regarding experiments. I tend to give a 4 after the authors revise the paper including the additional results and clarifications.", "rebuttal": "We thank the reviewer for the detailed questions. We agree that the agentic composition is a “practical and important challenge”. We address Q1-Q5 in turn, and then additional points about tool usage and selection.\n\n**Q1: Overhead of Skill & Query Generation**\n\nThe skill and query generation step incurs an LLM inference cost only once for the entire benchmarking task, during the initial tool/agent selection phase. In other words, when a new task description is given, the composer agent uses a single prompt to generate the list of required skills and a few test queries for each skill (as described in Appendix A.1). This is a one-time upfront step for composing the agent. It is not repeated during the agent’s actual execution. Thus, the skill/query generation contributes negligibly to runtime after the agent is composed.\n\n**Q2: Benchmark Dataset Sizes**\n\nWe follow the smolagents leaderboard splits which has 32 examples for GAIA and 50 examples for SimpleQA. For MedQA, it is 100 examples. For MAC benchmark, there are 30 examples in each domain.\n\n**Q3: Availability of Numerical Results**\n\nAll numerical results are provided in the appendix. In the main paper we focused on plotting Pareto curves for clarity, but the exact numbers underlying those figures are included in Appendix A.10 (“Detailed Performance Results”). For instance, Table 4 in Appendix A.10 reports the exact success rates, number of tools used, and budget spent for each approach, domain, and budget setting. We stated in the Experiments section that only a subset of results is in the main text and the full results are deferred to Appendix A.10. In the revised version, we will more explicitly reference Appendix A.10 so that readers can easily find the complete numeric results.\n\n**Q4: Clarification of “ID” and “RET” Baselines**\n\n“ID” refers to the Identity composer, the baseline that simply selects all available components (tools or agents) for the task. This can be thought of as equipping the agent with the entire inventory (subject to no budget limit), hence an identity function on the inventory. “RET” refers to the Retrieval composer, the baseline that uses semantic similarity to pick tools/agents relevant to the task description. In our implementation, the retrieval composer parses the task into skill descriptions and then selects the top-1 component per skill by embedding similarity matching (this is analogous to a purely LLM- or embedding-driven selection based on descriptions). Please see Section 4 where we discuss each composer in detail.\n\n\n**Q5: Baseline Performance and Cost – Our Gains**\n\nThe smolagents leaderboard reports vanilla scores. Sonnet 3.5 v2 has success rate of 0.03 on GAIA and 0.34 on SimpleQA. This is significantly lower than the baselines that use all tools (0.47 on GAIA; 0.8 on SimpleQA) or optimized set of tools with online knapsack (0.47 on GAIA; 0.92 on SimpleQA). We highlight in the paper that our composer matches the all-tools agent’s success with 98.5% less cost. This demonstrates that naive approaches (either using no tools or using all tools) are suboptimal: our optimized selection greatly boosts success over using none, and avoids the huge cost of using everything. We will include the vanilla scores in the camera-ready.\n\n\n**​​Tool Usage Statistics and Selection Process Clarification**\n\n**Tool Selection Process Clarification:** Reviewer asks whether “the online knapsack algorithm selects different agents/tools for each instruction”. For each benchmarking dataset/task, the same agents/tools are selected for that domain by online knapsack algorithm (same applies to other algorithms as well). This entire selection process happens once per task composition, and thereafter the chosen tools/agents are used by the main agent to solve the user’s query. During inference/evaluation, the agent may pick different tools (or supervisor agent pick different agents) depending on that instruction. \n\n**Tool Usage Statistics:** We have added an analysis of tool usage to the appendix to address the reviewer’s request. In Table 1 of the paper, we list examples of which tools were chosen by each approach on GAIA and SimpleQA. To summarize those findings: the retrieval baseline often misses certain relevant tools, the offline knapsack can over-select (including some irrelevant tools), and the online knapsack picks a precise subset of tools that covers the needs without extras. For example, on GAIA the retrieval composer failed to include any web search tool (it picked only a few knowledge-base and utility tools), whereas the online knapsack composer correctly selected the paid web search tool knowing it was crucial.  We reproduce the table 1 of the tool selection statistics here for clarity:\n\n**Table: Tools selected by different composers on GAIA and SimpleQA benchmarks.**  \n\n*Retrieval composer tends to miss out on relevant tools for the task. Offline knapsack often includes too many irrelevant tools. Online knapsack has both precise and well-covered choice of tools.*\n| **Composer**            | **GAIA**                                                                                           | **SimpleQA**                                                                                          |\n|-------------------------|----------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------|\n| **Retrieval**           | pub_med, read_file, wolfram_alpha, job_title_autocomplete, get_article_content, number_fact       | wikipedia, pub_med, sources, number_fact                                                              |\n| **Offline Knapsack ($30)** | web_search_free, arxiv, wikipedia, pub_med, read_file, scholar, instantaneous_values_service, get_recordings, get_article_content, number_fact | web_search_free, wikipedia, pub_med, semanticscholar, query_by_id, standard_language_detection, get_recordings, get_article_content, symbols_faq, number_fact |\n| **Online Knapsack ($30)**  | web_search_paid, arxiv, wikipedia                                                                 | web_search_paid, web_search_free, wikipedia, semanticscholar                                           |\n\nAs seen above, the retrieval composer picked a limited subset (on GAIA it missed any web_search tool, which hurt performance), while the offline knapsack composer included a broad set (some were unnecessary, e.g. get_recordings, symbols_faq on SimpleQA, not shown fully above), and the online knapsack composer selected the most relevant tools (including the correct web search tool for each domain) and avoided redundancy. We also tracked the average number of tools used by each approach: for instance, on GAIA the retrieval baseline used ~5–6 tools, offline knapsack around 10–12 (at $30 budget), and online knapsack ~4–5 tools while achieving higher success (per Table 4). These statistics underline how our method uses fewer, more targeted tools, which contributes to its cost-efficiency."}, {"review_id": "T4E8XcsAMO", "reviewer": "Reviewer_DBQc", "summary": "This work reframes agent component selection as an online knapsack optimization problem that dynamically selects tools by empirically testing them and factors in the costs of the agents. The key contribution is framing the agent component selection as the knapsack problem conditioning on the agent’s capability, cost, and compatibility. A composer agent is used to dynamically evaluate agents and assign a ranking to the agents based on their performance. Then, a code agent is used to evaluate the selected components. Empirical evaluation on popular benchmarks shows that the proposed formulation outperforms retrieval and offline knapsack baselines.", "questions": "Is the system applicable to real-time or streaming tasks, or only pre-deployment setup?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strength\n\n- This work is well-motivated and tackles the shortcomings of retrieval-based and offline knapsack baselines.\n- The proposed composer agent that uses dynamic tests to evaluate agent’s performance using sandbox testing rather than relying on on static metadata and description is an interesting idea.\n- Evaluation demonstrates strong performance in single- and multi-agent settings (GAIA, SimpleQA, MedQA, MAC domains) with substantial gains over retrieval and offline knapsack baselines.\n\n# Weakness\n\n- Results are all single-run and do not provide any error bars. It’s unclear whether performance differences are statistically significant or how sensitive results are to budget or LLM generation variation.\n    - It would be helpful to know whether the proposed system generalizes across different prompt templates, LLM backbones (e.g., GPT-4 vs Claude 3.5), or real-world agents beyond smolagents/ToolRet.\n- The overhead runtime (10-30 mins) and compute is a tradeoff between better agents component selection and compute budget.\n- All of the tests and evaluations are performed by an LLM, which raises significant questions about the validity of the proposed method. If LLM is so good at selecting the agents, why not delegate all of the component selection process to an LLM?", "was_revised": true, "final_justification": "My concerns are largely addressed by the author's rebuttal, and I believe the proposed method is a welcome addition to the agent selection problem.", "rebuttal": "We thank the reviewer for their insightful feedback and their comment on our strongly-motivated work. We address their points below.\n\n**Statistical Robustness of Results (Variance Across Runs)**\n\nWe have conducted additional runs to measure variance. In particular, we report the SimpleQA evaluation with Claude 3.5 Sonnet v2 three times (with different random seeds affecting the LLM’s tool-use decisions) and computed mean success rates and standard deviations for each approach. The results are summarized below:\n\n**Table: Statistical Testing on SimpleQA with Claude 3.5 Sonnet v2 (3 runs)**\n\n| Method | Budget | Success Rate | # Tools | Total Price | Avg Duration (s) | Tool Calls/Example |\n|--------|--------|--------------|---------|-------------|------------------|-------------------|\n| **Identity** | No limit | 0.840 ± 0.033 | 122 | $398.00 | 13.03 ± 0.62 | 2.55 ± 0.04 |\n| **Offline-KP** | $10 | 0.213 ± 0.009 | 3 | $9.00 | 14.68 ± 0.16 | 3.95 ± 0.01 |\n| **Offline-KP** | $30 | 0.207 ± 0.009 | 10 | $30.00 | 17.23 ± 0.29 | 4.25 ± 0.03 |\n| **Online-KP** | $10 | 0.860 ± 0.028 | 3 | $9.00 | 12.44 ± 1.04 | 2.77 ± 0.05 |\n| **Online-KP** | $30 | 0.873 ± 0.034 | 3 | $14.00 | 11.71 ± 0.68 | 2.81 ± 0.01 |\n\n- **Online-KP achieves comparable or better performance than Identity** (87.3% vs 84.0%) while using **97.5% fewer tools** (3 vs 122)\n- **Online-KP with $10 budget** achieves 86.0% success rate, outperforming Identity's 84.0%\n- **Efficiency Gains**: Online-KP ($10) achieves 0.096 success rate per dollar vs Identity's 0.002\n\nAs shown, the standard deviations are low across all metrics (e.g., success rate SD <= 0.034, tool price SD = \\\\$0 for all budget-constrained methods since tool selection is deterministic), indicating that performance is stable and consistent across independent runs. Notably, the improvements of our online knapsack method are substantially larger than these error bars. For example, with a \\\\$10 budget, we observe a +64.7 percentage point gain in success rate over the offline knapsack baseline (0.860 vs. 0.213), and a 44× reduction in cost compared to the identity composer (\\\\$9 vs. \\\\$398) while achieving comparable performance. Even more remarkably, our online knapsack with a \\\\$30 budget achieves a +3.3 percentage point improvement over the identity baseline (0.873 vs. 0.840) while using 97.5% fewer tools (3 vs. 122) and reducing costs by 28× (\\\\$14 vs. \\\\$398). These margins confirm that our gains are statistically significant and not attributable to random variance. The consistency of these results across multiple runs demonstrates the reliability and robustness of our proposed approach.\n\n**Real-Time vs. Pre-Deployment Use of the Composer**\n\nOur framework is intended as a pre-deployment or initialization step, rather than something that runs in real-time for every single user query. We evaluate our agents in the same manner as many agentic benchmarks do, where it is more in a pre-deployment setup. In the setup, we simulate this composition step for each task in the benchmark (since each evaluation query is a new task). Once composed, the agent (augmented with those components) can be deployed to handle incoming user queries without running the composer each time.  It is not embedded in the agent’s step-by-step reasoning during task execution. However, we agree that it would be interesting to extend to more real-time or streaming scenarios, which can be considered for future work.\n\n**Why Not Simply Delegate to a Single Large LLM?**\n\nReviewer asks “why not delegate all of the component selection process to an LLM?” since “All of the tests and evaluations are performed by an LLM, which raises significant questions about the validity of the proposed method.” We want to clarify that no LLMs were involved in the evaluation of the single-agent experiments. We used the same evaluation method for the leaderboard where responses from the agent was compared to the ground-truth answer. LLMs were involved in the evaluation of multi-agent experiments as we had reused the MAC benchmarking setup. Regarding whether letting LLM itself select all the tools, we did experiment with a retrieval model as a baseline. What the reviewer suggests here is to replace the retriever with a call to the LLM. The rest of the process is still needed to test the agents and tools. Therefore, our online knapsack approach can be complementary with any method to “retrieve” the initial set of tools/agents.\n\n**Generalization to Other LLMs / More Experiments**\n\nWe have experiments with more models in the Appendix with Claude 3.7 and Haiku 3.5, the online knapsack yields the highest success per cost across the board. We will ensure the final version highlights this broader applicability.  We also have extended our experiments to show that our framework is not limited to the Claude family. In particular, we ran additional evaluations using four other language model backbones: Qwen-2.5 72B Instruct, LLaMA 3.3 70B Instruct, Llama 4 Maverick 17B Instruct and Llama 4 Scout 17B instruct. On these models, the absolute performance on benchmarks was indeed lower (as these models are generally less capable than Claude 3.5), but the relative improvement from using our online knapsack composer versus the retrieval baseline was consistent. This demonstrates the generality of the knapsack-based composition: it is a model-agnostic framework that can benefit any agentic system, from proprietary models like Claude to open models like LLaMA. \n\nLlama 4 Maverick 17B Instruct Model\n| Domain     |Budget| Approach             |Success Rate | Tools Used   | Budget Spent   |\n|---------------|----------|------------------------|--------------------|------------------|----------------------|\n| gaia          | -          | Identity (all tools) | 0.38               | 122               | 398.0                |\n| gaia          | 10       | Offline knapsack  | 0.19               | 3                   | 9.0                    |\n| gaia          | 10       | Online knapsack  | 0.19               | 3                   | 9.0                    |\n| gaia          | 30       | Offline knapsack  | 0.31               | 10                 | 30.0                  |\n| gaia          | 30       | Online knapsack  | 0.44               | 5                   | 20.0                  |\n| medqa      | -          | Identity (all tools) | 0.85               | 122               | 398.0                |\n| medqa      | 10       | Offline knapsack  | 0.88               | 3                   | 9.0                    |\n| medqa      | 10       | Online knapsack  | 0.91               | 3                   | 9.0                    |\n| medqa      | 30       | Offline knapsack  | 0.89               | 7                   | 21.0                  |\n| medqa      | 30       | Online knapsack  | 0.89               | 4                   | 12.0                  |\n| simpleqa   | -         | Identity (all tools)  | 0.82               | 122               | 398.0                |\n| simpleqa   | 10       | Offline knapsack  | 0.28               | 3                   | 9.0                    |\n| simpleqa   | 10       | Online knapsack  | 0.78               | 3                   | 9.0                    |\n| simpleqa   | 30       | Offline knapsack  | 0.78               | 10                 | 30.0                  |\n| simpleqa   | 30       | Online knapsack  | 0.78               | 2                   | 11.0                  |\n\nLlama 4 Scout 17B Instruct Model\n| Domain     |Budget| Approach            | Success Rate | Tools Used   | Budget Spent  |\n|---------------|----------|------------------------|--------------------|------------------|---------------------|\n| gaia          | -          | Identity (all tools)| 0.28                | 122               | 398.0               |\n| gaia          | 10       | Offline knapsack | 0.19                | 3                   | 9.0                   |\n| gaia          | 10       | Online knapsack | 0.16                | 1                   | 3.0                   |\n| gaia          | 30       | Offline knapsack | 0.31                | 10                 | 30.0                 |\n| gaia          | 30       | Online knapsack | 0.31                | 2                   | 11.0                 |\n| medqa      | -          | Identity (all tools)| 0.84                | 122               | 398.0               |\n| medqa      | 10       | Offline knapsack | 0.82                | 3                   | 9.0                   |\n| medqa      | 10       | Online knapsack | 0.82                | 1                   | 3.0                   |\n| medqa      | 30       | Offline knapsack | 0.85                | 8                   | 24.0                 |\n| medqa      | 30       | Online knapsack | 0.85                | 1                   | 3.0                   |\n| simpleqa   | -          | Identity (all tools)| 0.88                | 122               | 398.0               |\n| simpleqa   | 10       | Offline knapsack | 0.16                | 3                   | 9.0                   |\n| simpleqa   | 10       | Online knapsack | 0.82                | 1                   | 8.0                   |\n| simpleqa   | 30       | Offline knapsack | 0.8                  | 10                 | 30.0                 |\n| simpleqa   | 30       | Online knapsack | 0.82                | 4                   | 17.0                 |\n\nSee rebuttal to Reviewer HfDw for other model results due to response length constraints. We appreciate the reviewer’s suggestion to improve generalization of our experiments. At the same time, we also believe that our experiments have sufficient coverage of various models, datasets, and scenarios (e.g. single-agent vs multi-agent). For example, in publications like “AvaTaR: Optimizing LLM Agents for Tool Usage”, their experiment coverage is also on a similar number of datasets and models to ours.  We hope that reviewers will take these updated results into account when re-scoring our paper."}, {"review_id": "COr5rOORbo", "reviewer": "Reviewer_HfDw", "summary": "The paper propose a framework for agentic system composition. This framework takes into account the value of adding components (tools or sub-agents) to the system and the cost of said components, making it related to the classical knapsack problem. They propose 4 different methods to solving this problem, ranging from a baseline identity composer, to their most complex method, an Online Knapsack Composer which tests the value of components at test time on the current task.\n\nThe authors show that the online knapsack composer sits on the pareto frontier of the cost / performance plot for a number of agent benchmarks.", "questions": "(1) Can you address point (4) of weaknesses.\n\n(2) Can you address point (5) of weaknesses. \n\n(3) For ON-KP, can you explain the type of test tasks and verifications the online composer does?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n(1) The paper presentation is very clear. The cost performance tradeoff is well motivated.\n\n(2) The topic of agent composition is significant. In a growing space of agentic tools and possible sub-agents, composing optimal (task specific) agentic systems is a challenging problem.\n\n(3) The consideration of cost performance tradeoff appears to be original.\n\n\n# Weaknesses\n\n(4) While the experimental results are strong, I do not think they are thorough enough. \n\nFirstly, baseline performance using other agentic systems (that use the same base model) apart from the identity and knapsack systems suggested in this paper should be considered. If it is true that ON-KP outperforms these methods in terms of cost and success rate this would be very impressive.\n\nSecondly, I think there should be another identity baseline where the agent is at least prompted with the current amount it has spent and the cost budget. I think this baseline would be much closer to the pareto frontier than ID.\n\nThirdly, as far as I can tell, only two claude models were used as base models. It would be good to include results using other base models.\n\n(5) I have some concerns about how the cost is calculated for the results shown in Figure 3 and Figure 4. Firstly, for the sub-agent experiment, why is the cost set arbitrarily to 1 dollar as opposed to the actual subagent cost? If the subagent cost is much lower than this, the choice is artificially inflating the cost numbers, which make ID look like a very poor method.\nIn addition, on line 199, there is no explanation of the 5 dollars and 8 dollars prices that are set.", "was_revised": true, "final_justification": "The paper tackles an important question given that agentic models are progressively being access to a larger and larger number of tools. The proposed method for solving this problem is promising. Overall I still have some concerns with how the cost accounting was done for the experiments in the paper, and so keep my recommendation to borderline accept. If the ACs and other reviewers are less concerned about this point, then I would defer to them and recommend acceptance (score of 5).", "rebuttal": "We thank the reviewer’s positive remarks on the presentation and motivation of our paper. We agree that the “topic of agent composition is significant”. We appreciate the feedback and we address the questions below.\n\n**(4) ​​Baseline with Direct LLM-Based Selection & Comparisons to Agentic Baselines & More model comparisons**\n\nWe agree that an LLM-driven selection baseline is a relevant point of comparison. In fact, our implemented Retrieval composer can be seen as a proxy for this: it uses the LLM to parse the task into skills, then essentially does a lightweight selection by semantic matching. One could imagine a more direct baseline where we prompt an LLM: “Here is the task and a list of all available tools, which tools should we use?” However, with an inventory of 120+ tools, providing all descriptions to an LLM is impractical (context length issues), and such an approach would still rely on tool descriptions alone. Prior work (e.g. semantic retrieval methods in agent/tool discovery) has shown limitations of relying purely on descriptions, tools might appear useful based on their names/descriptions but not actually work well, or vice versa. Our online knapsack addresses this by testing tools to get ground-truth performance. As such, it is not directly comparable to other agentic systems that rely solely on in-context reasoning for composition.\n\nWe did not compare to, for example, an AutoGPT-style agent that can use any tool at runtime without prior selection, because that scenario is different :  it removes the notion of a budget or upfront selection, and typically such agents still face the challenge of which tools to invoke (often solved by prompt engineering or trial and error). In fact, our Identity baseline (all tools equipped) combined with the agent’s own reasoning is effectively an upper-bound agentic baseline; if such an agent cannot solve a task with all tools at hand, then composition is not the limiting factor. Thus, ON-KP is not “yet another agent architecture,” but functions as a meta-layer to improve any such architecture by wisely picking components. \n\nRegarding additional model comparisons, the appendix has additional experiments for Claude Sonnet 3.7 and Haiku 3.5.  We also have extended our experiments to verify that the benefits of our framework are not limited to the Claude 3.5 series. In particular, we ran additional evaluations using four other language model backbones: Qwen-2.5 72B Instruct model, LLaMA 3.3 70B Instruct model, Llama 4 Maverick 17B Instruct model and Llama 4 Scout 17B instruct model. On these models, the absolute performance on benchmarks was indeed lower (as these models are generally less capable than Claude 3.5), but the relative improvement from using our online knapsack composer versus the retrieval baseline was consistent. This demonstrates the generality of the knapsack-based composition: it is a model-agnostic framework that can benefit any agentic system, from proprietary models like Claude to open models like LLaMA. \n\nQwen 2.5 72B Instruct Model\n\n| **Budget** | **Domain** | **Approach**         | **Success Rate** | **# Tools Used** | **Budget Spent** |\n| :--------: | :--------: | -------------------- | :--------------: | :--------------: | :--------------: |\n|      —     |    GAIA    | Identity (all tools) |     **0.28**     |        122       |        398       |\n|      —     |  SimpleQA  | Identity (all tools) |     **0.86**     |        122       |        398       |\n|      —     |    MedQA   | Identity (all tools) |     **0.90**     |        122       |        398       |\n|    \\$10    |    GAIA    | Offline knapsack     |       0.20       |         3        |         9        |\n|    \\$10    |    GAIA    | Online knapsack      |       0.25       |         3        |         9        |\n|    \\$10    |  SimpleQA  | Offline knapsack     |       0.58       |         3        |         9        |\n|    \\$10    |  SimpleQA  | Online knapsack      |       0.78       |         3        |         9        |\n|    \\$10    |    MedQA   | Offline knapsack     |       0.82       |         2        |         6        |\n|    \\$10    |    MedQA   | Online knapsack      |       0.91       |         2        |         6        |\n|    \\$30    |    GAIA    | Offline knapsack     |       0.22       |        10        |        30        |\n|    \\$30    |    GAIA    | Online knapsack      |     **0.30**     |         4        |        12        |\n|    \\$30    |  SimpleQA  | Offline knapsack     |       0.79       |        10        |        30        |\n|    \\$30    |  SimpleQA  | Online knapsack      |     **0.89**     |         3        |        14        |\n|    \\$30    |    MedQA   | Offline knapsack     |       0.89       |         3        |         9        |\n|    \\$30    |    MedQA   | Online knapsack      |     **0.92**     |         1        |         3        |\n\nLlama 3.3 70B Instruct Model\n\n| **Budget** | **Domain** | **Approach**         | **Success Rate** | **# Tools Used** | **Budget Spent** |\n| :--------: | :--------: | -------------------- | :--------------: | :--------------: | :--------------: |\n|      —     |    GAIA    | Identity (all tools) |    **0.31**    |        122       |        398       |\n|      —     |  SimpleQA  | Identity (all tools) |     **0.78**     |        122       |        398       |\n|      —     |    MedQA   | Identity (all tools) |     **0.84**     |        122       |        398       |\n|    \\$10    |    GAIA    | Offline knapsack     |       0.24       |         3        |         9        |\n|    \\$10    |    GAIA    | Online knapsack      |       0.27       |         3        |         9        |\n|    \\$10    |  SimpleQA  | Offline knapsack     |       0.63       |         3        |         9        |\n|    \\$10    |  SimpleQA  | Online knapsack      |       0.71       |         3        |         9        |\n|    \\$10    |    MedQA   | Offline knapsack     |       0.74       |         2        |         6        |\n|    \\$10    |    MedQA   | Online knapsack      |       0.77       |         2        |         6        |\n|    \\$30    |    GAIA    | Offline knapsack     |       0.29       |         8        |        30        |\n|    \\$30    |    GAIA    | Online knapsack      |     **0.35**     |         4        |        14        |\n|    \\$30    |  SimpleQA  | Offline knapsack     |       0.75       |         8        |        30        |\n|    \\$30    |  SimpleQA  | Online knapsack      |     **0.82**     |         4        |        14        |\n|    \\$30    |    MedQA   | Offline knapsack     |       0.81       |         4        |        14        |\n|    \\$30    |    MedQA   | Online knapsack      |     **0.88**     |         3        |        11        |\n\nPlease see our rebuttal to Reviewer DBQc for more results, which we could not include here due to response length constraints.\n\n**(5) Justification of Pricing Choices for Tools and Agents**\n\nWe used simple pricing assumptions in our experiments, and we agree that transparently explaining these is important. For single-agent tools, Appendix A.5 details how we estimated each tool’s “cost”. In short, the price reflects two factors: the API cost (if the tool calls an external API that charges per use) and the additional token cost that the tool’s usage adds to the agent’s prompt (since every tool call includes the tool’s input schema). For example, we estimated that a paid API tool (like a premium web search) would cost about \\\\$5 per 5000 calls based on SerpAPI pricing, and the prompt token overhead for 5000 calls is roughly \\\\$3, so together that tool was given a price ~\\\\$8 (per 5000 uses). Free tools were assigned a lower cost (just the token overhead, \\\\$3 per 5000 uses), and partially free tools (with rate limits) were intermediate (\\\\$5). These values (\\\\$3, \\\\$5, \\\\$8) are approximate but grounded in real API rates. \n\nFor the multi-agent experiments (Figure 4): We set each sub-agent's cost to \\\\$1 as a simplification, primarily because all sub-agents in the inventory are built on the same base model and operate under simulated conditions. In this controlled setting, there is no meaningful variation in runtime or API costs between sub-agents, so assigning a uniform cost allows us to isolate and evaluate the impact of agent selection strategies. Notably, ON-KP achieves much higher success rates (0.4 and 0.87) compared to ID (0.07 for both tasks), regardless of the specific cost assignment. This indicates that the performance gap stems from more effective agent selection rather than the pricing assumption.\n\n**(Q3) Online Knapsack Query Generation and Verification Procedure**\n\nFigure 2 and Algorithm 1 show an overview of online knapsack composer. We briefly address the steps here.\nFirst, for each skill identified from the task, the composer agent generates a small set of test queries that specifically exercise that skill. \n\nNext, the candidate tool or sub-agent is then tested on each query in a sandbox environment. For tools, this means we have the main agent attempt the query with that single tool available; for sub-agents, we simulate that sub-agent alone trying to address the query. Algorithm 1 (lines 9–17) pseudocode shows the loop: for each query, we call SANDBOX(component, query) which executes the component on that query.\n\n\nAfter each trial, we invoke a judge function that inspects what happened and outputs whether the component was helpful and/or broken on that query. \n\n\nThis end-to-end procedure (skill parsing → query generation → sandbox trials → LLM judgement → knapsack selection) is what we refer to as the online knapsack composer (ON-KP). In the camera-ready, we will clarify these details if they are not clear enough."}]

Author rebuttal:

Meta-review: This paper formulates automated LLM agent design as a knapsack problem. The authors propose a structured, automated framework to achieve better performance. Rebuttal discussion further addresses the reviewers' concerns on robustness and generalizability. Based on these considerations, I recommend acceptance.
Decision: Accept (poster)