acceptodds
Under review as a conference paper at ICLR 2027

Don't Just Optimize Prompts: Evolving Agent Communication Protocols with EvoProtocol

Abstract

Multi-agent systems (MAS) tackle complex tasks by coordinating role-specialized agents with focused context. By iteratively optimizing and evolving their components from execution feedback, these systems can improve their performance and efficiency over time. However, prior work mainly focuses on optimizing agent prompts or coordination workflows, while the inter-agent communication protocol, a fundamental component that determines what agents communicate and how they exchange information, remains largely underexplored. To address this limitation, we propose EvoProtocol, a framework that exposes the communication protocol as an explicit optimization variable and evolves it jointly with agent prompts. On MAS-PromptBench, jointly evolving prompts and protocols outperforms prompt optimization under every fixed protocol on all five tasks, even when compared against the best-performing fixed protocol for each task. On BrowseComp-Plus with a dynamic planner–executor workflow, EvoProtocol improves accuracy by – points over prompt optimization with fixed protocols, and its cost-aware variant achieves higher accuracy at lower cost than prompt optimization with the hand-designed PACT protocol. These results show that co-evolving communication protocols with agent prompts yields better combinations of prompts and protocols than prompt optimization under fixed protocols.

Primary area:
generative models
Keywords:
Self-Evolving Agent, Multi-Agent Systems

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_dTf5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes EvoProtocol, which represents each inter-agent communication protocol as text (an output schema, a set of forwarded harness-state entries and a message template) and evolves it jointly with the agent prompts inside GEPA, guided by local feedback built from what the receiving agent does after each message. It is evaluated on five MAS-PromptBench tasks with a four-agent sequential workflow and on BrowseComp-Plus with a planner-executor workflow, against prompt-only GEPA under raw-trace, agent-output and PACT protocols, with cost-aware optimization and ablations. The paper reports an average of 75.3 on MAS-PromptBench against 72.9 for the best prompt-only baseline, and 78.0 on BrowseComp-Plus against 72.5 with PACT, with a cost-aware variant at 78.5 and $0.47 per execution.

Critical strengths
  1. Treating the communication protocol as an explicit, textual optimization variable is a clean idea that plugs directly into existing textual optimizers, and the local feedback that ties each message to the receiving agent's next actions is a sensible way to give the optimizer something more specific than the final score. It matters to my assessment because it opens a component that prompt optimization leaves fixed, and Table 1 gives a reasonable motivation, since the best fixed protocol changes from task to task.

  2. The per-execution cost reporting is unusually careful. Table 3 breaks each method down into planner and executor tokens and dollars, and the totals reproduce from the prices in Table 7, which lets a reader weigh accuracy against deployment cost directly.

Critical weaknesses
  1. My main concern is that the comparison with the prompt-only baselines is not quite like for like. Section 4.1 states that the methods "differ only in the set of optimized variables", yet the protocol modules receive diagnostics the prompts never see, such as the per-hand-off "Answer trail" (Table 10), and on BrowseComp-Plus only EvoProtocol can forward the hand-designed harness state of Table 5, at over 25 times the default baseline's executor input tokens (Table 3). The search is also matched only in executions: EvoProtocol proposes revisions for more modules in each iteration, and the optimizer's own token cost is not reported for any method. This matters because the central claim is that optimizing the protocol is what helps, and at present the gain could also come from the extra information, compute and search.

  2. The evidence for several of the headline margins is thin. Every result comes from one optimization run, with no per-seed results, confidence intervals or significance tests, and the MAS-PromptBench test-set sizes are never stated, while the claim of winning on "all five tasks" rests on margins of 0.3 points on HotpotQA and 0.7 on BFCL (Table 1). The 5.5 point BrowseComp-Plus gain over PACT is averaged over two evaluation seeds on 100 questions. None of this shows the gains are absent, but I cannot yet tell which comparisons would survive sampling and run-to-run variation.

Questions for authors
  1. [Experiment] How does prompt-only GEPA perform when given the same protocol diagnostics as EvoProtocol, how does EvoProtocol perform with global feedback only, and on BrowseComp-Plus, how does a fixed protocol that forwards the Table 5 harness state compare at a matched executor cost? If the gains hold under these controls, I would be glad to raise my score.

  2. [Experiment] Could you report per-seed results with confidence intervals for Tables 1 and 2, repeat the optimization over a few seeds if feasible, and state the test-set size of each MAS-PromptBench task?

  3. [Clarification] Could you report each method's search cost (optimizer calls, tokens and dollars) separately from the per-execution cost, with a break-even number of deployed runs against accuracy-only PACT, where cost-aware EvoProtocol saves about $0.09 per execution (Table 3)? It would also help to know how sensitive the cost-aware results are to the 80% accuracy threshold of Section 3.3.

  4. [Experiment] In Table 4(a), EvoProtocol's prompts with the raw trace match or exceed the full system on MATH, GPQA and BFCL. What happens when the optimized protocols are paired with the GEPA-baseline prompts, and how does the sequential variant of Table 4(b) do with a full prompt budget?

  5. [Clarification] Table 10 does not cover BFCL, and the 11 interface checks and the optimizer prompts are not given. Could these be added to the appendix, and do you plan to release the code?

6 comments

We thank the reviewer for their feedback and insightful suggestions. We address each of the reviewer’s concerns individually below.

