MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems
Zhexuan Wang, Xuebo Liu, Li Wang, Zifei Shan, Yutong Wang, Zhenxi Song, Min Zhang · 2026
Read MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems by Zhexuan Wang, Xuebo Liu, Li Wang, Zifei Shan, Yutong Wang, Zhenxi Song, Min Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06623.txt.
Introduction
Zhexuan Wang and six co-authors introduce MASPO, a framework that optimizes the prompts of all agents in a multi-agent language model system together. Each agent's role prompt matters, but tuning prompts one by one misaligns local goals with whole-system success. Joint optimization across interacting agents is the hard, mostly unsolved problem they target.
MASPO judges each prompt by how much it helps successor agents succeed downstream, bridging local edits and global outcomes without ground-truth labels. An evolutionary beam search, guided by data, navigates the huge prompt space. Across six varied tasks MASPO consistently beats leading prompt optimization methods, with an average accuracy gain just under three points.
Catalog record
| CREATOR | Zhexuan Wang, Xuebo Liu, Li Wang, Zifei Shan, Yutong Wang, Zhenxi Song, Min Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06623
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems Zhexuan Wang, Xuebo Liu, Li Wang, Zifei Shan, Yutong Wang, Zhenxi Song, Min Zhang Abstract Large language model (LLM)-based Multi-agent systems (MAS) have shown promise in tackling complex collaborative tasks, where agents are typically orchestrated via role-specific prompts. While the quality of these prompts is pivotal, jointly optimizing them across interacting agents remains a non-trivial challenge, primarily due to the misalignment between local agent objectives and holistic system goals. To address this, we introduce MASPO, a novel framework designed to automatically and iteratively refine prompts across the entire system. A core innovation of MASPO is its joint evaluation mechanism, which assesses prompts not merely by their local validity, but by their capacity to facilitate downstream success for successor agents. This effectively bridges the gap between local interactions and global outcomes without relying on ground-truth labels. Furthermore, MASPO employs a data-driven evolutionary beam search to efficiently navigate the high-dimensional prompt space. Extensive empirical evaluations across 6 diverse tasks demonstrate that MASPO consistently outperforms state-of-the-art prompt optimization methods, achieving an average accuracy improvement of 2.9. We release our code at https://github.com/wangzx1219/MASPO . 1 Introduction Recent advancements in LLMs ( 1 ; 38 ) have exhibited exceptional capabilities in context understanding, instruction following, and complex reasoning, demonstrating strong performance across various tasks and scenarios. Building upon these foundations, Multi-Agent Systems (MAS) have emerged as a powerful paradigm for solving multi-stage problems. By orchestrating heterogeneous agents ( 25 ; 40 ; 13 ; 70 ) to communicate and collaborate, MAS often surpass the capabilities of single-agent counterparts. Within such systems, the design of agent-specific prompts is critical, as they not only define the distinct roles of each agent but also govern their interaction dynamics and reasoning trajectories. However, despite their critical importance, the joint optimization of these prompts remains a non-trivial challenge. Unlike single-agent scenarios, MAS optimization involves a combinatorial search space where the optimality of one agent’s prompt depends intrinsically on the behaviors of others. Typically, MAS operate through the collaboration of specialized agents. While existing prompt optimization methods typically rely on labeled data to evaluate prompt quality, this paradigm is ill-suited for MAS ( 14 ; 60 ) . In collaborative settings, specific agents may be tasked with intermediate steps, such as reasoning, reflection, or summarization rather than generating the final output. This leads to a severe credit assignment problem. A critical failure mode in MAS is Local-Global Misalignment, where an intermediate agent satisfies its local instructions perfectly but generates outputs that mislead downstream peers, causing system-wide failure. Although recent self-supervised strategies ( 51 ) leverage comparative feedback to assess reasoning quality, they remain confined to an isolated scope, failing to capture how local variations propagate to influence global system outcomes. In the context of MAS, recent works ( 30 ; 68 ) have introduced Bayesian search strategies utilizing Tree-structured Parzen Estimators (TPE). However, these methods are restricted to selecting prompts from a fixed, discrete candidate pool, thereby limiting their capacity for open-ended optimization and fine-grained adjustment. Consequently, there is an urgent need for a robust framework capable of automating prompt generation in dynamic multi-agent environments. To address these challenges, we propose MASPO, a joint prompt optimization framework tailored for multi-agent environments. MASPO introduces three key innovations. First, to resolve the credit assignment dilemma, we design a multi-granularity joint evaluation mechanism that integrates Local Validity, Lookahead Potential, and Global Alignment, assessing an agent’s utility through its contribution to the entire causal chain rather than isolated outputs. Second, we introduce Misalignment-Aware Sampling, a targeted technique that explicitly mines and injects historical traces where coordination failed despite local success, guiding the optimizer to diagnose and rectify specific interaction breakdowns. Third, regarding the co-adaptation protocol, we implement a coordinate ascent-style strategy augmented with a Beam Refresh mechanism, which ensures stability by realigning the search tree of each agent in real-time to mitigate the non-stationarity caused by peer agents. Extensive experiments conducted across diverse domains demonstrate that MASPO consistently delivers significant performance gains over existing baselines. Our primary contributions are summarized as follows: • Multi-Granularity Joint Evaluation : We introduce a composite evaluation metric that resolves the credit assignment dilemma in MAS. By synergizing Local Validity, Lookahead Potential, and Global Alignment, our approach captures the full causal impact of an agent within the collaborative chain. • Misalignment-Driven Generative Search : We design a beam search strategy explicitly guided by Misalignment Cases—scenarios where agents fulfill local roles but induce system-wide failure. • Adaptive Optimization Dynamics : We propose a coordinate ascent-based scheduling protocol augmented with a Beam Refresh mechanism. These techniques effectively mitigate the non-stationarity inherent in multi-agent interactions, ensuring that each agent adapts to the evolving behaviors of its peers. 2 Preliminary 2.1 LLM-Based Multi-Agent Systems Adopting the graph-theoretic perspective from the recent literature ( 3 ; 20 ; 50 ) , we formalize the MAS as a directed communication graph \mathcal{G}=(\mathcal{V},\mathcal{E}) . Here, \mathcal{V}=\{v_{i}\}_{i=1}^{N} represents the set of N agents, and the edge set \mathcal{E}\subseteq\mathcal{V}\times\mathcal{V} defines the communication topology. A directed edge (v_{j},v_{i})\in\mathcal{E} signifies that the output of agent v_{j} serves as input context for agent v_{i} . We equip each agent v_{i} with an LLM-based inference function f_{i}\in\mathcal{F} and, crucially, a specific system prompt p_{i} . We denote the set of all prompts as \mathcal{P}=\{p_{i}\}_{i=1}^{N} , which constitutes the primary learnable parameters in our optimization framework. Given a global task query q , the generation process for a specific agent v_{i} is formulated as: o_{i}=f_{i}\left(p_{i},q,\mathcal{C}_{i}\right),\quad\text{with}\quad\mathcal{C}_{i}=\bigoplus_{v_{j}\in\mathcal{N}_{in}(v_{i})}o_{j}, (1) where \mathcal{N}_{in}(v_{i}) denotes the set of predecessors of v_{i} . Here, \oplus denotes the concatenation operation applied in a fixed topological order, and \mathcal{C}_{i} represents the aggregated context. o_{i} is the resulting output conditioned on the role-specific agent’s prompt p_{i} . 2.2 Prompt Optimization Prompt optimization aims to automate the discovery of optimal instructions that maximize the performance of LLMs on downstream tasks. In the context of our defined MAS, this objective extends from optimizing a single string to jointly optimizing the set of role-specific prompts \mathcal{P} . Let \mathcal{D}=\{(q_{k},y_{k}^{*})\}_{k=1}^{|\mathcal{D}|} be a dataset consisting of input queries and their corresponding ground-truth labels (or reference answers). The execution of the multi-agent system \mathcal{G} on a query q , governed by the prompt configuration \mathcal{P} , produces a final system response o_{glob} . We abstract this complex interaction process as a composite function \Phi : o_{glob}=\Phi(\mathcal{G},\mathcal{P},q). (2) Here, o_{glob} represents the final output from multiple agents, derived through the topological propagation defined in Eq. (1). The goal of MAS prompt optimization is to identify the optimal configuration \mathcal{P}^{*} that maximizes the expected performance over the data distribution: \mathcal{P}^{*}=\operatorname*{argmax}_{\mathcal{P}\in\mathcal{S}^{N}}\mathbb{E}_{(q,o_{glob}^{*})\sim\mathcal{D}}\left[R\left(\Phi(\mathcal{G},\mathcal{P},q),o_{glob}^{*}\right)\right], (3) where \mathcal{S} denotes the discrete space of natural language strings (prompts), N is the number of agents, and R(\cdot,\cdot) is a scalar scoring function measuring the alignment between the prediction of the system and the ground truth. However, directly optimizing this objective is non-trivial. Since agents fulfill different intermediate roles, the final ground truth o_{glob}^{*} provides only sparse supervision and does not effectively assign credit to individual steps. To address this, we employ a self-supervised evaluation mechanism as a proxy, which is detailed in Section 3 . Figure 1 : Overview of the MASPO Framework. The optimization proceeds sequentially following the topological order