Transformer 实现通用推理的障碍（及其克服方法）

思维链（CoT）虽能提升 Transformer 性能并理论上达到图灵完备，但其对长于训练数据的 CoT 轨迹的泛化能力尚不明确。本文发现，在标准位置编码和有限字母表下，具备 CoT 的 Transformer 无法解决超出 $TC^0$ 类的问题。然而，若允许词汇表随问题规模增长，可实现图灵机的长度泛化模拟。通过为每个磁带位置分配独特标记令牌并仅记录值变化，本研究克服了重复复制和末次检索两大障碍，实证表明该方法能有效提升复杂问题的长度泛化能力。