跳转至

Lost in Transmission: When and Why LLMs Fail to Reason Globally

会议: NeurIPS 2025 (Spotlight)
arXiv: 2505.08140
代码: 无
领域: LLM推理
关键词: communication complexity, bounded attention, chain-of-thought, LLM limitations, computational framework
作者: Tobias Schnabel, Kiran Tomlinson, Adith Swaminathan, Jennifer Neville (Microsoft)

一句话总结

提出有界注意力前缀预言机(BAPO)计算框架，将LLM的注意力头建模为有限带宽通信信道，证明图可达性等全局推理问题是BAPO-hard的（需超常数带宽），且CoT可将任何BAPO-hard问题转化为BAPO-easy问题，实验在GPT-4o/Claude/Gemini上验证理论预测。

研究背景与动机

核心矛盾

核心矛盾：领域现状：LLM全局推理的系统性失败：基于Transformer的LLM在需要整合输入大部分信息的任务上（如图可达性、变量追踪、多数投票聚合）持续失败，即使模型规模很大也无济于事。

缺乏原理性解释：现有工作多在实证层面观察失败，缺少形式化框架来解释为什么某些任务难而某些容易，也无法预测哪类问题LLM会失败。

信息流瓶颈假说：论文认为失败根源并非计算能力不足（增加MLP宽度或层数无效），而是注意力机制的通信带宽限制——信息在残差流之间通过注意力传递时存在容量瓶颈。

CoT有效性的理论空白：Chain-of-Thought在实践中对复杂推理有帮助，但缺乏严格理论解释其为何以及何时有效。

通信复杂性的已有框架不够精准：已有工作用通信复杂性研究Transformer能力，但未能准确建模因果注意力中前缀→后缀的单向信息流特性。

实用意义：理解带宽限制可以指导架构设计（如增大带宽）、推理策略选择（CoT分解）和任务难度预判。

方法详解

BAPO计算框架

核心定义：\((b_p, b_a)\)-BAPO（有界注意力前缀预言机） - 将输入序列在任意位置分为前缀和后缀两部分 - 前缀流（模拟早期token的残差流）：可做无限计算，但只能向后缀发送 \(b_p\) 比特信息 - 后缀流（模拟最后一个token的残差流）：可通过注意力从前缀获取 \(b_a\) 比特信息 - 总通信带宽为 \((b_p, b_a)\)，要求对所有可能的分割位置都能正确输出 - 简化假设：前缀/后缀有无限计算能力、单token输出、完美位置编码

问题分类（三个硬度类） - BAPO-easy：常数带宽 \((O(1), O(1))\) 即可解决（如：检查首尾元素是否相同） - BAPO-hard：需要超常数带宽 \(\omega(1)\)，随输入长度增长（如：图可达性、字符串相等判定） - BAPO-Σ-hard：带宽依赖于字母表大小 \(|\Sigma|\)（如：第k大元素，k为常数时需 \(O(|\Sigma|)\)）

分析的6个问题及其带宽 1. First-Last（首尾比较）：BAPO-easy，\((0,1)\) 2. Equality（字符串相等）：BAPO-hard，\(\Omega(n)\) 3. Graph Reachability（图可达性）：BAPO-hard，至少 \(\Omega(\sqrt{n})\) 4. Variable Tracking（变量追踪）：BAPO-hard 5. Majority（多数投票）：BAPO-hard 6. Code Tracing（代码追踪）：映射到图可达性，BAPO-hard

CoT的理论作用 - 定理：对任何可判定问题，使用足够多的CoT推理token后，常数带宽 \((2,3)\) 的BAPO可以模拟图灵机的单步计算 - 推论：CoT使常数带宽BAPO变成图灵完备的，任何BAPO-hard问题都可通过CoT分解为一系列BAPO-easy子步骤 - 代价：可能需要大量推理token（实验中o3和Gemini 2.5 Flash使用10k+ token解决BAPO-hard问题）

