Learning Multi-Agent Orchestration:Higher-Order Interactions in Policy Improvement
Authors: Kaixuan Liu, Guojun Xiong
Organizations: Department of Computer Science Emory University Atlanta, GA 30322 · John Hopcroft Center for Computer Science Shanghai Jiao Tong University Shanghai, China
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
Figure 1: Overview of IAPO. (a) Orchestration decisions depend on one another: a new earlier worker helps only if a later call may read its output, so neither change helps alone. (b) IAPO credits each orchestrator step and every pair of steps in one pass over each training trajectory, and fits one bounded update per step size. (c) With the candidates fixed, IAPO computes two lower bounds on the gain from fresh trajectories, keeps the larger one, and updates the policy only if it is positive.
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
Table 1: Accuracy (%) with its change from Vanilla, and cost (grey, thousand tokens per problem; one episode for baselines, all voted episodes for IAPO) with Qwen2.5-7B-Instruct on long-input versions of five benchmarks. Bold : best; underline : runner-up. IAPO and IAPO-Lite (trained with λ=1 ) vote (on code, select programs) within the best baseline’s tokens per column. Avg. covers GSM8K, MATH, MBPP and HumanEval. Two-seed baselines are averaged; “–”: not run; † better accuracy of the upstream and diagnostic arms.
Figure 2: Accuracy (left) and tokens per episode (right, log scale) of IAPO, IAPO-Lite, the strongest baseline of each benchmark and the other baselines. Accuracy is that of the voted plan within the strongest baseline’s budget; tokens are those of a single episode.
Figure 3: With the interaction term ( Z2 ) and with first order only ( J1 ), for IAPO (left) and IAPO-Lite (right): accuracy with its gain in points (bold: z>2 ), and tokens per episode with IAPO’s tokens as a share of the first-order variant’s.
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 D
80
90
30
60
60
Units per document
81
91
31
61
61
Retrieved units k
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
Appendix
Table 2: The five environments. Prompt tokens are the mean over test of a single call that reads the whole input.
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- k 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
Appendix
Table 3: The roles. “Right after X ” means at the decision immediately following role X .
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
Appendix
Table 4: How each baseline was run. Budget is the trajectory cap in tokens; “Rep.” is attempts per test problem.
Setting
QA / math (GSM8K, MATH, DROP)
Code (MBPP, HumanEval)
Orchestrator decisions K+1
5
4
Rounds
1, from the uniform reference
1
Proposal sample
200 problems × 32 repeats =6,400
same
Validation sample
8,000 i.i.d. draws from the validation pool
same
Score model
MLP on the whole observation: Linear( 405→64 ), tanh, Linear( 64→10 ), tanh
MLP on the last 24 (process) features: Linear( 24→64 ), tanh, Linear( 64→11 ), tanh
Score range
fθ(s,a)∈[−1,1] , one output per action, shared across decisions
same
Appendix
Table 5: IAPO settings of every reported run.
config A ( λ=0.076 )
CW1 ( λ=1 )
Family
η
b(Z2)
b(ZIS)
ϵ
b(Z2)
b(ZIS)
ϵ
QA / math ( K+1=5 )
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 ( K+1=4 )
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
Appendix
Table 6: Known interval lengths b of Z2 and ZIS (with the per-problem baseline) and the remainder ϵ(η) , per family and per cost weight of the objective.
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
Appendix
Table 7: Single episode of the deployed policy, mean over runs: accuracy (%) and tokens per problem (thousands) of IAPO and of its first-order variant (FO).
(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.3 (2.2)
85.1 (25.8k)
+5.6 (5.5)
MATH
DyLAN 48.3 (54.3k)
48.6 (50.8k)
+0.3 (0.2)
54.3 (51.1k)
+6.0 (2.6)
DROP
Debate 70.6 (57.1k)
74.2 (46.0k)
+3.6 (3.3)
66.1 (51.7k)
−4.5 ( −2.9 )
MBPP ‡
DyLAN 71.2 (121.9k)
80.9 (33.1k)
+9.7 (6.3)
78.3 (29.0k)
+7.2 (4.6)
Appendix
Table 8: Paired comparisons, with z in parentheses and bold for z>2 . (a) Matched budget against the strongest baseline (mean over runs): accuracy (%) and tokens per problem, and the difference in points. ‡ Against DyLAN, at the smaller budget of Appendix I . (b) IAPO minus its first-order variant on net return and accuracy.
Figure 4: Every system on each benchmark. Top: accuracy, with the strongest baseline’s accuracy dashed; bottom: tokens per episode (log scale). IAPO and IAPO-Lite are shaded; as in Figure 2 , their accuracy is that of the voted plan within the strongest baseline’s budget.
Figure 5: Left: gain over the reference of the generalist alone (the choice of the first-order score), the analyst alone, and the evidence finder followed by the analyst. Right: runs that deploy the pair, with the interaction term and with first order only, for each benchmark.
Figure 6: Plan deployed by each IAPO run, with the interaction term (left) and with first order only (right): roles in call order, with accuracy and tokens of a single episode. Each row is a separately trained run. evid.: evidence finder; general.: second answerer reading the whole document; calc.: calculator; select: selector.
Large language models (LLMs) provide a flexible foundation for multi-agent systems, but their effectiveness and computational cost depend critically on orchestration design. Across different tasks, role design, capacity assignment, and dependency construction jointly affect both solution quality and execution efficiency. Existing approaches automate parts of this design process, yet they often optimize these decisions partially or sequentially, and rely on execution-level feedback that provides limited credit assignment for local orchestration decisions. We propose LEMON (Learning Executable Multi-Agent Orchestration via Counterfactual Reinforcement Learning), an LLM-based orchestrator that learns to design efficient multi-agent orchestration. Given a task, LEMON designs a unified orchestration specification that composes customized agent duties, capacity levels, and dependency relations. To train the orchestrator, we augment the orchestration-level Group Relative Policy Optimization (GRPO) objective with a localized counterfactual credit signal that edits role, capacity, or dependency fields and applies the resulting reward contrast only to the edited spans. Experiments on six reasoning and coding benchmarks, including MMLU, GSM8K, AQuA, MultiArith, SVAMP, and HumanEval, show that LEMON achieves the best average performance among evaluated multi-agent orchestration methods while improving the accuracy-token trade-off.
Agentic orchestration delegates tasks to sub-agents with independent contexts, providing a key path to extending the effective execution horizon of large language model agents. However, existing orchestration methods face two limitations: in execution, current methods fix sub-agents' goals and harnesses at creation time, limiting their adaptability to dynamic real-world environments; in optimization, sparse and delayed feedback constrains effective learning of the orchestration policy. To address these limitations, we introduce POrchestra, an on-the-fly proactive agentic orchestration framework. It allows sub-agents to proactively communicate with the orchestrator at any logical point to request harness adjustments while maintaining continuity of local execution. This mechanism not only enables sub-agents to adapt seamlessly to dynamic environments but also naturally inspires On-Policy Orchestration Distillation (OPOD) based on hindsight feedback. OPOD attributes sub-agents' proactive revision requests back to preceding orchestration decisions to derive targeted improvement signals, and leverages these signals as process supervision alongside the final reward to optimize the orchestration policy. We evaluate POrchestra on three long-horizon agent benchmarks spanning deep research, dynamic digital assistance, and software engineering. POrchestra improves task success by an average of 9.1% relative to the strongest baseline; combined with OPOD, it improves small-orchestrator success by an average of 10.0% relative to existing training baselines. POrchestra also achieves a more favorable cost-performance trade-off. Our code is publicly available at https://github.com/XueyangFeng/POrchestra.
Xueyang Feng, Chaozhuo Li, Xiaohe Bo +4
Gaoling School of Artificial Intelligence, Renmin University of China · Beijing Academy of Artificial Intelligence · The Chinese University of Hong Kong Shenzhen
Learned orchestration can automatically construct effective language-model multi-agent systems, but existing approaches couple planning to fixed worker pools and train decomposition and collaboration from the same terminal outcome, limiting transfer and obscuring credit assignment. We introduce DeOrch, which separates worker-agnostic planning from concrete worker selection. Its two-stage planner first decomposes the task without worker information, then chooses collaboration operations using compact, worker-identity-free matchability feedback from the pool, enabling conditional credit assignment to decomposition and collaboration decisions. A lightweight matcher estimates worker suitability from behavior on a fixed probe set and adapts online with a contextual bandit, allowing new workers to be incorporated without retraining the planner or matcher. Across diverse in- and out-of-distribution tasks, DeOrch outperforms prior automatic MAS orchestration methods with fewer worker calls than competing learned orchestrators, remains effective when transferred to an entirely unseen worker pool without retraining, and shows consistent gains from both components.