Verified Block Decomposition for Agent Teams

Sources#

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

Summary#

Ivan Ilin and Peter Richtárik (Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration, KAUST, arXiv 2610.28286, 2026-10-20, empirical) treat a team of LLM agents working on one shared artifact as finite block optimization. Each agent owns one block of the solution and searches it while the other blocks stay frozen. It is steered by its own local objective plus a correction, which tells it how its candidates change the parts other agents own. A verifier scores every proposal against the global loss on a common base, and a coordinator merges only proposals that cannot interfere, or a combination it has checked as a whole. The shared solution therefore never gets worse.

The paper is the first source in this vault to state, with a proof, which properties of the agents and the feedback make parallel local work add up to global progress. Earlier multi-agent sources measure whether a team helps (OrchBench, Li et al., Anthropic's swarm). The rate it proves separates three factors: how much single-block moves can achieve, how good each agent's search is, and how much of the verified gain the merge can keep. The error floor depends on one thing only, how accurate the correction is.

The experiments back the mechanism more than the speed claim. On a GPT-OSS-120B multi-robot routing task, the three-agent team reached a safe plan (every robot delivered, no collisions) in all 40 runs on two maps and ended with the smallest gap to the optimum. The same team without the correction was safe in 2 of 20 runs. Three parallel single agents were faster than the team but produced worse plans.

The model#

• Blocks and loss. The solution is x = (x₁, …, x_m), and agent b owns block x_b over a finite set. The team minimizes a global loss F, which an exact verifier can evaluate even when the agents do not know its formula.
• Local objective and correction. Each agent can cheaply score its candidates with a local objective L_b, which ignores how its block interacts with the others. The exact correction R_b is the part of the true change in F that L_b misses. The agent searches L_b plus an approximate correction R̂_b. The correction must be anchored: keeping the current block scores zero. It must also vary with the candidate, because adding the same constant to every candidate cannot change the ranking. For an LLM agent, the correction need not be a formula. It is the information in the prompt, such as the collisions the verifier has already reported.
• Dependency graph and coloring. Write F as a sum of factors, each depending on a set of blocks. Two blocks are adjacent when some factor depends on both. A proper coloring with κ colors puts adjacent blocks in different color classes. Changes inside one color class touch each factor at most once, so their gains add exactly.
• One epoch (Algorithm 1). Every agent searches its corrected objective for H private steps from the same frozen base. The verifier computes each proposal's gain on its own, and the coordinator accepts the improving proposals of the color with the largest total gain. That keeps at least 1/κ of the total verified gain, and the loss never rises. Applying every individually helpful proposal at once could raise it, because adjacent blocks share factors.

Fewer colors are better. A separable task has κ = 1 and needs no correction. That is the "one waters the garden, another goes shopping" case, where plain parallelism already works and the theory adds nothing. A task with a single global factor has a complete graph, κ = m, and only one block can change per epoch. Corrections and coloring matter exactly when blocks share factors, and the strength of that coupling, not the number of agents, decides how much they matter.

The guarantee#

Three assumptions, each with a constant measured on the runs:

1. Anchored correction accuracy (δ). The correction error is bounded at only two candidates, a true block minimizer and the proposal the agent actually returns, not uniformly over every candidate. In routing a uniform bound exceeds 10⁴. The measured errors are zero at the true block minimizers and about 40 on average at the returned proposals.
2. Local contraction (q). In H private steps an agent captures a fixed expected fraction of the available corrected improvement. LLM agents captured about two thirds of it (0.66 and 0.65 on the two maps) in H = 3 answers.
3. Block error bound (μ). Together, single-block improvements are worth at least μ times the remaining gap. This rules out single-block traps, states that only a coordinated change of two or more blocks can improve, such as two modules whose shared interface must be edited in both at once. In routing, μ is at least 0.43 on map 1 and 0.70 on map 2 at every state that starts a round. Six final states, all within 3 of the optimum, were traps.

Theorem 2. With α = μ·q(H)/κ, the expected gap after K epochs is at most (1 − α)^K times the initial gap, plus a floor B/α, where B is the summed correction error divided by κ. Exact corrections give geometric decay to zero. More private search improves only q. It cannot push the floor below roughly Σ(δ)/μ. Only a more accurate correction lowers it. The floor is an upper bound, not a level where the search must stall. If a correction error does not change which candidate ranks best, nothing is lost. In the synthetic task, biases below the smallest coefficient magnitude (0.605) left every run at the optimum.

Private work against synchronization (§7). With step cost c and synchronization cost C (building the correction, transferring context, verifying), the cost-minimizing private horizon grows with C, at about √(2C/(cλ)) when C is small. The more expensive synchronization is, the longer agents should work alone between checks.

Keeping the work the coloring throws away#

The coloring is built for the worst case. It separates every pair of blocks that could interact, whether or not this epoch's proposals do. In routing, any two agents' robots can collide, so κ = 3 and Algorithm 1 accepts one block per round. In 79 of 121 progressing rounds on map 1, and 64 of 115 on map 2, at least one discarded proposal would also have lowered the loss. Each counted on its own, the improving proposals of a round gained 1.5× as much as the accepted one.

Algorithm 2 (best-combination merge) checks combinations of proposals and accepts the one with the lowest verified loss. That is 2³ − 1 = 7 checks for three agents. A greedy version adds one block at a time and needs about |I|²/2 checks under pairwise coupling, instead of 2^m. Because the best-color set is one of the candidates, the merge never gains less than Algorithm 1, and Theorem 2 still holds. The rate then depends on the realized number of colors κ*, how many "colors' worth" of the verified gain the merge actually lost. It is bounded in advance by d + 1, where d is the most conflicts any improving proposal has. On a densely coupled task κ grows with the number of agents, but d + 1 need not.

Measured: Team (Alg. 2) updates 1.7 blocks per progressing round, with κ* averaging about 1.2 against κ = 3. Its whole search is about 30% shorter in mean than Algorithm 1's (p < 0.05 on every task), and it reaches a safe plan 40–50% sooner (median under four minutes on every task). It reaches a safe plan sooner than the parallel single agents too, by 22–39%, significantly on map 2 and two floors but not on map 1 (p = 0.27). The control matters: Team unsafe, which merges every changed block without a check, is not faster. Its plan got worse in 32 of 185 rounds on map 1 and 37 of 148 on map 2, and one final plan kept a collision. Merging more pays only when the merged combination is verified.

Coupling rises, then falls. Since Algorithm 2 checks every combination, its runs show which proposals actually conflict. In round 1 nearly every agent improves its block and the new routes collide (34 of 58 proposal pairs conflict on map 1). A plan with no collisions goes to 2.3–3.3 collisions on average, because delivering robots is worth more than a collision costs. A repair phase follows. Once the plan is safe the task is nearly decoupled, with κ_k averaging 1.03–1.04. The worst case κ_k = 3 occurred in 8 of 105 multi-proposal rounds, 6 of them in round 1. The authors expect the same arc in any shared task: parts changed independently must then be reconciled, and near a good solution few changes remain. A merge rule that adapts to the conflicts that actually occur pays for coupling only while it lasts.

The routing experiment#

• Task. Nine robots on a 16 × 16 grid with walls and a 48-tick horizon. The loss is arrival ticks, plus 148 + remaining distance for any robot not delivered, plus 100 per collision tick. The optimum is certified (F* = 144 on map 1, 147 on map 2) because multi-agent pathfinding has exact solvers, so every constant of the theory can be measured. LLMs still fail at multi-agent pathfinding on maps with obstacles, which is why this task was chosen.
• Agents. GPT-OSS-120B at medium reasoning, temperature 0.6, served by Groq via OpenRouter. Each team agent owns three robots. Its correction is the change in collision penalty for robot pairs the verifier has already reported, computed against the other robots' current routes. The LLM never computes the objective. It searches using what its prompt shows, and the system scores each attempt.
• Baselines. A single agent that sees all nine robots and rewrites one route per answer, the most reliable single-agent protocol they found. Best-of-W, which runs W copies of the single agent in parallel and matches the team's parallelism. Both use the same model and the same kind of prompt. 20 runs per variant per map, 10 for the no-correction team.

(Table 1, mean ± SD; Team unsafe row omitted. Reconciled against the prose and Appendix D.5: 40/40 team runs safe, no-correction 2/20 safe, single-agent final loss 156.00 and team 149.90 on map 1 = gaps 12.0 and 5.9, search 613.0 and 481.0 s.)

• The team gives the best and most consistent plans. It met the stopping threshold in 39 of 40 runs, against 32 for the single agent and 31 for best-of-three. Its mean gap on map 1 is lower (permutation p < 0.001 vs single, p = 0.011 vs best-of-three), and its median gap on map 2 is lower (p ≤ 0.002). Three single agents in parallel were the fastest, with a median of about 4.5 minutes against 7 for the team, but 3 of their 40 runs ended unsafe. At nine robots, parallel search buys speed, and decomposition with corrections buys the best plans.
• The correction is what resolves the coupling. Without it, every map-1 run delivers all nine robots but keeps one to five collisions, all between robots of different agents. Without the collision penalties its gap would average 3.1, close to the corrected team's 5.9. In 6 of 10 runs on map 1, and 7 of 10 on map 2, the plan freezes. Each agent's robots take shortest routes that avoid each other, every block is optimal for its own objective, so no agent can improve, and the plan keeps its collisions. Each part is solved, and what remains is the interaction between parts that no agent can see.
• Two floors (18 robots, six agents). The team's median search is 595 s, against the single agent's 1200 s (p < 0.001). Its median final gap is 11, against 22.5 and 15.5 for best-of-six (p ≤ 0.004). Read the "about 2× faster" result carefully. The floors never interact, so the dependency graph is two disconnected triangles, and the six-agent team runs are assembled from the recorded single-map runs played side by side, with no new model calls. The single agent, by contrast, sees both floors in one prompt and needs 63 answers on average. The speedup is two decoupled three-agent teams running at once against one agent carrying both. Best-of-six is faster than Team (Alg. 1) in mean (517 vs 656 s, p = 0.01), though not in median.
• Cost. The team asks the model more often: 47 answers against 28 on map 1, costing USD 0.23 per run against 0.16. As the authors say, they do not aim to reduce cost. Like a construction crew, a team spends more in total and finishes what one worker would finish slowly or not at all.
• The bound holds round by round. Computing α_k and B_k from each round's measurements, with nothing fitted to the loss curve, the recurrence bounds the gap in every round of every run under both merge rules. Coefficients from 10 runs bound the mean gap of the other 10. With κ = 3 the bound is loose, ending at 396 against an observed 13 on two floors. With the realized κ* it ends within 3–7× of the observed gap, against 30–60× with κ. The correction error at returned proposals starts near 100 (one unknown collision) and falls to a few units within six or seven rounds. With Algorithm 2 it falls faster, to 19 by round 3 against 56, because every collision found in its combination checks also becomes known to the correction.

Two smaller studies. In SQLite query planning, a deterministic controller learns edge counts from execution feedback, LEO/Bao-style, instead of counting in advance. It takes 0.65× the time on a favorable stream where costly groups recur, 0.84× over 192 queries, and 1.64× on a balanced stream where they rarely recur. Learning a correction pays only when the needed information is sparse and reused. In the synthetic task (6 blocks × 8 bits on a path, all constants certified), every one of 2,000 exact-correction runs reaches the optimum at every horizon. All 2,000 uncorrected runs at H = 8 stall at mean gap 31. Corrections biased above the smallest coefficient leave a floor (3.08 at ν = 1, 30.0 at ν = 2) that H = 32 does not lower. Longer private work cannot buy back correction error.

What it means for agent teams#

• The verifier is the merge gate, not just the scorer. The design rules the authors end on are corrections built from verified interactions, proposals verified against a common base, and merges that are either verified as a whole or limited to non-interacting changes. Each rule has a failing counterpart in the corpus. Li et al.'s largest failure class is shared state and merge (33.2%: deliverable overwrite, same-file collision), which is an unverified merge of interfering blocks. Cursor's >70,000 merge conflicts on Parallel Agent Orchestration were cut by a third-party merge agent, which is a coordinator. The theory says why "Team unsafe" fails: applying every individually helpful change at once can raise the global loss whenever blocks share factors.
• Siloing is the uncorrected fixed point. The no-correction team freezes in a plan where every block is locally optimal and the remaining loss is all interaction. That is the theory's version of the Opus 4.8 / Mythos behavior on Parallel Agent Orchestration, where agents avoid shared files, merge fraction scores well, and the product is bad. A local objective plus a global check that only rejects is not enough. Rejection does not tell an agent which alternative to try next, and the correction does.
• The dependency structure is the variable, not headcount. The rate's 1/κ (or 1/(d + 1) with checked merges) is set by how the blocks couple. That is the formal version of the dividing line Anthropic drew between its vulnerability swarm (independent outputs, coordination paid) and its game swarm (interdependent outputs, it did not). It also matches OrchBench's finding that agent count does not predict quality.
• Where this sits against OrchBench's context-overflow reading. OrchBench finds the multi-agent advantage is a context-capacity effect that vanishes once the working state fits one window. Here the single agent's nine-robot state fits its prompt easily, and the team still produces better plans (5.9 vs 12.0 on map 1). The mechanism is different: each request is smaller and easier to search, and a correction plus a verified merge stitches the parts back together. This is a qualification, not a contradiction. One open-weight model on one small, certifiable task is far narrower than OrchBench's DAG sweep, and parallel single agents still win on speed at this size.

How much to believe#

• Theory: clean and self-limiting. The proofs are short, the constants are stated where they must hold (every base the run reaches), and the authors concede that the uniform local-contraction assumption cannot be certified for LLM agents, only measured on visited histories. Assumption 3 excludes single-block traps by construction, and a few routing end states near the optimum are exactly such traps. Combining proposals cannot escape a trap, because with exact corrections no agent proposes the needed move.
• LLM evidence: narrow. One model (GPT-OSS-120B), two maps plus their two-floor combination, at most 20 runs per variant. The two-floor team is a replay of the single-map runs, not a separate six-agent run. On a single map, a single agent with a well-presented state also solves the task, and parallel single agents are faster than Team (Alg. 1).
• The prompt moves both protocols a lot (Appendix D). Moving from prompt v1 to v2 raised the single agent's safe rate from 9/10 to 20/20 and shortened both protocols' searches. Under v1, a single model writing all nine routes at once was safe in 1 of 10 runs. The authors' rule is to match prompts before comparing protocols. That applies to every single- versus multi-agent comparison in this vault.
• Software is the stated motivation but untested. The authors started with code and dropped it. Good design keeps modules apart, so strong coupling between agent-owned parts appears only in large systems, where the optimum is unknown and the interactions cannot be attributed. They name a coupling-measurable coding benchmark as the next step.
• Clean on COI. Academic authors, KAUST funding, open-weight model, code released (github.com/vectozavr/local-work-global-progress).

Connections#

• Multi-Agent Collective Intelligence — the first controlled datum on homogeneous-collective synergy where the gain is neither a context-capacity effect nor more parallel samples. The team beats a parallelism-matched best-of-W on plan quality, but only with the correction
• Parallel Agent Orchestration — the verified-merge rule is the formal version of Cursor's merge agent, and the no-correction freeze is the siloing failure Anthropic's swarm scored well on
• Orchestration-Plan Simulation — agent count does not set the rate; the coupling structure does. A real-agent case where the team wins on quality without context overflow
• Dynamic Concurrency in Coding Agents — its shared-state-and-merge failure class (33.2%) is the unverified merge of interfering blocks that Theorem 2's coloring and Algorithm 2's check exist to prevent
• Dynamic Workflows: An Algebra for Agents — the vendor version of the pitch: Anthropic sells flows as "discrete, verifiable units of work" merged without the developer managing the interconnections, with no exact global verifier or interaction correction named
• Global Proof Coordination — the same coordinator-plus-exact-verifier shape in Lean proving, where workers return structured diagnoses instead of corrections and the coordinator may rewrite the decomposition itself, retracting proved blocks. Its decompose-only ablation, which has no coordinator, ties a single agent
• Verification as the New Bottleneck — an exact global verifier is the protocol's load-bearing component. Without it the coordinator cannot gate merges, and the correction cannot learn new interactions

Open Questions#

• Does verified block decomposition beat a single agent on a coding task with strong, measurable coupling between agent-owned modules? Settler: the benchmark the authors call the next step, a large codebase split across agents with test failures attributable to cross-module interactions and a known-optimal or certified reference, run with and without corrections.
• Does the team's quality edge over parallel single agents survive at larger scale, with stronger models and more than three agents on one coupled graph, rather than two decoupled triangles? Settler: a single-floor routing or MAPF run with 6–12 agents sharing one map, across two or more frontier models, reporting safe rate, gap, κ* and wall-clock against best-of-W.

Sources#

• Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration — Ivan Ilin & Peter Richtárik (KAUST), Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration, arXiv 2610.28286, 2026-10-20, 59 pp, empirical (theory plus experiments). Cited for §3 (model, coloring, Algorithm 1), §4 (Assumptions 1–3, Lemma 1, Theorem 2), §5 (Algorithm 2, Corollary 3, Proposition 4), §6–7 (learned corrections, private-horizon cost), §8 (routing, SQLite, synthetic), §9 (limitations), Appendix C.1 (why routing, not software) and Appendix D.5–D.6 (prompt effects). Table 1 was reconciled before citing: each cell holds one mean ± SD, the six rows match the six variants the prose describes, and the safe rates, single-agent and team map-1 gaps, and search times recompute from the prose and Appendix D.5. Figures 1–5 were not opened. Every figure-derived number here comes from the prose and captions