Technical Summary: MANGO (Multi-Agent Network Gradient Optimization)

Problem Statement

Multi-agent systems offer a promising paradigm for extending Large Language Models (LLMs) by decomposing complex tasks into specialized subtasks. However, these systems are intrinsically prone to error propagation, where inaccuracies in workflow design or agent execution degrade final results. The paper identifies two primary challenges:

1. Workflow Generation Error (C1): Incorrect planning of the task sequence (e.g., choosing a web search instead of video analysis) leads to cascading failures. Existing methods often rely on manual heuristics or rule-based designs that struggle to adapt to diverse domains.
2. Single-Agent Execution Error (C2): Even with a correct workflow, individual agents may produce hallucinated or inaccurate outputs (e.g., retrieving a wrong date). Current textual gradient methods for mitigating these errors face limitations: they often provide weak supervision signals for intermediate steps in long chains (analogous to gradient vanishing) and incur high latency by backpropagating gradients through all agents, including those already well-optimized.

Methodology: MANGO Framework

The authors propose MANGO (Multi-Agent Network Gradient Optimization), a data-driven framework that organizes agent collaboration via a flow network constructed from past successful workflows. The framework jointly optimizes workflow paths (edges) and agent behaviors (nodes) using Reinforcement Learning (RL) and Textual Gradients (TG).

1. Flow Network Construction

The system constructs a directed graph $G = (V, E, s, t)$ where:

• Nodes ($V$): Each node represents an agent (an LLM with a specific system prompt and role description). Nodes are formed by clustering similar operations from historical successful workflows.
• Edges ($E$): Directed edges represent valid transitions between operations.
• Source ($s$) and Sink ($t$): The network has a source node receiving the input task and a sink node where final performance is evaluated.

2. Joint Optimization Strategy

MANGO addresses the joint optimization of the path $P$ and node parameters $\Theta_P$ through a complementary update strategy:

• Edge Optimization (Reinforcement Learning):

  • Workflow generation is formulated as finding a path from $s$ to $t$.
  • A planner agent generates a high-level plan, and a policy network ($\pi_\phi$) selects the next executor node based on the current state (similarity between the plan step and node role/experience).
  • The policy is optimized via REINFORCE, maximizing a reward that combines process-oriented correctness (matching ground-truth workflow structures) and result-oriented performance (final task accuracy).

• Node Optimization (Textual Gradients):

  • Once a path is sampled, the system prompts ($P_i$) and role descriptions ($r^*_i$) of the nodes along the path are optimized.
  • MANGO introduces local gradient signals alongside global signals. The loss function combines the final task loss with intermediate feedback to prevent gradient vanishing in long chains.
  • Parameters are updated using textual gradient descent, refining prompts without changing model weights.

• Skipping Mechanism for Efficiency:

  • To reduce computational costs, MANGO employs a skipping strategy. If a node is already well-optimized, the agent can skip it during the optimization process.
  • The agent can select from up to $K$-adjacent nodes in the network. Skipped nodes reuse ground-truth intermediate steps from training workflows, avoiding redundant on-the-fly generation and prompt updates.

Key Contributions

1. Novel Flow Network Model: The paper introduces a data-driven flow network model that formulates multi-agent collaboration as a joint optimization of edges (workflow paths) and nodes (agent outputs), explicitly addressing error propagation.
2. MANGO Framework: A unified system integrating Reinforcement Learning for path selection and Textual Gradients for prompt optimization. It uniquely incorporates local gradient signals and a skipping mechanism to improve efficiency.
3. Empirical Validation: Extensive experiments demonstrate that MANGO outperforms state-of-the-art baselines while significantly reducing computational costs.

Experimental Results

Experiments were conducted on seven benchmarks: HumanEval, MBPP, MATH, GSM8K, DROP, MMLU, and GPQA.

• Performance: MANGO achieves up to 12.8% improvement over the best state-of-the-art baselines (e.g., MaAS) on the MATH dataset. It consistently outperforms single-agent and multi-agent baselines across all domains.
• Efficiency: The framework reduces training time by 41.5% and inference time by 47.4% compared to MaAS, primarily due to the skipping mechanism. It also achieves lower API costs and token usage.
• Generalization:
  • Cross-Model: MANGO trained on GPT-4o-mini generalizes effectively to unseen backbone LLMs (Qwen-2.5-72B, Llama-3.1-70B), outperforming baselines in both zero-shot and few-shot settings.
  • Cross-Domain: The model demonstrates strong transferability, performing well when trained on one domain (e.g., MATH) and tested on another (e.g., GSM8K or HumanEval).
• Ablation Studies: Removing Reinforcement Learning or Textual Gradients significantly degrades performance, confirming the necessity of joint optimization. Local signals contribute a 6.8% accuracy gain, highlighting their role in mitigating error propagation.

Significance and Claims

The paper claims that MANGO represents a shift from heuristic-driven or rule-based multi-agent design to a data-driven paradigm that learns collaboration patterns from historical successes. By jointly optimizing the workflow structure and agent prompts, MANGO effectively mitigates the dual challenges of workflow generation errors and execution errors. The introduction of the skipping mechanism addresses the critical issue of computational redundancy in multi-agent systems, offering a scalable solution for efficient agent collaboration. The authors note that while the framework relies on the quality of initial successful workflows, it exhibits strong self-bootstrapping capabilities, progressively improving even when starting with lower-quality initial data.