量子位 09-17
o1方法性能无上限!姚班马腾宇等数学证明:推理token够多,就能解决任意问题
index_new5.html
../../../zaker_core/zaker_tpl_static/wap/tpl_keji1.html

 

OpenAI 用 o1 开启推理算力 Scaling Law,能走多远?

数学证明来了:没有上限

斯隆奖得主马腾宇以及 Google Brain 推理团队创建者 Denny Zhou 联手证明,只要思维链足够长,Transformer 就可以解决任何问题!

通过数学方法,他们证明了 Transformer 有能力模拟任意多项式大小的数字电路,论文已入选 ICLR 2024。

用网友的话来说,CoT 的集成缩小了 Transformer 与图灵机之间的差距,为 Transformer 实现图灵完备提供了可能。

这意味着,神经网络理论上可以高效解决复杂问题。

再说得直白些的话:Compute is all you need!

CoT 让 Transformer 运行更高效

首先需要说明的是," 可以解决任何问题 " 是一个通俗化的表述,严格来说,论文的核心结论是思维链(CoT)能够显著提升 Transformer 的表达能力。

作者首先通过理论分析,提出对于固定深度、多项式宽度、常数精度的 Transformer 模型,如果不使用 CoT,其表达能力将受限于 AC0 问题类别。(AC0 是一类可以在并行计算中高效解决的问题,但不包括需要复杂序列化计算的问题。)

在固定指数位的情况下,固定深度、对数精度的 Transformer 模型即使引入了正确的舍入操作,其表达能力也仅限于 TC0 问题类别。

但当引入 CoT 时,固定深度、常数精度的 Transformer 模型就能够解决任何由大小为 T 的布尔电路解决的问题。

这表明 CoT 显著扩展了模型的表达能力,使其能够处理更复杂的问题。

为了验证理论分析,论文在四个核心问题上进行了实验,考虑了基础(base)、CoT 和提示(hint)三种不同的训练设置:

模运算(Modular Addition):并行计算问题,论文展示了 CoT 如何提高模型在这个问题上的准确性;

置换群组合(Permutation Composition):需要序列化计算的问题,论文证明了 CoT 在解决这类问题上的有效性;

迭代平方(Iterated Squaring):典型的序列化计算问题,论文展示了 CoT 如何使模型能够有效地解决这类问题;

电路值问题(Circuit Value Problem):这是一个 P 完全问题,论文证明了即使是在模型深度较低的情况下,CoT 也能使模型能够解决这类问题。

首先在可并行的模运算问题上,输入是若干个模 7 的数,输出是它们的模 7 和。

实验结果表明,所有设置下的 Transformer 都能够学习模加;但在较长序列(如 n=16)上,CoT 的优势更加明显。

这说明即使是可并行问题,CoT 也能带来一定的效率提升。

在内在串行的置换群复合任务上,输入是 S_5 置换群中的若干个置换,输出是它们的复合结果。

结果,CoT 提高了低深度模型的准确性——

不使用 CoT 的 Transformer 即使深度较大也难以学习该任务(准确率约 20%),而使用 CoT 后即使是 1 层 Transformer 也能轻松学习(准确率 100%)。

对于迭代平方任务,输入是一个质数 p、一个整数 r 和若干个 "^2" 符号,输出是 r^ ( 2^k ) mod p。

实验结果与置换群复合任务相似:不使用 CoT 时。即使 16 层 Transformer 也难以学习;而使用 CoT 后。1 层 Transformer 就能完美求解。

这再次验证了理论分析,即迭代平方是内在串行的,需要 CoT 来提供必要的计算能力。

最后的电路值问题,输入是一个随机布尔电路的描述,输出是电路的最终输出值。

实验结果表明,在基准设置下,4 层 Transformer 的准确率约为 50%,8 层约为 90%,16 层接近 100%;

而使用 CoT 后,1 层 Transformer 就能达到接近 100% 的准确率。

这验证了理论结果,即 CoT 赋予了 Transformer 任意电路的模拟能力,使其能够解决电路值问题这一 P 完全问题。

CoT+Transformer 模拟门电路

除了上述实验,作者还对以下结论进行了理论证明:

对于任意一个可以用多项式大小的布尔电路计算的函数,都存在一个仅有常数层数的 Transformer,可以通过足够多步数的思维链(CoT)来模拟电路的计算过程,从而计算出这个函数。

证明的思路是先将布尔电路视为一系列逻辑门的组合,然后利用 Transformer 中的位置编码为每个逻辑门及其状态分配一个独特的表示,进而通过逐步计算来模拟整个电路的执行过程。

这个证明的关键,在于利用 CoT 来逐步模拟电路中每个门的计算

具体而言,对于一个有 T ( n ) 个门的电路,作者设计了一个 4T ( n ) 个 token 的输入序列。

这个序列包含了电路的完整描述,每个门用 4 个连续的 token 表示:门类型、两个输入门的索引和当前门的索引,并用输入序列中的第一个 token 指示了电路的输入值。

