“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”
The Expressive Power of Transformers with Chain of Thought
思维链步数如何决定 Transformer 的计算能力,多项式步恰为 P
论文从理论上问:生成中间 token 是否从根本上扩展了仅解码器 Transformer 的计算能力。答案是肯定的,但增幅取决于中间生成量:对数步数只比标准 Transformer 略有提升,线性步数(假设使用 projected pre-norm)能新增识别所有正则语言的能力,并且仍落在上下文相关语言之内;多项式步数配合广义 pre-norm 则恰好能识别多项式时间可解的问题类,这是首次用标准复杂度类精确刻画某类 Transformer。
评论者把它当作 Transformer 加思维链在理论上能解决任何 PTIME 问题的依据,也用它解释为什么计数等任务离不开思维链。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“particularly with chain of thought”
“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”
“Chain of thought increases the class of problems which fixed depth transformers can solve: The Expressive Power of Transformers with Chain of Thought”
“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”
“I think the more obvious explanation has to do with computational complexity: counting is an O(n) problem”
看全部 16 条 →
“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”
“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.”
“Autoregressive mode completely alleviate the problem as it can align its internal representation with the letters and it can just keep explicit sequential count.”
“chain of thought let's transformers break out of TCO complexity and be UTM.”
“sufficiently deep transformers with chain of thought have been shown to be theoretically capable of solving a very large class of problems.”
“transformers with sufficient chain of thought can solve any problem in P: The Expressive Power of Transformers with Chain of Thought”
“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.”
“by the same authors about this very thing! The Expressive Power of Transformers with Chain of Thought”
“the computational characteristics of LLMs are well-characterized by papers like The Expressive Power of Transformers with Chain of Thought”
“Notably Will Merrill's work: The Expressive Power of Transformers with Chain of Thought”
- The Expressive Power of Transformers with Chain of Thought (Revised) ↗yawboakye · 2024-03-24 · 20 分