Tree of Thoughts: LLMの探索による意図的な問題解決
過去2回の記事では、自己反省（Reflexion）やツールとの対話的な批判（CRITIC）を通じて自己修正を行うエージェントについて見てきましたが、今回は一歩引いて、より構造的なアプローチを検討してみたいと思います。「もしエージェントが最初から単一の推論パスに固執しなかったらどうなるか？」という問いです。YaoらによるTree of Thoughts (ToT)（NeurIPS 2023）は、まさにそれを提案しています。これは、LLMが線形な連鎖ではなく、中間的な推論ステップが枝分かれする探索空間を探索するフレームワークです。今回この論文を取り上げたのは、LLMの推論における「意図的な探索（deliberate search）」を最も明確に定式化しているからです。財務計算において、たった1つの中間ステップの誤りが下流のすべてを密かに台無しにしてしまう可能性がある場合、この意図的な探索こそが必要になります。
論文の概要
Shunyu Yao、Dian Yu、Jeffrey Zhao、Izhak Shafran、Thomas L. Griffiths、Yuan Cao、Karthik Narasimhanらは、Chain-of-Thoughtプロンプティングの一般化としてTree of Thoughtsを提案しました。重要なポイントは、中間的な推論ステップを、独立して評価可能な一貫したテキスト単位である「思考（thoughts）」として扱い、それらを連鎖ではなくツリー構造に組織化することです。各ノードでモデルは複数の候補となる「思考」を生成し、それぞれを評価します（別のLLM呼び出しを介して、状態を「確実 / 可能性がある / 不可能」としてスコアリングします）。その後、標準的な探索アルゴリズム（幅優先探索 BFS または 深優先探索 DFS）を適用してツリーを横断します。もしある枝が行き止まりに見えれば、モデルはその枝を切り捨て（プルーニング）、あるいは後戻り（バックトラッキング）することができます。これはCoTもCoT-SC（Self-Consistency）もできないことです。
論文では、3つのタスクで評価を行っています。「Game of 24」（4つの数字を四則演算で組み合わせて24にする）、「Creative Writing」（4つのランダムな文末表現を使用して一貫した文章を作成する）、「Mini Crosswords」（5×5のクロスワードパズルを解く）です。これら3つはいずれも、試行錯誤やバックトラッキングが有効な推論を必要とするものであり、まさに著者が意図した設定です。
主なアイデア
- Game of 24において、ビーム幅 b=5 のToTは74%の成功率を達成しました。これに対し、標準的なCoTを用いたGPT-4は4%、100個のサンプルを用いたCoT-SCは**9%**でした。この差は劇的です。
- GPT-3.5 + ToTは同じタスクで**19%**しか達成できませんでした。この手法のメリットはモデルの能力に強く依存します。GPT-4の「思考生成」の質が利益の大部分を占めており、GPT-4生成 + GPT-3.5評価は64%を達成した一方、GPT-3.5生成 + GPT-4評価は31%に留まりました。
- Creative Writingでは、GPT-4による一貫性スケールでToTは7.56を記録し（CoTは6.93）、人間のアノテーターも41/100の割合でToTの出力を支持しました（CoTは21/100）。
- Mini Crosswords：ToTは60%の単語レベル精度を達成しましたが（CoT：40.6%、IO：15.6%）、ゲーム全体を解けたのは20回中4回（20%）のみでした。単語レベルとゲームレベルの成功率の乖離は、バックトラッキングがあっても、グローバルな制約充足がいかに困難であるかを示しています。
- 評価ステップ自体がLLMの呼び出しです。クロスワードにおいて、評価者が馴染みのない語彙のために正しい部分的な状態を「不可能」と見なすことがあり、評価者のミスが探索を台無しにする「失敗の連鎖」モードが指摘されています。
- 計算コスト：Game of 24において、ToTは1ケースあたり約0.74ドルかかり、100サンプルのCoT（0.47ドル）を上回ります。著者自身も、GPT-4がすでに得意としているタスクについては、このオーバーヘッドに見合う価値はないと指摘しています。
評価：何が有効で、何がそうでないか
核心的な結果、つまり「中間的な思考に対するツリー探索は、バックトラッキングを必要とするタスクにおいて連続的なCoTを大幅に上回る」という点は、現実的であり再現可能です。Game of 24における74%対4%という差はノイズではありません。その理由はメカニズム的に健全です。CoTでは1つの誤った中間式が連鎖全体を台無しにしますが、ToTはその枝を切り捨てて別の分解を試みることができます。
一方で、汎用性に関する主張にはあまり説得力を感じません。評価された3つのタスクは、数学パズル、構造的制約のあるライティング、単語ゲームといった、比較的「人工的」なものです。本番環境の財務ワークフローに現れるような、オープンエンドで曖昧な問題には似ていません。また、著者らはGPT-4（およびアブレーションとしてのGPT-3.5）のみで評価しているため、より小型のモデルやファインチューニングされたモデルでToTがどう機能するかは不明です。GPT-3.5での19%という数字は、答えが「芳しくない」ことを示唆しています。
クロスワードにおけるゲームレベルの失敗（単語精度60%に対し成功率20%）は、より深い問題を指し示しています。ToTはローカルな評価器に導かれたローカルな探索です。サブソリューション間の相互作用が密接な問題において必要とされる「グローバルな制約モデル」を保持し ていません。後続の「Graph of Thoughts」論文（Besta et al., AAAI 2024）はこの点を明示的に批判しており、思考をマージしたりサイクルを形成したりすることを許可することで、ソートタスクにおいてToTを62%上回る質を達成し、コストを31%以上削減できることを示しています。
最後に、実務においてはコスト構造が重要です。b=5で評価器を繰り返し呼び出すToTは、1回のCoTパスよりもAPIコストが概ね15〜20倍高くなります。レイテンシやコストに敏感なアプリケーションにおいて、これは容易に受け入れられるものではありません。
なぜこれが金融AIにとって重要なのか
率直に言えば、ToTはBeancountの問題空間の狭い範囲において最も重要ですが、その範囲は無視できないものです。
バックトラッキングが必要となる典型的な財務タスクは、曖昧な取引を伴う多段階の勘定科目分類です。インポートされた銀行明細を勘定科目表にマッピングする場合、連鎖の初期段階での誤った割り当て（例えば、ローンの実行を収入として扱うなど）が、数ステップ後の残高照合（balance check）の失敗として波及することがあります。CoTエージェントでは、残高エラーが判明した時点ですでに、元の分類を再検討するメカニズムがありません。ToTエージェントであれば、そのノードまでバックトラッキングして、代わりに Liabilities:Loans を試すことができます。
同様に、会計年度を通じた税務最適化は、純粋なツリー探索問題です。標準控除にするか項目別控除にするか、キャピタルゲインの実現タイミング、寄付金のまとめ払い（バンチング）などです。これらの決定は非線形に相互作用するため、確定させる前に複数の枝を評価する必要があります。ToTのBFS/DFSフレームワークは、この構造に自然に適合します。
一方で、ToTが役に立たないのは、Beancountにおける支配的なケース、つまり日常的な取引の入力と照合です。元帳に明確な対応相手がいる取引については、CoT + PAL（計算をコードインタープリタにオフロードする）の方が速く、安く、そして十分に正確です。expenses:groceries（食費）の分類にToTを持ち出すのは、画鋲を打つのに大ハンマーを使うようなものです。
書き戻しの安全性（write-back safety）に関するより差し迫った懸念は、評価器の信頼性の問題です。状態評価器もLLMである場合、それは誤る可能性があります。そして誤った評価は探索を遅らせるだけでなく、正しいパスを切り捨ててしまいます。ToTを使用する本番用の財務エージェントは、別のLLM呼び出しではなく、外部のオラクル（残高照合、スキーマバリデータ、ルールエンジンなど）を評価器として使用する必要があるでしょう。
次に読むべきもの
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024) — arXiv:2308.09687。ToTをツリーから任意のグラフへと拡張し、思考のマージやフィードバックループを可能にします。ToTのオーバーヘッドなしに探索ベースの推論を行いたい場合、コスト削減の主張（31%以上）は直接的に関連します。
- Large Language Models Cannot Self-Correct Reasoning Yet (Huang et al., ICLR 2024) — arXiv:2310.01798。批判的な論点として、外部からのフィードバックがない限り、内発的な自己修正は推論パフォーマンスを低下させると述べています。これは、ToTのLLMベースの評価器が探索を導くのに十分な信頼性を持っているという前提に疑問を投げかけています。
- RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation (arXiv:2409.09584) — BFS/DFSの代わりにモンテカルロ木探索（MCTS）を思考探索に適用し、外部オラクルとしての実行フィードバックを利用します。コード生成の設定は、構造的に元帳への書き戻しと似ています。検証可能な正解（コードは実行できるか？残高照合は通るか？）が存在する場所こそ、モンテカルロ・ロールアウトが価値を発揮する場面です。
