Multi-Agent Collaboration via Evolving Orchestration

TL;DR

Multi-agent LLM systems usually hard-code their structure — a chain, a tree, a debate graph — and that rigidity gets expensive and brittle as you add agents (the paper notes a 50-node mesh taking 10 hours to write a few hundred lines of code). This work replaces the fixed wiring with a centralized orchestrator (the “puppeteer”) that, at each step, looks at the current task state and chooses one agent to activate next. The whole collaboration becomes a sequence of routing decisions rather than a pre-drawn graph. They then train the orchestrator with REINFORCE, a basic policy-gradient RL method, using a reward that rewards correct/high-quality answers and penalizes token/compute cost. Result: across math, knowledge, software-building, and creative-writing benchmarks, the evolved orchestrator beats static multi-agent baselines while using fewer tokens — and the structures it discovers are not chains but compact, cyclic graphs where a few “hub” agents repeatedly refine each other’s work.

Problem & Motivation

The pain in one sentence: static multi-agent topologies don’t scale — adding agents adds coordination overhead, redundant computation, and cost faster than it adds capability.

If you’ve built a multi-agent system, you know the failure mode. You decide up front that Agent A hands to Agent B hands to Agent C (a chain), or you let every agent talk to every other agent (a mesh). The chain is cheap but dumb — it can’t revisit a bad step. The mesh is expressive but explodes: with N agents you get up to N² communication paths, most of which are wasted, and the token bill scales accordingly. Worse, the right structure depends on the task. A simple arithmetic question wants a short path; a software project wants branching and backtracking. A single fixed topology can’t be right for both.

Prior attempts to fix this either (a) search over canonical graph shapes (chains/trees/DAGs) — but the space of topologies is combinatorially huge so they only explore a sliver, or (b) let each agent autonomously decide who to call next — which reintroduces the coordination overhead and is hard to optimize globally. Neither learns, from experience, a policy for who-talks-when that jointly optimizes quality and cost.

The motivating question the authors pose: can dynamic orchestration maximize collaborative effectiveness and computational efficiency at the same time? The interesting empirical claim is that the answer is yes — these usually trade off, and here they don’t.

What’s New (Core Contribution)

Two genuine ideas, plus a useful empirical finding:

• Dynamic orchestration as a sequential decision problem (the “puppeteer”). Before: the agent graph is drawn ahead of time (static) or negotiated locally by agents. Now: one centralized policy π picks a single agent to activate at each step, conditioned on the evolving task state. The graph is never explicitly chosen — it emerges as the trace of routing decisions. Crucially they serialize the problem: instead of searching over graph topologies, the orchestrator “unfolds” the collaboration into a linear sequence of picks. Fold that sequence back up and you recover a directed graph, but you never had to search graph-space — you searched over next-agent decisions, which is far more tractable.

• Adaptive evolution via reinforcement learning. Before: topology is fixed once and never improves from outcomes. Now: after each completed task, the system gets a reward combining answer quality and compute cost, and updates the orchestrator’s policy with REINFORCE. Over many tasks the puppeteer learns to promote agents that help and prune agents that waste tokens. This is the “evolving” in the title — the orchestrator gets better with experience, the agents themselves are not retrained.

• Empirical finding: efficiency and quality rise together, and the learned structure is compact + cyclic. Static MAS literature treats more-collaboration as more-tokens. Here, token use drops over training while accuracy rises. And the emergent structures aren’t trees — they condense into dense subgraphs of a few hub agents with cycles (agents revisiting each other to verify and refine, à la Reflexion).

What’s not new: REINFORCE is from 1992; modeling MAS as a directed graph-of-thoughts is borrowed (MacNet, Graph-of-Thoughts). The novelty is the framing (routing-as-RL-policy) and the joint quality/cost reward, not the RL machinery.

How It Works (Technically)

Let me build this up from the pieces, then trace one task through end to end.

The agent abstraction. Each agent is a triple a = (m, r, t): a foundation model, a reasoning pattern (decompose, reflect, critique, refine, summarize, terminate…), and a set of tools (web search, code interpreter, file reader…). The agent space A is every combination of those. So “GPT-4o + reflection + code-interpreter” and “Qwen-7B + critique + no-tools” are two different agents. An agent is an atomic reasoning behavior — one move in the collaboration.

The system as a graph that gets unfolded. Following MacNet, the MAS is a directed graph G = (V, E): nodes are agents, edges carry intermediate context from one agent to the next, with a source node (the task) and a sink node (the final artifact). The clever move: rather than choosing this graph up front, the orchestrator unfolds it into a sequence. At each step it appends one agent to the running trace. The edges are implied by which states feed which agent.

The orchestration loop (the heart). Formalized as a Markov Decision Process. At step t:

