💬 NLP

TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning

本論文は、相互作用をツリー構造のノードとしてモデル化し、報酬のコントラストと方策学習の効率を高めるために、プロンプトのルートと中間プレフィックスの両方を混合ターミナル報酬によって動的にターゲットにすることで、マルチターン・エージェンティック強化学習におけるロールアウト予算の割り当てを最適化する統一フレームワークであるTRACEを導入するものである。

原著者： Heming Zou, Qi Wang, Yun Qu, Yuhang Jiang, Lizhou Cai, Yixiu Mao, Ru Peng, Xin Xu, Weijie Liu, Kai Yang, Saiyong Yang, Xiangyang Ji

公開日 2026-06-10

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Heming Zou, Qi Wang, Yun Qu, Yuhang Jiang, Lizhou Cai, Yixiu Mao, Ru Peng, Xin Xu, Weijie Liu, Kai Yang, Saiyong Yang, Xiangyang Ji

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、非常に賢いが経験の浅い学生（AI）に、数学の問題を解いたり巨大な図書館から答えを見つけ出したりといった複雑なパズルを教えようとしている教師だと想像してください。この学生は、試行錯誤を行い、最後に「はい」か「いいえ」という単純な結果を得ることで学習します。

問題は、教師には学生に練習させるための限られた時間（予算）があることです。もし教師が、同じ簡単なパズルを100回や、同じ不可能なパズルを100回解かせるとしたら、学生は何も学べません。彼らには、成功することもあれば失敗することもある、ちょうど「適切な難易度」のパズルを試させる必要があります。

この論文では、この問題を解決するための新しい手法であるTRACEを紹介しています。以下に、シンプルな比喩を用いてその仕組みを説明します。

1. 問題点：「退屈な」経路による時間の浪費

これまでのAI学習では、研究者はパズルを選び、AIが最初から最後まで解き終えるまで放置していました。

問題点: パズルが簡単すぎると、AIは常に勝ちます。逆に難しすぎると、AIは常に負けます。どちらの場合も、最後に得られる「はい／いいえ」という答えは、AIに対して「どこで間違えたのか」を教えてくれません。
従来の方法: 研究者は、より良いパズルを最初に選ぼうとしましたが、一度AIが解き始めると、最後まで走りきるのをただ見守るだけでした。AIが途中で行き詰まっているかどうかを確認するために、途中で止めることはありませんでした。

2. 解決策：「分岐する道」（TRACE）

TRACEは、AIの試行を一本の直線ではなく、**多くの枝を持つ「木」**として扱うことで、ゲームのルールを変えます。

AIが宝物（正解）を見つけるために山登りをしている様子を想像してください。

根（スタート地点）: まず、TRACEは出発点（パズル）を確認します。そして、「このパズルは、成功と失敗が混ざり合うような内容か？」と予測します。もし簡単すぎたり難しすぎたりすれば、それはスキップします。もしそれが良い「学習用」のパズルであれば、AIを山へ送り出します。
枝（中間地点）: これが魔法の部分です。AIが登山をしている最中、道の分かれ道（意思決定を行う「ターン」）に到達したとします。ここでTRACEは立ち止まり、こう問いかけます。「もしAIがこの特定のルートを通ったとしたら、それは勝利につながる可能性が高いか、それとも敗北につながる可能性が高いか？」
- もしそのルートが、確実に勝利に終わるか、あるいは確実に敗北に終わることが分かっているなら、TRACEはその探索に時間を無駄に使いません。
- もしそのルートが不確実（成功するか失敗するか50/50の確率）に見えるなら、TRACEはこう言います。「この特定のルートにもっと多くの登山者を送り込んで、何が起こるか見てみよう！」

3. 「水晶玉」（予測モデル）

TRACEはどうやってどのルートが不確実なのかを知るのでしょうか？それは「水晶玉（予測モデル）」を使用しています。

この水晶玉は、これまでの登山の履歴（AIが行ってきた思考や行動）を観察します。
そして、成功の確率を推定します。
もし水晶玉が「ここでの成功率は50%だ」と言えば、そこは時間をかけるべき完璧な場所です。それは、AIが「勝つルート」と「負けるルート」を比較できる「学習ゾーン」にいることを意味しているからです。

4. 結果：より少ない努力で、よりスマートな学習を

限られた時間を「不確実な」部分だけに集中させることで、TRACEは豊かな**対照（コントラスト）**の地図を作り上げます。

AIは単に「失敗した」と知るだけでなく、「左の道を選んだから失敗したのだ。右の道を選んでいれば成功していただろう」ということを学ぶことができます。
これにより、たとえ練習に費やす総時間（予算）が以前と同じであっても、AIにとってより強力な学習シグナルを生み出すことができます。

まとめ

TRACEを、単に選手にランニングの練習をさせるだけのコーチではなく、スマートなコーチだと考えてください。

