Benefits and Limitations of Communication in Multi-Agent Reasoning¶

会议: ICLR2026
OpenReview: 0aPIVJUz5T
代码: https://github.com/michaelrizvi/coa-algorithmic
领域: 多智能体推理 / 表达力理论
关键词: 多智能体系统, 通信复杂度, 状态追踪, k-hop 推理, Transformer 表达力

一句话总结¶

本文给"把长上下文切块、多个 LLM agent 分头处理再汇总"这类多智能体推理系统建了一套基于 Transformer 表达力的理论框架，在关联召回、状态追踪、k-hop 推理三类任务上证明了需要多少个 agent、多少通信、能换来多少并行加速的紧界，划出三种 depth–通信权衡区间，并用 Llama 在合成基准上验证理论预测的拐点确实出现。

研究背景与动机¶

领域现状：链式思维（CoT）已经成了复杂推理的事实标准，自洽采样、思维树、流式搜索等都把推理看成在"思维"上做结构化遍历。但随着问题复杂度和上下文长度增长，单模型的推理能力会持续退化。为缓解这一点，近来一批多智能体范式（CoA、LLM×MapReduce、LongAgent、XpandA 等）把难任务拆成短的子问题，让多个 agent 分工协作，成了很有前景的近期解法。

现有痛点：这些系统几乎全是工程经验驱动——开多少个 worker、要不要让它们互相通信、通信能换来多少加速，都靠拍脑袋。学界对单模型 + CoT 的表达力已有深入刻画（Merrill & Sabharwal、Amiri 等），但对"多个 agent 之间通信与资源分配的根本极限"几乎一无所知。

核心矛盾：多智能体系统里有三个互相牵制的量——agent 数量 \(w\)、通信预算、计算深度（约等于 wall-clock 时间）。直觉上多开 agent 能并行降深度，但本文要回答的是：这种降深度是不是免费的？什么任务真能靠通信获益，什么任务再怎么通信也省不了深度？

本文目标：建一套形式化框架，对协作式多智能体推理的表达力给出可证明的上界与下界，把"agent 数 ↔ 通信量 ↔ 深度"三者的权衡刻画清楚。

切入角度：不把 agent 当成无限能力的处理器（那样 PRAM/通信复杂度的经典理论就够用了），而是把每个 agent 都建模成一个 Transformer，让分析精确到"Transformer 一步注意力能干什么、干不了什么"这个粒度。

核心 idea：用一句话概括——把多智能体系统形式化成一张 DAG（节点=某 agent 某时刻的状态，边=CoT 解码或 agent 间通信），再借 Transformer 表达力的下界工具，在三类代表性任务上证出 agent 数、通信、深度的匹配界。

方法详解¶

整体框架¶

本文不是提出一个新系统，而是提出一套分析工具 + 三个任务族上的定理。整体思路分三层：先用一个统一的图模型把"什么是一个多智能体推理系统"讲清楚；再定义衡量它代价的四个量（size / depth / width / 通信预算）；最后在关联召回、状态追踪、k-hop 推理三类任务上分别给出可实现的协议（上界）和不可逾越的下界，从而把整个多智能体推理空间切成三个区间。

agent 模型：每个 agent 是一个因果掩码的唯一硬注意力 Transformer（UHAT）——注意力把全部权重压在得分最高的那个位置上（并列时取最右）。选 UHAT 是因为它在固定精度下能覆盖普通 softmax Transformer 的表达力，且有现成的下界工具，适合刻画长上下文、大推理问题这种极限 regime。

系统模型（DAG 形式化）：一个多智能体系统 \(A\) 把输入串 \(x\) 映射成一张带标签的有向无环图 \(A(x)\)，最多 \(w(x)\le|x|\) 个 agent。每个节点记作 \(T_i^{(t)}\)，表示 agent \(i\) 在时刻 \(t\) 的状态。两类边：CoT 边 \(\{a,\sigma\}\) 表示 agent 自回归解码出下一个 token；通信边 \(\{c,\sigma\}\) 表示一个 agent 把单个符号 \(\sigma\) 发给另一个 agent（可以点对点 SEND，也可以 BROADCAST 广播给所有人）。关键约束：每个 agent 一次只能收/发一个 token，输入被等分成 \(N/w\) 大小的块分给各 agent，其中一个 agent 被指定为 manager，它最后一条 CoT 边的标签就是系统输出。

