Transformer在长推理链上难以泛化，新方法通过符号标记和变化记录突破瓶颈。
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
- 用唯一符号标记内存位置，仅记录变化值，绕过重复复制与最后出现检索障碍。
- 在词汇量随问题增长条件下，实现线性长度的图灵机模拟，支持长度泛化。
- 实验验证该方法能有效提升复杂任务的长序列推理能力，适合构建强推理系统。
链式思维（CoT）已被证明可提升Transformer的性能并理论上使其具备图灵完备性。然而，其在训练长度之外的推理链上是否具备泛化能力仍缺乏研究。基于最新的Transformer长度泛化理论框架，我们发现：在标准位置编码和有限词汇表下，含CoT的Transformer无法解决超过TC^0类的问题，即其表达优势在严格长度泛化要求下失效。但若允许词汇量随问题规模增长，则可实现图灵机的长度泛化模拟，且CoT追踪长度与模拟运行时间呈线性关系（常数因子内）。该构造克服了两个核心障碍：重复复制与最后出现位置检索。方法为每个磁带位置分配唯一符号标记，并仅记录值的变化，通过计数恢复当前符号，从而绕过双重障碍。此外，实验表明此类符号标记与变化编码策略对提升困难问题的长度泛化具有实际指导意义。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。