2025-11-20T09:37:15.420376

Benefits and Limitations of Communication in Multi-Agent Reasoning

Rizvi-Martel, Bhattamishra, Rathi et al.
Chain-of-thought prompting has popularized step-by-step reasoning in large language models, yet model performance still degrades as problem complexity and context length grow. By decomposing difficult tasks with long contexts into shorter, manageable ones, recent multi-agent paradigms offer a promising near-term solution to this problem. However, the fundamental capacities of such systems are poorly understood. In this work, we propose a theoretical framework to analyze the expressivity of multi-agent systems. We apply our framework to three algorithmic families: state tracking, recall, and $k$-hop reasoning. We derive bounds on (i) the number of agents required to solve the task exactly, (ii) the quantity and structure of inter-agent communication, and (iii) the achievable speedups as problem size and context scale. Our results identify regimes where communication is provably beneficial, delineate tradeoffs between agent count and bandwidth, and expose intrinsic limitations when either resource is constrained. We complement our theoretical analysis with a set of experiments on pretrained LLMs using controlled synthetic benchmarks. Empirical outcomes confirm the tradeoffs between key quantities predicted by our theory. Collectively, our analysis offers principled guidance for designing scalable multi-agent reasoning systems.
academic

Benefits and Limitations of Communication in Multi-Agent Reasoning

基本信息

  • 论文ID: 2510.13903
  • 标题: Benefits and Limitations of Communication in Multi-Agent Reasoning
  • 作者: Michael Rizvi-Martel, Satwik Bhattamishra, Neil Rathi, Guillaume Rabusseau, Michael Hahn
  • 分类: cs.MA cs.AI cs.LG
  • 发表时间: 2025年10月14日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.13903

摘要

Chain-of-thought prompting虽然在大语言模型中推广了逐步推理，但随着问题复杂性和上下文长度的增长，模型性能仍会下降。通过将长上下文的困难任务分解为更短、更易管理的子任务，最近的多智能体范式为这个问题提供了一个有前景的近期解决方案。然而，此类系统的基本能力尚未得到充分理解。本文提出了一个理论框架来分析多智能体系统的表达能力。作者将该框架应用于三个算法族：状态跟踪、召回和k-hop推理。研究推导了以下方面的界限：(i) 精确解决任务所需的智能体数量，(ii) 智能体间通信的数量和结构，(iii) 随着问题规模和上下文扩展可实现的加速。结果识别了通信可证明有益的机制，描绘了智能体数量与带宽之间的权衡，并暴露了当任一资源受限时的内在限制。

研究背景与动机

问题定义

本研究要解决的核心问题是：在多智能体推理系统中，通信和动态资源分配在算法层面是否存在可证明受益的任务？

研究重要性

  1. 现有局限性：尽管Chain-of-Thought (CoT)提示已成为处理复杂推理问题的事实标准，但大型推理模型(LRMs)的推理能力随着问题实例复杂性增加或上下文长度增长而退化
  2. 实际需求：多智能体协作方法通过将复杂任务分解为更简单的子问题来实现更强的性能，但其理论基础缺乏深入理解
  3. 理论空白：虽然带有CoT提示的Transformer表达能力已被深入研究，但对多智能体推理方案中通信和资源分配的基本限制和权衡知之甚少

研究动机

作者专注于Transformer基础的多智能体系统，这些系统在w个智能体之间平等分割大小为N的输入，这是许多设置的抽象，包括长上下文摘要、多智能体RAG、浏览器式智能体和map-reduce管道等实际应用场景。

核心贡献

  1. 理论框架：提出了基于Transformer表达能力丰富文献的多智能体推理系统形式化
  2. 算法界限：对三个不同的算法任务族（召回、状态跟踪和k-hop推理）推导了智能体数量和通信需求的界限，突出了这些资源之间的权衡
  3. 实证验证：通过实现理论给出的最优通信协议，提供了理论洞察的实证验证，表明准确性、通信和令牌使用方面的性能与理论预测密切一致
  4. 三种机制识别：揭示了多智能体任务的三个不同机制，每个都由具有广泛相关性的自然任务实例化

方法详解

理论模型

Transformer模型

作者假设因果掩码（仅解码器）唯一硬注意力Transformers (UHAT)，这是一个流行的抽象，其中注意力头将注意力集中在最大化注意力分数的位置上：

UHAT(A)_{i,j} = {1 if j = argmax A_{i,:}, 0 else}

多智能体系统形式化

定义3.1 (多智能体系统)：多智能体系统A将字符串x ∈ S映射到带有w(x) ≤ |x|个智能体的标记DAG A(x)，其中：

  • 每个节点唯一标记为T^{(t)}_i，表示智能体i在时间t的状态
  • 定义两种边类型：
    • 通信边{c, σ}：在不同智能体间传达符号
    • CoT边{a, σ}：对应模型的自回归解码

定义3.2 (复杂性)：

  • 计算深度：图中最长路径的长度（墙钟时间的代理）
  • 宽度：系统中智能体的数量
  • 大小：图中节点的总数
  • 通信预算：具有出站通信边的节点数

三个算法族分析

1. 关联召回 (Associative Recall)

任务：给定多个键值对和查询键，智能体必须返回关联值。

结果：

  • 计算深度：O(1)
  • 智能体数量：w(N)，块大小：N/w(N)
  • 通信预算：O(1)
  • 大小：O(w(N))

2. 状态跟踪 (State Tracking)

任务：在有限幺半群上的状态跟踪问题，形式化为评估m₀ · m₁ · ... · mₖ。

结果：

  • 计算深度：O(log w(N) + N/w(N))
  • 智能体数量：w(N)，块大小：N/w(N)
  • 通信预算：O(w(N))
  • 大小：N

