Learning Multi-Agent Orchestration:Higher-Order Interactions in Policy Improvement
Organizations: Department of Computer Science Emory University Atlanta, GA 30322 · John Hopcroft Center for Computer Science Shanghai Jiao Tong University Shanghai, China
Abstract
Learned orchestration has emerged as a promising paradigm for large language model (LLM)-based multi-agent systems, in which a central orchestrator selects agents and controls the information they receive throughout a task. Despite rapid empirical progress, existing methods train the orchestrator by crediting each decision with its own advantage, implicitly assuming that the other decisions in the episode stay fixed. This assumption fails in orchestration, where the contribution of each decision to the final outcome depends on the decisions preceding it, so the gain of a joint update is not the sum of its per-decision effects. To address this challenge, we introduce IAPO, an interaction-aware policy optimization framework that explicitly accounts for interactions among decisions. Specifically, IAPO exactly decomposes the performance difference between two policies into the effects of individual decisions and their interactions, which we prove can account for half of the attainable gain, and then optimizes both from sampled trajectories while certifying that every update is an improvement. On long-input versions of GSM8K, MATH, DROP, MBPP and HumanEval, against fifteen published multi-agent and workflow-search systems on the same 7B executor, IAPO's deployed plans reach the strongest system's accuracy with fewer tokens, and removing the interaction term costs 7 to 17 points of accuracy on code.
Figures & tables
| Method | GSM8K | MATH | DROP | MBPP | HumanEval | Avg. | |||||||||||
| Acc. | Tok. | Acc. | Tok. | Acc. | Tok. | Acc. | Tok. | Acc. | Tok. | Acc. | Tok. | ||||||
| Single-agent | |||||||||||||||||
| Vanilla | 61.9 | 3.8 | 36.7 | 5.5 | 42.6 | 9.1 | 67.5 | 7.7 | 72.9 | 8.8 | 59.8 | 6.5 | |||||
| CoT ( Wei et al., 2022 ) | 67.1 | 5.2 | 4.4 | 16.4 | 20.3 | 6.1 | 64.3 | 21.7 | 9.3 | 67.0 | 0.5 | 8.1 | 71.8 | 1.1 | 9.1 | 55.6 | 6.9 |
| ComplexCoT ( Fu et al., 2023 ) | 45.3 | 16.6 | 6.7 | 34.4 | 2.3 | 12.9 | – | – | 69.2 | 1.7 | 9.5 | 73.1 | 0.2 | 11.9 | 55.5 | 10.2 | |
| SC (CoT 5) ( Wang et al., 2023 ) | 74.2 | 12.3 | 26.9 | 19.8 | 16.9 | 39.3 | 67.4 | 24.8 | 56.5 | 71.8 | 4.3 | 48.5 | 73.3 | 0.4 | 55.2 | 59.8 | 42.5 |
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| GSM8K | MATH | DROP | MBPP | HumanEval | |
| Target unit | statements | statements | passage | specification | specification |
| Distractors | 80 | 90 | 30 | 60 | 60 |
| Units per document | 81 | 91 | 31 | 61 | 61 |
| Retrieved units | 3 | 3 | 2 | 3 | 3 |
| Whole-input prompt tokens | 3.6k | 4.9k | 9.1k | 7.4k | 8.4k |
| IAPO training problems | 2,000 | 1,131 | 1,000 | 447 | 577 |
| role | model calls | reads | produces |
|---|---|---|---|
| Decompose (planner) | 1 | task text only | at most four sub-questions (QA, math) or requirements (code); they only extend the evidence finder’s query |
| Extract (evidence finder) | 0 | task text (and the planner’s lines right after Decompose); BM25 over the document’s units | the top- units as evidence |
| Reason (analyst / programmer) | 1 | task text; the evidence right after Extract; a solution and its review right after Check (QA, math) | a candidate |
| ReasonAlt (generalist) | 1 | the whole document and the task text | a candidate |
| Calculate | 1 | QA, math: as Reason; code: task text only | QA, math: an arithmetic expression evaluated by a tool; code: a function written from its name alone |
| Check (checker / reviewer) | 1 | task text, the evidence if any, the current solution (code: only the candidate’s answer key) | a verdict (supported / unsupported) and review text |
| System | Setting | Budget | Rep. | Disclosed issue |
|---|---|---|---|---|
| Vanilla, CoT | one call with MaAS’s solving prompt for the task type | 131k | 4 | – |
| ComplexCoT | CoT with the 8 most complex training examples | 131k | 4 | not on DROP |
| SC | five CoT calls and MaAS’s ScEnsemble | 131k | 4 | invalid ensemble choices |
| MultiPersona | CoT prefixed by the SPP instruction | 131k | 4 | demonstrations omitted |
| LLM-Debate | 3 agents, 2 rounds, majority vote | 131k | 4 | – |
| LLM-Blender | 5 CoT candidates, PairRM ranking, fusion of the top 3 | 131k | 4 | executor fuses; PairRM unmetered |
| Setting | QA / math (GSM8K, MATH, DROP) | Code (MBPP, HumanEval) |
|---|---|---|
| Orchestrator decisions | 5 | 4 |
| Rounds | 1, from the uniform reference | 1 |
| Proposal sample | 200 problems 32 repeats | same |
| Validation sample | 8,000 i.i.d. draws from the validation pool | same |
| Score model | MLP on the whole observation: Linear( ), tanh, Linear( ), tanh | MLP on the last 24 (process) features: Linear( ), tanh, Linear( ), tanh |
| Score range | , one output per action, shared across decisions | same |
| config A ( ) | CW1 ( ) | ||||||
|---|---|---|---|---|---|---|---|
| Family | |||||||
| QA / math ( ) | 0.25 | 4.04 | 4.42 | 0.0208 | 7.50 | 8.21 | 0.0208 |
| 0.5 | 10.76 | 14.19 | 0.1768 | 20.00 | 26.38 | 0.1768 | |
| 1 | 32.28 | 66.71 | 1.5938 | 60.00 | 124.00 | 1.5938 | |
| Code ( ) | 0.25 | 2.96 | 3.10 | 0.0081 | 5.50 | 5.77 | 0.0081 |
| 0.5 | 7.53 | 8.74 | 0.0664 | 14.00 | 16.25 | 0.0664 | |
| config A | CW1 | |||||||
|---|---|---|---|---|---|---|---|---|
| IAPO acc. | tokens | FO acc. | tokens | IAPO acc. | tokens | FO acc. | tokens | |
| GSM8K | 78.1 | 5.6 | 77.4 | 9.7 | 79.3 | 4.0 | 66.4 | 4.3 |
| MATH | 37.7 | 5.6 | 37.6 | 15.2 | 39.0 | 1.0 | 36.4 | 1.2 |
| DROP | 69.2 | 11.5 | 67.9 | 20.1 | 59.8 | 1.0 | 60.3 | 0.8 |
| MBPP | 81.1 | 5.1 | 63.8 | 15.7 | 78.2 | 1.1 | 75.3 | 1.6 |
| HumanEval | 83.7 | 9.9 | 76.5 | 18.1 | 77.0 | 5.6 | 64.1 | 7.3 |
| (a) Matched budget | |||||
| Strongest baseline | IAPO | IAPO-Lite | |||
| acc. (tokens) | acc. (tokens) | diff. | acc. (tokens) | diff. | |
| GSM8K | Debate 79.5 (28.6k) | 81.8 (25.1k) | (2.2) | 85.1 (25.8k) | (5.5) |
| MATH | DyLAN 48.3 (54.3k) | 48.6 (50.8k) | (0.2) | 54.3 (51.1k) | (2.6) |
| DROP | Debate 70.6 (57.1k) | 74.2 (46.0k) | (3.3) | 66.1 (51.7k) | ( ) |
| MBPP ‡ | DyLAN 71.2 (121.9k) | 80.9 (33.1k) | (6.3) | 78.3 (29.0k) | (4.6) |
Multi-Agent Orchestration
Multi-agent orchestration coordinates specialized AI agents, tools, and workflows to solve complex tasks efficiently and reliably.
See all 214 papers