MASPO: Solving the Multi-Agent Credit Assignment Problem via Joint Prompt Optimization

TL;DR

MASPO (Multi-Agent System Prompt Optimization) is a breakthrough framework that automatically refines the instructions for every agent in a collaborative system. By focusing on "Lookahead Potential"—how much an agent's output helps the next agent—it eliminates the common pitfall where agents are locally correct but globally useless.

The Problem: The "Silent Failures" of Multi-Agent Systems

In a typical Multi-Agent System (MAS), a Predictor might generate a solution, and a Reflector might critique it. The bottleneck isn't usually the model's raw power, but the prompts that define these roles.

Current optimization methods face two massive hurdles:

1. Local-Global Misalignment: An intermediate agent (e.g., a summarizer) might do a "perfect" job locally, but its output lacks the specific details the next agent needs to solve the final query.
2. Non-Stationarity: In an evolving system, if you improve the "Reflector," the "Predictor" now faces a different environment. Old prompts that worked well before become obsolete, a phenomenon known as covariate shift.

Methodology: The MASPO Trinity

MASPO tackles these issues through a sophisticated loop of trace-guided evolution.

1. Multi-Granularity Joint Evaluation

Instead of just asking "Is this answer right?", MASPO evaluates prompts on three layers:

• Local Validity: Did the agent follow its specific role?
• Lookahead Potential: Did this agent's output make the next agent's job easier?
• Global Alignment: Did this change lead to a correct final system answer?

2. Misalignment-Aware Sampling

The system identifies "Misalignment Cases"—moments where an agent succeeded locally but the system failed globally. These cases are treated as "hard negatives" and fed back into the Optimizer LLM to force it to find prompts that bridge these specific coordination gaps.

3. Evolutionary Beam Search with "Beam Refresh"

To navigate the massive search space, MASPO maintains a "beam" of the best prompt candidates. Crucially, when an upstream agent changes, MASPO performs a Beam Refresh. It re-evaluates all candidates in the beam to ensure their scores reflect the current state of the system, preventing the optimization from chasing "stale" performance peaks.

Experiments & Results: Robust Gains Across the Board

The researchers tested MASPO on 6 benchmarks using Qwen3-8B as the backbone and Gemini-2.5-Pro as the optimizer/evaluator.

• Versatile Performance: MASPO boosted performance across Math (MATH-500), Reasoning (GPQA), and Code (HumanEval-ET).
• Topology Agnostic: Whether the agents were arranged in a simple sequence or a complex hierarchy, MASPO consistently delivered gains (up to +5.06 average accuracy).
• Transferability: Prompts optimized on an 8B model were shown to significantly improve the performance of much larger models like DeepSeek-V3 and Claude-Sonnet-4, suggesting that MASPO learns "generalized interaction logic" rather than just model-specific tricks.

Deep Insight: Why "Lookahead" Matters

A key takeaway from the ablation studies was the sensitivity of the reward weights. The researchers found that "Lookahead Potential" was just as important as "Local Validity." This confirms a long-suspected intuition in MAS design: The quality of an agent's communication is defined by the utility it provides to the receiver.

Conclusion

MASPO moves LLM prompt engineering from a manual "trial and error" process to a rigorous, automated, and system-aware discipline. It proves that the "intelligence" of a multi-agent system lies not just in the individual models, but in the joint optimization of how they talk to one another.

For developers building complex agentic workflows, the message is clear: Stop optimizing agents in silos. Start optimizing the causal chain.