Source-linked AI summary
PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Paths
Boyu Chen, Zirui Guo, Zidan Yang, Yuluo Chen, Junze Chen, Zhenghao Liu, Chuan Shi, Cheng Yang
TL;DR
Graph-based RAG can suffer from redundant retrieval and flat prompt organization. PathRAG prunes the indexing graph to retrieve key relational paths and converts them into textual prompts, outperforming state-of-the-art baselines across six datasets and five evaluation dimensions.
Problem
Current graph-based RAG methods may retrieve redundant information and organize retrieved content flatly, introducing noise and reducing prompt organization quality.
Method
PathRAG uses flow-based pruning to retrieve key relational paths and path-based prompting to present those paths to LLMs.
Results
PathRAG consistently outperforms state-of-the-art baselines across six datasets and five evaluation dimensions.
Takeaways & Limitations
PathRAG provides a graph-based RAG approach that reduces redundant retrieved information while preserving relational paths in the prompt.
Takeaways & Limitations
The authors identify future integration of human evaluation and other semantic-level assessment methods as an evaluation direction.
Abstract
from arXiv · showhide
Retrieval-augmented generation (RAG) improves the response quality of large language models (LLMs) by retrieving knowledge from external databases. Typical RAG approaches split the text database into chunks, organizing them in a flat structure for efficient searches. To better capture the inherent dependencies and structured relationships across the text database, researchers propose to organize textual information into an indexing graph, known asgraph-based RAG. However, we argue that the limitation of current graph-based RAG methods lies in the redundancy of the retrieved information, rather than its insufficiency. Moreover, previous methods use a flat structure to organize retrieved information within the prompts, leading to suboptimal performance. To overcome these limitations, we propose PathRAG, which retrieves key relational paths from the indexing graph, and converts these paths into textual form for prompting LLMs. Specifically, PathRAG effectively reduces redundant information with flow-based pruning, while guiding LLMs to generate more logical and coherent responses with path-based prompting. Experimental results show that PathRAG consistently outperforms state-of-the-art baselines across six datasets and five evaluation dimensions. The code is available at the following link: https://github.com/BUPT-GAMMA/PathRAG
Introduction
PathRAG addresses redundancy and flat prompt organization in graph-based RAG by retrieving key relational paths and presenting them textually to LLMs. It reports consistent gains over state-of-the-art baselines across six datasets and five evaluation dimensions.
- Motivation: Graph-based RAG organizes textual information into indexing graphs to capture dependencies and structured relationships across databases.Nodes represent extracted entities, while edges represent relationships between them.
- Motivation: Previous graph-based RAG methods may retrieve redundant information, introducing noise, increasing token consumption, and producing less logical or coherent answers.GraphRAG uses community information, while LightRAG uses immediate neighbors of query-related nodes and flatly concatenates retrieved content.
- Approach: PathRAG retrieves key relational paths among relevant nodes and converts them into textual form for LLM prompting.Its flow-based pruning algorithm uses distance awareness to identify key paths and reduce noise and token consumption.
- Approach: PathRAG uses flow-based pruning and path-based prompting to retrieve and organize graph information more selectively.The method is designed to improve the structure of information supplied to the generator.
- Results: PathRAG outperforms state-of-the-art baselines across six datasets and five evaluation dimensions.The introduction reports extensive experiments validating the design.
Related Work
Related work spans text-based RAG, KG-RAG, and graph-based RAG. These approaches differ in how they retrieve information and whether they preserve relationships across text segments or graph entities.
- Text-based RAG: Text-based RAG retrieves textual database content using sparse keyword matching or dense vector similarity.Sparse retrieval uses representative words, while dense retrieval addresses lexical mismatches and synonyms through embeddings.
- Text-based RAG: Most text-based RAG methods organize text segments flatly and therefore fail to capture essential relationships between chunks.The missing contextual dependencies can limit the quality of LLM-generated responses.
- KG-RAG: KG-RAG retrieves information about relevant entities and relationships from existing or optimized knowledge graphs.It typically extracts a local subgraph, such as an entity’s immediate neighbors.
- KG-RAG: Most KG-RAG methods focus on questions answerable from a single entity or relation, narrowing their applicability.This scope differs from graph-based RAG’s focus on global-level tasks requiring information across multiple database segments.
- Graph-based RAG: Graph-based RAG organizes text databases as text-associated graphs for global-level tasks requiring information from multiple segments.The graph construction process extracts entities, identifies relationships, and includes contextual descriptive text.
Preliminaries
Graph-based RAG structures a text database as an indexing graph, retrieves relevant graph elements for a query, and integrates their textual content into LLM generation.
- Indexing graph: Graph-based RAG constructs an indexing graph instead of storing text chunks as an unordered collection.This graph is created during preprocessing.
- Indexing graph: Nodes represent distinct entities with identifiers and textual chunks, while edges represent entity relationships with descriptive textual chunks.The indexing graph is denoted G = (V, E, K_V, T).
- Retrieval and generation: Given a query, a graph-oriented retriever extracts relevant nodes and edges from the indexing graph.The retrieved elements provide the textual evidence used in subsequent generation.
- Retrieval and generation: The system integrates retrieved textual chunks with the query and passes them to an LLM generator to obtain an answer.The workflow focuses on designing an effective graph-oriented retriever and supporting prompt template.
Methodology
PathRAG retrieves relevant graph nodes, prunes relational paths between them using flow and distance awareness, and presents reliable paths to an LLM in a structured prompt. Its design targets redundancy, preserves endpoint relations, and maintains acceptable retrieval complexity.
- Framework: PathRAG operates through node retrieval, path retrieval, and answer generation on an indexing graph.Relevant nodes are retrieved from query keywords; relational paths are then pruned and prioritized before prompting the LLM.
- Node Retrieval: Dense vector matching retrieves a predefined number N of nodes related to LLM-extracted query keywords.Keywords are extracted from the query, encoded with node identifiers, and matched using embedding similarity.
- Path Retrieval: A flow-based pruning algorithm with distance awareness propagates resources from each start node to identify key paths between retrieved node pairs.Information decays along edges, and paths are pruned early when node resources fall below a threshold.
- Path Retrieval: Path reliability is measured from average resource values flowing through its edges, retaining the top-K paths across retrieved node pairs.Reliable path-reliability pairs enter a global candidate pool before top-K selection for query retrieval.
- Answer Generation: Retrieved paths are converted into textual relational paths by concatenating the text of their nodes and edges.This representation retains the semantic relations connecting path endpoints rather than flattening shared nodes and edges.
- Answer Generation: The prompt places the query first and paths in ascending reliability order, positioning the most reliable path at the end.The ordering is designed around LLM long-context behavior and the reported “lost in the middle” issue.
- Efficiency: Candidate-path extraction has complexity O(N^2(1−α)^θ), which is acceptable for the reported retrieved-node range N ∈ [10, 60].Decay and early stopping limit the number of nodes involved in propagation relative to the full indexing graph.
Experiments
PathRAG is evaluated against six state-of-the-art baselines across diverse datasets, evaluation dimensions, ablations, graph sparsity levels, LLM backbones, and token costs. It consistently outperforms baselines, while path ordering, path-based prompting, robustness, and token efficiency are further examined.
- Experimental Setup: Experiments compare PathRAG with six state-of-the-art text-based, knowledge-graph-based, and graph-based RAG methods across eight datasets.Datasets range from 180,000 to 5,000,000 tokens; GPT-4o-mini is used uniformly as the base model, with ten-trial averaging for randomized components.
- Main Results (RQ1): PathRAG consistently outperforms baselines across all evaluation dimensions and datasets, including Comprehensiveness, Diversity, Logicality, Relevance, and Coherence.Its average win rates across dimensions are 62.52%, 65.37%, 60.68%, 59.92%, and 59.43%, respectively.
- Main Results (RQ1): 7.06% average improvement over the best baseline is achieved on BLEU, ROUGE, and METEOR evaluation using human-written SQuALITY summaries.This evaluation measures alignment between generated answers and reference summaries.
- Ablation Study (RQ2): 56.44% and 55.64% average win rates against random and hop-first variants, respectively, support the necessity of path ordering in prompts.The ablation compares PathRAG with two alternative strategies for ranking retrieved paths.
- Ablation Study (RQ2): 55.19% average win rate for path-based prompts over flat prompts supports preserving the organization of retrieved information as relational paths.The paper attributes this benefit to the interconnection of node and edge information within each path.
- Graph Sparsity Analysis (RQ3): Under random removal of 10%–50% of graph edges, PathRAG remains ahead of LightRAG and NaiveRAG on Agriculture and CS.Against NaiveRAG, win rates range from 54.84% to 57.32% on Agriculture and 51.72% to 54.92% on CS; against LightRAG, they range from 50.92% to 53.24% and 52.24% to 53.28%, respectively.
- Performance under Different LLMs (RQ4): 58.36% is PathRAG's average win rate with GPT-4o, compared with 56.48% using DeepSeek-V3 and 53.92% using GPT-4o-mini.PathRAG maintains stable performance across models with varying capabilities.
- Token Cost Analysis (RQ5): 13.69% lower token consumption accompanies significantly better performance for PathRAG, at a corresponding cost of 0.002$.PathRAG-lt reduces token usage by 40.41% while maintaining similar performance to LightRAG, with a 50.56% average win rate.
Conclusion
PathRAG retrieves key relational paths with flow-based pruning and path-based prompting, and its experiments show consistent gains over baselines across six datasets.
- PathRAG retrieves key relational paths from the indexing graph to alleviate noise.
- A flow-based pruning algorithm efficiently identifies key paths for graph-based retrieval.
- Path-based LLM prompting supports answer generation from the retrieved paths.
- PathRAG consistently outperforms baseline methods on six datasets.
- Future work includes optimizing indexing-graph construction, collecting more human-annotated datasets, and exploring substructures beyond paths.