betaFeedback

WorksComputer Science

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

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.

Introduction

Large language model (LLM) agents are increasingly asked to produce artifacts that are too large for a single request, such as software with many modules or plans for many robots. Human organizations handle such work by division of labor, and dividing work among agents promises two benefits. First, each request becomes smaller and easier, so a task that overwhelms one agent can become solvable. Second, the parts can be searched in parallel, so a solution arrives sooner. We do not aim to reduce monetary cost: like a construction crew compared with a single builder, a team spends more in total but completes work that one agent would finish slowly or not at all.

Not every task benefits from a team, and not every team needs coordination. A simple task, like changing a light bulb, is best done by one worker. If the parts do not interact, for example when one agent waters a garden while another goes shopping, agents can simply work in parallel. The interesting and common case lies in between: large tasks whose parts are coupled, such as the modules of a program, the components of an aircraft, or the routes of robots that share a floor. Each part is manageable alone, but a change to one part can change what is best for the others.

Coupling creates a coordination problem: improving each part in isolation need not improve the whole. A module can pass its own tests while violating another module’s interface; a robot can reach its goal along a route that collides with a robot controlled by another agent. A global check can reject a harmful proposal, but rejection does not tell the agent which alternative to try next: it needs information that changes how it ranks its own candidates.

We study this problem through finite block optimization. An agent is a local search procedure, for example an LLM, that owns one block of a shared solution and searches it while the other blocks stay frozen. A correction added to its local objective tells the agent how its changes affect the other blocks. Agents search their corrected objectives in parallel. A verifier then scores each proposal against the current shared solution, and a coloring of the dependency graph selects proposals that do not interfere (see Figure 1). The correction steers the proposals, while verification and coloring ensure that the shared solution never gets worse.

One epoch of Algorithm 1 on a constructed example with illustrative gains

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 f^b∗\hat{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).

We test the protocol with GPT-OSS-120B agents on robot routing, where robots of different agents can collide. A team of three agents finds collision-free plans in every run, better than those of a single agent that controls all robots at once. The same team without corrections rarely avoids collisions. On a larger task, a team of six agents also searches about twice as fast as the single agent in median. The coordinator can even merge interfering proposals once the verifier confirms that together they lower the loss more than the non-interfering ones alone. This rule, which our theory covers, cuts the team’s search time by about 30% and lets it reach low losses sooner than single agents searching in parallel. With constants measured on the runs, the convergence bound holds in every round, so theory and practice agree. Two smaller studies, on query planning in SQLite and on a synthetic objective, explore the theory and its limits further.

Contributions.

  1. We formalize collaborative problem solving as block optimization with corrected local objectives, and introduce a protocol of parallel private search, exact verification and compatible merging (Section 3).

  1. We prove linear convergence with an explicit error floor (Theorem 2). The rate separates task geometry, local search quality and merge compatibility.

  1. We show that the coordinator can accept the best verified combination of the agents’ proposals, keeping the compatible work of interfering blocks, with

the same guarantees and a rate set by how well the proposals actually combine (§ 5).

(4) We show how agents can learn reusable corrections from global evaluations, with a joint convergence rate for the solution and the correction (Appendix § 12.§ 4), and account for calibration, local work and synchronization costs (§ 6 and § 7).

(5) We evaluate the protocol with teams of three and six LLM agents on robot routing and relate the observed convergence to the theorem; a database study shows when acquiring correction information pays off, and a synthetic study confirms the error floor (§ 8).

The appendices contain further theory and examples (Appendix § 12), extended related work (Appendix § 13), and complete experimental protocols and outcomes.

The implementation and code for reproducing our experiments are available at https://github.com/vectozavr/local-work-global-progress.

Notation

All key notation used in this paper is summarized in tabular form in the Notation section before the appendices; see Table 2.

