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

Ivan Ilin; Peter Richtárik

cs.MAOct 20, 2026

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

Authors: Ivan Ilin, Peter Richtárik

Organizations: KAUST

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1. One epoch of Algorithm 1 on a constructed example with illustrative gains. Staircases show each agent’s best corrected score so far, which need not reach the minimum $\widehat{f}_{b}^{\,*}$ of the corrected objective. Each proposal is verified alone, and the coordinator accepts the color with the largest total gain: blocks 2 and 3 ( $3+2=5$ ) rather than the single largest gain ( $4$ ). A five-stage pipeline. Stage one: a coordinator holds the shared solution x with three blocks; each agent b receives its own block, where its search starts, and its correction, computed from the other blocks, which stay frozen. Stage two: three agents, drawn in blue, orange and magenta, each minimize their local objective plus correction over their own block; a small staircase shows the corrected score of the best candidate dropping at each of three private steps, from zero at the current block to the proposal, which stays above a dashed line marking the minimum. Stage three: a verifier evaluates each proposal alone against the same base, giving gains four, three and two. Stage four: in the dependency graph block one is connected to blocks two and three, which are not connected to each other. Color one contains blocks two and three with total gain five and is marked as selected; color two contains block one with gain four. Stage five: the new base replaces blocks two and three and keeps block one, and the loss drops by five. A solid arrow returns to the start for the next epoch; a dashed arrow shows that verified values update the correction.

Figure 2. Recorded plan at the optimum (first map, team seed 19 after round 4): nine delivered, zero collisions,

F=F^{*}=144

. (a) Robot 1: arrival at tick 20, cost 20. (b) All nine routes. (c) Block

\{r_{0},r_{1},r_{6}\}

with peers faded. Markers: starts; flags: goals. Overlapping segments are offset within cells; spatial crossings need not coincide in time. Three views of the same recorded plan, which is optimal. Left: robot one goes down from its start, then right and down to its goal, with Start at tick zero and Finish at tick twenty, and arrival cost twenty. Center: all nine robot routes, with coincident segments separated within their cells. Right: one agent's robots zero, one and six highlighted, with the six other robots faded. Numbered filled markers show starts; matching flags show goals. Gray cells are walls.

Figure 3. Mean gap

F-F^{*}

against search time (logarithmic gap axis); 20 runs per curve, 10 without correction. (a, b) Maps 1 and 2: nine robots, three team agents; (c) both maps as two floors: 18 robots, six team agents. Best-of-

W

W

parallel single agents, as many as team agents. Dotted: final mean of the team without correction. Variants: Section 8.1 . Three panels show the mean gap to the optimum against search time, with the gap on a logarithmic axis; the panels for map 1 and map 2 share a time axis up to about 1,570 seconds, and the two-floor panel extends to about 2,000 seconds. On map 1, the team with best combination falls fastest and ends near 5 after about 950 seconds; the team with Algorithm 1 ends near 6 after about 990 seconds; the team unsafe falls more slowly and ends near 5 after about 1,260 seconds; the best-of-three falls fast at first and levels off near 19; the single agent ends near 12; the team without correction stalls near 310. On map 2, the team with best combination falls fastest but levels off near 13, above Algorithm 1, which ends near 7; the team unsafe ends near 10; the best-of-three near 22 and the single agent near 20; the team without correction stalls near 180. On two floors, the team with best combination falls fastest and ends near 18 after about 1,010 seconds, Algorithm 1 near 13 after about 1,010 seconds, the team unsafe near 15 after about 1,280 seconds, the best-of-six near 21 and the single agent near 29 after about 1,970 seconds; the team without correction stalls near 495. Dotted lines continue the final values of the team without correction. Stars mark curve endpoints.

	Map 1					Map 2					Two floors
Variant	Safe runs $\uparrow$	$F-F^{*}$ $\downarrow$		Search (s) $\downarrow$		Safe runs $\uparrow$	$F-F^{*}$ $\downarrow$		Search (s) $\downarrow$		Safe runs $\uparrow$	$F-F^{*}$ $\downarrow$		Search (s) $\downarrow$
Single agent	100%	12.0 ${}\pm{}$	10.5	613 ${}\pm{}$	398	95%	19.5 ${}\pm{}$	44.4	538 ${}\pm{}$	366	100%	28.6 ${}\pm{}$	23.3	1149 ${}\pm{}$	420
Best-of- $W$	95%	18.9 ${}\pm{}$	48.8	326 ${}\pm{}$	198	90%	21.6 ${}\pm{}$	33.9	326 ${}\pm{}$	147	100%	21.4 ${}\pm{}$	16.3	517 ${}\pm{}$	124
Team (Alg. 1 )	100%	5.9 ${}\pm{}$	2.7	481 ${}\pm{}$	227	100%	7.2 ${}\pm{}$	12.6	482 ${}\pm{}$	202	100%	13.1 ${}\pm{}$	12.7	656 ${}\pm{}$	206
Team (Alg. 2 )	100%	5.4 ${}\pm{}$	3.2	340 ${}\pm{}$	197	100%	12.8 ${}\pm{}$	17.2	310 ${}\pm{}$	204	100%	18.2 ${}\pm{}$	17.4	452 ${}\pm{}$	227
Team unsafe	100%	5.0 ${}\pm{}$	2.6	601 ${}\pm{}$	284	95%	10.1 ${}\pm{}$	22.3	424 ${}\pm{}$	232	95%	15.1 ${}\pm{}$	22.5	717 ${}\pm{}$	263

Table 1. All outcomes per variant and task (20 runs, 10 without correction); mean

