acceptodds
Under review as a conference paper at ICLR 2027

From Agents to Edges: Paired Optimization for Multi-Agent Collaboration

Abstract

Strong individual agents do not guarantee effective collaboration. Communication must align what one agent conveys with how another interprets and uses it. This dependency makes the communication edge a natural unit of optimization. We introduce Paired Automated Communication Optimization (PACO), which jointly optimizes the instructions at both ends of each edge and their shared communication convention in systems built on black-box language models. PACO keeps model weights, agent roles, and workflow topology fixed. A state-aware discounted bandit selects edges for refinement, while execution feedback guides paired revisions evaluated through staged end-to-end execution. The optimized instructions integrate into existing agent prompts without additional model calls at deployment. On a four-agent workflow evaluated across diverse multi-agent benchmarks, PACO consistently outperforms leading prompt-optimization and communication baselines. Configurations learned on HotpotQA retain their advantage in cross-dataset transfer without target-specific optimization. These results demonstrate that optimizing how agents communicate can substantially improve collaboration within an otherwise fixed system.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Multi-Agent Systems, Communication Optimization, Paired Optimization

Reviews

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

This paper proposes PACO, an edge-centric communication optimization method for LLM-based multi-agent systems. Instead of optimizing each agent prompt independently, PACO treats each directed communication edge as an optimization unit consisting of upstream sending instructions, downstream receiving instructions, and a shared communication convention. The method keeps the model weights, agent roles, information access, and workflow topology fixed. A discounted bandit selects which edge to refine, and an LLM-based proposer performs two rounds of paired revision using execution feedback. Candidate updates are evaluated through staged end-to-end workflow execution under a fixed optimization-token budget. Experiments are conducted on a fixed four-agent workflow using HotpotQA for optimization and evaluation, with transfer to DROP and MuSiQue-Ans. PACO outperforms several communication and prompt-optimization baselines, including GEPA, while using similar optimization cost. Ablations suggest that paired endpoint refinement and adaptive edge selection are useful.

Critical strengths
  1. I think the paper picks a sensible unit of optimization. The distributed-averaging example in the introduction is simple, but it makes the point: providing the correct intermediate value is not enough if the next agent lacks the information or instructions to use it. Grouping the sender instructions, receiver instructions, and shared convention around an edge is a more specific proposal than generally 'improving communication.'
  2. The comparison is reasonably controlled. The workflow and model weights are kept fixed while PACO is compared against prompt and communication optimizers, including GEPA and MASPOB. On HotpotQA, the reported Joint F1 is 61.26 for PACO versus 59.27 for GEPA at similar optimization and deployment cost. Freezing the learned configuration before testing on DROP and MuSiQue-Ans is also a useful check; this is not a fresh optimization for each target dataset.
  3. I found the message example in Table 5 worth including. It shows a concrete handoff in which making the transaction direction explicit avoids ambiguity downstream. This kind of small execution trace helps explain what is actually being changed by the optimizer, which is otherwise difficult to see from final F1 scores alone.
Critical weaknesses
  1. The results are all from a fixed four-agent chain. That setting is appropriate for studying handoffs, but it also makes the edge-level formulation easier than it might be in a graph where an agent receives several messages or sends to multiple downstream agents. Paired updates could interact through a shared receiver. The paper makes fairly broad claims about multi-agent collaboration; I would be more comfortable with a narrower claim or at least one test on a branching workflow.
  2. I am less certain about the size of the gain specifically attributable to paired refinement. Table 3 reports 49.35 Joint F1 for PACO and 48.42 for independent updates at the 5M-token budget, which is a modest gap. The main PACO result uses optimizer seed 0, whereas some search comparisons report averages over three runs. The appendix notes a small range across repeated PACO runs but does not provide comparable means and uncertainty for the key pairwise comparisons. With the HotpotQA margin over GEPA also below two Joint F1 points, I would like clearer evidence that these differences are consistent rather than seed-specific.
Questions for authors
  1. What happens when one agent has two incoming edges and the corresponding communication packages are optimized separately? If you have a branching-workflow experiment, even a small one, it would be more informative to me than adding another chain-based QA dataset.
  2. Could you report PACO versus independent updates and PACO versus GEPA over matched optimization seeds, with means and variability? The 0.93-point Table 3 gap is the comparison I would most like to see repeated.
6 comments
AuthorsOpenReview ↗

Response to Question 1

Thank you for your review and for the specific questions about shared receivers and optimization variability. We address these two points below.

1. Shared-receiver interactions and a branching-workflow experiment

Concern (summary): The original experiments use a four-agent chain, while communication packages may interact when an agent receives multiple messages. What happens when incoming-edge packages are optimized separately, and does PACO remain effective in a branching workflow?

Response: (PART 1/2)

