First Convergence Theory for AI Agent Collaboration via Block Optimization

KAUST professor Peter Richtárik and Ivan Ilin published the paper "Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration" on arXiv on October 22, accompanied by a series of tweets outlining its core ideas and experimental results. This is the first theoretical work to provide convergence guarantees for AI agent collaboration.

Confirmed

• The paper models multi-agent collaboration as block optimization: each agent owns a block of the shared solution, searches over its own local objective, and adds a correction term that measures how its changes affect other blocks.
• Core theorem: after multiple agents run private searches in parallel for H steps, a coordinator verifies each proposal on the global loss and merges the best non-interfering sets of proposals by "coloring" a dependency graph; the merged solution is guaranteed to be no worse than before. The expected convergence rate is α=μ·q(H)/κ, with the correction error determining the lower bound.
• Experimental setup: GPT-OSS-120B serves as the agent, planning routes for 9 robots on a 16×16 grid (3 agents each manage 3 robots, 48 ticks total, with cost covering delivery time and each collision).
• Results: with the correction term, all 40 rounds were collision-free; without it, only 2/20 rounds were collision-free.
• Six-agent search roughly doubles speed compared with single-agent search.

Why it matters

• This work offers the first convergence-theoretic framework for increasingly popular multi-agent LLM systems, formalizing the "local work, global progress" intuition into provable guarantees.
• The experiments show the correction term is critical for multi-agent safety (collision avoidance), offering direct guidance for designing reliable multi-robot and multi-agent scheduling systems.

2026-10-22 ~ 2026-10-22 · 6 related posts

• [source] New paper proves linear convergence for LLM agent teams via block optimization — peter_richtarik · 2026-10-22
• Peter Richtarik outlines multi-agent block-coordinate optimization with verified merges — peter_richtarik · 2026-10-22
• [source] Richtárik proves linear convergence for parallel multi-agent local search, with rate α = μ·q(H)/κ — peter_richtarik · 2026-10-22
• [source] GPT-OSS-120B agents route 9 robots: correction step makes 40/40 runs collision-free, without it only 2/20 survive — peter_richtarik · 2026-10-22

2 near-duplicate retellings: peter_richtarik · peter_richtarik