证明带软注意力的思维链模型可实现图灵完备性。
Softmax Transformers are Turing-Complete
- 用计数型RASP扩展思维链，构建可泛化的软注意力模型。
- 在单字符语言下实现图灵完备，复杂算术推理任务训练成功。
- 适合研究模型计算能力与符号推理的学者参考。
已知硬注意力思维链（CoT）Transformer 是图灵完备的，但软注意力思维链（CoT）Transformer 是否具备此性质仍是开放问题。本文证明：具有长度泛化能力的软注意力 CoT Transformer 是图灵完备的。具体而言，通过将计数型 RASP（C-RASP）扩展为思维链形式，并引入因果掩码，在一元字母表（更一般地，字母受限语言）下实现了图灵完备性。尽管对任意语言不成立，但加入相对位置编码后，其扩展版本可在任意语言上实现图灵完备性。我们通过训练 Transformer 模型完成需复杂（非线性）算术推理的语言任务，实证验证了该理论。
原文摘要 · Abstract (English)
Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are Turing-complete. In this paper, we prove a stronger result that length-generalizable softmax CoT transformers are Turing-complete. More precisely, our Turing-completeness proof goes via the CoT extension of the Counting RASP (C-RASP), which correspond to softmax CoT transformers that admit length generalization. We prove Turing-completeness for CoT C-RASP with causal masking over a unary alphabet (more generally, for letter-bounded languages). While we show this is not Turing-complete for arbitrary languages, we prove that its extension with relative positional encoding is Turing-complete for arbitrary languages. We empirically validate our theory by training transformers for languages requiring complex (non-linear) arithmetic reasoning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。