ToT論文
https://scrapbox.io/files/65838ee02d788d0024515592.png
論文情報
タイトル：Tree of Thoughts: Deliberate Problem Solving with Large Language Models
著者：Shunyu Yao, Princeton University, Dian Yu, Jeffrey Zhao, Izhak Shafran
所属：Google DeepMind
論文から感じたこと
確かに多様なタスクでToTは有効かもしれない
一方で、トークン消費量が多くなってしまうため、APIのコストなどが気になるところではある
https://scrapbox.io/files/6583baac4384fb00240aaf20.png
実際に使うには？
GitHubに以下の記載があった
"思考のツリー "という手法を用いて、卓越した論理的思考力を持つ3人の専門家が共同で質問に答える。各専門家は、他の専門家のこれまでの考えを考慮し、誤りを認めながら、自分の思考プロセスを詳細に共有する。互いの考えを反復的に洗練させ、拡大し、謝意を表します。このプロセスは、決定的な答えが見つかるまで続く。回答全体をマークダウン表形式で整理する。課題は:
もしくは、このコードを使う
code:python
solution = tree_of_thoughts.solve(
initial_prompt=initial_prompt,
num_thoughts=num_thoughts,
max_steps=max_steps,
max_states=max_states,
pruning_threshold=pruning_threshold,
# sleep_time=sleep_time
)
print(f"Solution: {solution}")
論文の実験内容
24ゲーム
与えられた 4 つの整数 (4, 9, 10, 13) をそれぞれ 1 回ずつ使って、四則演算だけで答えを 24 にするゲーム。
(答え: (10 - 4) * (13 - 9) = 24 など)
ToTプロンプティングの詳細
https://scrapbox.io/files/658398070dea7c0024cb479c.png
propose prompt
value prompt
value_last_step_prompt
上図は「与えられた数の中から 2 つを選んで + - * / のどれかを適用」が LLM の思考の 1 ステップとなっている
3 ステップで必ず答え (の候補) に辿り着く。
作文
4 つの段落それぞれが指定された文で終わるような、自然に繋がる文章を作る問題。
https://scrapbox.io/files/658398d68de8c5002468a2bf.png
ミニクロスワード
5x5 のクロスワードパズル問題で、文字レベル、単語レベル、問題レベルの正答率を評価
https://scrapbox.io/files/65839901eaae740022188be7.png
論文解説
概要 (Abstract)
- 言語モデルは多様なタスクで問題解決に用いられていますが、従来のモデルはトークンレベルの左から右への決定プロセスに限定されていました。これにより、戦略的先読みや初期決定が重要なタスクで不足が生じます。
- ToTは、問題解決に向けた中間ステップとしての「思考」を検討し、複数の推論パスを考慮し、次の行動を自己評価することで意図的な意思決定を行うことができます。
- 実験では、ToTは「Game of 24」、「Creative Writing」、「Mini Crosswords」といった複雑な計画や探索を要求するタスクで言語モデルの問題解決能力を大幅に向上させました。
導入 (Introduction)
- 従来の大規模言語モデル（LLMs）は、テキスト生成のための単純な自動回帰メカニズムに基づいていますが、これだけでは一般的な問題解決者としては不十分です。
- 人間の認知研究から、意思決定には高速で自動的な「システム1」と遅く、意図的な「システム2」の二つのモードがあることが示唆されています。
- ToTは、「システム2」に相当するより意図的な計画プロセスを言語モデルに導入することを目指しています。
背景 (Background)
- CoTプロンプトは、非自明な入力と出力のマッピングを改善するために提案されましたが、局所的な探索や全体的な計画が欠けていました。
Tree of Thoughts: Deliberate Problem Solving with LM
- ToTは、問題を探索木として扱い、各ノードが「思考」で表される状態として表現されます。
- このフレームワークでは、思考の分解、思考の生成、状態の評価、探索アルゴリズムの選択が重要です。
- ToTの実装では、言語モデルを使って多様な「思考」を生成し、評価し、幅優先探索（BFS）や深さ優先探索（DFS）などの探索アルゴリズムを組み合わせます。
実験 (Experiments)
- 「Game of 24」、「Creative Writing」、「5x5 Crosswords」といった、既存の言語モデルでは難しいとされるタスクを用いてToTの効果を評価しました。
https://scrapbox.io/files/658399676fc13f0023c128de.png
- ToTはこれらのタスクで、標準的なIOプロンプトやCoTプロンプトよりも優れた結果を示しました。
ToT の正答率は 74% で、他のプロンプト手法より高い
「探索したツリーのノード数」に対する正答率を比較しても、他の手法より高い
CoT は最初の 1, 2 ステップで、約60%が無理筋に当たっているが、ToT はそれを回避できている
https://scrapbox.io/files/658399817f22b5002621e844.png
左: 文章生成
出力された文章を GPT-4 に評価させた結果、ToT のスコアが高い
CoT と ToT で生成された文章のどちらかを人間に選ばせた場合でも、ToT の方が良い結果
右: miniクロスワード
ToT の正答率が最も高い
ツリー探索の際に枝刈りやバックトラックをさせないと正答率が落ちる
https://scrapbox.io/files/6583998d15bb48002393b2ec.png
Limitation
実験タスクの選定が甘いかもしれない
24ゲーム
簡単なコードを書かせるだけで対処可能
クロスワード：LLM 以外で解く既存手法がある
作文：ToT と Self-Refinement のスコアにあまり差が無い
トークン消費量
GitHub レポジトリの /logs 以下に各実験のログが残っており、そこには OpenAI API のトークン消費量も記録されています。これを見ると全てのタスクで ToT の方が多くトークンを消費しているため、フェアな実験設定とは言い難いところです。
24 ゲームの ToT の結果
"usage_so_far": {
"completion_tokens": 547859,
"prompt_tokens": 1387936,
"cost": 74.50962
}
24 ゲームの CoT の結果
"usage_so_far": {
"completion_tokens": 461878,
"prompt_tokens": 148580,
"cost": 32.17008