W1.1 and Q1.1 How does prompt-only GEPA perform when given the same protocol diagnostics as EvoProtocol, how does EvoProtocol perform with global feedback only

We added two experiments that compare prompt-only GEPA using protocol feedback in EvoProtocol and EvoProtocol with global feedback only. As summarized in the table, giving the protocol diagnostics to prompt-only GEPA does not improve its accuracy as observed in EvoProtocol. In addition, removing segment-level feedback from EvoProtocol lowers the average accuracy from 75.3 to 73.5. These results show that the gain comes neither from the modified information alone nor from expanding the search space to protocols alone, but from the joint optimization of prompts and protocols, each with feedback tailored to it.

SettingsPromptProtocolMATHHotpotQAGPQABFCLToolHopAvg.
No optim.FixedFixed68.748.771.766.367.364.5
GEPAGEPAFixed76.352.074.092.369.772.9
EvoProtocolEvolvedEvolved79.354.078.093.072.075.3
EvoProtocol w/o Segment-level feedbackEvolvedEvolved77.350.374.092.073.773.5
GEPA w/ protocol diagnosticsEvolvedFixed69.750.074.092.370.371.3

W1.2 and Q1.2 and on BrowseComp-Plus, how does a fixed protocol that forwards the Table 5 harness state compare at a matched executor cost? Q3.2 It would also help to know how sensitive the cost-aware results are to the 80% accuracy threshold of Section 3.3.

We compare methods by the total cost per rollout rather than the executor cost alone. In multi-agent systems that combine a large and a small model, the cost per token differs greatly between agents (25 times in our setting, Table 7), so the total cost depends on how information is divided between them. EvoProtocol discovers such a division through search rather than by hand design. It forwards more harness states to the cheap executor, which increases the executor input but reduces the planner cost to about one third (\0.083vs.0.083 vs. \\0.268 for accuracy-only PACT). However, we agree that the original submission lacked a baseline that forwards the harness state to the executor with a fixed protocol. We therefore added a fixed protocol that forwards all harness states, optimized with both accuracy-only and cost-aware objectives. We also report both the highest-accuracy candidate (“Acc”) and the candidate selected by the 80% rule (“Cost”) to show the sensitivity to the threshold. In the Pareto column of the table, “Acc” and “Cost” denote these two candidates, respectively, and “Acc, Cost” indicates that both select the same candidate. As summarized in the table, forwarding all harness states achieves the highest accuracy (81.0%) at the highest cost (\0.915),whereascost−awareEvoProtocolachieveshigheraccuracyatalowercostthanthecost−awareallharnessstateprotocol(78.50.915), whereas cost-aware EvoProtocol achieves higher accuracy at a lower cost than the cost-aware all harness state protocol (78.5% at \\0.467 vs. 75.5% at \0.727).Comparedwiththehighest−accuracycandidateofcost−awarePACT,cost−awareEvoProtocolachievescomparableaccuracy(78.50.727). Compared with the highest-accuracy candidate of cost-aware PACT, cost-aware EvoProtocol achieves comparable accuracy (78.5% vs. 78.5%) at a lower cost (\\0.467 vs. \0.612),andthecostreductionof0.612), and the cost reduction of \\0.145 per rollout is larger than that against accuracy-only PACT. These results show that an efficient harness cannot be obtained simply by forwarding more information to the executor; it requires selecting which information to forward, which EvoProtocol learns through search. Based on these results, we will revise the manuscript as follows:

  • We will add the results on all harness states in Table 2
  • Report both the highest-accuracy candidate and the candidate selected by the 80% rule for cost-aware optimization in Table 3, including the protocol with all harness states.
  • We will revise the discussion of the BrowseComp-Plus results in Section 4.3 accordingly, shifting the focus from accuracy alone to the accuracy–cost trade-off.
SettingParetoPromptProtocolHarness StateAcc (%) on BC-PlusAcc (%) [trial1, trial2]\$/rollout
GEPAAccEvolvedFixedNone62.0[63.0, 61.0]0.172
GEPA + CostAcc, CostEvolvedFixedNone62.5[63.0, 62.0]0.251
PACTAccEvolvedFixedHuman72.5[74.0, 71.0]0.555
PACT + CostAccEvolvedFixedHuman78.5[80.0, 77.0]0.612
PACT + CostCostEvolvedFixedHuman59.0[58.0, 60.0]0.239
EvoProtocolAccEvolvedEvolvedOptimized78.0[77.0, 79.0]0.796
EvoProtocol + CostAcc, CostEvolvedEvolvedOptimized78.5[76.0, 81.0]0.467
All Harness StateAccEvolvedFixedAll81.0[81.0, 81.0]0.915
All Harness State + CostAccEvolvedFixedAll75.5[74.0, 77.0]0.727
All Harness State + CostCostEvolvedFixedAll68.0[69.0, 67.0]0.319

W1.3 and Q3.1 Could you report each method's search cost (optimizer calls, tokens and dollars) separately from the per-execution cost, with a break-even number of deployed runs against accuracy-only PACT, where cost-aware EvoProtocol saves about \$0.09 per execution (Table 3)?

