1 Introduction↩︎

Retrieval-Augmented Generation (RAG) integrates large language models (LLMs) with external document repositories, grounding responses from retrieved documents rather than parametric memory alone, thereby effectively mitigating LLMs’ hallucinations [1], [2]. Owing to its ability to combine retrieval and generation, RAG has demonstrated strong performance on knowledge-intensive tasks that require factual grounding and evidence-based reasoning. However, existing RAG systems largely overlook the complex queries referred to as exploratory reasoning problems (ERPs)¹ in this paper, as shown in Figure 1 (a). ERPs are characterized by high uncertainty and difficulty in reduction, where entities are coupled in fuzzy and emergent ways  [3], [4].

The inherent complexity of ERPs poses fundamental challenges for current RAG systems. As shown in Figure 1 (a), unlike conventional multi-hop queries with well-specified and decomposable chains, ERPs lack an explicit intermediate structure, making it unclear what information should be retrieved, in what order, and how to aggregate it coherently. More importantly, ERPs represent a broader class of scenarios that require long-horizon reasoning and global planning under uncertainty, in which sub-tasks are coupled by complex, implicit dependencies. Such characteristics make it inherently difficult to design effective planning strategies or decomposition schemes using existing methods, highlighting the fundamental importance of addressing ERPs. Consequently, existing RAG systems often struggle with the following three interrelated issues when resolving ERPs. (\(i\)) Retrieval noise proliferates: Due to ERPs’ uncertainty and ambiguity, the retrieval process often returns large volumes of irrelevant documents, overwhelming LLMs with spurious evidence [4]. (\(ii\)) Error accumulation: Iteration-based RAG methods process sub-queries sequentially, where early retrieval or generation errors propagate through later steps, leading to compounding hallucinations and unstable reasoning [2]. (\(iii\)) Lack of end-to-end planning: More importantly, existing planning approaches rely on manually annotated trajectories or decomposition rules, lacking an end-to-end mechanism for query optimization [4], [5]. We observe that a deterministic global planning mechanism can not only coordinate the execution order and dependencies across sub-queries, but also effectively reduce retrieval noise and error accumulation [4]. Notably, the limitation, i.e., the lack of an end-to-end planning to coordinate retrieval and generation, structurally resembles the core challenge addressed by query planning in database systems, where the order and dependencies of operations must be optimized before execution. This analogy motivates us to explore whether a planning mechanism can benefit natural language queries by introducing structured paths and reducing ambiguity in retrieval.

As shown in Figure 1 (b), motivated by database query planning where SQL queries are compiled into logical query trees (LQTs) and optimized through cost-based strategies [6], we propose to construct LQTs from natural language queries of ERPs, enabling efficient and interpretable planning. However, translating this idea into natural language is non-trivial due to two fundamental gaps between structured SQL and unstructured natural language. (\(i\)) Representation gap: SQL queries are grounded in explicit relational schemas that predefine how relational atoms can be joined via well-specified keys and relations, providing a clear blueprint for LQT representation. In contrast, natural language queries are unstructured, where semantic units and latent dependencies among them remain implicit and ambiguous. There is no predefined schema to dictate how these units should be organized into LQTs, making the automatic derivation of structurally robust and semantically sound LQTs a core challenge. (\(ii\)) Optimization gap: Database optimizers evaluate candidate LQTs in SQL using cost models that estimate physical execution cost (I/O, CPU, and memory) based on well-defined schemas and statistics. In contrast, optimizing LQTs in natural language cannot rely on such physical metrics. Therefore, the cost must reflect novel perspectives, such as semantics and structure, necessitating a multi-dimensional cost model tailored for conceptual query planning.

To bridge these gaps, we introduce an end-to-end RAG framework PlanRAG, that models ERPs as LQTs for ERPs, thereby mitigating retrieval noise and error accumulation. The overall pipeline of PlanRAG consists of three main stages, which align with classical database query planning: query parsing, logical optimization, and physical execution². First, in the query parsing, to address the representation gap, we decompose ERPs into atomic queries, each corresponding to a minimal semantic unit, i.e., a single relational triple, enabling precise representation of intermediate dependencies. These atomic queries exhibit semantic relationships, including Parent–child, Sibling, and Unrelated. Second, in the logical optimization, we hierarchically organize these atomic queries into an optimal LQT via semantic relationships using Selinger’s dynamic programming (DP). Before DP, we introduce relation preprocessing to reduce the number of LLM calls required to evaluate the potential node merging. During DP, we propose cycle prevention to preserve the DAG structure of LQTs, and context-aware merging to ensure that each local merging aligns with the tree structure. To address the optimization gap and guide the construction of high-quality LQTs, we design a cost model from five complementary dimensions, i.e., tree size (node number), structural density (edge number), tree depth, tree balance and semantic similarities, ensuring that LQTs are structurally robust and semantically sound. Finally, in the physical execution, we execute aggregation, rewriting, retrieval, and generation in an iterative manner over LQTs, where nodes are processed concurrently and intermediate results are recursively propagated upward until the root node yields the final answer. To mitigate latency and enable efficient inference, we further parallelize execution by scheduling independent nodes concurrently using multi-threaded execution.

To evaluate PlanRAG’s performance on ERPs, we have constructed and released an RAG dataset, namely WikiWeb-ERP, which contains some queries collected from existing datasets and those constructed following the approach of WebSailor [4], along with their corresponding documents retrieved from both Wikipedia and live webpages. Our experiments demonstrate our framework’s superiority over some state-of-the-art baselines on WikiWeb-ERP, and its potential for handling ERPs.

The main contributions of this paper include:

1. Following the paradigm of database query planning, we propose an RAG framework PlanRAG for resolving ERPs, which improves the planning capability for complex retrieval tasks and provides a new paradigm for optimizing natural language queries.

2. To bridge the gaps between structured SQL and unstructured natural language queries, we propose an effective method to construct LQTs for ERPs via dynamic programming guided by a multi-dimensional cost model, which enables efficient and interpretable planning within the RAG paradigm and presents a new application scenario for database query optimization techniques.

3. To systematically evaluate our PlanRAG’s performance specifically on ERPs, we further release a new dataset, WikiWeb-ERP, as a complex RAG benchmark. Our experimental results demonstrate that PlanRAG achieves state-of-the-art performance on WikiWeb-ERP over existing iteration-based and graph-based RAG systems, highlighting the critical advantage of our planning mechanism.

2 Related Work↩︎

2.1 Retrieval-Augmented Generation↩︎

Retrieval-Augmented Generation (RAG) integrates the generative capability of large language models (LLMs) with external knowledge retrieval, enabling dynamic access to external knowledge sources during reasoning [1], [7], [8]. This integration substantially enhances model performance on tasks requiring external knowledge retrieval and reasoning, such as question answering [9], fact verification [10], and knowledge-grounded dialogue [11]. The core idea of RAG is to employ a retriever to identify documents or evidence passages relevant to a given query from large-scale corpora, and to condition the generator on the retrieved evidence to produce grounded responses. Consequently, RAG effectively alleviates the limitations of LLMs’ parameterized knowledge and extends their applicability to tasks requiring real-time information access, broad knowledge coverage, and cross-document reasoning [12].