四个复杂度量：① size = 图的节点总数（≈总计算量）；② depth = 图中最长路径长度（≈wall-clock 时间）；③ width \(w(N)\) = agent 数；④ 通信预算 = 带外出通信边的节点数（≈agent 间总通信量）。本文的所有定理都是在刻画这四个量之间的可达组合与不可达组合。

关键设计¶

1. DAG 形式化：把"工程上五花八门的多智能体管线"压成一个可证明的对象

这是全文的地基，专治"多智能体系统没法做理论分析"这个痛点。作者观察到，应用界绝大多数 long-context 多智能体方法都遵循同一个骨架：把长上下文切成不重叠的块 → 多个 worker 并行处理各自的块 → 把信息汇给 manager 出最终答案，差别只在 worker 之间要不要、怎么通信（CoA/MapReduce 几乎零通信，LongAgent/XpandA 支持定向消息解冲突）。把这一切统一抽象成 Definition 3.1 的 DAG 后，每个真实系统就对应一张通信图，而 agent 自回归生成的 token 序列 \(\xi^{(i)}\)（输入块 + 自己的 ID + 一路上 RECEIVE/SEND/BROADCAST 的 token + EOS）只要能塞进 Transformer 的上下文窗口、且模型能正确预测所有外出边和 EOS，就算这个 Transformer 实现了该协议。这个抽象的妙处在于它只要求层数和注意力头数跨输入长度一致有界（宽度 \(d\) 可以随长度增长以容纳位置编码），比 CoT 理论里常见的"整个 Transformer 跨长度均匀"假设弱得多，却仍能证出几乎匹配的上下界。

2. 三区间定理：先在抽象层面把"通信能不能换深度"一刀切清楚

在做任何具体任务之前，作者先证了两条管全局的结论，直接划定了多智能体推理的可行边界。第一条是 size 守恒（Prop. 4.1）：任何多协议都能转成一个等价的单 agent 协议，size 只差常数倍——也就是说多开 agent 省不了总计算量。第二条更关键（Prop. 4.2）：如果一个任务存在通信预算 \(O(1)\) 的多智能体协议，那它本来就能被单 agent 用 \(O(1)\) 深度解决。换句话说，想靠多 agent 降深度，就必须付出通信代价，"通信保持 \(O(1)\) 同时深度按 \(\text{Size}/w\) 下降"这种好事是不可能的。配合不等式 \(\text{Size}(N)/w(N)\le\text{Depth}(N)\)，剩下的可行空间正好被切成三个区间（Figure 2）：(i) depth 和通信都 \(O(1)\)，多 agent 只是单纯能吞更大上下文、无额外代价；(ii) 多开 agent 能降深度、但通信随之上涨，存在 depth–通信权衡；(iii) 最坏情况下通信很大、深度却降不下来。三个区间各由一个自然任务实例化。

3. 三类任务的匹配界：把三个区间各钉死在一个代表性任务上

作者用三个算法族分别落地三个区间，每个都给出可实现协议 + 最优性下界（结果汇总见下表，\(w\)=agent 数、\(N\)=输入长度）。