\pm

sample SD. Safe runs: share of runs whose final plan delivers every robot without collisions.

F-F^{*}

: final gap to the optimum (

F^{*}=144

, 147, 291). Bold: best per column (mean and SD separately), excluding the team without correction. Best-of-

W

W=3

, or 6 on two floors.

Figure 4. (a) Two floors: mean gap of each team and its bounds with the divisors of Section 5 . (b) Mean correction error at the agents’ proposals, maps 1 and 2; 100 is one collision unknown to the correction. (c) Rounds of Team (Alg. 2 ) with several improving proposals, by their

\kappa_{k}

, or with one or none; bar height: active runs. All tasks: Figure E.4 . Three panels. Left, in two halves with a shared logarithmic gap axis: on two floors, the observed mean gap of the team with Algorithm 1 (orange) ends near 13 and its bounds end near 396 with kappa equal to 3, 87 with the smaller of kappa and the number of improving blocks, and 50 with the realized number of colors; the observed mean gap of the team with Algorithm 2 (brown) ends near 18 and its bounds end near 605, 191, 133 with the effective number of colors, and 70. Middle: the mean correction error at the agents' returned proposals on maps 1 and 2 falls from about 100 in round 1 to a few units by rounds 6 and 7 for both teams, with small rises when new collision pairs appear. Right: stacked bars per round for the 40 runs of the team with Algorithm 2, with bar height equal to the active runs; in round 1 most runs have conflicts that need two colors and six need three, rounds 2 to 4 mix rounds with conflicts, rounds where several proposals improve without conflict and rounds where one improves, and in rounds 5 to 8 most remaining runs have no improving proposal.

Figure 5. (a) SQLite controller time relative to measuring in advance (below 1: faster) on favorable (Fav.) and balanced (Bal.) workloads; points: databases. (b–d) Synthetic task, 2,000 runs per curve or point: (b) mean gap and Theorem 2 bound (dashed); (c) modeled cost, triangles at

H_{*}

(Section 7 ); (d) final gap under a correction bias

\nu

and the bound (dashed). Four panels. First: SQLite controller time relative to measuring the alternatives in advance, as bars that grow up or down from one; selective feedback is faster on the two favorable workloads and slower on the balanced one, with always-on feedback and the native planner for comparison and white dots for individual databases. Second: mean gap to the optimum on a logarithmic axis for the synthetic task; corrected runs with eight and thirty-two private steps fall to zero, dashed theoretical bounds lie above them, and runs without correction stall near thirty. Third: modeled completion cost against the number of private steps for four synchronization costs, U-shaped for positive cost, with triangles on each curve at the horizon predicted by the theory, left of the observed minimum for positive synchronization cost. Fourth: final mean gap against a persistent bias on the correction; it stays at zero up to about 0.6 and then rises to about thirty, nearly identically for eight and thirty-two private steps, with dashed upper bounds above it.

Symbol	Meaning
Shared task, local objectives and corrections
$m$	Number of blocks or agents.
$b$	Block or agent index.
$\mathcal{X}_{b},\mathcal{X}$	Finite block domain and product domain $\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{m}$ .
$x,x_{b},x_{bj}$	Shared candidate solution, its block $b$ , and coordinate $j$ of that block.
$x_{-b},(x_{-b},u)$	All blocks other than $b$ , and the solution with block $b$ replaced by $u$ .

Table 2. Notation used in the paper.

Appendix figures & tables36 assets

Supplementary material from the paper’s appendix.

Appendix

	ProxSkip	Present construction
Correction	Updated recursively through occasional proximal steps	Learned persistently from scalar verifier residuals in an identifiable model
Private work	Corrected gradient steps	Search within an assigned artifact block
Analysis	Joint iterate–correction error	Joint task–correction contraction; observable uncertainty for coordinate probes
Communication benefit	Accelerated communication under its optimization assumptions	Batching and a finite calibration budget; no ProxSkip acceleration claim

Appendix

Table B.1. Relation to ProxSkip ( Mishchenko et al., 2022 ) . Our correction can be learned from verifier feedback; its update and rate differ from ProxSkip’s.

Figure C.1. The two maps. Circles: starts; squares: goals; numbers: robot IDs; colors: the team agent that owns the robot (the single agent controls all of them); arrows point from start to goal; dark cells are walls. On two floors, map 1 is the first floor and map 2 the second, with its robots named s0–s8. Two sixteen-by-sixteen grids side by side. Left, map 1 with three two-by-two obstacles; right, map 2 with a horizontal wall of four cells, a vertical wall of four cells and two pieces of two cells. On each, nine robots have numbered circles at their starts and numbered squares at their goals, colored by the agent that owns them, and a thin arrow points from each start to its goal.

Map 1 (first floor)					Map 2 (second floor, s0–s8 on two floors)
Robot	Agent	Start	Goal	Dist.	Robot	Agent	Start	Goal	Dist.
r0	1	$(2,3)$	$(13,10)$	18	r0	1	$(2,1)$	$(14,12)$	23
r1	1	$(3,1)$	$(10,14)$	20	r1	1	$(1,9)$	$(13,10)$	13
r2	2	$(2,7)$	$(13,5)$	13	r2	1	$(2,4)$	$(14,5)$	13
r3	2	$(7,1)$	$(5,14)$	15	r3	2	$(6,2)$	$(5,13)$	14
r4	3	$(2,12)$	$(13,8)$	15	r4	2	$(14,1)$	$(11,13)$	15

Appendix

Table C.1. Assignments and shortest legal grid distances on both maps. On the first map the blocks are

