Tree of Thoughts (ToT)

思考の木（ToT）は、大規模言語モデル（LLM）が部分的な解答の木を探索して問題を解く、プロンプトエンジニアリングのフレームワークです。各ステップでモデルはいくつかの次のステップ候補（思考と呼ばれます）を提案し、それぞれの状態がどれだけ有望かを評価します。そのうえで探索アルゴリズムが、どの分岐を展開、維持、破棄するかを決定します。最初のトークンから1つの推論経路を進む思考の連鎖プロンプティングに対し、ToTでは先を見越して後戻りできます。Princeton UniversityとGoogle DeepMindのShunyu Yaoらは、NeurIPS 2023で発表したTree of Thoughts: Deliberate Problem Solving with Large Language Modelsでこの手法を紹介しました。同じ月にJieyi Longも、LLMで数独を解く同様の木探索システムを提案しました。24ゲームのパズルでは、ToTによってGPT-4の成功率が、思考の連鎖プロンプティングの4%から74%に向上しました。

思考の木の仕組み#

Yaoらは、4つの設計上の選択肢によってToTを定義しています。

• 思考の分解: 1つのステップをどのように定義するかです。24ゲームでは1つの式、創作テキスト生成では文章の構成案、クロスワードでは配置する1つの単語が思考に当たります。
• 思考の生成器: 候補をどのように生成するかです。オープンエンドなステップにはモデルが複数の思考を個別にサンプリングする方法が適しています。選択肢が限られている場合は、1つのプロンプトで異なる候補のリストを提案させると、重複を避けられます。
• 状態評価器: 進捗をどのように判断するかです。モデルは各状態を個別に評価し、たとえば目標到達の可能性を「確実」「たぶん」「不可能」で判定するか、複数の状態から最良のものに投票します。これらの評価は探索のヒューリスティックとして機能します。古典的な探索では、手書きのスコア関数がこの役割を担います。
• 探索アルゴリズム: 木をどのように探索するかです。幅優先探索は各レベルで最良のb個の状態を維持します。深さ優先探索は最も有望な分岐をたどり、評価器が除外した状態を枝刈りしてから後戻りします。

例: 24ゲーム#

24ゲームでは、4つの数字をそれぞれ1回ずつ使い、+、-、x、/を組み合わせて24を作ります。ToTでは解答を3つのステップに分け、それぞれのステップで2つの数字を結合する式を作ります。入力が4、9、10、13の場合、候補を提案するプロンプトは次のような候補を列挙します。

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

次に、値を評価するプロンプトで、残りの各数字の組み合わせから24を作れるかどうかを尋ねます。「4、4、10」は(10 - 4) x 4 = 24となるため「確実」です。「6、9、13」も(13 - 9) x 6 = 24となるため「確実」です。一方、「10、13、13」と「9、10、52」は不可能なので、探索では最初の2つの分岐だけを展開します。最初の分岐をたどると、10 - 4 = 6（残り: 4、6）、続いて4 x 6 = 24となります。

論文では、難しいゲーム100問を使って実験しました。幅優先探索では、各状態を3回ずつ評価し、各ステップで最良の状態を5個維持しました。GPT-4を用いたToTはゲームの74%を解きました。直接プロンプトでは7.3%、思考の連鎖では4.0%、自己整合性を用いた思考の連鎖では9.0%でした。思考の連鎖を100回サンプリングした場合でも、最良の結果は49%にとどまり、各ステップで1つの状態だけを維持するToTは45%でした。

思考の木の位置付け#

ToTは、初期の選択が後続の選択を制約し、誤った最初のステップを修正しにくい問題、たとえばパズル、計画、複数ステップの数学問題に役立ちます。5x5のミニクロスワードでは、枝刈りを用いた深さ優先ToTによって単語の60%を正しく埋め、20問中4問を解きました。代償は計算量です。木の各レベルで複数回の生成と評価が必要になるため、1つの回答に数十回以上のモデル呼び出しが必要になる場合があります。1つの連鎖より多くのトークンを必要とし、推論レイテンシも同様に増加します。

生成、評価、展開という同じループは、ハイパーパラメーター調整などの自動実験探索では、より大まかな単位で実行されます。Ultralytics Platform AutoTrainでは、Ask AIが、たとえば画像サイズを640、800、960にするなど、1つの設定だけが異なる複数のUltralytics YOLOモデルを訓練できます。そのうえで、検証データのmAP50-95を使って完了した実行を比較し、最良の結果に基づいて次の実験を提案します。

思考の木と関連手法#

• 思考の連鎖プロンプティング: 1つの推論経路で、各レベルに分岐が1つだけある木に相当します。
• ReActプロンプティング: 推論と、検索やツール呼び出しなど外部環境でのアクションを交互に行い、それらのアクションの結果に基づいて先へ進みます。ToTはモデル自身が生成した思考候補を探索します。
• 自己整合性: 完成した連鎖を複数サンプリングし、最終回答に多数決を適用します。途中のステップは評価しません。
• Graph of Thoughts：思考をマージして洗練することもできるグラフへとツリーを一般化した手法で、ToTよりコストを31%以上抑えながら、ソート品質が62%向上したと報告されています。
• モンテカルロ木探索（MCTS）：AlphaGoを支える探索アルゴリズムで、新しい分岐の探索と有望な分岐の活用のバランスを取り、思考の幅優先探索や深さ優先探索に代わる手法として利用できます。
• 推論モデル：強化学習によって、1回の生成で長い推論トレースを書くように学習されています。ToTでは、通常のモデルの外部にある探索プログラムによって分岐やバックトラッキングを行います。