🤖 AI

MURPHY: Feedback-Aware GRPO with Retrospective Credit Assignment for Multi-Turn Code Generation

本論文は、成功した改善からの報酬をより初期の有益な試行へと伝播させることで自己修正型コード生成を大幅に向上させるために、フィードバック条件付きロールアウト木と回顧的クレジット割り当てを活用するグループ相対方策最適化（GRPO）のマルチターン拡張であるMURPHYを導入する。

原著者： Chanakya Ekbote, Vijay Lingam, Sujay Sanghavi, Jun Huan, Behrooz Omidvar-Tehrani, Anoop Deoras, Stefano Soatto

公開日 2026-05-12

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

CC BY 4.0

原著者： Chanakya Ekbote, Vijay Lingam, Sujay Sanghavi, Jun Huan, Behrooz Omidvar-Tehrani, Anoop Deoras, Stefano Soatto

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

複雑なパズル、例えばコンピュータプログラムの作成をロボットに教える状況を想像してください。

従来の方法（「ワンショット」の誤り）
従来、ロボットにパズルを解くよう指示すると、間違えた場合、単に「もう一度試せ」と言い、最初から全く新しい解を推測させるだけでした。あるいは、より高度な設定では、ロボットが自分のミスを認識し、テスト中に修正を試みますが、ロボット自体は将来、ミスをより上手に修正する方法を学習することはありません。まるで、テストを受けて問題に赤い「バツ」をつけられ、次のテストの前にその教訓をすぐに忘れる生徒のようです。

現在の「学習」手法の問題点
新しい手法では、ロボットが試行し、失敗し、エラーメッセージを見て、再挑戦することを可能にします。これは機能しますが、「教師」（トレーニングアルゴリズム）は少し不器用です。それは、試行全体を単一の単位として扱います。

シナリオ: ロボットが解を試み、失敗し、エラーメッセージが失敗の「理由」を正確に伝えます（例：「負の数の処理を忘れました」）。ロボットはその手がかりを使ってコードを修正し、成功します。
不器用な教師: 従来のトレーニング手法は、「最終的な成功は素晴らしい！」と言いますが、最初の失敗した試行には全く評価を与えません。最初の失敗が、問題を解決するために必要な具体的な手がかりを提供したため、実際には「有益」だったことに気づいていないのです。それは、失敗を時間の無駄とみなします。

登場する MURPHY：「賢い探偵」のような教師
この論文は、これらのロボットを訓練する新しい方法としてMURPHYを紹介しています。MURPHY を、結末だけでなく、物語全体を見る探偵だと考えてください。

「試行の樹」の構築: 単一の試行ではなく、MURPHY はロボットに枝分かれさせます。
- 枝 A: ロボットが解を試みます。失敗します。
- 転換点: MURPHY はその失敗、エラーメッセージ、そして元の質問を取り、そのエラーを修正するために「具体的に」再挑戦するようロボットに求めます。
- 枝 B: ロボットはエラーの手がかりを使ってコードを修正し、成功します。
テープの巻き戻し（回顧的評価）: これが魔法の部分です。ロボットが枝 B で成功すると、MURPHY は時間を遡って戻ります。「待てよ！枝 B が成功したのは、枝 A がその特定のエラーの手がかりを提供してくれたからだ。だから、枝 A も評価に値する！」と言います。
- これは、容疑者の最初の過ち（指紋を残したこと）が、逮捕につながった決定的な証拠だったことに気づく探偵のようなものです。指紋は「悪い」動きではなく、解決に至るための必要なステップでした。
評価を与える 2 つの方法:
- MARS（楽観主義者）: ロボットの追試のいずれかが成功すれば、MARS はその連鎖を開始した初期の失敗に完全な評価を与えます。「もし最終的に宝を見つけられたなら、迷っていた時に描いた地図は価値があった」と言うようなものです。
- MERS（現実主義者）: この手法は、すべての追試の平均的な成功に基づいて評価を与えます。少し慎重で、評価を分散させます。
死んだ枝の切断（剪定）: 時には、ロボットがあまりにも多くのバリエーションを試すため、「樹」が大きくなりすぎて処理が遅くなります。MURPHY には賢い「庭師」ツールがあります。それは枝を見て、すべて同じことをしている（何も新しいことを学んでいない）枝を切り落とします。最も多様性と学習の潜在性がある枝を維持し、時間と計算資源を節約します。

結果
著者らは、2 つの異なるロボット「脳」（モデル）を使用して、3 つの異なるコーディング課題でこれをテストしました。

結果: MURPHY は、ロボットが自分のコードを修正する能力を大幅に向上させました。
絶妙なバランス: 改善は難しい問題で最も顕著でした。簡単な問題では、ロボットはもともと上手でした。しかし、ロボットが失敗し、エラーから学び、再挑戦しなければならなかった難しい問題では、MURPHY は以前の手法よりも約6% 多く成功するのを助けました。

