BAMAS: Structuring Budget-Aware Multi-Agent Systems

AI summary

Overview

• Research area: LLM-based multi-agent systems; specifically, cost-aware system construction and orchestration (arXiv:2511.21572v1 [cs.MA], 26 Nov 2025).
• Technical level: Intermediate. The paper combines Integer Linear Programming, offline reinforcement learning, and LLM agent design, but explains each component in accessible terms.
• Scope: The paper proposes and evaluates BAMAS, a three-stage method for building multi-agent systems that respect a user-specified cost budget while maintaining competitive task accuracy. Affiliations: Peking University, University of Illinois Urbana-Champaign, Nanyang Technological University, and Tsinghua University. Code and data are released at https://github.com/chunfenri/BAMAS. The work was supported by the National Natural Science Foundation of China under grant number 62325201.

What This Paper Is About

LLM-based multi-agent systems can solve complex tasks, but their cost is driven by token consumption during LLM calls and scales unpredictably with the number of agents and the way they interact. Existing frameworks such as AutoGen, MetaGPT, and ChatDev focus on maximizing performance and treat cost as an afterthought, providing limited control over the cost-performance trade-off. The paper asks how to design a multi-agent system that delivers strong task performance while adhering to a predefined cost budget, and answers it with a method that jointly decides which LLMs to use and how they should collaborate.

Key Contributions

1. BAMAS framework. A new approach for constructing multi-agent systems under budget constraints that jointly optimizes LLM selection (via Integer Linear Programming) and agent collaboration topology (via reinforcement learning) to maximize task performance within a fixed cost budget.
2. Budget-constrained LLM provisioning. A formulation of LLM pool selection as an ILP with a recursively defined tier-weighting scheme that guarantees a lexicographically optimal (performance-first) choice within the budget, requiring at least two LLMs to form a meaningful multi-agent setup.
3. Offline reinforcement learning for topology selection. A policy trained with a REINFORCE-style objective and entropy regularization that picks among Linear, Star, Feedback, and Planner-Driven collaboration topologies based on the task and budget, using a composite reward that combines task success with budget adherence.
4. Public release and empirical validation. Evaluation on three benchmark datasets against three state-of-the-art construction approaches, showing comparable or superior accuracy with up to 86% cost reduction, plus public code and data.

Main Findings

• Cost-performance trade-off (RQ1): On GSM8K with a budget of 1,625, BAMAS achieves 95.3% accuracy, nearly matching AutoGen with DeepSeek-V3 (95.4%), at an average cost of 542.9 versus 1,425.3 — a 62% cost reduction. On MBPP, BAMAS reaches 82.6% accuracy, comparable to the state-of-the-art (82.2%), at a cost of 529.2 versus 3,735.1 — an 86% reduction. On MATH with a budget of 2,000, BAMAS surpasses existing approaches in accuracy (81.2% vs. 77.6%) while maintaining lower cost (646.0 vs. 797.2).
• Tunability: Across all three datasets, increasing the cost consistently leads to higher accuracy. Unlike the baselines, BAMAS is tunable, so practitioners can raise accuracy by allocating a larger budget.
• Budget adherence: On the 1,319 GSM8K tasks, BAMAS incurs zero out-of-budget (OOB) tasks. On MBPP, OOB counts range from 1 to 5 across the five budget settings. On MATH, the highest OOB count is 30 under a budget of 2,000, which is 3% of all tasks.
• Component analysis (RQ2): Compared with the Naive-CostAware baseline, BAMAS matches the peak accuracy of the strongest Naive-CostAware configuration on GSM8K (95.3%, achieved at L5 with DeepSeek-V3) but at a substantially lower average cost (542.9 vs. 1,650.8). On MBPP, BAMAS attains higher peak accuracy (82.6% vs. 81.6%) while incurring lower cost (529.2 vs. 1,379.1), supporting the value of joint LLM provisioning and topology selection.
• Task-specific topology selection (RQ3): The policy does not use a one-size-fits-all topology. It selects the Feedback topology for 40.1% of GSM8K tasks and 69.8% of MATH tasks, while favoring the Linear topology for the code-generation MBPP dataset.
• Risk-averse behavior under tight budgets: Across all datasets, BAMAS heavily favors the simpler Linear and Star topologies when the budget is tight, since these do not include a critic agent and thus reduce the risk of exceeding the budget; as the budget grows, it becomes more willing to select the more complex Feedback topology.
• Planner-Driven topology is never selected: Across all datasets and budgets, the reinforcement learning component never chooses the Planner-Driven topology, learning that its high cost and instability make it a suboptimal choice.
• Topology diversity tracks dataset characteristics: GSM8K topology choices are highly uniform for a given budget, whereas MATH and MBPP — which contain more diverse problem types — show a more mixed distribution at certain budget levels.

