思考のツリー：システム2の概念をLLMに取り込み、CoTベースのGPT-4よりもさらに強力に
3つの要点
✔️ Yoshua Bengioらが求めてきたシステム２の概念に触発され、探索、戦略的先読み、自己評価がLLMに組み込まれました
✔️ CoT (思考の連鎖）に対して、ToT（思考のツリー）により複数の選択肢から探索を行い、GPT-4に困難な課題に対しても超越した性能を示しています
✔️ 商用のLLMと組み合わせることができるとしており、複雑なシステムとしては計算コストが低く、応用が広がる可能性を秘めています
Tree of Thoughts:Deliberate Problem Solving with Large Language Models
written by Shunyu Yao,Dian Yu,Jeffrey Zhao,Izhak Shafran,Thomas L. Griffiths,Yuan Cao,Karthik Narasimhan
(Submitted on 17 May 2023)
Comments: Code repo with all prompts: this https URL
Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
code：
本記事で使用している画像は論文中のもの、紹介スライドのもの、またはそれを参考に作成したものを使用しております。
概要
ChatGPT(GPT-3.5, GPT-4)などのLLMが、オペレータの意図を組んだ、あたかも（豊富に知識を持った）人間が回答しているかのような回答をできるようになった理由の一つとして、LLMモデルがあるレベルを超えて大規模になると思考の連鎖(CoT : Chain of Thoughts)を理解できるようになったということが分析されています。さらに、モデルへの指示に思考の連鎖を含めることにより、より望ましい回答が得られます（プロンプトエンジニアリング）。プロンプトエンジニアリングについて、数多くの発表や研究があり、それらのサーベイも発行されています。
本論文では、NLPにより人間に近い推論を行わせるために思考の連鎖が実現しているシステム１機能に、システム２処理を加えようとしています。具体的には、探索、戦略的先読み、自己評価を通じて意図的な問題解決を可能にすることで、言語モデルの能力を拡張するTree of Thoughts (ToT)というフレームワークを紹介します。これにより、言語モデルは複数の推論経路を考慮し、グローバルな選択を行い、必要に応じてバックトラックを行うことができ、２４のゲーム、クリエイティブライティング、ミニクロスワードなどのタスクにおいて問題解決能力を向上させることができました。
はじめに
GPTやPalMなどの言語モデル（LM）はトークンレベルの決定を1つずつ左から右に行う、テキスト生成の自己回帰メカニズムに基づいています。この論文では、このような単純なメカニズムが一般的な問題解決者向けにLMを構築するのに十分かどうか、そしてどのような問題が現在のパラダイムに挑戦するのかという疑問を提起しています。この論文では、これらの質問に答える手がかりとして、人間の認知に関する文献を調べています。
人間の認知に研究において、二重過程理論は、人が意思決定に関わる際に、高速で自動的な無意識のモード（「システム1」）と、低速で意図的な意識のモード（「システム2」）の2つのモードがあることを示唆しています。この2つのモードは、これまでにも機械学習で使われるさまざまな数学的モデルと結びつけられてきました。（Yoshua BengioによるNIPS2019での基調講演も有名です）例えば、人間や他の動物の強化学習に関する研究では、連想的な「モデルフリー」学習や、より熟慮的な「モデルベース」計画に取り組む状況が探られてきました。LMの単純な連想によるトークンレベルの選択は「システム1」を彷彿とさせるため、（1）現在の選択肢をただ選ぶのではなく、多様な選択肢を維持・探索し、（2）現在の状況を評価し、よりグローバルな決定を行うために積極的に先を見たり後戻りしたりする、より熟考された「システム2」計画プロセスによって補強することで利点があるだろうと考えました。
| システム1 | システム2 |
| 直観的 | 内省的 |
| 速い | 遅い |
| 無意識的 | 意識的 |
| バイアスがある反応 | 規範的反応 |
| 文脈的 | 抽象的 |
| 自動的 | 制御的 |
| 連想的 | ルール基盤的 |
| 経験則的 | 帰結主義的 |
このような計画プロセスを設計するために、人工知能（および認知科学）の起源に戻り、1950年代からNewell、Shaw、Simonが探求した計画プロセスからインスピレーションを得ました。Newellたちは、問題解決を、木として表現された組合せ問題空間の探索として特徴付けました。そこで著者たちは、言語モデルによる一般的な問題解決のためのTree of Thoughts (ToT)フレームワークを提案します。Fig.1が示すように、既存の方法が問題解決のために連続的な言語シーケンスをサンプリングするのに対し、ToTは積極的に思考の木を維持し、各思考は問題解決への中間段階として機能する首尾一貫した言語シーケンスとなります（Table 1）。このような高レベルの意味単位により、LMは、言語でもインスタンス化される意図的な推論プロセスを通じて、異なる中間思考が問題解決に向けてどのように進んでいるかを自己評価することができます（Fig. 2、4、6）。このように、LMの自己評価と熟考を通じた検索発見法（ヒューリスティック）の実装は、これまでの検索発見法はプログラムか学習によるものであったのに比べ、斬新です。最後に、この言語ベースの多様な思考の生成・評価機能を、幅優先探索（BFS）や深さ優先探索（DFS）などの探索アルゴリズムと組み合わせ、ルックアヘッドやバックトラックを用いて思考の木を系統的に探索することを可能にします。
評価用に、経験的には、最先端の言語モデルであるGPT-4を含む、既存のLM推論手法でも難しい3つの新問題（24のゲーム、クリエイティブ・ライティング、クロスワード）を提案します（Table 1）。これらの課題では、演繹的、数学的、常識的、語彙的な推論能力、そして体系的な計画や探索を取り入れる方法が必要とされます。
ToTはこれらのタスクにおける言語モデルの問題解決能力を大幅に高めることが示されました。著者らはまた、さまざまな選択肢が体系的な切り分けを通じてモデルのパフォーマンスにどのように影響するかを分析し、言語モデルをより適切にトレーニングして使用するための将来の方向性についても議論しました。
背景
まず、大規模な言語モデルを問題解決に利用する既存の手法をいくつかあげます。
入力-出力(IO)プロンプトは、入力xを出力yに変換する最も一般的な方法です: y ∼ pθ(y|promptIO(x)), promptIO(x) は入力xにタスク指示や入出力例の数ショットでラップします。簡単のため、pprompt θ (output | input) = pθ(output | prompt(input)) とし、IOプロンプトは y ∼ pIO θ (y|x) と定式化できるようにします。
思考の連鎖（CoT）プロンプト は、入力xから出力yへのマッピングが自明でない場合（例えば、xが数学の質問で、yが最終的な数値の答えの場合）に対処するために提案されました。重要なアイデアは、xとyを橋渡しする思考の連鎖z1, - - , znを導入することであり、各ziは問題解決に向けた意味のある中間ステップとして機能する首尾一貫した言語シーケンスです（例えば、ziは数学QAの中間方程式となりえます）。CoTで問題を解くには、各思考zi ∼ pCoT θ (zi | x, z1---i-1) を順次サンプリングし、次に出力y ∼ pCoT θ (y|x, z1---n) をサンプリングします。実際には、[z1--n, y] ∼ pCoT θ (z1---n, y|x) は連続した言語シーケンスとしてサンプリングされ、思考の分解（例えば、各ziがフレーズなのか、文なのか、パラグラフなのか）は曖昧なままになります。
CoT-SC (CoTとの自己整合) は、k個の独立同一分布する思考の連鎖をサンプリングするアンサンブルアプローチです： [z(i) 1---n, y(i)] ∼ pCoT θ (z1---n, y|x) (i = 1 - - k), そして最も頻度の高い出力： arg maxy #{i | y(i) = y}を返します。CoT-SCはCoTを改善します。なぜなら、同じ問題に対して一般的に異なる思考過程があり（例えば、同じ定理を証明する異なる方法）、より豊富な思考セットを探索することによって、出力決定をより忠実にすることができるからです。しかし、各チェーン内では、異なる思考ステップを局所的に探索することはできず、「最頻値」発見法は、出力空間が限られている場合にのみ適用されます（例：多肢選択式のQA）。
思考の木： LMによる意図的な問題解決
強調表示されたテキストを理解するには、体系的な計画や検索の概念を理解することが重要です。体系的な計画では、複雑な問題をより小さく管理しやすい部分に分解し、各部分を論理的かつ組織的に解決するための計画を立てます。検索アルゴリズムを使用して、問題領域を探索し、最適なソリューションを見つけます。言語モデルの文脈では、体系的な計画や検索では、モデルを使用して問題に対して考えられるさまざまな解決策を生成および評価します。
1. 思考の分解 CoTが明示的な分解をせずに思考をまとまった形でサンプリングするのに対し、ToTは問題特性を活用して中間的な思考ステップを設計・分解します。Table 1に示すように、問題によっては、思考は数個の単語（クロスワード）、数式の行（24ゲーム）、文章案の段落全体（クリエイティブ・ライティング）になることがあります。一般的に、思考は、LMが有望で多様なサンプルを生成できるように「小さく」、かつ問題解決への見通しを評価できるように「大きく」する必要があります（例えば、1冊の本を生成することは、通常「大きく」てまとまりがありません）。
2. 思考生成器G(pθ, s, k) 木状態s = [x, z1---i] が与えられたとき、次の思考ステップのためのk個の候補を生成する2つの戦略を考える：
(a) CoTプロンプトから独立同一分布思考のサンプル (Creative Writing, Fig. 4)： z(j) ∼ pCoT θ (zi+1|s) = pCoT θ (zi+1|x, z1---i) (j = 1 - - k). これは、思考空間が豊かな場合（例えば、各思考が段落になっている場合）、独立同一分布サンプルが多様性につながります。
(b) "propose prompt "を使って思考を順次提案する（Game of 24, Figure 2; Crosswords, Figure 6）： [z(1), - - , z(k)] ∼ ppropose θ (z(1---k) i+1 | s). この方法は、思考空間がより制約されている場合（例えば、各思考が単語や行だけである場合）、同じ文脈で異なる思考を提案することで重複を避けることができるので、より効果的です。
3. 状態評価器V (pθ, S) 異なる状態のフロンティアが与えられたとき、状態評価器は問題解決に向けたそれらの進捗を評価し、どの状態をどの順番で探索し続けるかを決定するための探索アルゴリズムの発見法として機能します。発見法は、探索問題を解決するための標準的なアプローチですが、一般的には、プログラムによるもの（DeepBlueなど）か、学習によるもの（AlphaGoなど）のいずれかです。著者らは、LM を用いて意図的に状態を推論することで、第3の選択肢を提案しています。このような意図的な発見法が適用できる場合、プログラムされたルールよりも柔軟であり、学習されたモデルよりもサンプル効率が良くなります。思考生成器と同様に、状態を独立に、あるいは一緒に評価する2つの戦略を考えます：
(a) 各状態を独立に評価する： V (pθ, S)(s) ∼ pvalue θ (v|s) ∀s∈S ここで、値プロンプトは、スカラー値v（例えば1-10）または発見法的に値に変えることができる分類（例えば確実/可能/不可能）を生成するために状態sについての理由を説明します。このような評価推論の根拠は、問題や思考ステップによって異なることがあります。この研究では、少数の先読みシミュレーション（例えば、5 + 5 + 14で5, 5, 14が24に達することを素早く確認する、あるいは" "の" "を埋めることで「hot l」が「inn」の意味になるなど）と常識（例えば、1 2 3が小さすぎて24にはならない、あるいは「tzxc」から始まる単語はない）を使って評価を探求しています。前者は「良い」状態を促進するかもしれないが、後者は「悪い」状態を排除するのに役立つかもしれません。このような評価は完璧である必要はなく、おおよそであればよいです。
(b)状態をまたいで投票する： V (pθ, S)(s) = 1[s = s∗] ここで、「良い」状態s* ∼ pvote θ (s∗|S) は、投票プロンプトでS内の異なる状態を意図的に比較した上で、投票されます。問題の成功を直接評価するのが難しい場合（例えば通路のまとまり）、代わりに異なる部分解を比較し、最も有望なものに投票するのが自然です。つまり、「どの状態を探索するか」を多肢選択式のQAとし、LMサンプルを使って投票します。
どちらの戦略でも、LMを複数回促して値を集計したり、投票結果で時間/リソース/コストをより忠実/ロバストな発見法と入れ替えたりすることができます。
4. 検索アルゴリズム 最後に、ToTフレームワークでは、木構造に応じて様々な検索アルゴリズムをプラグアンドプレイすることができます。
(a) 幅優先探索 (BFS) （アルゴリズム1）は、ステップごとに最も有望なb個の状態のセットを維持します。これは、木の深さが制限される24のゲームやクリエイティブライティングに用いられ（T≦3）、初期思考ステップを評価し、小さな集合に刈り込むことができます（b≦5）。
(b) 深さ優先探索（DFS）（アルゴリズム2）は、最終出力に達するまで（t > T ）、あるいは状態評価者が現在のsから問題を解くことは不可能と判断するまで（V (pθ, {s})(s) ≦ vth for a value threshold vth）最も有望な状態を先に探索します。後者の場合、sからのサブツリーは、探索と利用を交換するために刈り込まれます。どちらの場合も、DFSはsの親状態にバックトラックして探索を継続します。
ToT フレームワークは、思考ツリーを管理することで、体系的な計画や検索をサポートするように設計されています。各思考は、問題解決への中間ステップとして機能する首尾一貫した言語シーケンスです。LMは、言語でもインスタンス化される意図的な推論プロセスを通じて、さまざまな中間思考が問題解決に向けてどのように進んでいるかを自己評価できます。これにより、LMは複数の異なる推論経路を検討し、選択を自己評価して次の行動方針を決定できます。また、必要に応じて先を見据えたり、後戻りしたりして、グローバルな選択を行うことができます。
概念的には、ToTはLMを用いた一般的な問題解決のための手法として、以下のような利点があります：
(1) 一般性 IO、CoT、CoT-SC、self-refinementはToTの特殊なケースと見なすことができる（つまり、深さと幅が限定されたツリー；Fig. 1）。
(2) モジュラリティ ベースとなるLMをはじめ、思考分解、生成、評価、探索の各手順を独立して変化させることができる。
(3) 適応性 問題特性、LMの能力、リソース制約の違いに対応できる。
(4) 利便性 余分な訓練は必要なく、あらかじめ訓練されたLMがあれば十分である。
つまり、ToTは柔軟性があり、さまざまなレベルの思考、思考の生成と評価の方法、さまざまな問題の性質に特化した検索アルゴリズムにも適応できると述べています。すなわち、フレームワークをさまざまなタスクや問題のニーズに合わせてカスタマイズできます。
実験
標準的なIOプロンプトやCoTプロンプトを用いて、最先端の言語モデルGPT-4からサンプリングしても困難な3つのタスクを提案します。
24のゲーム
24のゲームは、4つの数字と基本的な算術演算（+-*/）を使って24を得ることを目的とした数学的推論課題です。例えば、「4 9 10 13」という入力があった場合、「(10 - 4) * (13 - 9) = 24」という解答を出力することができます。
タスクのセットアップ 4nums.comからデータをスクレイピングし、人間の解答時間によって簡単なものから難しいものまで分類された1,362のゲームを持ち、テストには901-1,000のインデックスを持つ比較的難しいゲームのサブセットを使用します。各タスクについて、出力が24に等しい有効な方程式であり、入力された数字をそれぞれ正確に1回ずつ使用する場合に成功と見なします。100ゲームにわたる成功率を指標とします。
ベースライン 標準的な入出力（IO）プロンプトを使用し、5つのインコンテキストの例を使用しました。思考の連鎖（CoT）プロンプトでは、各入出力ペアを3つの中間方程式で補強し、それぞれが残りの2つの数字で操作します。例えば、「4 9 10 13」という入力があった場合、「13 - 9 = 4（左：4 4 10）、10 - 4 = 6（左：4 6）、4 * 6 = 24（左：24）」という思考が可能です。各ゲームについて、IOとCoTのプロンプトを100回分サンプリングし、平均的なパフォーマンスを確認します。また、100回のCoTサンプルから多数派の出力を取るCoT自己整合性ベースラインと、最大10回のIOサンプルの上に反復精錬アプローチを検討します。各反復において、LMは、出力が正しくない場合、「間違いを反省し、洗練された答えを生成する」ように、以前のすべての履歴を条件とします。
ToTのセットアップ Game of 24をToTに組み入れるには、思考を3つのステップに分解し、それぞれを中間方程式とすることが自然です。Fig. 2(a)に示すように、各ツリーノードにおいて、「左」の数字を正確に表示し、LMに次のステップの可能性を提案するよう促します。同じ「提案プロンプト」が3つの思考ステップすべてに使用されていますが、入力数が4つの例は1つだけです。ToTでは幅優先探索（BFS）を行い、各ステップで最良のb = 5個の候補を残します。Fig. 2(b)に示すように、ToTで意図的なBFSを行うために、LMに各思考候補を24に達するかどうかを「確実/可能/不可能」で評価するように促します。その目的は、数回の先行試行で検証できる正しい部分解を促進し、「大きすぎる/小さすぎる」常識に基づく不可能な部分解を排除し、残りを「たぶん」にすることです。各思考に対して3回ずつ値をサンプリングします。
結果 Table2に示すように、IO、CoT、CoT-SCプロンプト手法は、このタスクにおいて、成功率7.3%、4.0%、9.0%しか達成できず、悪い結果を出しました。一方、b = 1の幅を持つToTはすでに45%の成功率を達成し、b = 5は74%を達成しています。また、kサンプル（1≦k≦100）のベストを使用して成功率を計算することにより、IO/CoTの神託設定を検討します。IO/CoT (best of k)とToTを比較するために、b = 1 - - - 5にわたってToTのタスクごとに訪問したツリーノードを計算し、Fig. 3（a）の5つの成功率をマッピングすることを検討します。驚くことではないが、CoTはIOよりもスケールが大きく、100個のCoTサンプルのベストは49％の成功率を達成したが、それでもToT（b > 1）でより多くのノードを探索するよりもはるかに悪いです。
エラー解析 Fig. 3（b）は、CoTおよびToTサンプルがどのステップでタスクに失敗したか、すなわち、思考（CoTにおいて）またはすべてのb個の思考（ToTにおいて）が無効または24に到達することが不可能であるかを分解しています。注目すべきは、CoTサンプルの約60%が、最初のステップ、つまり最初の3つの単語（例：「4 + 9」）を生成した時点で、すでにタスクに失敗していることです。これは、左から右への直接的なデコードの問題点を浮き彫りにしています。
クリエイティブ・ライティング
次の課題は、入力は4つのランダムな文であり、出力は4つの入力文でそれぞれ終わる4つの段落からなる首尾一貫した文章でなければならない創造的なライティングタスクです。このようなタスクはオープンエンドで探索的であり、創造的思考だけでなく高度な計画性も問われます。
タスクの設定 randomwordgenerator.comからランダムな文章をサンプリングして100個の入力を形成します。各入力制約に対するgroundtruth passageは存在しません。GPT-4はほとんどの場合、入力制約に従うことができることがわかったので、著者らは、GPT-4のゼロショットプロンプトを使って1-10のスカラースコアを提供する方法と、人間の判断を使って異なる方法からの出力のペアを比較する方法の2つの方法で、文章の一貫性を評価することに焦点を当てました。前者では、各タスクの出力について5つのスコアをサンプリングし、それらを平均化します。この5つのスコアは、出力全体の平均で標準偏差が約0.56と、通常一貫していることがわかります。後者については、著者の一部を盲検化し、100個の入力に対してパッセージの順序をランダムに反転させたCoTとToTの生成ペアの首尾一貫性を比較しました。
ベースライン タスクの創造的な性質を考慮し、IOとCoTのプロンプトはどちらもゼロショットです。前者は、入力制約がある中で、首尾一貫した文章を直接生成するよう促すのに対し、後者は、まず簡単な計画を立ててから文章を書くよう促す、つまり、計画が中間思考ステップとなります。1つのタスクにつき、10個のIOとCoTのサンプルを生成します。この場合、LMは入力制約と最後に生成された文章を条件として、その文章がすでに「完全に首尾一貫した」ものであるかどうかを判断し、そうでない場合は洗練されたものを生成します。
ToTの設定 LMはまずk = 5のプランを生成し、最も良いものに投票し（Fig. 4）、次に同様に最良のプランに基づいてk = 5のパッセージを生成し、最も良いものに投票します。ここでは、1ステップにつき1つの選択肢しか保持されないため、幅の制限b = 1としました。単純なゼロショット投票プロンプト（「以下の選択肢を分析し、どれがインストラクションにとって最も有望かを結論づける」）を用いて、両方のステップで5票をサンプリングしています。
結果 Fig. 5(a)は100のタスクのGPT-4スコアの平均値で、ToT（7.56）はIO（6.19）やCoT（6.93）よりもまとまりのある文章を生成すると判断されたことを示しています。このような自動測定はノイズが多いかもしれませんが、Fig. 5(b)は、人間が100のパッセージペアのうち41でCoTよりToTを好む一方、21でToTよりCoTを好む（他の38ペアは「同様に一貫」と判断）ことを示し、この結果を裏付けています。最後に、反復精錬はこの自然言語タスクにおいてより効果的であり、IO一貫性スコアを6.19から7.67に、ToT一貫性スコアを7.56から7.91に向上させることができました。ToTフレームワークにおける思考生成の第3のアプローチとして、独立同一分布や逐次生成ではなく、古い思考を洗練することで新しい思考が生まれると考えることができると考えています。
ミニクロスワード
24のゲームやクリエイティブ・ライティングでは、ToTは比較的浅く、最終的なアウトプットに到達するまでにせいぜい3回の思考ステップが必要でした。ここでは、より難しい自然言語による検索問題として、5×5のミニクロスワードを検討します。一般的なクロスワードは、LMの代わりに大規模検索を活用した特殊なNLPパイプラインで容易に解決できるため、ここでも単にタスクを解決することが目的ではありません。むしろ、LMが自らの思考を探求し、発見法として意図的な推論を行いながら自らの探求を導く一般的な問題解決者としての限界を探ることを目的としています。
タスクのセットアップ GooBixから、5×5のミニクロスワード156ゲームのデータを取得しました。隣接するゲームには似たようなヒントが含まれていることが分かっているので、テスト用にはインデックスが1, 6, - - , 91, 96の20ゲーム、プロンプティング用には136, 141, 146, 151, 156のゲームを使用することにしました。各タスクにおいて、入力は5つの水平方向の手がかりと5つの垂直方向の手がかりを記述し、出力はクロスワードを解くための5×5＝25文字のボードとします。評価については、正しい文字の部分（1ゲーム25個）、単語（1ゲーム10個）、ゲームという3つの成功レベルを考慮します。
ベースライン IOプロンプトでは5つの入出力ペアを例示し、CoTプロンプトではさらにh1...5→v1...5の順で中間単語を追加しました。各プロンプトを10サンプルずつ実行し、結果を平均化しました。
ToTのセットアップ 深さ優先探索（アルゴリズム2）を活用し、最も有望な後続語の手がかりを、その状態が有望でなくなるまで探索し続け、その後、親状態にバックトラックして代替案を探索します。探索を容易にするため、後続の思考は充填された単語や文字を変更しないよう制約されており、ToTの中間ステップは最大で10個となる。思考生成では、各状態で既存の思考（例えばFig.6(a)の状態では「h2.motor; h1.task」）を残りの手がかりの文字制約に変換し（例えば「v1.To heap: tm ;...」）、次の単語の場所と内容を埋める候補を思いつくよう提案プロンプトを5度出します。重要なのは、LMが異なる考えに対して信頼度を与えるよう促し、これらをプロポーザル間で集約して、次に探索すべき考えのソートリストを得ることである（Fig.6（a））。状態の評価については、同様に各状態を残りの手がかりの文字制約に変換し、制約が与えられた場合に充填が可能かどうかを手がかりごとに評価します。残りのヒントが「埋められない」と判断された場合（例：「v1. To heap: tm s」）、その状態のサブツリーの探索は刈り込まれ、DFSはその親にバックトラックして次の有望な思考を探索します。DFSの探索ステップを100に制限し、最も深く探索された状態（複数の場合は最初に探索された状態）を最終出力にレンダリングするだけです。
結果 Table3に示すように、IOとCoTプロンプトの方法は、単語レベルの成功率が16%未満とパフォーマンスが低いのに対し、ToTはすべての指標を大幅に改善し、単語レベルの成功率60%を達成し、20ゲーム中4ゲームを解決しました。IOとCoTには、異なる手がかりを試したり、決定を変更したり、後戻りしたりするメカニズムがないことを考えると、このような改善は驚くべきことではありません。
神託と切り分けの研究 タスクごとに神託（オラクル）のベストDFS状態（発見法的に決定したベスト状態ではなく）から出力した場合、ToTのパフォーマンスはさらに高く、実際に7/20ゲームを解決しています（Table 3、「+ベスト状態」）。このことは、本論文の単純な出力発見法は容易に改善できることを示しています。興味深いことに、クロスワードゲームを実際に解いたときに、状態評価器がいくつかの単語を「不可能」と判断して枝刈りすることがあります。おそらく、5×5のクロスワードには、GPT-4が認識できない珍しい単語や廃語が設計上あるためです。プルーニングの発見法としての状態評価は不完全であるため、プルーニングの無効化も検討したが、一般的に性能が低下することがわかりました（Table 3、"-prune"）。しかし、実際には4/20のゲームで正しい解を見つけることができ（ただし、発見法による出力は1のみ）、そのうち3つはToT+プルーニングでは100ステップ以内に解けないゲームです。このように、DFSプルーニングの発見法を改善することは、このケースの問題解決に不可欠です。最後に、最大20ステップの間、最も有望な手がかりを埋め続ける切り分けを実行し、上書きを許可することで、バックトラックの重要性を確認しました。これは、幅の制限をb = 1とした「貪欲な」BFS探索に似ており、単語レベルの成功率が20%しかなく、パフォーマンスが悪かったです（Table 3、「-backtrack」）。
まとめ
限界と今後の方向性
GPT-4が既に得意とする多くのタスクでは、ToTのような意図的な探索は必要ないかもしれません。初期段階として、この研究ではGPT-4に挑戦し、LMに組み込まれたより優れた探索・計画能力を求める3つの比較的単純なタスクのみを探索しました。しかし、より現実的な意思決定アプリケーション（コーディング、データ解析、ロボット工学など）にLMを導入し始めると、より複雑なタスクが出現し、これらの研究課題を研究する新しい機会を提供する可能性があります。また、ToTのような探索手法は、タスクのパフォーマンスを向上させるために、サンプリング手法よりも多くのリソース（GPT-4 APIコストなど）を必要としますが、ToTのモジュール的な柔軟性は、ユーザーがパフォーマンスとコストのトレードオフをカスタマイズできるようにし、現在進行中のオープンソースの取り組みは、近い将来にこのコストを容易に削減できるはずです。最後に、この研究は、市販のLMを使用することに焦点を当てており、ToTスタイルの高レベルの反事実的意思決定（例えば、次のトークンを予測するのではなく、次のパラグラフの潜在的な選択肢について熟考する）を使用してLMを微調整することは、LMの問題解決能力を強化する機会を提供するかもしれません。
より広範な影響
ToTは、LMがより自律的かつインテリジェントに意思決定や問題解決を行えるようにするフレームワークです。現在のタスクは推論や探索問題に限られていますが、外部環境や人間との相互作用を伴う将来のアプリケーションは、LMsの有害な利用を促進するなど、潜在的な危険をもたらす可能性があります。一方、ToTはまた、結果として得られる表現が暗黙の低レベルのトークン値ではなく、読みやすい高レベルの言語推論であるため、モデル決定の解釈可能性と人間による調整の機会を改善するでしょう。
結論
LMの連想的な「システム1」は、問題解決への可能なパスのツリー検索に基づく「システム2」によって有益に補強することができます。思考の木」フレームワークは、問題解決に関する古典的な洞察を、現代のLMのための実用的な手法に変換する方法を提供するものです。同時に、LMはこれらの古典的な方法の弱点に対処し、創作活動のように容易に形式化できない複雑な問題を解決する方法を提供します。著者らは、このようにLMと古典的なAIアプローチとの交差を、今後の研究のエキサイティングな方向性としています。
この記事に関するカテゴリー