要約すると
MURPHY は AI に失敗はデータであることを教えます。失敗した試行を「悪い」結果として扱うのをやめ、その失敗が最終的な成功に必要な情報を提供したのであれば、「必要なステップ」として扱うようにします。それは AI を、単なる最終回答だけでなく、自己修正の「プロセス」を価値あるものとして評価するように再配線します。

技術的概要：MURPHY – 振り返りによるクレジット割り当てを備えたフィードバック認識型 GRPO

問題定義

検証可能な報酬を用いた強化学習（RLVR）は、推論タスクにおける大規模言語モデル（LLM）の事後学習の標準的なアプローチとなり、グループ相対方策最適化（GRPO）が主要な手法として浮上しています。しかし、標準的な GRPO とその派生手法は本質的にシングルターンであり、孤立したプロンプト - 応答対からの最終報酬に基づいて最適化を行います。このアーキテクチャは、モデルが環境からのフィードバック（例：実行エラー、スタックトレース、失敗したテストケース）に応じて反復的にソリューションを洗練させる必要があるエージェンシー環境、特にコード生成には不適切です。

既存のマルチターン手法は、学習された検証器（µCODE）、PPO 風のクリティック（RLEF）、または独立した検証方策（REVEAL）などの複雑な補助メカニズムに依存することが多いです。自然なベースラインであるGRPO-MTは、フィードバック条件付きの相互作用を軌道として扱うことで GRPO をマルチターンに拡張しますが、GRPO-MT は粗いクレジット割り当てに悩まされています。これは、中間の失敗した試みが後の成功した洗練を可能にする有益なフィードバックを提供していたかどうかに関わらず、軌道内のすべてのトークンに同じ最終報酬を割り当てるためです。コード生成において、失敗した試みは均一的に否定的なものではなく、最終的な解決に不可欠な特定のエッジケースやランタイムエラーを露呈させる可能性があります。現在の手法は、同じ最終結果を共有する場合でも、「有益な失敗」と「有益でない失敗」を区別できません。

手法：MURPHY

著者は、学習されたクリティックや補助検証器を導入することなく、標準的な事後学習レシピをフィードバック認識型にするための GRPO の最小限の拡張であるMURPHY（Multi-turn Update with Retrospective Policy Optimization）を導入します。

1. フィードバック条件付きロールアウト木

MURPHY は、線形軌道の代わりに各入力プロンプトに対して木構造を構築します：

ターン 1: モデルは候補プログラムのグループをサンプリングします。
実行とフィードバック: 各候補はテストスイートに対して実行され、スカラー報酬（例：パス率）と定性的フィードバック（例：エラーメッセージ）が得られます。
拡張:
- 解決された候補は終了し、葉ノードとなります。
- 失敗した候補は拡張されます。新しいプロンプトは、元のタスク、失敗した出力、および実行フィードバックを連結して形成されます。モデルは、このフィードバック条件付きプロンプトに対して再呼び出しされ、新しい洗練グループを生成します。
このプロセスは固定されたターン数で繰り返され、エッジが特定のフィードバックに条件付けられた洗練ステップを表す木が作成されます。

2. 振り返りによるクレジット割り当て

中核的な革新は振り返りによるクレジット割り当てです。ロールアウト木が完了した後、報酬は葉から根へ逆方向に伝播されます。これにより、後の成功した洗練が、有用なフィードバックを生み出した以前の失敗した試みに「クレジット」を付与することを可能にします。論文では 2 つの伝播戦略を提案しています：

最大報酬（MARS）: 楽観的なバックアップ。ノード $v$ に対して、調整された報酬 $\tilde{r}(v)$ は、その即時報酬 $r(v)$ と子ノードの調整済み報酬の最大値の最大値となります：
$\tilde{r}(v) = \max\left(r(v), \max_{u \in C(v)} \tilde{r}(u)\right)$
これは、その子孫のいずれかが最終的にタスクを解決した場合、失敗した試みにクレジットを付与します。
平均報酬（MERS）: 期待値に基づくバックアップ。将来の報酬の割引平均を伝播します：
$\tilde{r}(v) = r(v) + \gamma \cdot \frac{\text{mean}_{u \in C(v)} \tilde{r}(u)}{Z(v)}$
ここで、 $\gamma$ は割引因子、 $Z(v)$ は正規化項です。

3. ローカル GRPO 更新

報酬が調整された後、MURPHY は木内の各応答グループに対してローカルに標準的な GRPO 目的関数を適用します。即時報酬の代わりに、クレジット調整済み報酬（ $\tilde{r}$ ）を使用してアドバンテージを計算します。これにより、木構造からの時間的クレジットを取り込みつつ、GRPO のグループ相対基準構造を維持します。

