MAPRO: Recasting Multi-Agent Prompt Optimization as Maximum a Posteriori Inference
This addresses the problem of prompt sensitivity and instability in multi-agent systems for AI researchers and practitioners, offering a principled method to automate prompt design, though it is incremental as it builds on existing automated prompt optimization efforts.
The paper tackles the challenge of designing effective multi-agent systems (MAS) by introducing MAPRO, a framework that formulates multi-agent prompt optimization as a Maximum a Posteriori inference problem and uses a language-guided max-product belief propagation algorithm, achieving state-of-the-art performance across various benchmarks and surpassing manual and automated baselines.
Large language models (LLMs) have demonstrated remarkable capabilities across diverse tasks, and LLM-based agents further extend these abilities to various practical workflows. While recent progress shows that multi-agent systems (MAS) can outperform single agents by coordinating specialized roles, designing effective MAS remains difficult due to prompt sensitivity and the compounded instability MAS creates. To cope with the challenge, recent efforts in automated prompt design have reduced manual effort. However, multi-agent prompt optimization remains largely unexplored. Challenges like exponentially expanding search space and ambiguous credit assignment together make systematic design intractable without principled methods. Therefore, we introduce M}ulti-Agent PRompt Optimization (MAPRO), a four-stage framework that first formulates MAS prompt optimization as a Maximum a Posteriori (MAP) inference problem and solves it using a language-guided variant of max-product belief propagation algorithm. To address credit assignment and updates the system iteratively, MAPRO employs a topology-aware refinement mechanism that integrates execution feedback and downstream blames to selectively update agent prompts. Through this process, MAPRO progressively converges to a coordinated set of agent-specific prompt policies. Across benchmarks in various tasks, MAPRO achieves state-of-the-art performance, consistently surpassing manually engineered baselines and recent automated alternatives. Beyond performance, our MAP-based formulation also delivers general guidelines for building more reliable and principled multi-agent systems in the future