3. k-hop推理

任务：给定N个事实和k-hop查询f₁(...(fₖ(x))...)，智能体需要迭代查找。

结果：

  • 计算深度：O(k)
  • 智能体数量：w(k)，块大小：N/w(k)
  • 通信预算：O(k)
  • 大小：O(wk)

实验设置

数据集

作者使用合成基准来验证理论预测：

  1. 关联召回：随机生成键值字符串，查询从键中均匀采样
  2. 奇偶性计算：固定长度的随机二进制字符串
  3. S5置换跟踪：5个球在5个不同箱子中的交换命令序列
  4. k-hop推理：实体和关系的事实库，生成有效的k-hop查询

评价指标

  • 准确性：任务完成的正确率
  • 计算深度：协议执行的步数
  • 通信成本：智能体间传递的令牌数量

对比方法

  • 多数投票 (Majority Voting)：自一致性基线
  • Chain-of-Agents (CoA)：类似理论最优协议的实现
  • 前缀求和 (Prefix Sum)：状态跟踪的理论最优协议
  • 迭代查询 (Iterative Query)：k-hop推理的最优协议

实现细节

  • 模型：Llama-3.3-70B-Instruct-Turbo和Llama-3.1-8B-Instruct-Turbo
  • 平台：TogetherAI API
  • 实验次数：每个设置运行100次，种子设为42
  • 智能体配置：多数投票使用8个智能体

实验结果

主要结果

关联召回

  • 在较短序列(64-512)中，两种模型表现相似
  • 随着长度增加，多智能体方法获得优势
  • 与理论理解一致：召回是Transformer易解决的任务，在短序列中通信开销可能有害

状态跟踪（奇偶性）

  • 前缀求和始终优于其他方法，特别是随着序列长度增长
  • 相比多数投票，CoA在长序列中退化较少
  • 通信深度与总通信量之间的权衡符合理论预测的N/w(N)深度 vs w(N)通信权衡

k-hop推理

  • 迭代查询通常优于多数投票
  • 随着跳数增加，这种趋势更加明显
  • 计算深度随查询跳数增加而增长，与理论一致

消融实验

作者通过改变前缀求和协议的分支因子生成帕累托前沿图，验证了计算深度与通信之间的权衡关系。

实验发现

  1. 三种机制验证：实验确认了理论预测的三种不同机制
  2. 通信-深度权衡：实证结果支持理论推导的权衡关系
  3. 模型指令遵循：在高通信机制中，模型会增加常数令牌开销，这在理论分析中需要考虑

相关工作

主要研究方向

  1. Chain-of-Thought推理：Wei et al. (2022)等建立的逐步推理标准
  2. 多智能体协作：Zhang et al. (2024b), Tran et al. (2025)等的任务分解方法
  3. Transformer表达能力：Merrill & Sabharwal (2023), Amiri et al. (2025)等的理论分析

本文优势

  • 首次系统性地分析多智能体推理系统的表达能力
  • 提供了通信和资源分配的理论界限
  • 将理论分析与实证验证相结合

结论与讨论

主要结论

  1. 三种机制识别：揭示了多智能体推理的三种不同机制，每种都有特定的深度-通信权衡特征
  2. 理论界限：为智能体数量、通信需求和计算深度提供了严格的数学界限
  3. 实用指导：为设计可扩展的多智能体推理系统提供了原则性指导

局限性

  1. 任务范围：仅分析了三个算法族，可能不涵盖所有实际推理任务
  2. 模型假设：基于UHAT的分析可能不完全适用于实际的softmax Transformer
  3. 通信限制：假设每次只能发送单个令牌，实际系统可能支持更复杂的通信模式

未来方向

  1. 扩展任务：将框架应用于图可达性等其他算法任务
  2. 多智能体范式：扩展到对抗性游戏或协作强化学习任务
  3. 实用协议设计：基于理论洞察设计新的多智能体系统

深度评价

优点

  1. 理论严谨性：提供了完整的数学证明和严格的界限分析
  2. 实证验证充分：理论预测与实验结果高度一致
  3. 实用价值高：为多智能体系统设计提供了具体指导
  4. 写作清晰：复杂的理论内容表述清楚，图表辅助理解效果好

不足

  1. 任务局限性：三个算法族可能不足以覆盖所有重要的推理场景
  2. 实际应用gap：合成任务与实际NLP任务之间存在差距
  3. 模型简化：UHAT模型虽然理论上合理，但与实际模型仍有差异

影响力

  1. 理论贡献：为多智能体推理系统提供了首个系统性理论框架
  2. 实用价值：指导实际系统设计，特别是在长上下文处理方面
  3. 可复现性：提供了完整的代码和实验设置

适用场景

  1. 长文档处理：文档摘要、问答系统
  2. 知识图谱推理：多跳关系查询
  3. 复杂计算任务：需要分解的大规模推理问题

参考文献

  1. Wei, J. et al. (2022). Chain-of-thought prompting elicits reasoning in large language models. NeurIPS.
  2. Zhang, Y. et al. (2024b). Chain of agents: Large language models collaborating on long-context tasks. NeurIPS.
  3. Merrill, W. & Sabharwal, A. (2023). The expressive power of transformers with chain of thought. arXiv preprint.
  4. Amiri, A. et al. (2025). Lower bounds for chain-of-thought reasoning in hard-attention transformers. ICML.

总体评价：这是一篇高质量的理论与实证相结合的论文，为多智能体推理系统提供了重要的理论基础。虽然在任务覆盖面和实际应用方面还有改进空间，但其严谨的理论分析和清晰的实用指导使其成为该领域的重要贡献。