🤖 machine learning

DecompRL: Solving Harder Problems by Learning Modular Code Generation

本論文は、大規模言語モデルがタスクをモジュール化されたサブ関数へと分解することを学習することで、これまで解決不可能であったコーディング問題を解決することを可能にし、それらを再結合することで探索空間を指数関数的に拡大させ、かつGPU推論コストを大幅に削減する強化学習アルゴリズムであるDecompRLを導入するものである。

原著者： Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

公開日 2026-07-03

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

CC BY 4.0

原著者： Juliette Decugis, Fabian Gloeckle, Francis Bach, Taco Cohen, Gabriel Synnaeve

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

DecompRL の解説：シンプルで日常的な例えを用いた説明

大きな問題：「ワンショット」のボトルネック

非常に難しいパズルを解こうとしている場面を想像してください。あなたの前には、そのパズルを解くことができる超スマートなロボット（大規模言語モデル）がいます。

現在、このロボットに難しいパズルを解かせる標準的な方法は、何度も繰り返し挑戦させることです。

従来の方法： あなたはロボットに「解答のすべてを書いてください」と頼みます。もし失敗したら、また頼みます。また失敗したら、また頼みます。
問題点： ロボットに毎回ゼロから「解答のすべて」を書かせようとすると、多額の費用と時間（GPUパワー）がかかります。もしパズルが本当に難しい場合、ロボットはたった一つの正解に辿り着くまでに、何百万回もの試行を繰り返す必要があるかもしれません。これは、美味しいオムレツが作れるかどうかを確認したいだけなのに、毎回一流のシェフを呼んで、ゼロからフルコースの料理を作らせるようなものです。コストがかかりすぎます。

新しいアイデア：「レゴ」のアプローチ (DecompRL)

この論文の著者たちは、ロボットに一度に巨大な城を建てさせるのではなく、パーツごとに組み立てる方法を教えるべきだと気づきました。

複雑なコーディングの問題を、巨大なレゴのお城を作ることに例えてみましょう。

標準的な方法： ロボットは一度に城全体を建てようとします。もし屋根の部分を間違えたら、全体が失敗に終わります。
DecompRL の方法： ロボットは、城を小さくて独立したパーツに分解することを学びます。「これは壁」「これはドア」「これは窓」といった具合です。

ロボットがこれらの小さなパーツを作ることを学んだとき、魔法のようなことが起こります：**「再結合（リコンビネーション）」**です。

例えば、ロボットが「壁」の異なるバージョンを5つ、「ドア」の異なるバージョンを5つ、「窓」の異なるバージョンを5つ作ったとします。
5つの「完全な城」を作るのは大変（高コスト）ですが、これらを組み合わせることができます。「壁の1番目」「ドアの3番目」「窓の5番目」を組み合わせて、新しい城を作ることができます。次に「壁の2番目」「ドアの1番目」「窓の4番目」を組み合わせます。
たった15個の小さなパーツがあれば、125通りの異なる城（5 x 5 x 5）を作り出すことができるのです。

仕組み：二段階のダンス

この論文では、ロボットにこの「レゴ」のアプローチを教えるための、DecompRL と呼ばれる新しい学習手法を紹介しています。これには、2つの専門化された役割（ポリシー）が使われます。

設計者（分解ポリシー / Decomposition Policy）： この部分は、難しい問題を見て、「よし、これを解くには、ソート関数、数学関数、そしてプリント関数が必要だ」と判断します。大きな問題を、小さく管理可能なタスクへと分解します。
職人（実装ポリシー / Implementation Policy）： この部分は、それらの小さなタスクそれぞれのコードを実際に書きます。

魔法のトリック：
システムは、「設計者のプラン」の多くのバリエーションと、「職人のコード」の多くのバリエーションを生成します。そして、安価なコンピュータ（CPU）を使って、それらすべての組み合わせを混ぜ合わせます。

