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
在带校正的块优化里，GPT-OSS-120B三人组四十次运行全部无碰撞，六人团队中位搜索时间约是单智能体的一半。
LLM 智能体分头改一份共享方案时，耦合会把局部改进变成全局退步。模块测试过了，接口却弄坏别人；机器人到了终点，却撞上另一台。全局否决能删掉坏提案，说不出下一次该试哪条。MetaGPT、AutoGen 一类协议凭经验设计，没有收敛保证。
KAUST 的 Ilin 与 Richtárik 把协作写成有限块优化：解切成块，每人只改自己那块，局部目标加校正，说明改动如何牵动别人。协调者按全局损失验收，只合并互不干扰的提案，损失不许变差。团队不省钱，调用更多，换单智能体做不快的任务。
损失是若干因子之和，每个因子只依赖一部分块。依赖图把共享因子的块连起来，着色后同色块不共享因子，收益精确相加，一轮至少留下已验证收益的 1/κ。完全可分时 κ=1，校正为零。全耦合时 κ 等于块数，每轮只能收一块。
Algorithm 1 让各块在同一份冻结底稿上做 H 步私有搜索，验证器计算每份提案的全局收益，变差记 0，协调者收下总收益最大的颜色。校正在搜索前更新。路径规划里，它只对已经报告的跨智能体碰撞计价，每个时间步罚 100。模型不算公式。提示词给出地图、己方路线和已知碰撞，外部打分器用局部损失加校正选题。
Theorem 2 的收缩率是 α = μ q(H) / κ。q 是 H 步吃掉的校正改进比例，这里 H=3，大约三分之二。μ 是单块最大改进盖住剩余间隙的比例，盖不住就是单块陷阱：必须几块一起改，谁也交不出新提案。地板来自校正误差，而且只要求两个点准，条件最优，以及实际提案。对全部路线做一致界会超过 10^4，运行中这两处是 0 和平均约 40。校正精确则地板消失，把搜索加长也压不掉。
着色按一切可能的交互来分，当轮提案却常常不冲突。Algorithm 2 改收全局损失最低的组合，不低于最好的单色，速率改看实现颜色数 κ。组合太多，就从最佳单色贪心添加，损失只降不升。未知部分若对已知特征线性，每次全局评估是一个线性方程，权重用 sketch-and-project 更新，解和校正可以一起线性收敛，没有地板。
实验是 16×16 网格上的路径规划，有墙，48 步，九个机器人，模型 GPT-OSS-120B（medium reasoning，温度 0.6）。三个智能体各管三台，每轮最多回答 3 次。地图 1 最优 144，起点 1476；地图 2 最优 147。各 20 次运行，无校正为 10 次。对照是同一模型的单智能体，以及人数相同的并行单智能体 best-of-W。冲突搜索只用来认证最优。
| 方法 | 间隙（图1/图2） | 图1搜索秒 | 18机器人秒 |
| 单智能体 | 12.0 / 19.5 | 613 | 1149 |
| best-of-W | 18.9 / 21.6 | 326 | 517 |
| 团队 Alg.1 | 5.9 / 7.2 | 481 | 656 |
| 团队 Alg.2 | 5.4 / 12.8 | 340 | 452 |
| 无校正 | 313.1 / 181.4 | 326 | 382 |
均为均值。团队 40 次全部安全，39 次离最优不到 9。单智能体到达该线 32 次，并行三人 31 次，另有 3 次不安全。地图 1 上团队间隙 5.9，低于 12.0 和 18.9（p<0.001，p=0.011）。地图 2 的均值差距不显著，中位数仍更好（p≤0.002）。并行三人中位约四分半钟，团队约七分钟。无校正的 20 次仅 2 次安全：地图 1 上机器人都能送达，碰撞留在智能体之间，去掉罚分后间隙约 3.1。
18 个机器人、最优 291 时，中位搜索是 1200 秒对 595 秒。终间隙中位，团队、单智能体、best-of-6 为 11、22.5、15.5。Algorithm 2 在有进步的轮次平均收下 1.7 块，平均搜索比 Algorithm 1 短约 30%，到达安全方案的中位不到四分钟。不检查就合并，地图 1 的 185 轮有 32 轮变差，地图 2 的 148 轮有 37 轮变差，一份终稿仍有碰撞。
把当轮测到的常数代入递推，界在每一轮、每一次运行都成立。κ=3 时两层楼的界收到 396 和 605，观测平均间隙是 13 和 18。κ 约 1.5 和 1.2 时，界落到观测的 3 到 7 倍，而不是 κ=3 时的 30 到 60 倍。μ 至少 0.43 和 0.70，q 约 0.66 和 0.65。
SQLite 上控制器不是 LLM。48 条有利查询里，从执行反馈学边数的用时是事先清点的 0.65 倍（4.92 对 7.53 毫秒）；很少复用时要 1.64 倍。合成任务 2000 次精确校正全部到达最优。偏差 ν=2 时地板约 30，H 从 8 加到 32 也去不掉。
速率拆成三件可测的事：单块改进覆盖多少间隙，本地搜索抓住多少，合并留下多少。对话和事后否决不改变智能体给自己候选打分的次序，校正会。
路径规划有精确求解器。拿它做实验，是因为最优、下界和单块最小值都能算，定理里的常数量得到。用得上的场合，是已有自动验证器、部分之间有交叉约束、一次请求塞不下。缺的信息稀疏且会复用，边做边学更省；又密又只用一次，事先量完更便宜。
地图 1 上团队平均 47 次回答、0.23 美元，单智能体 28 次、0.16 美元。九个机器人时，并行单智能体更快。十八个时，六人团队的中位时间大约是单智能体的一半，方案更好。这是一套有线性收敛证明的协议，加上一个被界跟住的 LLM 案例。单张地图上，状态摆清楚的单智能体也能做完。
Assumption 3 排除必须几块一起改才有进步的任务。路径规划里每轮起点有 μ≥0.43，但六个离最优不到 3 的终态是单块陷阱。LLM 的 q 和校正误差测自走过的历史，一致收缩没有认证。
证据是两张地图、叠成的两层楼、一个模型、每种最多 20 次。提示词对两边影响都很大，比协议之前先要把提示对齐。地图 2 上 Algorithm 2 的平均间隙停在 13 附近，六次没过早停线，Algorithm 1 只有一次（p=0.09）。六智能体没有新的模型调用，而是把两张地图同一种子的记录按轮拼起来，楼与楼并不相撞。软件场景没有实验。强耦合的 LLM 团队，最大只测到三个智能体。