2.2 RAG for Multi-Hop QA↩︎

Multi-hop question answering (QA) requires the model to perform a sequence of interdependent reasoning steps, thereby constructing a reasoning chain that leads to the final answer [13], [14]. Multi-hop QA constitutes a compelling testbed for evaluating RAG systems because it imposes stringent requirements on both the knowledge retriever and the answer generator [15], [16]. Graph-based methods explicitly model multi-hop dependencies by constructing document/reasoning graphs and retrieving evidence along graph paths, thereby enhancing coherence and interpretability [17], [18]. Iterative-based RAG methods enable models to repeatedly access external knowledge during the reasoning process, progressively constructing coherent reasoning chains and thereby effectively addressing challenges in multi-hop inference [19], [20]. Unlike iterative-based methods that execute sub-queries sequentially in a simple chain, ERPs examined in this paper involve problems with high uncertainty and difficulty in reduction [21]. ERPs cannot be adequately addressed through straightforward sequential reasoning; instead, they necessitate well-designed query planning that optimizes the execution order of sub-queries and the dependencies in the query structure.

2.3 Information-Seeking Agents↩︎

Information-seeking agents [22]–[27] aim to develop autonomous web systems capable of issuing search queries, navigating webpages, and extracting relevant evidence through sequential decision-making. Recent studies have demonstrated that these agents perform well on ERPs [4], [5], [28], which involve complex, long-horizon information-seeking tasks. Such agents typically rely on large collections of high-quality interaction trajectories for supervision, leveraging reinforcement learning or imitation learning to enhance performance. Fundamentally, information-seeking agents perform online optimization over action-sequence search spaces, where planning and execution are tightly interleaved and decisions are refined incrementally based on intermediate observations. This online paradigm, while flexible, often incurs high training costs and substantial variance during inference. In contrast, PlanRAG adopts offline planning, where planning is optimized before execution. Rather than searching over action sequences, PlanRAG explores a tree-structured search space, i.e., LQTs, directly from the natural language query. This shift enables global structural optimization without relying on trajectory supervision or online policy learning. As a result, our method is training-free and does not require manually annotated trajectories, offering greater practicality and scalability across domains.

3 Preliminaries↩︎

3.1 Query Planning↩︎

In database systems, SQL queries are first parsed into an abstract syntax tree and then transformed into logical query trees (LQTs), which capture queries’ semantics in relational algebra [29]. Based on the logical representation, query optimizers systematically explore alternative query plans through equivalence-preserving transformations, such as operator reordering and decomposition. Candidate plans are evaluated using cost models that estimate execution efficiency, and the optimized logical plan is subsequently translated into a physical query plan for execution. This planning process enables databases to perform global reasoning about query execution before accessing actual data.

3.2 Logical Query Tree↩︎

As shown on the left in Figure 1 (b), a logical query tree (LQT) is typically defined as a hierarchical logical plan derived from structured queries (e.g., SQL) in database systems, where nodes correspond to relational algebra operators (such as selection, projection, and join) and edges represent data flow between operators [30]. These trees are grounded in well-defined schemas and equivalence rules, ensuring deterministic semantics and enabling cost-based optimization for efficient query execution.

In this paper, we redefine LQTs as hierarchical representations that capture the compositional semantics of natural language queries. Formally, an LQT is modeled as a directed acyclic graph (DAG) \(\mathcal{T} = (V, E)\), where \(V\) is the node set and \(E\) is the edge set. Each node \(v \in V\) represents the atomic queries, as shown in Table 1, which are derived from the original ERP. Each edge \(e = (v_i, v_j) \in E\) encodes semantic dependencies between atomic queries, with leaf nodes corresponding to directly executable atomic queries. The LQT execution follows a bottom-up process: nodes are processed concurrently and intermediate results are recursively propagated upward until the root node yields the final answer. Unlike LQTs in databases, which operate over relations and algebraic operators with rigid semantics, LQTs in this paper are semantic composition trees constructed from natural language queries. This adaptation allows our LQTs to capture the compositional structure inherent in ERPs, providing a flexible yet interpretable system for RAG.

3.3 Selinger’s Dynamic Programming↩︎

Selinger’s dynamic programming (DP) is a classical method in database query planning for generating optimized LQTs from a set of atomic queries [6], [31]. The input of the algorithm is a set of atomic queries, each representing an indivisible basic operation derived from the original query, and the output is an optimized LQT \(\mathcal{T} = (V, E)\), where the nodes \(V\) correspond to atomic or intermediate sub-queries and the edges \(E\) encode semantic dependencies between sub-queries. The algorithm follows a bottom-up strategy: it first computes the execution cost for each atomic query and then recursively combines smaller subplans into larger ones for progressively larger subsets of atomic queries, selecting the combination with the minimum cost at each step. Let the set of atomic queries be \(\mathcal{Q} = \{q_1, q_2, \ldots, q_n\}\). For any non-empty subset \(S \subseteq \mathcal{R}\), let \(C(S)\) denote the minimum estimated cost for executing all joins among the queries in \(S\). To compute cost \(C(S)\), the algorithm considers splitting \(S\) into two non-empty subsets, where \(A \subset S\) represents one subset and the other subset is \(S \setminus A\). The recursive cost formula is defined as: \[C(S) = \min_{A \subset S} \left\{ C(A) + C(S \setminus A) + J(A, S \setminus A) \;\middle|\; A \neq \emptyset \right\},\] where \(J(A, S \setminus A)\) estimates the incremental cost of joining the subplan over \(A\) with the subplan over \(S \setminus A\), including I/O, CPU, and memory usage. The algorithm enumerates subsets in increasing order of size and prunes suboptimal intermediate plans to ensure that each intermediate subplan is locally optimal. Ultimately, all locally optimal subplans are combined to form a globally optimal LQT \(\mathcal{T}\). Compared with greedy or heuristic tree generation, DP supports systematic pruning, stable cost-based evaluation, and natural integration of semantic signals without relying on gradient-based learning. These properties make Selinger’s DP particularly suitable for LQT construction under semantic uncertainty in natural language.

3.4 BGE Model↩︎

BGE [32] is a pretrained dense embedding model designed for semantic similarity estimation and retrieval tasks. It maps input text into a dense vector space, where semantically similar texts are close to each other. Formally, given two text sequences \(x\) and \(y\), BGE encodes them into dense representations via an encoder \(E(\cdot)\), and their similarity is computed as: \[\text{sim}(x, y) = \langle E(x), E(y) \rangle,\] where \(\langle \cdot, \cdot \rangle\) denotes the inner product. In this paper, we use BGE to encode both the original query and the textualized logical query tree. The resulting similarity score measures the semantic alignment between the constructed logical query tree and the original query, and serves as a key signal in our cost model (Section 4.3).

4 Methodology↩︎