4. プリニング戦略

木を拡張する計算コスト（指数関数的に成長する可能性）に対処するため、MURPHY は報酬伝播前に有益な軌道を保持するポストロールアウトのプリニングメカニズムを導入します：

グループ内プリニング（INTRAP）: 各応答グループ内の軌道を固定数保持し、特に報酬分散に最も寄与するものを選択します（多様な学習信号を保持）。
グループ間プリニング（INTERP）: グループ内の報酬分散に基づいて、完全な洗練グループを保持します。これにより、最適化予算を、最も多様で有益な候補洗練をもたらすフィードバック文脈に配分します。

主要な貢献

MURPHY アルゴリズム: 構造的な時間的クレジット割り当てを通じて実行フィードバックを利用するようにコード LLM を訓練するマルチターン GRPO 拡張であり、学習された検証器やクリティックの必要性を排除します。
報酬伝播戦略: 成功した洗練から、より前の有益な失敗にクレジットを割り当てるためのMARS（楽観的）とMERS（期待値ベース）戦略の導入。
プリニングメカニズム: 学習信号を保持しながら有益でない軌道をフィルタリングすることで、マルチターン最適化を実用的にするINTRAPとINTERP戦略の設計。
実証的検証: 3 つのベンチマーク（HumanEval、MBPP、LiveCodeBench-v6）と 2 つのモデルファミリー（Qwen、OLMo）にわたる包括的な評価により、既存のマルチターン手法に対して顕著な改善を示しています。

実験結果

著者は、Qwen3（1.7B、4B）およびOLMo-2-7Bモデルを使用して、HumanEval、MBPP、LiveCodeBench-v6上で MURPHY を評価しました。

性能向上: MURPHY は、最も強力な既存のマルチターン実行フィードバック手法（GRPO-MT、µCODE、REVEALを含む）に対して、最大6% の絶対的な pass@1 向上を達成しました。
難易度スケーリング: 向上はMediumおよびHardサブセットで最も顕著でした。例えば、LiveCodeBench-v6（Medium サブセット）では、Iteration-5 で**+4.38%の向上を示し、Hard サブセットでは+4.20%**の向上を示しました。これは、この手法が反復的な自己修正が重要な場面で特に効果的であることを示唆しています。
ベースラインとの比較:
- OLMo-2-7Bにおいて、MURPHY は Iter-3 設定で HumanEval で**+6.20 pp**、MBPP で**+6.07 pp**の向上により、最も強力なベースラインを上回りました。
- Qwen3-4B（LiveCodeBench-v6）において、MURPHY は、より複雑なアーキテクチャを持つ REVEAL（共同学習された自己検証器を持つ手法）を、すべての難易度サブセットで上回りました。
アブレーション研究:
- MARS vs. MERS: MARS は、信号を平均化して希釈するのではなく、最も強力な結果を伝播することにより、特にスパース報酬設定で MERS よりも一般的に優れていました。
- プリニング: INTERPプリニング戦略が最も優れたコスト - 品質のトレードオフを提供し、最適化時間を**74.1%**削減（1 ステップあたりの総トレーニング時間を 21.4% 削減）しながら、プリニングを行わないモデルとの性能差を 0.8% 以内に維持しました。INTRAP はシングルターンの性能を向上させましたが、マルチターンの性能では劣化を引き起こしました。

意義と主張

この論文は、MURPHY が、クレジット割り当ての構造変更のみを通じて、標準的な GRPO 事後学習レシピをフィードバック認識型にできることを実証していると主張しています。

アーキテクチャの最小主義: 補助価値関数、学習された検証器、または明示的な検証方策を必要とする先行研究とは異なり、MURPHY は「最小限で、アーキテクチャを保存する拡張」です。これは、コード生成タスクに固有の実行フィードバックのみに依存します。
クレジット割り当ての不一致: この研究は、エージェンシー型コード生成における根本的な不一致、すなわち有益でないエラーと有益な失敗を区別できないという問題に対処します。報酬を逆方向に伝播させることで、MURPHY は Piet Hein の引用にあるように「失敗し、再び失敗する」ことが、エラーが修正に必要な信号を提供する限りにおいて価値があることをモデルに教えます。
スケーラビリティ: 提案されたプリニング戦略は、学習信号の質を犠牲にすることなく最適化の負担を軽減し、マルチターン学習を計算的に実行可能にします。

著者は、マルチターンロールアウトがシングルターン GRPO に比べてトレーニングコストを増加させるものの、特に困難な問題における自己修正能力の向上がそのアプローチを正当化すると結論付けています。彼らは、増加したトレーニングコストとクリーンな実行フィードバックへの依存という限界を指摘し、将来的な研究として、よりノイズの多いフィードバック信号や適応的なターン予算の検討を提案しています。