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/
