PaperlayerView exact revision on arXiv

Source-linked AI summary

MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems?

Juyang Bai, Laixi Shi

arXiv:2606.23664v1cs.LGcs.MA

TL;DR

Prompt optimization could improve MAS without model fine-tuning, but its transfer from single-agent settings is uncertain because multi-agent dependencies make the search space exponentially larger. This paper builds MAS-PromptBench to evaluate two natural optimizer extensions across tasks, workflows, communication protocols, and team sizes, finding gains up to 24.0 points alongside drops up to 16.0 points. The results identify configuration-dependent conditions for success and motivate algorithms tailored to MAS.

  • Problem

    It remains unclear whether, when, and by how much system-prompt optimization improves MAS across configurations, despite its accessibility and the lack of comparable controlled evidence.

  • Method

    The paper introduces MAS-PromptBench to evaluate natural multi-agent extensions of GEPA and MIPRO across fixed MAS configurations varying in tasks, workflows, communication protocols, and team sizes.

  • Results

    Prompt optimization yields gains up to 24.0 points but can reduce performance by as much as 16.0 points for certain MAS configurations.

  • Takeaways & Limitations

    Optimization is most effective with explicit, controllable, verifiable local behaviors, structured communication, topology awareness, and smaller teams, motivating principled MAS-specific algorithms.

  • Takeaways & Limitations

    The paper focuses on the instruction set within a broader agent input package rather than optimizing every component of that package.

Abstract

from arXiv · show

Multi-agent systems (MAS) offer a scalable path forward for agentic AI, comprising multiple LLM-based agents, each assigned a system prompt and a position within a workflow that governs inter-agent coordination and output aggregation. System prompts thus form a critical and accessible optimization surface: they specify agents' roles and behaviors, enabling system-level improvements without model finetuning. Although prompt optimization has shown substantial potential for single LLMs, extending it to MAS poses distinct challenges, notably an exponentially growing search space. It remains unclear whether, when, and by how much prompt optimization improves MAS performance, and how sensitive such gains are to system configuration. In this work, we systematically study system-prompt optimization across a broad range of MAS setups varying in task, workflow, communication protocol, and team size, benchmarking two prompt optimizers that naturally extend state-of-the-art single-agent methods. The results reveal its potential to unlock significant gains while exposing open challenges, characterizing when and how much prompt optimization helps across diverse MAS settings.

1 Introduction

Multi-agent systems make system prompts an accessible optimization surface, but prompt gains that transfer from single agents remain uncertain because inter-agent dependencies create an exponentially growing search space. MAS-PromptBench studies this question across diverse configurations and finds substantial but highly variable gains, including severe drops.

  • MAS coordinate specialized LLM agents through communication, delegation, and output aggregation, addressing bottlenecks in single-agent expertise breadth, context length, and sequential execution.
  • System prompts specify agent roles and behaviors, enabling system-level improvement without model fine-tuning while remaining practical under fixed architectures.
  • Inter-agent prompt dependencies and multi-turn coordination create an exponentially growing search space, leaving transfer of single-agent optimization gains to MAS underexplored.
  • MAS-PromptBench evaluates prompt optimization across task domains, workflow topologies, communication protocols, team sizes, and two default optimizers.
  • Prompt optimization gains reach up to 24.0 percentage points, but certain configurations experience drops of as much as 16.0 percentage points.
  • Optimization is more promising when local behaviors are explicit, controllable, and verifiable, communication has shared structure, workflows are topology-aware, and team sizes remain smaller.

2 Related Work

Prior work studies single-agent prompt optimization and MAS design, but lacks a comparable benchmark for measuring prompt-optimization gains under controlled multi-agent configurations. This work fills that gap by evaluating system prompts across tasks, workflows, communication protocols, team sizes, and optimizers.

  • Prompt Optimization for Single LLM: Single-agent prompt optimization searches discrete instruction spaces through sampling-based, feedback-based, and editing-based approaches.
  • Prompt Optimization for Single LLM: Whether single-agent prompt-optimization gains transfer to MAS remains unclear because multi-agent systems vary across tasks, workflows, communication protocols, team sizes, and optimizers.
  • Prompt Optimization in Multi-Agent LLM Systems: Existing MAS prompt optimizers often address manually designed roles, conversations, coordination patterns, or feedback-driven failures, while other methods jointly optimize prompts and orchestration.
  • Benchmarks for multi-agent LLM systems or prompt optimization: The benchmark uses fixed MAS configurations to quantify headroom relative to default prompts and provide an empirical roadmap for future optimization algorithms and MAS design.
  • Benchmarks for multi-agent LLM systems or prompt optimization: MAS-PromptBench fills the benchmark gap by measuring prompt-optimization gains under diverse tasks, workflow topologies, team sizes, and communication protocols.

