CEPO: A General Framework for Improving Prompt Optimization in Multi-Agent Systems

Overview

Abstract

Multi-agent systems (MAS) require both effective coordination and specialized task execution. Existing prompt optimization approaches typically couple these functions within agent-specific prompts. We introduce Coordinator-Executor Prompt Optimization (CEPO), a general framework for improving prompt optimization in MAS. CEPO separates system-level coordination from agent-level execution through a shared coordinator prompt and agent-specific executor prompts, and guides their updates according to their respective roles. This structure allows shared coordination rules to be refined consistently across agents while keeping execution instructions separately adjustable. CEPO provides the prompt structure and optimization guidance, while existing prompt optimizers perform the underlying search. Extensive experiments spanning 11 benchmarks across four domains demonstrate that applying CEPO to four existing prompt optimizers consistently improves their performance. Ablations and qualitative analyses support the proposed design, while controlled studies on a document-understanding MAS further demonstrate improved optimization budget efficiency and performance scaling with the number of agents.

Method

Two principles. Any optimizer.

CEPO changes only what is optimized and the guidance for optimizing it. Candidate generation and search are left to the optimizer you already use.

Principle 1 · Decompose

Pull shared coordination out of every agent into one coordinator prompt p_C. Each agent keeps an executor prompt p_E⁽ⁱ⁾; at inference agent A_i receives p_C ⊕ p_E⁽ⁱ⁾. Updating p_C changes the shared instructions of all agents at once; updating p_E⁽ⁱ⁾ changes only one agent’s local instructions.

Principle 2 · Align

Optimize each layer for its role with distinct meta-instructions. Φ_C steers the coordinator toward team-level collaboration (cross-agent communication, conflicting evidence, shared reasoning norms); Φ_E steers each executor toward its own task (task scoping, evidence use, concrete procedures). The coordinator learns what the team should do; the executor learns how to do it.

Phase 1 · optimize the coordinator

Φ_C · coordinator meta-instruction“Improve system-level behavior: how agents share findings, handle conflicting evidence, and support the final synthesis.”

meta-instruction → optimizer input

Black-box optimizer · unchangedPE2OPROProTeGiMASPO

optimizes p_C

p_C · coordinatorupdating · best iterate kept by system-level validation

frozenp_E^(1..N) · executorsheld fixed

Phase 2 · optimize the executors

Φ_E · executor meta-instruction“Improve this agent’s execution: scope its task, anchor on its evidence, make the procedure concrete.”

meta-instruction → optimizer input

Black-box optimizer · unchangedPE2OPROProTeGiMASPO

optimizes p_E⁽ⁱ⁾

p_E⁽ⁱ⁾ · executorsupdating · each selected by validation

frozenp_C^★ · coordinatorheld fixed

Decompose

Initialize executor prompts from the system’s default prompts; let an LLM draft an initial coordinator prompt from a description of the system and its agent roles.

Phase 1 · Coordinator

With executors frozen, the optimizer updates p_C for T_C iterations under Φ_C; the best iterate by system-level validation score is kept.

Phase 2 · Executors

With p_C^★ frozen, selected executor prompts are updated for T_E iterations under Φ_E, each selected by validation.

Any optimizer

Candidate generation and search follow the underlying optimizer. Both layers are selected by the same system-level objective; only the target and the guidance change.

Overview of CEPO: prompt decomposition into a coordinator prompt shared across all agents and executor prompts local to each agent; inference prepends the coordinator to every executor; optimization runs in two phases, coordinator first with meta-instruction Phi_C, then executors with Phi_E, using any black-box optimizer. — **Overview of CEPO.** Prompts in a multi-agent system are decomposed into two layers with distinct roles. The coordinator prompt `p_C` (shared across all agents) captures coordination signals: team composition, role assignment, shared norms for reasoning. Each executor prompt `p_E⁽ⁱ⁾` (local to agent *A_i*) captures execution signals: evidence anchoring, task scoping, procedure execution. The two layers are optimized sequentially with role-aligned guidance by an existing optimizer O plugged in without modification.

Prior work couples coordination and execution within agent-specific prompts; CEPO separates them into a shared coordinator prompt and agent-specific executor prompts with role-aligned optimization guidance. Right: accuracy on MDocAgent + MMLongBench-Doc rises from 54.1 (baseline) to 57.9 (vanilla PO), 58.6 (prompt decomposition) and 61.0 (CEPO). — **Prior work vs. CEPO.** Existing methods couple coordination and execution within agent-specific prompts and optimize them role-agnostically. CEPO represents the two functions as distinct optimizable parameters and guides their updates by role. On MDocAgent + MMLongBench-Doc, a vanilla optimizer improves the baseline from 54.1 to 57.9, prompt decomposition reaches 58.6, and decomposition with role-aligned optimization (CEPO) reaches **61.0**.