4.1 Overview↩︎

The pipeline of our proposed PlanRAG is shown in Figure 2, which enables global planning for ERPs. We begin with decomposing each ERP into atomic queries, namely, minimal semantic units (atomic query generation). Analogous to LQT construction in database query planning, we then organize these atomic queries into optimal LQTs via dynamic programming guided by a multi-dimensional cost model (LQT construction). To ensure efficiency, we perform a bottom-up and parallel execution strategy over LQTs, involving iterative aggregation, rewriting, retrieval, and generation until the root node yields the final results (LQT execution).

Notably, corresponding to the database query processing pipeline, the three stages of our PlanRAG are query parsing (atomic query generation), logical optimization (LQT construction), and physical execution (LQT execution). Our approach focuses primarily on the logical optimization, while physical optimization (e.g., caching mechanisms) is reserved for future research.

4.2 Atomic Query Generation↩︎

To enable precise representation of intermediate dependencies, we employ well-designed prompting techniques to leverage LLMs for decomposing complex queries into multiple atomic queries, where the detailed prompts are introduced in Appendix A. Specifically, we provide an explicit definition of atomic queries together with illustrative demonstrations in the prompt, guiding the LLM to formulate each atomic query in the form of (subject, predicate, object). In this paper, each atomic query is indivisible and corresponds to a single relational triple. For example, the atomic query (“What were the early Christian hymns?”) derived from the ERP in Figure 2 corresponds to a triple (the early Christian hymns, were, ?). This strict one-to-one mapping ensures both the semantic atomicity of decomposition results and the natural mapping between atomic queries and triples, thereby preserving the logical structure of original queries and enabling precise retrieval of supporting documents. These atomic queries can be organized into LQTs based on three types of semantic relationships: (\(i\)) Parent–child: One atomic query serves as the parent, while the other serves as the child, with the child semantically depending on or refining the parent. (\(ii\)) Sibling: Two queries are semantically independent and serve as sibling nodes at the same level of LQTs. (\(iii\)) Unrelated: Two queries have no meaningful semantic connection and do not share any parent–child or sibling relationship in LQTs.

4.3 Logical Query Tree Construction↩︎

Analogous to LQT construction in database query planning, we extend Selinger’s dynamic programming (DP) paradigm [6] to organize these atomic queries into LQTs. Before DP, we incorporate relation preprocessing to reduce the number of LLM calls. During DP, we propose cycle prevention to ensure that LQTs viewed as directed acyclic graphs (DAGs) stay cycle-free, and context-aware merging to preserve global semantic coherence, ensuring that each local merging aligns with the tree structure. Throughout this process, we evaluate all candidate trees using a multi-dimensional cost model to optimize LQTs. The pseudocode for LQT construction procedure is listed in Appendix B.

4.3.0.1 Relation Preprocessing

To reduce the number of LLM calls required to evaluate potential node merging during DP, we introduce relation preprocessing before DP. In our framework, unrelated relationships between atomic queries are determined during a relation preprocessing stage rather than during the DP process. Given an ERP, we utilize LLMs to semantically evaluate all pairs of atomic queries \((q_i, q_j)\) and categorize them into three types of relationships (‘Unrelated’, ‘Sibling’ and ‘Parent-child’). Specifically, the notion of unrelated query pairs, together with representative examples, is incorporated into the LLM prompt to guide the model in identifying unrelated atomic query pairs. The identified relationships are cached during the stage. As shown in Figure 2, we mark unrelated relationships between atomic queries. By observing a large number of samples, we find that LLMs can accurately identify unrelated query pairs (Section 6.4). Therefore, all query pairs labeled as “Unrelated” are immediately pruned without LLM invocation during DP. The detailed prompts for determining relationships between atomic queries are introduced in Appendix A.

4.3.0.2 Cycle Prevention

To preserve the DAG structure of LQTs, the algorithm prevents cycles by first checking whether merging the two nodes would introduce a cycle during DP. If so, the merging is disallowed.

4.3.0.3 Context-Aware Merging

To ensure that each local node merging aligns with the tree structure, we introduce context-aware merging to determine whether the “parent–child” relationship exists between two nodes. The key idea is to incorporate the partially constructed LQT into the LLM prompt, enabling the evaluation of the semantic compatibility of candidate nodes. Consequently, the technique improves the quality of resulting LQTs by grounding each node merging in the evolving context.

4.3.0.4 Cost Model

Unlike traditional database cost models that estimate physical execution cost (I/O, CPU, and memory) based on well-defined schemas and statistics, our proposed cost model is designed to evaluate the quality of LQTs from both structural and semantic perspectives. It evaluates LQTs in terms of structural soundness and derivational quality, while incorporating semantic consistency and alignment with the original query as optimization objectives. Specifically, the cost of a candidate tree is evaluated from the following five aspects³:

\(\bullet\) Tree size (ts): It is the number of nodes in LQTs. A larger tree size encourages the inclusion of as many atomic queries as possible, thereby preventing the loss of essential semantic units and ensuring that the reasoning chain remains complete.

\(\bullet\) Structural density (sd): It is the number of edges in LQTs. A sufficiently dense structure reflects rich semantic dependencies among atomic queries, which helps retain their interconnectedness.

\(\bullet\) Tree depth (td): It is the maximum distance from the root to any leaf node. Controlling depth prevents trees from degenerating into a long linear chain, which introduces sequential bottlenecks and amplifies propagation.

\(\bullet\) Tree balance (tb): The tree’s balance is measured by subtree height differences. A balanced tree structure helps further improve parallel efficiency while preventing the tree from degenerating into an overly deep linear chain.

\(\bullet\) Semantic similarity (ss): We transform LQTs into natural language and measure the similarity to the original query using BGE [32]. This dimension guides the optimizer by enforcing alignment with the original query intent, anchoring the constructed tree to the original query and ensuring that the planning remains semantically accurate. The full prompts are introduced in Appendix A.

