Skip to content

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

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper formalizes agentic component selection (tools, sub-agents) as an online knapsack optimization problem, replacing static semantic retrieval with empirical sandbox testing to assess real-time component utility under budget constraints. A "composer agent" iteratively tests candidate components, computes value-to-cost ratios via the ZCL algorithm, and assembles an optimal subset. Across five benchmarks, the online knapsack composer consistently Pareto-dominates retrieval baselines on the success-rate/cost frontier.

Problem

Existing agentic system design relies on static, metadata-based semantic retrieval to select tools and sub-agents. This fails because: (1) component descriptions are often incomplete or misaligned with actual capabilities; (2) retrieval ignores cost-utility tradeoffs; (3) static selection cannot handle stale, broken, or evolving components. The result is suboptimal tool/agent selection that either misses critical capabilities or wastes budget on redundant or non-functional components.

Method

The framework reduces agent composition to a multiple-choice online knapsack problem: given task τ, component inventory A (each with cost cᵢ), and budget B, find S* ⊆ A maximizing success rate subject to Σcᵢ ≤ B.

The online knapsack composer (Algorithm 1): 1. Parses the task description into a list of required skills via LLM. 2. For each skill, retrieves top-K candidate components by semantic embedding similarity (BGE-Large-EN). 3. Generates test queries per skill and sandbox-evaluates each candidate component, scoring it {−1 (broken), 0 (unhelpful), 1 (helpful)} per skill. 4. Computes value-to-cost ratio ρᵢ = vᵢ/cᵢ and applies the ZCL threshold Ψ = (U/L · e)^z · L/e (where z = fraction of budget spent), accepting the component only if ρᵢ ≥ Ψ. 5. Once a skill is covered, it is skipped for subsequent candidates; broken components are blacklisted.

An optional post-selection AvaTaR prompt optimization pass leverages the sandboxing trajectories to refine tool-use instructions. Baselines compared: identity (all tools), retrieval-only, and offline knapsack (linear programming over similarity scores, no live testing).

Key Contributions

  • Formal reduction of agentic component selection to a constrained optimization problem (knapsack variant) that jointly accounts for capability, cost, and compatibility.
  • A composer agent workflow that decomposes task descriptions into skills, generates test queries, empirically validates components via sandbox trials, and applies the ZCL online knapsack algorithm for selection.
  • Empirical validation on single-agent (tool selection: GAIA, SimpleQA, MedQA; 120-tool inventory) and multi-agent (sub-agent selection: travel, mortgage domains; 117-agent inventory) settings showing consistent Pareto-frontier placement.

Results

  • Single-agent (Claude 3.5 Sonnet, $30 budget): Online knapsack + AvaTaR is highest-performing on all three datasets (GAIA, SimpleQA, MedQA), lying on the Pareto frontier with higher success rate than identity at significantly lower cost; up to 31.6% success rate improvement over retrieval baselines; up to 80% performance gain over retrieval-based baselines (cost-adjusted).
  • Multi-agent (Claude 3.5 Sonnet, $6 budget, 117-agent inventory): Online knapsack increases success rate from 37% to 87% on travel/mortgage domains; identity composer degrades sharply at large inventory scale because the supervisor cannot delegate effectively across 100+ agents; retrieval/offline knapsack frequently selects "distractor" agents with overlapping descriptions but lacking real capabilities.
  • Results are consistent across Claude 3.5 Haiku, Claude 3.7 Sonnet, Llama 4, and Qwen 2.5 families.

Limitations

  • Requires a well-defined task description; ambiguous or exploratory goals are out of scope.
  • Sandbox testing adds 10–30 minutes of latency depending on budget; no optimized runtime solution proposed.
  • Components are tested individually, not in combination, missing interaction effects (synergies/conflicts).
  • Prompt optimization (AvaTaR) shows regression in some settings, indicating fragility.
  • Security risk: without monitoring, malicious components could be incorporated into composed agentic systems.
  • No comparison against greedy or MDP-based composition baselines.

Relevance to Agentic AI / LLM Agents

This work directly addresses the scalable assembly problem that arises as agent ecosystems grow: how to programmatically select tools and sub-agents from large inventories without manual curation. The knapsack framing bridges operations research and agentic system design (ADAS), providing a principled cost-aware alternative to RAG-style retrieval that is both more accurate and more economical. The sandbox-driven empirical valuation is practically important because it sidesteps the unreliability of natural-language capability descriptions, a well-documented failure mode in tool retrieval. For researchers building multi-agent orchestration pipelines or marketplace-style agent registries, this framework offers a concrete optimization primitive that can be composed with existing workflow engines.