MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems?
Source: arXiv:2606.23664 · Published 2026-06-22 · By Juyang Bai, Laixi Shi
TL;DR
This paper investigates the underexplored question of how prompt optimization, a technique well-established for single LLMs, transfers to multi-agent systems (MAS) composed of multiple LLM-based agents collaborating on complex tasks. MAS architectures offer scalability and specialization benefits but introduce a combinatorial explosion of prompt search space due to interactions and coordination. The authors introduce MAS-PromptBench, a comprehensive benchmark that evaluates system-prompt optimization across a diverse set of MAS configurations varying tasks, workflow topologies, communication protocols, and team sizes. They adapt two state-of-the-art single-agent prompt optimizers (GEPA and MIPRO) to the MAS setting and conduct large-scale systematic evaluations. Results demonstrate that prompt optimization can yield substantial performance gains (up to +24 percentage points) on tasks and MAS configurations with structured workflows and explicit, verifiable agent-local behaviors (notably coding and tool-calling). However, gains are more limited or even negative for reasoning tasks and very large teams, highlighting fundamental challenges in scaling and coordinating prompt optimization across agents. This work provides the first rigorous empirical roadmap identifying when and how much prompt optimization can improve MAS, laying groundwork for future algorithmic developments tailored to multi-agent settings.
Key findings
- Prompt optimization gains vary widely across tasks and topologies, from +24.0 points improvement (Sequential BFCL tool-calling task) to −16.0 points degradation (Independent topology on MATH reasoning task).
- Coding and tool-calling tasks exhibit larger average gains (+10.0 pts on APPS coding, +6.4 pts on BFCL tool-calling) than reasoning tasks (+3.2 pts on HotpotQA).
- Prompt optimization gains decrease as team size grows, with average improvements dropping from +2.4 points at 2 agents to −2.1 points at 10 agents, showing scaling challenges.
- More structured communication protocols enable larger prompt optimization gains: average gains increase from +1.6 points (Freeform) to +4.3 points (Structured) communication.
- Workflow topology strongly affects gains; Independent topology can cause prompt optimization failures, while Centralized and Decentralized topologies tend to amplify successes and failures.
- Extending the single-agent prompt optimizer GEPA to multi-agent setting (MAS-GEPA) yields diverse results: consistently improves single-agent systems but yields variable gains in MAS from positive to severe regressions.
- System prompt optimization is most effective when agent behaviors are explicit, verifiable, and locally controllable, allowing improvements to reliably propagate through the MAS workflow.
- Sequential workflows and structured communication protocols provide more consistent room for improvement via prompt optimization.
Threat model
n/a — This work focuses on empirical analysis and optimization of multi-agent system prompts rather than adversarial threat modeling or attack-defense scenarios.
Methodology — deep read
The paper defines a multi-agent system (MAS) as a tuple M = (A, G, P), where A is the set of LLM-based agents, G is the inter-agent coordination workflow graph (topology), and P is the communication protocol. Each agent is assigned a learnable system prompt that instructs its behavior. Tasks are drawn from distributions across reasoning, coding, and tool-calling domains, and outputs are evaluated against ground-truth references via task-specific metrics (accuracy, pass@1, exact match, etc.).
The core optimization problem is finding joint prompts π* maximizing expected system-level evaluation metric, subject to a budget on MAS rollout count. The authors implement two MAS extensions of state-of-the-art single-agent prompt optimizers: GEPA and MIPRO. These optimize each agent's prompt sequentially using feedback signals from the overall MAS execution and individual agent traces.
They introduce MAS-PromptBench, a benchmark evaluating prompt optimization gains across modular MAS configuration axes: 9 tasks (3 reasoning, 3 coding, 3 tool-calling), 5 workflow topologies (Single, Independent, Sequential, Centralized, Decentralized), 3 communication protocols (Freeform, Semi-structured, Structured), and 4 team sizes (2, 4, 8, 10 agents). Popular MAS frameworks (LangGraph, CrewAI, AutoGen, OpenAI agents SDK) provide varied baseline topologies for empirical comparisons.
Extensive empirical studies are run primarily using MAS-GEPA across configurations holding the model fixed, reporting prompt-optimization gains as performance deltas between optimized and initial prompts. Detailed results are aggregated by task, topology, communication protocol, and team size. Experiments show that prompt optimization generally outperforms baseline default prompts but with wide variance dependent on MAS setup.
The authors carefully analyze failure and success modes to identify factors impacting gains such as task structure, agent coordination complexity, and communication format. The benchmark design allows controlled component-wise ablations isolating each factor while fixing others. Code and benchmark datasets are publicly released for reproducibility. However, open questions remain on optimizing larger teams, dynamic workflow topologies, and end-to-end joint prompt-topology tuning.
In one example from the APPS coding task with Sequential topology, MAS-GEPA improves pass@1 from 62% to 80%, a +18 point gain, driven by optimized prompts that better instruct intermediate subtask formulation and error checking across chained agents.
Overall, the methodology balances broad empirical coverage with detailed controlled evaluation to systematically characterize the landscape of MAS prompt optimization.
Technical innovations
- MAS-PromptBench: the first comprehensive and modular benchmark suite for evaluating prompt optimization across multi-agent LLM systems varying tasks, workflows, communication protocols, and team sizes.
- Natural multi-agent extensions of state-of-the-art single-agent prompt optimizers (GEPA and MIPRO) tailored to sequential per-agent prompt updates guided by both global MAS metrics and local feedback.
- Characterization of when prompt optimization helps MAS performance, showing dependence on task decomposability, workflow topology, communication protocol structure, and team size scalability.
- Identification of new challenges in MAS prompt optimization such as coordination complexity and prompt interference, highlighting the need for topology-aware and communication-structured optimizers.
Datasets
- GPQA-Diamond — size unspecified — public dataset (reasoning)
- HotpotQA — size unspecified — public dataset (reasoning)
- MATH — size unspecified — public dataset (reasoning)
- LiveCodeBench — size unspecified — public dataset (coding)
- APPS — size unspecified — public dataset (coding)
- SWE-Bench Verified — size unspecified — public dataset (coding)
- BFCL — size unspecified — public dataset (tool-calling)
- ToolHop — size unspecified — public dataset (tool-calling)
- API-Bank — size unspecified — public dataset (tool-calling)
Baselines vs proposed
- Single-agent baseline on APPS: pass@1 = 52.0% vs MAS-GEPA optimized: 66.0% (+14.0 points)
- MAS-GEPA on Sequential BFCL: accuracy 60.0% baseline vs 84.0% optimized (+24.0 points)
- Independent topology on MATH: accuracy 76.0% baseline vs 60.0% optimized (−16.0 points)
- Centralized topology on APPS: pass@1 70.0% baseline vs 84.0% optimized (+14.0 points)
- HotpotQA under Freeform vs Structured communication protocols: average gains +1.6 pts vs +4.3 pts
- MAS-GEPA average gain Single agent: +4.2 points vs Decentralized MAS: +2.3 points
- Team size 2 agents average gain: +2.4 points vs 10 agents: −2.1 points
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.23664.
Fig 2: Overview of benchmark MAS-PromptBench. Given an input task, a multi-agent system produces
Limitations
- The explored MAS prompt optimizers (MAS-GEPA, MAS-MIPRO) optimize agent prompts sequentially and separately, potentially limiting joint prompt interaction effects.
- Empirical studies rely on fixed MAS topologies and communication protocols; dynamic or learned workflows are not explored.
- Dataset sizes and precise details on training compute and hyperparameters are not fully specified, affecting reproducibility granularity.
- The results focus on performance gains and failures but lack robustness tests under adversarial agents or distribution shifts.
- Scaling prompt optimization beyond 10 agents shows diminishing or negative returns, showing unresolved scalability challenges.
- The benchmark primarily studies system prompt text instructions and does not optimize other instruction layers such as skills or tool interfaces.
Open questions / follow-ons
- How to design topology-aware and communication-structured prompt optimizers that dynamically adapt to workflow graphs?
- Can joint optimization of prompts alongside MAS orchestration components (e.g., communication protocols, team size) yield better scaling and robustness?
- What techniques can mitigate negative interference and cascading failures when optimizing prompts for large MAS teams?
- How do prompt optimization gains translate to real-world MAS deployments involving dynamic environments, non-stationary tasks, and adversarial settings?
Why it matters for bot defense
For bot-defense and CAPTCHA engineers interested in multi-agent LLM systems, this paper illuminates the nuanced effects of prompt engineering in distributed LLM workflows. It highlights that optimizing agent roles and instructions via system prompts can substantially improve MAS task performance—particularly when task subcomponents are well-structured and agent coordination is explicitly defined. Conversely, naive or uncoordinated prompt modifications can degrade system-level accuracy, especially as team size grows or workflows become complex.
Practitioners designing multi-agent bots for detection, challenge generation, or human interaction can glean that prompt optimization is a promising lever to improve MAS reasoning and tool-use abilities without retraining models. However, to harness it effectively requires careful attention to MAS topology and communication design to preserve and propagate local improvements. This study also signals that prompt improvements for MAS may not transfer as directly as in single-agent systems, so evaluation frameworks like MAS-PromptBench are essential for diagnosing when prompt tuning helps or harms.
Cite
@article{arxiv2606_23664,
title={ MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems? },
author={ Juyang Bai and Laixi Shi },
journal={arXiv preprint arXiv:2606.23664},
year={ 2026 },
url={https://arxiv.org/abs/2606.23664}
}