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:
- Opaque Descriptions: Documentation rarely reflects real-world reliability or edge-case behavior.
- Economic Blindness: Standard retrieval ignores cost-utility trade-offs, leading to bloated token expenses or API bills.
- 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.
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:
- 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.
- Dynamic Sandboxing: Instead of trusting text metadata, the composer executes candidate components inside a sandbox environment using the generated queries to measure actual performance.
- 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.
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