🤖 machine learning

Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

本文表明，尽管标准思维链 Transformer 因在复制和检索方面的固有局限而无法泛化到更长的推理轨迹，但通过采用不断增长的词汇表，结合独特的路标标记和值变化编码来克服这些障碍，它们能够实现具有长度泛化能力的图灵完备性。

原作者： Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

发布于 2026-04-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是论文《Transformer 通用推理的障碍（及如何克服它们）》的通俗解释，辅以生动的类比。

宏观图景：那个会“遗忘”的“优等生”

想象一位非常聪明的学生（即Transformer）正在学习解决复杂的谜题。为了帮助他们，老师给他们提供了一块“草稿纸”，让他们可以一步步写下思考过程。这被称为思维链（Chain-of-Thought, CoT）。

先前的研究表明，有了这块草稿纸，这位学生在理论上可以解决任何谜题，无论其多么困难。这就像赋予了他们一种超能力。

然而，本文的作者发现了一个重大缺陷：这位学生擅长解决他们练习过的谜题，但当谜题变长时，他们会彻底失败。 如果你让他们训练解决一个 10 步的谜题，他们甚至无法解决一个 20 步的谜题，即使逻辑完全相同。他们似乎撞上了一道“天花板”，导致其推理能力崩溃。

本文提出了一个问题：为什么会发生这种情况，我们能修复它吗？

两大障碍

作者发现，这位学生的“大脑”（即 Transformer）存在两个特定的“故障”，阻碍了他们将能力泛化到更长的任务中。

1. “复印机”故障（重复复制）

想象这位学生需要从一本书中把一长串指令抄写到草稿纸上。

问题所在： 如果列表很短，他们可以轻松抄写。但如果列表很长，他们就会感到困惑。他们无法可靠地从长页面的中间找到确切需要复制的那一行，从而迷失方向。
论文观点： 标准的 Transformer 难以在长度变化时“复制”任意的信息字符串。他们会在文本中间迷失。

2. “最后所见”故障（检索）

想象这位学生正在追踪一个变量，比如"X 的值”。

问题所在： 如果学生写下"X = 5"，随后写下"X = 7"，接着又写下"X = 5"，他们需要知道当前的值是多少。在长长的思维链中，学生往往会忘记哪个"5"是最近出现的。他们可能会抓取页面开头那个旧的"5"，而不是新的那个。
论文观点： 模型难以在漫长的变更历史中找到最新的更新。这就像试图在一本有 1000 页条目的日记中，找出你最后一次吃苹果的时间。

解决方案：书写草稿纸的新方法

作者提出了两个巧妙的技巧来修复这些故障。他们并没有改变学生的“大脑”，只是改变了如何在草稿纸上书写指令。

技巧一：“姓名标签”（路标标记）

为了解决复印机故障，作者建议给谜题中的每个项目分配一张独特的 ID 卡或“姓名标签”。

工作原理： 指令不再是“去第 50 行”，而是“去带有姓名标签 #42 的项目”。
为何有效： 即使列表变长，学生也不必通过数数来找到第 50 行。他们只需寻找特定的姓名标签。这就像拥有一个图书馆，每本书都有唯一的条形码，因此你无需扫描整个书架就能找到你需要的那一本。

技巧二：“变更日志”（值变更编码）

为了解决最后所见故障，作者建议改变学生写下内容的方式。

旧方法： 学生每次都写下完整的当前状态（例如"X 是 5"，然后"X 是 7"，接着"X 是 5"）。这会产生大量噪音，让人难以分辨哪个是最新的。
新方法： 学生只写下发生了什么变化。
- 与其写"X 是 7"，不如写"X 从 5 变成了 7"。
- 与其再次写"X 是 5"，不如写"X 从 7 变成了 5"。
为何有效： 为了找到当前值，学生只需计算变更次数。如果他们看到“从 5 到 7"，接着看到“从 7 到 5"，他们就知道当前值是 5。这就像记录交易账本，而不是每次花掉一美元时都重写你的整个银行余额。

结果：理论与现实

论文通过两种方式测试了这些想法：

