技術要約：カリキュラム学習による推論の習得 II：構成的汎化（Compositional Generalization）

1. 問題設定

本論文は、複雑な問題をより単純な部分問題の解決策を組み合わせることで解く能力である**構成的汎化（compositional generalization）**の理論的基盤を調査している。これは、人工知能における思考の連鎖（Chain-of-Thought, CoT）推論の中核となるメカニズムである。取り組んでいる核心的な問いは、「問題を部分へと分解することが、直接解くよりも効率的な学習をもたらすのは、いつ、なぜなのか？」という点である。

この問いに答えるため、著者らは**セミオートマトン・シミュレーション（semiautomaton simulation）**を用いて問題を定式化している。セミオートマトンは、未知のマルコフ的で定常的な遷移関数 $\pi^*: S \times \Sigma \to S$ によって定義される。初期状態 $s_0$ と入力ワード $w_{1:T}$ が与えられたとき、目標は $T$ ステップ後の終端状態 $s_T$ を予測することである。中間状態 $s_{1:T}$ は思考の連鎖（chain of thought）を構成する。このモデルは、状態追跡、正規言語認識、およびモジュロ演算を捉えている。

本論文では、以下の2つの具体的な学習設定を研究している：

1. 対話型思考の連鎖監督（Interactive Chain-of-Thought Supervision, iSFT）： 学習者は、計算の任意のステップ $t$ における状態を、1単位のコストで返してくれるオラクルにアクセスできる。目標は、低い誤差を持つモデルを学習するために必要なオラクル・クエリ数（クエリ複雑性）と訓練インスタンス数（サンプル複雑性）を最小化することである。
2. 検証可能な報酬を伴う強化学習（Reinforcement Learning with Verifiable Rewards, RLVR）： 学習者は、長さ $B \ll T$ の短いインスタンスを一定の確率で解くことができる、事前学習済みの「弱い」参照モデル $\pi_{ref}$ と、終端状態の予測の正誤をチェックするアウトカム・ベリファイア（結果検証器）にアクセスできる。目標は、長いホライゾンにおいて弱いモデルを展開した際に発生する成功確率の指数関数的な低下を克服し、長さ $T$ のインスタンスを効率的に解けるように参照モデルを改善することである。

2. 手法

著者らは、長いシーケンスをより短い部分問題へと再帰的に分解し、それらを解く方法を学習してから、その解決策を合成するオートカリキュラム（autocurriculum）ベースのアプローチを提案している。このアプローチは、シリーズのパートIに基づき、**構成（composition）とブースティング（boosting）**のテンプレートを利用している。

コアとなるアルゴリズム構成要素

• 構成（Composition）： 長さ $\tau$ のインスタンスを解くように訓練されたモデルは、$T = L\tau$ であるとき、$L$ 回構成されることで長さ $T$ のインスタンスを解くことができる。ただし、構成の下では誤差が蓄積するため、短距離のモデルは高い精度で訓練されなければならない。
• ブースティング（Boosting）： 短い部分問題に対して必要な高精度を実現するために、著者らはマルチスケール・ブースティング戦略を採用している。これには、現在のアンサンブルが失敗する「困難な」インスタンスに焦点を当てた再重み付け分布上で、複数の弱い学習器を訓練し、それらを集約する（例：多数決）プロセスが含まれる。
• 自己生成カリキュラム（Self-Generated Curriculum）： 固定されたスケジュールではなく、学習者は、より細かいスケールで訓練されたモデルの失敗に基づいて、どの部分問題に対して訓練を行うかを適応的に選択する。

主要な技術的革新

• 逆サンプリング（Inverted Sampling）： ブースティングに固有の分布シフトを扱うための中心的な技術的貢献は、新しいサンプリング手法である。周辺分布の再重み付けされた混合物からの標準的な棄却サンプリングは非効率的である（最悪の場合 $\Omega(L)$ 個のサンプルを必要とする）。著者らは、長いシーケンス内のすべての $L$ 個の部分インスタンスに対して独立して棄却サンプリングを適用してから、受理されたインスタンスを一つ一様に選択するという逆サンプリングを導入した。これにより、学習アルゴリズムに必要な近似保証を維持しつつ、サンプル複雑性を大幅に削減し、受理確率を部分インスタンスの数に比例させることに成功した。
• マルチスケール再帰（Multiscale Recursion）： アルゴリズム（AutoLearn）は、ブースティング ＋ 構成のテンプレートを再帰的に適用する。それは長さ $T$ のインスタンスを長さ $\tau$ の部分問題へと分解し、さらにそれらを長さ1（次トークン予測）に到達するまで分解していく。これにより、より短い、より簡単な問題を解くモデルが、より困難な問題を解くために構成される階層構造が作成される。
• Guess-and-Check for RLVR： 中間状態のラベルが直接利用できないRLVRの設定において、著者らは、弱い参照モデルとベリファイアを使用して、インタラクティブ・オラクルをシミュレートする。各ブロックのロールアウトを生成し、ブロックの終端状態を検証することで、中間状態を効果的に「ラベル付け」し、カリキュラムを構築することができる。