SymbolMeaning
\multicolumn{2}{l}{Shared task, local objectives and corrections}
mmNumber of blocks or agents.
bbBlock or agent index.
Xb,X\mathcal{X}_b,\mathcal{X}Finite block domain and product domain X1×⋯×Xm\mathcal{X}_1 \times\cdots\times\mathcal{X}_m.
x,xb,xbjx,x_b,x_{bj}Shared candidate solution, its block bb, and coordinate jj of that block.
x−b,(x−b,u)x_{-b},(x_{-b},u)All blocks other than bb, and the solution with block bb replaced by uu.
x0,xk,x+x^0,x^k,x^+Initial solution, solution at epoch kk, and solution after the next commit.
u,Ub,Ubku,U_b,U_b^kTrial block value, returned block proposal, and the proposal in epoch kk.
ub∗,x∗u_b^*,x^*A true conditional block minimizer and a global minimizer.
F(x),F∗F(x),F^*Global loss F:X→RF:\mathcal{X}\to\mathbb{R} and its minimum over X\mathcal{X}.
Δ(x),Δ0\Delta(x),\Delta_0Global objective gap F(x)−F∗F(x)-F^* and its initial value Δ(x0)\Delta(x^0).
Lb(u)L_b(u)Available local objective Lb:Xb→RL_b:\mathcal{X}_b\to\mathbb{R}; LL is its one-block example.
fb(u;x)f_b(u;x)Exact conditional global change F(x−b,u)−F(x)F(x_{-b},u)-F(x); fb:Xb×X→Rf_b:\mathcal{X}_b\times\mathcal{X}\to\mathbb{R}.
Db(x)D_b(x)Best true block decrease −min⁡ufb(u;x)-\min_u f_b(u;x).
Rb(u;x)R_b(u;x)Exact anchored correction fb(u;x)−[Lb(u)−Lb(xb)]f_b(u;x)-[L_b(u)-L_b(x_b)]; Rb:Xb×X→RR_b:\mathcal{X}_b\times\mathcal{X}\to\mathbb{R}.
R^b(u;x)\hat{R}_b(u;x)Implemented approximation to the exact correction; R^b:Xb×X→R\hat{R}_b:\mathcal{X}_b\times\mathcal{X}\to\mathbb{R}.
f^b(u;x)\hat{f}_b(u;x)Corrected local change Lb(u)−Lb(xb)+R^b(u;x)L_b(u)-L_b(x_b)+\hat{R}_b(u;x); f^b:Xb×X→R\hat{f}_b:\mathcal{X}_b\times\mathcal{X}\to\mathbb{R}.
f^b∗\hat{f}_b^*Minimum of f^b(⋅;x)\hat{f}_b(\cdot;x) over Xb\mathcal{X}_b.
F^(x)\hat{F}(x)Learned global surrogate G(x)+⟨ϑ^+,φ(x)⟩G(x)+\langle\hat{\vartheta}^{+},\varphi(x)\rangle.
M,ℓa,N(a)M,\ell_a,N(a)Number of objective factors, factor aa, and the blocks on which it depends.
xN(a)x_{N(a)}Subvector indexed by the factor’s block set.
χ(b),κ\chi(b),\kappaColor assigned to block bb and number of colors.
Cj,jk\mathcal{C}_j,j^kColor class {b:χ(b)=j}\{b:\chi(b)=j\}, and the color selected in epoch kk.
gbg_bVerified nonnegative gain max⁡{0,−fb(Ub;x)}\max\{0,-f_b(U_b;x)\}.
SkS^kBlocks committed in epoch kk, the improving blocks of the selected color (Algorithm 1) or the best verified combination (Algorithm 2).
(x−S,US)(x_{-S},U_S)Solution xx with every block b∈Sb\in S replaced by its proposal UbU_b.
Φ(S)\Phi(S)Loss F(x−S,US)F(x_{-S},U_S) of accepting the proposals of the blocks in SS (Section 5).
IkI^kImproving blocks of epoch kk, those with gb>0g_b>0.
ξbb′\xi_{bb'}Interaction of the proposals of blocks bb and b′b': their joint change minus the sum of their single changes; they conflict if ξbb′>0\xi_{bb'}>0.
κ∗k\kappa_*^kRealized number of colors of the best-combination merge in epoch kk: ∑bgb\sum_b g_b over the realized gain (Section 5).
κb,deg⁡k(b)\kappa_b,\deg_k(b)Effective number of colors, the smallest number of conflict-free sets covering IkI^k, and the number of improving blocks that conflict with bb (Section 5); deg⁡(b)\deg(b) in the synthetic task is the degree in the dependency graph.
κˉ\bar{\kappa}Bound for κ∗k\kappa_*^k in every epoch (Corollary 3).
\multicolumn{2}{l}{Convergence and stopping certificates}
k,Kk,KCurrent epoch index and prescribed number of epochs.
HHNumber of private search steps per epoch.
H,Hk\mathcal{H},\mathcal{H}_kHistory conditioning a local search, or history before epoch kk's calibration.
δb∗,δb\delta_b^*,\delta_bTwo-point correction-error bounds (Assumption 1): at a true block minimizer, and in conditional expectation at the returned proposal.
δb\delta_bUniform absolute correction-error bound over block candidates.
ε(u),εb(u)\varepsilon(u),\varepsilon_b(u)Correction error f^(u)−f(u)\hat{f}(u)-f(u) of a candidate in the proofs, and of block bb in Proposition A.2.
Qb,eb∗,ebU,D^bQ_b,e_b^*,e_b^U,\hat{D}_bIn one recorded epoch (Proposition A.2): captured fraction of the corrected improvement, correction errors at a true block minimizer and at the returned proposal, and the available corrected improvement.
ρb,ρ,ρmin⁡\rho_b,\rho,\rho_{\min}Per-step local contraction parameter and its minimum across blocks.
qb(H),q(H)q_b(H),q(H)Captured-improvement guarantee 1−(1−ρb)H1-(1-\rho_b)^H, and its minimum over blocks.
μ\muBlock error-bound constant in ∑bDb(x)≥μΔ(x)\sum_b D_b(x)\geq\mu\Delta(x).
SymbolMeaning (continued)
μfin\mu_{\mathrm{fin}}Capped minimum improvement-to-gap ratio on the finite domain.
f^b\hat{f}_bComputable lower bound on min⁡uf^b(u;x)\min_u \hat{f}_b(u; x).
α\alphaDescent coefficient μq(H)/κ\mu_q(H)/\kappa.
BBCorrection-error term κ−1∑b(qb(H)δb∗+δb)\kappa^{-1}\sum_b(q_b(H)\delta_b^*+\delta_b); at most κ−1∑b(1+qb(H))δb\kappa^{-1}\sum_b(1+q_b(H))\delta_b under a uniform bound.
BδB_\deltaUniform-error counterpart κ−1∑b(1+qb(H))δb\kappa^{-1}\sum_b(1+q_b(H))\delta_b of BB (Appendix A.2).
B/αB/\alphaError floor in the expected-gap bound.
Δk,αk,Bk\Delta_k,\alpha_k,B_kGap after round kk and the round’s measured coefficients in Δk+1≤(1−αk)Δk+Bk\Delta_{k+1}\le(1-\alpha_k)\Delta_k+B_k.
ζ\zetaRelative-error fraction in (1+qb)δb≤ζqbDb(1+q_b)\delta_b\le\zeta q_bD_b.
ε\varepsilonRequested objective-gap tolerance; an expected-gap tolerance where expectation is specified.
Learning corrections from global evaluations
G(x)G(x)Known part of the structured global objective.
φ(x),r\varphi(x),rKnown feature vector in Rr\mathbb{R}^r and its dimension.
ϑ,ϑ^\vartheta,\hat{\vartheta}Fixed unknown coefficients and their retained estimate.
ϑ^k,ϑ^+\hat{\vartheta}^k,\hat{\vartheta}^+Estimate indexed by epoch and estimate immediately after calibration.
c0c_0Unknown additive constant in the objective.
Λb\Lambda_bKnown bound on ∣φ(x−b,u)−φ(x)∣2|\varphi(x_{-b},u)-\varphi(x)|_2.
z,zbz,z_bFeasible calibration probe and singleton proposal (x−b,Ub)(x_{-b},U_b).
a,aba,a_bFeature displacement φ(z)−φ(x)\varphi(z)-\varphi(x), or that of proposal zbz_b.
y,yby,y_bResidual global difference after subtracting the known-part difference.
y−⟨a,ϑ^⟩y-\langle a,\hat{\vartheta}\ranglePrediction residual for the current coefficient estimate.
PPMeasurement projector aa⊤/∣a∣22aa^\top/|a|_2^2; zero for a skipped or zero-length probe.
IIIdentity matrix on the coefficient space.
σ\sigmaExcitation constant in E[P∣Hk]⪰σI\mathbb{E}[P\mid\mathcal{H}_k]\succeq\sigma I.
η\etaLearning contraction factor 1−σ\sqrt{1-\sigma}.
ϑ~,ϑ~+,ϑ~next\tilde{\vartheta},\tilde{\vartheta}^+,\tilde{\vartheta}^{\mathrm{next}}Parameter error ϑ^−ϑ\hat{\vartheta}-\vartheta, after calibration, and after extra reused measurements.
EkE_kUpper envelope of the gap along a recorded run (Proposition A.2).
β\betaConversion coefficient κ−1∑b(1+qb(H))Λb\kappa^{-1}\sum_b(1+q_b(H))\Lambda_b.
ω\omegaPotential weight 2β/(1−η)2\beta/(1-\eta).
τ\tauJoint rate min⁡{α,(1−η)/2}\min\{\alpha,(1-\eta)/2\}.
Vk\mathcal{V}_kJoint potential Δ(xk)+ω∣ϑ^k−ϑ∣2\Delta(x^k)+\omega|\hat{\vartheta}^k-\vartheta|_2.
Binary calibration and observable uncertainty
db,dmax⁡d_b,d_{\max}Number of binary coordinates in block bb, and the largest block dimension.
Ψ(x)\Psi(x)Known coupling function in the coordinate residual model.
ϑbj,ϑ^bj\vartheta_{bj},\hat{\vartheta}_{bj}True and estimated coefficient of binary coordinate (b,j)(b,j).
MbjM_{bj}Known initial bound on ∣ϑbj−ϑ^bj0∣|\vartheta_{bj}-\hat{\vartheta}_{bj}^0|.
ssBit displacement: signed one-bit change zbj−xbj∈{−1,1}z_{bj}-x_{bj}\in\{-1,1\}.
ppProbe probability: probability that a block with unknown coordinates performs calibration.
Ubk,nbU_b^k,n_bRemaining unknown coordinates before epoch kk, and their number in a block.
Γk,Γb,k\Gamma_k,\Gamma_{b,k}Radii: sum of remaining bounds MbjM_{bj} over all blocks, or over block bb.
dtotd_{\mathrm{tot}}Query budget: total number of binary coordinates ∑bdb\sum_b d_b.
γ\gammaRadius contraction parameter p/dmax⁡p/d_{\max}.
ρ0\rho_0Coordinate-model conversion factor κ−1max⁡b(1+qb(H))\kappa^{-1}\max_b(1+q_b(H)).
ω0,τ0\omega_0,\tau_0Radius weight 2β0/γ2\beta_0/\gamma and joint rate min⁡{α,γ/2}\min\{\alpha,\gamma/2\}.
Wk\mathcal{W}_kObservable-radius potential Δ(xk)+ω0Γk\Delta(x^k)+\omega_0\Gamma_k.
MMValue range: width of a known interval of objective values in the impossibility argument.
Private work and cost accounting
ccPrivate cost: modeled cost of one parallel private-search slot.
CCOther per-epoch cost, including synchronization and context preparation; it includes verifier calls in Appendix A.3 and excludes them, charged through vv, in Appendix A.5.
vvCost of one scalar global evaluation.
Kε(H)K_\varepsilon(H)Sufficient epoch count for expected gap at most ε\varepsilon.
Tε(H),TKT_\varepsilon(H),T_KSufficient modeled completion cost and cost through KK epochs.
λ\lambda−log⁡(1−ρ)-\log(1-\rho), the exponential form of the worst-block local rate.
J(H)J(H)Relaxed cost ratio (cH+C)/(1−e−λH)(cH+C)/(1-e^{-\lambda H}).
H∗H_*Positive continuous minimizer of J(H)J(H) for C>0C>0.
ψ(H)\psi(H)Proof helper: eλH−1−λH−λC/ce^{\lambda H}-1-\lambda H-\lambda C/c.
Nq,KendN_q,K_{\mathrm{end}}Synthetic experiments: number of counted global evaluations, and the epoch at which a run completes.
SymbolMeaning (continued)
Robot-routing task and its offline references
ri, ir_i,\ iRobot label and robot index, i=0,…,8i=0,\ldots,8.
Ib\mathcal{I}_bSet of robots owned by team block bb.
WWNumber of single agents searching in parallel in the best-of-WW baseline, equal to the number of team agents.
xi,uix_i,u_iRoutes: accepted and candidate command arrays for robot ii.
(x,y),p(x,y),pGrid coordinates and a free cell in a reference-search state; xx increases rightward and yy downward.
ttRouting tick; the fixed horizon is 48 ticks.
si,gi,pi(t)s_i,g_i,p_i(t)Start, goal and position of robot ii at tick tt.
τi\tau_iFirst goal-arrival tick of a delivered robot.
di(p,gi)d_i(p,g_i)Shortest legal grid distance from cell pp to robot ii’s goal.
ci(xi)c_i(x_i)Delivery cost of robot ii. It equals the arrival tick for a delivered robot, otherwise 100+48+di(pi(48),gi)100+48+d_i(p_i(48),g_i).
Cij(xi,xj)C_{ij}(x_i,x_j)Number of simultaneous vertex and edge-swap conflicts for a robot pair.
Pk\mathcal{P}_kExternal robot pairs discovered before round kk.
R^b(u;xk)\widehat{R}_b(u;x^k)Routing correction: anchored collision-penalty change over the retained external pairs.
ΔLb,ΔR^b\Delta L_b,\Delta\widehat{R}_bChange in local loss and in the retained correction for a proposed route block.
Abpriv(u;xk)A_b^{\mathrm{priv}}(u;x^k)Absolute private score using the retained external pairs.
AballA_b^{\mathrm{all}}Absolute block score using every external pair.
dbd_bRouting bound: sum of shortest distances for robots owned by block bb.
AbCBSA_b^{\mathrm{CBS}}Reference score: absolute score of a collision-free delivered reference plan in the soft-penalty certificate.
Ai,wbA_i,w_bSingle-robot relaxation minimum and joint block witness program.
Cb,missk(u)C_{b,\mathrm{miss}}^k(u)Conflicts involving undiscovered external pairs against frozen peers.
εbk(u)\varepsilon_b^k(u)Realized score error f^b(u;xk)−fb(u;xk)\widehat{f}_b(u;x^k)-f_b(u;x^k).
Qk,b,Qs,k,bQ_{k,b},Q_{s,k,b}Fraction of the corrected improvement captured by a returned block; the counterpart of qb(H)q_b(H).
μobs,μs\mu_{\mathrm{obs}},\mu_sMinimum capped improvement-to-gap ratio over recorded states, or within run ss.
es,k,b∗,es,k,bUe_{s,k,b}^*,e_{s,k,b}^{U}Measured correction errors at a true block minimizer and at the returned block; realized counterparts of δb∗,δbU\delta_b^*,\delta_b^U.
Δs,k\Delta_{s,k}Objective gap for run ss after round kk.
αs,k,Bs,k\alpha_{s,k},B_{s,k}Round-specific descent and correction-error coefficients computed from all returned blocks.
αˉ,Bˉ\bar{\alpha},\bar{B}Pooled arithmetic means of the measured round coefficients.
xsk,Ksx_s^k,K_sAccepted state at round kk in run ss, and that run’s stopping round.
Es,kE_{s,k}Upper envelope for run ss’s objective gap at round kk.
Eˉk,αˉk,Bˉk\bar{E}_k,\bar{\alpha}_k,\bar{B}_kEnvelope propagated with round-kk coefficients averaged over the runs of one half (check on the other half).
UˉK\bar{U}_KMean loss envelope: the optimum plus the mean of Es,min⁡{K,Ks}E_{s,\min\{K,K_s\}}.
ss (replicate), j,k,h,bj,k,h,bRun index; single-agent step, team round, private step and block indices in the API-seed scheme.
aj,akba_j,a_{k b}Measured duration of a checkable model answer.
tkb,tbt_{k b},t_{b}Sum of a block’s checked durations in a round, and the team’s search time.
TparallelT_{\mathrm{parallel}}Search time of the parallel team and of the sequential replay of the same answers.
TsequentialT_{\mathrm{sequential}}Search time of the parallel team and of the sequential replay of the same answers.
ppTop-pp: nucleus-sampling parameter, fixed to 0.95 in routing.
Synthetic optimization experiment
tbj,tˉbjt_{bj},\bar{t}_{bj}Desired target bit and private target bit.
abja_{bj}Unary mismatch weight for bit (b,j)(b,j).
wwNeighbor-coupling weight, fixed at 0.2.
πb\pi_bActivity probability of block bb’s randomized coordinate solver.
Abj(x)A_{bj}(x)Exact affine coefficient of candidate bit ubju_{bj} with peers frozen.
hbj(x)h_{bj}(x)Difference between the exact and private affine coefficients.
A^bj\widehat{A}_{bj}Private coefficient plus learned unary correction and refreshed coupling coefficient.
cb,cdeg(b)c_b,c_{\mathrm{deg}}(b)Total incident coupling weight wdeg⁡(b)w\deg(b) and block degree on the path.
I(x)I(x)Set of coordinates whose bits differ from the desired target.
μdom\mu_{\mathrm{dom}}Unary-dominance certificate min⁡b,j(abj−cb)/(abj+cb)\min_{b,j}(a_{bj}-c_b)/(a_{bj}+c_b).
D^(x)\widehat{D}(x)Sum of all exact affine surrogate improvements at the committed base.
Γ(x)\Gamma(x)Sum of remaining coordinate uncertainty bounds at the current base.
Δ‾(x)\overline{\Delta}(x)Stopping: certified gap bound (D^(x)+Γ(x))/μdom(\widehat{D}(x)+\Gamma(x))/\mu_{\mathrm{dom}}.
νs,bj\nu_{s,bj}Persistent correction bias and its random sign in the approximate-correction series.
eb∗,ebU,Qbe_b^*,e_b^U,Q_bRealized correction errors at a true block minimizer and at the returned proposal, and the realized captured fraction, in the same series.
Database experiment
s,sdbs,s_{\mathrm{db}}Database source index and database-generation seed.
As,Bs,CsA_s,B_s,C_sLeft endpoint, edge and right endpoint tables for source ss.
SymbolMeaning (continued)
gs,hsg_s, h_sSelected left and right endpoint-group IDs.
ℓ,r\ell, rJoin directions: left-first and right-first traversal choices.
q,qs,asq, q_s, a_sQuery/report index, selected predicates for source ss, and its join-direction choice.
vs(ℓ,g),vs(r,h)v_s(\ell, g), v_s(r, h)Edge fan-out of a selected left or right group.
Jq(a),aJ_q(a), aSeparable fan-out surrogate and vector of three join directions.
Mathematical operations and summary conventions
R,Rr\mathbb{R}, \mathbb{R}^rReal numbers and real vectors of dimension rr.
⟨a,a′⟩,aT\langle a,a' \rangle, a^{\mathsf{T}}Euclidean inner product ∑jajaj′\sum_j a_j a'_j and vector or matrix transpose.
∥⋅∥2,∥⋅∥22\lVert\cdot\rVert_2, \lVert\cdot\rVert_2^2Euclidean norm and its square.
∥z−x∥1\lVert z-x \rVert_1Sum of absolute coordinate differences and scalar absolute value.
∣zj−xj∣\lvert z_j-x_j \rvert
E[Z]E[Z]
E[Z∣H]E[Z \mid\mathcal{H}]Expectation and conditional expectation of a random quantity ZZ.
A⪰BA \succeq BPositive-semidefinite matrix order: A−BA-B is positive semidefinite.
:=,=,≤,≥:=, =, \leq, \geqDefinition, equality and scalar inequality relations.
min⁡,max⁡,sup⁡\min, \max, \supMinimum, maximum and supremum over the stated index or candidate set.
∑,×\sum, \timesSum and multiplication or Cartesian product as indicated.
∈,⊆,∅\in, \subseteq, \varnothingMembership, subset relation and empty set.
log⁡,exp⁡,⋅\log, \exp, \sqrt{\cdot}Natural logarithm, exponential and square root.
⌈z⌉\lceil z \rceilSmallest integer greater than or equal to zz.
min⁡{⋅},max⁡{⋅}\min\{\cdot\}, \max\{\cdot\}Minimum or maximum of listed scalar quantities.
≈,O(n)\approx, O(n)Approximation and asymptotic upper-bound notation.
n,±,SD,SEn, \pm, \mathrm{SD}, \mathrm{SE}Sample count, displayed variation, sample standard deviation and standard error.
+,∗+, *A plus superscript marks an update; a star marks an optimum. Hats mark approximations or estimates; a tilde marks the private target of the synthetic task and, in Appendix A.4, a parameter error; bars and underlines mark averages or bounds, as defined in each entry.

Table 2. Notation used in the paper.

Related work

Block optimization and distributed coordination. Block coordinate descent and its convergence theory are classical [1, 48] (Nesterov 2012), as are its parallel and inexact variants [36, 47]. When parallel coordinate updates interfere through shared terms, prior analyses bound the interference [3, 36] or group weakly coupled coordinates [39]. We instead verify every proposal and then either merge only blocks of one color, whose gains add exactly, or check the merged combination as a whole. Distributed constraint optimization assigns coupled variables to agents: MGM coordinates improving moves, DSA randomizes local updates, and DPOP propagates conditional utility tables [22, 55, 34]. Our addition is an explicit interface for correcting candidate values and a bound that converts the correction error into lost global progress.

Persistent corrections and identification. ProxSkip and SCAFFOLD correct local work through control variates [25, 18]. Our corrections play the analogous role for discrete search, adjusting candidate scores of distant blocks rather than gradients; whether they also admit ProxSkip-type acceleration remains open. Our update for learning corrections (§ 6) is a randomized Kaczmarz, or sketch-and-project, step [46, 11], and additive Bayesian optimization and linear-bandit identification also exploit known structure and informative measurements [16, 42].

LLMs as evaluator-guided optimizers. LLMs can serve as search operators when paired with an automatic evaluator. OPRO proposes new solutions from a history of scored ones, and FunSearch and AlphaEvolve evolve programs under automated evaluation [51, 37, 29]. Our agents are such evaluator-guided searchers, each restricted to one block. The theory asks what feedback the evaluator must provide so that parallel block searches add up to global progress.

LLM collaboration and multi-robot planning. MetaGPT and ChatDev coordinate software-development artifacts, and AutoGen composes conversing agents [14, 35] (Wu et al. 2024). GPTSwarm optimizes agent graphs, and AgentPrune removes redundant communication [52] (Zhuge et al. 2024). Reflexion retains feedback-derived text across trials, and EvoMAC adapts collaboration using verification feedback [41] (Hu et al. 2025). Decomposed prompting splits complex tasks into simpler subtasks [19]. In robotics, one LLM agent per robot can negotiate a joint plan through dialogue and re-plan from motion-planner feedback such as collisions [23], and LLMs can decompose instructions and allocate the subtasks among robots [17]. Centralized, decentralized and hybrid LLM planners have also been compared as teams grow [7]. LLMs solve multi-agent path finding on empty maps but still fail on standard maps with obstacles [5], which is the difficulty our routing study targets. These works show empirically that decomposition and feedback help; our analysis states which properties of the agents and of the feedback yield convergence. Appendix B gives a broader comparison.

Model and protocol

This section turns the coordination problem from the introduction into an optimization model. We first define the shared task and the corrected objective that each agent searches (Section 3.1), then the dependency graph that determines which changes can be combined safely (Section 3.2), and finally the protocol that combines them (Section 3.3, Algorithm 1).

Task and corrected objectives

The shared solution is x=(x1,…,xm)x=(x_1,\ldots,x_m): agent bb owns block xbx_b, which takes values in a nonempty finite set Xb\mathcal{X}_b. The team solves

min⁡x∈XF(x),X=X1×⋯×Xm,(1)\min_{x\in\mathcal{X}} F(x), \qquad\mathcal{X}=\mathcal{X}_1\times\cdots\times\mathcal{X}_m, \tag*{(1)}

for a loss F:X→RF:\mathcal{X}\to\mathbb{R}. An exact verifier returns F(x)F(x) for any solution, although its formula need not be known to the agents. Each agent can also cheaply evaluate a local objective Lb:Xb→RL_b:\mathcal{X}_b\to\mathbb{R} of its candidate blocks u∈Xbu\in\mathcal{X}_b, which may ignore how uu interacts with the other blocks.

The optimal loss is F∗F^*, and the conditional change fb(u;x)f_b(u;x) is how much the global loss changes if agent bb alone replaces its block by uu:

F∗:=min⁡x∈XF(x),fb(u;x):=F(x−b,u)−F(x).(2)F^*:=\min_{x\in\mathcal{X}}F(x), \qquad f_b(u;x):=F(x_{-b},u)-F(x). \tag*{(2)}

These quantities serve the analysis; agents need not know them. The exact correction RbR_b is the part of the conditional change that the local objective misses, and an agent searches the corrected objective f^b\hat{f}_b built from an available approximation R^b\hat{R}_b:

Rb(u;x):=fb(u;x)−[Lb(u)−Lb(xb)],(3)R_b(u;x):=f_b(u;x)-[L_b(u)-L_b(x_b)], \tag*{(3)}
f^b(u;x):=Lb(u)−Lb(xb)+R^b(u;x).(4)\hat{f}_b(u;x):=L_b(u)-L_b(x_b)+\hat{R}_b(u;x). \tag*{(4)}

References

  1. [1]D. P. Bertsekas and J. N. Tsitsiklis. 1989. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englewood Cliffs, NJ. https://web.mit.edu/dimitrib/www/pdc.html
  2. [2]E. Bowring, J. P. Pearce, C. Portway, M. Jain, and M. Tambe. 2008. On K-Optimal Distributed Constraint Optimization Algorithms: New Bounds and Algorithms. In AAMAS, Vol. 2, pp. 607–614. https://www.ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0112.pdf
  3. [3]J. K. Bradley, A. Kyrola, D. Dickson, and C. Guestrin. 2011. Parallel Coordinate Descent for L1-Regularized Loss Minimization. Proceedings of the 28th International Conference on Machine Learning (ICML), pages 321–328. https://icml.cc/2011/papers/231_icmlpaper.pdf
  4. [4]M. Cemri, M. Z. Pan, S. Yang, L. A. Agrawal, B. Chopra, R. Tiwari, K. Keutzer, A. Parameswaran, D. Klein, K. Ramchandran, M. A. Zaharia, J. E. Gonzalez, and I. Stoica. 2025. Why Do Multi-Agent LLM Systems Fail? Advances in Neural Information Processing Systems, 38, Datasets and Benchmarks Track, pp. 135676–135729. https://doi.org/10.52202/085713-4082
  5. [5]W. Chen, S. Koenig, and B. Dilkina. 2025. Solving Multi-Agent Path Finding as an LLM Benchmark: How, How Good and Why. Transactions on Machine Learning Research; preprint arXiv:2401.03630. https://arxiv.org/abs/2401.03630
  6. [6]W. Chen, Y. Su, J. Zuo, C. Yang, C. Yuan, C.-M. Chan, H. Yu, Y. Lu, Y.-H. Hung, C. Qian, Y. Qin, X. Cong, R. Xie, Z. Liu, M. Sun, and J. Zhou. 2024b. AgentVerse: Facilitating Multi-Agent Collaboration and Exploring Emergent Behaviors. ICLR. https://openreview.net/forum?id=EHg5GDnyq1arxiv.org/abs/2308.10848
  7. [7]Y. Chen, J. Arkin, Y. Zhang, N. Roy, and C. Fan. 2024a. Scalable Multi-Robot Collaboration with Large Language Models: Centralized or Decentralized Systems? IEEE International Conference on Robotics and Automation (ICRA), pages 4311–4317. https://doi.org/10.1109/ICRA57147.2024.10610676
  8. [8]Y. Dang, C. Qian, X. Luo, F. Jan, Z. Xie, R. Shi, W. Chen, C. Yang, X. Chi, Y. Tian, X. Xiong, L. Han, Z. Liu, and M. Sun. 2025. Multi-Agent Collaboration via Evolving Orchestration. Advances in Neural Information Processing Systems, 38, pp. 182975–183009. https://doi.org/10.52202/085713-5502
  9. [10]Y. Fan, J. Zhang, K. Cai, J. Yang, C. Tang, J. Wang, and K. Wang. 2026. Cost-Effective Communication: An Auction-based Method for Language Agent Interaction. Proceedings of AAAI, 40(35):29412–29420. https://doi.org/10.1609/aaai.v40i35.40182
  10. [11]R. M. Gower and P. Richtárik. 2015. Randomized Iterative Methods for Linear Systems. SIAM Journal on Matrix Analysis and Applications, 36(4):1660–1690. https://doi.org/10.1137/15M1025487
  11. [12]Groq. 2025. What is a Language Processing Unit? Groq blog, 7 March 2025. Accessed 17 October 2026. https://groq.com/blog/the-groq-lpu-explained
  12. [13]Groq. 2026. OpenAI GPT-OSS 120B. Accessed 7 October 2026. https://console.groq.com/docs/model/openai/gpt-oss-120b
  13. [14]S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, C. Zhang, J. Wang, Z. Wang, S. K. S. Yau, Z. Lin, L. Zhou, C. Ruan, L. Xiao, C. Wu, and J. Schmidbauer. 2024. MetaGPT: Meta Programming for a Multi-Agent Collaborative Framework. ICLR. https://arxiv.org/abs/2308.00352
  14. [16]K. Kandasamy, J. Schneider, and B. Poczos. 2015. High Dimensional Bayesian Optimisation and Bandits via Additive Models. In ICML, PMLR 37:295–304. https://proceedings.mlr.press/v37/kandasamy15.htmlarxiv.org/abs/1503.01673
  15. [17]S. S. Kannan, V. L. N. Venkatesh, and B.-C. Min. 2024. SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Models. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 12140–12147. https://doi.org/10.1109/IROS58592.2024.10802322
  16. [18]S. P. Karimireddy, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh. 2020. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. ICML, PMLR 119:5132–5143. https://proceedings.mlr.press/v119/karimireddy20a.htmlarxiv.org/abs/1910.06378
  17. [19]T. Khot, H. Trivedi, M. Finlayson, Y. Fu, K. Richardson, P. Clark, and A. Sabharwal. 2023. Decomposed Prompting: A Modular Approach for Solving Complex Tasks. International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=_nGgZQjzaRyarxiv.org/abs/2210.02406
  18. [20]Y. Kim, K. Gu, C. Park, C. Park, S. Schmidgall, A. A. Heydari, Y. Yan, Z. Zhang, Y. Zhuang, Y. Liu, M. Malhotra, P. P. Liang, H. W. Park, Y. Yang, X. Xu, Y. Du, S. Patel, T. Althoff, D. McDuff, and X. Liu. 2026. Towards a Science of Scaling Agent Systems. arXiv:2512.08296v3, revised April 2026 (first posted 2025). https://arxiv.org/abs/2512.08296v3
  19. [21]Z. Liu, Y. Zhang, P. Li, Y. Liu, and D. Yang. 2024. A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration. COLM. https://openreview.net/forum?id=XII0Wp1XA9arxiv.org/abs/2310.02170
  20. [22]R. T. Maheswaran, J. P. Pearce, and M. Tambe. 2004. Distributed Algorithms for DCOP: A Graphical-Game-Based Approach. In Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS).
  21. [23]Z. Mandi, S. Jain, and S. Song. 2024. RoCo: Dialectic Multi-Robot Collaboration with Large Language Models. IEEE International Conference on Robotics and Automation (ICRA), pages 286–299. https://doi.org/10.1109/ICRA57147.2024.10610855
  22. [24]R. Marcus, P. Negi, H. Mao, N. Tatbul, M. Alizadeh, and T. Kraska. 2021. Making Learned Query Optimization Practical. In SIGMOD, pp. 1275–1288. https://doi.org/10.1145/3448016.3452838
  23. [25]K. Mishchenko, G. Malinovsky, S. U. Stich, and P. Richtárik. 2022. ProxSkip: Yes! Local Gradient Steps Probably Lead to Communication Acceleration! Finally! ICML, PMLR 162:15750–15769. https://proceedings.mlr.press/v162/mishchenko22b.htmlarxiv.org/abs/2202.09357
  24. [26]D. Monderer and L. S. Shapley. 1996. Potential Games. Games and Economic Behavior, 14(1):124–143. https://doi.org/10.1006/game.1996.0044
  25. [27]K. Murota. 2003. Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications, Vol. 10. SIAM, Philadelphia, PA. https://doi.org/10.1137/1.9780898718508
  26. [29]A. Novikov, N. V u, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog. 2025. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131. https://arxiv.org/abs/2506.13131
  27. [30]OpenAI. 2025. gpt-oss-120b & gpt-oss-20b Model Card. arXiv:2508.10925. doi:10.48550/arXiv.2508.10925
  28. [31]OpenRouter. 2026. Provider Routing. Accessed 7 October 2026. https://openrouter.ai/docs/guides/routing/provider-selection
  29. [32]J. Park, V. Kontonis, S. Garg, A. Krishnamurthy, and D. Papailiopoulos. 2026. Scaling discovery through test-time communication. arXiv:2609.21032. https://arxiv.org/abs/2609.21032
  30. [33]D. L. Parnas. 1972. On the Criteria To Be Used in Decomposing Systems into Modules. Communications of the ACM, 15(12):1053–1058. https://doi.org/10.1145/361598.361623
  31. [34]A. Petcu and B. Faltings. 2005. A Scalable Method for Multiagent Constraint Optimization. IJCAI, pp. 266–271. https://www.ijcai.org/Proceedings/05/Papers/0445.pdf
  32. [35]C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, J. Xu, D. Li, Z. Liu, and M. Sun. 2024. ChatDev: Communicative Agents for Software Development. Proceedings of ACL, pages 15174–15186. https://doi.org/10.18653/v1/2024.acl-long.810
  33. [36]P. Richtárik and M. Takáč. 2016. Parallel Coordinate Descent Methods for Big Data Optimization. Mathematical Programming, 156(1–2):433–484. https://doi.org/10.1007/s10107-015-0901-6
  34. [37]B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi. 2024. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475. https://doi.org/10.1038/s41586-023-06924-6
  35. [38]S. Sakai, M. Togasaki, and K. Yamazaki. 2003. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics 126, 2–3 (2003), 313–322.DOI
  36. [39]C. Scherrer, A. Tewari, M. H. Kalapanavar, and D. Haglin. 2012. Feature Clustering for Accelerating Parallel Coordinate Descent. Advances in Neural Information Processing Systems 25 (NIPS 2012). https://proceedings.neurips.cc/paper/2012/hash/4e732ced3463d06de0c a9a15b6153677-Abstract.htmlarxiv.org/abs/1212.4174
  37. [40]G. Sharon, R. Stern, A. Felner, and N. Sturtevant. 2012. Conflict-Based Search For Optimal Multi-Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 26. AAAI Press, Palo Alto, CA, 563–569. doi:10.1609/aaai.v26i1.8140
  38. [41]N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. 2023. Reflexion: Language Agents with Verbal Reinforcement Learning. In Advances in Neural Information Processing Systems, 36, pp. 8634–8652. https://proceedings.neurips.cc/paper_files/paper/2023/hash /1b44b878bb782e6954cd888628510e90-Abstract-Conference.html
  39. [42]M. Soare, A. Lazaric, and R. Munos. 2014. Best-Arm Identification in Linear Bandits. In Advances in Neural Information Processing Systems, 27, pp. 828–836. https://arxiv.org/abs/1409.6110
  40. [43]SQLite. 2026. Prepared Statement Scan Status; Prepared Statement Scan Status Opcodes. Documentation, accessed September 2026. https://www.sqlite.org/c3ref/stmt_scanstatus.html; https://www.sqlite.org/c3ref/c_scanstat_est.html.
  41. [44]R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Barták. 2019. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. In Proceedings of the Twelfth International Symposium on Combinatorial Search (SoCS), Vol. 10. AAAI Press, Palo Alto, CA, 151–158. doi:10.1609/socs.v10i1.18510
  42. [45]M. Stillger, G. M. Lohman, V. Markl, and M. Kandil. 2001. LEO—DB2’s Learning Optimizer. In VLDB, pp. 19–28. https://research.ibm.com/publications/leo-db2s-learning-optimizer
  43. [46]T. Strohmer and R. Vershynin. 2009. A Randomized Kaczmarz Algorithm with Exponential Convergence. Journal of Fourier Analysis and Applications, 15(2):262–278. https://doi.org/10.1007/s00041-008-9030-4
  44. [47]R. Tappenden, P. Richtárik, and J. Gondzio. 2016. Inexact Coordinate Descent: Complexity and Preconditioning. Journal of Optimization Theory and Applications, 170(1):144–176. https://doi.org/10.1007/s10957-016-0867-4
  45. [48]P. Tseng. 2001. Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization. Journal of Optimization Theory and Applications, 109(3):475–494. https://doi.org/10.1023/A:1017501703105
  46. [49]Z. Wang, Y. Wang, X. Liu, L. Ding, M. Zhang, J. Liu, and M. Zhang. 2025. AgentDropout: Dynamic Agent Elimination for Token-Efficient and High-Performance LLM-Based Multi-Agent Collaboration. Proceedings of ACL, pages 24013–24035. https://doi.org/10.18653/v1/2025.acl-long.1170
  47. [51]C. Yang, X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen. 2024. Large Language Models as Optimizers. International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=bB4VG0WELIarxiv.org/abs/2309.03409
  48. [52]G. Zhang, Y. Yue, Z. Li, S. Yun, G. Wan, K. Wang, D. Cheng, J. X. Yu, and T. Chen. 2025b. Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems. ICLR. https://arxiv.org/abs/2410.02506
  49. [53]G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, T. Chen, and D. Cheng. 2025c. G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks. Proceedings of ICML, PMLR 267:76678–76692. https://proceedings.mlr.press/v267/zhang25cu.htmlarxiv.org/abs/2410.11782
  50. [54]J. Zhang, J. Xiang, Z. Yu, F. Teng, X. Chen, J. Chen, M. Zhuge, X. Cheng, S. Hong, J. Wang, B. Zheng, B. Liu, Y. Luo, and C. Wu. 2025a. AFlow: Automating Agentic Workflow Generation. ICLR. https://arxiv.org/abs/2410.10762
  51. [55]W. Zhang, G. Wang, Z. Xing, and L. Wittenburg. 2005. Distributed stochastic search and distributed bracket: properties, comparison and applications to constraint optimization problems in sensor networks. Artificial Intelligence, 161(1–2):55–87. https://doi.org/10.1016/j.artint.2004.10.004
  52. [56]X. Zhang, Z. Wang, Z. Li, J. Yao, and J. Li. 2026. CommCP: Efficient Multi-Agent Coordination via LLM-Based Communication with Conformal Prediction. ICRA, 2026; arXiv:2602.06038. https://arxiv.org/abs/2602.06038

Paper details

vlnc:W_8fczmff4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents