Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Hanmin Li; Yury Demidovich; Peter Richtárik

cs.MAOct 21, 2026

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Authors: Hanmin Li, Yury Demidovich, Peter Richtárik

Organizations: King Abdullah University of Science and Technology Thuwal, Saudi Arabia

Abstract

Parallel AI agents can produce useful local edits yet degrade a shared solution when their edits are combined. We model this coordination problem as discrete block optimization with an exactly evaluable objective and a known dependency graph. Independent sets certify compatible edits whose verified gains, measured against the same current solution, add exactly. A coordinator constructs a safe compatible candidate and can also evaluate interacting edits to capture favorable interactions. We prove that an optimal fractional coloring yields a merger that preserves a $1/χ_f(G)$ fraction of the total verified local improvement, where $χ_f(G)$ is the graph's fractional chromatic number. This guarantee is tight among mergers that select a subset of the same proposals. Under conditional local-improvement guarantees and a block error-bound condition, repeated collaboration converges geometrically in the objective gap. The rate separates task structure, agent allocation, and computation cost, yielding a linear program for agent assignment and an explicit time-cost trade-off. Code-repair experiments show that verified merging resolves conflicts between individually useful edits that cause naive merging to fail. On larger conflict-free tasks, parallel agents reduce modeled completion time at higher input-token-equivalent cost. On three public road networks, fractional integration retains 922 units of verified graph-cut improvement across 90 paired runs. For route-search agents sharing exclusive access to vehicle routes, fractional scheduling reduces measured wall time by a median of 15% across twelve paired runs, with route-cost changes varying across runs.

Figures & tables

Panel of Figure 1 — Figure 1. Verified integration of parallel edits. In the running example, three individually improving edits give a gain of only one when merged together. The compatible pricing–receipt pair gains three and reaches the optimum. Three agents propose edits to pricing, checkout, and receipt, with individual gains two, two, and one. The dependency graph connects pricing and checkout. The compatible pricing and receipt pair gains three, compared with one for the full union, and is selected.

Panel of Figure 2 — Figure 2. Dependency graph induced by the objective in ( 3 ). The discount term depends jointly on pricing and checkout, while the receipt term depends only on the receipt block. Thus pricing and the receipt can share a color, whereas checkout must receive a different color. Three agents propose edits to pricing, checkout, and receipt blocks. Pricing and checkout are adjacent in the dependency graph, while the receipt is independent of both.

By model
	SGL	SEQ	MA	MAG	COL	OPT
Haiku	21/21	19/21	12/21	13/21	21/21	21/21
Sonnet	7/7	7/7	5/7	5/7	7/7	7/7
By first-round conflict
Conflict	11/11	11/11	0/11	1/11	11/11	11/11
No conflict	17/17	15/17	17/17	17/17	17/17	17/17

Table 1. Success rates on the repair benchmark. The upper panel groups runs by model. The lower groups the same runs by whether the two adjacent proposals conflict in the first round. Each entry reports successful runs over total runs.

	Completion time, $t_{\mathrm{ver}}=0$ (min)		SGL / OPT speedup			OPT / SGL
$m$	SGL	OPT	$t_{\mathrm{ver}}=0$	$60$	$300$	Input cost
4	2.4	3.5	0.68	0.67	0.67	2.23
8	4.2	2.9	1.43	1.04	0.79	2.23
16	9.2	4.5	2.05	1.43	0.91	1.94
32	15.3	4.1	3.69	2.42	1.32	2.02

Table 2. Scaling results as the number of modules

m

increases. Entries are geometric means over three instances at each size. Input cost excludes output tokens and verification charges.

Figure 3. Retained gain and union interactions on the twelve

C_{5}

units, normalized by the sum

S

of positive verified singleton gains. (a) Paired gains for ordinary ( COL3 ) and fractional ( FRAC5 ) coloring; lines join identical proposal sets. Dashed segments mark the guarantees

1/3

and

2/5

. (b) Directly evaluated full-union gain; the dashed line at

1

is the additive baseline. C5-only two-panel diagnostic. The left panel connects ordinary and fractional retained gains for each of twelve paired proposal sets. The right panel shows full-union gains normalized by positive singleton gains.

Figure 4. Remaining failed-check fractions on sixteen held-out interface-migration designs after up to three rounds. Each point is the mean final loss over three replicates divided by the initial loss. Circles denote

C_{5}

