技術的サマリー：LLM 推論および計画のための新奇性ベースの思考木探索

問題定義

大規模言語モデル（LLM）は言語ベースのタスクにおいて顕著な能力を示してきたが、複雑な推論や長期的な計画においては依然として脆い。単純なプロンプトはしばしば失敗し、思考木（ToT）のような構造化されたアプローチは、剪定されていない分岐探索に起因する指数関数的な実行時間とトークンコストに悩まされる。一方、反復幅（IW）のような幅ベースのプランナーに代表される古典的計画アルゴリズムは、「新奇性」に基づく状態の剪定によって効率を達成するが、これらは自然言語設定には適合しない硬直的で形式化された問題構造（例：PDDL）を必要とする。この研究が取り組む核心的な課題は、構造化されていない言語ドメイン内で新奇性の同様の概念を定義し、LLM の柔軟性を犠牲にすることなく ToT における効率的な剪定を可能にすることである。

手法

著者は、ToT フレームワークに新奇性ベースの剪定を統合する計画アルゴリズムを提案する。このアプローチは計画プロセスを以下の 4 つのサブタスクに分解する：

1. 行動生成: LLM が現在の状態から可能な次の行動を提案する。
2. 後続状態マッピング: LLM が行動を結果となる状態にマッピングする。
3. 計画検証: モデルが状態の系列が目標を満たすかどうかを判断する。
4. 新奇性推定: 新規の貢献であり、LLM が新奇性推定器として機能する。

新奇性推定と剪定

古典的プランナーがブール特徴部分集合に基づいて整数として新奇性を計算するのに対し、この手法は自然言語に適応した新奇性を採用する。LLM には、以前に訪問した状態のリストと比較して新しい状態が新奇かどうかを判断する二値の「はい/いいえ」質問がクエリされる。これにより、明示的な原子定義や数ショット例を必要とせず、モデルの事前学習された一般知識と意味理解を活用して、一意の状態を識別する。

探索木は、幅優先探索（BFS）または深さ優先探索（DFS）のいずれかを使用して探索できる。古典的な IW は通常 BFS を使用するが、著者は LLM の文脈では BFS が指数関数的なコスト増大を招く可能性があると指摘し、BFS と DFS の間のトレードオフを評価する。この手法はドメインに依存しないように設計されており、ドメインルールを説明する手作りのコンテキストプロンプトにのみ依存し、新奇性推定器自体に対するドメイン固有のプロンプトエンジニアリングを回避する。

主要な貢献

1. LLM 向け新奇性の適応: 本論文は、言語ドメインにおける測定可能な新奇性の概念を提案し、LLM の内面化された意味知識を活用して、硬直した特徴マッチングではなく状態の一意性に基づいて探索分枝を剪定する。
2. ドメイン非依存フレームワーク: 異なるドメイン（計画および推論）で柔軟な実験を可能にする一般的な実装が開発され、ドメインルールに関するコンテキストプロンプトの変更のみを必要とし、最小限の手作業で済む。
3. サブタスク評価: 古典的プランナーによって生成された真値に対して、4 つのサブタスク（行動生成、状態マッピング、検証、新奇性推定）を独立してテストするための、Plan-Bench に着想を得た専用の評価フレームワークを導入する。
4. プロンプト設計の実証的分析: 本研究は、LLM 計画がプロンプト設計に敏感であることを浮き彫りにし、特に「Blocksworld」における「pick-up」と「unstack」の区別など、反復する失敗点を特定し、ターゲットを絞ったプロンプト拡張がパフォーマンスを大幅に向上させることを実証する。

実験結果

このアプローチは、Blocksworld および Logistics 計画ドメイン、ならびに MATH ベンチマーク（レベル 5 の難易度）で評価された。

• サブタスクのパフォーマンス: Qwen3 14B モデルを使用した場合、「Thinking Mode」（推論トークン）と自然言語プロンプトが一般的に最良の結果をもたらした。モデルは標準的なシナリオで新奇性剪定を成功裏に実行したが、厳密な幅ベースの推論を必要とする非重複状態を含むより困難なバリアントでは苦労した。
• トークン効率: 適切に設定された環境（特に「Thinking Mode」と「Direct」な行動/状態マッピングを使用する場合）において、新奇性剪定 ToT は、同程度の成功率を維持しながら、標準的な ToT と比較して最大20 倍のトークンコスト削減を実現した。例えば、Blocksworld で DFS と Thinking Mode を使用した場合、ベースの ToT の平均トークン数は 33 万であったのに対し、新奇性剪定版は 1 万 8 千であった。
• 汎用性: この手法は、新奇性推定プロンプトの再チューニングなしに Logistics ドメインおよび MATH ベンチマークへ効果的に転移したが、MATH のような異なる推論ドメインにおける最適なトークン効率には、ドメイン固有のプロンプトチューニングが必要であるように見えた。
• 限界: 不適切に設定された環境では、パフォーマンスは著しく低下し、解決率はほぼゼロとなり、新奇性クエリのオーバーヘッドによりトークンコストは 100% 以上増加した。この手法は、基盤となる ToT 構成のベースパフォーマンスに大きく依存している。

意義と主張

本論文は、新奇性ベースの剪定が思考木推論の効率を成功裏に向上させ、探索空間とトークン消費を劇的に削減することで、複雑な計画タスクに対して実用的なものにすると主張している。著者は、この手法が解の品質や正確な新奇性計算に関する形式的な保証を欠く点で古典的な幅ベースの計画とは異なるが、LLM の適応性を活用した実用的で柔軟な代替案を提供していると強調している。

しかし、著者はこのアプローチの堅牢性については謙虚な立場をとっている。再帰的 LLM プロンプティングの不安定性が根本的な課題であり続けており、設定を煩雑で予測不可能なものにしていると指摘する。複雑なシナリオにおいて、剪定行動は真の「新奇性」推論というよりは、重複検出によって主に駆動されていることが観察された。したがって、この研究はより効率的な LLM 計画への一歩として提示され、ゴールのシリアライゼーション、代替の新奇性推定器、または状態理解を強化するためのより大規模なベースモデルの使用などの将来の方向性が示唆されている。