技術的サマリー：固定予算下でのロールアウト情報量の最大化

1. 問題定式化

本論文は、スパースな終端報酬（例：$R \in \{-1, +1\}$）下における、ツール拡張型大規模言語モデル（LLM）の強化学習（RL）における構造的なボトルネックに対処する。核心的な課題は、**固定予算下でのロールアウト情報量（RIFB）**である。

標準的なグループ相対方策最適化（GRPO）では、利得信号は $B$ 個のロールアウトからなるグループ内の報酬の標準偏差で正規化される。あるプロンプトに対する $B$ 個の独立したロールアウトがすべて同じ結果（すべて成功またはすべて失敗）をもたらす場合、標準偏差はゼロとなり、利得がゼロに崩壊する。その結果、方策に勾配が注入されず、それらのロールアウトに費やされた計算リソースは無駄になる。

著者は、独立サンプリングにおけるこの問題を不可能性結果として定式化する：

• 定理 1: 予算に依存しない任意の独立サンプリャーにおいて、崩壊（分散ゼロ）の確率は $p^B + (1-p)^B$ である。ここで $p$ はプロンプトあたりの成功確率である。
• 示唆: $p \to 0$ または $p \to 1$（困難なプロンプト）の場合、崩壊しない確率は予算に対して高々線形に増加する（$B \cdot \min(p, 1-p)$）。したがって、単にロールアウト予算 $B$ を増やしても、困難なプロンプトにおけるゼロ勾配領域から逃れることはできない。崩壊率は予算の大きさに関わらずゼロから離れて一定に留まる。

2. 手法：INFOTREE

独立サンプリングの限界を克服するため、著者はINFOTREEを提案する。これは、訓練時にどの状態を拡張するかを最適化するツリー探索フレームワークであり、何個サンプリングするかを最適化するものではない。

2.1 部分モジュラ性定式化

中核的な洞察は、ツリーの情報量を最大化するためにどの中間状態を拡張するかを選択する問題は、単調部分モジュラ最大化問題として定式化できるという点である。目的関数 $F$ は以下の 3 つの項から構成される：

1. カバレッジ: リーフのバックアップ値 $\bar{Q}(s)$ を追跡する。
2. 新規性: 訪問回数に基づく探索項（古典的な UCB 項）を追跡する。
3. 対比: トークンレベルのエントロピーから導出される、兄弟ノード間の結果の多様性を追跡する。

著者は $F$ が単調かつ部分モジュラであることを証明する。これにより、最適拡張スケジュールに対して理論的な $(1 - 1/e)$ 近似保証を持つ貪欲セレクタを使用できる。

2.2 UUCB セレクタ

部分モジュラ問題に対する貪欲解は、**不確実性認識型 Upper Confidence Bound（UUCB）**スコアをもたらす。これは任意のヒューリスティックではなく、目的関数の閉形式の限界利得である：
$$\text{UUCB}(v) = \bar{Q}(v) + c\sqrt{\frac{\ln N(p_a(v))}{N(v)+1}} + \lambda_H \tilde{H}(v) - \lambda_C \tilde{C}(v) - \lambda_D \tilde{d}(v)$$

• $\bar{Q}(v)$: カバレッジ利得。
• 第二項: 新規性利得（標準的な UCB 探索）。
• $\lambda_H \tilde{H}(v)$: 対比利得。深さ層別化されたトークンレベルのエントロピーを表し（深さ間で比較可能になるよう正規化されている）。
• ペナルティ: $\lambda_C$ と $\lambda_D$ は、それぞれ予算制約を尊重するためにツール呼び出しコストと拡張深さをペナルティ化する。

2.3 システムコンポーネント

INFOTREE は、UUCB セレクタを 2 つの追加メカニズムと統合して、実用的な弱点に対処する：

• 適応的予算アロケータ（ABA）: 単一出力ツリー（崩壊しやすい）を持つプロンプトが、単一の高温ロールアウトによって「救出」可能かどうかを予測するために、オフラインで訓練された軽量 MLP。予測された救出確率が閾値を超えた場合、追加のロールアウトがトリガーされる。これにより、混合出力比率は約 58% から約 76% に向上し、予算オーバーヘッドは 5% 未満で済む。
• 推測的拡張: ワークロード時間を削減するため、ワーカーは潜在的に古くなった Q 値（境界付きの古さ）を使用して UUCB スコアを評価する。バージョンタグに基づいて拡張の受諾またはロールバックを行う調整ステップにより、オーバーヘッドは 14.3% から 4.8% に削減される。
• 階層的利得: ルートからリーフへの経路に沿った兄弟間の対比から導出される勾配信号であり、グループ正規化された GRPO 利得を補完する代替のクレジット割り当てメカニズムを提供する。

