按年被提到
20222024 · 4 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2207.00729 · cs.CC

The Parallelism Tradeoff: Limitations of Log-Precision Transformers

并行性的权衡:对数精度 Transformer 的局限
William Merrill, Ashish Sabharwal · 2022

证明对数精度 Transformer 可被常数深度阈值电路模拟

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2023-05-18 · 最近 2024-09-17
4不同的人
4活跃月份
5讨论串
22被引(OpenAlex)

论文证明,算术精度为输入 token 数对数量级的 Transformer(且前馈网络可用线性空间计算)可被常数深度、对数空间一致的阈值电路模拟,从而借助已知复杂性结果刻画其计算能力。例如若 L ≠ P,则这类 Transformer 甚至无法准确求解线性方程或判定任意含空产生式的上下文无关文法的成员关系。作者据此推测性地提出“并行性权衡”:任何与 Transformer 同样可并行的架构都会受到类似限制,这暗示规模化范式可能存在固有弱点。

HN 为什么提它

评论者用它说明 Transformer 因高度并行而受限于 TC0 类计算,无思维链时难以做状态跟踪,并以此类推到 SSM。

其他难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1Transformer 架构
2电路复杂性与 TC0 类(threshold circuits)
3复杂性类 L 与 P
4形式语言与上下文无关文法

学习路径

读这篇之前,按顺序读书架上的 5 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先理解 Transformer,再看它的表达能力上界和下界的已有结果,以及形式化模型 RASP,最后读对数精度 Transformer 的复杂度结论。

  1. 1
    Attention Is All You Need注意力就是你所需要的一切 · 2017

    要证明的对象就是 Transformer 的计算结构。

    读注意力层、前馈层以及残差结构,这些是后面要用电路模拟的部分。

  2. 2
    Are Transformers universal approximators of sequence-to-sequence functions?Transformer 是序列到序列函数的通用逼近器吗? · 2019

    证明 Transformer 能通用逼近序列函数,是表达能力的一个上界对照。

    读通用逼近结论的假设,特别是对精度的假设。

  3. 3
    On the Turing Completeness of Modern Neural Network Architectures论现代神经网络架构的图灵完备性 · 2019

    证明 Transformer 图灵完备,目标论文说明这类结果依赖不现实的精度假设。

    读图灵完备的构造与其对精度的假设。

  4. 4
    Thinking Like Transformers像 Transformer 一样思考 · 2021

    RASP 把 Transformer 的计算抽象成一种编程语言,是理论刻画的相关工作。

    读RASP 的基本操作及其与注意力的对应。

  5. 5

    是目标论文最接近的前作:用常深度阈值电路模拟饱和 Transformer。

    读饱和注意力的假设与电路模拟的结论,对照目标论文如何放宽到对数精度。

  6. 6
    The Parallelism Tradeoff: Limitations of Log-Precision Transformers并行性的权衡:对数精度 Transformer 的局限 · 2022 · 就是这篇

    目标论文:对数精度 Transformer 可被常数深度阈值电路模拟。

    读主定理的陈述、复杂度类的含义,以及对 Transformer 能力局限的推论。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用shawntan · 2023-05

“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).”

引它说明并行带来的代价是 Transformer 能计算的程序类型受限
The Alan Turing Institute has failed to develop modern AI in the UK原评论 ↗
引用lambdaviking · 2023-05

“Our prior paper discusses how this works more in depth: The Parallelism Tradeoff”

引自己先前的论文,说明 Transformer 因并行性解决不了某些问题
A Logic for Expressing Transformers原评论 ↗
引用nyrikki · 2024-03

“To practically scale, parallelism is required, and the ability to find algorithms within the L or TC0 complexity classes is limited.”

拿它说明对数精度 Transformer 局限于 TC0 式并行计算
“Emergent” abilities in LLMs actually develop gradually and predictably – study原评论 ↗
引用logicchains · 2024-06

“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.”

引它说明没有 CoT 时 SSM 与 Transformer 都不能高效做状态追踪
The illusion of state in state-space models原评论 ↗
引用logicchains · 2024-09

“fixed depth transformer without chain-of-thought are very limited in what they can express: The Parallelism Tradeoff”

引它说明固定深度、无 CoT 的 Transformer 表达能力很有限
Chain of Thought empowers transformers to solve inherently serial problems原评论 ↗
引用logicchains · 2024-09

“Under more realistic assumptions, transformers without chain of thought are actually limited in what they can solve: The Parallelism Tradeoff”

引它说明在更现实的假设下,无 CoT 的 Transformer 可解的问题有限
Chain of Thought empowers transformers to solve inherently serial problems原评论 ↗