AoT論文
https://scrapbox.io/files/65a338c67ff2fd002b359ad0.png
論文情報
タイトル：Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models
発行日：2023年8月
著者：Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Ruoxi Jia, Ming Jin
所属：Virginia Tech
論文を読んで感じたこと
ToTやself-consisencyは、お金かかって、遅延して大変。消費電力を悪化させ、環境にも悪い。
そこで、このアプローチを考えたと、かなり現実的な発想
CoTの推論でたまにミスが出るのは、LLMが計算を必ずミスっているというわけではない...！
LLMは、プロンプト内の質問の条件と近い例示に、引っ張られることが原因かも
正しい推論が文脈に存在するだけで、算数の計算の精度が落ちている(Figure 3)
有効な推論と無効な推論の両方をfew-shotで示すことで、LLMの推論の精度を向上させる
AoTのアルゴリズムの選択は、DFSがいいみたい
https://scrapbox.io/files/65a8a545bc23bf0023b8e6f4.png
Limitationで、AoTの実施にはGPT-4が必要不可欠と書いてある 実際に使うにはどうする？
無課金ChatGPTには取りにくい戦略
API使うこと必須
code:python
dfs = AoT(
num_thoughts=2,
max_steps=10,
value_threshold=1,
initial_prompt=task,
# 以下にOpenAIのAPIkeyを入力してください
openai_api_key=""
)
result = dfs.solve()
print(result)
普段使いは難しい
概要
現在の文献では、CoT (Chain-of-Thought)アプローチを超えることを目指して、生成プロセスを停止させ、修正し、再開する外部の手法をしばしば採用しており、これにより大規模言語モデル（LLM）の推論能力が向上しています。このモードはクエリの数を増やし、コスト、メモリ、計算オーバーヘッドを増加させます。これに対処するため、我々はアルゴリズム思考法という新しい戦略を提案します。これは、LLMをアルゴリズム推論の道へと進めるもので、ICL(コンテキスト内学習: In Context Learning)の新しいモードを開拓します。アルゴリズムの例を用いることで、LLMの固有の反復ダイナミクスを利用し、わずか1回または数回のクエリでアイデア探索を拡大します。我々の技術は以前の単一クエリ手法を上回り、広範なツリー検索アルゴリズムを用いる最近のマルチクエリ戦略と同等です。興味深いことに、我々の結果は、アルゴリズムを用いてLLMを指導することで、アルゴリズム自体の性能を超える可能性があることを示唆しており、LLMがその直感を最適化された検索に織り込む固有の能力を持っていることを示唆しています。我々は、我々の方法の効果とその応用におけるニュアンスについて探求します。 はじめに
大規模言語モデルの最近の発展は、一般的な問題解決、コード生成、指示に従う能力での効果を浮き彫りにしています。初期のモデルは直接的な答えの戦略に依存していましたが、現代の研究は問題をサブタスクに分割して解決策を見つけるための線形推論パスに向かっているか、コンテキストを変更することでトークン生成を変更する外部メカニズムを活用しています。
人間の認知に類似して、初期のLLM戦略は衝動的な意思決定が特徴の瞬間的なシステム1を模倣しているように見えます。対照的に、CoT (Chain-of-Thought)やLeast to Mostなど、より最近の方法論は、システム2の内省的な性質を反映しています。特に、中間推論ステップの統合は、算数推論タスクの改善に寄与しています（Srivastava et al. 2022; Liang et al. 2022）。 しかし、より深い計画や広範な思考の探求にタスクが移行するにつれて、これらの方法は制限的に見えます。CoTとSelf-Consistencyを組み合わせた手法は複数のLLM出力を合意形成に利用しますが、詳細な評価の欠如がモデルの誤方向への導きにつながる可能性があります。ToT (Tree of Thoughts)は顕著な解決策として登場します。一方のLLMがアイデア生成に専念する一方で、別のLLMがこれらのアイデアの価値を評価し、停止-評価-再開のサイクルを経ています。この反復プロセスは、ツリー検索によって確立され、特に継続の範囲が広いタスクにおいて顕著な効果を示しています。この進歩は、人間が作業記憶の限界を回避するためにツールを使用することに似ており、LLMに外部の拡張を提供しています。 しかし、この強化されたLLMアプローチには落とし穴もあります。特に目立つ欠点は、クエリの数と計算要求の大幅な増加です。GPT-4などのオンラインLLM APIへの各クエリは金銭的な費用がかかるだけでなく、特にリアルタイムアプリケーションで重要な遅延にも寄与します。これらのクエリから生じる累積遅延は、解決策の効率を損なう可能性があります。インフラ面では、連続したやり取りがシステムに負荷をかけ、帯域幅の制約やモデルの利用可能性の低下につながる可能性があります。さらに、環境への影響も無視できません。絶え間ないクエリは、既に電力を多く消費しているデータセンターのエネルギー消費をさらに増加させ、炭素足跡を悪化させます。
これを念頭に置いて、私たちの目標は、世界知識の巧みな使用を必要とするタスクにおいて、現代のマルチクエリ推論方法によって使用されるクエリ数を劇的に削減し、性能を維持しながら、より責任あるかつ熟練したAIリソースの使用に向けて舵を取ることです。
LLMがシステム1からシステム2へと進化する過程を振り返ると、重要な要素が浮かび上がります：アルゴリズム。その方法論的な性質により、アルゴリズム的視点は、問題となる空間を熱心に探索し、戦略を実行し、解決策を策定する道を提供します。現在の文献の多くはLLM外部のアルゴリズムとして扱っていますが、LLMの固有の生成的反復を考えると、この反復的な論理を内部化できないでしょうか？
人間の推論の複雑なニュアンスとアルゴリズム的手法の規律ある精度の両方に基づいて、我々の仕事は、これらの二つの側面を融合させてLLM内の推論能力を増強することを目指しています。既存の研究は、人間が複雑な問題をナビゲートする際に、狭い焦点ではなく包括的な思考を確保するために過去の努力に直感的に頼ることを強調しています。トークンの制限にのみ束縛されるLLMは、人間の作業記憶の障壁を打ち破る準備ができているように見えます。この観察に触発され、LLMが以前の中間ステップを参照しながら、実行不可能なオプションを篩にかけるような、同様の層状のアイデア探索を模倣できるかどうかを調査しました。人間が直感的な洞察力で優れている一方で、アルゴリズムは組織的で体系的な探索で際立っています。現在の技術、例えばCoTは、この相乗的な可能性をしばしば見逃し、LLMにその場の精度に対する不当なプレッシャーをかけます。LLMの再帰的能力を最大限に活用することで、私たちはヒューマン-アルゴリズム的アプローチのハイブリッドを模倣します。これは、初期の候補から検証された解決策に至るまでの探求の本質を捉えるアルゴリズム的な例を使用することで達成されます。こうして、Figure 1と2で示されるように、私たちのアイデアであるThoughtsのアルゴリズム（AoT）が登場します。
より広い意味で、私たちのアプローチは文脈内学習の新たなパラダイムを示しています。従来の「教師あり学習」の型【問題、解決策】または【問題、解決への連続ステップ】とは異なり、私たちは【問題、探索プロセス、解決策】をカバーする新しい構造を提示します。自然に、アルゴリズムを使ってLLMを指導する際には、LLMがアルゴリズムの反復的思考を単に模倣することが期待されます。しかし、興味深いのは、LLMが自身の「直感」を注入し、アルゴリズム自体をも超える検索効率を達成する能力です（Figure 5を参照）。
関連する研究
標準プロンプト
この方法は、入力-出力プロンプトとも呼ばれ、言語モデルによるテストサンプルの回答を得る前に、タスクのいくつかの入力-出力例を提供します。この方法は非常に一般的で特別なプロンプト戦略を必要としませんが、より進んだ方法に比べて性能は劣ります。
CoTでは、LLMは、与えられた質問xが中間推論のピースc1, . . . , cnを通じてyという答えに至るプロセスとして展開される例を提示されます。これはx → c1 → . . . → cn → yとして表されます（Wei et al. 2022b; Lyu et al. 2023）。文脈内の例を模倣することで、LLMは解決策をより単純な線形ステップに自動的に分割し、数多くの推論ベンチマークで性能を向上させます。
最終回答を多数決で選択することにより、さまざまな推論パスを生成することを目的とした広く使用されているデコード戦略ですが、これには追加の生成が必要です。CoTの線形で直接的な進行とは対照的に、私たちのアプローチはLLMの探索的側面に焦点を当てています。私たちはc1, . . . , cnのシーケンスを単なる解決策への連続的なステップとしてではなく、アルゴリズム的な探索に似た動的で変更可能なパスとして再概念化し、探索、再調整、非線形進行を可能にします。
教育心理学（Libby et al. 2008）からのヒントを得て、L2MプロンプトはLLMに中心問題をより小さなサブプロブレムに分解するよう指示します。各サブプロブレムは順番に取り組まれ、次に進む前に結果が追加されます。この構造化された区別は、より広範な一般化に有益ですが、一回の試みでほぼ完璧な分解を見つけるという前提に基づいています。これは、明確な構造を持つ問題には理想的ですが、サブプロブレムの分解の複雑さ（24のゲームなど）と絡み合うタスクでは、この方法の柔軟性のなさが明らかになります。対照的に、AoTは活動中のサブプロブレムを強調するだけでなく（Figure 1を参照）、各サブプロブレムに対してさまざまなオプションを検討することにより、より思慮深いアプローチを可能にし、最小限のプロンプトでも効果を維持します。
各サブプロブレムが探索するための複数の実行可能なオプションを持つ場合、CoTやL2Mからの線形推論パスは思考空間のカバレッジを大幅に制限します。各サブプロブレムの可能なオプションを考慮すると、決定木は外部のツリー検索メカニズム（例：BFS、DFS）（Yao et al. 2023）によって探索されることがあります。LLMの評価能力も、効率を高めるために無望なノードを刈り取ることで検索を指示するために使用することができます。しかし、ToTのアキレス腱は、一つの問題に対して何百ものLLMクエリに過度に依存することです。私たちはこの制限を、単一の文脈内で全体の思考プロセスを生成することで解決します。
このようにして、我々の研究は既存の文献の中に位置づけられ、主要なアイデアについての議論に続きます。その後、実験結果を提示し、この新たなLLMの能力に関連する一連の仮説を探究し、最後に結論をまとめます。
https://scrapbox.io/files/65a890e592d5320026a509d7.png
思考のアルゴリズム
私たちの戦略は、現在の文脈内学習パラダイムの核心的な欠点を認識することに焦点を当てています。CoTは解決策につながる思考の連鎖を強化するものですが、時には間違った中間ステップを提示することがあります。Faithful CoTは、LLMの出力がPythonのような決定論的実行のための特定タスクの擬似コードに似ている、記号的な推論チェーンを引き出すことでこれを修正することを目指しています。この意図は、各リンクの出力や入力ではなく、思考プロセスのみを使用することですが、それらは信頼性が低い傾向があります。しかし、CoTのたまの誤りは、必ずしもLLMが正確に計算できないためではないかもしれません。LLMは、以前の文脈内の例の条件に密接に一致する質問に直面すると、適切な質問を生成するよりも、それらの出力をエコーすることを好むかもしれません。この現象を明らかにするために、実験を設計しました。算術タスク（例えば「11 − 2 =」）についてtext-davinci-003に問い合わせる際に、同一の出力に収束する複数の文脈内の方程式（例えば「15 − 5 = 10, 8 + 2 = 10」）を前置しました。Figure 3に示された結果からは、正しい推論が文脈に存在するだけで、基本的な算数スキルが不注意にも損なわれる可能性があることを示唆する精度の急激な低下が明らかになります。 https://scrapbox.io/files/65a8923dd03bc800249ef1ca.png
このバイアスを相殺するために、例の出力を多様化することが実現可能な解決策のように思えるかもしれませんが、これは出力の分布を微妙に歪める可能性があります。単に失敗した試みを追加することは、ランダムな検索のようなもので、モデルが本当に解決するよりも再試行を奨励するかもしれません。失敗した検索とその後の回復およびそうした試みからの学習の両方が役割を果たすアルゴリズム的振る舞いの真の本質を捉えるために、我々は探索アルゴリズムを模倣した文脈内の例を組み込んでいます。特に深さ優先探索（DFS）と幅優先探索（BFS）が注目されています。例についてはFigure 1を参照してください。
https://scrapbox.io/files/65a894c0ff1b1200226a2640.png
この論文では、ツリー検索問題を思い起こさせる広範なタスククラスに焦点を当てています。これらのタスクでは、主要な問題を分割し、各セグメントに対して実行可能な解決策を作成し、追求または放棄する経路に関する決定を行い、より有望なセグメント化の再評価のオプションを持つ必要があります。サブセットごとに別々のクエリを提示するのではなく、LLMの反復能力を活用して、一つの統一された生成スイープ内でそれらに対処します。一つまたは二つのLLMインタラクションに自分たちを制限することで、このアプローチは自然に先行する文脈候補からの洞察を取り入れ、解決領域の詳細な探求を必要とする複雑な問題に取り組むことができます。私たちの目標に沿って、それらの考えがどれほど小さいか、または大きいか、そしてトークン効率を促進するためにLLMにどのような文脈内の例を与えるべきかについても洞察を提供します。その後、ツリー検索アルゴリズムの主要なコンポーネントと、私たちのフレームワークにおけるそれらの表現について概説します。
サブプロブレムへの分解
問題を与えられた場合、実行可能な推論経路を示す検索ツリーを構築すること自体がすでに要求の高いタスクです。これは実際の問題解決の側面を除外しています。任意の分解は、サブタスク間の相互関係だけでなく、個々に対処する容易さも考慮しなければなりません。単純な複数桁の加算を考えてみましょう：数字をバイナリに変換することはコンピュータにとって効率的かもしれませんが、人間は通常、10進数の算数をより直感的に見つけます。さらに、サブプロブレムが一定であっても、その実行は異なる場合があります。直感は解決策のステップ間の近道につながる可能性がありますが、その欠如はより詳細なステップを必要とするかもしれません。適切なプロンプト（つまり、文脈内のアルゴリズム的な例）を作成することは、これらのニュアンスに依存し、LLMが信頼できるパフォーマンスのために必要な最小限のトークンを決定します。これは、LLMの文脈制約内に収まるためだけでなく、効果的であるためにも重要です。なぜなら、LLMは同様のトークン量を使用して、その文脈に共鳴する問題に対処することが期待されるからです。
サブプロブレムへの解決策の提案
既存の研究では、LLMトークン出力確率からの直接サンプリングが主流のアプローチです（Wang et al. 2022; Yao et al. 2023）。一回限りの回答には効果的ですが（Kadavath et al. 2022）、特定の制約があります（Robinson and Wingate 2022）。この方法は、連続したサンプルを統合するか、後続のプロンプトで評価することが必要なシナリオでは不足しています（Robinson and Wingate 2022）。モデルクエリを最小限に抑えるために、私たちは中断のない解決策作成プロセスを採用します。ここでは、生成を停止せずに、現在のサブプロブレムに対する解決策を直接かつ連続的に生成します。
この方法の利点は三つあります。
第一に、すべての生成された解決策が共有文脈内に存在するため、各解決策の評価に個別のモデルクエリを必要としません。
第二に、当初は直感に反するかもしれませんが、分離されたトークンやトークングループの確率は常に意味のある選択をもたらすわけではありません。Figure 4に示されるように、独立して評価すると、最初の数字の2番目に高い確率のトークンは「1」ですが、これは素数として適格ではありません。
https://scrapbox.io/files/65a89692a46af60023e0a2ef.png
しかし、生成が途切れない場合、導かれた数列は正しいです。この不一致は、シーケンスモデリングにおけるマルコフ性質の制限的な性質を指摘しています。私たちの視点の核心は、アルゴリズム的探索のような連続的なタスクにおいて、LLMは断続的に停止してトークンサンプリングプロセスを再開するよりも、完全な数列を生成するのに長けているという前提です。
サブプロブレムの可能性の評価
上記のように、既存の技術は追加のプロンプトに依存して、ツリーノードの可能性を見極め、探索方向に関する決定を支援します。私たちの観察では、もっとも有望なルートが文脈内の例に含まれている場合、LLMは有望な候補を優先するように自然に誘導します。これにより、複雑なプロンプトエンジニアリングの必要性が減少し、直感的または知識駆動の複雑なヒューリスティックスを組み込むことができます。再び、私たちのアプローチでは別個のプロンプトがないため、同じ生成内で候補の実現可能性を即座に評価することが可能です。
好ましい時点へのバックトラッキング
次に探索するノード（以前のノードに戻ることを含む）の決定は、選択されたツリー検索アルゴリズムに基づいています。以前の研究（Yao et al. 2023）では、検索プロセスにコード化されたメカニズムなどの外部手段が採用されていましたが、これはその広範な魅力を制限し、追加のカスタマイズを必要とします。私たちの設計は主に、剪定によって補完されるDFSアプローチを採用しています。目的は、同じ親を共有するノード間の近接性を維持し、LLMが遠くの特徴よりもローカルな特徴を優先するように促すことです。さらに、私たちはBFSに基づいたAoTアプローチのパフォーマンス指標を提示します。文脈内の例から洞察を得るモデルの固有の能力に依存することで、追加の特別なメカニズムの必要性を回避しています。
実験
AoTは他の単一プロンプト方法（例：標準、CoT/-SCプロンプト）を性能で上回り、24のゲームや5x5ミニクロスワードのようなベンチマークでToTなどの外部メカニズムを利用する方法と比較しても競争力があります。
24のゲーム
24のゲームは、プレイヤーに4つの数字が与えられ、加算、減算、乗算、除算（各操作は複数回使用できる）を使用してこれらの数字を合計24にする数学的カードゲームです。たとえば、数字「8 8 5 4」に対しては、「8 * (5 - (8/4)) = 24」という解決策があります。一見すると、このゲームは簡単に見えるかもしれませんが、4つの数字の任意のセットに対して約13,000の異なる式が可能であることを簡単な計算で示唆しており、現代のLLMにとって大きな挑戦です。
タスクセットアップ
(Yao et al. 2023)で詳述されているセットアップに従い、4nums.comで相対的な難易度でランク付けされた1362ゲームから、インデックス901-1000のゲームを使用します。試みが成功と見なされるためには、提供された正確な数字を使用し、許可された操作のみを使用して合計24を導き出す必要があります。
ベースライン
標準プロンプトとCoTは5ショット設定で使用され、CoTは操作の3ステップを統合します。これらの方法は100回サンプリングされ、これらのサンプルから得られた平均成功率が報告されます。CoT-SCも私たちのセットアップで100票でテストされます。ToTについては、5の幅を使用します。彼らの研究からのパフォーマンス指標が直接引用されており、無用な炭素排出の必要性を回避します。
AoTセットアップ
標準プロンプトとCoTベースラインセットアップと同じ5ショット設定を使用します。私たちの文脈内サンプルはDFSスタイルの探索アルゴリズムを利用しており、これはFigure 5で従来のDFSと対比する際に使用されるバージョンと同じです。各サブツリーの探索では、「最初のステップ」または「最初の操作」と呼ばれ、2つの数字（Figure 1の「3」とラベル付けされたサブツリーの3番目の「最初のステップ」での8と6の選択）と対応する操作（例：8 - 6）を選択します。この操作により新しい数字、2が生成され、合計3つの数字が残ります。これら3つの数字の徹底的な組み合わせは、Figure 1の「3」のサブツリーの下にある19の葉ノードで終わります。
https://scrapbox.io/files/65a8984ec0511b0023c8ad02.png
私たちは2つの側面を評価することを目指しています：LLMが有望な最初の操作を特定する能力、これは解決された葉ノードの数に直接影響を及ぼし、従来のDFSに対するそのパフォーマンスです。使用したプロンプトの詳細は付録に記載されています。私たちの方法はトラジェクトリサンプリング(現在のポリシーを使用して（次状態、アクション）のペアを得る手法)よりも連続的な生成を重視しているため、温度設定は0で操作します。
結果
表1からは、標準プロンプトとCoT/-SCがLLMを使用したツリー検索方法と比較して大幅に後れを取っていることが明らかです。"Standard + Refine"の結果は、成功率27%を示しており、これは（Yao et al. 2023）から引用されています。この方法では、LLMに対し、最初の回答が間違っている場合は最大10回の反復で回答を洗練するように求めます。一方、ToTは最大100のノード訪問に制限されており、これは各例について数百のLLMクエリに相当します。注目すべきは、AoTが単一のクエリで結果を達成していることです。100倍以上のリクエストを削減してもなお、このタスクでToTを上回る性能をAoTが示しています。
https://scrapbox.io/files/65a89a200fa213002300d21f.png
エラー分析
厳密にLLM中心のアプローチを採用し、外部ツールや編集を避けることで、24のゲーム中に観察された間違いを分類しました。これは、LLMのみを使用する際の改善点を明確にするのに役立ちます。これらのエラーを4つの異なる、網羅的なカテゴリに分類しました：
1）トークン超過エラー
LLMが最大トークン閾値に達し、解決策を特定できない。
2）表現の誤り
LLMは正しい論理またはステップを持っているが、それらをまとまりのある答えに表現または形成する際に失敗する。
3）非決定エラー
LLMは解決策を発見するが、それを確定せずに検索を続ける。
4）その他のエラー
この包括的な用語は、解決策を見落としたり、誤った答えを提供したりするような計算エラーなど、その他の間違いを含みます。
AoTの検索能力を独占的に示すために、AoT + マニュアル解決バージョンも提示します。ここでは、LLMが解決策を特定したら、その最終的な表現は手動で処理されます。これはToTメソッドでも採用されている戦略です。表2で示されているように、間違いの顕著な7％が非アルゴリズム的要因、例えば非決定や表現の誤りから生じています。実際、手動解決を行うと、AoTは78％の成功率を達成し、ToTを上回ります。これは、成功した問題解決の認識と表現に関する領域における私たちのプロンプトの精度を高める可能性を強調しています。また、トークン制限は、LLMの再帰的推論をさらに強化する可能性がある生成コンテキストウィンドウの拡大の魅力を強調しています。
https://scrapbox.io/files/65a89a9d6731770023d7ac33.png
ミニクロスワード
5×5ミニクロスワードは、25マスのグリッドを5×5の配置で特徴づけるコンパクトな単語パズルです。プレイヤーは、各単語に与えられた手がかりに基づいてグリッドを埋めることを任されます。手がかりは、横（水平方向）と縦（垂直方向）に走る単語の両方に与えられます。単語は特定の文字で交差し、パズルを完成させるための追加のヒントを提供します。
タスクセットアップ
(Yao et al. 2023)で概説されているセットアップに従い、goobix.comで利用可能な156ゲームのうち、136、141、146、151、156番のゲームからプロンプトを引き出します。テストは20ゲームのセットに焦点を当て、具体的には1、6、...、91、96番のゲームです。
ベースライン
24のゲームに対するアプローチと同様に、標準プロンプト、CoT、ToTと比較して私たちの方法をベンチマークします。標準プロンプトでは、クロスワードとそれぞれの解決策を文脈内の例として提供します。CoTはこれに加えて、10の手がかりのそれぞれに対する単語の取得を促します。これらは水平方向と垂直方向に均等に分割されます。ToTの成功率は、比較のために元の出版物から直接抽出されます。
AoTセットアップ
プロセスを2つのステップに分割し、それぞれにクエリを含めます。最初に、LLMに各行と列に対して5つの潜在的な単語を提案するように依頼します。次に、クロスワードフレームワーク内の他の単語との互換性が最も高いスタート単語候補を特定します。この予備段階は、アルゴリズム初期化の「ウォームアップ」シーケンスを模倣しています。次のステップでは、事前に選択された単語から始め、LLMのアルゴリズム的推論能力を独占的に活用します。この方法では、挿入する可能性が高いオプション（具体的には、行または列）を循環的に選択し、候補単語を生成し、既にボード上にある単語との互換性を評価します。一致が見つからない場合は、別の有望な候補に焦点を移します。そうでなければ、単語はクロスワードに追加され、検索が続きます。サイクルはボードが完全に埋められるか、適切な単語が見つからなくなるまで続きます。これは、既存の単語が誤っているか、一致する単語がないためかもしれません。特筆すべきは、このプロセス全体が単一の生成ウィンドウ内で展開されることです。私たちのプロンプトに含まれるアルゴリズム的な例（詳細は付録に記載）には、ゲームを完了する3つと、主にクロスワードを埋め、8または9のスロットを埋める2つが含まれています。
結果
表3は、ミニクロスワードタスクにおけるAoTの熟練度を強調しています。これは、完全に正確に完成した単語の割合を表す、既存の研究で使用される単語成功率という指標において、さまざまなプロンプト技術に依存する以前の方法を上回っています。しかし、ToTには及びません。重要な観察点は、ToTが使用するクエリの膨大な量で、AoTよりも100倍以上です。AoTがToTを上回ることを妨げている要因の一つは、アルゴリズム的な例に固有のバックトラッキング能力が完全に活性化されていないことです。この能力を完全に活用すると、生成フェーズが大幅に長くなります。対照的に、ToTはバックトラッキングのために外部メモリを利用する利点があります。
https://scrapbox.io/files/65a8a47623aa730024c45a7c.png
エラー分析
AoTが犯す一般的な間違いを理解するために、エラーを4つの異なるカテゴリに分類しました。各ゲームに対する分析では、初期エラーが後続の失敗に連鎖するため、LLMが推論の道筋を描く際に最初に生じるエラーに焦点を当てます。1) 事前選択なし：LLMはウォームスタートフェーズに必要な互換性のある単語を生成できない。正しく事前選択された単語があれば、再帰的推論のための第二段階では、次のようなエラーが生じる可能性があります：2) 表現の誤り：LLMはすべての選択肢を使い果たしたと誤って信じ、早急に答えに飛びつく。3) 誤ったパターンの抽出：LLMは現在のボードのレイアウトに基づいて誤ったパターンを抽出する。4) 誤った単語の配置：正しいパターンを認識していても、LLMは不一致の単語を選択するか、より適切な代替案を見逃す。
クロスワードの複雑さをナビゲートすることは、時代遅れの用語、専門的な参照、およびタイプミスから生じます。主に観察されたエラーは、誤った単語配置によるもので、パターンの誤解釈に続きます。また、LLMは正確なインデックスで文字を整列させて単語構造を作成することに挑戦しているようです。これは、ToTフレームワーク内で外部メカニズムによって回避される障壁です。
議論
このセクションでは、24のゲームを主要なケーススタディとして使用し、AoTのためのプロンプトを作成する際に考慮すべき重要な側面について詳しく説明します。
AoTは、それに基づいてパターン化されたDFSを超えることができますか？私たちの主要な疑問は、LLMが文脈内で紹介されたアルゴリズムを単に模倣するだけでなく、その効率を上回る能力を持っているかどうかを確かめることです。図5で示されているように、AoTはDFSの対応部分よりも少ないノードを体系的にナビゲートします。DFSは後続のサブツリーを調査する際に均一な戦略を採用しますが、AoTのLLMは固有のヒューリスティックを統合します。この基本アルゴリズムに対する増幅は、LLMの再帰的推論能力の利点を例示しています。
https://scrapbox.io/files/65a8a4db574ce6002445b32c.png
アルゴリズムの選択がAoTの効果にどのように影響するか？
AoTのパフォーマンスにアルゴリズムの選択がどのような影響を与えるかを探るために、我々はBFSとランダム検索をAoTフレームワーク内で実装しました。表5に示された結果は、3つのAoTのバリエーションが全て単一クエリCoTを上回ることを明らかにしました。この結果は予想されていましたが、アルゴリズムに関わらず、AoTは検索を行い、ランダム検索バリエーションのランダム再試行またはDFSとBFS構成のバックトラッキングによって潜在的な間違いを再訪します。特に、構造化された検索バージョンであるAoT（DFS）とAoT（BFS）は、AoT（ランダム）よりも効率が良いことが示されました。これは、アルゴリズム的な洞察が解決策の発見において有利であることを強調しています。しかし、AoT（BFS）はAoT（DFS）に後れを取りました。AoT（BFS）によるエラーの詳細な検査は、LLMがDFSの対応部分よりも最適な操作を特定する上でより大きな挑戦に直面していることを明らかにしました。
https://scrapbox.io/files/65a8a545bc23bf0023b8e6f4.png
アルゴリズム的な例内の検索ステップ数がAoTの振る舞いをどのように調整するか？
私たちは標準のAoTプロンプトから始めて、サブツリーの探索を修正します。AoT（ショート）では、各文脈内の例が1つまたは2つのステップを使用して解決策に到達し、AoT（ロング）では3つから5つの追加サブツリー探索を組み込みます。
https://scrapbox.io/files/65a8a6dd4a3ce30025be11ba.png
総検索ステップ数への影響はFigure 6に示されています。私たちの観察は、オリジナルのAoTに比べて、AoT（ロング）の生成が長く、AoT（ショート）の生成が短いことを示唆しています。これは、検索ステップ数がLLMの検索速度に暗黙のバイアスを導入することを示唆しています。特に、誤ったステップをナビゲートする際でも、有望な方向の探索を強調することが重要です。
制限事項
AoTはToTと比較してクエリ数を大幅に削減しますが、標準プロンプトやCoTよりもリソース要求が多くなります。これは、トークン生成を通じてアイデアの広範な探索の結果です。トークン効率の高いアルゴリズム的な例を作成することは一つの道ですが、LLMの「トンネルビジョン」を巧みに活用するか、解放することにも潜在的な可能性があります。私たちの研究は主に特定のアルゴリズムに焦点を当てており、特にツリー検索タスクに注目しています。GPT-4を独占的に使用してテストを行ったことを強調することが重要です。他のLLMよりもコストがかかるものの、GPT-4の高度な機能がAoTの最適な機能に不可欠であり、劣ったモデルではAoTから同等の性能向上が得られない可能性があります。
結論
この論文は、最小限のクエリを使用してLLM内の推論経路をナビゲートするための先駆的なプロンプト戦略であるThoughtsのアルゴリズムを紹介します。私たちの研究結果は、この方法が以前の単一クエリ技術を大幅に上回るだけでなく、外部ツリー検索の実装と競合することを明らかにしています。このようなアプローチは、コストと計算要求の両方のバランスをとりながら、LLM内のアイデアの発見を合理化する可能性を高めます。今後の作業には、トークン効率の高いアルゴリズム的な例の設計、検索を加速するための「トンネルビジョン」活性化のための適応メカニズムの開発、および理論的な角度からのこの新しい文脈内学習モードの理解を深めることが含まれます。