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

📄 arXiv: 2604.25800v1 📥 PDF

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

分类: cs.LG, cs.CL

发布日期: 2026-04-28

备注: Oliver Kraus and Yash Sarrof contributed equally as first authors. Alexander Koller and Michael Hahn are co-senior authors. Code: https://github.com/coli-saar/BarriersToUniversalReasoningWTransformers

💡 一句话要点

揭示Transformer在通用推理中长度泛化的局限性，并提出基于Signpost Token的解决方案

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer 链式思考 长度泛化 Signpost Token 值变化编码

📋 核心要点

  1. 现有研究表明CoT能提升Transformer性能，但其在长序列上的泛化能力仍是挑战。
  2. 论文提出使用Signpost Token和值变化编码，克服重复复制和最后一次出现检索的难题。
  3. 实验结果表明，该方法能有效指导Transformer在困难问题上提升长度泛化能力。

📝 摘要（中文）

本文研究了Transformer在链式思考(CoT)中长度泛化的能力。尽管CoT在经验上提升了Transformer的性能，并在理论上增强了其图灵完备性，但Transformer能否泛化到比训练期间更长的CoT轨迹仍未得到充分研究。基于Transformer长度泛化的理论框架，我们发现，在标准位置编码和有限字母表下，带有CoT的Transformer无法解决超出$TC^0$的问题，即表达性优势在更严格的长度泛化学习要求下不成立。然而，如果允许词汇表随问题规模增长，我们可以实现图灵机的长度泛化模拟，其中CoT轨迹长度与模拟运行时呈线性关系。我们的构造克服了可靠长度泛化的两个核心障碍：重复复制和最后一次出现检索。我们为每个磁带位置分配一个唯一的signpost token，并仅记录值的变化，以通过计数恢复当前的磁带符号，从而规避这两个障碍。此外，我们通过实验表明，使用这种signpost token和值变化编码可以为改进难题的长度泛化提供可操作的指导。

🔬 方法详解

问题定义：论文旨在解决Transformer在链式思考(CoT)推理中，无法有效泛化到比训练序列更长的序列的问题。现有方法在处理长序列时，容易出现重复复制和最后一次出现检索的困难，导致推理失败。这些困难限制了Transformer在需要长序列推理任务中的应用。

核心思路：论文的核心思路是引入Signpost Token和值变化编码。Signpost Token为每个磁带位置分配一个唯一的标识符，而值变化编码只记录值的变化。通过这种方式，模型可以通过计数来恢复当前磁带符号，从而避免了重复复制和最后一次出现检索的问题，实现了长度泛化。

技术框架：该方法的核心在于对输入序列的编码方式进行改进。首先，为每个磁带位置引入唯一的Signpost Token。其次，只记录值的变化，而不是记录所有值。在推理时，模型可以通过Signpost Token定位到特定的磁带位置，并通过计数来恢复该位置的当前值。整个框架仍然基于Transformer架构，但通过改进输入编码方式，提升了其长度泛化能力。

关键创新：最重要的技术创新点在于Signpost Token和值变化编码的结合使用。Signpost Token解决了最后一次出现检索的问题，而值变化编码减少了需要处理的信息量，降低了重复复制的风险。这种结合使得模型能够更有效地处理长序列，并实现长度泛化。

关键设计：论文的关键设计包括：1) 为每个磁带位置分配唯一的Signpost Token；2) 使用值变化编码，只记录值的变化；3) 在训练过程中，使用特定的损失函数来鼓励模型学习Signpost Token和值变化编码的表示。具体参数设置和网络结构细节在论文中进行了详细描述。

📊 实验亮点

实验结果表明，使用Signpost Token和值变化编码可以显著提升Transformer在困难问题上的长度泛化能力。具体的性能数据和对比基线在论文中进行了详细展示，证明了该方法的有效性。

🎯 应用场景

该研究成果可应用于需要长序列推理的各种领域，例如程序生成、算法学习、符号计算等。通过提升Transformer的长度泛化能力，可以使其在更复杂的任务中发挥作用，并推动人工智能技术的发展。

📄 摘要（原文）

Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness. However, whether Transformers can learn to generalize to CoT traces longer than those seen during training is understudied. We use recent theoretical frameworks for Transformer length generalization and find that -- under standard positional encodings and a finite alphabet -- Transformers with CoT cannot solve problems beyond $TC^0$, i.e. the expressivity benefits do not hold under the stricter requirement of length-generalizable learnability. However, if we allow the vocabulary to grow with problem size, we attain a length-generalizable simulation of Turing machines where the CoT trace length is linear in the simulated runtime up to a constant. Our construction overcomes two core obstacles to reliable length generalization: repeated copying and last-occurrence retrieval. We assign each tape position a unique signpost token, and log only value changes to enable recovery of the current tape symbol through counts circumventing both barriers. Further, we empirically show that the use of such signpost tokens and value change encodings provide actionable guidance to improve length generalization on hard problems.