1. The orchestrator observes global state S_t (everything produced so far, plus the task spec τ).
2. It samples one agent to activate: a_t ∼ π(S_t, τ). Read this plainly: π is a function that takes “what’s happened so far” and outputs a probability distribution over which agent to call next; you sample from it. In practice π can be a neural scorer, an embedding-similarity model, or a Bradley-Terry-style preference model (they initialize it from a Llama-3.1 reward-model variant).
3. The chosen agent runs: o_t = f_{a_t}(s_t(a_t), S_t) — it gets its slice of the state and produces an output o_t.
4. The state updates: S_{t+1} = Φ(S_t, o_t) — fold the new output back into the shared context.
5. Repeat. Because the next pick depends only on the current state S_{t+1} (not the full history), the process satisfies the Markov property — this is what licenses using standard RL. The loop stops when a designated Terminator agent is chosen or the step budget is exhausted, then an aggregation function F_agg (they use majority voting) combines outputs into the final answer.

That’s the inference-time mechanism. Now the learning.

Why RL, and which one. The orchestrator’s choices are discrete (pick an agent) and you only learn whether they were good after the whole task finishes (was the answer right? how many tokens did it burn?). That delayed, non-differentiable feedback is exactly what reinforcement learning is for. They use REINFORCE — the simplest policy-gradient method. Intuition: run the policy, get a trajectory and its total reward R(τ); if the reward was high, nudge the policy’s parameters to make all the choices in that trajectory more likely; if low, less likely. The gradient estimate is:

∇θ J(θ) ≈ (1/N) Σ_n Σ_t  ∇θ log πθ(a_t | S_t) · R(τ)

In English: for each step t in each sampled trajectory n, take the gradient of the log-probability the policy assigned to the agent it actually picked, and scale it by the trajectory’s total reward. Sum and average. Then θ ← θ + α·∇θ J(θ) — climb the reward. High-reward trajectories pull their agent-choices up; low-reward ones push theirs down. Over thousands of tasks the policy converges on routing patterns that pay off. (REINFORCE is high-variance — no baseline/advantage subtraction here — which is the main thing a follow-up would fix; see “How to Improve It”.)

The reward design — this is where the cost-saving lives. The terminal reward at the last step is r − λ·C_T: solution quality r (∈{0,1} for tasks with ground truth, ∈[0,1] for open-ended) minus λ times the total compute cost. Rewards propagate backward through the trajectory with a discount γ:

R_t = r − λ·C_T                if t = T   (terminal step)
R_t = γ·R_{t+1} − λ·C_t        if t < T   (earlier steps)

and the per-step cost is C_t = F · log(1 + t/φ), where F is a FLOPs/token measure of that step and φ is the max step budget. Two knobs do the work: λ trades accuracy against cost (bigger λ → the policy fights harder to use fewer/cheaper agents and to terminate early), and the log(1 + t/φ) term makes later steps progressively more expensive, nudging the orchestrator to finish sooner. Set λ=0 and the system “degenerates into a traditional large-scale collaborative framework” — i.e., the cost penalty is the only thing keeping it lean. They use λ=0.1, γ=0.99, episode length 4, up to 3 parallel explorations.

Architecture & data flow

flowchart TB
  subgraph Inference["Inference: one task episode"]
    T[Task τ] --> S0[State S_0]
    S0 --> P{Puppeteer policy π}
    P -->|pick agent a_t| AG[Agent a_t = model + reasoning + tools]
    AG -->|output o_t| UP[State update Φ: S_t+1]
    UP -->|S_t+1| P
    P -->|pick Terminator or budget hit| AGG[F_agg: majority vote]
    AGG --> ANS[Final artifact o*]
  end
  subgraph Learning["Learning: after the episode"]
    ANS --> REW["Reward R = quality r − λ·cost C"]
    REW --> RL["REINFORCE: ∇θ log π · R"]
    RL -->|update θ| P
  end

Step through one episode: the puppeteer picks an agent each step based on the current state; folding the sequence of picks back up reveals the emergent graph (with cycles). Schematic, not the paper's exact runs.

The algorithm, simplified

# The puppeteer loop + REINFORCE update. Stubs: llm-agent runs, reward eval.
def run_episode(task, policy, agents, max_steps=4):
    state = init_state(task)
    trajectory = []                       # (state, chosen_agent) pairs for the update
    for t in range(max_steps):
        probs = policy(state, task)       # distribution over candidate agents
        agent = sample(agents, probs)     # the routing decision being learned
        trajectory.append((state, agent))
        if agent.is_terminator:
            break
        output = agent.run(state)         # an LLM call: reason / tool-use / critique
        state = update(state, output)     # Φ: fold output back into shared context
    answer = majority_vote(state.outputs) # F_agg
    return answer, trajectory