\{r_{0},r_{1},r_{6}\}

\{r_{2},r_{3},r_{7}\}

and

\{r_{4},r_{5},r_{8}\}

; on the second,

\{r_{0},r_{1},r_{2}\}

\{r_{3},r_{4},r_{5}\}

and

\{r_{6},r_{7},r_{8}\}

. The sums are the optima.

Figure D.1. How the protocols and the prompt were chosen (first map; mean gap

F-F^{*}

against search time). (a) Single-agent protocols with prompt v1, ten runs each. (b) Team protocols with prompt v1, ten runs each; the sequential replay plays the team’s answers one agent at a time. (c) Prompt v1 against prompt v2: twenty runs for the v2 one-route single agent and team, ten for the other curves. Stars mark the end of recorded support. Three panels of mean gap to the optimum against search time on logarithmic axes, all on the first map. (a) Single-agent protocols with prompt v1: the two whole-plan protocols stall near a gap of 700; answers with up to three or two routes stall near 37 and 44; one route per answer continues lower and ends near 23. (b) Team protocols with prompt v1: the team ends near 12, the team with the efficiency paragraph near 23, the team with partial updates near 38, the team without correction stalls near 250, and the sequential replay of the team reaches the team's values more slowly. (c) Prompt v1 against prompt v2: with v2 the one-route single agent ends near 12 instead of 23 and the team near 6 instead of 12; the single agent also ends sooner; the single agent with exactly three routes per answer and prompt v2 ends near 77.

Metric	Single agent (whole plan)	Team
Actual elapsed (s)	$315.25\pm 132.36$	$1089.55\pm 896.47$
Checked answers	$8.30\pm 2.71$	$59.30\pm 7.92$
Safe delivery of all nine	1/10	10/10

Appendix

Table D.1. All ten outcomes per variant; mean

\pm

sample SD where applicable. Team answer counts sum across agents, whereas its search time uses the per-round maximum. Actual elapsed time includes failed requests and recovery pauses.

	Single agent, whole plan				Team (Alg. 1 )
Seed	Final $F$	Delivered/conflicts	Answers	Time (s)	Final $F$	Rounds	Answers	Time (s)
0	1476	0/0	5	165.6	152	7	45	608.0
1	1476	0/0	5	135.4	158	8	58	650.2
2	455	9/3	8	264.4	152	7	57	494.2
3	490	8/2	10	372.6	155	8	59	673.6
4	722	9/5	9	253.7	155	8	66	578.9

Appendix

Table D.2. Every completed seed, without selection. Time is the search time defined above. All ten team outcomes deliver 9/9 without conflicts. Single-agent delivered/conflict counts refer to its final accepted plan, including an unchanged initial plan.

Seed	0	1	2	3	4	5	6	7	8	9
Final $F$	452	444	152	451	448	294	448	444	548	248
Collisions	3	3	0	3	3	1	3	3	4	1
Rounds	8	8	4	8	8	8	8	8	8	8

Appendix

Table D.3. All ten no-correction team outcomes. Every final plan delivers all nine robots; collisions are cross-block events in the final plan.

	1 route per answer				Up to 2 routes				Up to 3 routes				All nine routes
Seed	$F$	Coll.	Ans.	Search (s)	$F$	Coll.	Ans.	Search (s)	$F$	Coll.	Ans.	Search (s)	$F$	Coll.	Ans.	Search (s)
0	152	0	16	241.8	152	0	18	298.3	160	0	27	637.7	1476 ∗	0	15	403.4
1	161	0	35	742.6	267	1	25	448.3	153	0	19	402.9	259	1	60	1502.2
2	152	0	32	577.1	170	0	25	778.1	152	0	17	331.2	1476 ∗	0	15	395.3
3	150	0	43	814.7	152	0	22	396.1	152	0	9	161.9	1476 ∗	0	15	469.2
4	151	0	51	1153.7	152	0	13	194.5	152	0	10	168.6	691	5	18	395.7

Appendix

Table D.4. Single agents with the efficiency paragraph and patience fifteen, by the number of routes an answer may replace: independently replayed final plans of all forty runs. Coll.: collisions in the final plan; Ans.: checked answers. ∗ : no route was ever accepted, so the plan is the initial one and delivers no robot; every other final plan delivers all nine. Runs with a safe plan and

F\leq 153

stopped early, seed 1 of the whole-plan agent at its ceiling of sixty answers, and all others after fifteen answers without improvement. The whole-plan agent’s elapsed time, which adds retries, exceeds its search time by less than 5 s in every run except seed 2 (75 s).

	Efficiency paragraph					Partial route updates
Seed	$F$	Coll.	Rounds	Search (s)	USD	$F$	Coll.	Rounds	Ans.	Search (s)	USD
0	150	0	7	400.19	0.23792	152	0	5	43	257.44	0.15622
1	149	0	5	276.32	0.16257	152	0	6	51	320.67	0.19878
2	154	0	8	501.97	0.31963	248	1	8	58	489.37	0.26790
3	188	0	8	567.83	0.32965	150	0	4	33	212.23	0.12381
4	161	0	8	429.93	0.17183	153	0	6	44	268.90	0.16628

Appendix

Table D.5. Two variants of the v1 team: independently replayed final plans of all ten runs of each. Every final plan delivers all nine robots. Coll.: collisions in the final plan; Ans.: checked answers, summed over agents; USD: reported cost. With partial updates, seed 0 is the adopted pilot; the runs with a safe plan and

F\leq 153

stopped early, the others at the eight-round cap, and elapsed time exceeds search time by less than 3 s in every run except seed 0 (31 s).