实验设计

  • 在6个合成任务上测试GPT-4o、Claude Haiku、Gemini 1.5 Pro（无CoT）和带CoT版本
  • 变化输入大小 \(n\)（如图节点数从10到200），观察准确率随 \(n\) 的变化
  • 扩展到真实任务：情感分析聚合、代码追踪

实验关键数据

表1：BAPO-easy vs BAPO-hard 在LLM上的表现

任务类型 典型问题 带宽需求 GPT-4o/Claude/Gemini(n=200)
BAPO-easy First-Last比较 \((0,1)\) ~100%准确率，保持稳定
BAPO-hard 图可达性 \(\Omega(\sqrt{n})\) 随n增大急剧下降至~50%(随机水平)
BAPO-hard 字符串相等 \(\Omega(n)\) 中等n时已开始失败
BAPO-hard 变量追踪 超常数 较小n时即失败

表2：CoT对BAPO-hard问题的效果

模型 CoT方式 BAPO-hard准确率 推理token量
GPT-4o等(无CoT) - 随n增大→随机 N/A
GPT-4o(250词CoT限制) 外部CoT 有限提升，n>50后仍下降 ~250词
o3 / Gemini 2.5 Flash 内部推理 保持高准确率 10,000+ tokens

关键发现：(1) BAPO-easy/hard的分类精确预测了LLM的成功/失败模式；(2) CoT有效但需足够长的推理链——250词限制不够，o3/Gemini的内部长推理则可解决；(3) 真实任务(情感聚合、代码追踪)中也观察到与理论一致的BAPO-hard失败。

亮点与洞察

  1. 优雅的理论框架：BAPO模型将复杂的Transformer行为抽象为简洁的通信带宽问题，建立了理论-实验的清晰对应，AC评价其为"clean and valuable theoretical contribution"
  2. 原理性解释CoT：首次证明CoT的理论效力——将BAPO变成图灵完备，提供了CoT有效性的形式化保证，而非仅实证观察
  3. 精确的预测能力：BAPO-easy/hard分类在GPT-4o、Claude、Gemini上都得到验证，理论预测与实验高度吻合
  4. 架构设计启示：指出增加MLP宽度/层数（计算能力）无法解决问题，关键在于增大注意力通信带宽，为架构改进提供方向性指引
  5. NeurIPS 2025 Spotlight：4位审稿人中3位给Accept(5分)，AC强调其在理解LLM方面的重要性和对后续研究的激发作用

局限与展望

  1. 模型抽象过度简化：假设前缀/后缀有无限计算能力、完美位置编码、单token输出，与真实Transformer差距较大，限制了直接应用性
  2. 任务集合有限：仅分析6个合成问题，尚未覆盖更多自然语言中的推理任务；理论下界多数是松弛的
  3. 有效带宽的根因不明：论文承认不理解"为什么LLM的有效带宽如此有限"，可能与泛化能力的权衡有关
  4. CoT实验不够充分：250词CoT限制下的实验效果不明显（Figure 4），仅o3/Gemini内部推理成功，但这些是闭源模型无法深入分析
  5. 缺少训练小模型的验证：审稿人建议在BAPO-hard任务上从头训练小Transformer以隔离架构因素，论文未做此实验

评分

维度 评分 说明
新颖性 ⭐⭐⭐⭐⭐ 全新的BAPO计算框架，首次将通信带宽视角系统性地应用于LLM推理失败分析
技术深度 ⭐⭐⭐⭐⭐ 严格的理论证明(图灵完备性、带宽下界) + 多模型实验验证，39页完整论文
实验充分性 ⭐⭐⭐ 合成任务验证了理论预测，但任务数量有限、CoT实验不够充分
实际影响 ⭐⭐⭐⭐ 为理解LLM局限性和CoT有效性提供理论基础，可指导架构设计和推理策略

相关论文