def reward(answer, task, trajectory, lam=0.1, gamma=0.99, phi=4):
    quality = score(answer, task)                 # 1/0 or [0,1]
    total_cost = sum(flops(a) * log(1 + t/phi)    # later steps cost more
                     for t, (_, a) in enumerate(trajectory))
    return quality - lam * total_cost             # the joint objective

def train(policy, tasks, lr=1e-5):
    for task in tasks:
        ans, traj = run_episode(task, policy, AGENTS)
        R = reward(ans, task, traj)               # one scalar for the whole trajectory
        # REINFORCE: push up log-prob of every pick, scaled by the trajectory reward
        loss = -sum(log_prob(policy, s, a) for (s, a) in traj) * R
        policy.step(loss, lr)                      # gradient ascent on expected reward

That ~25 lines is the whole idea. Everything else — the agent zoo, the benchmarks — is scaffolding around this loop.

Built on Prior Work

Results & Evidence

What they tested. Four benchmarks spanning two regimes: closed-domain (GSM-Hard arithmetic, MMLU-Pro knowledge — graded on accuracy) and open-domain (SRDD software-building, CommonGen-Hard creative sentence generation — graded on composite quality metrics). Two agent pools by model size: Mimas (small open models: Qwen-7B/14B, Llama-3.1-8B/3.2-3B, Mistral) and Titan (large/frontier: GPT-4-Turbo, GPT-4o-Mini, Gemini-1.5, Claude-3, Qwen-72B, Llama-405B). Baselines span pure models, single-agent methods (Self-Refine, AFlow), and multi-agent methods (MacNet, EvoAgent).

Headline numbers. In the Titan subspace, the full Puppeteer’s average rises from 0.6893 (initial) to 0.7731 (evolved) — the RL training is doing real work, not just the architecture. The evolved Puppeteer is best or near-best on average across both subspaces, and Puppeteer-Mono (all agents driven by one model, so it’s a fair head-to-head against single-model baselines like MacNet) beats the competing methods on nearly all tasks — evidence the orchestration itself, not just model diversity, is responsible.

The efficiency claim — the interesting one. Token consumption decreases over training across almost all settings while accuracy rises. The mechanism splits by pool: Titan agents are capable enough that the orchestrator learns to stop earlier (fewer agents per task); Mimas agents are weaker, so it keeps the chain length but routes to cheaper agents. λ tunes this directly.

The structural finding. As training proceeds, graph density rises (communication concentrates among a few hub agents) and cycles increase (cycle-length stats climb, e.g. length-1 self-loops from 1.08→1.45 avg). Structures go from loose, exploratory disjoint chains to tight, cyclic, self-refining clusters.

Caveats — what the evidence does NOT establish. (1) REINFORCE with no baseline is high-variance; they don’t report variance across seeds, so the size of the gains is hard to bound. (2) Some single-task numbers regress after evolution (e.g., a few SRDD/CommonGen cells drop initial→evolved) — the win is on average, with task-level trade-offs the cost penalty sometimes gets wrong. (3) Benchmarks are academic; SRDD software tasks are small. No latency/wall-clock numbers, only token/FLOP proxies. (4) λ, episode length, and depth/width caps are tuned; the non-monotonic sensitivity (their W4D2 default is a sweet spot, more depth/width hurts) means production tuning is non-trivial. (5) The orchestrator is initialized from a strong reward model — how much of the lift comes from that prior vs. the RL isn’t fully isolated.

How You’d Use It

This maps almost directly onto an agent-orchestration offering, which is squarely in your wheelhouse.

• Replace your hand-tuned routers with a learned one. If you run a multi-agent product where you currently decide “planner → coder → tester” by hand, this is the upgrade path: log your episodes (state, which agent ran, final quality, tokens spent), and train a small routing policy on that log. You already have the data if you’re running production agents.
• Sell “cost-aware orchestration” as a line item. The λ knob is a clean client conversation: “do you want maximum quality, or quality-per-dollar?” You can expose that as a setting. Most clients are over-spending on multi-agent calls because every agent runs every time; a learned terminator + cheap-agent routing is a concrete, demonstrable cost reduction.
• Heterogeneous model pools. The Titan/Mimas split is exactly the practical question “when do I escalate to GPT-4/Claude vs. stay on a cheap open model?” The orchestrator learns that escalation policy from outcomes instead of you writing if-statements. This is a real moat — it improves with usage.
• Where it slots in: it sits above your agents as a router and beside your eval harness (the eval is the reward signal). You don’t need to retrain the agents themselves, which keeps it compatible with whatever models/tools you already deploy.