正しいレースを選ぶ: 挑戦的でありながら、勝ち目もあるレースを選びます。
トリッキーな曲がり角で止まる: 選手が走る様子を見守ります。もし選手が、滑るかもしれないし滑らないかもしれないという、トリッキーな曲がり角に差し掛かったら、コーチは他の選手をその全く同じ曲がり角に送り込み、滑るのと踏みとどまる際の違いを確認させます。
時間を節約する: 単調な直線コースや、到底登れない崖などは無視します。

この手法を用いることで、AIモデル（具体的にはQwen3）は、従来のメソッドと同じ計算量でありながら、数学、多段階の質問、およびツールの使用において、より優れた能力を獲得したことが論文によって示されています。TRACEは、平坦で退屈な練習セッションを、一歩一歩が新しい学びとなる、ダイナミックで分岐のある探求へと変えるのです。

技術要約: TRACE — 効率的なエージェンティック強化学習のための統一されたロールアウト予算配分フレームワーク

1. 問題提起

検証可能な報酬（RLVR: Reinforcement Learning with Verifiable Rewards）を用いた強化学習は、大規模言語モデル（LLM）の推論能力やエージェント的行動を強化するための重要なメカニズムとして浮上しています。しかし、標準的なRLVRパイプラインは、長い思考連鎖（CoT: Chain-of-Thought）の軌跡生成や、環境との交互作用（interleaved interaction）に伴う高い計算コストによる重大な計算効率の低下に直面しています。

核心となる課題は、**報酬のコントラスト（reward contrast）**にあります。結果のみに基づく報酬設定（ロールアウトの最後に単一のバイナリ報酬が割り当てられる設定）では、学習信号が疎で不均衡になりがちです。

プロンプトレベル: 過度に単純、あるいは過度に複雑なプロンプトは、分散の低いフィードバック（例：すべて成功、またはすべて失敗）を生成し、方策更新のための信号をほとんど提供しません。
軌跡レベル: 長いマルチターン・ロールアウトに対して単一の終端報酬を割り当てることは、ローカルなクレジット割り当て（credit assignment）を不明瞭にします。中間的なフィードバックがない場合、モデルはどの特定のターンや決定が最終的な結果に寄与したのかを区別できません。

既存の手法は、有望なプロンプトへのロールアウト予算の割り当て（プロンプト選択）や、プロンプトあたりのロールアウト回数の割り当て（ロールアウト数割り当て）によってこれを軽減しようと試みています。しかし、これらのアプローチはロールアウトをアトミックな（不可分な）軌跡として扱っています。一度プロンプトが選択されると、ロールアウト全体が線形に生成され、結果が不確実な中間ターン（プレフィックス）で分岐する可能性が無視されます。その結果、固定されたサンプリング予算内で情報の密度を最大化することに失敗した、「平坦な」ロールアウトの集合性が生じてしまいます。

2. 手法: TRACE

著者らは、ロールアウトの割り当てをツリー構造のプロセスとして再定義する、TRACE (Tree Rollout Allocation for Contrastive Exploration) という統一フレームワークを提案しています。独立した線形な軌跡を生成する代わりに、TRACEは、プロンプトの「ルート」と中間的な「プレフィックス」の両方に動的に予算を割り当てることで、同一の条件付けコンテキスト内で混合された終端報酬（成功と失敗の両方）を観察する確率を最大化します。

主要な技術構成要素:

ツリー構造のロールアウト:
- 本フレームワークは、ReActスタイルの相互作用（思考-行動-観察）をツリー内のノードとしてモデル化します。
- ルート (Roots): 初期のプロンプト ( $x$ )。
- プレフィックス (Prefixes): $t$ ターン後に形成される中間履歴 ( $H_t$ )。
- 分岐 (Branching): 訪問された任意のプレフィックスにおいて、システムは「事実的な（factual）」ブランチから逸脱する「反事実的な（counterfactual）」継続（新しいサフィックス）を生成するために、追加の予算を割り当てることができます。
統一された割り当て目的関数 (Mixed-Reward Contrast):
- 目標は、条件付き成功確率 ( $V^\pi_t$ ) が0でも1でもなく、中間的な値をとるアンカー（ルートまたはプレフィックス）に予算を割り当てることです。
- 理論的根拠: 本論文では、ロールアウトのサフィックスに沿った条件付き成功予測の期待二次変動は、 $V^\pi_t(1 - V^\pi_t)$ に等しいことを確立しています。この値は「コントラストのポテンシャル」を表します。コントラストポテンシャルの高いアンカーに予算を割り当てることで、同じプレフィックスから派生した兄弟ブランチが反対の終端結果を持つ確率が最大化され、最適化のための暗黙的なペアワイズ選好信号が生成されます。
2段階の割り当てプロセス:
1. グローバル・ルート割り当て: サンプリングの前に、予測器が候補プロンプトのプールに対して成功確率を推定します。予算は、混合された結果を生む可能性が高いプロンプトに割り当てられます（決定的な成功または失敗となるものは除外されます）。予測確率が0または1に近いプロンプトには、予算は割り当てられません。
2. ローカル・プレフィックス拡張: アクティブなプロンプトに対して、システムは訪問された非終端プレフィックスを特定します。その後、これらのプレフィックスから追加の継続を生成するためにローカル予算を割り当てます。割り当ては、観測された事実的な結果が予測確率と異なるプレフィックス（すなわち、反事実的なブランチによって結果が反転する可能性が高い箇所）を優先します。
共有可能な汎用予測器:
- 軽量な予測器 ( $\tilde{V}_\psi$ ) が、プレフィックス履歴から条件付き成功確率を推定します。
- これは、収集されたロールアウトツリーから導出された再帰的なターゲット（終端報酬のボトムアップ的な経験平均）を用いた平均二乗回帰を通じて訓練されます。
- この予測器が、ルート選択とプレフィックスの分岐決定の両方をガイドします。
ツリー認識型方策最適化:
- 得られるツリー構造は、暗黙的なステップごとの選好ペア（例：同じプレフィッションからの成功した継続 vs 失敗した継続）を提供します。
- これらは、標準的な結果のみの更新よりも密な信号を利用して、方策を更新するために使用されます。

