💬 NLP

MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems

MASPO is a novel framework that automatically optimizes prompts for LLM-based multi-agent systems by employing a joint evaluation mechanism and evolutionary beam search to align local agent objectives with global system goals, thereby outperforming existing methods across diverse collaborative tasks.

Original authors: Zhexuan Wang, Xuebo Liu, Li Wang, Zifei Shan, Yutong Wang, Zhenxi Song, Min Zhang

Published 2026-05-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhexuan Wang, Xuebo Liu, Li Wang, Zifei Shan, Yutong Wang, Zhenxi Song, Min Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a team of expert robots working together to solve a very difficult puzzle. Each robot has a specific job: one reads the clues, another does the math, a third checks for errors, and a fourth writes the final answer.

In the past, if the team failed, it was hard to know who to blame. Was the math robot bad at math? Or did the reading robot give it the wrong clues? This is the problem the paper MASPO solves.

Here is how MASPO works, explained through simple analogies:

1. The Problem: The "Blame Game" in a Team

Usually, when we train these robot teams, we only look at the final answer. If the answer is wrong, we don't know which robot messed up.

The Analogy: Imagine a relay race. If the team loses, you can't just yell at the last runner. Maybe the first runner dropped the baton, or the second runner ran the wrong path. If you only train the last runner to run faster, the team will still lose because the baton hand-off is broken.
The Paper's Insight: The authors realized that in a multi-agent system, a robot can do its own job perfectly (local success) but still give the next robot information that leads to a total failure (global failure). This is called "Local-Global Misalignment."

2. The Solution: MASPO (The Team Coach)

MASPO is a new framework that acts like a smart coach who doesn't just watch the finish line, but watches every single hand-off in the relay race. It automatically rewrites the "instruction manuals" (prompts) for every robot to make the whole team work better together.

It does this using three main tricks:

A. The "Future-Proof" Scorecard (Joint Evaluation)

Instead of just asking, "Did this robot do its job?" MASPO asks, "Did this robot's work help the next robot succeed?"

The Analogy: Imagine a chef preparing a meal. A standard judge might just taste the soup and say, "It's salty." But MASPO is like a judge who also asks, "Is this soup salty enough to go well with the bread the next chef is baking?"
How it works: MASPO gives every robot a score based on three things:
1. Did they follow their own rules? (Local Validity)
2. Did their output make the next robot's job easier? (Lookahead Potential)
3. Did it help the team win the final game? (Global Alignment)

B. Learning from "Almost" Disasters (Misalignment Mining)

Most systems only learn from mistakes where the final answer was wrong. MASPO looks for a specific, sneaky type of mistake: when a robot did its job perfectly, but the team still failed.

The Analogy: Imagine a driver who follows every traffic law perfectly (local success) but accidentally drives into a dead-end street because the map was confusing (global failure). A normal coach would say, "Good job, driver!" MASPO says, "Wait, you followed the rules, but we still got lost. Let's fix your instructions so you don't drive into dead ends next time."
How it works: The system saves these "Local Success, Global Failure" cases and forces the robots to study them, ensuring they don't repeat the same coordination errors.

C. The "Re-Alignment" Drill (Beam Refresh)

As the robots learn and change their behavior, the instructions for the next robot might suddenly become outdated.

The Analogy: Imagine a dance team. If the first dancer speeds up, the second dancer's timing is now wrong. If you keep practicing the old routine, they will keep stepping on each other's toes.
How it works: MASPO constantly checks the team. If the first robot has changed its style, MASPO immediately updates the "score" for the second robot's instructions so they are practicing against the current reality, not an old version of the team.

3. The Results: A Better Team

The authors tested this on 6 different types of hard tasks, including complex math, logic puzzles, and writing computer code.

The Outcome: The MASPO-trained teams consistently outperformed other methods. They improved their accuracy by an average of 2.9% compared to the best existing methods.
Why it matters: This proves that by teaching robots to care about how their work affects their teammates (not just their own task), the whole system becomes much smarter.

Summary

Think of MASPO as a team coach that rewrites the playbook in real-time. Instead of just telling the players to "do their best," it analyzes how Player A's pass affects Player B's catch, and it rewrites the instructions for both of them to ensure the whole team wins, not just the individual players. It solves the problem of "I did my job, but we still lost" by making sure everyone's job is designed to help the team win.

Technical Summary: MASPO – Joint Prompt Optimization for LLM-based Multi-Agent Systems

Problem Statement

Large Language Model (LLM)-based Multi-Agent Systems (MAS) have demonstrated significant potential in solving complex collaborative tasks by orchestrating heterogeneous agents via role-specific prompts. However, the joint optimization of these prompts remains a critical bottleneck. Unlike single-agent scenarios, MAS optimization involves a combinatorial search space where the optimality of one agent's prompt is intrinsically dependent on the behaviors of others.

Existing prompt optimization methods face two primary challenges in the MAS context:

Local-Global Misalignment (Credit Assignment): In collaborative settings, intermediate agents often perform tasks like reasoning or summarization rather than generating the final output. Standard evaluation methods relying on ground-truth labels fail to assign credit effectively to these intermediate steps. An agent may satisfy its local instructions perfectly (Local Validity) yet generate outputs that mislead downstream peers, causing system-wide failure.
Non-Stationarity and Search Complexity: The functional coupling between agents creates a non-stationary optimization landscape. Modifying an upstream agent's prompt alters the input context for downstream agents, inducing covariate shifts that render historical performance scores unreliable. Furthermore, existing methods like Tree-structured Parzen Estimators (TPE) are often restricted to selecting from fixed, discrete candidate pools, limiting open-ended, fine-grained optimization.

Methodology: The MASPO Framework