How incoming-edge updates are evaluated. A shared receiver's communication prompt contains the receiving blocks associated with its incoming edges. In an ordinary single-edge step, PACO may revise the selected edge's sender instructions, receiver instructions, and shared convention, while keeping the other edge packages fixed. The receiver still processes all incoming messages together. Updating one package can therefore change how it uses information from the other messages, even though their instruction blocks remain unchanged.

Candidate updates are assessed through complete workflow executions, with candidate and parent task scores compared on the same examples at each evaluation stage. The observed gain therefore includes the effects of the update on the shared receiver and the final output. Edge-scheduling histories are also specific to the full configuration, since an edge's benefit can change when the surrounding packages change. When an ordinary step achieves a new best score on the full internal validation set, PACO additionally triggers a cooperative step that can revise multiple packages. Thus, single-edge editing does not assume independent effects across edges; candidate changes are evaluated in their existing communication context.

AuthorsOpenReview ↗

Response to Question 1

1. Shared-receiver interactions and a branching-workflow experiment

Concern (summary): The original experiments use a four-agent chain, while communication packages may interact when an agent receives multiple messages. What happens when incoming-edge packages are optimized separately, and does PACO remain effective in a branching workflow?

Response: (PART 2/2)

Direct test with three incoming edges. We additionally evaluate a four-role hierarchical MAS inspired by MASPO. Three parallel agents—Answer Proposer, Evidence Scout, and Bridge Resolver—independently examine the same complete source evidence and send messages to one Answer Verifier. The Verifier receives the question and their three messages, without raw evidence. It therefore combines three incoming communication packages within a single receiver call. Detailed role definitions, initialization, message assembly, and constraints are provided in our response to Reviewer 74Th (Weakness 2).

All agents use gpt-5.6-luna with low reasoning effort. The optimized methods start from the same hierarchical configuration under the original 25M-token optimization budget, with roles, topology, evidence access, and output constraints fixed. Configurations learned on HotpotQA are frozen for evaluation on DROP and MuSiQue-Ans, without target-specific optimization. For each optimized method, we independently repeat optimization and evaluation five times; Vanilla and PACT are each evaluated five times. Results are mean ± std, where std is the population standard deviation (denominator N = 5). Token costs are in millions (M).

HotpotQA: quality metrics and token costs.

Method     Joint F1    Joint EM   Answer F1   Answer EM  Support F1  Support EMDep. tokens (M)Opt. tokens (M)
Vanilla  48.05 ± 0.37  21.18 ± 0.45  54.86 ± 0.39  34.80 ± 0.66  69.52 ± 0.35  45.40 ± 0.346.34 ± 0.0030
PACT  46.74 ± 0.62  12.98 ± 0.36  57.97 ± 1.17  33.83 ± 0.60  72.25 ± 0.70  36.35 ± 0.766.73 ± 0.040
MASPO  46.46 ± 1.79  20.60 ± 0.95  53.37 ± 1.53  34.60 ± 0.53  67.89 ± 0.89  43.37 ± 0.436.34 ± 0.0224.36 ± 0.11
MASPOB  50.31 ± 2.13  22.98 ± 1.46  59.18 ± 2.42  39.17 ± 2.24  70.01 ± 1.24  45.03 ± 0.606.43 ± 0.0224.62 ± 0.08
GEPA  60.59 ± 1.18  28.88 ± 1.65  69.16 ± 1.24  46.83 ± 1.87  79.14 ± 0.22  52.88 ± 0.227.53 ± 0.1024.55 ± 0.31
PACO  62.73 ± 0.76  30.33 ± 0.87  72.43 ± 0.71  51.40 ± 0.82  79.42 ± 0.40  51.78 ± 0.916.90 ± 0.3224.37 ± 0.40

Frozen cross-dataset evaluation.

Dataset  Method   Answer F1   Answer EM   Dep. tokens (M)
DROP  Vanilla   30.03 ± 0.41   7.50 ± 0.57   1.36 ± 0.002
DROP  PACT   26.55 ± 0.49   6.35 ± 0.90   1.64 ± 0.05
DROP  MASPO   28.13 ± 2.48   6.45 ± 1.21   1.36 ± 0.12
DROP  MASPOB   36.08 ± 3.73   13.60 ± 3.17   1.41 ± 0.03
DROP  GEPA   40.57 ± 0.83   13.30 ± 0.58   1.91 ± 0.05
DROP  PACO   48.09 ± 1.32   20.00 ± 1.28   1.64 ± 0.15
MuSiQue-Ans  Vanilla   26.60 ± 0.45   15.35 ± 0.51   4.49 ± 0.002
MuSiQue-Ans  PACT   25.52 ± 1.20   11.55 ± 0.78   4.64 ± 0.06
MuSiQue-Ans  MASPO   26.24 ± 2.31   16.40 ± 0.93   4.48 ± 0.15
MuSiQue-Ans  MASPOB   31.49 ± 0.92   20.75 ± 0.76   4.53 ± 0.02
MuSiQue-Ans  GEPA   44.28 ± 1.19   30.85 ± 1.85   5.12 ± 0.07
MuSiQue-Ans  PACO   48.62 ± 2.57   34.25 ± 1.86   4.79 ± 0.17