Figure D.2. Measured constants of the team per run for four prompt settings: v1 and v1 with the efficiency paragraph on map 1 (ten runs each), v2 on map 1 and on map 2 (twenty runs each). Panels (a)–(c) average within a run; (d) takes the smallest ratio

\sum_{b}D_{b}/\Delta

over the states of the run that start a round. Diamonds and bars: mean

\pm

sample SD, not confidence intervals. Since every true-minimizer error is zero, a run’s mean

B

equals its mean error at returned proposals. Four panels compare four prompt settings using run-level statistics: prompt v1, v1 with the efficiency paragraph, prompt v2 on map 1 and prompt v2 on map 2. Panels show mean realized search quality Q, mean error term B, mean descent coefficient alpha, and the smallest geometry ratio over the states that start a round. Dots are individual runs; white diamonds with bars show mean and sample standard deviation. Search quality is higher with prompt v2; the error term and descent coefficient change little.

Per-run statistic	v1	v1 + par.	v2, map 1	v2, map 2
Mean $Q$	$0.59\pm 0.08$	$0.63\pm 0.11$	$0.70\pm 0.15$	$0.69\pm 0.14$
Mean $B$	$47.4\pm 12.7$	$49.2\pm 18.3$	$49.7\pm 16.5$	$40.4\pm 19.5$
Mean $\alpha$	$0.25\pm 0.04$	$0.26\pm 0.07$	$0.27\pm 0.07$	$0.26\pm 0.08$
Smallest ratio	$0.81\pm 0.15$	$0.88\pm 0.12$	$0.92\pm 0.14$	$0.93\pm 0.10$

Appendix

Table D.6. Mean

\pm

sample SD over runs (ten for v1 settings, twenty for v2). Smallest ratio: the minimum of

\sum_{b}D_{b}/\Delta

over the states of a run that start a round; its mean is not a certificate over the union of runs.

Variant	Appendix	Safe	Final $F$	Search time (s)	Answers	Reported USD/run
Prompt v2, map 1 (main text)
Single agent, 1 route per answer	E	20/20	$156.00\pm 10.53$	$613.01\pm 397.82$	$27.80\pm 11.67$	$0.161\pm 0.101$
Single agent, exactly 3 routes per answer	E	9/10	$220.80\pm 220.38$	$561.24\pm 253.45$	$20.40\pm 9.89$	$0.147\pm 0.065$
Best-of-3 one-route single agents	E	19/20	$162.90\pm 48.82$	$326.41\pm 198.10$	$39.30\pm 11.30$	$0.188\pm 0.108$
Team (Alg. 1 )	E	20/20	$149.90\pm 2.67$	$481.04\pm 227.32$	$47.10\pm 16.08$	$0.228\pm 0.106$
Team (Alg. 2 )	E.5	20/20	$149.40\pm 3.22$	$339.74\pm 196.91$	$36.20\pm 11.88$	$0.181\pm 0.074$

Appendix

Table D.7. All routing variants, with prompt v2 of the main text and with prompt v1; twenty runs for the v2 one-route single agent, its best-of-three (best-of-six on two floors), the team with each of its three merge rules and its sequential replay on each task, ten for every other variant; mean

\pm

sample SD over all runs, including unsafe ones. Safe: all robots delivered without collisions in the final plan. Search time ends at the stopping rule; for an unsafe run it is not a time to a solution. Answers counts checked answers per run, summed over agents for teams. Reported costs omit charges that the provider did not return. Each sequential replay reuses its team’s recorded answers, so it has no new cost.

	Single agent, 1 route			Best-of-3		Single agent, exactly 3 routes			Team (Alg. 1 )			Team, no correction
Seed	$F$	Ans.	Time (s)	$F$	Time (s)	$F$	Ans.	Time (s)	$F$	Rounds	Time (s)	$F$	Time (s)
0	148	20	318.9	157	673.7	153	10	280.6	145	6	304.2	444 †	209.3
1	153	19	276.9	151	250.8	151	26	554.3	152	7	542.3	452 †	533.2
2	153	20	323.4	152	195.3	848 †	20	448.2	152	5	253.0	546 †	357.1
3	151	14	209.8	152	213.4	153	14	504.3	147	11	666.7	444 †	163.7
4	150	22	334.7	148	156.3	148	13	267.0	150	12	987.2	444 †	270.8

Appendix

Table E.1. Every run on the first map with prompt v2, independently replayed; — marks a seed that was not run for that variant. † marks a final plan that is not safe. Ans.: checked answers; team times use the per-round maximum ( C.1 ).

	Single agent			Best-of-3		Team (Alg. 1 )			Team, no correction
Seed	$F$	Ans.	Time (s)	$F$	Time (s)	$F$	Rounds	Time (s)	$F$	Time (s)
0	156	20	458.2	153	173.3	151	12	916.2	447 †	93.0
1	154	24	526.9	152	203.3	148	5	341.1	247 †	89.4
2	155	14	278.0	156	409.8	155	7	396.9	347 †	307.1
3	153	45	1236.5	185	476.3	151	5	260.7	647 †	68.0
4	156	20	324.7	156	379.3	155	6	367.6	447 †	194.0

Appendix

Table E.2. Every run on the second map with prompt v2, independently replayed. † marks a final plan that is not safe. Ans.: checked answers; team times use the per-round maximum ( C.1 ).

