Skip to content

BAMAS: Structuring Budget-Aware Multi-Agent Systems

🕒 Published (v1): 2025-11-26 16:48 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

BAMAS is a framework for constructing LLM-based multi-agent systems under explicit cost budgets. It jointly optimizes which LLMs to deploy (via Integer Linear Programming) and how they should collaborate (via offline reinforcement learning over four topology types). On code generation and math reasoning benchmarks, BAMAS matches state-of-the-art accuracy while cutting costs by up to 86%.

Problem

Existing multi-agent frameworks (AutoGen, MetaGPT, ChatDev) treat cost as an afterthought: they fix an LLM and a collaboration topology without any budget constraint, leading to unpredictable and often excessive token expenditure. No prior work jointly optimizes LLM allocation and agent interaction topology under a predefined cost ceiling.

Method

BAMAS has three sequential components:

  1. Budget-Constrained LLM Provisioning (ILP): Given available LLMs ranked by the LMSys Chatbot Arena leaderboard, BAMAS formulates an Integer Linear Programming problem to select the lexicographically optimal subset P ⊆ A with total estimated cost ≤ B. Decision weights Wi are constructed recursively so that any single higher-tier LLM always outweighs any budget-feasible combination of lower-tier models, guaranteeing performance-first selection. Token cost per call is estimated with Tin=500 (input) and an empirically derived maximum output length.

  2. Topology Selection via Offline RL: A policy πθ maps (task description, budget B) → topology t ∈ {Linear, Star, Feedback, Planner-Driven}. It is trained offline on pre-collected trajectories using REINFORCE with a composite reward: a binary task-success reward Rperf and a cost-efficiency reward Rcost that penalizes budget overruns and provides a savings bonus for successful under-budget runs. Entropy regularization prevents premature convergence to a single topology.

  3. Agent Instantiation: LLMs in P are assigned to roles dictated by the chosen topology. Higher-weight (stronger) LLMs fill critic/planner roles; weaker ones act as executors. The execution engine then manages inter-agent information flow according to the topology.

Key Contributions

  • BAMAS framework: first approach to jointly optimize LLM selection (ILP) and collaboration topology (offline RL) under an explicit budget constraint.
  • Lexicographic ILP formulation with recursively constructed decision weights that guarantee performance-first, budget-feasible LLM pool selection.
  • Offline RL topology selector avoiding expensive online trajectory collection in LLM environments.
  • Demonstrated that a learned topology policy adapts: favoring simpler topologies (Linear, Star) under tight budgets and iterative topologies (Feedback) for harder tasks with larger budgets.
  • Public code release at https://github.com/chunfenri/BAMAS.

Results

  • GSM8K (Budget 1,625): BAMAS 95.3% accuracy at avg cost 542.9 vs. AutoGen+DeepSeek-V3 at 95.4% / 1,425.3 — 62% cost reduction at matched accuracy.
  • MBPP (Budget 1,250): BAMAS 82.6% at avg cost 529.2 vs. MetaGPT+DeepSeek-V3 at 82.2% / 3,735.1 — 86% cost reduction at matched accuracy.
  • MATH (Budget 2,000): BAMAS 81.2% at avg cost 646.0 vs. best baseline AutoGen+GPT-4.1 nano at 77.6% / 797.2 — higher accuracy at lower cost.
  • Budget adherence: Zero out-of-budget (OOB) tasks on GSM8K; 1–5 OOB per 500 tasks on MBPP; max 30/1,000 (3%) on MATH.
  • vs. Naive-CostAware (ablation): BAMAS achieves peak GSM8K accuracy (95.3%) at avg cost 542.9 vs. 1,650.8 for greedy; peak MBPP accuracy 82.6% vs. 81.6% at cost 529.2 vs. 1,379.1.
  • Planner-Driven topology is never selected by the RL policy across all experiments.

Limitations

  • Only two LLMs evaluated (DeepSeek-V3 and GPT-4.1 nano); generalization to larger or more diverse model pools is untested.
  • Token cost estimation relies on fixed heuristics (Tin=500, max observed Tout from 50 training samples), which may not generalize to out-of-distribution tasks.
  • Topology library is small and fixed (four types); more expressive or task-specific topologies are not explored.
  • Offline RL training requires a pre-collected dataset of trajectories, which itself has an upfront execution cost; how this bootstrapping cost is amortized is not discussed.
  • Evaluation domains are limited to math word problems and Python code generation; broader task coverage (e.g., tool-use, long-horizon planning) is absent.
  • Planner-Driven topology is never chosen—suggesting the RL policy may not have learned a sufficiently broad topology space, or that topology is underrepresented in training data.

Relevance to Agentic AI / LLM Agents

BAMAS directly addresses the deployment-readiness gap in LLM multi-agent systems: most research maximizes capability without cost constraints, making production scaling impractical. By formalizing agent configuration as a constrained optimization problem (ILP + offline RL), it introduces principled cost-awareness as a first-class design axis alongside performance. The finding that topology choice matters as much as model choice—and that optimal topology is budget- and domain-dependent—is actionable for anyone designing agentic pipelines. This connects to the broader line of work on mixture-of-agents, LLM routing/cascading, and frugal AI, extending those ideas to the multi-agent collaboration structure level.