Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection

Michelle Yuan, Khushbu Pahwa, Shuaichen Chang, Mustafa Kaba, Jiarong Jiang, Xiaofei Ma, Yi Zhang, Monica Sunkara

TL;DR

This paper introduces an automated framework that treats AI agent composition as a constrained optimization problem—specifically, an online knapsack problem. By dynamically testing tools and sub-agents in a real-time sandbox rather than relying on static text descriptions, the framework selects the most cost-effective components under a strict budget, boosting single-agent success rates by up to 31.6% and multi-agent success rates from 37% to 87%.

What Problem Does This Paper Address?

Building effective LLM-based agents requires equipping them with the right tools, APIs, and specialized sub-agents. However, as the ecosystem of available components grows, developers face a combinatorial explosion of choices.

Traditional methods rely on semantic retrieval (like RAG) to match a task description to tool documentation. This approach suffers from three major flaws:

  1. Opaque Descriptions: Documentation rarely reflects real-world reliability or edge-case behavior.
  2. Economic Blindness: Standard retrieval ignores cost-utility trade-offs, leading to bloated token expenses or API bills.
  3. Static Architectures: Systems cannot dynamically adapt when components change, break, or experience rate limits.

This paper tackles the "paradox of choice" by engineering a composer agent that systematically balances capability, cost, and compatibility.

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 to accomplish goals as set by the user at inference.

Methods

The authors formalize agent composition as a classic Knapsack Problem: maximize the system's probability of success given a fixed budget constraint ($B$). They introduce an Online Knapsack Composer that operates via an iterative discovery and testing workflow:

  1. Skill & Query Generation: The composer parses a task description into a fine-grained list of required skills and automatically generates practical test queries and reference plans for each.
  2. Dynamic Sandboxing: Instead of trusting text metadata, the composer executes candidate components inside a sandbox environment using the generated queries to measure actual performance.
  3. Threshold-Based Selection: Utilizing the ZCL online knapsack algorithm, the framework computes a dynamic value-to-cost threshold based on how much budget has already been spent. A component is only added to the agentic system if its empirical utility-to-price ratio exceeds this threshold.

Additionally, the authors integrate an optimization layer using AvaTaR, which refines the agent's system prompt based on sandbox failure trajectories to improve tool-calling clarity.

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.1). Then, the composer retrieves components from the inventory given skill descriptions. With the retrieved components, the composer tests them individually. If value-to-price ratio meets the online knapsack threshold, then it is added as part of the agentic system. Otherwise, the search continues.

Datasets

The framework was evaluated across two distinct setups using Claude 3.5/3.7 Sonnet, Qwen 2.5, and Llama 3.3 models:

  • Single-Agent Tool Selection: Evaluated on GAIA (complex general assistant tasks), SimpleQA (factuality and short-form web search), and MedQA (clinical knowledge questions from US medical licensing exams).
  • Multi-Agent Collaboration: Evaluated on enterprise benchmarks covering Travel and Mortgage planning domains, utilizing a hierarchical multi-agent collaboration dataset. The authors synthetically expanded the inventory to over 100 agents to test scalability.

Key Insights and Ideas

  • Don't Trust the Docs, Test the Code: Semantic retrieval often falls for "semantic distractors"—tools that sound perfect in an embedding space but lack the actual capability to execute. Sandboxing exposes these flaws immediately.
  • Uncovering Hidden Constraints: In one experiment, an offline optimizer selected a free web search tool based on description alone, which failed due to severe rate limits. The online knapsack composer detected this failure in the sandbox and opted for a paid search tool instead, yielding a much higher task success rate.
  • Smarter Multi-Agent Delegation: In large-scale multi-agent networks, giving a supervisor agent access to all 100+ sub-agents causes confusion and delegation failures. Pruning the inventory down to a tightly optimized "knapsack" of sub-agents dramatically improves coordination.

Key Results

The online knapsack composer consistently hit the Pareto frontier, achieving optimal accuracy at a fraction of the cost of the baseline models:

  • Single-Agent Performance: On the SimpleQA dataset with Claude 3.5 Sonnet, the online knapsack composer with prompt optimization achieved an 82% success rate on a tight $10 budget, vastly outperforming the standard retrieval baseline which sat at 24%.
  • Multi-Agent Performance: In the Mortgage domain, when selecting from an inventory of over 100 diverse agents, the framework raised the overall goal success rate from 37% (baseline) to 87% under a $6 budget limit.

Limitations and Future Work

  • Dependency on Task Clarity: The framework assumes that the initial task description is well-defined. If a user's goals are highly ambiguous or exploratory, the skill-parsing step may falter.
  • Time Overhead: Running real-time sandbox trials is computationally expensive, taking between 10 to 30 minutes per composition depending on the budget. This makes it ideal for development-time configuration rather than real-time, inference-time adjustments.
  • Security Risks: Automatically executing and composing third-party tools introduces potential security vulnerabilities if malicious or compromised components exist within the inventory. Future work must integrate strict safety guardrails into the sandboxing phase.

Summary updated

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.
BibTeX
@inproceedings{yuan2025automated,
  author = {Michelle Yuan and Khushbu Pahwa and Shuaichen Chang and Mustafa Kaba and Jiarong Jiang and Xiaofei Ma and Yi Zhang and Monica Sunkara},
  title = {{Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=1LPPMAUlaT},
}
Figure