💻 computer science

Reinforced Graph of Thoughts: RL-Driven Adaptive Prompting for LLMs

本論文は、強化学習を活用してグラフ・オブ・ソートス・プロンプティングにおける操作グラフを動的に適応させる自動化フレームワークである強化グラフ・オブ・ソートス（RGoT）を提案し、これにより手動で定義された構造の硬直性を克服し、複雑な問題解決タスクへの対応を改善するものである。

原著者： Manuel Noah Riesen, Peter Alfred von Niederhäusern

公開日 2026-05-22

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

CC BY 4.0

原著者： Manuel Noah Riesen, Peter Alfred von Niederhäusern

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

非常に頭が良いが、ときどき気が散ってしまうアシスタント（大規模言語モデル、または LLM）がいると想像してください。このアシスタントは物語を書くのが得意ですが、複雑な数学や散らかったデータの整理には苦労します。単に「これを解いて」と頼むだけでは、特に問題が巨大な場合、混乱したり間違いを犯したりする可能性があります。

アシスタントを支援するために、研究者たちは通常、「レシピ」または段階的な計画を与えます。

思考の連鎖（Chain of Thought）: 「A を行い、次に B、次に C」という直線的な指示の列のようなものです。
思考の木（Tree of Thoughts）: 家族樹のように、アシスタントが異なる枝を試して、どれが良さそうか確認し、行き止まりに当たれば後戻りする仕組みです。
思考のグラフ（GoT）: 最も高度なバージョンです。地下鉄の路線図を想像してください。アシスタントは問題を異なる路線に分割し、それぞれを個別に解決してから、結果を再び統合します。これは大きな問題には優れていますが、使用が困難です。アシスタントが作業を開始する前に、あなたという人間が地下鉄の路線図全体を自分で描かなければなりません。間違った地図を描けば、アシスタントは失敗します。

問題点：「静的な地図」

元の「思考のグラフ」は、硬直した事前に描かれた地下鉄の地図のようです。問題があなたが予想したものと完全に一致すれば完璧に機能します。しかし、問題がより大きくなったり複雑になったりした場合（例えば、あなたが思っていた長さの 2 倍の数字のリストなど）、あなたの固定された地図は破綻します。地図が新しいサイズを考慮していなかったため、アシスタントは迷子になります。

解決策：強化された思考のグラフ（RGoT）

この論文の著者、マヌエル・ノア・リーゼンとペーター・アルフレッド・フォン・ニーダーハウゼルンは、RGoTと呼ばれるシステムを構築しました。あなたが地図を描く代わりに、彼らはアシスタントに運転しながら学習する GPSを与えました。

これがどのように機能するか、簡単な比喩を使って説明します。

「合計」ゲーム
タスクが非常に長い数字のリストを合計することだと想像してください。

従来の方法: あなたはアシスタントに「これらの数字を合計して」と伝えます。リストに 5 個の数字があれば、彼らは行います。50 個あれば、混乱して誤った答えを出します。
RGoT の方法: システムには基本的な動きのツールボックスがあります。
- 分割（Split）: 大きなリストを 2 つの小さなリストに切断する。
- 合計（Sum）: 小さなリストを合計する。
- 統合（Merge）: 2 つの小さな結果を 1 つの大きな結果に組み合わせる。

いつ分割したり統合したりするかをあなたが決めるのではなく、システムは強化学習（RL）エージェントを使用します。このエージェントを、レベルをクリアしようとするビデオゲームのキャラクターだと考えてください。

ゲーム: 「レベル」は数字のリストです。
動き: キャラクターは「分割」「合計」「統合」、または「停止」を選ぶことができます。
報酬: 最終的な答えが正しければ、キャラクターはポイントを獲得します。失敗すればポイントを失います。

学習の魔法
最初は、エージェントは何も知りません。100 個の数字のリストを一度に合計しようとして失敗するかもしれません。しかし、「ゲーム」（強化学習）をプレイしているため、失敗から学びます。

気づきます。「ねえ、リストが巨大な場合、一度に合計しようとするとペナルティを受ける。でも、まず分割して、小さな部分を合計し、最後にそれらを統合すれば、大きな報酬がもらえる！」
時間とともに、エージェントは問題のサイズに完全に適応した独自の「地下鉄の地図」（操作グラフ）をその場で構築することを学びます。

彼らが実際に行ったこと