数学证明（理论）：
- 坏消息： 如果你坚持使用固定的词汇集（有限字母表）和标准的书写风格，这位学生无法学会解决超过特定复杂度的谜题（具体来说，他们无法超越称为TC0的一类问题）。他们在数学上被卡住了。
- 好消息： 如果你允许学生使用无限供应的独特姓名标签（路标），并采用“变更日志”方法，那么他们在理论上可以解决任何谜题，无论其长度如何。
实验（现实）：
- 作者从头开始训练小型计算机模型，以应对三项高难度任务：
  - 奇偶校验（Parity）： 计算一串数字中 1 的数量是奇数还是偶数。
  - 布尔求值（Boolean Evaluation）： 解决复杂的逻辑谜题（真/假）。
  - S5 排列（S5 Permutation）： 追踪 5 个物体被交换移动的过程。
- 结果：
  - 使用标准方法训练的模型，在谜题变长时失败了。
  - 使用姓名标签和变更日志训练的模型，在解决从未见过的更长谜题时表现要好得多。
- 他们还在大型预训练 AI 模型（如 Llama 和 Mistral）上测试了这一点。即使不重新训练这些模型，仅仅提示它们在回答中使用姓名标签和变更日志，也能显著提高它们解决长难问题的能力。

核心启示

论文得出结论：思维链并非魔法。 如果 AI 的思考方式容易在长列表中迷失，那么仅仅告诉 AI“一步步思考”是不够的。

为了让 AI 在长期推理中真正可靠，我们需要以避开两大陷阱的方式来格式化“思考”：

给每一步分配独特的姓名标签，以防任何内容丢失。
仅记录变更，以免模型被旧信息混淆。

通过修复推理的格式，我们可以帮助 AI 模型突破当前的限制，解决更困难的问题。

以下是论文《通用推理的 Transformer 障碍（及如何克服）》的详细技术总结。

1. 问题陈述

尽管思维链（Chain-of-Thought, CoT）提示在经验上提升了 Transformer 的性能，并在理论上被证明能将其表达能力提高至图灵完备，但仍存在一个关键差距：Transformer 能否学会将 CoT 推理泛化到比训练所见更长的长度？

现有的经验证据表明，即使在算法和逻辑任务上，随着 CoT 轨迹长度的增加，Transformer 的准确率也会急剧下降。本文探讨了在更严格的长度可泛化可学习性要求下，图灵完备的理论主张是否成立。具体而言，它提出了以下问题：

当泛化到更长序列时，标准 CoT 格式是否允许 Transformer 解决超出 $\text{TC}^0$ （常数深度阈值电路）复杂度类的问题？
哪些具体的结构障碍阻碍了这种泛化？
能否通过特定的格式化策略克服这些障碍？

2. 方法论

作者结合了理论形式化与经验验证：

理论框架

本研究利用了关于 Transformer 长度泛化的最新理论框架：

C-RASP： 一种用于推理具有有限字母表和位置编码的 Transformer 的形式化方法。其成员资格意味着长度泛化保证。
C-RASP：* C-RASP 的扩展，允许使用无限字母表（具体而言，是无界的指路标记 token）和局部匹配谓词。
学习模型： 作者采用了一种理想化的学习模型，其中在递增输入长度上训练的一系列 Transformer 收敛到单一的基础算法。如果任务可以在这些形式化方法中表达，则泛化得到保证。

经验设置

任务： 选择了三个算法推理任务：
1. 奇偶校验（Parity）： 判断二进制字符串中 1 的数量是偶数还是奇数。
2. 布尔求值（Boolean Evaluation）： 评估嵌套逻辑公式的真值。
3. S5 排列（S5 Permutation）： 跟踪一系列交换操作后 5 个对象的状态。
模型：
- 从头训练（From-Scratch）： 在有无特定格式化的 CoT 轨迹上训练的 GPT-2 模型（2500 万参数）。
- 预训练大语言模型（Pretrained LLMs）： 在 Qwen2.5-7B、Mistral-Small-24B 和 Llama-3.3-70B 上进行的零样本和少样本提示实验。
格式化变体：
- 朴素 CoT： 标准顺序推理。
- 指路标记 Token（Signpost Tokens）： 为特定位置或操作分配唯一标识符（例如 <34>），以实现任意寻址。
- 值变更编码（Value-Change Encoding）： 模型不记录每一步的完整状态，而是仅记录值的变化（例如 1 -> 0），或明确记录值保持不变的情况。