With three branches feeding a shared receiver, PACO achieves the highest mean scores among the evaluated methods on five of the six HotpotQA quality metrics, including Joint F1/EM and Answer F1/EM. Its mean advantage over GEPA is 2.14 Joint F1 points on HotpotQA, with 7.52 and 4.34 Answer F1 points on DROP and MuSiQue-Ans, respectively. These results extend the empirical evidence from sequential handoffs to a parallel workflow with shared evidence and multiple incoming edges.

AuthorsOpenReview ↗

Response to Question 2

2. Repeated optimization for PACO versus Independent updates and GEPA

Concern (summary): The 0.93-point Table 3 advantage over Independent updates and the approximately two-point main advantage over GEPA come from single optimization runs, while some other comparisons use multiple runs. Matched optimization seeds, means, and variability are needed for these two key comparisons.

Response: (PART 1/2)

We have now repeated both comparisons using five independent optimization runs per optimized method, with optimizer seeds 0–4, including the original seed-0 run. Each run repeats optimization from the common initial workflow and then evaluates its resulting configuration. The model, workflow, data splits, and evaluation conditions are fixed within each comparison.

Paired-refinement ablation (Table 3; 5M-token budget). All four variants use the same 5M-token optimization budget. Independent updates can optimize the same sender instructions, receiver instructions, and shared convention as PACO, but changes only one behavioral component per refinement step while holding the other two fixed. PACO allows coordinated changes within an edge package. These restrictions apply to both ordinary and cooperative steps, with the remaining search procedure unchanged.

The table reports mean ± std over the five independent optimization-and-evaluation runs. Token costs are in millions (M).

Variant Joint F1 Answer F1Opt. tokens (M)
PACO 49.66 ± 0.95 59.33 ± 0.774.61 ± 0.05
Upstream only 47.16 ± 1.07 56.24 ± 0.894.67 ± 0.06
Downstream only 46.41 ± 1.21 55.92 ± 0.744.70 ± 0.08
Independent updates 48.58 ± 0.76 58.29 ± 0.634.85 ± 0.06

Across five independent optimization runs, PACO's mean scores are 1.08 points higher in Joint F1 and 1.04 points higher in Answer F1 than those of Independent updates. The revised Table 3 will report these results, which support a modest benefit from coordinated refinement under the same budget.

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

This paper proposes PACO, a framework for optimizing communication in multi-agent systems. Instead of optimizing individual agents independently, PACO jointly refines the sender instructions, receiver instructions, and shared conventions of each communication edge. It combines adaptive edge selection, two-round prompt refinement, and end-to-end feedback to improve collaboration. Experiments on HotpotQA, DROP, and MuSiQue demonstrate improvements over existing prompt optimization methods and some cross-dataset transferability.

Critical strengths
  1. Treating communication edges rather than individual agents as optimization units is an interesting approach to addressing information loss and misinterpretation in multi-agent collaboration.
  2. PACO combines paired prompt refinement, adaptive edge selection, and execution feedback into a coherent optimization process without modifying model parameters or workflow topology.
  3. PACO achieves competitive performance against strong prompt optimization baselines. The cross-dataset evaluations and ablation studies provide evidence for the effectiveness and transferability of the learned communication strategies.
Critical weaknesses
  1. Jointly optimizing both endpoints of a communication edge is the central contribution, but its improvement over independent updates is relatively small (49.35 vs. 48.42 Joint F1 in Table 3). More evidence is needed to establish whether this advantage is consistent and significant.
  2. The experiments are restricted to three text-based QA benchmarks and a fixed four-agent chain. Since this topology naturally creates information-passing bottlenecks, it remains unclear whether PACO is equally effective in more complex workflows involving parallel communication, branching, or shared contexts.
  3. Both the proposer and workflow agents use the same model family. The optimized communication strategies may reflect model-specific prompting preferences, and their effectiveness with heterogeneous agents remains unverified.
Questions for authors
  1. Given the small improvement over independent updates in Table 3, could the authors provide multi-seed evaluations to demonstrate that paired refinement consistently offers additional benefits under matched optimization budgets?
  2. Does PACO remain effective on more diverse tasks and communication structures, such as tool-use workflows, parallel agents, or branching graphs, beyond the evaluated four-agent QA chain?
  3. How sensitive is PACO to the choice of proposer and workflow models? Could the authors evaluate whether communication strategies optimized with one model family transfer to other models or heterogeneous agent teams?
6 comments
AuthorsOpenReview ↗

Response to Question 1

Thank you for reviewing our paper. We address your three concerns below.

1. Repeated optimization runs for paired refinement