Realistic effort: a usable v1 is weeks, not months, if you already have an automated quality scorer. The scorer is the hard prerequisite — without a reward signal there’s nothing to train on.

Build Your Own (Minimal Recipe)

Smallest version that captures ~80% of the value:

1. Define the agent zoo. A dict of agents, each (model, reasoning_prompt, tools). Start with 5–8: a decomposer, a solver, a critic, a refiner, a tool-user, and a terminator. The terminator is essential — it’s how the policy learns to stop.
2. Build the episode loop. Exactly the run_episode pseudocode above: maintain a shared state (a growing context string or structured blackboard), let the policy pick one agent per step, run it, fold the output back.
3. Build the reward. quality − λ·cost. Quality from your eval (exact-match, unit tests for code, an LLM-judge for open-ended). Cost = total tokens. This is the load-bearing component — get it right before anything else.
4. The policy. Don’t start with a trained neural net. Start with a small classifier or even an LLM-as-router that outputs a distribution over the agent names given the state. Then add learning.
5. The learning loop. Plain REINFORCE: run K episodes, compute each trajectory’s reward, update log-probs scaled by reward. A few hundred lines.

The two genuinely hard parts: (a) the reward/eval harness — automated, reliable quality scoring is most of the work and the thing that breaks; (b) REINFORCE variance — raw REINFORCE is noisy, so you’ll want a baseline (subtract the mean trajectory reward) almost immediately or training won’t converge cleanly.

Reach for: any LLM API for the agents; trl or a hand-rolled policy-gradient loop for the RL; a reward model or LLM-judge for open-ended scoring; the authors’ own code (OpenBMB/ChatDev, puppeteer branch) as a reference.

How to Improve It

1. Swap REINFORCE for GRPO or PPO. REINFORCE with no baseline is the weakest part. Subtracting a baseline (advantage = reward − mean reward over a group of sampled trajectories, i.e. GRPO) slashes variance and typically converges faster and higher. Low-risk, high-payoff, and directly testable against their numbers.
2. Per-step (process) rewards, not just terminal. Right now the only signal is the final answer; every pick in a trajectory gets the same scalar. Credit-assigning which agent call actually helped (a learned critic or a value function) would let the policy prune more surgically and learn faster.
3. Make the cost model real. log(1 + t/φ) is a proxy. Plug in actual $/token per model and actual latency, and the orchestrator optimizes the metric clients actually care about (dollars, wall-clock), not FLOP estimates.
4. Let the policy pick multiple agents per step. They activate one agent per step (serialized). True parallel branching — pick a set, run concurrently, merge — would cut latency and better exploit the tree/graph structures they observe emerging, at the cost of a bigger action space.
5. Generalize the policy across task distributions. They train per-setting. A policy conditioned on a task embedding that transfers zero-shot to new task types would be the difference between a research result and a product. Test: train on math+knowledge, evaluate cold on software tasks.
6. Curriculum / online deployment learning. Because the reward is just your eval, the policy can keep learning in production from real outcomes — a flywheel where the router gets cheaper and better the more clients use it. Worth instrumenting from day one.

Glossary

• Orchestrator / puppeteer — the centralized policy that decides which agent runs next at each step.
• Puppet — an individual LLM agent, abstracted as (model, reasoning pattern, tools).
• Policy (π) — a function from current state to a probability distribution over actions (here, over which agent to activate).
• MDP / Markov property — a process where the next decision depends only on the current state, not the full history; this is what makes standard RL applicable.
• REINFORCE — the simplest policy-gradient RL algorithm: increase the probability of choices made in high-reward trajectories, decrease it for low-reward ones.
• Policy gradient — using the gradient of expected reward w.r.t. policy parameters to improve the policy.
• Reward shaping — designing the reward (here, quality − λ·cost) to steer the learned behavior.
• λ (lambda) — the trade-off weight: how hard the system fights to reduce compute cost vs. maximize quality.
• γ (gamma) / discount factor — how much future-step rewards are valued relative to immediate ones.
• Trajectory / episode — one full run of the collaboration on a task, from input to final answer.
• Terminator agent — a special agent whose selection ends the episode; learning to call it early is how the system saves cost.
• Aggregation (F_agg) — how multiple agent outputs combine into a final answer (here, majority voting).
• Graph-of-thoughts — modeling a reasoning process as a directed graph of intermediate thoughts/agents rather than a single chain.
• Compaction — the observed trend of communication concentrating among a few densely connected “hub” agents.
• Cyclicality — emergent loops where agents revisit each other to verify and refine, enabling Reflexion-style iterative reasoning.
• Bradley-Terry model — a way to turn pairwise preferences into scores; one option for implementing the routing policy.
• Titan / Mimas — the paper’s large-model and small-model agent pools, used to test the method across capability levels.