and squares denote prism graphs; numerals identify coincident points. Points below the diagonal favor FOPT over MA . Paired scatterplot of normalized final failed-check counts. All sixteen design points lie below the diagonal of equal loss, indicating fewer remaining failures for FOPT than for merge-all.

Network	COL	FRAC	MAG	MA
Pennsylvania	283	343	68	14
California	278	305	114	87
Texas	238	274	60	28
Total	799	922	242	129

Table 3. Held-out road-network proposal integration: sums of graph-cut edges removed over 30 paired region–seed units per network. Larger is better. COL uses one ordinary coloring fixed before proposals; FRAC considers the five supported

C_{5}

independent pairs.

Method	Penalty reduction	Feasible
Fixed COL	150	$9/9$
FRAC	165	$9/9$
MA	—	$8/9$

Table 4. Penalty reductions and feasible outcomes on nine ITC-2007 instances. Higher reduction is better. The MA total is omitted because one timetable is infeasible.

Public CVRP instance	Faster pairs	Median wall reduction
Loggi-n401-k23	$3/3$	$14.74\%$
Loggi-n501-k24	$3/3$	$15.27\%$
ORTEC-n242-k12	$3/3$	$13.52\%$
ORTEC-n323-k21	$3/3$	$15.76\%$
All pairs	$12/12$	$15.00\%$

Table 5. Wall-time reduction under fractional route-search scheduling. Each instance has three paired repeats. “Faster pairs” counts runs in which the fractional schedule is faster than the ordinary schedule. The final column gives the median paired reduction.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Modules (blocks)	Ambiguous interface	Edge	Lines	Checks	$F(x^{0})$	Double
T1 invoice	parsing, pricing, checkout	coupon discount	pricing–checkout	44	25/10	21	5
T2 profiles	users, cards, pages	HTML escaping	users–cards	24	18/8	19	4
T3 calendar	timeparse, planner, agenda	UTC offset	timeparse–planner	49	23/10	26	5
T4 CSV export	records, csvrow, exporter	CSV quoting	records–csvrow	20	19/9	24	6
T5 blog URLs	slugs, urls, sitemap	percent-encoding	slugs–urls	23	18/9	25	5
T6 logging	events, formatter, sink	log escaping	formatter–sink	26	20/8	26	6

Appendix

Table 6. Tasks in the three-module repair benchmark. Each task has a path dependency graph. “Lines” counts faulty editable code; “Checks” gives visible/hidden check counts; and

F(x^{0})

is the initial number of failures. “Double” counts the integration failures caused by applying the interface transformation in both adjacent modules when all other code is correct.

	SGL	SEQ	MA	MAG	COL	OPT
Solved, Haiku (21)	21	19	12	13	21	21
Solved, Sonnet (7)	7	7	5	5	7	7
Conflict units (11)	11	11	0	1	11	11
Other units (17)	17	15	17	17	17	17
Agent calls	1.14	3.14	4.71	4.71	3.86	3.86
Evaluations	2.14	4.00	2.86	2.86	5.76	6.19

Appendix

Table 7. Success and resource use across the six repair protocols. The first four rows count solved task–replicate units; the conflict and other-unit rows pool both models. Resource-use rows are means over all 21 Haiku units. The final two rows give median cost among successful Haiku runs, in median-call-equivalent units, with each objective evaluation charged at

v

. Input costs exclude output tokens; “k” denotes thousands of input-token equivalents. Haiku denotes claude-haiku-4-5 . Sonnet denotes claude-sonnet-5 .

	Haiku							Sonnet
Task	Conf.	SGL	SEQ	MA	MAG	COL	OPT	Conf.	SGL	SEQ	MA	MAG	COL	OPT
T1	3	3	3	0	0	3	3	0	1	1	1	1	1	1
T2	0	3	2	3	3	3	3	1	1	1	0	0	1	1
T3	2	3	3	1	1	3	3	0	1	1	1	1	1	1
T4	0	3	3	3	3	3	3	0	1	1	1	1	1	1
T5	1	3	3	2	3	3	3	0	1	1	1	1	1	1

Appendix

Table 8. Solved runs and first-round edit conflicts for each repair task. Protocol columns count successful runs out of three replicates for Haiku and one for Sonnet. “Conf.” counts runs with a genuine conflict between adjacent proposals, as defined in the conflict diagnostic. C0 has no ambiguous interface. Haiku denotes claude-haiku-4-5 . Sonnet denotes claude-sonnet-5 .

	Haiku (of 21)						Sonnet (of 7)
