这篇论文解决了低精度Transformer在链式思维推理中表达能力的关键理论问题，对研究Transformer计算极限和推理效率的学者很有价值，建议关注其理论突破和实验验证。
这篇论文研究了标准Transformer解码器在低精度（如软注意力、激活值和注意力权重取整）下的表达能力，发现其仍能模拟图灵机。作者通过构建硬注意力Transformer作为中间步骤，证明了软注意力Transformer在链式思维推理中具有强大的计算能力。研究还分析了摘要式链式思维范式，表明其能更高效地模拟图灵机，模型大小仅与空间边界对数相关而非时间边界。在数独推理任务上的实验验证了理论预测，与现有高精度结果相比更符合实际可学习性。代码已开源。
The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
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.