Methodology in Plain English

The problem is stated as: given a task, a set of available LLMs, and a cost budget, choose an optimal subset of LLMs and a collaboration topology that governs their interactions, with each selected LLM acting as a distinct agent.

Step 1 — Budget-constrained LLM provisioning. The available LLMs are ranked into performance tiers using the LMSys Chatbot Arena Leaderboard as a proxy. Each LLM's cost is estimated from input and output token counts multiplied by the vendor's per-token prices. Because exact token usage is unknown before execution, the authors use estimates: input tokens per call are set to 500, based on prior measurements that typical LLM input lengths fall within 128~256 tokens, roughly doubled to account for context an agent ingests from others in a multi-agent setting; output tokens are determined by sampling 50 training instances from the target dataset and using the maximum observed output length as an upper bound. A decision weight is defined for each tier, recursively from the bottom up starting at 1 for the lowest tier, such that any single LLM from a higher tier outweighs any budget-affordable group of lower-tier LLMs. An ILP then maximizes total selected weight subject to total cost not exceeding the budget and at least two LLMs being selected; multiple instances of the same LLM may be selected. Because of how the weights are built, the selected configuration is guaranteed to be lexicographically optimal.

Step 2 — Collaboration topology selection. A policy selects a topology from a curated library conditioned on the task and budget. The library contains Linear (sequential reasoning), Star (parallel hypothesis generation and evaluation), Feedback (generate-and-critique refinement cycles), and Planner-Driven (a central planner dynamically coordinating other agents). The policy is trained offline, avoiding the cost and latency of online trial-and-error with LLM calls. The reward combines a task-success term (a positive constant for success, a negative constant otherwise) with a cost term (a heavy penalty if actual cost exceeds the budget, plus a bonus scaling with the fraction of budget saved, awarded only for successful executions). Training uses a REINFORCE-style reward-weighted policy-gradient loss with an entropy regularization term to prevent premature convergence, and the parameters achieving the highest average composite reward across the offline dataset are kept.

Step 3 — Agent instantiation. Selected LLMs are assigned to roles defined by the topology. In Linear and Star, all agents are executors. In Feedback, the highest-weight LLMs serve as critics and the rest as executors. In Planner-driven, the highest- and second-highest-weight LLMs serve as planner and critics, with the remaining models as executors. The execution engine then manages information flow according to the topology.

Evaluation setup. Three datasets are used: GSM8K (first 1,000 examples from the official training set as the reinforcement learning corpus; evaluated on the full 1,319-problem test set), MBPP (all 374 training problems as the reinforcement learning corpus; evaluated on the full 500-problem test set), and MATH (stratified sampling by difficulty level and problem type to build training and test sets of 1,000 problems each, preserving the original distribution). Two LLMs are used: DeepSeek-V3 ($0.27 per million input tokens, $1.10 per million output tokens) and GPT-4.1 nano ($0.10 per million input tokens, $0.40 per million output tokens). Metrics are Accuracy (the percentage of tasks solved correctly) and Average Cost, computed per task from input and output token counts and per-token prices, multiplied by 10^6 for clearer presentation. Baselines are AutoGen, MetaGPT, and ChatDev, plus a heuristic Naive-CostAware baseline that greedily picks configurations at five resource levels, where Level i uses i+1 LLMs and a static linear topology. All baselines are restricted to DeepSeek-V3 and GPT-4.1 nano to match BAMAS; for MATH, which incurs substantially higher costs, baseline results are reported only with GPT-4.1 nano.