Variant	Safe	$F\leq 156$	Final $F$	Search time (s)	Answers	USD/run
Single agent, 1 route per answer	19/20	16/20	$166.50\pm 44.38$	$537.9\pm 365.7$	$24.5\pm 11.2$	$0.137\pm 0.093$
Best-of-3 one-route single agents	18/20	15/20	$168.55\pm 33.92$	$326.3\pm 147.0$	$38.7\pm 9.6$	$0.195\pm 0.089$
Team (Alg. 1 )	20/20	19/20	$154.15\pm 12.56$	$482.3\pm 201.6$	$44.8\pm 16.1$	$0.221\pm 0.093$
Team without correction	2/10	2/10	$328.40\pm 153.41$	$178.1\pm 87.2$	$19.0\pm 7.2$	$0.069\pm 0.031$
Sequential replay of the team	20/20	19/20	$154.15\pm 12.56$	$778.2\pm 304.6$	$44.8\pm 16.1$	—

Appendix

Table E.3. All runs on the second map; mean

\pm

sample SD over all runs, including unsafe ones.

Variant	Safe	Both thresholds	Final $F$	Search time (s)	Answers	USD/run
Single agent, 1 route per answer	20/20	9/20	$319.60\pm 23.31$	$1148.7\pm 419.6$	$63.2\pm 16.2$	$0.365\pm 0.127$
Best-of-6 one-route single agents	20/20	16/20	$312.40\pm 16.26$	$516.8\pm 123.9$	$142.5\pm 17.1$	$0.680\pm 0.154$
Team (Alg. 1 )	20/20	19/20	$304.05\pm 12.73$	$656.4\pm 206.1$	$91.9\pm 20.7$	$0.449\pm 0.141$
Team without correction	0/10	0/10	$785.50\pm 181.90$	$382.1\pm 176.1$	$56.0\pm 19.9$	$0.202\pm 0.079$
Sequential replay of the team	20/20	19/20	$304.05\pm 12.73$	$1632.1\pm 468.5$	$91.9\pm 20.7$	—

Appendix

Table E.4. All variants on two floors (

F^{*}=291

); mean

\pm

sample SD over all runs. Team answers and costs are summed over both floors.

	Single agent			Best-of-6			Team (Alg. 1 )				Team, no correction
Seed	$F_{1}{+}F_{2}$	Ans.	Time (s)	$F_{1}{+}F_{2}$	Rounds	Time (s)	$F_{1}{+}F_{2}$	Rounds	Time (s)	Seq. (s)	$F_{1}{+}F_{2}$	Time (s)
0	150+164 ∗	69	1778.2	151+178 ∗	26	676.8	145+151	12	916.2	1906.9	444+447 ∗	219.5
1	150+155	68	1518.6	151+155	31	739.3	152+148	7	578.4	1586.1	452+247 ∗	533.2
2	152+165 ∗	62	1380.5	200+163 ∗	28	638.8	152+155	7	423.9	1186.9	546+347 ∗	435.2
3	153+161 ∗	67	1356.9	152+153	24	491.6	147+151	11	723.4	1335.1	444+647 ∗	163.7
4	152+156	32	473.4	150+153	21	390.4	150+155	12	1012.8	2412.9	444+447 ∗	324.2

Appendix

Table E.5. Every run on two floors.

F_{1}{+}F_{2}

: final loss of each floor; ∗ marks a run that misses a threshold. Every final plan of the single agent, the best-of-six and the team is safe; no final plan without correction is. Team runs pair seed

s

of both maps; Seq.: sequential replay.

Task and merge rule	Safe	Threshold	Final $F$	Search time (s)	Sequential (s)	Rounds	Answers	USD/run
Map 1, Team (Alg. 2 )	20/20	19/20	$149.40\pm 3.22$	$339.7\pm 196.9$	$601.7\pm 255.5$	5.7	$36.2\pm 11.9$	$0.181\pm 0.074$
Map 1, Team unsafe	20/20	20/20	$149.00\pm 2.55$	$601.4\pm 284.5$	$1180.2\pm 515.9$	9.3	$64.6\pm 25.9$	$0.357\pm 0.154$
Map 2, Team (Alg. 2 )	20/20	14/20	$159.75\pm 17.21$	$310.4\pm 204.1$	$520.0\pm 287.0$	5.6	$33.0\pm 15.5$	$0.174\pm 0.135$
Map 2, Team unsafe	19/20	19/20	$157.05\pm 22.26$	$423.7\pm 232.4$	$764.2\pm 410.3$	7.4	$48.0\pm 22.6$	$0.235\pm 0.130$
Two floors, Team (Alg. 2 )	20/20	14/20	$309.15\pm 17.39$	$451.6\pm 227.1$	$1121.7\pm 421.2$	7.1	$69.2\pm 19.8$	$0.355\pm 0.158$
Two floors, Team unsafe	19/20	19/20	$306.05\pm 22.54$	$716.8\pm 263.0$	$1944.3\pm 562.7$	10.6	$112.5\pm 28.8$	$0.592\pm 0.172$

Appendix

Table E.6. The team with the best-combination and the unsafe merge; mean

\pm

sample SD over twenty runs. The team with Algorithm 1 is in Table 1 . On two floors, answers and costs are summed over both floors.

	Map 1					Map 2
	Team (Alg. 2 )			Team unsafe		Team (Alg. 2 )			Team unsafe
Seed	$F$	Rounds	Time (s)	$F$	Time (s)	$F$	Rounds	Time (s)	$F$	Time (s)
0	152	3	191.1	147	843.9	148	2	75.3	153	948.6
1	152	8	595.0	149	646.0	157	8	489.1	155	319.2
2	153	6	385.7	150	807.0	150	9	502.5	153	539.6
3	148	5	262.6	144	342.9	153	4	203.9	149	938.4