Concern (summary): Table 3 reports only a small advantage over Independent updates (49.35 versus 48.42 Joint F1). Multi-seed comparisons under matched optimization budgets are needed to assess the reliability of the paired-refinement gain.

Response:

Paired-refinement ablation (Table 3; 5M-token budget).

We agree that the original single-run comparison did not adequately characterize run-to-run variability. We have added four independent optimization runs for every Table 3 variant, giving five runs per variant, including the original seed 0, under the same 5M-token optimization budget. Each run starts from the common unoptimized configuration, independently repeats optimization, and evaluates the resulting configuration using the same model, workflow, data splits, and HotpotQA evaluation protocol.

To clarify the comparison, both PACO and Independent updates permit optimization of the sender instructions, receiver instructions, and shared communication convention. Independent updates changes only one behavioral component per refinement step, holding the other two fixed; PACO permits coordinated changes to these components within an edge's communication package. The component restrictions apply throughout the refinement rounds and evaluation, including ordinary and cooperative steps. Upstream only and Downstream only restrict behavioral changes to the corresponding endpoint while fixing the opposite endpoint and shared convention.

The following table reports mean ± std over the five independent optimization-and-evaluation runs on HotpotQA, where std is the population standard deviation (denominator N = 5). Optimization token costs are expressed in millions (M).

Variant Joint F1 Answer F1Opt. tokens (M)
PACO 49.66 ± 0.95 59.33 ± 0.774.61 ± 0.05
Upstream only 47.16 ± 1.07 56.24 ± 0.894.67 ± 0.06
Downstream only 46.41 ± 1.21 55.92 ± 0.744.70 ± 0.08
Independent updates 48.58 ± 0.76 58.29 ± 0.634.85 ± 0.06

PACO exceeds Independent updates by 1.08 Joint F1 and 1.04 Answer F1 points, while consuming 0.24M fewer optimization tokens on average. Its mean Joint F1 is also 2.50 and 3.25 points higher than Upstream only and Downstream only, respectively. The average advantage over Independent updates remains when the comparison is extended to five independent optimization runs, without requiring more optimization tokens. The gain is modest, and we will replace the original single-run Table 3 summaries with these means and standard deviations.

Main comparisons (Tables 1 and 2; 25M-token optimization budget).

We also repeated the main comparisons in Tables 1 and 2 under the original 25M-token optimization budget for optimized methods. Each optimized method has five independent optimization-and-evaluation runs, including the original seed 0; Vanilla and PACT are each evaluated five times. Configurations optimized on HotpotQA are frozen before evaluation on DROP and MuSiQue-Ans, without target-specific optimization.

The following table includes representative methods from Tables 1 and 2 and reports Answer F1 / EM as mean ± std.

Method  HotpotQA   DROP   MuSiQue
  Answer F1Answer EM   Answer F1Answer EM   Answer F1Answer EM
Vanilla  43.01 ± 1.1631.05 ± 1.30   40.96 ± 0.9320.00 ± 0.91   30.00 ± 0.4220.80 ± 1.07
PACT  66.45 ± 1.1447.90 ± 0.82   47.34 ± 2.9629.05 ± 2.67   38.30 ± 0.8228.60 ± 0.97
MASPO  45.85 ± 0.8435.78 ± 1.21   16.09 ± 0.408.35 ± 0.72   23.59 ± 1.3317.85 ± 1.71
MASPOB  57.15 ± 2.0040.30 ± 1.54   40.62 ± 2.4619.25 ± 2.06   33.57 ± 1.6323.45 ± 1.29
GEPA  68.27 ± 0.9949.00 ± 1.05   48.06 ± 1.1920.75 ± 0.87   43.21 ± 2.3330.70 ± 1.59
PACO  70.62 ± 1.3552.85 ± 1.48   53.19 ± 2.0832.05 ± 2.88   46.14 ± 1.9735.20 ± 1.02

PACO retains higher mean Answer F1 and Answer EM than GEPA on all three datasets. Its Answer F1 gains are 2.35, 5.13, and 2.93 points on HotpotQA, DROP, and MuSiQue-Ans, respectively; the corresponding Answer EM gains are 3.85, 11.30, and 4.50 points. These main-comparison results complement the repeated Table 3 ablation by showing that PACO's average performance advantage also remains in the original main-budget setting.

AuthorsOpenReview ↗

Response to Question 2

2. Applicability beyond the original chain

Concern (summary): The experiments use three QA benchmarks and one four-agent chain, which naturally creates information-passing bottlenecks. Results on parallel, branching, shared-context, or tool-use workflows would help establish broader applicability.

Response:

