10,626 文字
こんにちは皆さん、今日も見に来ていただきありがとうございます。今日は推論の複雑性について少しお話ししましょう。
メビウスの帯の上に小さなアリがいると想像してください。この小さなアリは解決策を探しています。例えば、推論クエリがあるとしましょう。この時、選択肢が2つあります。1つは、システムの状態空間に次元を追加するという選択肢。もう1つは、このアリがメビウスの帯上を歩くための5つの線形ステップを追加するという選択肢です。どちらがより良い解決策でしょうか？
例えば、アリがメビウスの帯上を7歩進むことができるとします。または、もっと複雑になりますが、クラインの壺を使うことも考えられます。どちらが良いでしょうか？状態空間に次元性を追加して、アリにより多くの探索を許可するか、それともマルチステップ推論を行うか？
これはもちろん、複雑なクエリを処理する際に、高次元の探索空間または高次元の大規模言語モデルを持つことが良いのか、それともマルチステップ推論モデルを選ぶべきかという問題に転換されます。つまり、次元性のためにトレーニングするか、マルチステップ推論のためにトレーニングするかということです。
状態空間に限定せず、より高次元の特徴ベクトルやより高次元の埋め込みベクトルなど、どのようなものでも考えてみてください。どの特定の状態を高次元にするかは重要ではなく、単に考え方の問題です。
ここで視点を変えて、アリからクモに変えてみましょう。クモには非常に特殊な特性がありますよね？そうです。この場合、あなたはどう答えますか？2つの選択肢があります。状態空間に次元を追加するか、クモがメビウスの帯上でさらに5つの線形ステップを追加できるようにするか。どちらが良いでしょうか？
トポロジー上にクモのような、ショートカットを使うことができるオブジェクトがある場合、シンプルなトポロジーを選ぶか、クラインの壺を使うか考えてみてください。どのようなモデルを選びますか？
もちろん、私たちは地球上でこれを行っているので、重力というもう一つの制約があります。このクモは推論を行うために別の境界条件を必要とします。より高次元のショートカットを開発したでしょうか？
では、大規模言語モデルを使って複雑な推論タスクを解決するために何が必要でしょうか？より複雑なタスクのために、より高次元の空間、より高次元の潜在空間、より高次元の埋め込み、より高次元の特徴ベクトル、より高次元の隠れ層が必要なのか、それとも全く別のものが必要なのでしょうか？
マルチステップ推論トレーニングのためのトレーニングデータセットを提供する必要があるのでしょうか？これは、教師あり微調整や強化学習に焦点を当てるとまた別の問題になります。メビウスの帯のような低次元空間にとどまりながら、より複雑なタスクに対してより多くのステップの自由度を提供するとしたら、どちらを選びますか？
実は答えは比較的簡単で、新しい研究によれば、私たちのLLMは未見かつ困難な推論タスクを実行するために、テスト時の計算トークンを生成し使用することができます。ご存知のように、OpenAIのO1やO3、DeepSeek R1などは推論モデルですが、それらの経験的な成功にも関わらず、このテスト時の追加の推論トークンがどのように改善された推論性能に寄与しているのかは不明確なままです。
既存の文献では一般的に、より多くの推論トークンの必要性を「より解決が困難な問題」と関連付けていますが、これは本当でしょうか？昨日、コーネル大学とハワード大学から新しい研究が発表され、さらに一歩進んだ解決策が示されました。
著者らは、様々なタスクと異なるLLMにわたって、タスクの精度がピークに達する推論トークンの量が存在することを実証しました。これを「臨界長」と呼びますが、タスクとモデルによって異なります。しかし、タスク自体の複雑さを測定することは非常に難しいので、彼らは複雑さの問題を近似するための数学的フレームワークが必要だと主張しています。
彼らは、多くのタスクが数学的に単純なモデル、決定性有限オートマトン（DFA）モデルで表現できるという事実に基づくフレームワークを提案しています。単純化されたDFAの推論複雑性を形式化することで、彼らの結果は推論ステップを推論時にどのように活用するかについての実用的な洞察を提供します。
彼らは臨界長を、DFAの基本的な特性から線形回帰モデルで予測できると主張しています。正しい臨界長にあるもののみを含めるために棄却サンプリングを実行することで、LLMの推論性能を向上させることができます。
これは新しい考え方ではなく、2025年2月の北京大学、MIT、ミュンヘン工科大学の研究でも、LLMにおける思考の連鎖の長さに関する類似のアイデアが提示されています。彼らは推論ステップの数が増えると、最初はパフォーマンスが向上するが、その後低下し始めることを発見しました。つまり、「より多い」が常に「より良い」というわけではないのです。
このDFAフレームワークは、タスクの難しさと推論の複雑さを形式的に定量化し、より深い洞察を得ることを可能にします。この形式主義により、より広範囲の推論タスクを研究することができ、数学を超えて進むことができます。
過去数週間の私の動画では数学に強く焦点を当てていましたが、数学は結果が正しいか正しくないかが簡単に判断できたからです。言語では、結果を異なる方法で解釈できるかもしれません。しかし今、私たちは数学的な近似、単純化を持っていますが、数学を超えることができます。これは素晴らしいことです。
2025年3月の「状態空間モデルにおける状態の錯覚」という研究を覚えていますか？彼らは、状態ベースのモデルが状態追跡の表現力においてオートレグレッシブ変換器モデルよりも本当に優位性があるかという質問に「いいえ」と答え、MAMBAモデルが状態追跡に苦戦していることも発見しました。
状態追跡に馴染みがない場合は、2024年4月の論文「LLM状態：LLMとの長期的タスク計画のためのオープンワールド状態表現」をお勧めします。1年以上前のものですが、良い論文です。これは意思決定の仕組みを示しています：LLMは注意機構、状態推定器、ポリシーとして機能します。
シンプルな入力から始め、周囲を見回し、部屋内のオブジェクトを識別します。次にタスクの説明と目標があります。LLMの注意機構はシンプルです：生成されたオブジェクトマップがあり、「牛乳0」「冷蔵庫0」などがあります。そして次の入力が「牛乳」「冷蔵庫」で、特定のタスクのためのアクションが「牛乳を取る、電子レンジを開ける、牛乳を電子レンジに入れる、電子レンジを閉める、電子レンジをつける、正常に加熱されるまで待つ」である場合、システムの新しい状態が生成されます。この新しい状態では、牛乳は加熱された状態で電子レンジ内にあり、冷蔵庫は開いています。このようにシンプルで、ポリシーは私が示したプランにすぎません。
適切な論文を読めば多くのことが簡単になるということですね。2025年2月の「LLMによる行動と計画のための状態追跡と推論」（インペリアル・カレッジ・ロンドン計算機科学部）を推奨します。彼らの方法論の核心には「状態の連鎖」と呼ばれるものがあり、目標の痕跡、状態の痕跡、推論の痕跡を含む少数の短い例の単純な注釈があります。
シンプルな推論の痕跡から、システムのパフォーマンスを向上させるために、彼らは状態の連鎖方法論を提案しています。これは推論の痕跡だけでなく、目標の痕跡（どれだけの目標が達成されたか）と状態の痕跡（例えば、牛乳が現在どこにあるか）も含んでいます。システムのこれらの特性を追跡・記録するのは興味深いですね。
2025年3月の中国・北京大学高信頼ソフトウェア技術研究所、香港大学、上海AI研究所による研究では、思考の連鎖を持つ変換器内の有限状態オートマトンに関する興味深い研究が行われています。これは状態追跡のメカニズム的研究です。
変換器内部を覗いて、推論の痕跡、より複雑な推論の痕跡の推論生成のための思考の連鎖トレーニングを持つ変換器内部を見たいと思います。変換器内部には、有限状態オートマトンというより単純な数学モデルがあることがわかります。
彼らは、思考の連鎖でトレーニングされた変換器アーキテクチャがどのようにアルゴリズムを学習できるのかについてのメカニズム的理解が限られていると指摘しています。彼らは変換器モデル内の暗黙的な有限状態オートマトン（FSA）の証拠を提供し、各状態が個別のニューロン集合によって圧縮されていることを発見しました。
これは興味深いことで、変換器アーキテクチャの完全な複雑さを解決しようとするのではなく、変換器内部に特定のトピックに対してより簡単に解決できる単純化された数学モデルを識別しています。なぜ簡単な解決空間でそれらを解決し、より複雑なシステムに戻って見ないのでしょうか？
彼らは位数2の巡回群から始めます。この系は二つの状態q1とq0を持ち、遷移規則を定義できます。そして彼らはこの美しい可視化を提供し、二つの状態q0とq1、さまざまな入力M1から何でも、自己注意や多層パーセプトロンなどの通常の変換器アーキテクチャがあれば、出力は単に状態q_hatなどになると言います。
変換器シーケンスを遷移規則で訓練すると、モデルは最終状態を予測するだけでなく、中間のステップバイステップを生成するように訓練されます。これが思考の連鎖であり、変換器に状態遷移を明示的に追跡することを強制します。これが変換器内部で起こっており、変換器の能力があるため、FSAという単純なモデルを回復することができます。
この論文の中心的な主張は、Z2遷移規則によって生成されたデータで思考の連鎖を持つ変換器をトレーニングした後、変換器は効果的にFSAをシミュレートする内部メカニズムを学習するということです。
これがどのように機能するのか、著者らは詳細な分析を行っています。私はここで詳細に焦点を当てていませんが、重要なのは変換器アーキテクチャ内にFSAが存在し、数学的理解のための単純化があるということです。彼らは変換器がどのようにこれを行うかを調査し、多層パーセプトロン内の特定のニューロン、特に後半のものが専門化していることを発見しました。
一組の明確なニューロンが、システムが状態q0にあるべき時に活性化し、別の一組のニューロンが状態q1にあるべき時に活性化します。これを緑の点と黄色または橙色の点で見ることができます。MLP出力ニューロンを見ると、FSAが内部に存在することが明確にわかります。
これらの異なるニューロン集合を活性化させることで、MLPは内部的にこれらの2つの状態を表現し区別することができ、次のステップに対して正しく遷移規則を適用することができます。つまり、私たちは完全に詳細を理解していない変換器の複雑さを通り抜ける必要はなく、単純化されたバージョンで役立つFSAモデルを持っているということです。
トレーニング後、思考の連鎖を持つ変換器は、後期層MLPニューロン内の2つの異なるニューロン集合を使用して、Z2の2つの状態（緑と橙色）を区別することで、暗黙的なFSAを復元することに成功しました。
一歩下がって考えてみると、思考の連鎖でトレーニングされた変換器は表面的なパターンだけでなく、内部表現を構築しています。この内部表現がどのように見えるかに興味があり、それが暗黙的なFSAであることがわかりました。この表現は、ニューラルネットワーク内のニューロンの活性化パターン、特に後期層MLPニューロンに機械的にリンクされています。
ChatGPTに簡単なFSA例を提供してもらいました。この単純なFSAは、限られた数の状態を持つマシンが、与えられた固定ルール（遷移ルール）に従って状態間を遷移することで、特性を追跡できることを示しています。シンプルなFSAで追跡特性が可能になりました。素晴らしい！これで要素が揃いました。
ハワード大学の研究者によれば、LLMには最適な思考長があります。これは興味深いことです。彼らは様々なモデル（Q1 7B、Llama 8B、DeepSeek V3、Mistral 8B、GPT-4 Omni、O3 mini、QAT、Llamaモデルからの全ての蒸留モデルなど）を調査しました。最後の列は、モデルの最終強化学習トレーニングステージを示しており、いくつかは指示チューニング、いくつかは私たちが探している思考の連鎖強化学習です。
思考の連鎖推論のための最適な思考長は何でしょうか？彼らは2022年のGoogle研究スタンフォード大学の有名なBig Benchタスク、あるいは2024年1月のMITとMeta AIのCROOKS評価を使用しました。どのベンチマークを選んでも、臨界長が存在します。
推論の精度が向上し、向上し、向上した後、閾値があり、推論にさらにトークンを提供しても性能が低下することがわかります。上昇、上昇、上昇、そして性能低下というパターンが見られます。
個人的な意見ですが、これは急激な変化ではなく、例えばいくつかのタスクでは線形の傾きがわずかに低下することがほとんど気づかないレベルですが、他のモデルではチャック！と急落してから飽和するような変化が見られます。
この臨界長をLと呼び、彼らはすべての異なるLLMを調査し、すべての異なるモデルが明確に識別可能な臨界長を持っていることを発見しました。モデルごとに臨界長が異なることがわかります。これは生成長がゼロから4000トークンまで変化する臨界長指標です。
しかし、より多くの推論トークンが精度の低下と相関する場所もあり、「より多い」が常に「より良い」わけではないことを示しています。ただ最適な長さのスイートスポットを見つける必要があるのです。
これはどうして可能なのでしょうか？彼らのコアアイデアは、テスト時計算の最適な推論長がDFAの実行長と関連しているということです。これは、テスト時計算における推論トークンの臨界長を制御する最も重要な要因は何かという質問に答えます。
彼らは、推論タスクのベンチマークが決定性有限オートマトン（DFA）として表現でき、DFAの言語が複雑性を測定するための明示的な次元を提供すると述べています。これは私たちが探していたものです。複雑性とは何か、複雑性自体に内在する複雑性の異なる次元を本当に定義する方法について話しました。
彼らは、数学における決定性有限オートマトン理論の数学的単純化を使用すれば、複雑性を完全に定義するのではなく、80-90％特徴付ける測定可能な次元を見つけることができると言います。
私たちが考慮するすべてのタスクは、タスクを解決する一つの方法が暗黙的にDFAを推論してその状態を横断することであるようなDFAとして表現できます。スタンフォードの公式数学表記を見たい場合はここにあります。
別の例で実行長を明示的に示すと、例えばビット文字列のパリティを評価する問題を考えます。この問題は、偶数または奇数の2つの状態を持つDFAとして表現でき、パリティを決定する一つの方法は、DFAの偶数状態から始め、文字ごとにDFAを通過し、最終状態を報告することです。したがって、実行長nは5です。なぜなら私たちは正確に5つの文字を処理したからです。
もう一つの特性はDFA状態空間サイズであり、これが私がこのビデオをメビウスの帯、クラインの壺、そして2次元多様体上を移動する小さなアリと小さなクモから始めた理由です。
実際のLLMアプリケーションに戻り、タスクの複雑性を定義したいと考えています。実行長は特定のタスクを解決するために必要な最小の推論ステップに対応し、DFA状態空間サイズは根本的な決定空間の複雑性を表しています。この決定空間はユークリッド空間になるのか、非ユークリッド空間になるのか？
コーネルとスタンフォードによる素晴らしいアイデアがあります。問題の実行長を増やすということは、別の +1 mod 2を追加するか、実行長を4（1,2,3,4）、状態数を2（0と1）から実行長5（1,2,3,4,5）、状態数2（0と1）に増やすことを意味します。または、システムが存在できる状態の数を増やします。つまり、問題を拡張して「0+2+1 mod 3」は何かと問うと、実行長は4ですが、状態数は0、1、2の3つになります。
これらは基礎となる単純化されたDFAモデルであり、複雑性が何に敏感であるかを理解しようとしています。実行長（メビウスの帯上で小さなアリが移動できるステップ数、4、5、または7ステップ）なのか、システムが存在できる状態の数（より高次元の空間）なのか？
この問いへの答えを見てみましょう。コーネル大学とハーバード大学による2025年4月2日（私にとっては昨日）の「臨界的思考」という研究があります。これは、私たちの推論モデル（R1やO3モデル）でテスト時計算スケーリングを行う際に、どの複雑性が最適な推論長を支配しているかについての研究です。
彼らは、タスクの複雑性の測定1と測定2、つまり実行長と次元性を発見しました。先に示したすべての推論タスクには特定のL（不連続性）があり、各タスクはDFAとしても表現できます。状態の数は、最大深さや個別の演算子、この追跡の可能な値、または特定のサイズ、数値範囲、オブジェクトの数、人の数などです。複雑性の2番目の特性である実行長は、ステップ数や式の深さなどです。
彼らはベンチマークタスクごとにこれらを特定し、複雑性がどのように臨界長に影響するかを調査しました。ここで結果があります。臨界長と実行長の関係、および臨界長と状態数の関係があります。相関係数は実行長で0.84、状態空間サイズKで0.234です。
彼らは、異なるLLMの臨界長Lが実行長と強く相関していることを発見しました。つまり、ビデオの冒頭の例で言えば、小さなアリがメビウスの帯上でどれだけのステップを移動できるかであり、状態空間のサイズではありません。高次元空間で移動し、与えられた複雑性に対する解空間であるトポロジカル空間でショートカットを開発する小さなクモではないのです。
あなたは「これは間接的な議論だ」と言うかもしれません。なぜなら、これは実行長と臨界長の間の相関関係に過ぎず、臨界長は100％の相関関係で正しい答えを保証するものではないからです。臨界長は正しい臨界長を持っていることを示すだけで、その臨界長の答えを事実確認する必要があります。
例えば、「結果は42です」と言うことも、「ユーザーXYZによって指定された2つの整数を足した結果は42です」と言うこともできます。どちらの答えも正しい結果を示していますが、推論の長さが全く異なります。したがって、長さだけでは正確性の完璧な指標ではありませんが、1つの指標ではあります。
著者らは、より大きな状態空間はより複雑な推論を意味する可能性があるため、この発見はやや驚くべきことだと述べています。私たちは、10億の自由パラメータの代わりに50億の自由パラメータを持つ言語モデルを使用すれば、より複雑な推論タスクに対処できると考えています。
しかし彼らの結果は、この形式の複雑性が最適な推論長に影響を与えていないように見えることを示しています。つまり、複雑な推論のためのより高次元の状態空間の次元性は、私たちが探している要因ではなく、最適な推論長に影響を与えていないように見えます。彼らは最適な推論長だけに言及していることを覚えておいてください。これは複雑な推論の正確性の指標です。
興味深い質問は、これがユークリッド空間の幾何学だけに限定されているのかということです。これが、このビデオの冒頭で非ユークリッド的トポロジカル空間を選んだ理由です。
彼らはさらに進み、私にとって主要な結果とも言える仮説を提示しています。この現象の一つの可能性は、LLMが明示的に完全に表現するのではなく、このオートマトンを表現するためにショートカットに依存している可能性があるということです。
有限状態オートマトンの単純化された表現に対してもAIが内部でショートカットを行うというこのトピックは、私にとって非常に魅力的ですが、この研究の主要部分ではないので、次のビデオで取り上げます。
彼らはGitHubリポジトリと必要なすべてのコードを提供してくれています。ありがとうございます。推論について学んだことを振り返ると、私たちは推論について何も知らないと言えるでしょう。これは複雑なトピックであり、なぜそれが機能し、いくつかのデータを提供するのかについてはまったく分かりません。経験的に試しているだけです。
しかし著者らは、テスト時計算における追加の推論トークンは、状態空間の次元性で測定されるより複雑なDFAを表現するためではなく、実行長で測定される暗黙的な状態追跡をサポートするという仮説と一致していると述べています。
これは理論的に、すべての公式に示され暗黙的に隠されているすべての含意があれば、より低次元のLLMを使用できることを意味します。ただし、より多くのマルチステップ推論能力を与えるだけで、より高次元の状態でシステムを表現するより高い複雑性を構築する必要はありません。
しかしこれは本当なのでしょうか？彼らは、臨界長Lと正確性の確率の間に強い相関関係があると述べています。これは正確性の確率に戻ることになりますが、素晴らしい研究なので自分で読んでみてください。
彼らは、LLMの最高のパフォーマンス（90％の精度）が推論の約50トークンで発生する場合、10トークンの文字列を持つ解決策はおそらく短すぎ、推論の150トークンを持つ解決策は長すぎる可能性があると主張しています。
モデルのL*、推論トークンの完全な長さがどこにあるかを知っていれば、テスト時に生成された解決策の中から、その長さの解決策だけをフィルタリングすることができます。言語モデルは、推論トークンの生成を続ける場合、正しい中間結論を上書きすることがあります。または、早すぎる停止で十分に詳しく説明できないかもしれません。これは私の最近の動画のトピックである「思考不足」と「思考過剰」です。
彼らは、テスト時の計算スケーリングを最適なゾーンに制限することによって、推論トークンシーケンスの間違った長さからくるオーバーシューティングとアンダーシューティングのエラーを排除できると期待しています。
私は、推論トークンシーケンスの長さだけが、推論トークンシーケンスの正確性に対する信頼できる信号を与えるかどうかは疑問です。なぜなら、私は正しい答えを求めているからです。解決策を見つけようとしていますが、それは決して単純なことではありません。
スタンフォードとコーネルによるこの研究からの結果を見てみましょう。予測された最適な長さによる推論チェーンのフィルタリングから生じる精度の向上をまとめています。「旧精度」と「新精度」（フィルタリング後）の差が示されています。
これは数値データまたはグラフで表示されており、異なるモデルで異なる精度向上が達成されていることがわかります。最良のものは3.8%の向上で、これは蒸留されたO1モデルです。次にQ2 32BのPlus 3.7%精度向上があります。
全体的に見ると、改善は0.2%から3.8%の範囲の一桁台です。これらのモデルにはすべて小さなジャンプがありますが、これが本当に推論精度を向上させる解決策なのでしょうか？最大で3.8%の向上にとどまり、これは本当の解決策とは言えないでしょう。
これは完璧な推論長が存在するという指標であり、何らかの形でそれを考慮すべきですが、それが主要な指標なのかどうかについては、個人的には疑問があります。
著者らは、予測された最適な長さによる推論チェーンのフィルタリングから生じる精度の向上について述べ、モデルの精度を最大3.8%まで向上させることができると述べています。
フィルタリングは、前述のようにトレーニング時ではなく、推論時（テスト時の計算）に行われます。これは、予測された最適な長さから離れすぎた思考の連鎖の長さをフィルタリングするだけです。この最適な長さは、すべてのシステム、すべてのLLMサイズ、異なる企業によって生成されたすべてのLLMによって異なります。
彼らは、この研究の方向性に沿って、トレーニング段階中に推論の長さを追跡することが、トレーニングプロセスが最適点に達したことやタスクの習得が最適に機能していることを示す有用な診断信号として機能する可能性があると結論付けています。
テスト時の計算スケーリングから推論の長さが全体モデルの精度に最大3.8%の影響を与えることを理解し、テスト時の計算からトレーニング時（教師あり微調整と強化学習）に移行すると、トレーニング段階（テスト時の計算段階ではなく）で推論の長さを追跡することでも改善される可能性があるという議論は理解できます。
しかし、個人的には本当に納得していません。解空間の異なるトポロジー、非ユークリッド空間について話しましたが、まだ多くの未解決の質問があります。
大規模言語モデルの推論を理解する上で、私たちがもっと進んでいると思っていましたが、特にテスト時の計算、マルチオン推論モデルを見ると、何が起こっているのか、どのようにこの結論に至るのかについて、まだ明確には分かっていません。
しかし、次のビデオでは、LLMの推論についての異なる見解と、他の研究者たちが発見したことについて見ていきます。そして、私たちが組み立てることができるパズルのピースを解決しようとします。
もし興味があれば、このチャンネルを購読してください。次のビデオでお会いしましょう。
コメント