LLMで思考ゲームのような推論が必要なタスクを可能にする手法に関する論文「Tree of Thoughts: Deliberate Problem Solving with Large Language Models」を読んだ際のメモ。
LLMはアイディアを出したりする創作的なタスクや、要約や翻訳のような変換のタスクは得意だが、論理的な思考が必要なタスクは比較的苦手である。
Chain-of-thought (CoT)のようなプロンプトエンジニアリングによって、数学の問題もある程度解けるようになっているが、例えば将棋のような思考ゲームをプレイするようなことはできない。
この研究では、LLMとヒューリステックな探索を組み合わせることで、Game of 24という簡単な思考ゲームを解くことができる手法を提案している。
LLMの特性として、トークンを順番生成する過程で、途中で間違いに気づいても後戻りできずそのまま間違った回答をすることがある。
生成した終わった後に、内容が間違いかどうかは判断することはできる。
そこで、生成した内容をLLM自身で評価して、やり直すことができれば、正解を出せる可能性が高まる。
Game of 24
Game of 24は、4つの1桁数字を使用して、四則演算を組み合わせて答えが24になる数式を作るゲームである。
例：4 4 6 8
⇒(4 + 8) * (6 - 4) = 24
GPT4に解かせてみる
まずは、GPT4にfew-shotラーニングを使って、単一のプロンプトで解かせてみる。
Use numbers and basic arithmetic operations (+ - * /) to obtain 24. Input: 4 4 6 8 Answer: (4 + 8) * (6 - 4) = 24 Input: 2 9 10 12 Answer: 2 * 12 * (10 - 9) = 24 Input: 4 9 10 13 Answer: (13 - 9) * (10 - 4) = 24 Input: 1 4 8 8 Answer: (8 / 4 + 1) * 8 = 24 Input: 5 5 5 9 Answer: 5 + 5 + 5 + 9 = 24 Input: 5 5 4 3
回答：
Answer: (5 - 3) * (5 + 4) = 24
間違った答えが出力された。
CoTで段階的に思考させてみる
CoTで段階的に答えを出させてみた。
Use numbers and basic arithmetic operations (+ - * /) to obtain 24. Each step, you are only allowed to choose two of the remaining numbers to obtain a new number. Input: 4 4 6 8 Steps: 4 + 8 = 12 (left: 4 6 12) 6 - 4 = 2 (left: 2 12) 2 * 12 = 24 (left: 24) Answer: (6 - 4) * (4 + 8) = 24 Input: 2 9 10 12 Steps: 12 * 2 = 24 (left: 9 10 24) 10 - 9 = 1 (left: 1 24) 24 * 1 = 24 (left: 24) Answer: (12 * 2) * (10 - 9) = 24 Input: 4 9 10 13 Steps: 13 - 10 = 3 (left: 3 4 9) 9 - 3 = 6 (left: 4 6) 4 * 6 = 24 (left: 24) Answer: 4 * (9 - (13 - 10)) = 24 Input: 1 4 8 8 Steps: 8 / 4 = 2 (left: 1 2 8) 1 + 2 = 3 (left: 3 8) 3 * 8 = 24 (left: 24) Answer: (1 + 8 / 4) * 8 = 24 Input: 5 5 5 9 Steps: 5 + 5 = 10 (left: 5 9 10) 10 + 5 = 15 (left: 9 15) 15 + 9 = 24 (left: 24) Answer: ((5 + 5) + 5) + 9 = 24 Input: 5 5 4 3
回答：
Steps: 5 * 5 = 25 (left: 3 4 25) 25 - 4 = 21 (left: 3 21) 21 + 3 = 24 (left: 24) Answer: (5 * 5 - 4) + 3 = 24
正解している。
これは簡単な例で、頭から順に数字を使っていけばよい。
少し難しくしてみる。
Input: 2 6 4 3
回答：
Steps: 6 / 2 = 3 (left: 3 3 4) 3 * 3 = 9 (left: 4 9) 4 * 9 = 36 (left: 36) Unfortunately, it is not possible to get 24 from 36 using only one number and basic arithmetic operations.
今度は解けなかった。
提案手法
このゲームは、3手の先読みをするゲーム木探索で回答することができる。
提案手法では、LLMでゲーム木の各ノードの枝の候補の生成と、展開されたノードの評価をLLMで行い、終端ノードで正しく回答ができたかをLLM自身で評価する。
BFSの手法で各ステップで5つまで枝を残してゲーム木探索を行うことで回答を得る。
温度0.7で複数回サンプリングを行い、平均的なパフォーマンスで評価した結果、既存手法を大幅に上回る結果が得られた。
枝の候補を生成するプロンプト
枝の候補は以下のようなプロンプトで生成する。
Input: 2 8 8 14 Possible next steps: 2 + 8 = 10 (left: 8 10 14) 8 / 2 = 4 (left: 4 8 14) 14 + 2 = 16 (left: 8 8 16) 2 * 8 = 16 (left: 8 14 16) 8 - 2 = 6 (left: 6 8 14) 14 - 8 = 6 (left: 2 6 8) 14 / 2 = 7 (left: 7 8 8) 14 - 2 = 12 (left: 8 8 12) Input: 5 5 4 3 Possible next steps:
出力：
5 + 5 = 10 (left: 10 4 3) 5 - 5 = 0 (left: 0 4 3) 5 * 5 = 25 (left: 25 4 3) 5 / 5 = 1 (left: 1 4 3) 4 + 5 = 9 (left: 9 5 3) 4 - 5 = -1 (left: -1 5 3) 4 * 5 = 20 (left: 20 5 3) 4 / 5 = 0.8 (left: 0.8 5 3) 3 + 5 = 8 (left: 8 5 4) 3 - 5 = -2 (left: -2 5 4) 3 * 5 = 15 (left: 15 5 4) 3 / 5 = 0.6 (left: 0.6 5 4)
ノードを評価するプロンプト
ノードは以下のようなプロンプトで3段階(sure/likely/impossible)で評価する。
Evaluate if given numbers can reach 24 (sure/likely/impossible) 10 14 10 + 14 = 24 sure 11 12 11 + 12 = 23 12 - 11 = 1 11 * 12 = 132 11 / 12 = 0.91 impossible 4 4 10 4 + 4 + 10 = 8 + 10 = 18 4 * 10 - 4 = 40 - 4 = 36 (10 - 4) * 4 = 6 * 4 = 24 sure 4 9 11 9 + 11 + 4 = 20 + 4 = 24 sure 5 7 8 5 + 7 + 8 = 12 + 8 = 20 (8 - 5) * 7 = 3 * 7 = 21 I cannot obtain 24 now, but numbers are within a reasonable range likely 5 6 6 5 + 6 + 6 = 17 (6 - 5) * 6 = 1 * 6 = 6 I cannot obtain 24 now, but numbers are within a reasonable range likely 10 10 11 10 + 10 + 11 = 31 (11 - 10) * 10 = 10 10 10 10 are all too big impossible 1 3 3 1 * 3 * 3 = 9 (1 + 3) * 3 = 12 1 3 3 are all too small impossible 25 2 4
出力：
25 + 2 + 4 = 31 (25 - 2) * 4 = 23 * 4 = 92 2 * 4 = 8, but adding or subtracting 8 to/from 25 does not reach 24 However, 25 - 2 / 4 = 25 - 0.5 = 24.5 is within a reasonable range likely
終端ノードを評価するプロンプト
Use numbers and basic arithmetic operations (+ - * /) to obtain 24. Given an input and an answer, give a judgement (sure/impossible) if the answer is correct, i.e. it uses each input exactly once and no other numbers, and reach 24. Input: 4 4 6 8 Answer: (4 + 8) * (6 - 4) = 24 Judge: sure Input: 2 9 10 12 Answer: 2 * 12 * (10 - 9) = 24 Judge: sure Input: 4 9 10 13 Answer: (13 - 9) * (10 - 4) = 24 Judge: sure Input: 4 4 6 8 Answer: (4 + 8) * (6 - 4) + 1 = 25 Judge: impossible Input: 2 9 10 12 Answer: 2 * (12 - 10) = 24 Judge: impossible Input: 4 9 10 13 Answer: (13 - 4) * (10 - 9) = 24 Judge: impossible Input: 5 5 4 3 Answer: (5 - 3) * (5 + 4) = 24 Judge:
出力：
sure
試した例だと、間違った結果が出力された。
他の例だと上手くいった。
Input: 2 6 4 3 Answer: (6 - 4) * (2 + 3) = 24 Judge:
出力：
impossible
Input: 2 6 4 3 Answer: (6 * 4) * (3 - 2) = 24 Judge:
出力：
sure
この例「2 6 4 3」は、上記で単一のプロンプトでは解けなかったが、終端ノードが正しく評価できているので、ToTの手法では解けそうである。
論文では、他にも、「4つの文から文章を生成するタスク」と「ミニクロスワード」のタスクでも効果があったと報告している。
まとめ
LLMは論理的な思考が苦手であったが、ToTの手法によりヒューリステックな探索が必要なタスクでも解ける可能性が示された。
思考ゲームのようなタスクは、既存のアルゴリズムで超人的なパフォーマンスが達成できているので、わざわざLLMに解かせる必要はないが、より複雑な現実世界のタスク（コーディング、データ分析、ロボティクスなど）で、LLMを活用してパフォーマンスを向上できる可能性がある。
この手法は、枝の生成と評価に人間が設計したプロンプトが必要で、ゲーム木の探索もLLMの外側で実装が必要なため、将来的にはLLM自体で解決して欲しい課題である。
