last_modified: 2026-01-11
生成AIによる自動生成記事に関する免責事項: 本記事は、提供された学術論文 arXiv:2308.09687v4 [cs.CL] (Graph of Thoughts: Solving Elaborate Problems with Large Language Models) の内容に基づき、大規模言語モデルによって作成された解説記事です。正確な内容は参考文献を必ず参照してください。
1. 序論:線形連鎖からネットワーク状推論へ
大規模言語モデル(LLM)の推論能力を引き出すためのプロンプティングエンジニアリングは、近年のAI研究における中心的課題の一つである。初期のInput-Output (IO) プロンプティングから、中間推論ステップを明示する Chain-of-Thought (CoT) 、さらに複数の推論パスを探索する Tree of Thoughts (ToT) へと、そのパラダイムは進化を遂げてきた。
しかし、これらの既存手法は、推論の構造を「連鎖(Chain)」や「木(Tree)」といった特定のトポロジーに限定しているという点で制約が存在する。人間の思考プロセスや脳内の神経回路網、あるいは複雑なアルゴリズムの実行フローは、必ずしも木構造には従わず、より一般的な グラフ構造(ネットワーク) を形成する場合が多い 。例えば、ある推論パスで得られた洞察を別のパスと結合したり(Aggregation)、循環的なフィードバックループ(Loop)を経て洗練させたりする操作は、木構造では自然に表現できない。
Besta et al. (2023) が提案した Graph of Thoughts (GoT) は、LLMの推論単位(Thought)をグラフの頂点、依存関係を辺としてモデル化することで、これまでの制約を撤廃するフレームワークである 。本稿では、GoTがいかにしてCoTやToTを包含しつつ、複雑なタスクにおいてコスト削減と精度向上を同時に達成するかについて、数理的背景と実験結果に基づき詳述する。
2. 歴史的文脈と関連研究
GoTの理論的位置付けを明確にするため、プロンプティング手法の進化を構造的観点から概観する。
2.1 Chain-of-Thought (CoT) とその派生
Wei et al. (2022) によるCoTは、入力 から出力 への写像において、中間的な思考 を生成過程に組み込むものである 。
これはグラフ理論的には、分岐のない有向パス(Path Graph)に相当する。Wang et al. (2023) の Self-Consistency (CoT-SC) は、複数の独立したCoT ( 個のチェーン) を生成し、多数決などで最良の解を選択する手法であるが、各チェーン間の情報交換は行われない。
2.2 Tree of Thoughts (ToT)
Yao et al. (2023) および Long (2023) によるToTは、推論プロセスを木構造としてモデル化する 。各ノードは部分解を表し、探索アルゴリズム(BFSやDFS)を用いて有望な枝を伸ばし、不適切な枝を剪定(Backtracking)する。
ToTは「試行錯誤」や「先読み」を可能にしたが、一度分岐したブランチ同士が再び合流して情報を統合することは構造上不可能であった 。
2.3 Graph of Thoughts (GoT) の革新性
GoTは、任意の有向グラフ(Directed Graph)を許容することで、ToTの制約を克服する。特筆すべき点は、Aggregation(集約) と呼ばれる操作により、複数の独立した推論パスを一つの頂点に統合できる点である 。これにより、LLMは「分割統治法(Divide and Conquer)」のようなアルゴリズム的思考や、複数の視点の統合といった高度な推論が可能となる。
3. 数理的定式化
GoTフレームワークは、形式的にはタプル として定義される 。以下に各要素の定義を示す。
3.1 推論プロセスとしてのグラフ
LLMの推論プロセスは有向グラフ で表される 。
- 頂点集合 : 各頂点 は、LLMによって生成された「思考(Thought)」または「情報単位」を表す。これはパラグラフ、コードブロック、数値列など、タスク依存の形式を持つ 。
- 辺集合 : 有向辺 は、思考 が を入力として(すなわち に依存して)生成されたことを示す 。
一部のタスクでは、頂点が異なるクラス(例:「計画」と「実行」)を持つ異種グラフ(Heterogeneous Graph) として拡張される 。
3.2 思考変換(Thought Transformations)
グラフ の状態を遷移させる操作を変換 と定義する。変換適用後のグラフ は以下のように表される 。
ここで、 は使用されるLLM、 は新たに追加される頂点と辺、 は削除される頂点と辺を表す。GoTでは以下の主要な変換が定義される。
-
Aggregation (集約): 複数の思考 を統合し、新たな思考 を生成する操作。これはToTには存在しないGoT固有の強力な機能である 。
グラフ理論的には、頂点 の入次数(indegree)が となる状態を作り出す。
-
Refining (精緻化): ある思考 に対して自己ループ的な修正を行い、改善された思考を生成する 。
-
Generation (生成): 一つの思考 から新たな思考 を生成する。CoTやToTにおける基本的なステップと同様である 。
3.3 評価関数 と ランキング関数
- 評価関数 : 思考 の品質をスコア化する。LLM自身による自己評価や、人間によるフィードバック、あるいはタスク固有の検証器(Sortingにおける順序チェックなど)が用いられる 。
- ランキング関数 : グラフ内の思考から、スコアに基づき上位 個を選択する。これは探索空間を制限し、コンテキストサイズを節約するために重要である 。
3.4 構造的指標:Latency-Volume Tradeoff
GoTの構造的優位性を定量化するため、論文では新たに「思考の体積(Volume of a thought)」という概念を導入し、Latency(待ち時間/深さ)とのトレードオフを解析している 。
- Latency (): グラフ内の経路の長さ(逐次的なステップ数)。
- Volume (): ある思考 に到達可能な(影響を与えうる)先行思考の総数 。
各プロンプティング手法における比較は以下の通りである(入力サイズ 、分岐係数 )。
| 手法 | Latency (Order) | Volume (Order) | 構造的特徴 |
|---|---|---|---|
| CoT | 直列。情報は蓄積されるがステップ数が長い。 | ||
| CoT-SC | 並列。各パスは短いが、パス間の情報共有がないためVolumeは小さい。 | ||
| ToT | 木構造。探索効率は良いが、AggregationがないためVolumeは対数的に制限される。 | ||
| GoT | 理想的。Aggregationにより、短いパスで多くの情報を集約可能 。 |
GoTは、完全 -分木とその逆向きの木を結合したような構造をとることで、低レイテンシかつ高ボリュームを実現できる唯一の手法である。
4. システムアーキテクチャと実装
GoTを実装するためのシステムアーキテクチャは、モジュール性と拡張性を重視して設計されている 。
4.1 主要モジュール
- Prompter: グラフ構造をLLMへの入力テキスト(プロンプト)にエンコードする責務を持つ。コンテキスト内に過去の思考を含める際のフォーマットを管理する 。
- Parser: LLMの出力(Thought)から必要な情報を抽出し、プログラムが扱える内部状態(Thought State)に変換する 。
- Scoring & Validation: 生成された思考の正当性を検証し、スコアを付与する。外部ツールやLLM自身を使用する 。
- Controller: 推論プロセス全体の制御を行う中核モジュール。次の2つの構造を管理する 。
4.2 制御構造:GoOとGRS
GoTの実行制御は、静的な定義と動的な状態管理の分離によって実現されている。
- Graph of Operations (GoO): タスクごとの実行計画を定義する静的な構造。思考に対する操作(Generate, Aggregate, Scoreなど)の順序と依存関係を規定する 。これはアルゴリズムの「設計図」に相当する。
- Graph Reasoning State (GRS): 実行時の動的な状態を保持する構造。生成された全ての思考、そのスコア、現在のステップなどの履歴を管理する 。
この分離により、ユーザーはGoOを変更するだけで、CoTやToTを含む様々なプロンプティング戦略を容易に実装・切り替え可能となっている 。
5. 実験的評価と成果
論文では、GoTの有効性を検証するために、標準的なベンチマークではなく、構成的かつ複雑な推論を要する4つのタスクを用いて評価を行っている。
5.1 実験設定
- モデル: GPT-3.5 (主に使用), Llama-2 (比較用) 。
- 比較対象: IO, CoT, CoT-SC, ToT, ToT2 (設定を変えたToT)。
- 評価指標: タスクごとの品質スコア(エラー数など)およびコスト(トークン数)。
5.2 ユースケース別の結果
1. Sorting (数値列のソート)
重複を含む0-9の数字列(長さ32, 64, 128)をソートするタスク。LLMは長列のソートを苦手とするため、マージソートのアルゴリズムをGoTで模倣した 。
- GoTのアプローチ: 入力列を分割 (Split) 部分列をソート (Generate/Sort) ソート済み部分列を併合 (Aggregate/Merge)。
- 結果: 入力長128において、GoTはToTと比較してエラーの中央値を約 62% 削減し、同時にコストを 31%以上 削減した 。
- 考察: 分割統治アプローチにより、各ステップでLLMが扱うコンテキスト量が削減されたことが、コスト低下と精度向上の主因である。
2. Set Operations (集合演算)
2つの集合の共通部分(Intersection)を求めるタスク。
- 結果: IOやCoTは集合サイズが増加すると性能が著しく低下したが、GoTは安定して高い正解率を維持した。特にサイズ128の場合、ToTよりも有意に優れたスコアを記録した 。
3. Keyword Counting (キーワード出現数カウント)
テキスト内の特定カテゴリ(国名など)の単語出現数をカウントする。
- GoTのアプローチ: テキストをパッセージに分割 各パッセージでカウント サブ結果を集計 (Aggregate)。
- 結果: 入力テキストを細かく分割して処理し、最後に集約するGoTのアプローチが最も高い精度を示した 。
4. Document Merging (文書統合)
複数のNDA(秘密保持契約書)から、重複を最小限にしつつ情報を最大化した一つの契約書を作成する実用的なタスク 。
- 結果: GoTは、冗長性の排除と情報の保持率の両面において、他の手法を上回る品質の文書を生成した(スコア比較で優位)。
5.3 コストと精度のパレート最適性
実験全体を通して、GoTは単に精度が高いだけでなく、コスト効率においても優れていることが示された。ToTは探索の幅()や深さ()を増やすことで精度を向上できるが、コストが爆発的に増加する傾向がある。一方、GoTは不要な探索を行わず、有効な部分解を「集約」することで、探索空間を効率的に活用している 。
6. 考察と議論
6.1 なぜGoTは有効なのか?
GoTの勝因は、LLMの推論プロセスを「人間の思考」や「アルゴリズムの構造」により近づけた点にある。
- 非線形な思考の模倣: 人間は問題解決において、複数のアイデアを結合したり、前の思考に戻って修正したりする。GoTのグラフ構造はこのプロセスを自然に表現できる 。
- アルゴリズム的分解: マージソートの例に見られるように、複雑な問題を「分割統治」可能な小さなサブタスクに分解し、それらを構造的に統合することで、LLMのコンテキストウィンドウの制限や注意機構の分散による性能低下を回避している 。
6.2 既存手法との関係
GoTは、CoTやToTをその特殊形として包含する一般化フレームワークである。
- が一直線ならば CoT。
- が木構造で Aggregation を持たなければ ToT。 これにより、タスクの性質に応じて最適なトポロジーを選択・設計できる柔軟性を持つ 。
7. 結論
Besta et al. による Graph of Thoughts (GoT) は、大規模言語モデルのプロンプティングにおいて「グラフ構造」と「集約(Aggregation)」という概念を導入することで、推論能力の限界を拡張した。数理的には、グラフ理論に基づく変換操作と、レイテンシ・ボリュームのトレードオフ最適化によってその優位性が裏付けられている。
実証実験においては、ソートや文書統合などのタスクで、従来のToTと比較して大幅なコスト削減と品質向上を達成した。これは、LLMを単なるテキスト生成器としてではなく、複雑な問題解決エンジンのパーツとして組み込む際の、新たな設計指針(Design Pattern)を提供するものである。
参考文献
- Besta, M., et al. (2023). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. arXiv:2308.09687v4 [cs.CL].
- Wei, J., et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903.
- Yao, S., et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS ‘23.
- Wei, J., et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models.
- Wang, X., et al. (2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models. ICLR ‘23.
- Long, J. (2023). Large Language Model Guided Tree-of-Thought. arXiv:2305.08291.
- Besta, M., et al. (2023). Formal definition of GoT framework.
- Besta, M., et al. (2023). System Architecture of GoT.
- Besta, M., et al. (2023). Evaluation Results on Sorting Task.
- (その他、本文中で引用した全ての文献は原著論文のReferencesセクションに準拠する)
補遺:GoTにおけるグラフ操作の数理的詳細
本セクションでは、GoTの中核をなすグラフ変換操作の数理的定義と、それが計算複雑性(特にコンテキスト長とAPIコール数)に与える影響について、アルゴリズム的な視点から深掘りする。
A. グラフ変換の集合論的記述
GoTにおける状態遷移 は、頂点集合 と辺集合 に対する集合演算として厳密に定義される。
ある変換 が適用されるとき、新しい状態 は以下のように導出される。
-
Generate (): 既存の思考 に基づき、 個の独立した新しい思考 を生成する。
これはToTにおけるBranching操作と同等であり、探索空間を広げる役割を持つ。
-
Aggregate (): GoTの最重要操作。 個の思考を統合し、単一の思考 を生成する。
この操作により、グラフのトポロジーにおいて合流点(Confluence Point)が形成される。情報理論的には、異なるコンテキストからの情報を圧縮・統合することで、後続の推論におけるエントロピーを減少させる効果が期待される。
B. コストモデルと計算量
プロンプティングスキームのコストは、主に「生成される思考の総数(頂点数)」と「各ステップでのコンテキストサイズ」に依存する。
GoTにおける総コスト は、グラフ内の全頂点 に対するトークンコストの総和で近似できる。
分割統治法(例:マージソート)を適用した場合のコスト優位性は以下のように説明できる。 サイズ の問題を扱う際、CoTでは常にサイズ のコンテキストを保持し続ける必要があるため、ステップ数 に対してコストは となる(線形増加)。 一方、GoTで問題を 個に分割して並列処理し、後に統合する場合、深さ のレベルでの各ノードの入力サイズは 程度に縮小される。
厳密な係数はプロンプトのオーバーヘッドに依存するが、巨大な問題をそのまま扱うよりも、小さな部分問題の総和の方が、LLMのAttention機構の計算量 (はシーケンス長)の観点からも、実際のAPIコストの観点からも有利になる場合が多い。これが、実験結果においてGoTがToTよりも低コストで高い性能を出せた数理的な背景である。
補遺:高校数学と線形代数で解き明かすGraph of Thoughtsの数理
本セクションでは、Graph of Thoughts (GoT) がなぜ高い性能を発揮するのか、そのメカニズムを行間を補いつつ数理的に説明します。複雑なアルゴリズムに見えるGoTも、高校数学の「関数」「数列」および線形代数の「ベクトル」の言葉で記述することで、その本質が「誤差の平均化」と「最適化問題」にあることが理解できます。
1. 言語モデルのベクトル関数による定式化
大規模言語モデル(LLM) は、数学的には入力テキストを処理し、出力テキストを生成する巨大な関数とみなせます。
入力と出力のベクトル化
線形代数の視点では、あらゆるテキスト(思考 )は高次元のベクトル空間上の点(ベクトル)として表現されます。
- 入力: プロンプトや文脈を表すベクトル
- 出力: 生成された思考を表すベクトル
LLMはこの変換を行う写像 です。
※厳密には確率分布 からのサンプリングですが、ここでは最も確からしい出力を得る関数として扱います。
2. 「Aggregation(集約)」の数理:なぜ混ぜると良くなるのか?
GoTの最大の強みである Aggregation(複数の思考の統合)は、数学的には**「アンサンブル学習」や「ベクトルの平均化」**として解釈できます。
独立した試行と誤差の相殺
ある問題に対する正解をベクトル とします。LLMが生成する思考 には、必ず誤差(ノイズ) が含まれます。
ここで、CoT-SC(Self-Consistency)のように独立して 個の思考 を生成したとします。これらの誤差 がランダムで、正の方向にも負の方向にも偏りがない(期待値 )と仮定すると、これらを「集約(平均化)」した新しい思考 は以下のようになります。
統計学的に、独立した誤差の平均をとると、その分散は に縮小します。 つまり、GoTにおけるAggregationとは、**「複数の異なる視点(推論パス)をベクトル的に合成することで、個々の推論に含まれるバイアスや誤りを相殺し、より正解に近いベクトルを得る操作」**であると数理的に正当化できます。
3. 明示的な目的関数(Objective Function)の設定
GoTは、漠然と回答を生成しているのではなく、数学的な**「最適化問題」**を解いています。すなわち、ある評価関数(目的関数) を最大化するような出力 を探索するプロセスです。
論文中のタスクを例に、その中身を明確に示します。
ケーススタディ:ソーティング(整列)
数字の列 を出力する場合、目的関数(コスト関数 )は以下のように定義されます。これを最小化することが目標です。
- は条件を満たすとき1、そうでないとき0となる指示関数。
- 第2項は、入力に含まれる数字の個数と出力に含まれる数字の個数のズレ(幻覚など)へのペナルティ。
GoTでは、この関数 の値を評価器(Scoring)で計算し、値が悪い枝を切り捨て(Pruning)、値が良い枝のみを採用して次の生成を行うことで、解を反復的に改善しています。
ケーススタディ:文書統合(Document Merging)
複数の契約書を統合する場合、目的関数は「情報の網羅性」と「冗長性のなさ」のトレードオフとして定式化されます。
- : 元文書の重要情報がどれだけ含まれているか(再現率)。
- : 同じ情報が重複して書かれていないか。
- : 重み係数。
4. LLMプロンプティングへの応用:GoT効果を得るためのレシピ
GoTのような複雑なグラフ制御システムを構築せずとも、この数理的背景を理解していれば、チャット形式のプロンプトで近い効果を得ることが可能です。以下にその具体的な手法を解説します。
手法A: 擬似的なAggregation(マニュアル・アンサンブル)
「ベクトルの平均化」効果を狙い、単一の出力ではなく、複数の案を出させてから統合させるプロンプトです。
プロンプト例:
- 「この問題について、異なる観点から3つの解決案を生成してください。(案A、案B、案C)」
- 「これら3つの案の長所と短所を比較してください。」
- 「それぞれの長所を組み合わせ、短所を補った『最良の統合案』を作成してください。」
これにより、1回の生成(One-pass)では避けられない確率的な「外れ値」を回避し、精度の高い回答へ収束させることができます。
手法B: 再帰的なRefinement(勾配上昇法の模倣)
目的関数 を最大化するために、評価と修正のループを回します。
プロンプト例:
- 「まず、初稿を書いてください。」
- 「この初稿を、次の基準(目的関数)で採点し、問題点を列挙してください:【基準:論理的整合性、網羅性、具体性】」
- 「指摘された問題点を修正し、スコアを高めた第2稿を作成してください。」
これは数理的には、評価関数の勾配(改善方向)に沿って解を更新するステップ に相当します。
手法C: 分割統治(次元削減)
入力ベクトル の次元数(トークン量や複雑さ)が大きすぎると、関数 の精度は低下します。問題を部分グラフに分解します。
プロンプト例:
- 「この複雑なタスクを、独立して解決可能な3つのサブタスクに分割してください。」
- 「サブタスク1〜3をそれぞれ順に解決してください。」
- 「得られた3つの結果を統合して、最終的な回答を導出してください。」
これは、高次元の困難な問題を、低次元の解きやすい小問題 に帰着させるアプローチです。
結論: Graph of Thoughtsの本質は、グラフ構造そのものではなく、**「複数の推論パスの生成(Generate)」、「評価に基づく選抜(KeepBest)」、「情報の統合(Aggregate)」**という3つの数学的操作の組み合わせにあります。これらを意識的にプロンプトに組み込むことで、単なる対話を超えた高度な推論能力を引き出すことが可能になります。