Since the optimizer cost was not recorded in the original experiments, we re-ran two optimization iterations for each method, one starting from the seed and one starting from the final optimized state, to measure the per-iteration search cost. The table below separates this cost into rollout generation and optimizer calls. For EvoProtocol, we report the cost-aware variant to compare it against accuracy-only PACT. The search cost is dominated by rollout generation, and the additional optimizer calls of EvoProtocol cost less than \1periteration.Toestimatethetotalsearchcostwithabudgetof600rollouts,weassumethattherolloutcostchangeslinearlyfromtheseedtothefinalstateandmultiplytheaveragerolloutcostofthetwomeasurediterationsby12.Wecomputetheoptimizercostfromtheaveragecostpercallandtheactualnumberofoptimizercalls(12forPACTand32forEvoProtocol).Theestimatedtotalsearchcostis1 per iteration. To estimate the total search cost with a budget of 600 rollouts, we assume that the rollout cost changes linearly from the seed to the final state and multiply the average rollout cost of the two measured iterations by 12. We compute the optimizer cost from the average cost per call and the actual number of optimizer calls (12 for PACT and 32 for EvoProtocol). The estimated total search cost is \\211.5 for PACT and \220.9forcost−awareEvoProtocol.Giventheper−executionsavingof220.9 for cost-aware EvoProtocol. Given the per-execution saving of \\0.09, the additional search cost is recovered after about 110 runs. Based on these results, we will revise the manuscript as follows:

  • Add the search cost of each method, separated into rollout generation and optimizer calls, to the appendix.
MethodIterationRolloutsRoll inRoll cachedRoll outRoll $Opt callsOpt inOpt outOpt $Total $
GEPASeed5056,371,91213,553,4082,447,21715.6682157,9285,6780.96016.628
PACTSeed5050,678,21512,114,0481,717,44914.7202146,2085,3630.89215.612
EvoProtocol + CostSeed5082,573,78211,836,6722,288,99021.1224200,9447,5611.23222.354
GEPAOptimized5017,078,1914,237,9521,289,7546.7832139,6309,0020.9687.752
PACTOptimized5026,717,5777,889,0241,953,30019.5842147,9748,6190.99820.583
EvoProtocol + CostOptimized5041,105,4906,543,3602,286,11614.2094137,06310,5501.00215.211

W1.4 the central claim is that optimizing the protocol is what helps, and at present the gain could also come from the extra information, compute and search.

Given the controlled experiments (see W1.1, W1.2, and W1.3), the gains of EvoProtocol cannot be explained by the additional information, compute, or search alone. Providing the protocol diagnostics to prompt-only GEPA does not improve its accuracy (W1.1). Forwarding all harness states improves accuracy but at a substantially higher cost, whereas EvoProtocol learns which information to forward and to whom, achieving a better accuracy–cost trade-off (W1.2). Moreover, expanding the search space to protocols adds only a marginal optimizer cost (less than \1 per iteration). In addition, EvoProtocol is estimated to cost \220.9, only about 4.5% more than accuracy-only PACT (\$211.5), and this additional cost is recovered after about 110 deployed runs thanks to its lower per-execution cost (W1.3). Instead, the gains stem from co-optimizing prompts and protocols, with segment-level feedback guiding the protocol search, as supported by the ablations (see W1.1).

Reviewer_r9YiOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether optimizing inter-agent communication protocols jointly with agent prompts can improve the performance of LLM-based multi-agent systems (MAS). The authors propose EvoProtocol, which represents each communication protocol through a message template, an output schema, and selected harness states, and jointly optimizes these components with agent prompts using GEPA and execution-trace feedback. Experiments on MAS-PromptBench and BrowseComp-Plus show consistent improvements over GEPA-based prompt optimization with fixed communication protocols, with additional benefits in execution cost under cost-aware optimization. Compared with prior work focusing on prompt or workflow optimization, the main contribution is introducing communication protocols as explicit optimization variables within a self-evolving MAS framework.

Critical strengths
  1. The paper studies an important yet relatively underexplored problem: optimizing inter-agent communication protocols rather than treating them as fixed components. This is particularly relevant for practical MAS, where effective information exchange between specialized agents can significantly affect overall performance. The paper is among the early attempts to explicitly optimize message-level communication protocols jointly with agent prompts.

  2. The paper evaluates EvoProtocol across multiple tasks and both static and dynamic MAS workflows. The experiments control the underlying optimizer and optimization budget, making the comparison with fixed-protocol GEPA informative. The ablations on protocol replacement and joint versus sequential optimization provide useful evidence of the interactions between agent prompts and communication protocols. The cost-aware experiments further demonstrate potential practical benefits.

Critical weaknesses
  1. Limited comparisons with existing MAS-specific prompt optimization methods. This is my main concern. All prompt optimization baselines use GEPA, differing only in their fixed communication protocols (Raw Trace, Agent Output, and PACT). However, GEPA is a generally single-agent prompt optimizer rather than an optimization method specifically designed for MAS. Existing alternatives include MIPROv2 for multi-module prompt optimization and MAS-specific methods such as MAPRO, MASPO, and AgentGrad, which explicitly address challenges arising from agent interactions and credit assignment. Without comparisons against these approaches, it is unclear whether the reported improvements generalize beyond GEPA-based prompt optimization. I would strongly encourage the authors to include additional prompt optimization baselines under comparable computational budgets.

  2. The methodological novelty and contribution of the proposed protocol optimization mechanism need stronger justification. EvoProtocol is largely built upon GEPA, with communication protocols introduced as additional textual optimization modules. While the proposed protocol representation is useful, it is unclear what methodological advances are introduced beyond applying the existing GEPA optimization framework to an expanded set of variables. In particular, the proposed protocol-level feedback is not sufficiently validated through ablation studies. For example, the paper does not compare against protocol optimization using only global task feedback, or against optimizing communication protocols alone. These experiments would help clarify whether the improvements arise from the proposed feedback mechanism, the enlarged optimization space, or their combination.

