本研究が対象とする探索的推論問題（ERPs）は、エンティティ間の依存関係が不明瞭で、従来のマルチホップQAのような明示的な分解が困難な「レベル3タスク」として定義される。従来のRAG手法では、検索ノイズの増大、推論過程における誤差の累積、およびエンドツーエンドの計画メカニズムの欠如といった課題が存在する。また、既存の情報探索エージェントは強化学習等を用いるが、高い学習コストや推論時の分散が問題となる。これに対し、PlanRAGはトレーニングフリーで、実行前にグローバルな構造最適化を行うオフライン計画アプローチを採用している。
PlanRAGは、自然言語クエリを論理クエリツリー（LQTs）として構造化し、データベースのクエリ最適化技術をRAGに導入した。具体的には、Selingerの動的計画法（DP）を拡張し、ツリーのサイズ、密度、深さ、バランス、および意味的類似性の5つの次元に基づく多目的コストモデルを提案している。これにより、検索ノイズを抑制しつつ、複雑な推論経路を最適化することが可能となった。また、新たに構築された「WikiWeb-ERP」データセットにおいて、既存の反復型（RetGen, DualRAG等）およびグラフ型（ChainRAG, HopRAG等）のSOTAを上回る性能を実証した。さらに、リレーション前処理による計算コストの削減と、並列実行による高速化も実現している。
PlanRAGは「原子クエリ生成」「論理最適化」「物理実行」の3段階で構成される。まず、ERPを $(subject, predicate, object)$ 形式の原子クエリ集合 $\mathcal{Q}$ に分解する。次に、論理最適化フェーズにおいて、部分集合 $S \subseteq \mathcal{Q}$ の最小コスト $C(S)$ を、以下の再帰式を用いて算出する：
$$C(S) = \min_{S_1, S_2} \{ C(S_1) + C(S_2) + \text{inc\_cost}(S_1, S_2) \}$$
ここで、コスト関数 $Cost(\mathcal{T})$ は、ツリーサイズ $ts$、構造密度 $sd$、ツリー深度 $td$、ツリーバランス $tb$、および意味的類似性 $ss$ を用いて次のように定義される：
$$Cost(\mathcal{T}) = \alpha_1 ts + \alpha_2 sd - \alpha_3 td - \alpha_4 tb - \alpha_5 ss$$
物理実行フェーズでは、LQT上の各ノードに対し、子ノードの集約（$\text{agg}$）、書き換え（$\text{rew}$）、検索（$\text{ret}$）、生成（$\text{gen}$）をボトムアップに行う：
$$\text{node} = \text{gen}(\text{ret}(\text{rew}(\text{agg}(\text{children}))))$$
このプロセスはマルチスレッドによる並列化が可能である。
評価には、Wikipediaやライブウェブページから構築された「WikiWeb-ERP」データセットが用いられた。評価指標には、Accuracy (Acc)、Exact Match (EM)、Token-level F1、および $\text{gpt-3.5-turbo-instruct}$ による $\text{Acc}_{\text{sem}}$ が採用されている。実験の結果、PlanRAG w/ Retは既存の高度なRAG手法を凌駕した。アブレーション研究により、サイクル防止（w/o cp）、コンテキスト認識型マージ（w/o ca）、意味的類似性（w/o ss）の各要素が重要であることが示された。また、Llama-3やQwen-2.5、BGEやColBERTといった異なるモデル・リトリーバーに対しても頑健であることが確認された。効率面では、リレーション前処理によりLQT構築時間を82.8sから8.4sへ、LLMコール数を63.6から10.4へと大幅に削減し、並列実行により実行時間を2.56倍高速化した。
PlanRAGは、動的計画法の理論的複雑度が $O(2^n)$ であるものの、実用的なERPでは原子クエリ数 $n$ が15以下であることが多く、事前処理による枝刈りによって実用的な効率を維持している。本手法は、モデルやリトリーバーに依存しない（model-agnostic/retriever-agnostic）特性を持つ。しかし、いくつかの限界も存在する。第一に、単純な問題シナリオへの汎化が困難である可能性が挙げられる。第二に、提案されたコストモデルが、文書の長さやタスクの複雑度を明示的に正規化していないという課題がある。
本研究では、不確実性や曖昧性の高い探索的推論問題（Exploratory Reasoning Problems, ERPs）に対し、データベースのクエリプランニングの概念を応用したRAGフレームワーク「PlanRAG」を提案している。PlanRAGは、自然言語によるERPsを論理クエリ木（Logical Query Trees, LQTs）としてモデル化することで、従来の反復型やグラフベースの手法が抱えていた検索ノイズや誤差の累積、エンドツーエンドの計画メカニズムの欠如という課題を解決する。具体的には、ERPsを原子クエリに分解した後、複数の補完的な次元を含むコストモデルに基づいた動的計画法を用いて、これらを最適なLQTsへと構成する。実行フェーズでは、LQT上のノードに対して反復的な集約、書き換え、検索、生成を行い、中間結果を上位へ伝播させるとともに、マルチスレッドによる並列化で効率化を図っている。新たに構築されたデータセット「WikiWeb-ERP」を用いた実験の結果、PlanRAGは既存の最先端の反復型およびグラフベースのRAGシステムを上回る性能を示した。
本研究は、探索的推論問題（Exploratory Reasoning Problems, ERPs）に対処するため、データベースのクエリプランニングの概念を導入したRAGフレームワーク「PlanRAG」を提案している。ERPsは、エンティティ間の依存関係が曖昧で、従来のマルチホップクエリのような明示的な分解が困難な「レベル3タスク」として定義され、既存のRAGでは検索ノイズの増大、誤差の累積、エンドツーエンドのプランニングの欠如といった課題がある。PlanRAGは、自然言語クエリを論理クエリツリー（Logical Query Trees, LQTs）としてモデル化し、クエリパース、論理最適化、物理実行の3段階で処理を行う。論理最適化では、Selingerの動的計画法（DP）を用いて、ツリーサイズ、構造密度、ツリーの深さ、ツリーのバランス、および意味的類似性の5つの次元からなる多次元コストモデルに基づき、最適なLQTを構築する。物理実行フェーズでは、LQT上のノードを反復的かつ並列的に処理することで、中間結果を再帰的にルートノードへ伝播させる。評価には、Wikipediaやライブウェブページから構築された新しいベンチマークデータセット「WikiWeb-ERP」が用いられ、実験の結果、PlanRAGは既存の反復型およびグラフベースのRAGシステムを上回るSOTA性能を達成した。
RAGは、LLMの生成能力に外部知識の検索を統合することで、パラメータ化された知識の限界を補い、事実検証や知識に基づいた対話などのタスクを強化する手法である。マルチホップQAにおいては、グラフベースの手法による依存関係のモデル化や、反復的なRAGによる推論チェーンの構築が提案されているが、本論文が扱う探索的推論問題（ERPs）は、単純な逐次的な推論では解決困難な高い不確実性と分解の難しさを有している。情報探索エージェントは、強化学習や模倣学習を用いてアクションシーケンスの探索空間をオンラインで最適化するが、これは高い学習コストと推論時の大きな分散を伴う。これに対し、提案手法であるPlanRAGは、実行前に計画を最適化するオフライン計画を採用しており、自然言語クエリから直接、木構造の探索空間である論理クエリツリー（LQTs）を探索する。このアプローチにより、軌跡の教師あり学習やオンラインの方策学習に依存することなく、グローバルな構造最適化が可能となり、トレーニングフリーでスケーラブルな手法を実現している。
本セクションでは、データベースにおける論理クエリツリー（LQT）の概念を、探索的推論問題（ERP）における自然言語クエリの構成的意味論を捉えるための階層的表現へと再定義している。本論文におけるLQTは、原子クエリの集合をノード $\mathcal{V}$、それらの間の意味的依存関係をエッジ $\mathcal{E}$ とする有向非巡回グラフ（DAG）としてモデル化され、葉ノードからルートノードへとボトムアップに実行される。最適化手法にはSelingerの動的計画法（DP）を採用しており、原子クエリの集合 $\mathcal{Q}$ に対し、部分集合 $S \subseteq \mathcal{Q}$ の最小実行コスト $C(S)$ を、分割された2つの部分集合 $S_1, S_2$ （$S = S_1 \cup S_2$）を用いた再帰式 $C(S) = \min_{S_1, S_2} \{ C(S_1) + C(S_2) + \text{inc\_cost}(S_1, S_2) \}$ によって算出する。ここで $\text{inc\_cost}$ はI/OやCPU、メモリ使用量を含む増分コストを推定する。また、コストモデルの重要な信号として、BGEモデルを用いて元のクエリとテキスト化されたLQTのセマンティックな整合性を、内積 $\text{sim}(x, y) = \text{enc}(x)^\top \text{enc}(y)$ によって算出する手法が導入されている。
PlanRAGは、探索的推論問題（ERP）を解決するために、データベースのクエリ計画に触発された論理クエリツリー（LQT）を構築・実行するフレームワークである。手法は、ERPを $(subject, predicate, object)$ 形式の原子クエリに分解する「原子クエリ生成」、動的計画法（DP）を用いて最適なLQTを構成する「論理最適化」、およびボトムアップの並列実行を行う「物理実行」の3段階で構成される。論理最適化では、SelingerのDPパラダイムを拡張し、関係性の事前処理、サイクル防止、および部分的なLQTをプロンプトに含めるコンテキスト認識型マージを導入している。LQTの評価には、ツリーサイズ $ts$、構造密度 $sd$、ツリー深度 $td$、ツリーバランス $tb$、および元のクエリとの意味的類似性 $ss$ を用いた多目的コスト関数 $Cost(\mathcal{T})$ を定義しており、以下の式で最小化を目指す：
$$Cost(\mathcal{T}) = \alpha_1 ts + \alpha_2 sd - \alpha_3 td - \alpha_4 tb - \alpha_5 ss$$
実行フェーズでは、非葉ノードにおいて子ノードのクエリと回答を統合（$\text{agg}$）し、それらをコンテキストとしてクエリを書き換え（$\text{rew}$）、検索（$\text{ret}$）および生成（$\text{gen}$）を行うプロセス $\text{node} = \text{gen}(\text{ret}(\text{rew}(\text{agg}(\text{children})))) $ を繰り返す。計算量に関しては、DPの理論的複雑度は $O(2^n)$ であるが、実用的なERPでは原子クエリ数 $n$ が15以下であることが多く、LLM呼び出しのコストが支配的であるため、事前処理による「無関係（Unrelated）」なペアの枝刈りが実行効率に大きく寄与する。
本実験では、探索的推論問題（ERP）に特化したWikiWeb-ERPデータセットを用い、提案手法であるPlanRAGの性能を、Accuracy (Acc)、Exact Match (EM)、Token-level F1、およびgpt-3.5-turbo-instructによるSemantic Accuracy ($\text{Acc}_{\text{sem}}$) の4指標で評価している。実験の結果、PlanRAG w/ Retは、反復型（RetGen, DualRAG等）やグラフ型（ChainRAG, HopRAG等）の既存の高度なRAG手法を上回り、SOTAを達成した。アブレーション研究により、論理的誤りを防ぐサイクル防止（w/o cp）や、意味的一貫性を維持するコンテキスト認識型マージ（w/o ca）、およびプランニングの意図を逸脱させないための意味的類似性（w/o ss）が、LQT（Logical Query Tree）構築において極めて重要であることが示された。また、PlanRAGはLlama-3やQwen-2.5などの異なるベースモデルや、BGE、ColBERTなどの異なるリトリーバーに対しても性能が向上することを確認しており、モデルやリトリーバーに依存しない頑健性（model-agnostic/retriever-agnostic）が実証された。効率面では、リレーション前処理によりLQT構築時間を82.8sから8.4sへ、LLMコール数を63.6から10.4へと大幅に削減し、さらに並列実行により実行時間を2.56倍高速化することに成功している。一方で、本手法には、単純な問題シナリオへの汎化の難しさや、コストモデルが文書長やタスク複雑度を明示的に正規化していないといった限界が存在する。