Research map / Multi-agent systems and games / LLM agents
Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames agent composition as a knapsack problem and proposes an online knapsack composer that selects tools/sub-agents by sandbox-testing candidates against a ZCL threshold under a budget, outperforming retrieval baselines on GAIA, SimpleQA, MedQA and multi-agent travel/mortgage tasks.
Problem
Selecting reusable agentic components (tools, sub-agents) under budget constraints is hard because semantic retrieval relies on incomplete capability descriptions and ignores cost and real utility.
Approach
A composer agent parses tasks into skills, generates test queries, sandbox-tests candidate components, estimates their value from observed helpfulness, and admits them via the ZCL online knapsack value-to-cost threshold, rather than selecting by static retrieval scores.
Key results
- Online knapsack with AvaTaR optimization at $30 reaches 0.47 on GAIA and 0.92 on SimpleQA with Claude 3.5 Sonnet, versus 0.19 and 0.24 for top-1 retrieval.
- In multi-agent composition with 100+ agents, online knapsack ($6) raises mortgage goal success rate from 0.37 (top-1 retrieval) to 0.87.
- Identity composer (all 122 tools) reaches 0.47 on GAIA at $398 cost, showing cost-performance tradeoff that knapsack methods aim to reduce.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use online knapsack instead of offline knapsack | Claude 3.5 Sonnet single-agent tool composition · GAIA (budget $30) | success rate (avg): 0.41 -> 0.47 | Helped |
| add AvaTaR prompt optimization to online knapsack (ablation) | Claude 3.5 Sonnet single-agent tool composition · SimpleQA (budget $10) | success rate (avg): 0.24 -> 0.82 | Helped |
| add AvaTaR prompt optimization to online knapsack (ablation) | Claude 3.5 Sonnet single-agent tool composition · GAIA (budget $30) | success rate (avg): 0.47 -> 0.47 | No clear effect |
| add AvaTaR prompt optimization to online knapsack (ablation) | Claude 3.5 Sonnet single-agent tool composition · SimpleQA (budget $30) | success rate (avg): 0.92 -> 0.92 | No clear effect |
| add AvaTaR prompt optimization to online knapsack (ablation) | Claude 3.5 Sonnet single-agent tool composition · MedQA (budget $10) | success rate (avg): 0.91 -> 0.89 | Hurt |
| use online knapsack instead of offline knapsack | Claude 3.5 Sonnet single-agent tool composition · SimpleQA (budget $30) | success rate (avg): 0.88 -> 0.92 | Helped |
| use online knapsack instead of offline knapsack | Claude 3.5 Sonnet single-agent tool composition · MedQA (budget $30) | success rate (avg): 0.91 -> 0.93 | Helped |
| use online knapsack instead of offline knapsack | Claude 3.5 Sonnet multi-agent composition · Travel (MAC, budget $6) | Overall GSR: 0.17 -> 0.40 | Helped |
| use online knapsack instead of offline knapsack | Claude 3.5 Sonnet multi-agent composition · Mortgage (MAC, budget $6) | Overall GSR: 0.70 -> 0.87 | Helped |
| use online knapsack instead of offline knapsack | Claude 3.5 Sonnet multi-agent composition · Mortgage (MAC, budget $3) | Overall GSR: 0.67 -> 0.40 | Hurt |
Surprising findings
- Offline knapsack (retrieval-value based) sometimes selects many irrelevant tools and performs worse than online knapsack, e.g., 0.13 on GAIA at $30 with Claude 3.5 Sonnet... (Haiku table)
- Prompt optimization causes regressions in some settings, e.g., Online knapsack + OPT drops to 0.18 on SimpleQA at $10 with Haiku 3.5.
Limitations
- Assumes well-defined task descriptions; ambiguous goals are not handled.
- Sandbox trials take 10-30 minutes depending on budget.
- Prompt optimization shows regressions in a few settings and needs more robust methods.
Experimental setup
Datasets: ToolRet LangChain tools GAIA SimpleQA MedQA MAC multi-agent benchmark
Benchmarks: GAIA SimpleQA MedQA MAC travel MAC mortgage
Metrics: success rate budget spent Pareto frontier goal success rate
Baselines: identity composer top-1 retrieval offline knapsack RAG-MCP
Builds on: ZCL online knapsack algorithm CodeAct AvaTaR ADAS
Closest papers by meaning
- AgentSwift: Efficient LLM Agent Design via Value-Guided Hierarchical Search (AAAI 2026 · similarity 0.88)
- AgentSquare: Automatic LLM Agent Search in Modular Design Space (ICLR 2025 · similarity 0.88)
- AOrchestra: Automating Sub-Agent Creation for Agentic Orchestration (ICML 2026 · similarity 0.88)
- Automated Design of Agentic Systems (ICLR 2025 · similarity 0.88)
- Multi-agent Architecture Search via Agentic Supernet (ICML 2025 · similarity 0.87)
- A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.