3. 主要な貢献

1. 理論的定式化: 本論文は RIFB を定義し、独立サンプリングが予算の大きさに関わらず困難なプロンプトにおいて持続的な崩壊に陥ることを証明する。
2. 部分モジュラ性への還元: 固定予算下でのツリー構築が部分モジュラ最大化問題であることを確立し、貪欲な UUCB セレクタに対して理論的な $(1-1/e)$ 保証を提供する。
3. 解析的導出: UUCB におけるエントロピーボーナスが、経験的なトリックではなく、部分モジュラ目的関数（対比項）の解析的な帰結であることを実証する。
4. システム設計: ABA と推測的拡張の導入により、情報量と計算効率のバランスを取る実用的なフレームワークを創出した。
5. 直交性: 著者は、選択メカニズムが軌道再重み付け（例：CW-GRPO）やロールアウト再利用（例：Tree-GRPO プレフィックス共有）とは直交する軸で動作することを示し、組み合わせによる利益が可能であることを明らかにした。

4. 実験結果

この手法は、数学的推論、ウェブ検索、ツール豊富なコーディング/OS エージェントにわたる 9 つのベンチマークで評価された。

• 性能: INFOTREE は、フラット GRPO、DeepSearch、Tree-GRPO、AT2PO、CW-GRPO、RC-GRPO を一貫して上回った。
  • AIME 2025において、INFOTREE は Mean@32 で 30.2 を達成した（フラット GRPO は 27.7、Tree-GRPO は 29.1）。
  • GAIAにおいて、56.0% の精度を達成した（フラット GRPO は 44.8%）。
• 組み合わせ性: INFOTREE を Tree-GRPO プレフィックス共有または CW-GRPO 貢献重みと組み合わせることでさらなる利益が得られ、アプローチの直交性が確認された。
• 頑健性: UUCB 係数（$\lambda_H, \lambda_C, \lambda_D$）に対する $5 \times 5 \times 5$ のハイパーパラメータグリッドにより、空間の 75% 以上が最適値から 2.1 ポイント以内に収まることが示され、手法がハイパーパラメータ調整に対して脆弱ではないことが示された。
• 効率性: ツリー探索にもかかわらず、推測的拡張によりウォールクロックオーバーヘッドは 4.8% に削減された。「ターゲットまでのステップ数（Mean@32 が 28 に達するまでのステップ数）」は、フラット GRPO の 248 から INFOTREE の 138 に減少し、ウォールクロック時間で 1.57 倍の改善となった。
• 勾配の情報量: 勾配ノルムの二乗の直接測定により、INFOTREE はフラット GRPO よりも 3.9 倍高い RIFB を生成することが示された。

5. 意義と主張

本論文は、ロールアウト戦略の設計を工学的な好意から、形式的に根拠のある最適化問題へと再位置づけることを主張する。

• ヒューリスティックから理論へ: エントロピーボーナスを経験的なトリックから、部分モジュラ目的関数の必須コンポーネントへと変換し、その採用に対する理論的根拠を提供する。
• 崩壊の解決: 部分モジュラ選択と適応的予算割り当てを通じて「ゼロ勾配」領域を明示的にターゲットにすることで、INFOTREE は困難なプロンプトにおける現在の GRPO ベースのエージェントの根本的な限界に対処する。
• 相補性: 結果は、ツリー構築によるロールアウト情報量の最大化が、独立サンプルの再重み付けや多様化に焦点を当てた既存の手法とは異なり、相補的な軸であることを示唆している。

著者は、ツリー構築エピソード内の固定方策という仮定や、検証可能な報酬を持たないオープンエンドタスクにおける結果の予備的な性質など、限界を指摘している。しかし、このフレームワークは、スパース報酬下でのツール拡張型エージェントの訓練に対する堅牢な解決策として提示されている。