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

AI summary

Overview

• Research area: Agentic AI system design, automated agent/tool composition, and operations research (knapsack optimization), evaluated with large language model agents on question-answering and enterprise task benchmarks.
• Technical level: Intermediate. The paper formalizes a constrained optimization problem but presents its workflow, algorithms, and empirical results in mostly accessible terms; readers benefit from basic familiarity with LLM agents, semantic retrieval, and combinatorial optimization.
• Scope in one sentence: The paper frames the selection of tools and sub-agents for an AI system as an online knapsack problem, and shows through experiments with Claude 3.5 Sonnet on five benchmarking datasets that testing components in a sandbox before selecting them yields higher success rates at lower cost than retrieval-based selection.

What This Paper Is About

As the ecosystem of AI models, APIs, and specialized agents grows, developers face a combinatorial explosion of possible configurations for assembling an agentic system. Existing methods rely on static, semantic retrieval of tools or agents from descriptions, which fails when capability descriptions are incomplete or do not match real-world behavior, and which ignores cost-utility trade-offs and budget constraints. The authors address this by treating component selection as a knapsack problem, in which a "composer agent" identifies, tests, and assembles an optimal set of components that jointly satisfies performance, budget, and compatibility requirements.

Key Contributions

1. A formalization of agent composition as a constrained optimization problem, where a subset of components is chosen to maximize the probability of task success subject to a budget constraint, explicitly bridging modular AI design and operations research.
2. A composer agent workflow that parses task descriptions into skills with descriptions, importance values, and test queries; assesses the utility of agentic components through real-time sandbox testing; and returns an optimal set of components for a given domain using the ZCL online knapsack algorithm.
3. Empirical validation across diverse domains and two settings (single-agent tool selection and multi-agent team composition), reporting consistent improvements in cost-adjusted performance, described in the introduction as up to 80% performance gains over retrieval-based baselines.
4. Concrete composer variants for comparison — identity, retrieval, offline knapsack, and online knapsack composers, plus an online knapsack variant followed by AvaTaR prompt optimization.

Main Findings

• Single-agent improvement: In the single-agent setup, the online knapsack composer shows a success rate improvement of up to 31.6% compared to the retrieval baselines.
• Multi-agent improvement: 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.
• Pareto frontier placement: With Claude 3.5 Sonnet on GAIA, SimpleQA, and MedQA, the online knapsack with AvaTaR optimization at a $30 budget is the highest-performing approach on the cost-success Pareto frontier, and online knapsack without optimization is also on the frontier for GAIA and MedQA.
• Retrieval is insufficient: Retrieval-only approaches (the retrieval composer and the offline knapsack composer) fare worse across all three single-agent datasets, validating prior findings that retrieval alone is insufficient for tool discovery.
• Tool selection quality: On GAIA and SimpleQA, the retrieval composer did not select any web search tool; the offline knapsack composer selected web_search_free, a cheaper tool with severe throttling limits; the online knapsack composer selected web_search_paid, which the authors attribute to its higher success rate.
• Multi-agent distractor avoidance: Retrieval-based methods often selected "distractor" agents that overlapped semantically with the intended agents but lacked the tools and instructions to complete tasks; the offline knapsack composer at $6 chose five agents that lacked true capabilities for the travel domain, while online knapsack consistently avoided non-operable agents.
• Identity composer fails at scale in multi-agent settings: Unlike the single-agent experiments, returning all components no longer yields high success rate because the supervisor agent has trouble delegating tasks to an inventory of more than 100 diverse agents.
• Prompt optimization effects: AvaTaR prompt optimization boosted performance for SimpleQA, attributed to clearer guidelines on query formulation, tool usage, source verification, and error recovery, but the authors report regressions in a few settings, motivating a more robust optimization method.
• Consistency across models: The appendix reports similar results on several models, including ones from the Llama 4 and Qwen 2.5 model families, with online knapsack tending to outperform baselines, and consistent results across multiple runs.
• Runtime cost: Sandbox trials take additional time, reported as 10–30 minutes depending on budget.

Methodology in Plain English