3 Prompt Optimization for Multi-Agent LLM Systems

The paper models an LLM-based multi-agent system through its agents, workflow, communication protocol, and jointly optimized system prompts. Prompt optimization compares initialized and optimized prompts while holding the model parameters and surrounding configuration fixed.

  • An MAS is represented by ordered agents, an inter-agent workflow, a communication protocol, and learnable system prompts for each agent.Each agent combines fixed LLM parameters with a learnable system prompt, and the joint prompt is optimized across the system.
  • System-prompt optimization searches for joint prompts that improve the MAS output metric while keeping the model parameters fixed.The metric evaluates the MAS output against a task reference, such as a ground-truth answer or code unit tests.
  • The paper uses “system prompt” as an umbrella term for the instruction set supplied to agents, while leaving optimization of individual instruction components or combinations for future work.The broader input package can include user requests, layered instructions, skills, memory, retrieved context, and tools.
  • The study varies task distribution, workflow, team size, and communication protocol to measure when prompt optimization helps across MAS configurations.These components define the configuration used to study prompt-optimization gains.
  • The primary optimizers are GEPA and MIPRO, treated as multi-agent extensions of state-of-the-art single-agent prompt-optimization methods.The optimized prompt π⋆ is compared with the initialized prompt π0 for a fixed optimizer and configuration.

4 MAS-PromptBench: Prompt Optimization for MAS Benchmark

MAS-PromptBench addresses the lack of comparable multi-agent prompt-optimization resources with a modular benchmark spanning diverse MAS configurations. Its controlled protocol supports both broad evaluation of optimization gains and component-level studies that vary one configuration factor at a time.

  • MAS-PromptBench fills the underdeveloped benchmark gap for controlled prompt-optimization studies in multi-agent systems.The benchmark is designed for extensive investigation across diverse MAS configurations.
  • The benchmark measures prompt-optimization gain by comparing optimized prompts π⋆ with initialized prompts π0 under a fixed optimizer and MAS configuration.This comparison isolates the effect of prompt optimization for a specified task, topology, protocol, and team size.
  • Its modular design enables component-level studies that vary the optimizer, topology, communication protocol, or team size while holding other factors fixed.This supports isolating how individual MAS factors affect system-level performance.
  • The benchmark is extensible: new tasks and MAS configurations can be added as additional configuration values for different application domains and user requirements.

5 Empirical Study of Prompt Optimization in MAS

Across tasks, topologies, communication protocols, and team sizes, MAS prompt optimization produces highly configuration-dependent gains, including substantial improvements and regressions. The study finds that optimization is most promising for explicit, verifiable behaviors and structured communication, but becomes harder with larger teams and requires topology-aware methods.

  • 5 Empirical Study of Prompt Optimization in MAS: MAS-GEPA and MAS-MIPRO optimize each agent’s system prompt separately and sequentially using overall MAS evaluation feedback and agent experience traces.The benchmark studies fixed configurations across task, topology, communication protocol, and team size, with MAS-MIPRO used as an optimizer ablation.
  • 5.1 Task: +24.0 points is the largest reported gain for Sequential on BFCL, while optimization improves seven of nine tasks overall and reaches +10.0 points on APPS.Coding and tool-calling benefit more consistently than reasoning: domain-average gains are +3.7 and +4.3 points versus +1.3 for reasoning.
  • 5.1 Task: Prompt optimization has greater potential when agent-local behaviors are explicit, controllable, and verifiable, as in coding and tool-calling, than when tasks primarily require reasoning.Verifiable artifacts, structured tool interfaces, and clear outcome formats make local behaviors easier to shape and propagate through the workflow.
  • 5.2 Workflow Topology: Across four MAS topologies, average gains reach at most +2.3 points, below the single-agent baseline’s +4.2 points, and topology-specific effects range from +9.0 to −5.0 points.Table 3 reports baseline/optimized performance and signed changes for five workflow topologies; the comparison motivates topology-aware rather than one-size-fits-all optimization.
  • 5.2 Workflow Topology: Independent optimization can reduce performance by −16.0 points on MATH, whereas Centralized optimization improves APPS by +14.0 points but reduces HotpotQA by −9.0.These contrasting outcomes suggest that uncoordinated revisions may erase one another’s gains and that topology can amplify both successes and failures.
  • 5.3 Communication Protocol: Average communication-protocol gains rise from +1.6 points with Freeform messages to +2.4 with Semi-structured and +4.3 with Structured messages.The largest gains occur on HotpotQA, where agents must preserve and pass intermediate evidence; LiveCodeBench gains are smaller and less consistent.
  • 5.4 Team Size: Average gains fall from +2.4 points at n=2 to +0.6 at n=4, then become negative at n=8 and n=10, reaching −2.1 at n=10.Larger teams add handoffs and intermediate states that can dilute local improvements, while the effect also depends heavily on topology: Centralized HotpotQA falls to −12.0 at ten agents, whereas Decentralized remains nonnegative.
  • 5.5 Ablation of prompt optimizers: MAS-GEPA and MAS-MIPRO show consistent protocol trends, with MAS-MIPRO gains increasing from +0.1 under Freeform to +4.8 under Semi-structured and +6.3 under Structured communication.The largest gains remain on HotpotQA, while LiveCodeBench improvements are comparatively smaller, suggesting the pattern is not tied to one optimizer.

