> Paper: BAMAS: Structuring Budget-Aware Multi-Agent Systems > Authors: Liming Yang, Junyu Luo, Xuanzhe Liu, Yiling Lou, Zhenpeng Chen > Paper: https://arxiv.org/abs/2511.21572 > Code: https://github.com/chunfenri/BAMAS > In one sentence: the first budget-aware dynamic multi-agent architecture that uses integer programming for model selection and reinforcement learning for topology selection, cutting API costs by 86% without sacrificing performance.
1. The Pain Point: Capability Is Burned with Tokens
Multi-agent systems (MAS) built on frameworks like AutoGen, MetaGPT, and ChatDev let multiple LLM agents collaborate on complex tasks—but their capability comes at a token cost. A single complex task may require 10–50 LLM API calls, each with hundreds to thousands of tokens, with agents iterating and revising repeatedly. For example, one MetaGPT programming run can call DeepSeek-V3 dozens of times, easily exceeding $3 per run; at 1,000 runs per day, that's ~$90,000/month.
Worse, existing frameworks are "performance first, cost be damned": AutoGen's call counts are uncontrollable, MetaGPT calls the LLM at every fixed step, and ChatDev's virtual-company simulation uses many agents and deep dialogue rounds. None has built-in budget control—enterprises either accept huge bills or manually truncate and break tasks.
2. BAMAS's Three Components
BAMAS's core idea: push budget constraints forward into every step of system design, rather than stopping losses after the fact.
Component 1: Budget-Constrained LLM Configuration (ILP)
Given budget B, select the optimal subset of LLMs: 1. Tier all available LLMs by performance (per LMSys Chatbot Arena rankings) 2. Assign decision weights so a single higher-tier LLM outweighs any affordable combination of lower-tier ones 3. Solve an integer linear program (PuLP + CBC): maximize total selected weight, subject to total cost ≤ B and selecting at least 2 LLMs
The result is a lexicographically optimal pool—strongest models first within budget. Cost estimation uses a fixed 500-token input estimate and a sampled upper bound on output length (max output over 50 training instances).
Component 2: Collaboration Topology Selection (Offline RL)
A topology library offers four options:
- Linear: sequential reasoning; good for multi-step reasoning tasks
- Star: parallel hypothesis generation plus aggregation; good for decomposable problems
- Feedback: generate–critique–revise loops; good for iterative refinement
- Planner-Driven: a central planner agent coordinates dynamically; for open-ended tasks
- Math tasks (GSM8K, MATH) favor the Feedback topology (40.1% and 69.8%), since iterative refinement helps
- Code generation (MBPP) favors Linear, matching step-by-step construction
- Low budgets favor simple topologies (Linear/Star, no Critic); high budgets permit the stronger-but-pricier Feedback—risk-averse behavior learned automatically by the RL policy
- Paper: BAMAS: Structuring Budget-Aware Multi-Agent Systems (arXiv:2511.21572)
- Code: https://github.com/chunfenri/BAMAS
- Components: ILP budget-constrained LLM configuration + RL topology selection + agent instantiation/execution
- Benchmarks: GSM8K, MBPP, MATH
- Key results: MBPP −86% cost (529 vs 3,735), GSM8K −62%, MATH cheaper and more accurate
- Topologies: Linear, Star, Feedback, Planner-Driven (never selected)
- Budget overruns: < 3% of tasks
An offline RL policy (REINFORCE with entropy regularization) is trained on pre-collected (task, budget, topology, outcome) tuples. State: task description (384-d MiniLM embedding) + budget scalar. Action: pick one of four topologies. Reward: composite of task success (+C_succ / −C_fail), heavy penalty for budget overflow (−C_overflow), and a bonus for succeeding under budget.
Key finding: the Planner-Driven topology was never selected—the policy learned its cost and instability aren't worth it.
Component 3: Agent Instantiation and Execution
Agents are instantiated per the selected pool and topology: high-weight LLMs take key roles (Critic, Planner); low-weight ones act as Executors. If cumulative cost exceeds budget, execution terminates immediately.
3. Results: 86% Cost Cut, No Performance Loss
Datasets: GSM8K (1,319 test problems), MBPP (500 Python tasks), MATH (1,000 problems). Available LLMs: DeepSeek-V3 ($0.27/$1.10 per million tokens) and GPT-4.1 nano ($0.10/$0.40).
| Benchmark | BAMAS | Baseline | Result | |---|---|---|---| | GSM8K | 95.3% acc, cost 542.9 | AutoGen + DeepSeek-V3: 95.4%, 1,425.3 | 62% cheaper, accuracy on par | | MBPP | 82.6% acc, cost 529.2 | MetaGPT + DeepSeek-V3: 82.2%, 3,735.1 | 86% cheaper, slightly better accuracy | | MATH | 81.2% acc, cost 646.0 | AutoGen + GPT-4.1 nano: 77.6%, 797.2 | Cheaper and more accurate |
Budget compliance: BAMAS rarely overruns—0 of 1,319 GSM8K tasks, at most 5 of 500 MBPP tasks (1%), at most 30 of 1,000 MATH tasks (3%), because the ILP strictly bounds cost at configuration time.
Ablation vs. greedy (Naive-CostAware): on GSM8K, a greedy tier-based strategy matching 95.3% accuracy costs 1,650.8 vs. BAMAS's 542.9—joint ILP+RL optimization is roughly 3x cheaper at the same accuracy.
Topology selection is task-driven and budget-sensitive:
4. Why It Matters
1. From post-hoc patches to front-loaded constraints: budgets are embedded in model selection (ILP) and topology choice (RL), not bolted on as truncation. 2. Tunable cost-performance trade-offs: on GSM8K, budget 500 → cost 222 / 87.9% accuracy; budget 1,625 → cost 543 / 95.3%; enterprises can pick the sweet spot. 3. A win for small models: the ILP often picks mixed pools (one strong + several weak models), beating all-strong-model configurations on cost with near-equal performance. Not every agent needs the strongest model—key roles get strong models, executor roles get cheap ones. 4. Enterprise necessity: BAMAS answers the deployment question directly—given a budget, what performance is achievable? Or given a performance target, what's the minimum budget?
5. Limitations and Outlook
1. Only two LLMs tested (DeepSeek-V3, GPT-4.1 nano); richer model pools enlarge the ILP search space but the principle holds. 2. Offline RL data dependency: new task types require recollecting data and retraining; online RL avoids this but is too expensive. 3. Limited topology library: four hand-designed topologies; dynamic, adaptive topologies aren't covered. 4. Latency ignored: only cost (tokens × price) is optimized; parallel topologies may be faster but pricier. 5. Per-task budgets: streaming or continuously running systems may need dynamic budget allocation.
6. One-Line Takeaway
The core insight of BAMAS: multi-agent cost is not fixed overhead but a design variable that systematic optimization can slash dramatically. By combining ILP-based LLM selection with RL-based topology selection, BAMAS cuts API costs by up to 86% without sacrificing performance—a paradigm shift from "burn money for capability" to "spend carefully," and a key step from lab toys to enterprise-grade multi-agent deployment.
References