Questions for authors
  1. Comparison with stronger prompt optimizers. How would EvoProtocol compare with alternative prompt optimizers, particularly MIPROv2 and MAS-specific approaches such as MAPRO, MASPO, and AgentGrad? Can the authors clarify whether the benefits of communication protocol optimization are expected to generalize across different underlying optimization algorithms?
  2. Contribution of protocol-specific feedback. Could the authors provide ablations isolating the benefits of protocol-specific local feedback and the individual protocol components (message templates, output schemas, and harness-state selection)? In particular, how effective is the proposed local feedback when several communication events are grouped into the same execution segment?

3, Additional related work. I suggest discussing OMAC (A Holistic Optimization Framework for LLM-Based Multi-Agent Collaboration), which considers joint optimization of agent functionality and communication flows. Although OMAC focuses on communication routing rather than message-level schemas and templates, it is closely related to the broader motivation of jointly optimizing MAS components. Clarifying the distinction between OMAC and EvoProtocol would help position the methodological novelty of this work.

5 comments

We thank the reviewer for their feedback and insightful suggestions. We address each of the reviewer’s concerns individually below.

W1 and Q1. Compare with alternative prompt optimizers, particularly MIPROv2 and MAS-specific approaches such as MAPRO, MASPO, and AgentGrad

We’d first clarify the position of our EvoProtocol. While our evaluation is mainly built on GEPA, EvoProtocol is inherently orthogonal to prompt optimizers. Therefore, our method can be applied on top of existing prompt optimizers rather than replacing them. However, our experiments lack an evaluation of the generality of our method across different optimization approaches. To address this limitation, we apply EvoProtocol to two optimizers, including MIPROv2 and MASPO. We selected the benchmarks that are supported by default in MASPO codebase and overlap with MAS-PromptBench (MATH and GPQA). Extending the MASPO codebase to our full benchmark suite was not feasible within the rebuttal period; we will make every effort to include the full results in the camera-ready version. In both settings, adding EvoProtocol on top of prompt-only optimization improves performance. While the improvement with MASPO is marginal, this integration was implemented within the short rebuttal period, and we believe there is still room to better integrate protocol search with MASPO. Improving EvoProtocol so that it can be more effectively combined with various prompt optimizers is left for future work. For MAPRO and AgentGrad, to the best of our knowledge, their implementations are not publicly available, which made it infeasible to include them within the rebuttal period. Based on these results, we will revise the manuscript as follows:

  • We will add optimizer generalization experiments in appendix
  • We will clarify the orthogonality of existing prompt optimizer in the manuscript
MethodEnvironmentPromptProtocolMATHGPQA
No Optim.MASPON/AN/A65.369.7
MASPOMASPOEvolvedFixed65.779.0
MASPO w/ EvoProtocolMASPOEvolvedEvolved66.379.3
No Optim.MAS-PromptBenchN/AN/A68.771.7
MIPROv2MAS-PromptBenchEvolvedFixed69.370.7
MIPROv2 w/ EvoProtocolMAS-PromptBenchEvolvedEvolved75.775.3

W2 and Q2.1. The methodological novelty and contribution of the proposed protocol optimization mechanism need stronger justification.

Our novelty lies in the co-optimization of prompts and protocols for multi-agent systems, and our methodological contribution lies in introducing textual representation for protocols and segment-level feedback for protocol optimization. While our approach performs better than prompt-only optimization, current evaluation lacks the detailed analysis of how co-optimization is crucial and how much segment-level feedback contributes to the final performance, as the review mentioned. To address these concerns, we have added two additional experiments: (i) compare EvoProtocol against protocol-only optimization and (ii) compare segment-level feedback with global feedback. As summarized in the table, (i) Co-optimization (75.3) outperforms protocol-only optimization (66.7) and prompt-only optimization (72.9), showing that neither component alone is sufficient. (ii) Removing segment-level feedback from EvoProtocol lowers the average from 75.3 to 73.5, showing that segment-level feedback contributes to the final performance. Together, these results indicate that the improvement comes from the combination of co-optimization and segment-level feedback, not merely from applying GEPA to a larger set of variables.

SettingsPromptProtocolMATHHotpotQAGPQABFCLToolHopAvg.
No optim.FixedFixed68.748.771.766.367.364.5
GEPAGEPAFixed76.352.074.092.369.772.9
EvoProtocolEvolvedEvolved79.354.078.093.072.075.3
Protocol-onlyFixedEvolved61.752.371.781.766.366.7
EvoProtocol w/o Segment-level feedbackEvolvedEvolved77.350.374.092.073.773.5

Q2.2 Ablation isolating the benefits of the individual protocol components (message templates, output schemas, and harness-state selection)?

To isolate the individual contribution of protocol components, we ran EvoProtocol by fixing one component to its seed value. As shown in the following table, fixing any of the three components lowers the average accuracy, showing that all components contribute to the final performance. We will add this ablation study to the appendix of the revised manuscript.

