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

Feng Lin; Xiaotian Yu; Yifan Yang; Aijun Li

cs.CLOct 13, 2026

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

Authors: Feng Lin, Xiaotian Yu, Yifan Yang, Aijun Li

Organizations: Intellifusion Inc.

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.

Figures & tables

Figure 1: Overview of PACO. (a) Task context can be omitted during handoff or misused downstream. (b) PACO jointly optimizes upstream and downstream instructions together with their shared communication convention. (c) An automated loop selects edges, refines paired instructions, evaluates candidates, and commits accepted revisions.

	Joint $\uparrow$		Answer $\uparrow$		Support $\uparrow$		Tokens (M)
Method	F1	EM	F1	EM	F1	EM	Opt.	Deploy.
Vanilla	30.00	8.88	41.64	29.63	38.68	15.75	0.00	3.91
Faithful Rewriter	29.36	8.25	41.16	30.63	37.95	14.75	0.00	6.84 (+75%)
Task-Aware Rewriter	24.35	7.00	33.82	25.00	30.92	11.38	0.00	8.60 (+120%)
LLMLingua-2 ( Pan et al., 2024 )	29.36	8.50	41.15	29.50	37.74	13.88	0.46	3.90 ( $-0.2$ %)
OPTiMACS ( Gupta et al., 2026 )	24.37	6.88	34.18	24.50	31.35	12.00	19.10	8.63 (+121%)

Table 1: HotpotQA performance and cost. Scores are percentages; parentheses show deployment-token changes relative to vanilla. Methods are grouped by optimization approach. Support denotes supporting-fact evaluation. Bold and underlined values mark the best and second-best scores.

	DROP			MuSiQue-Ans
Method	F1 $\uparrow$	EM $\uparrow$	Deploy.	F1 $\uparrow$	EM $\uparrow$	Deploy.
Vanilla	42.25	21.50	1.28	29.60	21.25	2.43
PACT ( Huang et al., 2026 )	45.46	27.25	1.47 (+15%)	37.94	28.50	2.52 (+4%)
MASPO ( Wang et al., 2026 )	15.70	9.50	2.84 (+122%)	25.12	19.50	4.08 (+68%)
MASPOB ( Hong et al., 2026 )	42.80	20.50	1.38 (+8%)	32.83	22.75	2.54 (+5%)
GEPA ( Agrawal et al., 2026 )	49.09	21.00	1.92 (+50%)	44.50	31.00	3.12 (+28%)

Table 2: Transfer without further optimization. HotpotQA configurations are frozen for transfer. F1/EM measure answer quality; units and highlighting follow Table 1 .

Table 4

Question: To what team was the 2014 NBA Rookie of the Year traded in October 2016?
Resolver’s local evidence: Michael Carter-Williams was named NBA Rookie of the Year in 2014.
	Vanilla	PACO
Scout handoff	“The Chicago Bulls traded Tony Snell to the Milwaukee Bucks for Michael Carter-Williams on October 17, 2016.”	“Tony Snell $\rightarrow$ Milwaukee Bucks; Michael Carter-Williams $\rightarrow$ Chicago Bulls”
Resolver output	“the incoming claim states he was traded to the Milwaukee Bucks in October 2016.”	“therefore, Carter-Williams was traded to Chicago”
Final answer	Milwaukee Bucks	Chicago Bulls
Answer / Joint F1	0 / 0	100 / 80

Table 5: Making transaction direction explicit. Selected message excerpts; surrounding text is omitted. Both final predictions are valid. F1 scores are percentages.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	Value
Workflow / proposer model	gpt-5.6-luna / gpt-5.6-luna
Workflow / proposer reasoning effort	Low / high
Proposer maximum output tokens	16,384
Optimizer seed	0
Search / internal validation examples	400 / 100
Pilot / promotion examples per step	4 / 8

Appendix

Table 6: PACO optimization settings. Thresholds use scores in

[0,1]

. Settings describe the main 25M-token run; ablations use a 5M-token budget.

Dataset	Subset	Examples
HotpotQA	Search	400
HotpotQA	Internal validation $H$	100
HotpotQA	Evaluation	800
DROP	Transfer evaluation	400
MuSiQue-Ans	Transfer evaluation	400

Appendix

Table 7: Data allocation. The HotpotQA search subset and internal validation set

H

together form the 500-example optimization pool. DROP and MuSiQue-Ans are used only for transfer evaluation.

Agent	Available evidence and messages	Cap
Scout	Own evidence shard	768
Resolver	Own shard; Scout message	768
Integrator	Resolver message	640
Verifier	Integrator message	384

Appendix

Table 8: Fixed workflow configuration. All agents additionally receive the question. Caps are maximum output tokens per agent call.

	Parent	Revised edge
Sender	Select locally supported information; preserve evidence and uncertainty.	Organize candidates by required relations; attach exact support and local/inherited provenance.
Receiver	Retain useful supported information and respect uncertainty.	Check each essential relation; preserve support from an explicitly inherited claim.
Shared rule	Suggested fields include claims, references, an answer hypothesis, and uncertainty.	Distinguish local and inherited support; an inherited fact needs no duplicate local citation.
Actual $e_{2}$ fields	supporting_facts : local (Sitcom S, 0) . upstream_claim : (Actor A, 2) .	required_constraints : actor–sitcom and sitcom–network links. matched_evidence : (Sitcom S, 0) ( local ); (Actor A, 2) ( inherited ).
Forwarded refs.	(Sitcom S, 0) only.	(Sitcom S, 0) and (Actor A, 2) .
Final outcome	Answer: Network N; valid. Joint F1: 66.67.	Answer: Network N; valid. Joint F1: 100.00.