Appendix

Table E.7. Every run of the two merge variants, independently replayed. † marks a final plan that is not safe.

Figure E.1. The recorded repair behind Figure 2 (prompt v2, first map, team seed 19). (a) All nine accepted routes after round 3; colors identify the three agents; filled circles mark starts and open diamonds goals. The red circle marks the only collision of this plan:

r_{1}

and

r_{8}

exchange cells at tick 11. (b) The block of the agent that owns

r_{0},r_{1},r_{6}

after its accepted answer in round 4: only

r_{1}

changes its cells (old route dashed), with the same arrival tick, and the plan reaches the optimum

F=144

. Coincident segments are slightly offset for visibility; all event checks use the original cells and ticks. Two maps reconstructed from saved commands. Left: all nine routes of team seed nineteen after round three, colored by agent, with a red circle where robots one and eight exchange cells at tick eleven, the only collision of that plan. Right: the three routes owned by the agent that makes the next accepted update; only robot one changes its cells, with its old route dashed in gray and its new route solid, and the same arrival tick.

Figure E.2. Two more recorded repairs with prompt v2 on the first map, as positions of the two robots at ticks

t-3

t+1

around the collision tick

t

(larger dot: tick

t

; red circle: the swap). Left: team seed 11, round 7; the agent of

r_{0},r_{1},r_{6}

knows the swap of

r_{0}

with

r_{7}

from the correction, and only

r_{0}

’s route changes, with the same arrival tick (

F

from 259 to 159). Right: single agent seed 4, answer 22; only

r_{4}

’s route changes, with the same arrival tick, and the swap with

r_{8}

disappears (

F

from 250 to 150). Python replays the recorded answers without editing them. Close-up frames around two recorded collisions, before and after the accepted change, showing positions of the two robots over five ticks around the collision. Left: team seed eleven, round seven; robots zero and seven swap cells at tick eight before the change; afterwards robot zero arrives from above and passes behind robot seven. Right: single-agent seed four, answer twenty-two; robots four and eight swap cells at tick six before the change; afterwards robot four turns up and lets robot eight pass.

	Map 1				Map 2
Block	$n$	Mean $Q$	$Q=0$	$Q=1$	$n$	Mean $Q$	$Q=0$	$Q=1$
Agent 1	125	0.67	26	40	79	0.72	18	31
Agent 2	114	0.63	28	16	115	0.73	23	58
Agent 3	104	0.68	23	26	144	0.56	46	22
All	343	0.66	77	82	338	0.65	87	111

Appendix

Table E.8. Realized search quality

Q

after each private search of the team with prompt v2, including unselected proposals; searches with zero initial corrected gap are excluded. Agents 1, 2 and 3 own

\{r_{0},r_{1},r_{6}\}

\{r_{2},r_{3},r_{7}\}

and

\{r_{4},r_{5},r_{8}\}

on map 1 and

\{r_{0},r_{1},r_{2}\}

\{r_{3},r_{4},r_{5}\}

and

\{r_{6},r_{7},r_{8}\}

on map 2.

Figure E.3. Offline assumption diagnostics for the team with prompt v2. (a) Mean realized

Q

over searches with a positive corrected gap, in the rounds with at least ten such searches. (b) Exact ratio

\sum_{b}D_{b}(x)/\Delta(x)

at every recorded state, one line per run; dashed lines mark the smallest value over the states that start a round,

\mu=0.43

on map 1 and

0.70

on map 2; dots mark final states, crosses the single-block traps (ratio 0). Left: mean realized search quality by global round for both maps; it falls from about 0.93 and 0.99 in round one to between 0.3 and 0.5 after round five. Right: the ratio of the summed block improvements to the global gap at every recorded state, one thin line per run and colored by map, with dashed lines at 0.43 for map 1 and 0.70 for map 2; dots mark final states and crosses the six single-block traps at ratio zero.

	$\mu$	$\bar{Q}$	$\bar{\alpha}$	$\bar{B}$	Coupled	Gap (bound)
Team (Alg. 1 )
Map 1, prompt v1	0.60	0.58	0.247	47.4	39%	12.5 (211.7)
Map 1	0.43	0.66	0.246	45.5	30%	5.9 (254.2)
Map 2	0.70	0.65	0.242	36.5	32%	7.2 (226.8)
Two floors	—	0.66	0.222	66.7	31%	13.1 (395.9)
Team (Alg. 2 )

Appendix

Table E.9. Measured constants of the team runs:

\mu

at states that start a round, mean search quality

\bar{Q}

, pooled means of the round coefficients, share of locally safe proposals that collide with another agent’s robot, and final mean gap with the averaged bound in parentheses. Prompt v1 values use all states and its ten runs; the two-floor rows pool the searches of both maps, and their

\mu

is not computed. For the unsafe team the round coefficients and the bound are not defined, because its loss can increase. The correction error at true block minimizers is zero in every case, so

\bar{B}

is the mean error at returned proposals (summed over both floors on two floors).

Figure E.4. Observed mean gap of each team and its averaged trajectory-wise bound (Appendix E.8 ) for every task, with the divisors of Section 5 :

\kappa=3

;

\min\{\kappa,|I^{k}|\}

(1 if no block improves), which bounds the number of colors that contain an improving block; the effective number of colors

\kappa_{k}

(Proposition 2 ), which needs checked combinations and therefore applies only to Team (Alg. 2 ); and the realized number of colors

\kappa^{*}_{k}