SettingsMATHHotpotQAGPQABFCLToolHopAvg.
EvoProtocol79.354.078.093.072.075.3
EvoProtocol w/ Fixed template74.047.373.793.368.371.3
EvoProtocol w/ Fixed Schema77.051.074.390.073.773.2
EvoProtocol w/ Fixed Harness State72.757.075.793.768.373.5
seed68.748.771.766.367.364.5

Q2.3 How effective is the proposed local feedback when several communication events are grouped into the same execution segment?

Our segment-level feedback relies on rule-based checks of observable actions such as tool calls, so communication events without such actions cannot be evaluated individually and are grouped into the same segment. This grouping is one design choice for implementing segment-level feedback, whose overall effect is validated in the ablation (see W2), and comparing it with alternatives such as LLM-generated segment-level feedback remains as future work.

Q3 Additional related work. I suggest discussing OMAC (A Holistic Optimization Framework for LLM-Based Multi-Agent Collaboration)

OMAC optimizes agent functionality and collaboration structure, including an LLM controller that decides whether one agent’s output is passed to another. In our formulation (Eq. 2), this routing decision determines which edges are active, so it is a dynamic form of topology optimization over G, whereas EvoProtocol optimizes how agents communicate on each edge, which OMAC keeps fixed. Although what component is jointly optimized is different between EvoProtocol and OMAC as OMAC jointly optimizes agent functionality and collaboration structure, we agree that OMAC shares our broader motivation of jointly optimizing multiple components of a multi-agent system. We will therefore add OMAC to Section 2.2 as a method that jointly optimizes agent prompts and topology in the revised version.

Thank you again for your detailed and constructive review. As the discussion period ends soon, we would like to briefly summarize how we addressed your concerns, and we would greatly appreciate it if you could let us know whether our responses have addressed your concerns.

W1/Q1 (Comparison with other prompt optimizers)

We clarified that EvoProtocol is orthogonal to the underlying prompt optimizer, and applied it on top of MIPROv2 and MASPO. Adding protocol optimization improved over prompt-only optimization in both settings, while the gain for MASPO was smaller given our preliminary integration within the rebuttal period (average +0.5 for MASPO, +5.5 for MIPROv2).

W2/Q2.1 (Source of improvement)

New ablations show that co-optimization (75.3 avg.) outperforms both prompt-only (72.9) and protocol-only (66.7) optimization, and that removing segment-level feedback lowers performance (75.3 to 73.5). This indicates the gains come from co-optimization and protocol-specific feedback, not merely from a larger optimization space.

Q2.2 (Protocol components).

Fixing any one of template, schema, or harness state reduces average accuracy (71.3 / 73.2 / 73.5 vs. 75.3), indicating that each component contributes to the overall performance, with the most influential component differing across tasks.

Q2.3 / Q3.

We clarified how communication events are grouped into segments and positioned OMAC as co-optimizing topology/routing, whereas EvoProtocol co-optimizes prompts and protocols.

Reviewer_T3h7OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces EvoProtocol, a method to automatically evolve communication protocols in multi-agent systems. The authors treat the protocol as a textual addition to the prompt and leverage GEPA to jointly optimize both the prompt and protocol for each agent. They also experiment with having multiple protocols for each edge, instead of assuming two agents always communicate the same way. Experiments on MAS-promptbench demosntrate the advantage of this method over several baselines.

Critical strengths
  1. Paper tackles an interesting and useful question - how should agent communcation evolve based on task feedback?
  2. Paper is clearly written and easy to understand.
  3. Experiments are well done and demonstrate the advantage of the method cleanly.
Critical weaknesses
  1. While the experiments are generally good, there are several potential confounders that need to be fully investigated: a) run prompt-only GEPA using the same feedback (i.e. keep the protocol fixed) b) compare the diff methods at compute-matched budgets (looks like evoprotocol might use more) c) does evoprotocol work well with optimizers other tahn GEPA?
Questions for authors
  1. Do the learned protocols (after full evolution) transfer well to new tasks? would be great to see something in this direction
  2. Could you report variance for the scores? Since LLM optimizers are prone to stochasticity, would be helpful to have this.
3 comments

We thank the reviewer for their feedback and insightful suggestions. We address each of the reviewer’s concerns individually below.

W1 (a). run prompt-only GEPA using the same feedback (i.e. keep the protocol fixed)

We ran the experiment prompt-only GEPA that uses the same feedback used for protocol optimization in EvoProtocol. As shown in the table below, this does not improve performance in prompt-only GEPA. This result suggests that the gains do not come from the additional feedback information alone, but from the combination of protocol diagnostics and protocol optimization. Therefore, we consider the design of target-specific feedback, including segment-level feedback for protocol optimization, to be one of our contributions, and will add this experiment to the revised manuscript.

SettingsPromptProtocolMATHHotpotQAGPQABFCLToolHopAvg.
No optim.FixedFixed68.748.771.766.367.364.5
GEPAGEPAFixed76.352.074.092.369.772.9
EvoProtocolEvolvedEvolved79.354.078.093.072.075.3
GEPA w/ protocol diagnosticsEvolvedFixed69.750.074.092.370.371.3

W1 (b). compare the diff methods at compute-matched budgets (looks like evoprotocol might use more)