Formally, let the candidate tree be \(\mathcal{T} = (V, E)\), where \(V\) and \(E\) denote the set of nodes (atomic queries) and directed edges, respectively. The total cost is defined as: \[\text{Cost}(\mathcal{T}) = - \Bigl( |V| + |E| - \text{Depth}(\mathcal{T}) - \text{Balance}(\mathcal{T}) + \alpha \, \text{Sim}(\mathcal{T}) \Bigr), \label{eq2}\tag{1}\] where \(|V|\) denotes \(\mathcal{T}\)’s size, \(|E|\) represents \(\mathcal{T}\)’s structural density, \(\text{Depth}(\mathcal{T})\) measures \(\mathcal{T}\)’s depth, \(\text{Balance}(\mathcal{T})\) quantifies \(\mathcal{T}\)’s balance, and \(\text{Sim}(\mathcal{T})\) captures the semantic similarity. Tree size \(|V|\) and structural density \(|E|\) are treated as positive contributors, encouraging coverage of more semantic units. In contrast, tree depth \(\text{Depth}(\mathcal{T})\) and tree balance \(\text{Balance}(\mathcal{T})\) are included as negative terms to discourage overly deep or unbalanced structures. The semantic similarity term \(\text{Sim}(\mathcal{T})\) is scaled by a factor of \(\alpha\) (\(\alpha > 1\)) to amplify its role in aligning the constructed tree with the original query intent, thereby avoiding semantic deviation. The cost model is a multi-objective trade-off, not a simple preference for larger plans. Tree size and structural density serve as positive terms, while tree balance and depth act as negative terms. This design encourages high coverage of atomic queries while preventing the plan from degenerating into linear structures. In addition to this, redundancy is discouraged by the semantic similarity term (weighted by \(\alpha\)), which measures each node’s alignment with the original query intent. Repetitive or irrelevant substructures reduce this score and are penalized. Furthermore, the DP search evaluates alternative structures covering the same atomic queries, selecting the plan with the lowest cost. Redundant decompositions often increase depth or reduce semantic alignment, making them unlikely choices. To simplify the formulation and maintain balanced contributions across dimensions during initial optimization, we assign equal linear coefficients to each dimension except for \(\text{Sim}(\mathcal{T})\). The DP algorithm enumerates all possible construction orders and selects the optimal LQT with the minimal cost: \[\mathcal{T}^* = \arg\min_{\mathcal{T}} \text{Cost}(\mathcal{T}).\] Overall, unlike database query optimization—which relies on well-defined statistics and physical cost metrics—the “optimal LQT” in our approach is optimal only under a heuristic and LLM-driven function. Therefore, our method is better viewed as a structured search strategy rather than traditional cost-based optimization. Due to the heuristic nature of the cost estimates, the DP optimality guarantee from database query optimization does not directly apply to our LQT setting. Nevertheless, PlanRAG remains a structured and database-inspired planning method that effectively guides semantic compositions, without claiming equivalent theoretical guarantees.

4.4 Execution Strategy over Logical Query Trees↩︎