然后,作者构造了一个常数深度的 Transformer,这个 Transformer 的嵌入维度只需要 O ( log n ) ,就足以对 T ( n ) 个门进行编码。

在第一层,Transformer 读取输入序列,并将电路的描述信息存储到其位置嵌入中。

接下来是关键的 CoT 步骤。Transformer 逐步生成 4T ( n ) 个 token 的思维链,每 4 个 token 对应电路中的一个门。

对于第 i 个门 ,Transformer 执行以下操作:

利用注意力机制获取两个输入门的计算结果:如果输入门是电路的输入,可以直接从输入序列中读取;如果输入门是前面计算过的中间结果,则可以从思维链的对应位置读取。

根据门的类型(与、或、非等),用前馈网络计算当前门的输出。

将当前门的输出写回到思维链中,作为后续门的输入。

通过这一过程,Transformer 逐步模拟了电路中每一个门的计算,并将中间结果存储在思维链中。在生成完整个思维链后,最后一个门的输出就对应了电路的最终输出。

也就是说,通过将电路 " 展开 " 为一个长度为 O ( T ( n ) ) 的思维链,即使固有深度很浅,Transformer 也可以逐步执行电路中的计算。

在此基础上,作者进一步证明,具有 O ( T ( n ) ) 长度 CoT 的常数深度 Transformer,可以模拟任意 T ( n ) 大小的电路,因此其计算能力等价于多项式大小电路

理论打通了,实际可行吗?

能够模拟电路的计算过程,意味着 CoT+Transformer 能够解决可计算问题。

同时,这也说明只要有足够的 CoT 思考时间,大模型不需要扩展尺寸也能解决复杂问题。

有专业人士用一篇长文解释了 CoT 和图灵完备性之间的关系:

如果没有 CoT,Transformer 仅限于执行 AC0 复杂度类中的可并行任务;

CoT 推理从根本上改变了这一格局,它使 Transformer 能够通过中间推理 token 处理串行计算,从而增加计算深度并允许模型模拟 AC0 以外的更深层次的电路。

这一进步将 Transformer 带入了 P/poly 领域,即多项式大小电路可以解决的问题类型。

理论上,只要有足够的 CoT 步骤,Transformer 就可以模拟多项式大小电路可以执行的任何计算,从而缩小了 Transformer 与图灵机之间的差距。

但实际限制仍然存在,例如有限的上下文窗口和计算资源。要充分利用这一潜力,需要仔细的模型设计和优化。

还有人把这项成果和 OpenAI 的 " 草莓 ",也就是爆火的超强模型 o1 联系到了一起——

草莓同样也是思考的时间越长,准确性越高,按照这个思路,只要有好的模型,就能解决人类面临的一系列难题。

甚至有人表示,如果这项研究是真的,那么 AGI 就已经在到来的路上了……

不过也有人认为,这只是一个理论性的结果,距离实际应用还存在很大差距。

即使抛开理论与实际条件的不同,时间和成本问题就是一个重要的限制因素。

而且实验的一个假设是模型权重被正确设置,但实际模型的训练很难达到这一程度。

还有人指出,这种模拟门电路运算,并不是大模型实际学习和工作的方式。

换言之,如何将实际问题用布尔电路表示,是 Transformer 从能解决运算问题到能够解决实际问题的一个关键。

但现实中,诸如 " 如何治疗癌症 " 这样的问题,很难以电路的形式去描述。

虽然距离实际应用还有一系列问题要解决,但这项研究至少揭开了 CoT 的巨大潜力。

作者简介

本论文一共有四名作者,全部都是华人。

按署名顺序,第一位作者为清华姚班校友李志远,是马腾宇已毕业的博士生,现为芝加哥丰田技术学院(TTIC)的终身教授助理教授。

第二位作者是Hong Liu,也是马腾宇的博士生,现在在读,本科就读于清华,曾获得特等奖学金及优秀毕业生荣誉。

第三位是 Google Brain 推理团队创建者Denny Zhou,中科院博士,2017 年加入 Google 前在微软担任了 11 年的高级研究员。

最后是 2021 年斯隆奖得主、斯坦福大学助理教授马腾宇,他是姚班校友、陈丹琦的同班同学。

论文地址:

https://arxiv.org/abs/2402.12875

参考链接:

[ 1 ] https://x.com/denny_zhou/status/1835761801453306089

[ 2 ] https://www.reddit.com/r/singularity/comments/1fiemv4/denny_zhou_founded_lead_reasoning_team_at_google/

宙世代

宙世代

ZAKER旗下Web3.0元宇宙平台

逗玩.AI

逗玩.AI

ZAKER旗下AI智能创作平台

相关文章
评论
没有更多评论了
取消

登录后才可以发布评论哦

打开小程序可以发布评论哦

12 我来说两句…
打开 ZAKER 参与讨论