按年被提到
20232024 · 9 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2310.07923 · cs.LG

The Expressive Power of Transformers with Chain of Thought

带思维链的 Transformer 的表达能力
William Merrill, Ashish Sabharwal · 2023

思维链步数如何决定 Transformer 的计算能力,多项式步恰为 P

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 8 人首次 2024-03-24 · 最近 2026-09-09
8不同的人
11活跃月份
15讨论串
21被引(OpenAlex)

论文从理论上问:生成中间 token 是否从根本上扩展了仅解码器 Transformer 的计算能力。答案是肯定的,但增幅取决于中间生成量:对数步数只比标准 Transformer 略有提升,线性步数(假设使用 projected pre-norm)能新增识别所有正则语言的能力,并且仍落在上下文相关语言之内;多项式步数配合广义 pre-norm 则恰好能识别多项式时间可解的问题类,这是首次用标准复杂度类精确刻画某类 Transformer。

HN 为什么提它

评论者把它当作 Transformer 加思维链在理论上能解决任何 PTIME 问题的依据,也用它解释为什么计数等任务离不开思维链。

奠基之作难度 5 / 5约 90 分钟经得起时间
读之前最好知道
1计算复杂性理论(P、TC0 等复杂度类)
2形式语言与自动机(正则语言、上下文相关语言)
3Transformer 架构
4思维链(chain-of-thought)

HN 书评

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

“Transformers with chain-of-thought are strictly more powerful than transformers without it, and can efficiently solve classes of problems that would otherwise require exponentially increasing model depth: The Expressive Power of Transformers with Chain of Thought”

引用其形式化结果:带思维链的 Transformer 严格更强,能解决否则需指数级深度的问题
Simple tasks showing reasoning breakdown in state-of-the-art LLMs原评论 ↗
引用logicchains · 2024-09

“particularly with chain of thought”

引用它说明带思维链的 Transformer 表达能力很强
Ilya Sutskever's SSI Inc raises $1B原评论 ↗
引用shawntan · 2024-09

“Theoretical results exist that try to quantify the number of CoT tokens needed to reach different levels of computational expressibility: The Expressive Power of Transformers with Chain of Thought”

引用理论结果,量化达到不同计算表达力所需的 CoT token 数
Chain of Thought empowers transformers to solve inherently serial problems原评论 ↗
引用logicchains · 2024-09

“Chain of thought increases the class of problems which fixed depth transformers can solve: The Expressive Power of Transformers with Chain of Thought”

引用它说明思维链扩大了固定深度 Transformer 能解决的问题类别
Chain of Thought empowers transformers to solve inherently serial problems原评论 ↗
引用aithrowawaycomm · 2024-11

“I really think the answer is computational complexity: counting is simply too hard for transformers unless you use CoT. The Expressive Power of Transformers with Chain of Thought”

认为计数对 Transformer 太难,除非用 CoT,原因在计算复杂度
Something weird is happening with LLMs and chess原评论 ↗
引用aithrowawaycomm · 2024-11

“I think the more obvious explanation has to do with computational complexity: counting is an O(n) problem”

用计算复杂度解释:计数是 O(n) 问题,需要思维链
Something weird is happening with LLMs and chess原评论 ↗
看全部 16 条 →
引用logicchains · 2024-12

“We know from complexity theory that transformers with chain of thought are guaranteed to be able to reproduce a significant fraction of human reasoning, anything in the complexity class PTIME: The Expressive Power of Transformers with Chain of Thought”

引用它说明带思维链的 Transformer 必能复现相当一部分人类推理,即 PTIME 内的任何问题
Byte Latent Transformer: Patches Scale Better Than Tokens原评论 ↗
引用logicchains · 2024-12

“An LLM with chain of thought and unbounded compute/context can run any program in PTIME: The Expressive Power of Transformers with Chain of Thought, which is a huge class of programs.”

引用它说明有思维链且算力和上下文不限的 LLM 能运行 PTIME 内的任何程序
Computing Inside an AI原评论 ↗
引用Isinlor · 2025-01

“Autoregressive mode completely alleviate the problem as it can align its internal representation with the letters and it can just keep explicit sequential count.”

说明自回归加上显式逐步计数,才解决了 Transformer 数字母的问题
30% drop in O1-preview accuracy when Putnam problems are slightly variated原评论 ↗
引用inciampati · 2025-01

“chain of thought let's transformers break out of TCO complexity and be UTM.”

拿它说明思维链让 Transformer 突破 TC0 复杂度,成为通用图灵机
O1 isn't a chat model (and that's the point)原评论 ↗
引用logicchains · 2025-06

“sufficiently deep transformers with chain of thought have been shown to be theoretically capable of solving a very large class of problems.”

引用它说明足够深且带思维链的 Transformer 理论上能解决非常大的一类问题
The bitter lesson is coming for tokenization原评论 ↗
引用logicchains · 2025-09

“transformers with sufficient chain of thought can solve any problem in P: The Expressive Power of Transformers with Chain of Thought”

引用它说明思维链足够多的 Transformer 能解决 P 中的任何问题
The wall confronting large language models原评论 ↗
引用red75prime · 2025-09

“Their recognition abilities are limited by context-sensitive languages, if the number of steps in chain-of-thought is linear in the length of input.”

引用它说明 CoT 步数与输入线性相关时,Transformer 能识别的语言受限于上下文相关语言
Markov chains are the original language models原评论 ↗
引用anonymid · 2026-02

“by the same authors about this very thing! The Expressive Power of Transformers with Chain of Thought”

指出同一批作者写过讨论这个问题的论文,即回传 token 如何改变 CoT 的复杂度
I don't think AGI is imminent原评论 ↗
引用logicchains · 2026-08

“the computational characteristics of LLMs are well-characterized by papers like The Expressive Power of Transformers with Chain of Thought”

指出这类论文已较好刻画了 LLM 的计算特性,包括计算上限
Learning more about Claude's mathematical capabilities原评论 ↗
引用shawntan · 2026-09

“Notably Will Merrill's work: The Expressive Power of Transformers with Chain of Thought”

特别点出 Will Merrill 的工作,思维链让固定深度 Transformer 解决原本解决不了的问题
GPT-6 Astra, looped transformers, and hidden reasoning原评论 ↗
被提交为 story · 1 次