研究者たちはこの手法をいくつかのタスクでテストしました。

リストの合計: 数字を合計する。
リストのソート: 数字を順序立てる。
キーワードの計数: テキスト内の単語が何回出現するかを見つける。
ドキュメントの統合: 情報を重複させずに複数のテキストを 1 つにまとめる。

彼らは、コストがかかりすぎて遅くなるため、実際の AI モデルを使って訓練したわけではありませんでした。代わりに、シミュレーションを作成しました。AI が 10 個、20 個、50 個などのアイテムのリストで間違いを犯す可能性を計算し、それをゲームにプログラムしました。エージェントはこのシミュレーション内で学習し、その後、実際の AI でテストされました。

結果

この論文は以下を主張しています。

適応性: エージェントは問題の難易度に応じて戦略を自動的に変更することを学びました。リストが短ければ単純な合計を行い、リストが巨大であれば、まず分割することを自動的に決定します。
基礎的な手法より優れている: エージェントは、AI に一度に「やって」と頼むだけ（「入力 - 出力」方式）よりも、はるかに信頼性高く複雑な問題を解決しました。
汎化能力: 訓練中に一度も見たことのないリストのサイズ（30 までのリストで練習しただけなのに、60 個のリストなど）を与えられた場合でも、エージェントは依然として良い戦略を見つけ出しました。

結論

この論文は、高度な AI の問題解決を自動化する方法を提示しています。複雑なタスクをどのように構造化するかを人間専門家が正確に知る必要ではなく、システムは「学習エージェント」を使用して、与えられた問題のサイズに応じた最適な段階的な計画（グラフ）を特定します。これにより、硬直した手動プロセスが、柔軟で自己調整型のプロセスへと変わります。

注：この論文は完全にこれらの特定のタスク（数学、ソート、計数、統合）に焦点を当てており、この手法が医療診断、法的助言、またはこれらの定義された論理問題以外の他の現実世界の応用で機能すると主張するものではありません。

技術的サマリー：強化グラフ・オブ・シンキング（RGoT）

問題定義

大規模言語モデル（LLM）は、Chain of Thought（CoT）、Tree of Thoughts（ToT）、Graph of Thoughts（GoT）などのプロンプト・パラダイムを通じて、意図的な問題解決において顕著な能力を示してきました。GoT は、思考を任意のグラフとして構造化し、集約や複雑な推論を可能にする一般化されたフレームワークを提供しますが、既存の実装は静的で手動定義された操作グラフに依存しています。

この手動定義には、主に 2 つの制限があります：

アクセシビリティ：GoT グラフの構築には、問題解決の深い知識と操作の特定の順序付けが必要であり、ユーザーにとって参入障壁が高くなっています。
適応性：静的グラフは硬直的です。入力インスタンスの複雑さの変動や、LLM 出力の非確定的かつエントロピー的な性質に適応できません。その結果、特定の複雑さレベル向けに設計されたグラフは、異なる特性を持つ入力に適用された場合、失敗する可能性があります。

先行研究（Ha et al., 2024）は GoT の自動化を試みましたが、グラフの構築には基盤となる LLM の論理的な能力に依存していました。本論文は、推論トポロジー自体を生成するために LLM の計画能力に依存しないアプローチの必要性に対処します。

手法

著者は、人間が定義した利用可能な操作のセットから操作グラフを適応的に生成するために強化学習（RL）を活用する自動化アプローチ**Reinforced Graph of Thoughts（RGoT）**を提案します。

コアフレームワークの構成要素

システムは、**操作グラフ（GoO）と思考グラフ（GoT）**を分離します：

操作グラフ（GoO）：操作の順序と構造を定義する有向非巡回グラフ（DAG）です。最大深さ（ $d_{max}$ ）と最大幅（ $b_{max}$ ）によって制約されます。収束を確保するため、発散カットオフ深さ（ $d_{\neg div}$ ）が強制され、それ以降はグラフが単一のシンクに向かって収束しなければなりません。
思考グラフ（GoT）：LLM の思考が生成される実際の実行トレースです。各思考は、それを生成した操作を参照します。
操作：プロンプト操作（LLM 呼び出し）または実行操作（プログラム的な関数）として定義されます。スコア操作は思考の品質を評価し、数値スコアを返します。

強化学習の定式化

RGoT エージェントは、GoO を層ごとに構築するために、カスタム RL 環境内で動作します。