6 Conclusion

MAS-PromptBench shows that system-prompt optimization can substantially improve multi-agent performance, but gains vary widely and can also become harmful depending on task and configuration.

  • 6 Conclusion: Gains reach 24.0 points, while performance drops can reach 16.0 points, showing both substantial potential and substantial risk.The benchmark identifies prompt optimization as promising but not uniformly beneficial across MAS settings.
  • 6 Conclusion: Optimization works best when agent-local behaviors are explicit, controllable, and verifiable, and communication protocols impose shared structure.These properties make agent interactions easier to control and transfer.
  • 6 Conclusion: Larger teams often add coordination overhead, making prompt optimization more difficult.The findings motivate optimizers that account for task structure and MAS configuration.
  • 6 Conclusion: MAS-PromptBench provides a benchmark spanning diverse tasks, topologies, communication protocols, team sizes, and optimizers.It is intended to support development of more robust and scalable MAS prompt-optimization methods.

A.1 Frameworks

The benchmark instantiates MAS configurations across four frameworks representing graph-based, role-based, conversational, and production-oriented workflows.

  • A.1 Frameworks: Four frameworks cover graph-based orchestration, role-based collaboration, conversational interaction, and production-oriented agent workflows.Together, they provide diverse execution environments for evaluating prompt optimization.
  • A.1 Frameworks: LangGraph represents agents as graph nodes with directed edges, enabling sequential, branching, and cyclic coordination with explicit routing and state propagation.It is used where control over workflow routing and state is required.
  • A.1 Frameworks: CrewAI organizes agents around specialized responsibilities, predefined goals, and delegation patterns for role-based and hierarchical coordination.This framework tests how optimization interacts with structured role assignments.
  • A.1 Frameworks: AutoGen supports iterative message exchange for debate, reflection, collaboration, and tool use in communication-intensive workflows.Its workflows depend heavily on inter-agent interaction.
  • A.1 Frameworks: OpenAI Agents SDK supports delegation, tool invocation, tracing, handoffs, and structured execution in realistic agent pipelines.It combines reasoning, coordination, external tool use, and workflow monitoring.

A.2 Task Datasets

The benchmark covers reasoning, coding, and tool-use regimes using datasets with native metrics tailored to each task’s required behavior.

  • A.2 Task Datasets: The datasets span reasoning, coding, and tool use, testing both explicit artifacts and workflows centered on exchanged rationales and final answers.Metrics are reported as each benchmark’s native accuracy, pass rate, or resolve rate.
  • A.2 Task Datasets: GPQA-Diamond measures expert-level scientific multiple-choice reasoning using exact answer accuracy.Its questions are designed to resist retrieval shortcuts and challenge highly capable language models.
  • A.2 Task Datasets: HotpotQA evaluates multi-hop evidence integration through SQuAD-style exact match after combining information from multiple documents.It targets collaborative multi-step reasoning.
  • A.2 Task Datasets: MATH tests long-chain symbolic reasoning across competition-level mathematics problems using math-equivalence accuracy on extracted final answers.The benchmark spans algebra, geometry, number theory, probability, and calculus.
  • A.2 Task Datasets: LiveCodeBench, APPS, and SWE-bench Verified evaluate executable code generation and software engineering through all-tests-pass accuracy or resolve rate.SWE-bench Verified additionally requires repository understanding, file modification, and an executable patch.
  • A.2 Task Datasets: BFCL, ToolHop, and API-Bank measure structured function calling, sequential multi-tool planning, and interactive API use.Their metrics assess function-call correctness, final-answer accuracy, or API-call accuracy.