コストの転換： コードを書くことは高価ですが（高給な設計者を雇うようなもの）、コードが機能するかどうかをチェックすることは安価です（単純な品質チェックのようなもの）。
結果： 「完全な解答」を生成する回数を減らし、代わりに多くの「パーツ」を組み合わせることで、システムはわずか数回の生成コストで、何千もの潜在的な解決策をテストすることができます。これにより、ボトルネックを、高価な「思考力（GPU）」から、安価な「検証力（CPU）」へとシフトさせています。

なぜこれが重要なのか

この論文は、ロボットが通常は 99.9% 失敗してしまうような非常に難しい問題において、以下のことを示しています。

標準的な方法は限界に突き当たります。何度「完全な解答」を試させても、ロボットは失敗し続けます。
DecompRL は進化し続けます。小さなパーツを組み合わせることで何千もの組み合わせをテストできるため、従来の「完全な解答」方式では決して到達できなかった解決策を見つけ出すことができるのです。

注意点（限界）

論文では、デメリットについても正直に述べています。

「フォーマット税（Format Tax）」： 簡単な問題に対しては、分解するやり方はむしろ遅く、非効率的です。それは、サンドイッチを食べたいだけなのに、パンと具材をバラバラにして食べるようなものです。ロボットは、いつ分解すべきかを判断するために、特別に訓練される必要があります。
学習の難易度： ロボットは自然にこの方法を知っているわけではありません。「設計者」と「職人」の役割を学ぶために、特別な強化学習プロセスを用いて、ゼロから再学習させる必要があります。

まとめ

DecompRL は、AIに答えを一度に書き切らせるのをやめさせ、難しい問題を解決させるための新しい方法です。代わりに、AIに「小さくて再利用可能なパーツの道具箱」を作ることを教えます。これらのパーツを組み合わせることで、AIは膨大な数の「完全な解答」を生成するという高いコストを支払うことなく、何百万もの可能性をテストできるのです。これは、高価な「推測して確認する」ゲームを、安価な「組み合わせて試す」ゲームへと変えるものです。

技術要約: DecompRL

問題提起

大規模言語モデル（LLM）は、ベースとなるポリシーが正しい解を生成する確率がほぼゼロであるような複雑な問題を解決する際、現在大きな困難に直面しています。既存の戦略には以下の重大なボトルネックが存在します：

反復サンプリング (pass@k): テスト時の計算量をスケールさせるには効果的ですが、GPUコストは試行回数に対して線形に増加します。性能の向上は、これらの線形コストに対して対数的に成長することが多いです。
標準的な強化学習 (RL): PPOやGRPOのような手法は、単一試行の正確性（pass@1）を向上させますが、サンプルの多様性を低下させることがよくあります。これは、高い $k$ 値（ $k \gg 100$ ）に対して推論をスケールさせる際の有効性を損ないます。
核心的な限界: 探索空間が大きすぎる場合、サンプリングの増加も勾配信号も、ベースとなるポリシーが正しい解を生成する低い確率を克服することはできません。

手法: DecompRL

著者らは、階層的なモジュール生成を活用することで、計算のボトルネックを高価なGPU推論から安価なCPU評価へとシフトさせる強化学習フレームワークである DecompRL を提案しています。

1. 階層的推論

DecompRLは、モノリシックなコード解を生成する代わりに、問題を独立して解決可能なサブ関数の階層へと分解するようにモデルを訓練します。

分解ポリシー ( $\pi(D)$ ): 問題 $x$ を、シグネチャと自然言語によるドックストリングで指定された $n$ 個の関数の集合 $D$ に分解します。
実装ポリシー ( $\pi(I|D)$ ): $D$ 内の各関数に対して $k$ 個の独立した実装を生成します。
再結合: 各関数に対して $k$ 個の実装を生成することで、システムは再結合を通じて $k^n$ 個の候補プログラムを作成します。これにより、線形な推論コスト（ $k \times n$ トークン）で、潜在的なプログラムの組合せ爆発（ $k^n$ ）を実現します。

2. 強化学習の目的関数

DecompRLは、2つのポリシーを含む協調的マルチエージェントRL問題として階層的推論を扱います。再結合に伴う疎な報酬と高い分散に対処するため、著者らは特定のアルゴリズム的適応を導入しています。

LogMeanExp 目的関数: 探索と活用のバランスを取るため、著者らは $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$ で定義されるソフトな目的関数を使用します。これは、平均（ $\beta \to \infty$ ）と最大値（ $\beta \to 0$ ）の間を補間し、pass@k 目的関数の対数一様混合を近似します。
Leave-One-Out ベースライン: ポリシー勾配を計算するために、著者らは leave-one-out ベースラインを使用します。特定の行動（分解または実装）に対して、アドバンテージは、全報酬セットから計算されたマルチサンプル目的関数と、その行動を除外したセットから計算された目的関数を比較することによって算出されます。これにより、勾配の分散を抑え、バイアスを防ぎます。
逐次学習: 分解ポリシーと実装ポリシーは、共同ではなく逐次的（交互のステップ）に訓練されます。これは、マルチエージェントRLにおける「動く標的（moving target）」問題に対処し、実装ポリシーが特定の分解に過学習したり、その逆が起きたりすることを防ぎます。

3. 計算量のシフト

この手法は、計算のボトルネックを根本的に変化させます。

標準的なRL: 完全な解を生成するためのGPU推論コストによって支配されます。
DecompRL: 再結合された解を評価するためのCPU実行コストによって支配されます。同等の評価予算（例：512回の評価）において、GPUトークン生成は劇的に削減されます。DecompRLは、GPUトークン生成を約 50倍 削減します。

主な結果

実験は、Qwen 2.5 7B、Llama 3.1 8B Instruct、および Code World Model 32B を用いて LiveCodeBench および CodeContests で行われました。

困難な問題への性能: DecompRLは、トークン予算が $10^5$ を超える場合、標準的なRLベースライン（GRPO、pass@k 訓練、SPO）を上回ります。標準的な生成では到達できない問題を解決し、LiveCodeBenchの「hard」サブセットにおいて最大 35% の解決率 を達成しました。
スケーリング挙動: 標準的な手法はトークン予算が増加するにつれて飽和しますが、DecompRLの成功率は上昇し続けます。最大300万トークンを用いた場合、既存の手法を大幅に凌駕します。
多様性と再結合: この手法は多様な解を生成します。分析によると、DecompRLで訓練されたモデルは、訓練が進むにつれてより大きな分解（より多くの関数）を作成することを学習しており、これが大規模な推論予算における成功率の向上と相関しています。
効率性: 1問題あたり512回の評価において、DecompRLはGPUトークン生成を標準的な約198kから約4kへと削減し、実行時間の支配をCPU実行（CPU時間が99.6%、GPU時間が0.4%）へとシフトさせます。

意義と主張

著者らは、DecompRLがベースとなるポリシーの成功率がほぼゼロであるような「より困難な」問題を解決するための新しい経路を提供すると主張しています。

コールドスタートの克服: これは探索ツールとして機能し、標準的な高pass@k サンプリングでは到達不可能なタスクのための正しい解を発見します。したがって、ポリシー蒸留パイプラインの自然な補完となります。
効率的なスケーリング: 生成コストと評価コストを切り離すことで、GPUのフットプリントを比例して増やすことなく、安価なCPUクラスター上での探索のスケーリングを可能にします。
制御軸としてのモジュール性: 得られる生成パイプラインは、反復サンプリングやスケールされた思考の連鎖（chain-of-thought）メソッドにはない解釈性と制御軸を提供します。
限界: 著者らは、「フォーマット税（format tax）」について言及しています。これは、階層的推論が、簡単な問題や低いトークン予算においてはモノリシックな生成よりも性能が劣ることを指します。また、訓練中に「サイズ崩壊（size collapse）」（分解サイズの縮小）が起こる傾向があることも観察されていますが、これらは logmeanexp 目的関数と逐次学習によって緩和されています。

著者らは、DecompRLを標準的なRLのポストトレーニング（強力な初期ポリシーに対しては依然としてサンプル効率が高い）の代替品としてではなく、高品質なデータを発見し、以前は解決不可能であったタスクを解決するための特化した探索戦略として位置付けています。