We additionally evaluate a four-role hierarchical MAS inspired by MASPO. Three parallel agents—Answer Proposer, Evidence Scout, and Bridge Resolver—receive the same complete source evidence and send messages to an Answer Verifier, which receives their messages and the question without raw evidence. This setting includes parallel branches, shared evidence, and multiple incoming edges at a shared receiver. Detailed role definitions, initialization, communication constraints, and aggregation procedures are provided in our response to Reviewer 74Th (Weakness 2).

All workflow agents use gpt-5.6-luna with low reasoning effort. Configurations optimized on HotpotQA are frozen for evaluation on DROP and MuSiQue-Ans, without target-specific optimization.

For PACO, GEPA, MASPO, and MASPOB, each of the five runs independently repeats optimization and evaluation. Vanilla and PACT are each evaluated five times. The tables report mean ± std while token costs are expressed in millions (M).

HotpotQA: quality metrics and token costs.

Method     Joint F1    Joint EM   Answer F1   Answer EM  Support F1  Support EMDep. tokens (M)Opt. tokens (M)
Vanilla  48.05 ± 0.37  21.18 ± 0.45  54.86 ± 0.39  34.80 ± 0.66  69.52 ± 0.35  45.40 ± 0.346.34 ± 0.0030
PACT  46.74 ± 0.62  12.98 ± 0.36  57.97 ± 1.17  33.83 ± 0.60  72.25 ± 0.70  36.35 ± 0.766.73 ± 0.040
MASPO  46.46 ± 1.79  20.60 ± 0.95  53.37 ± 1.53  34.60 ± 0.53  67.89 ± 0.89  43.37 ± 0.436.34 ± 0.0224.36 ± 0.11
MASPOB  50.31 ± 2.13  22.98 ± 1.46  59.18 ± 2.42  39.17 ± 2.24  70.01 ± 1.24  45.03 ± 0.606.43 ± 0.0224.62 ± 0.08
GEPA  60.59 ± 1.18  28.88 ± 1.65  69.16 ± 1.24  46.83 ± 1.87  79.14 ± 0.22  52.88 ± 0.227.53 ± 0.1024.55 ± 0.31
PACO  62.73 ± 0.76  30.33 ± 0.87  72.43 ± 0.71  51.40 ± 0.82  79.42 ± 0.40  51.78 ± 0.916.90 ± 0.3224.37 ± 0.40

Frozen cross-dataset evaluation: answer metrics and deployment costs.

Dataset  Method   Answer F1   Answer EM   Dep. tokens (M)
DROP  Vanilla   30.03 ± 0.41   7.50 ± 0.57   1.36 ± 0.002
DROP  PACT   26.55 ± 0.49   6.35 ± 0.90   1.64 ± 0.05
DROP  MASPO   28.13 ± 2.48   6.45 ± 1.21   1.36 ± 0.12
DROP  MASPOB   36.08 ± 3.73   13.60 ± 3.17   1.41 ± 0.03
DROP  GEPA   40.57 ± 0.83   13.30 ± 0.58   1.91 ± 0.05
DROP  PACO   48.09 ± 1.32   20.00 ± 1.28   1.64 ± 0.15
MuSiQue-Ans  Vanilla   26.60 ± 0.45   15.35 ± 0.51   4.49 ± 0.002
MuSiQue-Ans  PACT   25.52 ± 1.20   11.55 ± 0.78   4.64 ± 0.06
MuSiQue-Ans  MASPO   26.24 ± 2.31   16.40 ± 0.93   4.48 ± 0.15
MuSiQue-Ans  MASPOB   31.49 ± 0.92   20.75 ± 0.76   4.53 ± 0.02
MuSiQue-Ans  GEPA   44.28 ± 1.19   30.85 ± 1.85   5.12 ± 0.07
MuSiQue-Ans  PACO   48.62 ± 2.57   34.25 ± 1.86   4.79 ± 0.17

In the hierarchical workflow, PACO achieves the highest mean scores among all evaluated methods on five of the six HotpotQA quality metrics, including Joint F1/EM and Answer F1/EM. Compared with GEPA, PACO improves Joint F1 by 2.14 points on HotpotQA and Answer F1 by 7.52 points on DROP and 4.34 points on MuSiQue-Ans. These results support PACO's effectiveness beyond the original chain, extending to a parallel workflow with shared evidence and a shared receiver.

Our task-level evaluation remains limited to QA, and we will make this scope explicit in the revised manuscript. We appreciate the reviewer's suggestion to broaden the task coverage and consider evaluation beyond QA an important direction for future work.

AuthorsOpenReview ↗

Response to Question 3

3. Cross-model transfer and dependence on model choice

Concern (summary): The proposer and workflow agents use the same model family, so the learned communication strategies may reflect model-specific prompting preferences. Can configurations optimized with one model transfer to other models or heterogeneous teams, and how sensitive is PACO to proposer and workflow model choice?

Response:

To examine whether the learned communication strategies are specific to the source model, we evaluate their transfer to three other workflow models, including a model from a different family.