3. 主要贡献与理论结果

贡献 1：有限字母表的局限（负面结果）

作者证明，在标准位置编码和有限字母表下，带有 CoT 的 Transformer 无法长度泛化以解决 $\text{TC}^0$ 之外的问题。

定理 3.4： 如果语言 $L$ 的 CoT 轨迹可在 C-RASP 中表达（含位置原语），则 $L$ 在 $\text{TC}^0$ 中可定义。
含义： 尽管 CoT 在理论上允许图灵完备，但如果词汇表固定，此类模拟的可学习性受限于 $\text{TC}^0$ 。表达能力的提升并未转化为长度可泛化的可学习性。

贡献 2：利用无限字母表克服障碍（正面结果）

本文确定了长度泛化的两个核心障碍：

重复复制： 将任意字符串复制到新位置的困难。
最后出现检索： 当发生多次更新时，检索变量最新值的困难（非唯一检索）。

为了克服这些障碍，作者提出了使用 C-RASP* 的构造：

指路标记 Token： 为每个磁带位置或操作步骤分配一个唯一的、无界的 token（来自无限字母表）。这通过允许任意索引而无需记忆绝对身份，解决了复制障碍。
值变更编码： CoT 不记录完整状态，而是仅记录转换（例如“值从 $x$ 变为 $y$ "）。当前状态通过计算相对于初始状态的净变化来恢复。这通过将当前值转化为计数函数而非搜索“最后”出现的位置，解决了检索障碍。
定理 3.8： 如果 Transformer 利用无限字母表的指路标记 token 并通过值变更编码计算，则带有 CoT 的 Transformer 可以长度泛化以模拟任何图灵机。CoT 轨迹长度在模拟运行时间中保持线性。

4. 经验结果

从头训练

奇偶校验： 标准 CoT 未能泛化到训练长度之外。值变更编码实现了对训练长度 2 倍的稳健泛化。
布尔求值与 S5 排列： 这些更难的任务（超出 $\text{TC}^0$ ）在朴素 CoT 下失败。添加指路标记 token显著改善了长度泛化，但由于模型可能利用潜在的“捷径”（启发式方法），S5 任务仍然具有挑战性。
二进制排列： S5 的一个高重复变体。朴素和仅指路标记的 CoT 因“非唯一检索”错误而失败。结合指路标记 + 值变更产生了最佳结果，证实了这两种机制在理论上的必要性。

提示预训练大语言模型

指路标记： 在少样本提示中使用自然数作为指路标记提示，显著提高了所有测试的大语言模型（7B 到 70B）在布尔和 S5 任务上的性能，特别是在较长序列长度下。
值变更： 在代码执行任务（跟踪变量赋值）中，提供显式记录值变化的内联注释（例如 # node a: 9 -> 0），即使没有中间推理步骤，与标准代码格式化相比，也显著提高了最终答案的准确率。

5. 意义与结论

重新定义 CoT 成功： 本文认为，CoT 的成功并非 inherent 于“思考”过程本身，而是高度依赖于轨迹的格式化。标准 CoT 格式往往无法泛化，因为它们违反了可学习性所需的约束（局部性和平移不变性）。
理论边界： 它阐明了 Transformer 的图灵完备性是有条件的。它适用于表达能力（硬编码解决方案），但不适用于可学习性（训练模型进行泛化），除非提供特定的结构辅助（无限字母表/指路标记）。
实践指南： 研究结果为提高大语言模型在困难推理任务上的性能提供了可操作的原则：
1. 使用索引提示： 用唯一标识符明确标记位置或步骤，以辅助检索。
2. 记录变化而非状态： 格式化推理轨迹以突出状态转换，而非完整状态转储，以避免检索歧义。
未来方向： 这项工作表明，未来的预训练数据和 CoT 方案的设计应考虑到这些理论约束，以释放 Transformer 在长视野推理任务上的全部计算潜力。

总之，本文证明，虽然 Transformer 在理论上具备通用推理能力，但要以实现长度可泛化的方式实现这一能力，需要通过使用指路标记 token和值变更编码来克服特定的架构和格式化障碍。