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.

(4) ​​Baseline with Direct LLM-Based Selection & Comparisons to Agentic Baselines & More model comparisons

We 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.

We 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.

Regarding 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.

Qwen 2.5 72B Instruct Model

Llama 3.3 70B Instruct Model

Please see our rebuttal to Reviewer DBQc for more results, which we could not include here due to response length constraints.

(5) Justification of Pricing Choices for Tools and Agents

We 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.

For 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.

(Q3) Online Knapsack Query Generation and Verification Procedure

Figure 2 and Algorithm 1 show an overview of online knapsack composer. We briefly address the steps here. First, for each skill identified from the task, the composer agent generates a small set of test queries that specifically exercise that skill.

Next, 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.

After each trial, we invoke a judge function that inspects what happened and outputs whether the component was helpful and/or broken on that query.

This 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.

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.

Q1: Overhead of Skill & Query Generation

The 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.

Q2: Benchmark Dataset Sizes

We 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.

Q3: Availability of Numerical Results

All 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.

Q4: Clarification of “ID” and “RET” Baselines

“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.

Q5: Baseline Performance and Cost – Our Gains

The 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.

​​Tool Usage Statistics and Selection Process Clarification

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.

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:

Table: Tools selected by different composers on GAIA and SimpleQA benchmarks.

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.

As 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.

As we have a few more days until the discussion period is over, we hope the reviewer can carefully look at our rebuttal and see whether we have addressed your concerns. Please let us know if you have any further questions and whether there are any changes in the review for this paper. Thank you!

We thank the reviewer for their insightful feedback and their comment on our strongly-motivated work. We address their points below.

Statistical Robustness of Results (Variance Across Runs)

We 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:

Table: Statistical Testing on SimpleQA with Claude 3.5 Sonnet v2 (3 runs)

• Online-KP achieves comparable or better performance than Identity (87.3% vs 84.0%) while using 97.5% fewer tools (3 vs 122)
• Online-KP with $10 budget achieves 86.0% success rate, outperforming Identity's 84.0%
• Efficiency Gains: Online-KP ($10) achieves 0.096 success rate per dollar vs Identity's 0.002

As 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$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.

Real-Time vs. Pre-Deployment Use of the Composer

Our 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.

Why Not Simply Delegate to a Single Large LLM?

Reviewer 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.

Generalization to Other LLMs / More Experiments

We 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.

Llama 4 Maverick 17B Instruct Model

Llama 4 Scout 17B Instruct Model

See 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.

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.

Regarding 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.

We 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.

We believe we have addressed all the reviewer’s points and can address any further questions in the discussion.