(Corollary 1 ). Bands: pointwise minimum and maximum of the observed gap over the twenty runs, not confidence intervals; a run at the optimum is drawn at gap 1. On two floors each floor uses its own divisor. Six panels in two rows, for map 1, map 2 and two floors, against the global round, with the gap on a logarithmic axis. Top row: the team with Algorithm 1, its observed mean gap (orange) with a light band between the pointwise minimum and maximum over the twenty runs, and three averaged bounds: with kappa equal to 3 (gray squares), with the smaller of kappa and the number of improving blocks (purple triangles) and with the realized number of colors (red circles). Bottom row: the team with Algorithm 2 (brown), with the same three bounds and the bound with the effective number of colors (teal diamonds). On the two maps the observed bands reach the bottom of the axis where runs reach the optimum.

Map	Phase	Rounds	Mean $\|I^{k}\|$	Conflicting pairs	New collision	Mean $\kappa_{k}$	Mean accepted	Accepting a conflicting pair
Map 1	Start (round 1)	20	2.95	34/58	34	2.20	2.35	11
	Repair (unsafe base)	57	1.89	36/72	21	1.49	1.42	2
	Refinement (safe base)	36	0.61	1/5	1	1.03	0.61	0
Map 2	Start (round 1)	20	2.90	19/56	19	1.75	2.85	13
	Repair (unsafe base)	35	1.63	21/30	7	1.49	1.17	1
	Refinement (safe base)	56	0.32	2/4	2	1.04	0.30	0

Appendix

Table E.10. Realized coupling in the best-combination runs by phase: number of rounds, mean number of improving proposals, conflicting pairs among pairs of improving proposals, conflicts in which the two proposals together create a collision that neither causes alone, mean effective number of colors, mean number of accepted blocks, and rounds whose accepted combination contains a conflicting pair.

Figure E.5. Parallel search time (solid) against the sequential replay of the same answers (dashed) for Team (Alg. 1 ), Team (Alg. 2 ) and Team unsafe; mean gap

F-F^{*}

on a logarithmic axis, twenty runs per curve; the single agent for reference. Three panels of mean gap to the optimum against search time on logarithmic axes, for map 1, map 2 and two floors. For each of the three team variants, Algorithm 1, best combination and unsafe, the parallel search time (solid) and the sequential replay of the same answers (dashed) are drawn in one color; the single agent is drawn for reference. Each dashed curve reaches the values of its solid curve later, by a factor between about 1.6 and 2.7, and on two floors the sequential replays of the teams end near or beyond the single agent's search time.

Quantity	Fixed value
Sources per report	3
Groups per endpoint table	4,096
Objects per group	2
High/low outgoing degree per object	400 / 1
Edges per source	1,642,496
Probability of a high-degree right group	0.97

Appendix

Table F.1. Fixed database and feedback settings. The 0.97 probability governs generation of edge endpoints, not a success probability of the controller.

Policy	Favorable, 48 reports	Favorable, 192 reports	Balanced, 48 reports
Native planner	6.64	23.44	13.27
Always left	6.54	25.05	15.77
128-edge sample	13.61	32.40	22.76
2,048-edge sample	36.47	51.29	40.16
Full joined histograms	433.34	440.16	439.11
Exact counts, cached	10.78	21.19	10.88

Appendix

Table F.2. Controller time of all policies, in milliseconds. Each entry is the pooled median of nine timings: three repetitions on each of three independent databases. All answers pass the recorded correctness checks. Calibration, feedback processing and policy-specific instrumentation are included.

Figure F.1. (a) Controller time for the principal controls: bars show the mean of the three per-database timing medians; white points are those medians and whiskers their minimum and maximum. Table F.2 reports pooled medians, and all policies compute the same correct answers. (b, c) Accumulated SQLite VM work for the favorable and balanced 48-report streams, including calibration, which is charged before its associated report. Lines average the three database trajectories and light bands show their minimum and maximum; repeated timing runs have identical VM counts within a database. VM work measures engine work, not elapsed time: the archive records complete controller time only at the end of a workload. Three panels. Left: grouped bars of controller time for the principal policies on three workloads, favorable with 48 and 192 reports and balanced with 48, with white points for the three databases and whiskers for their range. Middle and right: accumulated SQLite virtual-machine work against report index for the favorable and balanced 48-report streams, one line per policy, with light bands for the range over the three databases.

Block	True target $t_{b}$	Private target $\tilde{t}_{b}$	$\pi_{b}$
1	10100000	01011111	0.5
2	01000001	01000001	0.6
3	00100010	11011101	0.7
4	10000010	10000010	0.8
5	11011001	00100110	0.9
6	11111101	11111101	1.0

Appendix

Table G.1. The single fixed 48-bit task. Bit strings list coordinates 1 through 8 in order. Random solver trajectories change search randomness, not this task.

$H$	Completion epochs, mean $\pm$ SE	Cost, $C=0$	Cost, $C=5$	Cost, $C=20$	Cost, $C=100$
1	$61.73\pm 0.37$	61.7	370.4	1296.4	6235.1
2	$33.60\pm 0.18$	67.2	235.2	739.2	3427.2
4	$18.19\pm 0.09$	72.8	163.7	436.6	1891.8
8	$10.34\pm 0.05$	82.7	134.4	289.4	1116.4
16	$6.01\pm 0.03$	96.1	126.2	216.3	696.9
32	$3.49\pm 0.02$	111.6	129.1	181.4	460.5

Appendix

Table G.2. Exact correction: all 2,000 trajectories per horizon reach the optimum on the same task. Standard errors reflect solver randomness. Cost is modeled parallel work plus synchronization overhead.

	$H=8$			$H=32$