关联召回（区间 i）：给 \(N\) 个键值对和一个查询键，要返回对应值。把输入分给 \(k\) 个 agent、每个都拿到查询，则每个 agent 用一次注意力判断查询键在不在自己块里、用归纳头取出对应值，只有一个 agent 会命中并汇报给 manager。深度 \(O(1)\)、通信 \(O(1)\)、size \(O(w)\)——多开 agent 纯赚上下文容量，零额外代价。
状态追踪（区间 ii）：形式化成有限幺半群上的累乘 \(m_0\cdot m_1\cdots m_k\)，涵盖 PARITY、Python 代码求值、棋局追踪等。这类任务 size 必然 \(\Omega(N)\)（Prop. 4.4，省不掉），但深度可以靠并行换：用前缀和 / 并行扫描协议（Figure 1b），\(w(N)\) 个 agent 时深度 \(O\!\left(\log w(N)+\frac{N}{w(N)}\right)\)、通信预算 \(O(w(N))\)、size \(N\)（Prop. 4.6）。当 \(M\) 是非平凡群时这个界还是最优的（Prop. 4.7：通信 \(\Omega(w)\)、深度 \(\Omega(N/w)\)）——这正是教科书式的 depth–通信权衡：多花通信，换 wall-clock 加速。
k-hop 推理（区间 iii）：给 \(N\) 条事实 \(f(x)=y\) 和一个嵌套查询 \(f_1(\dots f_k(x)\dots)\)，每个 agent 拿一份不重叠的事实子集。最优策略是迭代查询（Figure 1c）：manager 沿 \(f_k(x),f_{k-1}(f_k(x)),\dots\) 一跳跳地问，每跳让持有该事实的 worker 回答。深度 \(O(k)\)、通信 \(O(k)\)、size \(O(wk)\)（Prop. 4.8）。要命的是——只要 agent 多于一个，最坏情况下深度和通信都是 \(\Omega(k)\)，多开 agent 降不了深度，因为相关事实可能散落在不同 agent 手里，逼得你只能一跳跳串行查。这就是"通信很贵、深度不降"的第三区间。

任务	Size	Depth	通信
关联召回	\(\Theta(w)\)	\(\Theta(1)\)	\(\Theta(1)\)
状态追踪	\(\Theta(N)\)	\(O(\frac{N}{w}+\log w)\)	\(\Theta(w)\)
k-hop 推理	\(O(w^k)\)	\(O(k)\)	\(\Theta(k)\)（当 \(w>1\)）

4. 与自洽（多数投票）的超多项式分离：从理论上说清"通信协议为什么强过自洽"

这是一个把理论价值落到实践直觉上的点。作者定义"多数投票"为 \(w(N)\) 个 agent 各自在完整输入上独立跑、各输出一个 token，再取众数。在 PARITY 上他们证了一个超多项式分离（Prop. 6.1）：要让多数投票在 \(O(\log N)\) 深度内算对 PARITY，需要 \(w(N)=2^{\Omega(N^c)}\) 个 agent（指数级）；而前缀和协议只需 \(w(N)=N\) 个 agent、\(O(\log N)\) 深度就能完美准确。这就从根上解释了"为什么带精巧通信协议的多智能体系统能碾压简单的自洽采样"——不是常数倍的差距，而是指数级的。

实验关键数据¶

实验目的不是刷 SOTA，而是验证三个理论区间在真实 LLM 上是否真出现。模型用 Llama-3.3-70B-Instruct-Turbo（8B 在附录），agent 被 prompt 各自的角色和任务指令，通信协议硬编码（仿 CoA 实现）。

主实验：三任务各自验证一个区间¶

任务	最优协议	基线	关键现象
关联召回（needle-in-haystack）	Chain-of-Agents	多数投票	CoA 准确率跨上下文长度基本恒定；多数投票随长度增长持续退化（且 needle 在首尾时也会失败）
状态追踪（PARITY）	Prefix Sum	多数投票 / CoA	Prefix Sum 在各序列长度上一致最优，序列越长优势越大；CoA 比多数投票退化慢
k-hop 推理	Iterative Query	多数投票	跳数越多，Iterative Query 越显著领先；500 条事实比 100 条事实差距更明显

关键发现¶