Budget	SGL	SEQ	MA	MAG	COL	OPT	SGL	SEQ	MA	MAG	COL	OPT
3 calls, $v=0$	21	8	3	3	3	3	7	5	3	3	3	3
3 calls, $v=1$	9	0	0	0	0	0	3	0	0	0	0	0
6 calls, $v=\nicefrac{{1}}{{4}}$	21	19	12	12	12	12	7	7	5	5	5	5
9 calls, $v=1$	21	19	12	12	8	8	7	7	5	5	4	4
5 min, $t_{\mathrm{ver}}=60$ s	18	0	11	11	3	3	7	0	5	5	5	5

Appendix

Table 9. Runs solved within fixed cost or time budgets, out of 21 Haiku runs and seven Sonnet runs. “Calls” denotes median-call-equivalent input cost, with an additional charge of

v

per objective evaluation, rather than a limit on the number of calls. Time budgets include

t_{\mathrm{ver}}

for each sequential verification step. All runs contribute to the denominators. Haiku denotes claude-haiku-4-5 . Sonnet denotes claude-sonnet-5 .

Figure 5. Fraction of the 21 Haiku runs solved as the available budget increases. (a) Input cost, measured in median-call equivalents and excluding output tokens, with one additional unit per objective evaluation (

v=1

). (b) Modeled completion time, combining the measured agent critical path with 60 seconds per sequential verification step. Unsuccessful runs remain in the denominator. Figure 6 varies the verification charges. Haiku denotes claude-haiku-4-5 . Success rates of the six repair protocols as the input-token-equivalent and modeled completion-time budgets increase.

Figure 6. Effect of verification charges on the fraction of Haiku runs solved within a budget. The top row varies the price of one objective evaluation over

v=0,\nicefrac{{1}}{{4}},1

median-call equivalents. The bottom row varies sequential verification latency over

t_{\mathrm{ver}}=0,60,300

seconds. Every curve uses all 21 runs, including failures; input costs exclude output tokens. Haiku denotes claude-haiku-4-5 . Success-rate curves for six repair protocols under three token-accounting prices and three verification-time assumptions.

	SGL	SEQ	MA	MAG	COL	OPT
Solved	7	7	5	5	7	7
Agent calls	1.00	3.14	4.14	4.14	3.57	3.57
Evaluations	2.00	4.14	2.57	2.57	5.57	5.86
Input eq. (k)	78	216	312	323	277	279
Modeled time (s), $t_{\mathrm{ver}}=0$	38	99	69	74	73	65
Cost to solve, $v=0$	1.05	2.82	2.89	2.89	3.14	3.14

Appendix

Table 10. Success and resource use in the seven-run Sonnet replication. “Solved” counts successful runs. Agent calls, objective evaluations, input-token equivalents (thousands), and modeled time are means over all seven runs. The final two rows report median cost among successful runs, in median-call-equivalent units, charging

v

per objective evaluation as in Table 7 . Sonnet denotes claude-sonnet-5 .

Task and replicates	MA	MAG	COL	OPT
T1, replicates 1–3	21, 5, 5, 5	21, 5, 5, 5	21, 6, 5, 0	21, 5, 0
T3, replicates 2–3	26, 5, 6, 5	26, 5, 5, 5	26, 4, 4, 0	26, 4, 4, 0
T5, replicate 3	25, 5, 5, 5	25, 5, 5, 0	25, 14, 5, 0	25, 5, 0
T6, replicates 1–3	26, 6, 6, 6	26, 6, 6, 6	26, 14, 5, 0	26, 6, 0

Appendix

Table 11. Failing checks after successive merges on the nine Haiku runs with edit conflicts. Each sequence begins with the initial loss

F(x^{0})

and ends at success or the round cap. Runs grouped in the same row have identical trajectories. Haiku denotes claude-haiku-4-5 .

Instances	Clusters	$m$	Bugs	Checks (visible/hidden)	$F(x^{0})$
S4a, S4b, S4c	A; C; D	4	20	36/36, 37/37, 36/36	47, 45, 48
S8a, S8b, S8c	A+B; C+D; B+D	8	40	72/72, 73/73, 72/72	87, 105, 95
S16a, S16b, S16c	A–D	16	80	145/145	206, 190, 182
L32a, L32b, L32c	A–H	32	160	289/289	386, 383, 363

Appendix

Table 12. Size and composition of the twelve scaling tasks. Each size

m