A.3 Communication Formats

The communication-format comparison keeps the HotpotQA task and topology fixed while varying how agents encode and transmit information.

  • A.3 Communication Formats: The comparison uses the same HotpotQA multi-hop task and topology while changing only the inter-agent communication format.This isolates communication format as the experimental variation.
  • A.3 Communication Formats: Free-form messages provide question-and-answer context but leave downstream agents to infer which facts matter.The example reports the researcher’s findings and final answer in unconstrained prose.
  • A.3 Communication Formats: Semi-structured messages expose status, summary, evidence, confidence, next step, entities, reasoning hops, and answer candidate through explicit tags.These tags make the intermediate report more explicit without fully adopting a machine-readable object format.
  • A.3 Communication Formats: Structured messages encode the same information in a JSON-style report that is easier to parse and validate automatically.The example includes entities, reasoning hops, evidence, and an answer candidate.

A.4 Prompt Optimizers

The paper adapts GEPA and MIPRO to optimize system prompts in multi-agent LLM systems while preserving the underlying workflows and communication structures. GEPA updates agents sequentially using team-level context, whereas MIPRO searches jointly over prompt configurations across agents.

  • GEPA: GEPA selects candidates from a Pareto frontier, evaluates minibatch rollouts, and uses textual feedback plus execution traces to generate revised prompts.The traces include intermediate reasoning, tool calls, tool outputs, and final answers.
  • GEPA: GEPA maintains per-agent candidate-prompt pools and sequentially updates one agent at a time while holding the other agents’ prompts fixed.Reflection uses the selected agent’s execution trace, surrounding interaction context, final team outcome, and evaluation feedback.
  • Evaluation protocol: Both optimizers use 25-example training and validation splits, while final evaluation excludes all examples used during prompt optimization.The optimized configuration is retained only when it outperforms the original seed on GEPA’s validation split; otherwise, the seed is kept.
  • MIPRO: MIPRO treats each agent as an optimizable module and jointly searches prompt configurations using end-to-end task performance while leaving execution and communication structures unchanged.This directly adapts MIPRO’s single-agent program optimization to multi-agent systems.
  • MIPRO: MIPRO proposes three instruction candidates and three bootstrapped demonstration sets per agent, then searches their combinations across three optimization trials.Demonstrations contain up to four examples and require no manually labeled examples.

A.5 Models

The experiments use separate task and reflection models under a controlled no-thinking evaluation protocol, with role-specific seed prompts generated from each benchmark configuration. The prompt examples preserve the fixed task setup while refining agent responsibilities, tool use, output constraints, and coordination behavior.

  • Models: Qwen/Qwen3.5-9B executes benchmark tasks, while Qwen/Qwen3.5-122B-A10B-FP8 analyzes failures and proposes prompt updates.This separates task execution from reflection during prompt optimization.
  • Models: Disabling thinking mode controls hidden reasoning budgets so comparisons reflect visible agent behavior and coordination rather than variable internal reasoning.Reported scores therefore represent performance under a controlled agentic protocol, not the model’s maximum capability.
  • Seed prompts: Role-specific seed prompts are generated from the benchmark, metric, topology, communication protocol, and each agent’s workflow position.The generation prompt also specifies the agent’s responsibility, local procedure, inter-agent information exchange, and required final-output constraint.
  • Prompt examples: The prompt examples show optimization clarifying task requirements, tool-use procedures, output constraints, and coordination behavior without changing the benchmark, topology, or available tools.The examples include baseline and optimized prompts for solver and manager roles.
  • Prompt examples: Solver prompts require multi-hop Wikipedia search and page retrieval, evidence-based reasoning, entity disambiguation, and normalized final answers suitable for consensus aggregation.The prescribed workflow searches for relevant entities, reads article text, verifies intermediate facts, and formats a short answer.
  • Prompt examples: Manager prompts coordinate a star topology by delegating investigation, editing, and testing tasks to specialist workers, then validating results and assembling the final diff.The manager is instructed to use repository tools and worker-specific delegation tools rather than inventing tools or using external resources.
Loading 2606.23664v1…