Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration
Ivan Ilin, Peter Richtárik
cs.MA, cs.AI, cs.LG, math.OC
2026-10-20
Three GPT-OSS-120B agents find collision-free routes in all 40 runs; six agents finish 18-robot routing in about half a single agent's median time.
Hand a shared artifact to several LLM agents and coupling is where the work breaks. A module can pass its own tests and still break a neighbor's interface. A robot can reach its goal on a route that hits another agent's robot. A global check can reject the bad proposal. Rejection does not say which candidate to try next. Protocols in the style of MetaGPT and AutoGen are mostly designed by hand, with no convergence guarantee.
Ilin and Richtárik at KAUST cast collaboration as finite block optimization. The solution is split into blocks, and each agent edits only its own. A correction is added to the local score so the agent can see how its change pulls on the other blocks. A coordinator scores every proposal on the global loss and merges only proposals that do not interfere. The shared loss is not allowed to rise. The team is not a cost cut. It spends more calls and takes work one agent finishes slowly or not at all.
The loss is a sum of factors, and each factor depends on only some blocks. A dependency graph links blocks that share a factor. After coloring, blocks of one color share no factor, so their gains add exactly, and a round keeps at least 1/κ of the verified gain. A separable task has κ = 1 and a zero correction. A single global factor forces κ equal to the number of blocks, so only one block is accepted per round.
Algorithm 1 freezes one base. Every block runs H private search steps, the verifier scores each proposal on the global loss, negative gains are clipped to zero, and the coordinator keeps the color with the largest total gain. The correction is refreshed before search. In routing it prices only cross-agent collisions the verifier has already reported, at 100 per tick. The model never evaluates the formula. The prompt shows the map, the agent's own routes, and the known collisions. An external scorer picks the proposal using local loss plus correction.
Theorem 2 contracts the expected gap at rate α = μ q(H) / κ. Here q is the fraction of the available corrected improvement captured in H steps; with H = 3 that fraction is about two thirds. μ is how much the best single-block improvements cover the remaining gap. If they do not, the state is a single-block trap, and every agent returns its current block. The floor comes from correction error at two points only: a conditional block minimizer, and the proposal actually returned. A uniform bound over all routes exceeds 10^4. On the runs those two errors are 0 and about 40. An exact correction removes the floor. Longer private search cannot.
Coloring separates every pair that might interact, even when this round's proposals do not. Algorithm 2 keeps the checked combination with the lowest global loss. It is never worse than the best color, and the rate then follows the realized number of colors, κ. If there are too many combinations, greedy addition from the best color never raises the loss. When the unknown part of the loss is linear in known features, a sketch-and-project step learns the correction from global evaluations, and the solution and the correction contract together with no floor.
The main task is pathfinding on a 16×16 grid with walls, 48 ticks, and nine robots. The model is GPT-OSS-120B with medium reasoning at temperature 0.6. Three agents own three robots each and answer at most three times per round. Map 1 has optimum 144 and starts at 1476. Map 2 has optimum 147. Each variant has 20 runs, 10 without the correction. Baselines use the same model: one agent that sees every robot, and best-of-W parallel copies, one per teammate. Conflict-based search only certifies the optimum.
| Method | Gap (map 1 / map 2) | Map 1 seconds | 18-robot seconds |
| Single agent | 12.0 / 19.5 | 613 | 1149 |
| best-of-W | 18.9 / 21.6 | 326 | 517 |
| Team Alg. 1 | 5.9 / 7.2 | 481 | 656 |
| Team Alg. 2 | 5.4 / 12.8 | 340 | 452 |
| No correction | 313.1 / 181.4 | 326 | 382 |
Entries are means. The team is safe in all 40 runs, and 39 finish within 9 of the optimum. The single agent hits that line 32 times, best-of-3 hits it 31 times, and 3 of those 40 runs are unsafe. On map 1 the team gap is 5.9, against 12.0 and 18.9 (p<0.001 and p=0.011). On map 2 the means are not cleanly separated; the median still favors the team (p≤0.002). Three parallel agents have a median near four and a half minutes, the team near seven. Without the correction, 2 of 20 runs finish safe. On map 1 every robot is delivered, the remaining collisions are cross-agent, and dropping the collision penalty leaves a gap near 3.1.
With 18 robots and optimum 291, median search is 1200 seconds against 595. Median final gaps are 11, 22.5, and 15.5 for the team, the single agent, and best-of-six. Algorithm 2 accepts 1.7 blocks on rounds that make progress, cuts mean search time by about 30% versus Algorithm 1, and reaches a safe plan in a median under four minutes. Merging with no check raises the loss in 32 of 185 rounds on map 1 and 37 of 148 on map 2, and one final plan still collides.
Substitute the constants measured on each round and the bound holds on every round of every run. With κ = 3 the two-floor bounds end at 396 and 605, against observed mean gaps of 13 and 18. With κ near 1.5 and 1.2, the bound lands within a factor of 3 to 7 of the observed gap, rather than 30 to 60. μ is at least 0.43 and 0.70, and q is about 0.66 and 0.65.
The SQLite controller is not an LLM. On 48 favorable queries, learning edge counts from execution feedback takes 0.65 of the time of counting in advance (4.92 versus 7.53 ms), and 1.64 times as long when costly groups rarely repeat. All 2,000 exact-correction runs of the synthetic task reach the optimum. A correction bias of ν = 2 leaves a floor near 30, and raising H from 8 to 32 does not remove it.
The rate splits into three measurements: how much single-block moves cover the gap, how much local search captures, and how much the merge keeps. Dialogue and after-the-fact rejection do not change the order in which an agent ranks its own candidates. The correction does.
Routing already has an exact solver. It is the testbed because the optimum, the lower bounds, and the block minima can all be computed, so every constant in the theorem can be measured. The fit is search that already has a verifier, cross constraints between parts, and a solution that does not fit in one request. Sparse facts that get reused are cheaper to learn on the way. Dense one-shot facts are cheaper to measure up front.
On map 1 the team averages 47 answers and 0.23 dollars a run, against 28 and 0.16 for one agent. At nine robots, parallel single agents are faster. At eighteen, the six-agent median is about half the single agent's, with better plans. This is a protocol with a linear convergence proof, and one LLM case in which the bound tracks the runs. On a single map, one agent with a clear view of the state also finishes.
Assumption 3 rules out tasks that move only when several blocks change together. Every routing state that starts a round has μ at least 0.43, but six final states within 3 of the optimum are single-block traps. For the LLM agents, q and the correction errors are measured on visited histories. The uniform contraction in Assumption 2 is not certified.
The LLM evidence is two maps, those maps stacked, one model, and at most 20 runs per variant. The prompt moves both protocols, so a comparison has to match prompts first. On map 2, Algorithm 2's mean gap levels off near 13. Six runs miss the early-stop line, against one for Algorithm 1 (p=0.09). The six-agent runs are not new model calls. They replay paired seeds from the two maps round by round, and robots on different floors never meet. There is still no software experiment. The largest tightly coupled LLM team in the study is three agents.