has three instances with different bug seeds and five bugs per module. Clusters A–H cover commerce, logistics, scheduling, analytics, inventory, geometry, identifiers, and text analytics; each contains two base and two composite modules. Instance names encode the number of modules; suffixes a–c distinguish the three instances at each size. Multiple entries in a cell follow the listed instance order.

F(x^{0})

counts initially failing checks.

	Minutes, $t_{\mathrm{ver}}=0$					Minutes, $t_{\mathrm{ver}}=60$ s					Input equivalents (M)
$m$	SGL	SEQ	MA	COL	OPT	SGL	SEQ	MA	COL	OPT	SGL	SEQ	OPT
4	2.4	4.8	3.5	3.5	3.5	4.4	9.9	5.6	6.6	6.6	0.25	0.47	0.56
8	4.2	8.6	2.9	2.9	2.9	6.2	17.6	5.0	6.0	6.0	0.49	0.86	1.09
16	9.2	19.3	4.5	4.5	4.5	11.2	36.3	6.8	7.8	7.8	1.19	1.80	2.30
32	15.3	—	4.1	4.1	4.1	17.3	—	6.1	7.1	7.1	2.08	—	4.22

Appendix

Table 13. Time and input cost to solve tasks with

m

modules, averaged geometrically over three instances at each size. The first two column groups give modeled minutes at verification latencies of 0 and 60 seconds per sequential step. The final group gives millions of input-token equivalents, excluding output tokens and verification charges (

v=0

). MAG matches MA ; at zero verification latency, COL matches OPT because its extra verification step needs no agent call. Dashes mark the omitted 32-module SEQ runs.

Figure 7. Time and input cost to solve increasingly large repair tasks. Panels (a) and (b) show modeled completion time with 0 and 60 seconds per sequential verification step, respectively; panel (c) shows input-token equivalents, excluding output tokens. Lines connect geometric means over three instances per size, and dots show the individual instances. In panel (a), MA , COL , and OPT have equal modeled times. Modeled completion time and input-token-equivalent cost of the repair protocols as the number of modules increases.

Figure 8. Fraction of initially failing checks repaired over time for tasks with (a) 16 and (b) 32 modules. Single-agent curves evaluate workspace snapshots taken every five seconds on visible and hidden checks. Team curves model simultaneous first-round starts and immediate merging as each call finishes, with no verification delay. Each curve represents one instance; the team curves provide an optimistic merge-on-finish reference for comparison with the single-agent runs. Anytime repair trajectories for a single agent and a parallel team on tasks with 16 and 32 modules.

$m$	50%	90%	100%
4	0.79	0.53	0.57
8	1.38	1.26	1.32
16	2.13	2.26	—
32	4.06	4.61	3.61

Appendix

Table 14. Relative time to reach 50%, 90%, and 100% repair under the merge-on-finish model. Entries are geometric means over three instances of single-agent time divided by modeled team time; values above one favor the team. Repair fractions refer to initially failing checks. The completion ratio at

m=16

is omitted because one first-round union left failures.

	$m=16$		$m=32$
Added test cost	$t_{\mathrm{ver}}=0$	$t_{\mathrm{ver}}=60$ s	$t_{\mathrm{ver}}=0$	$t_{\mathrm{ver}}=60$ s
None	2.09	1.44	3.73	2.42
0.1 s per check	2.26	1.55	4.24	2.73
0.5 s per check	2.91	1.95	5.86	3.79
1 s per check	3.60	2.42	7.41	4.92
10 s per invocation	1.86	1.37	3.35	2.33

Appendix

Table 15. Projected speedup of OPT over SGL when tests take longer. Entries are geometric means of single-agent time divided by team time, adding the stated latency per visible check or test-runner invocation while holding recorded agent behavior fixed. Columns vary task size and verification latency. The “None” row removes measured test time, explaining the small difference from Table 2 .

Method	Overall	$C_{5}$	Prism
Initial	34.38	19.50	49.25
SGL	12.27	5.92	18.63
SGL-MF ( $\leq 2\times$ )	20.52	6.25	34.79
MA	20.02	10.25	29.79
MAG	19.58	10.25	28.92
COL	6.19	2.50	9.88

Appendix

Table 16. Mean final failed-check counts on the held-out interface-migration benchmark. Results average over 48 task–replicate units overall and 24 per graph family; lower is better. Parallel rules run for at most three rounds. The multi-file control has a token cap of twice the corresponding FOPT run.

Repository	Base F2P	Final F2P	Final P2P
HTTPie	$0/12$	$12/12$	$2/2$
TheFuck	$2/4$	$4/4$	$2/2$