Cross-model and cross-family transfer. We also freeze the PACO-optimized chain configuration learned using gpt-5.6-luna and replace all four agent models with a target model at once. The learned settings are used without target-model optimization or additional interface adaptation. Each frozen configuration is evaluated five times independently. The following tables report mean ± std while deployment token costs are expressed in millions (M).

GPT-4o.

DatasetConfigurationAnswer F1Answer EMDep. tokens (M)
HotpotQAVanilla6.35 ± 3.005.18 ± 2.233.25 ± 0.01
HotpotQAPACO23.13 ± 4.9616.80 ± 3.253.96 ± 0.23
DROPVanilla4.45 ± 2.483.45 ± 1.971.00 ± 0.01
DROPPACO13.46 ± 4.178.30 ± 3.581.36 ± 0.08
MuSiQue-AnsVanilla1.78 ± 1.921.50 ± 1.322.00 ± 0.01
MuSiQue-AnsPACO9.06 ± 3.967.30 ± 3.222.41 ± 0.10

GPT-6.1 Sol.

DatasetConfigurationAnswer F1Answer EMDeployment tokens (M)
HotpotQAVanilla73.82 ± 1.7353.55 ± 1.693.87 ± 0.03
HotpotQAPACO77.90 ± 1.0759.90 ± 1.234.55 ± 0.21
DROPVanilla42.71 ± 3.0120.55 ± 2.841.27 ± 0.02
DROPPACO55.91 ± 2.6635.20 ± 2.881.60 ± 0.09
MuSiQue-AnsVanilla48.36 ± 3.8934.70 ± 2.832.43 ± 0.02
MuSiQue-AnsPACO57.91 ± 4.4844.40 ± 3.422.77 ± 0.11

DeepSeek-V4.1-Flash-1017.

DatasetConfigurationAnswer F1Answer EMDeployment tokens (M)
HotpotQAVanilla42.78 ± 0.5928.35 ± 0.515.50 ± 0.01
HotpotQAPACO65.85 ± 4.0045.50 ± 4.716.01 ± 0.69
DROPVanilla15.98 ± 0.328.85 ± 0.601.93 ± 0.003
DROPPACO47.03 ± 6.8531.35 ± 5.782.20 ± 0.30
MuSiQue-AnsVanilla15.10 ± 1.8510.35 ± 1.633.21 ± 0.01
MuSiQue-AnsPACO40.59 ± 5.5130.00 ± 4.673.43 ± 0.32

These experiments hold the proposer fixed and vary the workflow model, providing evidence of cross-model and cross-family transfer. The frozen PACO configuration improves mean Answer F1 and Answer EM over the corresponding Vanilla workflow in all nine target-model–dataset combinations, without any target-specific optimization. GPT-6.1 Sol starts from the highest Vanilla scores and shows smaller relative gains in both metrics than GPT-4o and DeepSeek across all three datasets, consistent with more limited headroom for improvement. GPT-4o achieves substantial gains from a much weaker Vanilla baseline using the same frozen configuration. DeepSeek records the largest absolute gains in both metrics on every dataset, further supporting the transferability of the learned communication settings across model families.

In our experiments, we use gpt-4o-2024-11-20, GPT-6.1 Sol with low reasoning effort, and DeepSeek with reasoning disabled (even its low-effort setting frequently exhausted the configured output-token budget and caused response truncation).

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

This paper proposes Paired Automated Communication Optimization (PACO), a black-box prompt optimization framework for multi-agent systems with fixed model weights, roles, information access, and workflow topology. PACO treats each directed communication edge as an optimization unit, jointly revising sender instructions, receiver instructions, and their shared communication convention. Its search combines a candidate pool, configuration-specific discounted bandit scheduling, two-round refinement using execution feedback, staged end-to-end evaluation, and occasional cooperative updates. Experiments optimize a four-agent evidence-processing chain on 500 HotpotQA examples and evaluate frozen configurations on HotpotQA, DROP, and MuSiQue-Ans. PACO achieves 61.26 Joint F1 on HotpotQA, compared with 30.00 for the initial workflow and 59.27 for GEPA. Transfer gains over GEPA are 5.86 and 0.56 Answer F1 points on DROP and MuSiQue-Ans, respectively. Ablations and execution analyses provide preliminary evidence for coordinated communication refinement. The learned instructions require no additional deployment model calls, although token consumption increases relative to the initial workflow.

Critical strengths
  1. Jointly optimizing message construction and interpretation directly addresses dependencies that isolated agent improvements may overlook. The formulation provides a concrete, interpretable way to optimize handoffs while preserving the underlying workflow.

  2. PACO outperforms the strongest evaluated baseline, GEPA, on HotpotQA Joint F1 while using slightly fewer optimization tokens: 23.96M versus 24.20M. It leads on five of six reported HotpotQA quality metrics (Table 1).

  3. Frozen configurations improve performance on both transfer datasets, particularly DROP, where PACO exceeds GEPA by 5.86 Answer F1 points. This supports usefulness beyond the source benchmark’s specific questions (Table 2).

  4. The appendices disclose initial and learned instructions, data separation, baseline adaptations, failure handling, and matched-outcome analyses. These details help distinguish aggregate performance improvements from changes in reference preservation and output validity.