状態空間（ $S$ ）：現在のグラフの深さ、幅、タスクの複雑さ、局所的な複雑さ、現在のグラフ内の操作のシーケンス、前の行動、および前のスコアを含む離散空間の組み合わせ。
行動空間（ $A$ ）：stop（グラフ構築の終了）、backtrack（シンク層の削除）、append(o)（操作 $o$ を含む新しい層の追加）などの離散的な行動。
報酬関数：過度な深さを罰し、有効な操作を報酬し、タスクの成功（最終状態）に対して大きな正の報酬を与えるように、報酬設計を通じて設計されます。
シミュレーション：実際の LLM 呼び出しを用いたトレーニングの高コストを軽減するため、LLM の動作がシミュレートされます。特定の複雑さ $c$ における操作の成功確率は、確率 $P(c)$ を持つベルヌーイ試行としてモデル化され、ターゲット LLM（例：gpt-3.5-turbo-0125）を各複雑さレベルで 100 回プロンプトすることにより経験的に推定されます。

実験設定

著者は、RGoT を以下の 5 つのタスクで評価しました：

Sum List：整数のリストの合計（主要な例）。
Sort List：整数のソート。
Intersect Set：集合の共通部分の発見。
Count Keywords：テキスト内のキーワード出現回数のカウント。
Merge Documents：保持を最大化し冗長性を最小化しながらドキュメントをマージ。

実験には、2 層のネットワークアーキテクチャ（64 ユニット）を用いた**Proximal Policy Optimization（PPO）**アルゴリズムが使用されました。エージェントは特定の複雑さの範囲でトレーニングされ、その後、分布内および分布外（より高い複雑さ）のインスタンスの両方で評価されました。

主要な結果

適応的構築：RL エージェントは、タスクの複雑さに適応する操作グラフを構築することを学習しました。複雑さが増加するにつれて、エージェントは自動的にグラフの分岐（発散）と深さを増加させ、問題を分解しました。これは明示的にプログラムされたものではなく、報酬シグナルを通じて学習された行動です。
ベースラインとの性能比較：RGoT エージェントは、標準的な Input-Output（IO）プロンプト・ベースラインを大幅に上回りました。IO 戦略は、複雑さが LLM の直接能力を超えると失敗しましたが、RGoT エージェントはタスクを分解することで高い成功率を維持しました。
一般化：エージェントは、トレーニング中に経験した複雑さよりも高い分布外の複雑さを解決する能力を示し、平均合計解決率 $0.7512 \pm 0.1089$ を達成しました。
分散：著者は、特に分布外の領域において、異なるランダムシード間でのエージェントの性能に分散を観察しました。これは、高複雑さにおけるスパースな報酬シグナルと、早期の非最適軌道へのコミットメントからの回復を制限する PPO のオンポリシー性質に起因すると考えられます。

意義と主張

本論文は、言語モデルの計画能力やタスクの特性の理解に依存することなく、操作グラフを生成・探索することによって思考グラフを構築する自動化アプローチを提示する最初の研究であると主張しています。

主な貢献点は以下の通りです：

GoT の自動化：手動によるグラフ定義の必要性を排除し、利用可能な操作のセットのみを定義すればよいユーザーにとって GoT パラダイムをよりアクセスしやすくします。
適応性：自動化されたエージェントが入力複雑さに基づいて推論トポロジーを動的に調整し、静的グラフの硬直性を克服することを示しました。
モデル非依存性：フレームワークは特定の LLM に依存しません。LLM の成功確率をシミュレートすることで、システムはコスト効果的にトレーニングでき、異なる能力範囲を持つモデルを含む様々なモデルに適用できます。
相補性：著者は、RGoT（推論トポロジーの構造化）が、外部から取得した知識を構造化する Knowledge Graph of Thoughts（KGoT）と相補的であると指摘し、将来の組み合わせ応用の可能性を示唆しています。

著者は控えめなトーンを維持しており、このアプローチは特定の制約下および定義されたタスクにおいて有望であることを示しつつも、性能の分散やトレーニングにおけるシミュレーションへの依存は考慮すべき領域であると認めています。すべてのプロンプト手法に対して普遍的な優位性を主張するのではなく、複雑で分解可能なタスクに対する適応的かつ自動化されたグラフ構築の特定の有用性を強調しています。