Transformer 通用推理的障碍（以及如何克服它们）

思想链 (CoT) 已被证明可以根据经验提高 Transformer 的性能，并在理论上提高其图灵完整性的表达能力。然而，Transformer 是否能够学习泛化到比训练期间看到的更长的 CoT 轨迹尚待研究。我们使用最新的 Transformer 长度泛化理论框架，发现在标准位置编码和有限字母表下，带有 CoT 的 Transformer 无法解决超出 $TC^0$ 的问题，即在长度泛化学习性的更严格要求下，表达性优势不成立。然而，如果我们允许词汇量随着问题大小而增长，我们就可以获得图灵机的长度可概括的模拟，其中 CoT 迹线长度在模拟运行时间中呈线性关系，直至恒定。我们的构造克服了可靠长度概括的两个核心障碍：重复复制和最后出现的检索。我们为每个磁带位置分配一个唯一的路标标记，并仅记录值更改，以便通过绕过这两个障碍的计数来恢复当前磁带符号。此外，我们凭经验表明，使用此类路标标记和值更改编码为提高难题的长度泛化提供了可行的指导。