# MAPRO: Recasting Multi-Agent Prompt Optimization as Maximum a Posteriori Inference

arXiv: https://arxiv.org/abs/2510.07475 · HTML: https://mlsanity.com/paper/2510.07475/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 35 of its 56 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 35)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [ChatEval: Towards Better LLM-based Evaluators through Multi-Agent Debate](https://mlsanity.com/paper/2308.07201/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [Mixture-of-Agents Enhances Large Language Model Capabilities](https://mlsanity.com/paper/2406.04692/) (2024)
- [NewsQA: A Machine Comprehension Dataset](https://mlsanity.com/paper/1611.09830/) (2016)
- [Maximum a Posteriori Policy Optimisation](https://mlsanity.com/paper/1806.06920/) (2018)
- [Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs](https://mlsanity.com/paper/2406.11695/) (2024)
- [Agentic Retrieval-Augmented Generation: A Survey on Agentic RAG](https://mlsanity.com/paper/2501.09136/) (2025)
- [Scaling Large Language Model-based Multi-Agent Collaboration](https://mlsanity.com/paper/2406.07155/) (2024)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers](https://mlsanity.com/paper/2309.08532/) (2023)
- [Debug like a Human: A Large Language Model Debugger via Verifying Runtime Execution Step-by-step](https://mlsanity.com/paper/2402.16906/) (2024)
- [Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies](https://mlsanity.com/paper/2502.02533/) (2025)
- [Batch Calibration: Rethinking Calibration for In-Context Learning and Prompt Engineering](https://mlsanity.com/paper/2309.17249/) (2023)
- [RepoGraph: Enhancing AI Software Engineering with Repository-level Code Graph](https://mlsanity.com/paper/2410.14684/) (2024)
- [CodeScore: Evaluating Code Generation by Learning Code Execution](https://mlsanity.com/paper/2301.09043/) (2023)
- [CodexGraph: Bridging Large Language Models and Code Repositories via Code Graph Databases](https://mlsanity.com/paper/2408.03910/) (2024)
- [Mora: Enabling Generalist Video Generation via A Multi-Agent Framework](https://mlsanity.com/paper/2403.13248/) (2024)
- [Test-Time Preference Optimization: On-the-Fly Alignment via Iterative Textual Feedback](https://mlsanity.com/paper/2501.12895/) (2025)
- [Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars](https://mlsanity.com/paper/2405.16122/) (2024)
- [PRompt Optimization in Multi-Step Tasks (PROMST): Integrating Human Feedback and Heuristic-based Sampling](https://mlsanity.com/paper/2402.08702/) (2024)

## Built on by (most cited first, 17 of 17)

- [EvolveRouter: Co-Evolving Routing and Prompt for Multi-Agent Question Answering](https://mlsanity.com/paper/2604.05149/) (2026)
- [NG-Router: Graph-Supervised Multi-Agent Collaboration for Nutrition Question Answering](https://mlsanity.com/paper/2510.09854/) (2025)
- [Drift-Bench: Diagnosing Cooperative Breakdowns in LLM Agents under Input Faults via Multi-Turn Interaction](https://mlsanity.com/paper/2602.02455/) (2026)
- [MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks](https://mlsanity.com/paper/2603.02630/) (2026)
- [Why Semantic Entropy Fails: Geometry-Aware and Calibrated Uncertainty for Policy Optimization](https://mlsanity.com/paper/2605.21801/) (2026)
- [MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems?](https://mlsanity.com/paper/2606.23664/) (2026)
- [Optimizing What Policies Learn From: Recoverability-aware Rollout Intervention Learning](https://mlsanity.com/paper/2608.05080/) (2026)
- [Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization](https://mlsanity.com/paper/2605.30227/) (2026)
- [SAGE: Answer-Conditioned Uncertainty Targets for Verbal Uncertainty Alignment](https://mlsanity.com/paper/2606.11512/) (2026)
- [Multi-Agent Coordination Adaptation via Structure-Guided Orchestration](https://mlsanity.com/paper/2605.25746/) (2026)
- [CANTANTE: Optimizing Agentic Systems via Contrastive Credit Attribution](https://mlsanity.com/paper/2605.13295/) (2026)
- [Confidence Laundering in Agent Systems: Why Uncertainty Needs a Latent Carrier](https://mlsanity.com/paper/2606.20662/) (2026)
- [Communication Policy Evolution for Proactive LLM Agents](https://mlsanity.com/paper/2606.14314/) (2026)
- [HoosierHelp: Benchmarking LLM Agents for Social Service Navigation](https://mlsanity.com/paper/2608.09946/) (2026)
- [One Prompt Does Not Fit All: Self-Meta-Evolve for Personalized Information Extraction](https://mlsanity.com/paper/2609.21626/) (2026)
- [Can Language Models Learn to Reject Their Own Bad Reasoning Steps?](https://mlsanity.com/paper/2610.05976/) (2026)
- [From Agents to Edges: Paired Optimization for Multi-Agent Collaboration](https://mlsanity.com/paper/2610.18069/) (2026)

## Abstract (arXiv)

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