Appendix

Table 17. Selected public-test outcomes on the real-repository check. Final counts hold separately for all three repeats of each repository in both the module-restricted and global conditions. F2P and P2P denote fail-to-pass and pass-to-pass tests.

Route-cost differences by repeat:
Input	Repeat 1	Repeat 2	Repeat 3	Median reduction
Loggi-n401-k23	$7.472\to 6.370$	$7.462\to 6.366$	$7.542\to 6.322$	$14.74\%$
Loggi-n501-k24	$8.605\to 7.249$	$8.395\to 7.289$	$8.493\to 7.196$	$15.27\%$
ORTEC-n242-k12	$7.909\to 6.543$	$7.670\to 6.633$	$7.555\to 6.561$	$13.52\%$
ORTEC-n323-k21	$6.888\to 5.894$	$6.944\to 5.850$	$7.058\to 5.916$	$15.76\%$
Loggi-n401-k23: $+56,0,0$ ; Loggi-n501-k24: $-96,-210,-1$ .

Appendix

Table 18. Wall-time reduction under fractional route-search scheduling. Each pair gives ordinary

\rightarrow

fractional completion time in seconds. Reductions are medians over three paired runs. Route-cost differences are fractional minus ordinary; positive values indicate higher route cost.

	Coverage $a$		Modeled time
$h$	Uniform	Opt.	Uniform	Opt.
0.25	0.0126	0.0340	236.6	87.1
0.5	0.0245	0.0662	167.4	61.2
1	0.0467	0.1254	135.8	49.0
2	0.0850	0.2211	124.8	45.6
4	0.1430	0.3459	132.0	48.4

Appendix

Table 19. Effect of the call deadline

h

on uniform and optimized (Opt.) allocation in the six-block example. Coverage

a

is the smallest per-round repair probability across blocks. Modeled time is the time needed to reduce the worst-block expected remaining loss to

0.01

, using round duration

h+0.4

Merge policy	Failed checks	Evaluations
Color only	$23\to 12\to 0$	5
Optimistic	$23\to 0$	5
Merge all	$23\to 0$	2

Appendix

Table 20. Repair progress and verification cost in the three-agent pipeline pilot. Arrows show the number of failing checks from the initial artifact through successive merges; “Evaluations” counts charged objective evaluations. Within each batch, all policies reuse the same three frozen proposals. The original and repeat batches give the same counts.

Multi-Agent Collaboration

Multi-agent collaboration studies how autonomous agents coordinate, share information, and combine capabilities to solve tasks together.

See all 310 papers

Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration
Oct 20, 2026Ivan Ilin, Peter RichtárikMulti-Agent Collaboration Multi-Agent Planning
KAUST
Verifying Coordination in Parallel Coding Agents: NP-Bench and a Scheduling Planner
Oct 5, 2026Sumanyu MukuCoding Agent Benchmarks Multi-Agent Coordination
Amira Learning
When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding
May 31, 2026Xu Yang, Lunyiu Nie, Ethan Chandra +3Graph Partitioning Multi-Agent System Optimization
1The University of Texas at Austin · University of Oxford

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

Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration

Ivan Ilin, Peter Richtárik

KAUST

Multi-Agent Collaboration Multi-Agent Planning

Open paper AskPDF arXiv

Teams of large language model (LLM) agents are increasingly applied to complex tasks, but their collaboration protocols are mostly designed empirically, without convergence guarantees. We formalize collaborative problem solving as block optimization: each agent improves one part of a shared solution, guided by its local objective plus a correction for how its changes affect the other parts. A coordinator checks every proposal against the global objective and merges proposals that do not interfere with each other. We prove linear convergence up to an error floor that vanishes when the corrections are exact. Interfering proposals can also be merged once their combination has been checked; the rate then depends on how well the proposals actually combine, not on worst-case interactions. With GPT-OSS-120B agents on robot routing, a three-agent team finds collision-free plans in every run, better than those of a single agent that controls all robots. On a larger routing task, a six-agent team completes its search about twice as fast as the single agent (in median). Merging the best checked combination of proposals, rather than only proposals that do not interfere, cuts the team's search time by about 30%. With constants measured on the runs, our convergence bound holds in every round and follows the observed progress. We also test the theory on query planning in SQLite and on a synthetic task.

Abstract

Multi-Agent Collaboration

Explore similar work

Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration

Verifying Coordination in Parallel Coding Agents: NP-Bench and a Scheduling Planner

When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding