OpenAI は、o1 を使用して推論コンピューティング能力のスケーリング則を有効にすることで、どこまで実現できるでしょうか?

数学的な証明はここにあります：上限はありません。

スローン賞受賞者のTengyu Ma 氏と Google Brain 推論チームの創設者 Denny Zhou 氏は、思考の連鎖が十分に長ければ、Transformer はどんな問題でも解決できることを共同で証明しました。

彼らは数学的手法を使用して、Transformer が任意の多項式サイズのデジタル回路をシミュレートできることを証明し、その論文は ICLR 2024 に採択されました。

ネットユーザーによれば、CoT の統合により、Transformer とチューリング マシン間のギャップが縮まり、Transformer がチューリング完全性を実現できるようになりました。

これは、ニューラル ネットワークが理論的には複雑な問題を効率的に解決できることを意味します。

もっと率直に言えば、必要なのはコンピューティングだけです。

CoT により Transformer の実行効率が向上

まず、「あらゆる問題を解決できる」というのはよく使われる表現であることに注意する必要があります。厳密に言えば、この論文の核心的な結論は、CoT（コンセプトチェーン）がTransformerの表現力を大幅に向上させることができるというものです。

著者らはまず、理論分析を通じて、固定深度、多項式幅、定数精度の Transformer モデルの場合、その表現力は CoT を使用しない AC0 問題カテゴリに限定されると提案しています。(AC0 は並列コンピューティングで効率的に解決できる問題クラスですが、複雑なシリアル化計算を必要とする問題は含まれていません。)

固定指数の場合、固定深度と対数精度を持つ Transformer モデルは、正しい丸め操作を導入しても、TC0 問題カテゴリのみを表現します。

しかし、CoT が導入されると、固定深度と定数精度を持つ Transformer モデルは、サイズ T のブール回路で解決できるあらゆる問題を解決できるようになります。

これは、CoT によってモデルの表現力が大幅に拡張され、より複雑な問題を処理できるようになることを示しています。

理論的分析を検証するために、この論文では、ベース、CoT、ヒントの 3 つの異なるトレーニング設定を考慮して、4 つのコア質問に関する実験を実施しました。

• モジュラー加算：並列計算問題。本論文では、CoTがこの問題におけるモデルの精度をどのように向上させるかを示します。
• 順列合成：これは直列化計算を必要とする問題です。本論文では、この種の問題を解決する上でのCoTの有効性を示しています。
• 反復スクエアリング: 典型的なシリアル化計算問題であり、この論文では、CoT によってモデルがこの種の問題を効果的に解決する方法を説明します。
• 回路値問題：これはP完全問題です。この論文では、CoTを用いることで、モデルの深さが浅くてもこの種の問題を解くことができることが証明されています。

まず、並列化可能なモジュロ演算問題では、入力は 7 を法とする複数の数値であり、出力はそれらの 7 を法とする合計です。

実験結果によると、Transformer はすべての設定でモジュラー加算を学習できますが、CoT はより長いシーケンス (n=16 など) でより明らかな利点があります。

これは、並列化可能な問題の場合でも、CoT によって一定の効率向上がもたらされることを示しています。

本質的にシリアルな順列グループ合成タスクでは、入力は S_5 順列グループ内のいくつかの順列であり、出力はそれらの合成結果です。

その結果、CoT は低深度モデルの精度を向上させました。

CoT がないと、ディープ Transformer でもタスクの学習に苦労します (精度は約 20%)。一方、CoT があれば、単層 Transformer でも簡単に学習できます (精度は 100%)。

反復平方タスクの場合、入力は素数 p、整数 r、およびいくつかの "^2" 記号であり、出力は r^(2^k) mod p です。

実験結果は、順列グループ複合タスクの結果と似ています。CoT がないと、16 層の Transformer でも学習に苦労しますが、CoT があれば、単層の Transformer で問題を完璧に解決できます。

これは、反復的な二乗は本質的に順次的であり、必要な計算能力を提供するには CoT が必要であるという理論的分析をさらに検証します。

最終回路値問題は、ランダム ブール回路の記述を入力として受け取り、回路の最終出力値を出力します。

実験結果によると、ベースライン設定では、4 層トランスフォーマーの精度は約 50%、8 層トランスフォーマーは約 90%、16 層トランスフォーマーは 100% に近くなります。

CoT を使用すると、単一の Transformer レイヤーでほぼ 100% の精度を実現できます。

これは、CoT が Transformer に任意の回路をシミュレートする能力を与え、回路値問題の P 完全問題を解決できるようにするという理論的結果を検証します。

CoT+トランスフォーマーアナログゲート回路

上記の実験に加えて、著者らは以下の結論に対する理論的証明も示した。

多項式サイズのブール回路を使用して計算できる任意の関数については、関数を計算するために十分な数の思考チェーン (CoT) を通じて回路の計算プロセスをシミュレートできる、定数個のレイヤーのみを持つトランスフォーマーが存在します。

証明のアプローチは、まずブール回路を一連の論理ゲートの組み合わせとして扱い、次にトランスフォーマーの位置エンコーディングを使用して各論理ゲートとその状態に一意の表現を割り当て、最後に段階的な計算を通じて回路全体の実行プロセスをシミュレートすることです。

この証明の鍵は、CoT を使用して回路内の各ゲートの計算を段階的にシミュレートすることにあります。

具体的には、T(n)ゲートを持つ回路の場合、著者らは4T(n)トークンの入力シーケンスを設計しました。

このシーケンスには回路の完全な記述が含まれており、各ゲートは4つの連続するトークン（ゲートの種類、2つの入力ゲートのインデックス、現在のゲートのインデックス）で表されます。入力シーケンスの最初のトークンは、回路の入力値を示します。

次に、著者らは、埋め込み次元が O(log n) のみで十分である一定深度のトランスフォーマーを構築しました。これは、T(n) ゲートをエンコードするのに十分です。

最初のレイヤーでは、Transformer が入力シーケンスを読み取り、回路記述情報をその位置埋め込みに格納します。

次に重要なCoTステップが続きます。Transformerは4T(n)個のトークンのチェーンを徐々に生成します。4個のトークンからなる各チェーンは、回路内のゲートに対応します。

i 番目のゲートに対して、Transformer は次の操作を実行します。

• 2 つの入力ゲートの計算結果は、アテンション メカニズムを使用して取得されます。入力ゲートが回路の入力である場合は、入力シーケンスから直接読み取ることができます。入力ゲートが以前に計算された中間結果である場合は、思考チェーン内の対応する位置から読み取ることができます。
• 現在のゲートの出力は、ゲート タイプ (AND、OR、NOT など) に基づいてフィードフォワード ネットワークを使用して計算されます。
• 現在のゲートの出力を、後続のゲートの入力として思考チェーンに書き戻します。

このプロセスを通じて、Transformerは回路内の各ゲートの計算を段階的にシミュレートし、中間結果を思考チェーンに保存します。思考チェーン全体が生成された後、最後のゲートの出力が回路の最終出力に対応します。

言い換えれば、回路を長さ O(T(n)) の思考チェーンに「展開」することで、固有の深さが非常に浅い場合でも、Transformer は回路内の計算を段階的に実行できます。

これを基にして、著者らはさらに、長さ O(T(n)) CoT の一定深さのトランスフォーマーが任意のサイズ T(n) の回路をシミュレートできること、したがってその計算能力が多項式サイズの回路と同等であることを証明しています。

理論は正しいが、実際に実現可能だろうか?

回路の計算プロセスをシミュレートする機能は、CoT+Transformer が計算可能な問題を解決できることを意味します。

これはまた、CoT の思考時間が十分にある限り、大規模なモデルでもサイズを拡大せずに複雑な問題を解決できることを示しています。

専門家が、CoT とチューリング完全性の関係を説明する長い記事を書いています。

CoT がない場合、Transformer は AC0 複雑度クラスの並列化可能なタスクの実行に制限されます。

CoT 推論は、この状況を根本的に変え、Transformer が中間推論トークンを介してシリアル計算を処理できるようにすることで、計算の深さを増やし、モデルが AC0 を超えるより深いレベルの回路をシミュレートできるようにします。

この進歩により、トランスフォーマーは、多項式サイズの回路が解決できるタイプの問題である P/poly ドメインに導入されました。

理論上、十分な CoT ステップがあれば、Transformer は多項式サイズの回路が実行できるあらゆる計算をシミュレートできるため、Transformer とチューリング マシン間のギャップは縮まります。

しかし、コンテキストウィンドウや計算リソースの制限など、実用的な制約は依然として残っています。この可能性を最大限に実現するには、慎重なモデル設計と最適化が必要です。

この成果を、非常に人気があり、非常に強力な O1 モデルである OpenAI の「Strawberry」と関連付ける人もいます。

イチゴについて長く考えれば考えるほど、その精度は高まります。この考え方に従えば、優れたモデルさえあれば、人類が直面する一連の問題を解決できるのです。

この研究が真実であれば、AGI はすでに登場しつつあると示唆する人もいます...

しかし、これはあくまで理論的な結果に過ぎず、実際に適用されるまでにはまだ長い道のりがあると考える人もいます。

理論的な条件と実際の条件の違いを別にしても、時間とコストは重要な制限要因となります。

さらに、この実験の前提条件の 1 つは、モデルの重みが正しく設定されていることですが、実際のモデルをトレーニングするときにこのレベルの精度を達成することは困難です。

また、このアナログ ゲート回路の動作は、大規模なモデルが実際に学習して動作する方法ではないと指摘する人もいます。

言い換えれば、ブール回路を使用して実用的な問題をどのように表現するかが、計算上の問題を解決できることから実用的な問題を解決できることへの Transformer の変換における重要な側面です。

しかし、現実には「がんをどう治療するか」といった問題を回路の形で記述することは困難です。

実用化までにはまだ解決すべき一連の問題が残っているものの、この研究によって少なくとも CoT の大きな可能性が明らかになった。

著者について

この論文には4人の著者がおり、全員が中国人です。

著者順によると、第一著者は清華大学姚クラスの卒業生である李志遠（リー・ジーユアン）氏です。彼はプリンストン大学で博士号を取得した馬騰宇（マー・テンユ）氏のポスドク研究員であり、現在はシカゴトヨタ工科大学（TTIC）の助教授を務めています。

二人目の著者は、馬騰宇の博士課程の学生でもある洪劉氏です。彼は現在清華大学に在籍しており、特別奨学金と優秀卒業生の栄誉を受けています。

3人目は、Google Brain推論チームの創設者であるデニー・ジョウ氏です。彼は中国科学院で博士号を取得し、2017年にGoogleに入社するまで11年間、Microsoftで上級研究員として勤務していました。

最後に、2021年のスローン賞受賞者でスタンフォード大学助教授の馬騰宇（マ・テンユ）氏です。彼はヤオ・クラスの卒業生であり、陳丹奇（ダンチー・チェン）の同級生です。

論文アドレス: https://arxiv.org/abs/2402.12875 参考リンク: [1]https://x.com/denny_zhou/status/1835761801453306089 [2]https://www.reddit.com/r/sing..._zhou_founded_lead_reasoning_team_at_google/