After obtaining the optimized LQT, we iteratively perform bottom-up aggregation, rewriting, retrieval, and generation over LQTs. In LQTs, each node \(v\) represents an atomic query. The processing differs between leaf and non-leaf nodes.
Leaf nodes retrieve directly from the corpus and generate answers: \[\mathrm{Ans}(v) = \mathrm{Generate}\bigl(\mathrm{Retrieve}(v)\bigr).\] Non-leaf nodes first aggregate the queries and answers of their child nodes as context to guide rewriting the original queries. Then, we use the rewritten queries to retrieve passages and generate answers: \[\begin{gather} \mathrm{Ctx}(v) = \mathrm{Aggregate}\!\left( \{ (v, u, \mathrm{Ans}(u)) \mid u \in \mathrm{Children}(v) \} \right), \\ v' = \mathrm{Rewrite}\!\left(v, \mathrm{Ctx}(v)\right), \\ \mathrm{Ans}(v') = \mathrm{Generate}\!\left( \mathrm{Retrieve}(v') \right), \end{gather}\] where \(\mathrm{Aggregate}(\cdot)\), \(\mathrm{Rewrite}(\cdot)\), \(\mathrm{Retrieve}(\cdot)\), and \(\mathrm{Generate}(\cdot)\) are aggregation, rewriting, retrieval, and generation operations, respectively. The prompts for rewriting queries are introduced in Appendix A. To enhance computational efficiency and fully leverage parallelism, we follow the DAG’s topological order and execute in parallel all nodes using multi-threading. This layer-by-layer execution continues until the root node is processed.

4.5 Prompt Interaction and Orchestration↩︎

Our framework involves multiple LLM prompts across different stages, which interact in a structured pipeline. Specifically, the output of each stage serves as the input to subsequent steps, forming a coherent information flow.
(1) In the atomic query generation, the LLM decomposes the ERP into atomic queries using prompt1 in Figure 2.
(2) In the relation preprocessing stage, prompt2 in Figure 2 is applied to determine semantic relationships between atomic queries, and the identified unrelated pairs are cached for subsequent pruning during LQT construction.
(3) During LQT construction, the LLM is further invoked for context-aware merging, where the partially constructed tree is incorporated into the prompt (prompt3 in Figure 2) to guide local decisions.
(4) In the cost modeling stage, we prompt (prompt4 in Figure 2) the LLM to transform candidate LQTs into natural language queries, which are then compared with the original query to estimate semantic alignment.
(5) In the execution stage, we use LLMs (prompt5 in Figure 5) to aggregate the queries and answers of child nodes as context, and use this context to rewrite the atomic query for subsequent retrieval and answer generation.
This staged design ensures that intermediate representations (atomic queries, relations, and partial LQTs) are explicitly passed between prompts, enabling coordinated steps across the pipeline.

4.6 Complexity Analysis↩︎

4.6.0.1 Time Complexity of LQT Construction

Our method focuses on constructing LQTs using Selinger’s dynamic programming algorithm. Although the algorithm has exponential theoretical time complexity, with a classical upper bound of \(\mathcal{O}(n^{2} 2^{n})\), a single query is rarely decomposed into more than 15 atomic queries in practical ERP scenarios by our statistics. The cases with more than 15 atomic queries are extremely rare, whereas most queries involve fewer atomic queries, making the search space acceptable. Our approach remains feasible even in more complex scenarios involving over 20 atomic queries, while preserving plan quality and execution efficiency. The dominant cost in ERPs does not come from planning but from LLM invocations. Redundant planning steps may introduce redundant retrieval and unnecessary LLM calls during planning. In contrast, the search times of DP are negligible compared with downstream costs. Therefore, identifying a better execution structure during planning provides practical benefits: it reduces unnecessary LLM calls, improves retrieval efficiency, and controls overall system cost. During DP, any pair labeled as ‘Unrelated’ is immediately pruned without invoking the LLM. Let \(p_0\) denote the accuracy of detecting ‘Unrelated’ pairs, then the expected number of LLM calls during DP can be approximated as: \[\mathbb{E}\!\left[N_{\mathrm{DP}}\right] \;\simeq\; (1 - p_0)\,\binom{n}{2}.\]

Without relation preprocessing, DP must repeatedly invoke the LLM to assess every candidate pair during search, causing the number of LLM calls to grow exponentially with \(n\) and resulting in more several-fold LLM calls. In typical scenarios, the DP enumeration accounts for only a small fraction of the total runtime (around \(5\%\)), while retrieval and LLM calls dominate (about \(90\%\)). Thus, despite the exponential theoretical complexity of DP, relation preprocessing and a relatively small number of atomic queries keep the actual runtime affordable, demonstrating the practical efficiency of our methods in real-world applications.

4.6.0.4 Time Complexity of LQT Execution

The LQT execution follows a bottom-up dependency order, where each node can be processed only after all of its child nodes are processed. Independent nodes can be executed in parallel to reduce runtime, and the total execution cost is \[T_\mathrm{total} = \mathcal{O}\!\bigl(d (T_{\mathrm{LLM}} + T_{\mathrm{retrieval}})\bigr),\] where \(d\) is the LQT’s depth, \(T_{\text{LLM}}\) and \(T_{\text{retrieval}}\) denote the average latency of each LLM call and retrieval, respectively. In the best case, where the LQT is well-balanced, the depth is \(d = \log n\). The total parallel execution cost is \[T_\mathrm{best} = \mathcal{O}\!\bigl( \log n (\,T_{\mathrm{LLM}} + T_{\mathrm{retrieval}}\,) \bigr).\] In the worst case, the LQT degenerates into a linear chain of depth \(n\), where all nodes are sequentially dependent, i.e., \(d = n\). In this scenario, the execution cost becomes \[T_\mathrm{worst} = \mathcal{O}\!\bigl(n (T_{\mathrm{LLM}} + T_{\mathrm{retrieval}})\bigr).\]

4.7 WikiWeb-ERP↩︎

To the best of our knowledge, there is currently no dedicated benchmark specifically designed for ERPs. As shown in Table 2, existing datasets contain a relatively low proportion of ERPs. To comprehensively evaluate our PlanRAG’s performance specifically on ERPs, we have constructed and released a high-quality dataset WikiWeb-ERP tailored for RAG systems. The construction procedure of WikiWeb-ERP is as follows.

First, we collect ERPs from two complementary aspects to ensure diversity and representativeness. Specifically, (\(i\)) Dataset Sampling: We selected QA pairs from several existing datasets (BrowseComp [21], BrowseComp-Plus [33], BrowseComp Long Context [21], and GAIA [3]) to guarantee data reliability and cross-dataset comparability. (\(ii\)) Generative Expansion: We adopt the query-generation approach proposed by WebSailor [4] to further expand these QA pairs, which models real-world Internet information flows in practical and open-domain scenarios.

Similarly, we construct the document collection from two sources. First, we combine dense and sparse retrieval techniques to retrieve candidate documents from the Wikipedia dump related to each query as the first document source. Second, we use the web collection method in WebSalior [4] to crawl real webpages from the Internet for each query, forming the second document source. These webpages capture the distribution of real-world knowledge and inherent noise in open-domain information. Together, the two types of documents constitute the document collection of WikiWeb-ERP, ensuring authenticity and diversity of retrieval sources.
Overall, WikiWeb-ERP comprises 3,536 queries and 53,682 documents. Of these queries, 2,405 originate from existing datasets, while 1,131 are generated via WebSailor [4]. In terms of documents, 24,050 are retrieved from the Wikipedia dump, and 29,632 are crawled from real webpages. The average lengths are 93.48 words per query and 121.09 words per document, respectively.

5 Experiments↩︎

5.1 Evaluation Metrics↩︎

Following prior work on RAG and multi-hop QA [34], we evaluate model performance using four complementary metrics: Accuracy (Acc), Exact Match (EM), Token-level F1 (F1) and Semantic Accuracy (Acc\(\dagger\)). These metrics jointly assess factual correctness, lexical overlap, and semantic consistency, which are particularly important for ERPs. (\(i\)) Acc measures whether the generated answer adequately captures the key content of ground-truth answers. (\(ii\)) EM measures the degree of exact match between generated and ground-truth answers. (\(iii\)) F1 evaluates the token-level similarity between generated and ground-truth answers. (\(iv\)) We also compute Acc\(\dagger\) using gpt-3.5-turbo-instruct for a more thorough evaluation, where the LLM evaluates the correctness of generated answers, taking ground-truth answers as reference.

5.2 Baselines↩︎

To ensure a comprehensive evaluation, we compare our PlanRAG with DirectLLM and NaiveRAG [1], along with two major families of advanced RAG systems. Iteration-based methods include RetGen [19], GenGround [20], DualRAG [34] and KiRAG [35], which perform retrieval and generation iteratively along a sequential reasoning chain. In contrast, graph-based methods include ChainRAG [36], HopRAG [17], and LEGO-GraphRAG [18], which construct document/reasoning graphs to capture multi-hop dependencies and retrieve evidence along graph paths.

\(\bullet\) DirectLLM generates answers without retrieving external knowledge.

\(\bullet\) NaiveRAG retrieves documents once and generates answers based on the retrieved documents.

\(\bullet\) RetGen enhances LLMs with an iterative retrieval-generation synergy strategy to answer a multi-hop question.

\(\bullet\) GenGround iteratively generates and grounds answers with retrieved evidence to improve multi-hop question answering.

\(\bullet\) DualRAG jointly ranks queries and documents using multi-view relevance scoring.

\(\bullet\) KiRAG enhances iterative retrieval-augmented generation by using knowledge triples to build reasoning chains.

\(\bullet\) ChainRAG iteratively rewrites sub-questions and retrieves sentences via a sentence graph to address missing entities for multi-hop QA.

\(\bullet\) HopRAG constructs a passage graph using pseudo-queries and performs multi-hop reasoning through a ‘retrieve-reason-prune’ mechanism.

\(\bullet\)LEGO-GraphRAG modularizes GraphRAG retrieval into subgraph-extraction and path-retrieval modules to enable flexible construction and systematic evaluation of instances.

5.3 Implementation Details↩︎

We conduct all experiments on three NVIDIA A800 80GB GPUs. In this paper, we use BM25 as the retriever and employ LLaMA-3-8B as the base model for all methods. Given that documents in the WikiWeb-ERP dataset are inherently concise, with lengths consistently below the standard chunk size of 10,000 tokens, we treat each entire document as a single passage without further segmentation. In addition, we dynamically set the thread count as the smaller value between the available cores and the number of independent nodes in the current layer, typically ranging from 4 to 7, which helps avoid thread-switching overhead while maximizing concurrency. Throughout our pipeline, we use GPT-4o-mini for atomic query generation, relation preprocessing, context-aware merging, and query rewriting. We set the scaling factor \(alpha\) in Equation 1 to 10 through grid search to avoid deviating semantically.

For ChainRAG, DualRAG, KiRAG and LEGO-GraphRAG, we reproduce the results on our dataset WikiWeb-ERP using the standard implementations released by the original authors. For ChainRAG, we adopt the context integration setting that utilizes contexts retrieved by sub-questions to generate answers [36]. For RetGen, GenGround and HopRAG, we replicate the experiments on our dataset following the parameter settings reported in their papers. For LEGO-GraphRAG, we build graphs from the corpus via Microsoft GraphRAG [37] before retrieval.

5.4 Main Results↩︎

As shown in Table 3, our approach (PlanRAG w/ Ret) achieves state-of-the-art performance on our WikiWeb-ERP dataset⁴, with the best results highlighted in bold and the second-best results underlined for clarity, where w/ Ret and w/o Ret indicate external retrieval is enabled and absent in PlanRAG framework⁵, respectively. The results show that compared with DirectLLM and NaiveRAG, PlanRAG w/ Ret achieves a significant gain, demonstrating the effectiveness of our framework on ERPs. PlanRAG w/ Ret also outperforms several advanced iteration-based RAG methods, including RetGen, GenGround, DualRAG, and KiRAG, which generally follow a chain-like process of decomposition, retrieval and generation. However, such iterative mechanisms often lack global planning between retrieval and generation, resulting in irrelevant document retrieval and error accumulation. In contrast, our framework performs global planning before generation, optimizing LQTs through dynamic programming and ensuring better alignment between retrieval and generation. Moreover, our framework surpasses graph-based RAG methods (ChainRAG, LEGO-GraphRAG and HopRAG), which leverage graph structures to retrieve logically connected information for multi-hop QA. While these methods improve retrieval recall by exploring graph neighborhoods, they often introduce computational overhead for graph construction and traversal, and may still propagate errors through spurious connections. The global planning mechanism in PlanRAG directly optimizes the retrieval path through dynamic programming, thus leading to more robust performance. Finally, the fact that PlanRAG w/ Ret and PlanRAG w/o Ret both outperform NaiveRAG and RetGen, confirming that the performance improvement is attributed to our planning mechanism rather than retrieval alone.

5.5 Ablation Study↩︎

We perform ablation studies on LQT construction to verify the effectiveness of our proposed method. As shown in Table 4, we remove relation preprocessing, cycle prevention and context-aware merging to evaluate their impacts on the overall performance of PlanRAG. Notably, removing relation preprocessing (w/o pc) does not cause a significant performance degradation, because relation preprocessing primarily reduces system cost (such as runtime, token cost and the number of LLM calls) rather than directly improving generation quality. Removing cycle prevention (w/o cp) causes significant performance degradation, demonstrating that the mechanism is critical for maintaining LQT structure and preventing logical errors induced by cycles. Similarly, disabling context-aware merging (w/o ca) leads to a performance drop, highlighting the importance of the partially constructed tree to maintain semantic coherence throughout the planning process.

To evaluate the effectiveness of the cost model in guiding LQT construction, we also evaluate the performance of PlanRAG’s ablated variants without each dimension in the cost model. Across all variants, the results in Table 4 consistently show that removing any single dimension leads to a degradation in overall performance, indicating that each contributes to the optimization objective. These findings highlight the significance of incorporating all five dimensions to achieve structural robustness and semantic soundness in LQT construction. Notably, the exclusion of the semantic similarity (w/o ss) results in the most significant decline. While structural regularization terms (e.g., tree depth or balance) in the cost model regulate execution efficiency, semantic similarity serves as a global alignment signal that prevents LQTs from drifting away from the original intent, suggesting that effective planning for ERPs requires semantic anchoring.

5.6 Robustness Across Different Base Models and Retrievers↩︎

5.6.0.1 Base Models

To verify the generalization ability of our framework across different LLMs, we also conduct experiments using various LLMs as base models, including Llama-3-70B, Llama-2 (7B/13B/70B), and Qwen-2.5 (7B/14B/72B). For each base model, we compare the performance of NaiveRAG, PlanRAG w/o Ret and PlanRAG w/ Ret. As shown in Table 5, PlanRAG w/ Ret consistently yields performance improvements across all model scales and base models, demonstrating that the effectiveness of our framework is model-agnostic. Notably, the improvements are more significant for the models at smaller parameter scales (e.g., 7B and 13B), suggesting that our planning strategy compensates for their limited parametric knowledge and capacity. This observation highlights the potential of our method to enhance RAG systems even under constrained computational budgets.

5.6.0.2 Retrievers

In addition to varying base models, we further evaluate our framework across diverse retrievers, including BGE-small [32], Contriever [38], and ColBERT [39]. The experimental results in Table 6 consistently indicate that our framework surpasses NaiveRAG and PlanRAG w/o Ret across all retrievers, demonstrating that our framework’s performance is robust and retriever-agnostic.

5.7 Efficiency Analysis↩︎

5.7.0.1 Relation Preprocessing’s Impact on LQT Construction’s Efficiency

To verify the effect of relation preprocessing on LQT construction, we compare time, token cost and the number of LLM calls with and without the component. Table 7 reports the results on 100 sampled queries from WikiWeb-ERP. Obviously, enabling relation preprocessing reduces the average LQT construction time from 82.8s to 8.4s, decreases the number of LLM calls from 63.6 to 10.4, and lowers token cost from 3,454.4 to 1,265.2. Together with the results in Table 4, this optimization significantly reduces computational cost without sacrificing generation quality.

5.7.0.2 Parallel Execution’s Impact on LQT Execution’s Efficiency

To verify the effect of parallel execution on LQT execution, we compare single-threaded sequential execution (w/o parallel) with multi-threaded parallel execution (w/ parallel) for LQT execution on 100 randomly sampled queries from WikiWeb-ERP. Table 7 shows that parallel execution reduces the average execution time from 18.7s to 7.3s, achieving a 2.56\(\times\) speedup. This improvement arises from the structural properties of LQTs, allowing nodes to be executed in parallel. Notably, the parallel execution primarily reduces execution time, while it does not reduce the number of LLM calls or token cost. Overall, these findings demonstrate that parallel execution is effective in enhancing efficiency, enabling PlanRAG to achieve high accuracy while meeting real-time performance demands in practical deployments.

5.7.0.3 System Cost Comparisons

To better evaluate the efficiency of PlanRAG, we compare its system cost with various baselines, reporting the average token cost, runtime, and peak GPU memory usage over 100 samples, respectively. Figure 3 shows clear divergences in system cost across different RAG systems. These iteration-based baselines rely on multiple rounds of retrieval and generation, where accumulated errors often trigger additional LLM calls, increasing token consumption. Their inherently sequential workflows prevent parallel execution, further increasing overall runtime. Graph-based baselines introduce substantial overhead in graph construction and traversal. As the graph grows larger, redundant nodes and irrelevant edges accumulate quickly, thereby inflating resource usage. Compared with these baselines, PlanRAG employs the global planning mechanism to reduce redundant retrieval and unnecessary inference. It makes the execution more focused and amenable to parallelization. Although planning introduces an initial cost, the overall workflow becomes more streamlined, resulting in a superior cost–efficiency trade-off in terms of system cost and performance.

5.8 Results on Multi-Hop QA↩︎

To further validate the generality of PlanRAG beyond ERPs, we evaluate our method on four widely used multi-hop QA benchmarks, including HotpotQA [40], MuSiQue [41], 2WikiMultiHopQA [42], and StrategyQA [43]. As shown in Table 8, PlanRAG achieves competitive performance across most datasets and obtains the best result on StrategyQA, demonstrating its generalization ability beyond ERPs. In particular, PlanRAG performs comparably to graph-based baselines on HotpotQA and MuSiQue, but shows a gap on 2WikiMultiHopQA, whose reasoning chains are more explicit and therefore better suited to graph-based retrieval methods. In contrast, PlanRAG is mainly designed for ERPs with ambiguous dependencies, where explicit reasoning chains are not present, and our method can perform explicit query planning to effectively improve performance.

6 Further Analysis and Discussions↩︎

6.1 Sensitivity Analysis of Scaling Factor \(\alpha\)↩︎

To further validate the effectiveness of the scaling factor \(\alpha\) in the cost model, we conduct a sensitivity analysis. Specifically, we vary \(\alpha\) within the range \([1, 20]\) and evaluate the final accuracy. Figure 4 (a) shows that performance first improves and then stabilizes as \(\alpha\) increases, reaching the highest accuracy at \(\alpha = 10\); further increasing \(\alpha\) yields limited gains or slight degradation. From a scaling perspective, the structural terms (tree depth or balance) grow with the number of nodes, whereas the semantic similarity term is normalized within \([0,1]\), leading to a scale mismatch. The introduction of \(\alpha\) serves to align their contributions. These results indicate that \(\alpha\) is not an arbitrary tuning parameter, but plays a critical role in balancing structural regularization and semantic alignment, with its optimal value corresponding to a well-calibrated trade-off between the two.

6.2 Performance and Cost Comparisons Across Query Complexity↩︎

6.2.0.1 Performance Comparisons Across Query Complexity

To further examine the robustness of PlanRAG varying query complexity⁶, we categorize queries into the buckets of size \(\{5, 6, 7, 8, 9, >9\}\) based on the number of atomic queries, and report the average accuracy within each bucket. This setup reflects the intuition that a larger number of atomic queries generally implies deeper dependency chains. The results in Figure 4 (b) show that PlanRAG consistently outperforms the baselines across all buckets. Notably, while all methods exhibit performance degradation as the number of atomic queries increases, PlanRAG demonstrates a significantly slower decline. PlanRAG explicitly encodes dependencies and performs global structural optimization, which localizes errors and prunes suboptimal plans early. Moreover, its structural regularization terms (e.g., tree depth and balance) in the cost model prevent planning from degenerating into long chains, leading to more stable performance under high complexity. Overall, these results emphasize the effectiveness of PlanRAG in scaling to high-complexity queries beyond conventional RAG pipelines.

6.2.0.2 System Cost Comparisons Across Query Complexity

To assess the system cost of PlanRAG when increasing query complexity, we analyze system cost as a function of the number of atomic queries \(n\). We bucket the ERPs in WikiWeb-ERP according to \(n \in \{5, 6, 7, 8, 9, >9\}\) and measure four metrics: (a) token cost, (b) runtime, (c) peak GPU memory, and (d) the number of LLM calls. As shown in Figure 5, the values of all four metrics increase as the number of atomic queries \(n\) grows. Specifically, token cost and the number of LLM calls grow approximately linearly with \(n\), reflecting the expansion of intermediate steps as LQTs increase in size. Runtime also increases with \(n\), while peak GPU memory rises from around 9.0 GB at \(n=5\) to nearly 12 GB at \(n>9\), due to the accumulation of KV cache and intermediate results during execution. Overall these results demonstrate that PlanRAG exhibits a predictable increase in system cost as query complexity grows, confirming its scalability for complex queries.

6.3 Evaluation of LQT Quality↩︎

To examine the effectiveness of our LQT construction method, we conduct a comparative evaluation between LQTs generated by our method and those directly produced by LLMs. The evaluation prompts for LLMs are listed in Appendix A, which measures whether LQTs exhibit structural robustness and semantic soundness. Each LQT’s quality is evaluated using a 4-point (\(1\sim 4\) score) ordinal scale as below, by human annotators and the LLM judge, respectively.

4 – Excellent: The LQT exhibits a well-formed and stable structure with clearly defined dependencies among atomic queries, while maintaining strong semantic alignment with the original query intent throughout the tree.

3 – Good: The LQT is largely structurally coherent and semantically consistent, with minor structural imperfections or slight semantic ambiguities that do not undermine the overall process.

2 – Fair: The LQT shows noticeable structural weaknesses (e.g., missing or improper dependencies) or semantic inconsistencies that partially affect the correctness of the workflow.

1 – Poor: The LQT lacks structural robustness and semantic soundness, exhibiting disorganized dependencies and significant semantic drift.

The final score \(S\) is computed as the average score over all 30 generated LQTs: \(S = \frac{1}{30} \sum_{i=1}^{30} s_{i}.\) where \(s_i\) denotes the score assigned to the LQT. Table 9 reports the scores of human assessment and LLM judge, respectively. The results show that the LQTs constructed by our method have better quality than the LQTs directly generated by the LLM. Furthermore, we construct an ablated variant by removing the semantic similarity from the cost model and evaluate the resulting LQTs. The quality drops noticeably, indicating that semantic similarity plays a critical role in maintaining the semantic alignment of LQTs. Specifically, a powerful LLM could directly generate a plan in a single step. However, this approach often lacks stable structural constraints, and different invocations may produce inconsistent or dependency-violating plans. In contrast, we first decompose complex queries into atomic queries and then construct an LQT with explicit structural constraints, ensuring clear dependencies and executable reasoning.

The linear graph sometimes generated by LLMs is not necessarily optimal for ERPs. In many cases, some atomic queries are semantically independent and can be executed in parallel. For example, in Figure 1, identifying candidate authors (and their death years) and retrieving candidate chronologies are largely independent tasks and can be performed separately before being aligned through the constraint that the chronology’s final year matches the author’s death year. Therefore, LQT organizes these queries into a tree rather than a strict linear chain, reducing sequential dependency and error propagation. Notably, the linear structure generated by Claude resembles the sequential reasoning strategy used in baselines such as ReTGen and GenGround, while PlanRAG significantly outperforms them in Table 3, highlighting the benefit of tree-structured planning.

6.4 Fine-grained Analysis on LQT Construction↩︎

To evaluate LQT construction more comprehensively, we further analyze 100 randomly sampled queries from four critical aspects: atomic query generation, atomic query coverage, linear degradation rate, and relationship classification accuracy. The evaluation results are listed in Table 10.

6.4.0.1 Atomic Query Generation

To evaluate the accuracy of atomic query generation, we conduct a manual assessment on 100 randomly sampled queries. The evaluation results indicate that the atomic queries generated by LLMs achieve 98.5% accuracy. The reported 98.5% accuracy is obtained through manual annotation of the generated atomic queries and their corresponding triples, where multiple annotators independently evaluate the correctness of each triple based on predefined criteria. Specifically, inter-annotator agreement is assessed using Fleiss’s kappa, achieving \(k\) = 0.82, which indicates strong agreement among annotators. It demonstrates that our decomposition method can extract the minimal semantic units from the original ERPs, thereby providing a reliable foundation for the subsequent LQT construction.

6.4.0.2 Atomic Query Coverage

To verify that LQTs have high atomic query coverage, we systematically count the number of atomic queries in all generated LQTs. The results show that PlanRAG achieves full coverage of all atomic queries in 94.2% of cases. It demonstrates that our planning mechanism can integrate the vast majority of atomic queries, thereby supporting execution grounded in a complete chain of atomic queries.

6.4.0.3 Linear Degradation Rate

Given the ERPs characterized by inherent high uncertainty and difficulty in reduction, our planning mechanism explicitly organizes dependencies through LQT’s structure. In the ideal case where semantic relationships between atomic queries are clear and easily distinguishable, PlanRAG constructs well-structured LQTs. However, in the worst case, where atomic queries are largely semantically independent, LQTs may degrade into an approximately linear chain structure. To quantify the frequency of such occurrences, we conduct structural analysis on the generated LQTs. The results show that only 3.2% of queries exhibit a near-linear structure, while the vast majority of queries (over 96%) maintain explicit tree-like dependency relationships.

6.4.0.4 Relationship Classification

As highlighted in Section 4, we leverage LLMs to identify unrelated relationships in relation preprocessing. To assess the reliability of the classification, we manually verify the predicted semantic relationships and measure their classification accuracy. The results show that LLMs achieve 96.4% classification accuracy for unrelated relationships, while the accuracies for parent-child and sibling relationships are 83.1% and 87.9%, respectively. High accuracy for unrelated relationships demonstrates that relation preprocessing can improve the efficiency of LQT construction.

6.5 Stage-level Robustness Analysis↩︎

6pt

To analyze stage-level robustness, we conduct controlled perturbation experiments to examine how errors propagate through the PlanRAG pipeline in Table 11. We randomly sample 100 queries from the dataset and inject noise at three stages, with noise levels of 10%, 20%, and 30%. (1) Atomic query generation: we randomly remove atomic queries to simulate incomplete or noisy decomposition. (2) Relation classification: we randomly select edges and replace their relations with randomly chosen labels (parent–child, sibling, or unrelated), thereby perturbing the tree structure. (3) LQT execution: we replace retrieved contents with irrelevant text to simulate retrieval and reasoning errors. For each stage, we vary the noise level while keeping the other stages unchanged and evaluate the impact on final answer accuracy. Results show that performance degrades gradually as noise increases, indicating that errors do propagate across stages. However, the degradation is smooth rather than catastrophic, indicating that PlanRAG is robust to upstream errors, mainly due to its structured planning.

6.6 Error Analysis↩︎

To evaluate the credibility of PlanRAG on ERPs, we categorize the errors in queries into four types: (\(i\)) Planning errors (36%) primarily stem from insufficient recognition of dependencies among atomic queries, resulting in LQTs that can not accurately capture grounding logical orders, thereby compromising overall performance. These errors are typically caused by ambiguous relations or low-confidence merging decisions, highlighting the necessity of more accurate relationship classification. (\(ii\)) Retrieval errors (32%) arise when retrievers only acquire partially relevant but ultimately irrelevant information, or fail to retrieve critical evidence passages, reducing the support for subsequent steps. These errors are often caused by entity mismatches or inadequate query reformulation, suggesting that retrieval robustness can be improved through hybrid retrieval and optimized query rewriting. (\(iii\)) Reasoning consistency errors (19%) occur when individual answers of atomic queries are correct, but their integration into a global reasoning outcome leads to deviations from factual conclusions, reflecting the limitations in global consistency. (\(iv\)) Generation and synthesis errors (13%) are observed during the final answer aggregation stage, manifesting as ambiguous entity references or disrupted output formats, typically caused by the instability in structured representations over long reasoning chains.

Overall, our PlanRAG’s main bottlenecks lie in planning and retrieval, and further performance improvements require the reinforcement of adaptive planning mechanisms and robust retrieval strategies.

7 Conclusion↩︎

In this paper, we propose PlanRAG, an end-to-end RAG framework designed for ERPs motivated by database query planning. PlanRAG first decomposes ERPs into atomic queries. These atomic queries are then organized into optimized LQTs that model semantic dependencies via dynamic programming, mitigating retrieval noise and error accumulation. Based on optimized LQTs, PlanRAG iteratively executes aggregation, rewriting, retrieval, and generation in a bottom-up and parallel manner, recursively propagating intermediate results to efficiently yield the final answer. Extensive experiments on the newly released WikiWeb-ERP dataset demonstrate consistent improvements over iteration-based and graph-based RAG baselines, while further analyses confirm the efficiency, effectiveness and interpretability of our proposed planning mechanism.
We acknowledge that our method has several limitations. First, PlanRAG struggles to generalize to simple problem scenarios, as its planning mechanism may be unnecessary for straightforward queries. Second, for queries with low logical complexity or clear stepwise paths, the method may degenerate into a standard multi-hop QA decomposition paradigm. Additionally, our cost model is a simplified abstraction and does not explicitly normalize costs based on factors such as document length or task complexity. Its goal is not to precisely estimate the true execution cost of each semantic query, but rather to provide a lightweight heuristic to guide plan selection. While different subplans may share the same modeled cost yet differ in actual execution overhead, variations in retrieval and reasoning cost are partially reflected through semantic similarity and structural terms, which help prioritize more coherent and efficient plans. Moreover, we plan to incorporate fine-tuning strategies to reduce reliance on LLMs in components such as atomic query generation, relation preprocessing, and query rewriting, by replacing GPT-4o-mini with lightweight open-source models (e.g., LLaMA and Qwen families). Lastly, we will explore how to map LQTs into a physical query plan, incorporating system-level optimizations such as caching mechanisms to provide a more complete systems-level optimization formulation.

8 Prompts↩︎

{
    ''nodes``: [
        {''id``: ''Q1``, ''query``: ''What were the 
    early Christian hymns?``},
        {''id``: ''Q2``, ''query``: ''Which late   
    antique authors composed Christian hymns?``},
        {"id": ''Q3``, ''query``: ''Which authors  
    passed away around the middle of the 5th century?``},
        {"id": ''Q4``, ''query``: ''Which authors’ 
    years of death coincide with the final year 
                                    of a scientific chronology?``},
        {"id": ''Q5``, ''query``: ''Which     
    scientific chronologies reconstruct environmental 
    conditions from several centuries 
    before the modern era?``},
        {"id": ''Q6``, ''query``: ''What is the     
    name of the scientific chronology?``}
    ],
    ''edges``: [
        {''from``: ''Q1``, ''to``: ''Q2``},
        {''from``: ''Q2``, ''to``: ''Q4``},
        {''from``: ''Q3``, ''to``: ''Q4``},
        {''from``: ''Q4``, ''to``: ''Q6``},
        {''from``: ''Q5``, ''to``: ''Q6``}
    ] 
}

9 Algorithm↩︎

10 Case Study↩︎

To further demonstrate the advantages of our planning mechanism, we compare the detailed results of PlanRAG and ChainRAG on a toy example of ERP. As shown in Figure 7⁷, PlanRAG explicitly identifies dependencies among atomic queries and executes them in topological order, thereby preventing error propagation and ultimately producing the correct answer. In contrast, ChainRAG executes sub-queries sequentially without explicit dependency planning, introducing early errors to propagate and affecting the final result⁸. This comparison result clearly demonstrates that PlanRAG suppresses error propagation through explicit logical planning, enhancing the accuracy and interpretability of RAG systems.

References↩︎