证明低精度Transformer能模拟图灵机，且推理效率更高。
The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
- 用低精度softmax注意力+链式思考，模拟图灵机
- 模型规模随空间复杂度对数增长，优于以往线性增长
- 适合研究模型表达力与推理效率的理论工作者
现有Transformer表达力分析多依赖hardmax注意力、高精度计算等脱离实际的假设。本文分析标准Transformer解码器在激活值和注意力权重量化下的表达能力，允许深度和宽度随上下文长度对数增长。中间步骤构建了三值激活、分离注意力分数的hardmax Transformer，通过链式思考（CoT）模拟图灵机。该构造可转化为无需极端参数或高精度的等价softmax Transformer。进一步分析最近提出的摘要式链式思考（Summarized CoT）范式，发现其以对数尺度随空间界缩放模型大小，比时间界更高效。在数独推理任务上验证预测，结果比高精度模型更贴近可学习性。代码已开源。
原文摘要 · Abstract (English)
Existing expressivity results for transformers typically rely on hardmax attention, high precision, and other architectural modifications that disconnect them from the models used in practice. We bridge this gap by analyzing standard transformer decoders with softmax attention and rounding of activations and attention weights, while allowing depth and width to grow logarithmically with the context length. As an intermediate step, we construct hardmax transformers with ternary activations and well-separated attention scores that simulate Turing machines using Chain-of-Thought (CoT). This lets us convert the constructions to equivalent softmax transformers without the unrealistic parameter magnitudes or activation precision that prior approaches would require. Using the same technique, we analyze a recently proposed summarized CoT paradigm and show that it simulates Turing machines more efficiently, with model size scaling logarithmically in a space bound rather than a time bound. We empirically test predictions made by our results on a Sudoku reasoning task and find better alignment with learnability than for prior high-precision results. Our code is available at https://github.com/moritzbroe/transformer-expressivity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。