We matched the search budget across methods by the number of rollouts, following GEPA. To examine the actual compute within this budget, we re-ran two optimization iterations for each method to measure its per-iteration cost (one from seed, another from the optimized state to capture cost changes during optimization), as the optimization cost was not recorded in the original experiments. The table below separates the search cost into rollout generation and optimizer calls, and shows the estimated total cost for the full budget of 600 rollouts, obtained by averaging the two measured iterations and scaling to 12 iterations. We select GEPA with the PACT protocol and the cost-aware variant of EvoProtocol to compare them at comparable inference-time cost-accuracy trade-offs. As shown in the table, most of the cost comes from rollout generation, and the estimated total search cost of cost-aware EvoProtocol is only about 4.5% higher than that of PACT. This indicates that the methods consume comparable compute under the same number of rollouts, so the accuracy gain of EvoProtocol over PACT cannot be attributed to additional compute. We therefore believe that matching the total number of rollouts across methods, as in GEPA, provides a fair comparison of the search budget.

MethodIterRolloutsRoll inRoll cachedRoll outRoll $Opt callsOpt inOpt outOpt $Total $
GEPASeed5056,371,91213,553,4082,447,21715.6682157,9285,6780.96016.628
GEPAOptimized5017,078,1914,237,9521,289,7546.7832139,6309,0020.9687.752
GEPATotal (Estimated)600134.7167.7142.4
PACTSeed5050,678,21512,114,0481,717,44914.7202146,2085,3630.89215.612
PACTOptimized5026,717,5777,889,0241,953,30019.5842147,9748,6190.99820.583
PACTTotal (Estimated)600205.8125.7211.5
EvoProtocol + CostSeed5082,573,78211,836,6722,288,99021.1224200,9447,5611.23222.354
EvoProtocol + CostOptimized5041,105,4906,543,3602,286,11614.2094137,06310,5501.00215.211
EvoProtocol + CostTotal (Estimated)600212.0328.9220.9

W1 (c). does evoprotocol work well with optimizers other tahn GEPA?

Yes. Our approach is orthogonal to prompt optimizers, so it can be applied on top of them rather than replacing them. To verify this, we applied EvoProtocol to two additional optimizers, MIPROv2 and MASPO, and observed improvements over prompt-only optimization in both settings, as shown in the table below. While the improvement with MASPO is marginal, this integration was implemented within the short rebuttal period, and we believe there is still room to better integrate protocol search with MASPO. Improving EvoProtocol so that it can be more effectively combined with various prompt optimizers is left for future work.

MethodEnvironmentPromptProtocolMATHGPQA
No Optim.MASPON/AN/A65.369.7
MASPOMASPOEvolvedFixed65.779.0
MASPO w/ EvoProtocolMASPOEvolvedEvolved66.379.3
No Optim.MAS-PromptBenchN/AN/A68.771.7
MIPROv2MAS-PromptBenchEvolvedFixed69.370.7
MIPROv2 w/ EvoProtocolMAS-PromptBenchEvolvedEvolved75.775.3

Q1. Do the learned protocols (after full evolution) transfer well to new tasks? would be great to see something in this direction

We transferred the protocols learned on HotpotQA and MATH to the other tasks, replacing only the protocol while keeping the prompts learned on each target task. The transferred protocols generally perform comparably to the protocols learned on each target task. One possible explanation is that the learned protocols convey not only task-specific content but also information about the sender agent itself as harness state. Through the co-optimization of prompts and protocols, the receiving agents learn to use such information to decide their next actions, which makes the learned protocols transferable across tasks.

ProtocolMATHHotpotQAGPQABFCLToolHop
Raw trace (no learned protocol)80.344.078.093.366.3
From HotpotQA80.3–77.392.769.0
From MATH–54.777.392.768.7
Learned on the target task79.354.078.093.072.0

Q2. Could you report variance for the scores? Since LLM optimizers are prone to stochasticity, would be helpful to have this.

We report the standard deviation and the range over evaluation seeds for all methods as shown in the following two tables (The first table covers MAS-PromptBench, and the second table covers BrowseComp-Plus). EvoProtocol outperforms the best fixed-protocol baseline on MATH, GPQA, and ToolHop, and is competitive on HotpotQA and BFCL. On BrowseComp-Plus, EvoProtocol outperforms PACT in every evaluation seed. Based on these results, we will revise the manuscript as follows:

  • Report the standard deviation and the range over evaluation seeds in Tables 1 and 2.
  • Fix the claim of winning on all five tasks to “EvoProtocol outperforms or is competitive with the best fixed-protocol baseline on all five tasks, and outperforms it on average.”