Appendix

Table 9: A real paired revision at Resolver

\rightarrow

Integrator. Rule rows summarize the saved instructions; message rows project actual fields. Names are aliases, sentence indices are unchanged, and omitted fields are not reconstructed. Scores are from the original training pilot.

Method	Adaptation
Vanilla	Initial endpoint instructions and conventions in Appendix D ; no optimization.
Faithful Rewriter	LLM-based message rewriting with general evidence-preservation guidance and receiver context.
Task-Aware Rewriter	LLM-based rewriting with task-specific guidance and information about the communicating roles.
LLMLingua-2	The released compression model is applied as message-processing middleware with rate=0.9 .
OPTiMACS	Task-dependent representation search, using Joint F1 as the optimization objective in this workflow.
PACT	A fixed action-state communication protocol adapted to the four-role chain, without prompt search.

Appendix

Table 10: Implementation scope of the evaluated baselines.

Method	Edge	Refs.	Rate (%)	Z	Refs.	Rate (%)	Z
		Sending: $\|A\cap M\|/\|A\|$			Continuation: $\|M\cap O\|/\|M\|$
Vanilla	e1	794/991	80.1	0	294/794	37.0	74
Vanilla	e2	1085/1743	62.2	0	1028/1090	94.3	51
Vanilla	e3	1028/1090	94.3	51	696/1058	65.8	63
PACO	e1	645/991	65.1	0	521/645	80.8	232
PACO	e2	1168/1594	73.3	0	1208/1269	95.2	65

Appendix

Table 11: Recognized gold-reference retention on all 800 matched questions per system. Counts are references, and Z counts tasks with a zero denominator. All 800 saved input/output stages are available for every edge.

Method	Stratum	Tasks	$e_{1}$	$e_{2}$	$e_{3}$
Vanilla	Answer EM $=1$	237	124/250 (49.6)	370/376 (98.4)	371/380 (97.6)
Vanilla	Answer EM $<1$	563	170/544 (31.2)	658/714 (92.2)	325/678 (47.9)
Vanilla	Joint EM $=1$	71	68/74 (91.9)	145/145 (100.0)	153/153 (100.0)
Vanilla	Joint EM $<1$	729	226/720 (31.4)	883/945 (93.4)	543/905 (60.0)
PACO	Answer EM $=1$	438	294/355 (82.8)	680/705 (96.5)	854/854 (100.0)
PACO	Answer EM $<1$	362	227/290 (78.3)	528/564 (93.6)	551/646 (85.3)

Appendix

Table 12: Continuation by outcome stratum, with reference counts and percentage in parentheses. Strata are defined separately by answer EM and Joint EM; invalid final predictions belong to each EM

<1

group.

Dataset	Both valid	PACO only	GEPA only	$\Delta_{B}$	$\Delta_{O,G}$	Total
HotpotQA	678	54	36	+1.02	+0.96	+1.98
DROP	340	14	31	+7.98	-2.12	+5.86
MuSiQue-Ans	181	59	58	+1.33	-0.77	+0.56

Appendix

Table 13: Matched outcomes for PACO and GEPA. Counts partition examples by final validity; score contributions use the full dataset denominator. HotpotQA uses Joint F1, and the targets use answer F1. Contributions are percentage points.

Figure 2: Observed PACO search trajectory. Left: complete internal-validation evaluations and the best-so-far score against optimization tokens. Right: the selected ancestry in generation order. Scores use the optimization-time evaluator.

Multi-Agent Communication

Multi-agent communication studies how autonomous agents exchange information to coordinate decisions, share knowledge, and act together under constraints.

See all 375 papers

CEPO: A General Framework for Improving Prompt Optimization in Multi-Agent Systems
Oct 26, 2026Jongha Kim, Seohyun Lee, Jonathan Minho Chung +2Prompt Optimization Multi-Agent System Optimization
Korea University · KAIST · Google Cloud AI Research
Not Every Agent Needs the Strongest Model: Unified Prompt-Model Optimization for Heterogeneous LLM-based Multi-Agent Systems
Oct 22, 2026Mingxiu Cai, Haoyang Xian, Xinyu Ma +4Multi-Agent LLM Systems Multi-Agent System Optimization
Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen
MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems?
Jun 22, 2026Juyang Bai, Laixi ShiMulti-Agent LLM Systems Multi-Agent System Optimization
Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD 21218, USA.

Oct 26, 2026J/K move · Enter open · S save

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

Jongha Kim, Seohyun Lee, Jonathan Minho Chung, Jinsung Yoon+1

Korea University · KAIST · Google Cloud AI Research

Prompt Optimization Multi-Agent System Optimization Multi-Agent Coordination

Open paper AskPDF arXiv

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.

Abstract

Multi-Agent Communication

Explore similar work

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

Not Every Agent Needs the Strongest Model: Unified Prompt-Model Optimization for Heterogeneous LLM-based Multi-Agent Systems

MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems?