🤖 machine learning

Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers

本論文は、組み合わせ最適化問題に対して再利用可能かつ制約を考慮したソルバーを生成するように強化学習で訓練されたコード LLM が、解の質と計算効率の両面で従来の推論時探索手法を大幅に凌駕することを示している。

原著者： Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge

公開日 2026-05-19

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

原著者： Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge

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

以下は、論文「Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers（推論時の探索を超えて：強化学習が再利用可能なソルバーを合成する）」について、平易な言葉と創造的な比喩を用いて解説したものです。

大きなアイデア：「毎回推測する」ことから「マニュアルを作成する」ことへ

非常に賢いものの、少し無秩序なアシスタント（大規模言語モデル、LLM）がいると想像してください。毎回、難しいパズルを渡すと、彼らはゼロから推測し、確認し、再び推測するという方法で解こうとします。時には正解することもありますが、多くの場合、行き詰まったり、愚かな間違いを犯したりします。これが現在、ほとんどの AI が問題を解決する方法です：質問を受けるたびに、毎回推論を行っているのです。

この論文は、異なる問いを投げかけます：もし、毎回パズルを解く代わりに、AI が誰でも使える完璧な指示書（「ソルバー」）を書く方法を学んだらどうなるでしょうか？

研究者たちは、AI が「推測するアシスタント」から「コンパイラ」のように振る舞うように訓練できるかどうかを確認したいと考えていました。新しい顧客のために毎回作業を行うのではなく、AI は一度だけルールを学び、再利用可能なプログラムを作成し、そのプログラムが将来の何千もの問題を瞬時に解決できるようにするのです。

テスト：「欺瞞的な」パズルボックス

これを検証するために、研究者たちは**シナジース的依存関係選択（Synergistic Dependency Selection: SDS）**と呼ばれる特定の種類のパズルを作成しました。

比喩： 重量制限のあるバックパックを持つ宝探しを想像してください。価値のあるアイテムを選びたいと考えています。しかし、ここには落とし穴があります。あるアイテムは、一緒に選ばれた場合にのみ価値を発揮し（シナジー）、あるアイテムは両方選ぶと互いに打ち消し合います（対立）。また、あるアイテムは、特定の他のアイテムを先に選ぶことを要求します（優先順位）。
罠：このパズルは「欺瞞的」に設計されています。単純で貪欲な戦略（例：「まず最も重いアイテムを選ぶ」）は機能するように見えますが、実際には行き止まりへと導きます。まっすぐで簡単に見える道が実際には壁につながっている迷路のようなものです。

「ベース」AI の問題点

研究者たちはまず、標準的な未訓練の AI モデルを使ってこれらのパズルを解こうと試みました。彼らは、各パズルに対して AI に 64 回異なる試行を行わせ（「Best-of-64」と呼ばれる手法）、最も良い回答を選びました。

結果： 64 回の試行を行っても、AI が達成できた価値は、達成できたはずの価値の約**71%**に過ぎませんでした（28.7% のギャップ）。
なぜか？ AI は論理を「幻覚」していました。それは良い戦略の「名前」（例：「シミュレーテッド・アニーリング」は、「箱を振って最良の配置を見つける」という高級な言い方）を知っていましたが、その戦略のコードを書く際に、致命的な論理エラーを犯していました。まるで、ケーキのレシピを知っているシェフがオーブンをオンにするのを忘れたり、さらに悪いことにケーキを冷凍庫に入れてしまったりするようでした。

解決策：AI に自らの論理を「修正」させること

その後、研究者たちは**強化学習（Reinforcement Learning: RL）**という手法を用いました。これは、「よくやった！」や「悪いね！」と言うだけでなく、具体的なフィードバックを与える厳格なコーチのようなものです。

「実現可能性ゲート」： コーチは言います。「もしあなたのコードがルール（例：対立する 2 つのアイテムを選ぶなど）を破れば、スコアがどれだけ良く見えても、0 点になります。」これにより、AI は単に高い数値を得ることよりも、ルールに従うことを優先せざるを得なくなります。
「怠け防止」ペナルティ： AI が簡単な道（例：複雑な相互作用を無視して、単に重量でアイテムを並べ替えるなど）を選ぼうとすれば、コーチは AI を罰します。
「足場」： 研究者たちは、AI に特定の思考テンプレートを与えました。「問題を分解し、戦略を推測し、その推測を批判し、その後コードを書く」というものです。

結果：再利用可能な「ソルバー」の誕生

この訓練の後、AI は単に推測が上手くなっただけでなく、その働き方そのものが根本的に変化しました。

「コンパイラ」効果： AI は、「シミュレーテッド・アニーリング」戦略を正しく実装した、単一の再利用可能なコード（ソルバー）を書くことを学びました。
魔法： 場合の**99.8%**において、AI はこの正しいパターンに従うコードを書きました。未訓練の AI が繰り返し犯していた論理エラーを修正したのです。
パフォーマンス： 新しい「ヒーロー」ソルバーは、理論上の最良の答えの**5%**以内のスコアを達成しました。
コスト： ここが最もエキサイティングな部分です。
- 古い方法（パズルごとに 64 回推測する）は、新しいパズルごとに大量のコンピューター時間を要しました。
- 新しい方法（ソルバーを一度だけ作成する）では、コンピューターは重い作業を一度だけ行えば済みました。その後、そのソルバーは数千のパズルを瞬時に実行できます。
- 数学： 新しい方法は、古い「推測」方法と比較して、パズルあたりのコンピューター時間という点で91 倍安くなりました。

機能しなかったこと（「否定的」な教訓）

この論文では、特別な訓練のテクニックを除去した場合に何が起こるかもテストしました。

ルールなし： AI に制約に従うという厳格なルールなしに創造的になろうとさせただけでは、再び間違いを犯すようになります。
緩いルール： AI に「スコアが高ければ、ルールを少し破ってもいい」と伝えても、失敗します。AI がルールを尊重することを学ぶためには、明確な「停止」シグナルが必要です。
プロンプトだけ： 指示書で AI に「賢くあれ」と伝えるだけで、報酬システムによる訓練を行わなければ、依然として失敗します。指示書は単なる地図に過ぎず、訓練こそが実際に車を運転する車両なのです。

結論

この論文は、AI モデルを「即座に推測する者」から「プログラマー」へと訓練できることを証明しています。厳格なルールを用いた強化学習によって、AI は個々の問題を個別に解決することに苦労するのではなく、一連の難しい問題を正しく解決する再利用可能なツールを合成することができます。

毎日、誰かに数学の問題を解いてもらうこと（高くつくし遅い）と、その人にあなたのために問題を永遠に解く計算機を作らせること（安くて速い）の違いです。研究者たちは、適切な訓練を行えば、AI はその計算機を作れることを示しました。

技術的概要：推論時検索の枠を超えて

1. 問題定義

現在の大規模言語モデル（LLM）は、通常、組み合わせ最適化を推論時の手続きとして扱い、サンプリング、検索、または反復プロンプティングを通じて各問題インスタンスを個別に解決します。このパラダイムは、すべての新しいクエリに対して推論の「限界コスト」を発生させます。著者らは、強化学習（RL）がその推論コストをモデルの重みへ移行させ、個々のインスタンスごとの解生成ではなく、問題ファミリー全体に対する再利用可能なソルバーの合成を可能にするかどうかを調査しています。

本研究は、二次ナップサック問題の制御された強 NP 困難な変種である**相乗的依存関係選択（SDS）**に焦点を当てています。SDS は、以下のような「欺瞞的」な最適化ランドスケープとして設計されています：

局所信号が大域最適性と矛盾する： 二次相互作用項が線形重みを支配し、貪欲ヒューリスティックが失敗する。
厳密な実行可能性制約： 解は、基数、順序、相互排他、およびグループ制限を満たさなければならない。
テンプレート検索対実装： ベースモデルは適切なソルバーの構文（例：シミュレーテッド・アニーリング）を頻繁に検索できるが、実行可能なロジック（例：受入則の誤用）を正しく実装できないことが多い。

本論文は、以下の 3 つの核心的な研究課題に答えます：

能力の壁： 欺瞞的なランドスケープにおいて、広範なテスト時サンプリング（Best-of-N）は RL 訓練済みポリシーのパフォーマンスを回復できるのか、それともベースモデルは天井にぶつかるのか？
意味的修復： RL が成功する場合、それは単に正解の頻度を鋭くするだけなのか、それとも単純なサンプリングでは回復できない実行可能なアルゴリズム的ロジックを修復するのか？
償却されたソルバー合成： 訓練時最適化は、推論を軽量で再利用可能なプログラムへと蒸留し、反復的なインスタンスごとの検索を上回る性能を発揮できるか？

2. 手法

著者らは、Qwen2.5-Coder-14B-Instruct モデル上でグループ相対方策最適化（GRPO）を用いて微調整された方策Heroを提案します。このアプローチは意図的にミニマリストであり、実行可能性優先のレシピの効果を単離するために、KL ペナルティやオラクル・アンカリングなどの一般的な安定化要素を排除しています。

主要コンポーネント：

構造化システムプロンプト： プロンプトは「分解 - 仮説 - 批判」の推論ループを強制します。モデルに対して貪欲ヒューリスティックを警告し、探索と利用のバランスを取る検索戦略の設計を促します。
階層的報酬設計： 複合報酬 $r(o)$ $r (o)$ は、生きた最適性よりも構造的準拠を優先します：
- フォーマットと実行（ $R_{exec}$ ）： 有効な Python 構文、スキーマ準拠、およびグラフ理論的構造を確保します。重要なのは、二次相互作用を無視する線形貪欲ヒューリスティックを使用する事前学習済みモデルの傾向を抑制する怠惰なソートに対するペナルティを含めることです。
- 実行可能性ゲート付き最適性（ $R_{nom}$ ）： 主要な最適化信号は厳密にゲート制御されます。解が基数や順序などのハード制約のいずれかに違反する場合、目的関数のスコアに関わらず報酬はゼロになります。これにより、方策は目的関数の最適化に先立って制約充足を優先することが強制されます。
訓練レジーム： モデルは 12 個の NVIDIA GH200 GPU 上で 90 回のグローバルステップにわたって訓練され、フルプロンプトレベルのエポックの約 4.5% しか観察しませんが、23,040 の推論トレースを生成します。

3. 主要な貢献

本論文の貢献は、アルゴリズム的というよりも経験的かつ機械論的です：

能力の壁の特定： 同一のプロンプティング下において、ベースモデルの Best-of-64 サンプリングは、仮想最良ソルバー（VBS）に対する28.7% のギャップで飽和します。表面的に適切なソルバーテンプレート（例：21.9% のユニークなベースコードがシミュレーテッド・アニーリングに類似）を検索するにもかかわらず、ベースモデルはそれらを正しく実装できません。
意味的修復の証明： RL 訓練済み方策（Hero）は、実行可能な出力の**99.8%**で制約を認識したシミュレーテッド・アニーリングテンプレートに収束します。これは、ベースモデルのサンプルに蔓延する「大域最良バグ」を修復します。このバグでは、受入ロジックが現在の状態ではなく、実行中の大域最良に対して近傍を誤って比較します。この修正により、真のアニーリング動作が可能になります。
償却されたソルバー合成の検証：
- 性能： Hero は VBS に対して5.0% のギャップを達成し、ベースモデルや局所探索（10.0% のギャップ）などの古典的ヒューリスティックを大幅に上回ります。
- 効率性： Hero は、Best-of-64 評価の累積コストと比較して、生成後の実行・検索コストにおいて91 倍安価です。
- 再利用性： 「一度コンパイル」の評価により、シードごとに生成された単一の凍結ソルバーが、変更なしにテストセット全体で再利用された場合でも、高い競争力（97.87% のパス率、4.34% のギャップ）を維持することが示され、モデルがインスタンスごとのジェネレーターではなく再利用可能なアーティファクトを合成していることが証明されました。

4. 結果とアブレーション

主要性能： Hero は 97.8% のパス率と VBS に対する 5.0% のギャップを達成します。これは、デプロイ時に強力なプロプライエタリモデルを使用するリフレッシュされた ShinkaEvolve ベースラインを上回り、CP-SAT（1.0% のギャップ）のパフォーマンスに迫りつつ、実行速度は 6.3 倍高速です。
アブレーション研究：
- 構造的構造化： 構造的報酬（怠惰なソートに対するペナルティとグラフ構造チェック）を削除すると、モデルが脆い貪欲ヒューリスティックに戻り、性能は 34.7% のギャップまで崩壊します。
- 実行可能性ゲート： ハードな実行可能性ゲートをソフトなペナルティに置き換えると、性能は著しく低下します（97.8% から 57.4% のパス率）。これは、無効な解へのモード崩壊を防ぐためにハードゲートが必要であることを確認します。
- オラクル/多様性： オラクル・アンカリングや多様性ペナルティを追加すると性能が低下し、このドメインでは密な結果形成よりも、スパースで実行可能性優先のフィードバックがより効果的であることを示唆しています。
一般化：
- 破滅的忘却なし： モデルは一般的なコーディング能力を保持しています（HumanEval Pass@1：ベースの 82.3% に対し 80.9%）。
- クロスドメイン： 同じレシピをジョブショップスケジューリング（JSSP）に適用すると、肯定的な結果（99.3% のパス率、6.12% のギャップ）が得られますが、著者はこれはドメイン非依存の堅牢性の証明というよりも、転移のより狭い証拠であると指摘しています。

5. 意義と主張

本論文は、RL がコード LLM をインスタンスごとの検索のレジームから再利用可能なソルバー合成へと移行させることを実証していると主張しています。その意義は、RL が単に既存の解を見つける効率を向上させる「分布の鋭化器」ではなく、単純なサンプリングでは信頼性高く回復できない実行可能なロジック（例：メトロポリス受入則の修正）を修復する機能的コンパイラとして機能するという発見にあります。

著者は、この成功が普遍的なレシピではなく、規律ある実行可能性優先の構造化に依存していると強調しています。この手法は、ハードな実行可能性ゲートや構造的ペナルティなどの特定の設計選択に依存しており、報酬の正規化に対して敏感です。この研究は、複雑で欺瞞的な最適化ランドスケープにおいて、ソルバーを構築するために必要な「推論」をモデルの重みへと蒸留でき、反復的な推論時検索よりもはるかに効率的な展開可能なアーティファクトを作成できることを示唆しています。