3. 主要な貢献

統一された定式化: 本研究は、混合報酬コントラストの割り当てを、サンプル効率的なRLVRの単一の視点として定式化し、プロンプトフィルタリング、ロールアウト数割り当て、およびプレフィックスレベルの分岐を、ロールアウトツリーのアンカーに対する戦略的な予算決定として統合しました。
理論的導出: 著者らは、共通の降下セット目的関数に基づいた割り当てユーティリティを導出し、プレフィックスレベルの情報がグループの難易度予測を厳密に改善すること、および中間的な不確実性に予算を割り当てることがコントラストポテンシャルを最大化することを証明しました。
TRACEフレームワーク: この視点を、予測器に導かれた予算制約付きのツリー・ロールアウト・フレームワークへと具現化し、手作業によるプロセス報酬を必要とせずに、グローバルなルート割り当てとローカルなプレフィックス拡張を統合し、暗黙的なクレジット信号を強化しました。

4. 実験結果

著者らは、Qwen3-8BおよびQwen3-14Bバックボーンを用い、3つのマルチターン・エージェンティック・ベンチマーク（数学的推論：DeepScaler, AIMEなど、マルチホップQA：HotpotQA, 2Wikiなど、および関数呼び出し：BFCL v4）でTRACEを評価しました。

性能向上: 同等のサンプリング予算の下で、TRACEは標準的なGRPO、プロンプト選択手法（PCL）、およびランダムなツリーベース手法（TreePO）を含むベースラインを一貫して上回りました。
- 例: マルチホップQAにおいて、TRACEはQwen3-14Bの平均精度を競争力のあるベースラインより2.8ポイント向上させました。
- 例: 数学的推論において、TRACEはQwen3-8Bの精度を70.0%（GRPO）から71.1%に向上させました。
効率性とコントラスト: TRACEは、有効比率（Effective Ratio）（成功と失敗の両方の結果を含むプロンプト/ロールアウトの割合）を大幅に増加させました。
- Qwen3-8Bを用いた数学的推論において、有効比率は26.8%（GRPO）から60.6%（TRACE）へと上昇しました。
- これは、TRACEが飽和した（決定論的な）アンカーから、コントラスト豊かな領域へと予算を効果的に転換していることを示しています。
アブレーション研究:
- ルート割り当てとプレフィックス拡張の両方の段階が、それぞれ独立して性能向上に寄与しました。
- フレームワークは異なる予算サイズに対して堅牢性を示し、「予算の形状」（ルートの広がり vs 継続の深さ）が極めて重要であることが判明しました。

5. 意義と主張

本論文は、エージェンティックRLVRのサンプリングを、「どれだけ多くの独立したロールアウトを引くか」という問いから、「ロールアウトツリー内のどこで分岐するか」という問いへと再構築するものだと主張しています。

より密な学習信号: スケーラブルな結果報酬を、より密な混合報酬コントラストと暗黙的なステップごとの選好ペアに変換することで、TRACEは計算コストを増やすことなく方策更新の信号を増幅します。
汎用性: このアプローチは、ルートとプレフィックスの両方に共有の予測器に依存しており、プレフィックスの履歴が分岐決定をガイドできる学習可能な局所的不確実性の概念を保持していることを示しています。
限界: 著者らは、TRACEが主に明確な終端検証を伴う結果のみのRLVR向けに設計されていることを指摘しています。明確な終端報酬を欠くタスクでは、コントラスト目的関数の再検討が必要になる可能性があります。また、現在の予測器の実装はバニラな設定であり、特定のエージェンティック・タスクに特化したより強力な予測器の開発が今後の課題であるとしています。

要約すると、TRACEは、不確実性をターゲットとし、報酬コントラストを最大化するようにツリー構造のロールアウトを動的に構築することで、マルチターン・エージェンティックRLにおける固定されたロールアウト予算の情報の価値を最大化する体系的な手法を提供します。