今回の論文
今回取り上げるのは、Shunyu Yao、Dian Yu、Jeffrey Zhao、Izhak Shafran、Thomas L. Griffiths、Yuan Cao、Karthik Narasimhan による論文「Tree of Thoughts: Deliberate Problem Solving with Large Language Models」です。2023年5月17日に arXiv で公開されました。公開元は arXiv、研究分野は LLM 推論、探索アルゴリズム、計画的問題解決です。URL は https://doi.org/10.48550/arXiv.2305.10601 です。
この論文を選んだ理由は、いまの AI アプリ開発でよくある「1回の推論で正解まで一直線にたどり着けない」問題に、かなり本質的な視点を与えてくれるからです。特に、複雑なエージェント処理、複数ステップの計画、制約付き生成を扱うときに、「まず候補を分岐させてから良い枝を残す」という考え方はそのまま実装のヒントになります。
どんな技術か
Tree of Thoughts、略して ToT は、LLM の出力を 1 本の文章としてそのまま伸ばすのではなく、途中の思考ステップを複数候補に分岐させ、評価し、必要なら戻りながら解を探す推論技術です。
通常の Chain-of-Thought は、途中経過を書かせる点では有効ですが、基本的には 1 本の推論列を左から右へ伸ばしていきます。そのため、最初の一手を間違えると、そのまま間違った方向へ進みやすいです。ToT はそこを変えて、途中の思考を「探索木」として扱います。
要するに ToT は、LLM に対して「答えを1回で出して」と頼むのではなく、「次の手を何通りか考え、見込みを比べ、良さそうなものを先に掘る」という探索的な振る舞いを持たせる技術です。これは単なるプロンプト工夫というより、LLM を探索器として使うための推論フレームワークだと見るほうが実態に近いです。
課題
この技術が解決しようとしているのは、LLM が複雑な問題を解くとき、局所的にはもっともらしく見えても、全体としては誤った道に入りやすいという課題です。
何が難しいのかというと、通常の自己回帰生成では、出力はトークン単位で順番に確定していき、いったん選んだ方向を後から大きく修正しにくいからです。数式問題、制約付き生成、探索が必要なタスク、複数段階の意思決定では、この性質がかなり不利に働きます。
既存の方法にも限界がありました。通常の Input-Output prompting は当然ながら途中の探索を持ちませんし、Chain-of-Thought も途中式は出せますが、各ステップで別候補を比較する仕組みは弱いです。Self-Consistency は複数の推論列を最後に多数決しますが、途中の段階で枝を選別したり、見込みの低いルートを早めに捨てたりはしません。
なぜこの課題を解く必要があるのかというと、実際の AI システムでは、正解に至るまでに試行錯誤が必要な場面が増えているからです。エージェントがツール実行計画を立てるとき、複数の問い合わせ方や操作順序を比べたいことがあります。コード修正、数理推論、ルール制約の強い生成、複数文書をまたぐ意思決定でも、「まず候補を出して、途中で見直す」能力があるかどうかで結果が大きく変わります。
実務で見ると、1 回の LLM 呼び出しに全部を背負わせる設計は、タスクが難しくなるほど不安定になります。ToT は、推論の中間状態を明示的に持ち、探索と評価を分けることで、この不安定さを減らそうとした技術です。
用語解説
- Chain-of-Thought
- LLM に途中の推論過程を書かせる手法です。ToT はこの考え方を出発点にしつつ、途中経路を1本に固定せず、複数候補の探索に拡張しています。
- 探索木
- 候補の分岐を木構造として表したものです。ToT では各ノードが「ここまでの部分解」を表し、どの枝を掘るかが性能を左右します。
- 状態評価
- 途中の部分解がどれだけ有望かを見積もる処理です。ToT ではこの評価自体も LLM にやらせる点が重要で、単なる生成器ではなくヒューリスティック評価器としても使います。
- ヒューリスティック探索
- 全候補を総当たりせず、有望そうなものを優先して調べる探索方法です。ToT の実用性は、このヒューリスティックがあるからこそ成り立っています。
- Backtracking
- 進めた枝がうまくいかなかったときに前の状態へ戻って別ルートを試す考え方です。エージェント実装でも失敗時の再計画に近い役割を持ちます。
技術の仕組み
ToT の仕組みは、LLM を単なる次トークン予測器としてではなく、「候補生成」と「候補評価」を行う部品として使い、その上に探索アルゴリズムを載せることにあります。
基本アイデア
論文では、問題解決を 1 本の推論列ではなく、思考の木をたどる探索問題として捉えます。各ノードは「入力」と「ここまでの思考列」からなる部分解です。そこから次の思考候補をいくつか生成し、それぞれが有望かどうかを見て、残す枝と捨てる枝を決めます。
この発想の重要な点は、途中の思考をそのまま出力ではなく「探索単位」に変えていることです。つまり、LLM の中間生成を最終回答の一部として固定せず、探索のための作業メモとして扱います。
モデル構造
ToT は新しいモデルアーキテクチャを学習する論文ではありません。既存の LLM をそのまま使い、推論時の制御ロジックを変える方式です。追加学習なしで導入できるため、実装の本質はモデル重みではなくオーケストレーション層にあります。
論文では GPT-4 を中心に評価しており、モデルの外側に次の 4 要素を置いています。
1. Thought decomposition
まず、問題をどの粒度の思考ステップに分けるかを決めます。Game of 24 では「1 行の中間式」、Creative Writing では「文章全体の下書き計画」、Mini Crosswords では「1 つの単語候補」といった具合です。
ここで大事なのは、思考単位が小さすぎると評価しにくく、大きすぎると分岐の意味が薄れることです。ToT は、タスクに応じて「評価できる最小単位」を設計する発想だと言えます。
2. Thought generation
各状態から、次の思考候補を複数個生成します。論文では主に 2 通りのやり方を使っています。
1 つは独立サンプル方式で、同じ状態から複数の候補をランダムに出させます。これは Creative Writing のように候補空間が広いタスクに向いています。もう 1 つは提案方式で、同じ文脈の中で重複しない複数候補をまとめて提案させる方法です。こちらは Game of 24 や Crosswords のように候補空間が比較的狭い場面に向いています。
3. State evaluation
ToT の肝は、生成した候補を LLM 自身に評価させる点です。論文では、各状態を単独で採点する value 方式と、複数状態を比較して良いものに投票する vote 方式を使い分けています。
value 方式は、たとえば「この中間式から 24 に到達できそうか」を sure、maybe、impossible のように判定する設計です。vote 方式は、複数の文章プランを見比べて、どれが最も一貫した文章になりそうかを選ばせる設計です。
この構造によって、LLM は生成器と評価器の二役を担います。ここが実務でも重要で、検索器やルールベース評価器を別に用意しなくても、ある程度の探索制御が組めます。
4. Search algorithm
最後に、候補をどの順で掘るかを探索アルゴリズムで決めます。論文では主に BFS と DFS を使っています。
BFS
BFS は各ステップで有望な候補を幅広く残しながら進む方法です。浅い深さで方向性を見極めたいタスクに向いており、論文では Game of 24 と Creative Writing に使われました。
DFS
DFS は一度有望な枝を深く掘り、だめなら戻る方法です。探索深度が長く、途中で詰み判定や枝刈りをしたいタスクに向いています。論文では Mini Crosswords で使われました。
学習方法
学習は不要です。ToT は pre-trained な LLM に対し、プロンプト設計と探索制御を追加するだけで動きます。これは実運用上かなり大きく、独自学習基盤がないチームでも試しやすいです。
推論方法
推論は 1 回の生成ではなく、状態管理を伴う反復処理になります。ざっくり言うと、現在状態の集合を持ち、候補生成、候補評価、候補選別を繰り返しながら、最終状態に到達するまで探索します。
このため、ToT は通常の 1-shot 推論よりトークン消費は増えやすいです。ただしその代わり、難しいタスクでは「1 回で外す回数」を減らしやすくなります。正解率を上げるためにモデルをさらに大きくする以外の道を示した点が、この論文の大きな価値です。
実験と結果
論文では、ToT が本当に探索を必要とするタスクで有効かを検証するため、数学パズル、創作、クロスワードという性質の異なる 3 つの課題で評価しています。
何を検証したのか
主な検証点は、通常の直接生成や Chain-of-Thought よりも、探索つき推論のほうが難しい問題を解けるかどうかです。加えて、どの探索幅や探索戦略が効くか、途中での枝刈りや backtracking がどれくらい重要かも見ています。
使ったデータセットや評価指標
Game of 24 では 4nums.com 由来の 100 問を使い、正しい式を作れた割合を success rate として評価しています。Creative Writing では 100 個の入力に対して文章を生成し、GPT-4 による 1〜10 の一貫性スコアと、人手による比較評価を使っています。Mini Crosswords では GooBix 由来の 20 問を使い、文字単位、単語単位、ゲーム全体の正答率を測っています。
Game of 24 では 4% から 74% へ大幅改善
もっとも象徴的なのは Game of 24 の結果です。論文では、GPT-4 の CoT prompting が成功率 4.0%、IO prompting が 7.3%、CoT-SC が 9.0% だったのに対し、ToT は探索幅 b=5 で 74% を達成しました。探索幅 b=1 でも 45% あり、単に複数サンプルを取るだけではなく、途中状態を見ながら枝を残すことが効いていると読めます。
この差は、最初の数手を誤ると取り返しづらい問題では、左から右への一本勝負がかなり不利であることを示しています。論文のエラー分析でも、通常の CoT は最初の一手で崩れる割合が高いと報告されています。
Creative Writing でも一貫性評価が改善
Creative Writing では、ToT は文章の整合性でも優位でした。GPT-4 による平均スコアは IO の 6.19、CoT の 6.93 に対し、ToT は 7.56 でした。さらに人手比較では、100 ペア中 41 件で ToT のほうが良いと評価され、CoT が優勢だったのは 21 件でした。
この結果は、ToT が数理問題専用ではないことを示しています。文章生成でも、先に全体プランを複数案出し、その中から良いものを選ぶ設計が効くということです。プロダクト実装で言えば、いきなり本文を書かせるより、構成案レベルで探索するほうが安定しやすいと解釈できます。
Mini Crosswords では backtracking の価値が見える
Mini Crosswords では、ToT は文字正答率 78%、単語正答率 60%、ゲーム全体成功率 20% を記録しました。比較対象の IO はゲーム成功率 0%、CoT は 1% だったため、ここでも探索の有効性がはっきり出ています。
さらに、論文のアブレーションでは backtracking を外すとゲーム成功率が 5% まで落ち、枝刈りを外しても 5% まで落ちています。つまり ToT の価値は「複数案を出す」ことだけではなく、「見込みの低い枝を切る」「だめなら戻る」まで含めた探索制御全体にあります。
結果から何が言えるのか
この論文の結果から言えるのは、難しいタスクで必要なのは、いつもより長い Chain-of-Thought ではなく、途中状態を操作できる推論ループであることです。特に、正解までの経路が1本ではなく、途中で選び直しが必要な問題では、ToT のような探索ベースの推論が強いです。
一方で、単純な QA や短い定型タスクにまで常に ToT を入れるべきだ、という意味ではありません。探索の価値があるタスクだけに使うほうが実務的です。
何に使える？
ToT の考え方は、学術ベンチマークだけでなく、複数ステップの意思決定が入る AI アプリでかなり広く使えます。
AIエージェントの計画生成
エージェントがツールを使うとき、いきなり 1 本の行動列を確定するより、「どの情報を先に集めるか」「どの順で API を叩くか」「失敗時にどう巻き戻すか」を候補として持つほうが安定します。ToT の枠組みは、そのまま計画候補の分岐と選別に使えます。
複雑なコード修正やデバッグ
コード支援でも、難しいバグは 1 回の修正案で当てるより、「原因仮説を複数出す」「各仮説に対する調査手順を比べる」「有望な枝だけ掘る」ほうが成功しやすいです。ToT はこの流れを推論フレームワークとして整理しやすくします。
制約付き文章生成
契約文、説明文、提案書、長文回答のように、全体整合性が重要な生成では、本文の前に構成案や主張順序を探索するだけでも品質が上がりやすいです。Creative Writing の結果は、その方向性を裏づけています。
業務フロー自動化
社内オペレーションの自動化でも、1 つの依頼に対して処理ルートが複数あることは珍しくありません。ToT 的な考え方で「安全なルート」「速いルート」「情報不足時の確認ルート」を木として扱うと、エージェント設計がしやすくなります。
探索と評価を分けたワークフロー
ToT の発想は、LLM を一発回答器ではなく、生成器と評価器に役割分担させることです。これは RAG の再ランキング、SQL 生成の検証、テストケース生成の候補比較などにも応用しやすいです。
開発や事業へのヒント
この論文から得られるヒントは、AI プロダクトの性能改善を「モデルを強くする」だけで考えないほうがよい、という点です。推論フローの設計を変えるだけでも、難しいタスクではかなり振る舞いが変わります。
1-shot 依存をやめる
もし自分で AI アプリを作るなら、失敗コストが高い処理ほど 1-shot 出力に依存しない設計に寄せる価値があります。たとえば見積作成、障害調査、法務レビュー補助、要件分解などは、最終回答前に候補比較を入れたほうが事故が減りやすいです。
中間状態をアプリ側で持つ
ToT の重要な示唆は、中間思考をモデル内部に閉じ込めず、アプリ側の状態として管理することです。これにより、途中候補のログ保存、再評価、ヒューマンレビュー、失敗時の再開がしやすくなります。これは SaaS や社内ツールでも実装価値が高いです。
小規模プロダクトでも部分導入できる
ToT をフル実装しなくても、「計画案を3つ出す」「各案を別プロンプトで採点する」「上位1案だけ実行する」だけで、かなり ToT 的な設計になります。小規模なプロダクトでも試しやすく、モデル追加学習も不要です。
今後注目すべき方向性
今後は、ToT をそのまま使うよりも、探索コストを減らしつつどこで分岐すべきかを学習または推定する方向が重要になりそうです。また、ツール使用、環境状態、外部評価器と統合した探索型エージェント設計は、今後も強いテーマであり続けるはずです。これは推測を含みますが、実務上の発展方向としてはかなり自然です。
限界
ToT の最大の注意点は、推論コストが重くなりやすいことです。候補生成、候補評価、探索の繰り返しが必要なので、単発の応答よりも API コストもレイテンシも増えます。難しいタスクには効いても、単純タスクへ一律適用すると割に合わない可能性があります。
また、状態評価の質は LLM 自体の能力に依存します。候補を出すのは上手くても、どの候補が有望かを見抜く力が弱いと、探索が逆にノイズを増やすことがあります。評価器を同じ LLM に任せる構造には、この自己評価の限界があります。
実装面では、どの粒度で thought を切るか、何本候補を出すか、いつ枝刈りするかなど、チューニング点が多いです。タスクごとに設計を変える必要があり、完全に汎用な設定は作りにくいです。
さらに、論文の評価対象は GPT-4 と比較的限定的なタスクです。実運用でのエージェント、RAG、コード実行、ツール接続にそのまま一般化できるとは限りません。発想は強いですが、どの用途でも万能というわけではありません。
よくある質問
Q. Tree of Thoughts は Chain-of-Thought と何が違うのですか？
A. Chain-of-Thought は基本的に 1 本の推論列を順に伸ばしますが、Tree of Thoughts は途中の思考を複数候補に分岐させ、評価して枝を選びます。違いは「途中経過を書くかどうか」ではなく、「途中経過を探索対象として扱うかどうか」です。
Q. Tree of Thoughts は AI エージェントにそのまま使えますか？
A. そのまま完全適用するより、計画候補の分岐、行動案の採点、失敗時の backtracking といった部分を取り込むのが現実的です。特に複雑なツール選択や再計画が必要なエージェントとは相性が良いです。
Q. すべての LLM タスクで ToT を使うべきですか？
A. いいえ。短い要約や単純な FAQ のように 1 回で答えやすいタスクでは、コストに見合わないことが多いです。ToT は、探索や試行錯誤が本質的に必要なタスクでこそ効きます。
Q. Tree of Thoughts は学習が必要ですか？
A. 論文の提案自体は追加学習なしで動きます。必要なのは、thought の分け方、候補生成プロンプト、状態評価プロンプト、探索戦略の設計です。
Q. 実務で導入するなら、まず何から始めるのがよいですか？
A. まずは「候補を複数出す」と「候補を別プロンプトで評価する」の 2 段階に分けるだけでも十分です。そのうえで、失敗率が高い処理にだけ枝刈りや backtracking を足していくと、コストと効果のバランスを取りやすいです。
今日の学び
この論文は、LLM が複雑な問題で一本道の推論に縛られると、最初の判断ミスを引きずりやすい課題を扱いました。そこに対して Tree of Thoughts は、途中思考を木構造として扱い、候補生成、自己評価、探索、backtracking を組み合わせて解こうとしました。
ここから得られるヒントは、AI アプリの賢さはモデル性能だけでなく、推論フローの設計でも大きく変えられるということです。特にエージェントや複雑ワークフローでは、「まず分岐させ、あとで選ぶ」という設計がそのまま開発上の武器になります。