To address these challenges, the authors propose MASPO, a framework designed to automatically and iteratively refine prompts across the entire multi-agent system. The framework operates through a systematic loop involving topological scheduling, trace-guided generation, joint evaluation, and adaptive beam search.

1. Topological Context and Trace-Guided Proposal

MASPO adopts a coordinate ascent-style strategy that respects the causal dependencies of the agent communication graph. Instead of fully converging one agent before moving to the next, it employs an interleaved evolution protocol. Agents are optimized in topological order for a limited number of generations ( $T$ ) before being frozen, allowing the system to stabilize co-adaptation and prevent upstream overfitting to suboptimal downstream behaviors.

For prompt generation, MASPO utilizes a data-driven approach grounded in actual execution traces rather than blind mutation. An Optimizer Model ( $M_{opt}$ ) analyzes the mapping from input context to output to propose variations. Crucially, the framework employs Misalignment Sampling, injecting "hard negative" traces into the generation process. These are historical cases where an agent satisfied local objectives but failed to support the global system, explicitly guiding the optimizer to bridge the gap between local instructions and global goals.

2. Multi-Granularity Joint Evaluation

To resolve the credit assignment dilemma, MASPO introduces a composite scoring function ( $R$ ) that evaluates candidate prompts across three dimensions:

Local Validity: Measures if the agent's output satisfies role-specific constraints better than the baseline.
Lookahead Potential: A topology-aware metric quantifying the "ripple effect." It evaluates whether downstream agents produce better outputs when fed the new context generated by the current agent.
Global Alignment: Measures the impact on the final system response, capturing long-range dependencies.

This joint reward model ( $R = \alpha \cdot \text{Local} + \beta \cdot \text{Lookahead} + \theta \cdot \text{Global}$ ) allows the system to assess an agent's utility through its contribution to the entire causal chain rather than isolated outputs.

3. Evolutionary Beam Search with Adaptive Dynamics

To navigate the high-dimensional prompt space, MASPO employs a Trace-Guided Beam Search. It maintains a beam of top- $K$ candidates, accumulating joint reward scores along the path to select the most robust prompts.

A key innovation is the Beam Refresh Mechanism. As peer agents evolve during topological traversal, the input distribution for a specific agent shifts, rendering historical scores stale. When an agent is revisited in a new epoch, MASPO discards stale cumulative scores and re-anchors the beam by evaluating candidates against the current global best prompt. This ensures the search resumes from a valid, up-to-date performance manifold, effectively mitigating non-stationarity.

Key Contributions

The paper outlines three primary contributions:

Multi-Granularity Joint Evaluation: A composite metric that resolves the credit assignment dilemma by synergizing Local Validity, Lookahead Potential, and Global Alignment, capturing the full causal impact of an agent within the collaborative chain.
Misalignment-Driven Generative Search: A beam search strategy explicitly guided by "Misalignment Cases"—scenarios where agents fulfill local roles but induce system-wide failure. This allows the optimizer to diagnose and rectify specific interaction breakdowns.
Adaptive Optimization Dynamics: A coordinate ascent-based scheduling protocol augmented with a Beam Refresh mechanism. These techniques mitigate the non-stationarity inherent in multi-agent interactions, ensuring agents adapt to the evolving behaviors of their peers.

Experimental Results

The authors evaluated MASPO across six diverse tasks spanning mathematical proficiency (MATH-500, AGIEval-MATH, AQuA), complex reasoning (GPQA), and code generation (MBPP, HumanEval-ET). The framework was tested on both Sequential and Hierarchical MAS architectures using Qwen3-8B as the backbone, with Gemini-2.5-pro serving as the optimizer and evaluator.

Performance Gains: MASPO consistently outperformed state-of-the-art baselines, including single-agent strategies (Vanilla, CoT, Self-Refine) and existing multi-agent optimization methods (TPE, SPO). It achieved an average accuracy improvement of 2.9% over the best-performing optimization baselines.
Robustness: The framework demonstrated topology-agnostic performance, improving Sequential MAS by 5.06% and Hierarchical MAS by 2.73% over their respective baselines.
Ablation Studies: Experiments confirmed the necessity of all core components. Removing the Beam Refresh mechanism or Joint Evaluation led to significant performance drops. Sensitivity analysis revealed that balancing Local Validity and Lookahead Potential (weights 0.4/0.4) yielded superior adaptability compared to heavy reliance on Global Alignment.
Transferability: Prompts optimized on Qwen3-8B successfully transferred to unseen architectures (DeepSeek-V3, GLM-4.6, Claude-Sonnet-4, Gemini-2.5-Pro), indicating that MASPO captures generalized interaction logic rather than overfitting to specific model idiosyncrasies.

Significance and Claims

The paper claims that MASPO offers a robust solution to the underexplored challenge of joint prompt optimization in dynamic multi-agent environments. By moving beyond isolated agent tuning, MASPO effectively bridges the gap between local interactions and global outcomes without relying on ground-truth labels for intermediate steps.

The authors emphasize that their approach is particularly significant for:

Solving the Credit Assignment Problem: Providing a mechanism to evaluate intermediate agents based on their downstream utility rather than just final correctness.
Handling Non-Stationarity: Introducing a dynamic refresh mechanism that keeps the optimization process stable despite the shifting input distributions caused by peer agents.
Practical Applicability: Demonstrating that high performance can be achieved with a small, unlabeled sample pool (50 instances), making the framework computationally efficient and suitable for resource-constrained or privacy-sensitive deployments.

The work suggests that future research in collaborative AI systems should focus on dynamic role specialization and architectural optimization, with MASPO serving as a foundational step toward automated, self-improving multi-agent systems.