MethodProtocolOptimizedMATHHotpotQAGPQABFCLToolHopAvg.
No optim.Raw Trace–68.7 ± 2.9 [67.0, 72.0]48.7 ± 1.2 [48.0, 50.0]71.7 ± 5.5 [68.0, 78.0]66.3 ± 1.5 [65.0, 68.0]67.3 ± 1.2 [66.0, 68.0]64.5 ± 0.4 [64.2, 65.0]
GEPARaw Traceπ76.3 ± 1.2 [75.0, 77.0]52.0 ± 3.6 [49.0, 56.0]74.0 ± 4.4 [69.0, 77.0]92.3 ± 2.5 [90.0, 95.0]69.7 ± 1.2 [69.0, 71.0]72.9 ± 1.4 [71.2, 73.8]
GEPAAgent outputπ68.3 ± 1.5 [67.0, 70.0]53.7 ± 4.2 [49.0, 57.0]65.0 ± 4.6 [60.0, 69.0]91.0 ± 2.0 [89.0, 93.0]61.3 ± 1.5 [60.0, 63.0]67.9 ± 0.8 [67.0, 68.4]
GEPAPACTπ75.7 ± 1.5 [74.0, 77.0]46.3 ± 1.5 [45.0, 48.0]72.7 ± 3.1 [70.0, 76.0]89.7 ± 1.5 [88.0, 91.0]70.0 ± 1.7 [69.0, 72.0]70.9 ± 0.9 [69.8, 71.4]
EvoProtocolOptimizedπ, P79.3 ± 3.2 [77.0, 83.0]54.0 ± 1.7 [52.0, 55.0]78.0 ± 2.0 [76.0, 80.0]93.0 ± 1.0 [92.0, 94.0]72.0 ± 2.6 [70.0, 75.0]75.3 ± 1.0 [74.2, 76.2]
MethodProtocoltrial 1trial 2Average
GEPAAgent output63.061.062.0
GEPAPACT74.071.072.5
EvoProtocol (single)Optimized77.079.078.0
EvoProtocol (multiple)Optimized77.078.077.5

Thank you again for your detailed and constructive review. As the discussion period ends soon, we would like to briefly summarize how we addressed your concerns, and we would greatly appreciate it if you could let us know whether our responses have addressed your concerns.

W1a Same feedback for prompt-only GEPA.

With the same protocol diagnostics, EvoProtocol outperforms prompt-only GEPA (75.3 vs. 71.3 on average), indicating that the gains do not come from the additional feedback alone.

W1b Compute-matched comparison

All methods use the same number of rollouts, and rollout generation dominates the search cost. The estimated total search cost of cost-aware EvoProtocol is only about 4.5% higher than that of PACT ($220.9 vs. $211.5).

W1c Other optimizers

We applied EvoProtocol on top of MIPROv2 and MASPO. Adding protocol optimization improved over prompt-only optimization in both settings, while the gain for MASPO was smaller given our preliminary integration within the rebuttal period (average +0.5 for MASPO, +5.5 for MIPROv2).

Q1 Transfer to new tasks

Protocols learned on HotpotQA and MATH transfer to the other tasks and generally perform comparably to the protocols learned on each target task.

Q2 Variance

We reported the standard deviation and range over evaluation seeds for all methods.

Reviewer_LV3KOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes EvoProtocol, a framework for jointly optimizing agent prompts and inter-agent communication protocols in multi-agent systems. Unlike existing approaches that primarily optimize prompts while keeping communication protocols fixed, EvoProtocol represents each protocol as a searchable textual object consisting of a message template, an output schema, and selected harness state. The framework additionally introduces segment-level feedback to evaluate the effectiveness of individual communication events and integrates these mechanisms into the GEPA optimization framework.

The authors evaluate EvoProtocol on five tasks from MAS-PromptBench and on BrowseComp-Plus using a dynamic planner–executor workflow. The results show that joint prompt and protocol optimization outperforms prompt-only optimization under the evaluated fixed protocols. The paper also explores cost-aware optimization and demonstrates that execution costs can be reduced while maintaining competitive accuracy.

Critical strengths
  • A meaningful extension of the optimization space for multi-agent systems. The paper identifies inter-agent communication protocols as an important component that is typically fixed during prompt optimization. Representing protocols as optimizable textual objects provides a practical way to extend existing prompt optimization frameworks. I find this formulation interesting because it highlights the potential benefit of jointly adapting different components of multi-agent systems rather than optimizing prompts in isolation.

  • Encouraging empirical results across different multi-agent workflows. The evaluation covers both static multi-agent workflows and a dynamic planner–executor setting. EvoProtocol consistently improves upon the evaluated fixed-protocol baselines, and the cost-aware experiments suggest that communication protocol optimization can also improve the accuracy–cost trade-off. The use of a shared optimization framework and execution budget across the main comparisons is another positive aspect.

Critical weaknesses
  • Insufficient ablation studies to isolate the contributions of the proposed components. The paper introduces several components, including textual protocol parameterization and segment-level feedback, but their individual contributions are not sufficiently evaluated. In particular, an ablation without segment-level feedback is missing, making it unclear how much this mechanism contributes to the improvements. Moreover, Table 4(a) shows that replacing the learned protocols with raw traces does not hurt performance on several tasks, raising questions about the direct contribution of protocol optimization.

  • Limited analysis and interpretability of the learned communication protocols. Although the paper demonstrates performance improvements, it provides limited insights into why the evolved protocols are effective. Tables 11 and 12 mainly summarize the selected fields and harness states without showing the complete learned message templates or representative communication examples. Providing concrete examples and analyzing how the evolved protocols influence downstream agent behavior would strengthen the interpretability of the proposed approach and help explain the observed improvements.

Questions for authors
  • Could the authors provide an ablation without segment-level feedback to clarify its contribution to the performance improvements?

  • Could the authors provide concrete examples of learned communication protocols and explain how they improve downstream agent behavior?

  • Could the authors further clarify the accuracy–cost trade-off of EvoProtocol compared with fixed-protocol baselines under comparable inference budgets?

3 comments

We thank the reviewer for their feedback and insightful suggestions. We address each of the reviewer’s concerns individually below.