$\nu$	Final gap	Solved	Bound	Final gap	Solved	Bound
0.00	$0.00\pm 0.00$	2000	0.0	$0.00\pm 0.00$	2000	0.0
0.25	$0.00\pm 0.00$	2000	10.6	$0.00\pm 0.00$	2000	6.8
0.50	$0.00\pm 0.00$	2000	20.2	$0.00\pm 0.00$	2000	13.4
0.75	$0.30\pm 0.01$	1340	26.8	$0.27\pm 0.01$	1187	19.2
1.00	$3.08\pm 0.04$	48	30.4	$2.79\pm 0.03$	40	24.7

Appendix

Table G.3. Approximate corrections: final mean gap after 160 epochs (

\pm

one standard error), runs reaching the optimum out of 2,000, and the mean per-run recurrence envelope.

Policy	$H$	Completion epochs, mean $\pm$ SE	Mean verifier queries	Cost, mean $\pm$ SE
Learn ( $p=1$ )	8	$12.78\pm 0.07$	87.1	$444.8\pm 1.96$
Learn ( $p=0.5$ )	8	$21.32\pm 0.13$	85.5	$682.5\pm 3.58$
Learn ( $p=0.25$ )	8	$42.35\pm 0.29$	83.1	$1268.9\pm 8.09$
Refresh every round	8	$10.24\pm 0.07$	524.8	$811.6\pm 5.06$
Identify once	8	$10.24\pm 0.07$	81.1	$367.9\pm 1.89$
Learn ( $p=1$ )	32	$8.86\pm 0.02$	80.9	$541.7\pm 1.31$

Appendix

Table G.4. Every calibrated configuration in the learned-correction series: 1,000 trajectories each on the fixed task. Queries include initial evaluation, deliberate calibration and changed-proposal verification. Costs use

C=20

, unit parallel private-slot cost and one additional unit per counted scalar evaluation.

Policy	$H$	Epochs, mean $\pm$ SE	Queries	Probes	Reused	Cost, mean $\pm$ SE
Dedicated	8	$12.78\pm 0.07$	87.1	48.0	0.000	$444.8\pm 1.96$
Verification reuse	8	$12.78\pm 0.07$	83.9	44.8	3.186	$441.6\pm 1.96$
Identify once	8	$10.24\pm 0.07$	81.1	48.0	0.000	$367.9\pm 1.89$
Dedicated	32	$8.86\pm 0.02$	80.9	48.0	0.000	$541.7\pm 1.31$
Verification reuse	32	$8.86\pm 0.02$	80.2	47.3	0.703	$541.0\pm 1.30$
Identify once	32	$3.44\pm 0.03$	60.8	48.0	0.000	$239.7\pm 1.37$

Appendix

Table G.5. All verification-reuse configurations, with 1,000 trajectories each. Queries count every charged scalar evaluation, probes count deliberate calibration, and reused counts coefficients identified from already-paid proposal evaluations. Epoch and cost errors are standard errors of their means. Identify-once remains the strongest control.

Figure G.1. Learning the correction and reusing verification. (a) Mean loss at

H=8

for the acquisition policies; refresh and identify-once have the same trajectory. (b) Mean completion costs of all acquisition policies at the three horizons, with one-standard-error bars. (c) True mean loss (solid) and

F^{*}

plus the mean online stopping certificate (dashed) at

H=8

, for dedicated calibration and verification reuse;

F^{*}

is added only to display the offline comparison. (d) All counted verifier queries, averaged over 1,000 trajectories, including calibration and the initial evaluation. Four panels. First: mean loss against epoch at eight private steps for the acquisition policies; refresh and identify-once coincide. Second: mean completion cost of every acquisition policy at eight, 32 and 64 private steps, with one-standard-error bars. Third: true mean loss and the optimum plus the mean online stopping certificate against epoch at eight private steps, for dedicated calibration and verification reuse. Fourth: mean verifier queries against the number of private steps for dedicated calibration, verification reuse and identify-once.

Multi-Agent Collaboration

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

See all 309 papers

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization
Oct 21, 2026Hanmin Li, Yury Demidovich, Peter RichtárikMulti-Agent Collaboration Multi-Agent System Optimization
King Abdullah University of Science and Technology Thuwal, Saudi Arabia
LLMs Can Predict Failure Risk, But Struggle to Predict Which Collaboration Protocol Pays Off: Cost-Aware Protocol Routing Across Reasoning Tasks
Aug 14, 2026Chih-Hsuan Yang, Jingyan Jiang, Cheng-Hau Yang +4LLM Agent Routing Efficient Language Model Reasoning
Argonne National Laboratory, Lemont, IL, USA · Oregon State University, Corvallis, OR, USA
AgentCollab: A Self-Evaluation-Driven Collaboration Paradigm for Efficient LLM Agents
Mar 27, 2026Wenbo Gao, Renxi Liu, Xian Wang +8LLM Agents LLM Agent Workflow Optimization
Huawei · Hong Kong Polytechnic University

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

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Hanmin Li, Yury Demidovich, Peter Richtárik

King Abdullah University of Science and Technology Thuwal, Saudi Arabia

Multi-Agent Collaboration Multi-Agent System Optimization Distributed Optimization Combinatorial Optimization

Open paper AskPDF arXiv

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.

Abstract

Multi-Agent Collaboration

Explore similar work

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

LLMs Can Predict Failure Risk, But Struggle to Predict Which Collaboration Protocol Pays Off: Cost-Aware Protocol Routing Across Reasoning Tasks

AgentCollab: A Self-Evaluation-Driven Collaboration Paradigm for Efficient LLM Agents