The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought

📄 arXiv: 2605.18079v1 📥 PDF

作者: Moritz Brösamle, Stephan Eckstein

分类: cs.LG, cs.CC, cs.CL

发布日期: 2026-05-18

备注: Accepted to ICML 2026

🔗 代码/项目: GITHUB

💡 一句话要点

研究低精度Softmax Transformer的表达能力，结合CoT实现图灵机模拟

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer Softmax注意力 低精度量化 Chain-of-Thought 图灵机模拟 表达能力 推理任务

📋 核心要点

  1. 现有Transformer表达能力的研究通常依赖于Hardmax注意力、高精度等，与实际应用模型存在差距。
  2. 本文通过分析低精度Softmax Transformer，结合Chain-of-Thought，实现了图灵机的模拟。
  3. 实验表明，该方法在Sudoku推理任务中表现出更好的可学习性，验证了理论结果的有效性。

📝 摘要（中文）

本文分析了具有Softmax注意力机制和激活值/注意力权重舍入的标准Transformer解码器的表达能力，并允许深度和宽度随上下文长度呈对数增长。研究表明，使用Chain-of-Thought (CoT) 可以构建具有三元激活和良好分离的注意力分数的Hardmax Transformer来模拟图灵机。这使得可以将构造转换为等效的Softmax Transformer，而无需先前方法所需的不切实际的参数大小或激活精度。此外，本文分析了一种最近提出的summarized CoT范例，并表明它可以更有效地模拟图灵机，模型大小与空间界限呈对数关系，而不是时间界限。最后，通过Sudoku推理任务的实证测试，验证了结果与可学习性的一致性，优于先前的高精度结果。代码已开源。

🔬 方法详解

问题定义：现有Transformer表达能力的研究，通常依赖于Hardmax注意力机制、高精度激活值，以及其他架构修改，这使得理论分析结果与实际应用的模型存在脱节。实际应用中，Softmax注意力机制和低精度量化更为常见。因此，如何分析实际应用中Transformer的表达能力是一个重要的问题。

核心思路：本文的核心思路是利用Chain-of-Thought (CoT) 的思想，将复杂的计算过程分解为多个步骤，并通过Transformer的注意力机制来模拟这些步骤。通过构建一个能够模拟图灵机的Transformer，证明了其具有通用计算能力。关键在于如何将高精度的计算过程映射到低精度的Transformer中，并保证计算的正确性。

技术框架：本文的技术框架主要包括以下几个步骤：1) 构建一个Hardmax Transformer，使用三元激活和良好分离的注意力分数，通过CoT模拟图灵机。2) 将Hardmax Transformer转换为等效的Softmax Transformer，避免了不切实际的参数大小或激活精度。3) 分析summarized CoT范例，证明其能更有效地模拟图灵机。整体流程是从理论上构建一个能够模拟图灵机的Transformer，然后将其转换为实际可用的Softmax Transformer。

关键创新：本文最重要的技术创新点在于，证明了低精度Softmax Transformer在结合Chain-of-Thought的情况下，能够模拟图灵机，从而具有通用计算能力。与现有方法相比，本文的方法更贴近实际应用，不需要高精度激活值和复杂的架构修改。此外，summarized CoT的引入进一步提高了模拟图灵机的效率。

关键设计：在Hardmax Transformer中，使用了三元激活，即激活值只能取-1、0、1三个值。注意力分数需要良好分离，保证每个时刻只有一个位置被关注。在Softmax Transformer中，通过调整参数，使得Softmax的输出近似于Hardmax的输出。Summarized CoT通过对CoT步骤进行总结，减少了计算量，提高了效率。具体的参数设置和网络结构细节在论文中有详细描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，本文提出的方法在Sudoku推理任务中表现出更好的可学习性，与先前的高精度结果相比，更符合实际情况。这表明低精度Softmax Transformer在结合Chain-of-Thought的情况下，能够有效地解决复杂的推理问题。具体的性能数据和对比基线在论文中有详细描述。

🎯 应用场景

该研究成果可应用于各种需要复杂推理和决策的任务中，例如自然语言处理、知识图谱推理、智能问答等。通过降低Transformer的精度要求，可以降低计算成本和存储空间，使其更容易部署在资源受限的设备上。此外，该研究也为理解Transformer的表达能力提供了新的视角，有助于设计更高效的Transformer架构。

📄 摘要（原文）

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.