Experiments

Any domain · any MAS · any optimizer: it goes up

Applied to four prompt optimizers on four multi-agent systems, CEPO improves every optimizer × system × benchmark setting we tried.

DomainsDocumentMathCodeVideo

SystemsMDocAgentDocAgentMASPO-MASLongVideoAgent

OptimizersPE2ProTeGiOPROMASPO

0 / 26

settings improved

Accuracy gain in points vs. the same optimizer without CEPO; the DocAgent row is vs. its unoptimized baseline. Hover a cell for the setting.

Table 2: document understanding results on MMLongBench-Doc, LongDocURL, PaperTab, PaperText and FetaTab. MDocAgent + CEPO and DocAgent + CEPO improve on every benchmark, with average gains of 4.3 and 2.7 points. — **Document understanding.** PE2 + CEPO on two multi-agent systems, MDocAgent (Qwen-3.5 4B) and DocAgent (GPT-5-mini), against proprietary models, single-agent and multi-agent baselines. Both systems improve on every benchmark: +4.3 and +2.7 on average, up to +7.9 on MMLongBench-Doc. Green subscripts are gains over the unoptimized system; CEPO rows are highlighted. † marks results on a custom 10/10/80 train/val/test split; other rows are on the original test sets.

Table 8: PE2, ProTeGi and OPRO on MDocAgent with and without CEPO across five document benchmarks; CEPO improves every optimizer-benchmark combination. — **Different prompt optimizers.** PE2, ProTeGi and OPRO on MDocAgent, each kept with its default hyperparameters; rows are cumulative within each block. CEPO improves every optimizer–benchmark combination, by 0.6 to 6.5 points over the corresponding vanilla optimizer.

Table 3: MASPO with and without CEPO on AQuA, MATH-500, AGIEval-MATH, HumanEval-ET and MBPP; CEPO improves all five, +5.07 average over the baseline. — **Math & code with a MAS-specific optimizer.** On MASPO’s Qwen3-8B multi-agent system, CEPO on top of MASPO improves all five benchmarks: +5.07 average over the baseline, +1.04 over MASPO alone.

Table 7: LongVideoAgent on LongTVQA+: 60.3 baseline, 63.4 with PE2, 64.9 with PE2 + CEPO. — **Long-video understanding.** LongVideoAgent (Qwen2.5-7B master agent, GPT-5-mini grounding and vision agents) on LongTVQA+: CEPO adds 1.5 points over vanilla PE2 and 4.6 over the baseline.

Analysis

Why it works

MDocAgent on MMLongBench-Doc with PE2. Both principles matter, the gains grow with the team, and CEPO reaches a higher score with fewer optimizer and MAS calls.

Both principles matter

Component ablation, accuracy (%)

Decomposition alone reaches 58.6; role-aligned optimization of both layers reaches 61.0. Table 4

Gains grow with the team

Accuracy vs. number of agents

Vanilla PE2 is non-monotonic (below the unoptimized system at three agents); PE2 + CEPO rises monotonically, and its advantage grows from +3.9 at two agents to +6.9 at five. Figure 3

Cheaper, too

Accuracy by training budget · bar = MAS API calls

PE23 executor iterations

5,714 MAS calls · 10 opt. calls

57.9

PE2 + CEPO1 + 1 iterations

3,120 MAS calls · 2 opt. calls

60.1

PE26 executor iterations

11,945 MAS calls · 22 opt. calls

57.4

PE2 + CEPO3 + 3 iterations

11,458 MAS calls · 20 opt. calls

61.0

One iteration per layer beats vanilla PE2 with three at roughly half the MAS calls; at a comparable budget the gap is 3.6 points. Table 5

Role-aligned guidance is best

Guidance swap · which meta-instruction goes to which layer

p_E ← Φ_C
coordination

p_E ← Φ_E
execution

p_C ← Φ_C
coordination

58.1same guidance

61.0role-aligned (CEPO)

p_C ← Φ_E
execution

57.7swapped

59.1same guidance

Coordination guidance for the coordinator and execution guidance for the executors is best; reversing them is worst, and using the same guidance for both layers lands in between. Table 6

Optimized prompts: the coordinator evolves from a generic system description into team-level orchestration rules; the General agent's executor evolves from vague instructions into a concrete agent-level execution procedure. — **Complementary roles.** Through optimization, the coordinator prompt evolves from a generic description into team-level orchestration rules (flag unsupported claims, identify unresolved issues, support final synthesis), while the General agent’s executor prompt evolves from vague instructions into a concrete execution procedure (combine OCR and image evidence, ground answers locally, extract table rows). The coordinator learns *what the team should do*; the executor learns *how to do it*.