召回（区间 i 验证）：CoA 的 token 用量跨 chunk 大小和上下文长度基本不变（Figure 3c），印证理论预测的"召回深度/通信 \(O(1)\)"——切块分治让长上下文检索变得免费可扩展。
状态追踪（区间 ii 验证）：Figure 4b 画出计算深度 vs 总通信量，确实呈现理论预测的"深度 \(N/w\) ↔ 通信 \(w\)"权衡曲线。唯一偏差是高通信区深度略有上升，原因是模型指令遵循不好——会反复复述查询、解释流程，叠加了常数级 token 开销。
k-hop（区间 iii 验证）：计算深度随查询跳数单调上升（Figure 5c），与"深度 \(\Omega(k)\)、多开 agent 也降不下来"一致。有趣的反例：跳数最小（4 跳）时多数投票偶尔反超 Iterative Query，作者推测此时"每轮失败的概率"超过了"在更大语料里检索事实的难度"。

亮点与洞察¶

把"agent 是 Transformer"当成分析的核心约束，而非把 agent 当无限处理器：正是这个选择让分析能区分"关联召回一步注意力搞定"和"状态追踪必须多步显式推理链"——经典并行计算模型（PRAM、通信复杂度）会把两者都预测成低深度，分不出差别。这是本文相对纯并行计算理论的真正增量。
三区间是一张实用的设计地图：拿到一个新任务，先判断它属于哪个区间，就能知道"该不该多开 agent、该不该让它们通信"。比如纯检索/汇总类任务属区间 i，多开 worker 免费；而多跳推理属区间 iii，盲目并行只会徒增通信、深度照样降不下来。
指出 CoA/MapReduce 这类"多 worker 单 manager"架构的隐患：它们只是把上下文瓶颈从 worker 转移到了 manager 身上——manager 要聚合一大堆 worker 回复，照样容易出错。作者据此提出前缀和式级联（迭代摘要、分支因子和深度可调）来摊薄 manager 瓶颈，以及把 Iterative Query 用于复杂查询分解的设计建议。
超多项式分离给了"自洽不如通信"一个硬核理论背书：很多经验上观察到的"自洽采样在难任务上收益有限"，这里被钉成了 PARITY 上的指数级 agent 数差距。

局限与展望¶

任务局限：只覆盖关联召回、状态追踪、k-hop 三族；图可达性、对抗博弈、协作强化学习等更复杂的多智能体范式尚未触及（作者自己列为 future work）。
agent 抽象偏理想：用 UHAT 这种硬注意力理想模型，且通信被限制为单 token、输入被等分成连续块。真实 LLM 系统里 agent 能力不均、消息是变长自然语言、上下文切分也不一定等分均匀，理论界与工程现实之间仍有 gap（作者注明扩展到有界长度消息是直接的，但等分块假设是真实约束）。
理论 vs 实测的偏差暴露了一个实践短板：高通信区深度偏离理论，根因是模型指令遵循差、反复复述。这说明即便协议在理论上最优，实际部署时 prompt 工程和指令遵循仍会侵蚀加速收益——这块本文只是观察到，没给系统性的缓解方案。
没把设计建议真正落地实现：前缀和级联、Iterative Query 用于查询分解等都只停在"我们相信有前景"的层面，没有在真实长文档/复杂 QA 任务上做端到端系统验证。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次把多智能体推理系统建成基于 Transformer 表达力的 DAG 模型，并证出 agent 数/通信/深度的匹配界，填补了"多智能体协作的根本极限"这一理论空白
实验充分度: ⭐⭐⭐⭐ 三任务×两模型在受控合成基准上干净地验证了三区间，但都是合成任务，缺真实长文档/复杂推理的端到端验证
写作质量: ⭐⭐⭐⭐ 形式化严谨、三区间的故事线清晰，定理与任务一一对应；代价是定义和符号较重，对非理论背景读者门槛偏高
价值: ⭐⭐⭐⭐⭐ 给多智能体 LLM 系统设计提供了"该不该多开 agent、该不该通信"的原则性判据，三区间地图和设计建议有直接的工程指导意义