Note on a reported inconsistency: the "Configuration of BAMAS" section states the five budget levels for GSM8K and MBPP as 500, 875, 1,250, 1,650, and 2,000, while Tables 1, 3, and 4 report the fourth level as 1,625. MATH uses three budget levels: 1,000, 2,000, and 3,000. The minimum budget is defined as the estimated cost of executing a viable workflow with two LLMs, which is 500 for GSM8K and MBPP and 1,000 for MATH. Additional hyperparameter configurations are described as being in Appendix B, which is truncated in the provided content; the specific values of the learning rate, entropy coefficient, and batch size are therefore not reported here.

Why This Matters

• Impact on research: The paper reframes LLM allocation in multi-agent systems as a constrained optimization problem rather than an afterthought, and shows that topology choice can be learned rather than hard-coded. It also provides evidence that a single strong model is often preferable to ensembles of weaker ones for complex reasoning under budget, and that complex orchestrators (Planner-Driven) may be rejected by learned policies as too costly and unstable.
• Real-world applications:
  • Deploying code-generation assistants where per-task API spend must stay within a fixed envelope, using the Linear topology the policy favors for such tasks.
  • Mathematical reasoning and tutoring systems, where the Feedback topology's generate-and-critique loop dominates for 40.1% of GSM8K tasks and 69.8% of MATH tasks.
  • Enterprise agent platforms that need predictable, auditable per-run cost ceilings rather than open-ended token spend.
  • Multi-model routing services that must decide, per request, which vendor models to call and in what pattern given a price list and a budget.
• Industry relevance: Cost predictability is a gating factor for production deployment. BAMAS reports rare out-of-budget occurrences (zero on all 1,319 GSM8K tasks; at most 30 of 1,000 MATH tasks at a budget of 2,000) and up to 86% cost reduction at comparable accuracy, which is directly relevant to teams operating LLM pipelines at scale with per-task cost limits.

Future Directions

• Broaden the LLM pool. The experiments use only two representative LLMs (DeepSeek-V3 and GPT-4.1 nano); testing provisioning across a larger, more heterogeneous pool of models and vendors is an open extension.
• Richer topology libraries. The action space contains four curated topologies, and the Planner-Driven option is never selected; whether more structured or hybrid patterns, or repairs to the Planner-Driven design, could be learned and chosen is unresolved.
• Reduce out-of-budget incidents further. Cost is non-deterministic before execution, and OOB tasks still occur on MBPP (1 to 5) and MATH (up to 30). Tighter cost estimation or runtime budget enforcement could close this gap.
• Transfer and generalization. Whether a topology selection policy trained offline on these datasets transfers to new task domains, or requires new offline experience data per domain, is not established in the reported results.

Target Audience

Researchers and engineers working on LLM-based multi-agent systems, agent orchestration, and cost-efficient AI deployment. It is most useful to readers with some familiarity with multi-agent frameworks (AutoGen, MetaGPT, ChatDev) and basic optimization or reinforcement learning concepts, and to practitioners who need to operationalize agent pipelines under explicit monetary budgets.

Authors’ abstract

Large language model (LLM)-based multi-agent systems have emerged as a powerful paradigm for enabling autonomous agents to solve complex tasks. As these systems scale in complexity, cost becomes an important consideration for practical deployment. However, existing work rarely addresses how to structure multi-agent systems under explicit budget constraints. In this paper, we propose BAMAS, a novel approach for building multi-agent systems with budget awareness. BAMAS first selects an optimal set of LLMs by formulating and solving an Integer Linear Programming problem that balances performance and cost. It then determines how these LLMs should collaborate by leveraging a reinforcement learning-based method to select the interaction topology. Finally, the system is instantiated and executed based on the selected agents and their collaboration topology. We evaluate BAMAS on three representative tasks and compare it with state-of-the-art agent construction methods. Results show that BAMAS achieves comparable performance while reducing cost by up to 86%.