The setup assumes two inputs: a task description with a budget, and an inventory of components (tools in the single-agent case, sub-agents in the multi-agent case), where each component has a cost and a description. The goal is to pick the subset that maximizes the probability of task success without exceeding the budget — formally equivalent to a knapsack problem, except that true success probabilities are unknown until tested, components interact non-additively, and the inventory changes over time.

The authors define a progression of composers. The identity composer simply returns every component. The retrieval composer first uses a composer agent to parse the task description into up to six skills, each with a name, description, importance value, and test queries, then retrieves the top-1 component per skill by semantic similarity (embedding model: BGE-Large-English bge-large-en-v1.5). The offline knapsack composer retrieves the top-K components per skill, assigns values using retrieval similarity scores within a multiple-choice knapsack formulation solved with linear programming, and enforces both a budget constraint and a skill-coverage constraint. The online knapsack composer goes further: it actually runs the candidate component in a sandbox to measure whether it helps answer generated test queries, assigning values of 1 (helpful), 0 (not helpful), or -1 (broken). It applies the ZCL online knapsack algorithm, which sets a dynamic threshold based on how much budget has already been spent and accepts a component only if its value-to-cost ratio exceeds that threshold; the algorithm is proven to be ln(U/L)+1-competitive given lower and upper bounds L and U on the value-to-cost ratio. Two shortcut optimizations reduce runtime: broken components are flagged and never tested again, and once a skill is covered, it is not reassessed for other candidate components.

For evaluation, the selected components are equipped onto a CodeAct agent (for single-agent experiments) or a hierarchical supervisor/sub-agent team following the ReAct tool-calling setup (for multi-agent experiments), and the resulting system is run on the benchmarks. In the single-agent experiments, the tool inventory contains 120 tools drawn from real Langchain APIs and a subset of the ToolRet benchmark, with estimated costs around $3 for roughly 5K calls to a free API tool and around $5 and $8 for paid APIs; budgets were set to $10 or $30. In the multi-agent experiments, the original inventory of about 20 sub-agents was synthetically augmented to about 117 agents, each priced uniformly at $1, with budgets of $3 and $6.

Why This Matters

• Research impact: The work reframes agent and tool discovery as a constrained optimization problem rather than a pure retrieval problem, and demonstrates that empirically validating component utility in a sandbox outperforms static metadata matching. It connects multi-agent system design to classical online knapsack theory and provides baselines (identity, retrieval, offline knapsack) for future comparisons on cost-aware composition.
• Real-world applications:
  • Enterprise development teams selecting tools from internal tool registries under a compute or API budget.
  • Marketplace scenarios where automated agents assemble solutions from commercial API inventories.
  • Clinical or scientific assistance systems where specialized tools (for example scientific search) must be distinguished from general-purpose web search.
  • Customer-facing multi-agent teams in domains such as travel and mortgage, where a supervisor delegates to specialist sub-agents and distractor agents must be avoided.
• Industry relevance: The paper reports cost-adjusted success rates rather than raw accuracy, discussing Pareto frontiers, per-tool pricing, and sandbox wall-clock time of 10–30 minutes. It also ties composition to avoiding hidden technical debt from poorly organized machine learning systems, and notes that without careful monitoring, malicious or harmful components could be introduced into an agentic system.

Future Directions

• Handling ambiguous tasks: The formalization assumes the task is well-defined with a clear description; extending composition to developer goals that are ambiguous and require exploration remains open.
• Alternative and stronger comparison methods: The authors suggest comparing against simple greedy approaches and more complex formulations such as modeling agent composition as a Markov Decision Process, as well as testing combinations of components rather than evaluating them individually.
• Reducing sandbox cost: Since sandbox trials take 10–30 minutes depending on budget, a more optimized approach could reduce this overhead.
• More robust prompt optimization and learning from experience: The authors report regressions from prompt optimization in some settings and suggest a more robust optimization method, while also proposing future work on learning how to compose from past experience using more dynamic methods.

Target Audience

Researchers and engineers working on LLM agents, tool retrieval, multi-agent orchestration, and automated machine learning system design; practitioners who need to select tools or sub-agents under cost constraints in production; and operations research or optimization researchers interested in applying knapsack formulations, particularly the online ZCL algorithm, to AI system composition.

Authors’ 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.