“But we do pay for that in terms of what can be computed (The Parallelism Tradeoff - TL;DR: Transformers are limited in the types of programs/functions it can compute because of parallelism).”
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
证明对数精度 Transformer 可被常数深度阈值电路模拟
论文证明,算术精度为输入 token 数对数量级的 Transformer(且前馈网络可用线性空间计算)可被常数深度、对数空间一致的阈值电路模拟,从而借助已知复杂性结果刻画其计算能力。例如若 L ≠ P,则这类 Transformer 甚至无法准确求解线性方程或判定任意含空产生式的上下文无关文法的成员关系。作者据此推测性地提出“并行性权衡”:任何与 Transformer 同样可并行的架构都会受到类似限制,这暗示规模化范式可能存在固有弱点。
评论者用它说明 Transformer 因高度并行而受限于 TC0 类计算,无思维链时难以做状态跟踪,并以此类推到 SSM。
学习路径
读这篇之前,按顺序读书架上的 5 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出先理解 Transformer,再看它的表达能力上界和下界的已有结果,以及形式化模型 RASP,最后读对数精度 Transformer 的复杂度结论。
- 1
- 2
证明 Transformer 能通用逼近序列函数,是表达能力的一个上界对照。
读通用逼近结论的假设,特别是对精度的假设。
- 3
证明 Transformer 图灵完备,目标论文说明这类结果依赖不现实的精度假设。
读图灵完备的构造与其对精度的假设。
- 4
- 5
是目标论文最接近的前作:用常深度阈值电路模拟饱和 Transformer。
读饱和注意力的假设与电路模拟的结论,对照目标论文如何放宽到对数精度。
- 6The Parallelism Tradeoff: Limitations of Log-Precision Transformers
目标论文:对数精度 Transformer 可被常数深度阈值电路模拟。
读主定理的陈述、复杂度类的含义,以及对 Transformer 能力局限的推论。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“Our prior paper discusses how this works more in depth: The Parallelism Tradeoff”
“To practically scale, parallelism is required, and the ability to find algorithms within the L or TC0 complexity classes is limited.”
“SSMs are theoretically no more powerful than transformers, meaning without chain of thought they can't efficiently solve state-tracking problems, unlike RNNs: The Parallelism Tradeoff.”
“fixed depth transformer without chain-of-thought are very limited in what they can express: The Parallelism Tradeoff”
“Under more realistic assumptions, transformers without chain of thought are actually limited in what they can solve: The Parallelism Tradeoff”