Critical weaknesses
  1. Main comparisons use one optimization seed, while provider generation seeds are unset. Confidence intervals and repeated main-budget runs are absent, making the approximately two-point HotpotQA and 0.56-point MuSiQue gains difficult to assess. Table 4 also compares a single PACO run with a three-run baseline average. Repeated optimization runs and paired uncertainty estimates are needed.

  2. All experiments use one model and one four-agent chain, with evidence access restricted to the first two agents. This design makes communication a particularly strong bottleneck. Results on branching workflows, larger teams, heterogeneous models, or tool-based tasks are needed to establish broader applicability (Section 4.1; Appendices C–D).

  3. Although the paper discusses MASPOB’s adjacent-agent block updates, its implementation explicitly disables them (Appendix G). Consequently, the experiments do not establish whether the advantage comes from edge-based parameterization or a more favorable joint-update mechanism. A comparison matching optimization budget, feedback, and proposal generation would strengthen the central contribution.

  4. Invalid predictions receive zero even when their answer text is correct. Table 13 attributes 0.96 of the reported 1.98-point HotpotQA advantage to the net contribution from examples valid under only one method. The remaining improvement is meaningful, but ungated answer metrics and direct evidence-use analyses would better distinguish reasoning improvements from formatting and validity effects.

Questions for authors

see weaknesses

12 comments

If the authors can address my questions during the discussion period, I would consider raising my score.

AuthorsOpenReview ↗

Additional Experiments and Clarifications

Thank you for your constructive feedback and your willingness to reconsider your assessment. Over the past few days, we have been conducting and checking a substantial set of additional experiments to address your concerns, which has delayed our response. We appreciate your patience and provide the results below.

Aggregated results are reported as mean ± std, where std denotes the population standard deviation (computed with denominator N). We distinguish independent optimization-and-evaluation runs from repeated evaluations of a frozen configuration. The separate seed-0 rescoring diagnostic reports individual-run scores rather than means and standard deviations. Token costs are expressed in millions (M).

AuthorsOpenReview ↗

Response to Weakness 1

1. Repeated optimization runs and variability

Concern (summary): The main results rely on a single optimization seed, and Table 4 compares unequal numbers of runs. Repeated optimizations and paired uncertainty estimates are needed to assess the reported gains.

Response:

We agree that the original single-run comparisons did not adequately characterize run-to-run variation. We have added four independent runs, giving five runs in total, including the originally reported optimizer seed 0. For methods requiring optimization, each run independently repeats optimization and then evaluates the resulting configuration; methods without optimization are evaluated five times. The optimized configurations are frozen before evaluation on DROP and MuSiQue-Ans.

The complete repeated-run results for all evaluated methods are as follows:

HotpotQA: quality metrics and token costs.

Method    Joint F1   Joint EM  Answer F1  Answer EM Support F1 Support EMDep. tokens (M)Opt. tokens (M)
Vanilla 31.34 ± 1.03 9.90 ± 0.95 43.01 ± 1.16 31.05 ± 1.30 39.98 ± 1.24 16.18 ± 0.523.91 ± 0.0040
Faithful Rewriter 29.28 ± 1.30 8.43 ± 0.53 41.52 ± 1.32 30.45 ± 0.66 37.67 ± 0.61 14.75 ± 0.506.81 ± 0.020
Task-Aware Rewriter 24.25 ± 1.72 7.48 ± 0.76 34.22 ± 1.45 25.02 ± 0.81 31.42 ± 0.67 12.17 ± 0.508.60 ± 0.010
LLMLingua-2 29.17 ± 1.09 8.33 ± 0.45 41.18 ± 0.72 29.40 ± 0.59 37.88 ± 0.72 13.80 ± 0.523.90 ± 0.010.46
OPTiMACS 26.24 ± 2.60 7.95 ± 1.13 36.29 ± 1.66 26.10 ± 1.19 32.52 ± 2.38 13.33 ± 1.378.61 ± 0.0219.1 ± 0.01
PACT 47.10 ± 1.04 11.73 ± 0.45 66.45 ± 1.14 47.90 ± 0.82 59.12 ± 1.18 21.22 ± 0.984.11 ± 0.010
MASPO 37.07 ± 1.53 16.38 ± 1.33 45.85 ± 0.84 35.78 ± 1.21 45.53 ± 0.32 25.28 ± 0.707.55 ± 0.3024.61 ± 0.30
MASPOB 45.61 ± 1.88 16.50 ± 1.28 57.15 ± 2.00 40.30 ± 1.54 59.32 ± 1.71 30.10 ± 1.304.17 ± 0.0524.65 ± 0.22
GEPA 57.97 ± 1.73 26.35 ± 1.07 68.27 ± 0.99 49.00 ± 1.05 73.52 ± 1.49 45.18 ± 0.974.89 ± 0.4024.23 ± 0.12
PACO 59.96 ± 1.37 28.25 ± 0.49 70.62 ± 1.35 52.85 ± 1.48 74.65 ± 1.05 45.30 ± 0.424.84 ± 0.3424.16 ± 0.24