W1 and Q1: an ablation without segment-level feedback is missing, making it unclear how much this mechanism contributes to the improvements. Table 4(a) shows that replacing the learned protocols with raw traces does not hurt performance on several tasks, raising questions about the direct contribution of protocol optimization.

We have added an ablation study that removes segment-level feedback from protocol feedback to isolate how much segment-level feedback contributes to the improvement. As shown in the following table, accuracy drops on four tasks without segment-level feedback, and the average gain over GEPA shrinks from 2.4 points to 0.6 points. These results demonstrate that segment-level feedback is a key component for EvoProtocol to benefit from the joint optimization of prompts and protocols. Regarding Table 4(a), protocol optimization contributes in two ways. On HotpotQA and ToolHop, reverting the learned protocols to the raw trace drops accuracy below the unoptimized system, so the learned protocols contribute directly. On MATH, GPQA, and BFCL, prompts optimized with EvoProtocol outperform GEPA under the same raw trace, so exposing the protocol to the search leads to better prompts. In both cases, the gains arise from co-optimizing prompts and protocols, rather than from the protocol alone. The new ablation further supports the contribution of protocol optimization: weakening only the protocol feedback lowers the average accuracy from 75.3 to 73.5. Based on these results, we will update the manuscript as follows:

  • We will add the feedback ablation as Table 4(c).
  • We will revise the discussion of Table 4(a) in Section 4.4 to clarify the two ways in which protocol optimization contributes, supported by the new feedback ablation.
SettingsPromptProtocolMATHHotpotQAGPQABFCLToolHopAvg.
No optim.FixedFixed68.748.771.766.367.364.5
GEPAGEPAFixed76.352.074.092.369.772.9
EvoProtocolEvolvedEvolved79.354.078.093.072.075.3
EvoProtocol w/o Segment-level feedbackEvolvedEvolved77.350.374.092.073.773.5

W2. and Q2 Limited analysis and interpretability of the learned communication protocols.

We analyzed the learned protocols on HotpotQA, where the effect of learned protocols on accuracy is the most significant among the five tasks (Table 4(a)), by comparing full message traces of GEPA and EvoProtocol on the same test questions. The learned protocols improve how information is handed over between agents, by making each agent’s output explicit and preventing information from being lost at hand-offs. For example, on hotpotQA, the learned protocol declared evidence field, in which the agent reports the key facts extracted from its search results. As a result, the agent stops searching once it has gathered the evidence, avoiding unnecessary searching. Compared with GPEA on the same test question, EvoProtocol reduces the number of rollouts in which the agent exhausts its search budget from 35 to 14 across 3 seed executions (300 rollouts), and the search calls per question from 10.7 to 7.3. These results show that the learned protocols shape downstream agent behavior in combination with the jointly optimized prompts, which explains why prompts and protocols need to be optimized jointly. We will add the complete learned templates, representative communication examples, and this behavioral analysis to the appendix.

Q3. the accuracy–cost trade-off of EvoProtocol compared with fixed-protocol baselines under comparable inference budgets

Tables 2 and 3 show that EvoProtocol achieves a better accuracy–cost trade-off than the fixed-protocol baselines. At a comparable cost, cost-aware EvoProtocol outperforms accuracy-only PACT in both accuracy and cost (78.5% at \0.47vs.72.50.47 vs. 72.5% at \\0.56).

MethodProtocolAcc.$/roll
GEPAPACT72.50.555
EvoProtocol + CostOptimized78.50.467

Thank you for the authors' detailed responses and clarifications. Most of my concerns have been addressed, and I am willing to raise my score to 3.

Thank you very much for reconsidering our work and raising your score. We truly appreciate your constructive feedback and your careful engagement throughout the discussion.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We thank all reviewers for their constructive feedback and insightful suggestions. We have addressed each concern in the individual responses below, with additional experiments and analyses. We also found errors in the “No optim.” row of Table 1: the accuracy on MATH should be 68.7 (not 68.6) and that on BFCL should be 66.3 (not 89.7), which changes the average to 64.5. We will correct them in the revised version, and all tables in our responses will use the corrected values.

We have uploaded a revised version of the paper. All changes are highlighted in red. The main changes are as follows:

  • Main results (Table 1, Sec. 4.1–4.2): Corrected the "No optim." row, added standard deviations over evaluation seeds, stated the test-set size (100 examples per task), and revised the claim to "outperforms on average and is competitive on individual tasks" (T3h7, dTf5).
  • BrowseComp-Plus (Tables 2–3, Sec. 4.3): Added per-seed results, a control that forwards all harness states, and both the highest-accuracy and 80%-rule candidates for cost-aware optimization; revised the discussion around the accuracy–cost trade-off (T3h7, dTf5).
  • Ablations (Table 4(c), Sec. 4.4): Added protocol-only optimization, removal of local feedback, and prompt-only optimization with protocol diagnostics (LV3K, T3h7, r9Yi, dTf5).
  • Related work (Sec. 2.2): Added OMAC (r9Yi).
  • Appendix: Combination with MIPROv2 and MASPO (App. B; r9Yi, T3h7), search cost (App. C; T3h7, dTf5), ablation of protocol components (App. D; r9Yi), learned protocols and behavioral analysis on HotpotQA (App. E; LV3K), and the interface checks, BFCL feedback, and reflection prompts (App. A; dTf5).

The measured total search cost and the full MASPO results will be included in the final version.

We thank all reviewers again for their constructive feedback, which has substantially improved the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.