3. 主要な貢献と結果

設定 I: iSFT (Interactive Supervision)

本論文は、セミオートマトンを**劣多項式（subpolynomial）**のクエリおよびサンプル複雑性で学習するアルゴリズム AutoLearn を提示している。

• 結果： クエリおよびサンプル複雑性は $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ によって上界が抑えられる。
• 比較： これは、直接的なシミュレーション手法に固有の $\Omega(T)$ の障壁を打破するものである。
  • フルCoT監督（Full CoT Supervision）： すべての状態にラベルを付けるために、インスタンスあたり $\Omega(T)$ のクエリを必要とする。
  • エンドツーエンドのフィードバック（End-to-End Feedback）： 中間的な接地（grounding）なしには終端状態から汎化できないため、$\Omega(T)$ のサンプル複雑性を必要とする。
• メカニズム： 部分問題を適応的に選択し、分布シフトを管理するために逆サンプリングを使用することで、AutoLearnは $T$ に対して劣多項式、具体的には $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ の複雑性を達成する。

設定 II: RLVR (Verifiable Rewards)

本論文は、弱い参照モデル $\pi_{ref}$ を、ブロックレベルの能力（$B$）からフルレングスの能力（$T$）へと向上させる AutoLearn.RL を提示している。

• 結果： アルゴリズムは、長さ $T$ のインスタンスに対して高い精度を達成するが、そのコストは全長 $T$ ではなく、より短いブロック長 $B$ における参照モデルのカバー率によって支配される。
• カバレッジの拡大（Coverage Expansion）： 標準的なRLVR手法は、長さ $T$ において非自明なカバレッジを必要とするが、これは長さ $B$ でのみカバレッジを持つ場合、指数関数的に起こりにくい（すなわち $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$）。AutoLearn.RLは、この要求を長さ $B$ におけるカバレッジへと軽減する。
• 複雑性：
  • サンプル複雑性：$\tilde{\mathcal{O}}(d/\varepsilon)$。
  • クエリ複雑性：$\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$。
  • 計算コスト：$\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$。
• 意義： 「バーイン（burn-in）」コストは短尺スケール $B$ におけるカバレッジに依存するため、長さ $T$ における実効的なカバレッジを、指数関数的に小さい状態から定数へと拡大させることができる。

4. 意義と主張

本論文は、構成と自己生成カリキュラムの組み合わせが、カリキュラムを用いないベースラインと比較して、監督および計算コストにおいて**超多項式的な削減（superpolynomial reductions）**を達成できると主張している。

• 理論的基礎： 問題を分解することがなぜ助けになるのかについて、厳密な理論的枠組みを提供している。すなわち、構成を通じて学習者が精度要件とシーケンス長をトレードオフすることを可能にし、ブースティングが部分問題に対する必要な精度を保証するからである。
• 効率性： セミオートマトン・シミュレーションのようなタスクにおいて、学習は $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$ の複雑性で達成可能であることを示しており、これは標準的なアプローチの線形な $\Omega(T)$ 複雑性に対する劇的な改善である。
• 汎化： 学習者が自ら問題を設計するオートカリキュラムは、単なるヒューリスティックではなく、長期間の推論における統計的および計算的な障壁を克服するためのメカニズムとして、理論的に正当化できることを示唆している。
• 限界と今後の課題： 著者らは、モデルクラスをマルコフ的モデルに限定していること（Transformerのようなフル履歴アテンションを除外している）や、決定論的な遷移を仮定していることなどの簡略化を認めている。これらを非マルコフ的モデルや確率的遷移へと拡張することが重要な今後の方向性であると述べている。また、現在の結果は $T$ に対する劣多項式依存を達成しているが、有限のミス境界（finite mistake bounds）のようなより強い仮定を必要とする可能性のある、対数多項式（polylogarithmic）依存の達成は依然として未解決の課題であるとも指摘している。

要約すると、本論文は、適応的なカリキュラムによって導かれ、逆サンプリングなどの手法によって支えられた構成的汎化が、直接的な学習手法では困難な複雑な逐次タスクを学習するための、証明可能なほど効率的な経路を提供することを確立している。