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
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.
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.
SGL
SEQ
MA
MAG
COL
OPT
By model
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, tver=0 (min)
SGL / OPT speedup
OPT / SGL
m
SGL
OPT
tver=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 C5 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 C5 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 C5 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(x0)
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(x0) 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=\nicefrac14
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, tver=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 tver 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,\nicefrac14,1 median-call equivalents. The bottom row varies sequential verification latency over tver=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), tver=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(x0) 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(x0)
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(x0) counts initially failing checks.
Minutes, tver=0
Minutes, tver=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
tver=0
tver=60 s
tver=0
tver=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
C5
Prism
Initial
34.38
19.50
49.25
SGL
12.27
5.92
18.63
SGL-MF ( ≤2× )
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.
Table 18. Wall-time reduction under fractional route-search scheduling. Each pair gives ordinary → 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→12→0
5
Optimistic
23→0
5
Merge all
23→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.
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.
A team of coding agents can look fine agent by agent yet fail as a team: each passes its own tests while the merged result is broken, and single-agent evaluation never catches it. As teams run several LLM coding agents in parallel on one codebase, the agents collide: two rewrite the same function, one codes against a contract a teammate just changed, and integration fails after the work is done. Most coordination tools react (watch for a conflict, then warn), but at agent speed the warning arrives after the wasted edit. We recast the problem as scheduling: take each work item's declared scope, partition the work into disjoint scopes, and order merges along the producer->consumer graph, all up front. We build this planner into Nerveplane and evaluate it with NP-Bench, an environment-grounded three-arm benchmark (no coordination; reactive detection; proactive planning) that verifies integration off a real git merge, both in a deterministic simulation and with live agents. The planner lifts clean-integration from 1/9 to 9/9 scenarios and cuts merge conflicts from 13 to 0, with a gap that grows in the number of agents. On a live breaking contract change it rescues an outcome both baselines miss on every seed: the clean-integration rate rises from 0 (no coordination and reactive detection) to 1.0 on a frontier model and 0.6 on a small one, while agents respect assigned scopes (0/5 leakage). A cross-session memory drops the repeated-mistake rate from 1.00 to 0.00 on strong and weak models alike. We also report a negative result: routing facts to agents does not rescue long-context accuracy at window-fitting scales; its value is cost and capacity, not attention. Across two capability tiers and two vendors, the benefit did not shrink as models got stronger, because it comes from how work is allocated, not model reasoning.
Multi-agent Large Language Model (LLM) systems offer a way to decompose complex tasks, such as coding, through parallelization and context isolation. However, adding agents in practice introduces inter-agent communication overhead, which incurs extra cost and can sometimes offset the efficiency gains. We formalize multi-agent orchestration as a graph partitioning problem that captures the communication-to-computation trade-off: task decomposition can shorten critical-path computation, but cross-agent dependencies require costly context transfer. We instantiate this view in repository-level software engineering and present Cohesion-aware Coder (Co-Coder), which builds dependency graphs from static analysis, isolates structural hub files, partitions the graph via community detection, and executes the partition with a dependency-aware scheduler. Across 28 real-world tasks on DevEval and CodeProjectEval, Co-Coder advances the Pareto-frontier over sequential and file-based parallel baselines as well as Claude Code with Agent Teams, lifting pass rate by up to 14.0%, achieving up to a 2.10x wall-clock speedup, and reducing API cost by up to 35%, with the largest gains on the most dependency-dense projects. Co-coder demonstrates how cohesion-aware orchestration can make parallel coding agents both theoretically grounded and practically efficient, suggesting a broader design principle for multi-agent systems.
Xu Yang, Lunyiu Nie, Ethan Chandra +3
1The University of Texas at Austin · University of Oxford