Frozen cross-dataset evaluation: answer metrics and deployment costs.

DatasetMethod Answer F1 Answer EM Dep. tokens (M)
DROPVanilla 40.96 ± 0.93 20.00 ± 0.911.28 ± 0.003
DROPPACT 47.34 ± 2.96 29.05 ± 2.671.49 ± 0.02
DROPMASPO 16.09 ± 0.40 8.35 ± 0.722.92 ± 0.15
DROPMASPOB 40.62 ± 2.46 19.25 ± 2.061.40 ± 0.06
DROPGEPA 48.06 ± 1.19 20.75 ± 0.871.73 ± 0.19
DROPPACO 53.19 ± 2.08 32.05 ± 2.881.72 ± 0.15
MuSiQue-AnsVanilla 30.00 ± 0.42 20.80 ± 1.072.43 ± 0.002
MuSiQue-AnsPACT 38.30 ± 0.82 28.60 ± 0.972.53 ± 0.01
MuSiQue-AnsMASPO 23.59 ± 1.33 17.85 ± 1.714.14 ± 0.11
MuSiQue-AnsMASPOB 33.57 ± 1.63 23.45 ± 1.292.56 ± 0.04
MuSiQue-AnsGEPA 43.21 ± 2.33 30.70 ± 1.592.94 ± 0.21
MuSiQue-AnsPACO 46.14 ± 1.97 35.20 ± 1.022.97 ± 0.14

PACO exceeds GEPA by 1.99 points on HotpotQA Joint F1, 5.13 points on DROP Answer F1, and 2.93 points on MuSiQue-Ans Answer F1. Its Answer EM gains are 3.85, 11.30, and 4.50 points on HotpotQA, DROP, and MuSiQue-Ans, respectively. PACO's higher mean performance is retained across the repeated experiments at comparable optimization cost.

We also repeated the Table 4 HotpotQA comparisons so that all three variants now have five independent optimization runs under the same 5M-token budget, replacing the original comparison with unequal numbers of runs:

VariantJoint F1Answer F1Opt. tokens (M)
PACO49.66 ± 0.9559.33 ± 0.774.61 ± 0.05
Uniform edge selection42.79 ± 4.1853.29 ± 3.784.64 ± 0.04
Single-round refinement48.74 ± 1.0158.95 ± 0.894.56 ± 0.04

The mean Joint F1 advantage is 6.87 points over uniform edge selection and 0.92 points over single-round refinement. We will replace the original single-run summaries with these repeated-run statistics and describe the latter improvement as modest.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Summary

Rebuttal Summary

Dear AC, SAC, and Reviewers,

Thank you for overseeing the review. We conducted additional experiments to address all main questions raised by the reviewers.

  • Repeated optimization for the whole methods and paired refinement. Across five matched optimization seeds, under the 25M-token budget, PACO exceeded GEPA by 1.99 Joint F1 points on HotpotQA, 5.13 Answer F1 points on DROP, and 2.93 Answer F1 points on MuSiQue-Ans on average. Under the 5M-token budget, PACO's paired refinement exceeded independent updates by 1.08 HotpotQA Joint F1 points on average.

  • Branching workflows and model transfer. With a hierarchical MAS setup, PACO exceeded GEPA by 2.14 Joint F1 points on HotpotQA, 7.52 Answer F1 points on DROP, and 4.34 Answer F1 points on MuSiQue-Ans on average. Without any target-specific optimization, the frozen PACO configuration achieved higher mean scores than each target model's Vanilla workflow across all nine model–dataset combinations. These results support the transferability of PACO's learned communication settings across models and model families.

  • Additional comparisons and evidence use. PACO also significantly outperformed the requested MASPOB block-size-2 baseline on all three datasets. After removing citation and format validity gates, PACO retained higher Answer F1 and EM than GEPA across both workflows and all three datasets in the seed-0 evaluation. The analysis of supporting sentence's effect was also provided.

Reviewers 74Th and GNva now rate the paper Weak Accept. We also completed all evaluations F8Mm prioritized: (1) the branching workflow with a shared receiver and (2) the multiple-seed comparisons. In the revised paper, we will report the five-run results, add the additional comparisons, and make clear both paired-refinement gain and the current scope of the evaluation.

Thank you once again for your time and consideration.

Sincerely,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.