LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora

1 INTRODUCTION

• Large-scale, unstructured corpora distribute relevant information unevenly, while retrieved context can be voluminous, intricate, and poorly organized.Segmenting documents into smaller chunks can lose contextual details needed for retrieval accuracy and complex-task reasoning.Source: §1 · p. 1
• GraphRAG graph-construction errors can introduce noisy, ambiguous context through inaccurate entity relations and globally incoherent structure.Bottom-up community summarization and topic modeling are also described as vulnerable to propagating relationship errors into higher-level abstractions.Source: §1 · p. 2
• LinearRAG replaces costly relation extraction with lightweight entity extraction and semantic linking in a hierarchical graph of entities, sentences, and passages.Its retrieval first activates entities through local semantic bridging, then aggregates global importance with personalized PageRank to retrieve passages.Source: §1 · p. 2
• The relation-free Tri-Graph avoids unstable relation modeling and reduces indexing time by over 77%.The two-stage retrieval mechanism pairs local semantic bridging for entity activation with global importance aggregation for passage recall.Source: §1 · p. 2
• LinearRAG consistently outperforms state-of-the-art baselines in retrieval quality, generation accuracy, and scalability across four benchmark datasets.The authors describe these results as validating its practicality for real-world applications.Source: §1 · p. 3

2 PRELIMINARY STUDY

• The preliminary study attributes GraphRAG's frequent underperformance against naive RAG on traditional tasks to flaws in graph construction.The analysis focuses on how constructed graphs affect retrieval and generation.Source: §2 · p. 3

2.1 PERFORMANCE DEGRADATION IN GRAPHRAG SYSTEMS

• 36.86% to 54.61% context relevance for LightRAG and HippoRAG is below Vanilla RAG's 62.87% on GraphRAG-Bench.GraphRAG methods moderately improve evidence recall, but the study says noisy and ambiguous context offsets that gain.Source: §2.1 · p. 3

2.2 GRAPH QUALITY AND ERROR ANALYSIS

• Relation extraction can create local factual errors and global contradictions because relations are extracted passage by passage without corpus-wide validation.The example of Einstein's Nobel Prize illustrates how a relation can reverse a sentence's meaning.Source: §2.2 · p. 3
• A hierarchy that treats AI subfields and a learning technique as parallel subcategories creates structural ambiguity that misleads retrieval.The example distinguishes NLP and computer vision as AI subfields from unsupervised learning as a technique used within them.Source: §2.2 · p. 4

2.3 DISCUSSION

• Explicit relation extraction is computationally expensive and linguistically difficult, while aligned entities can connect passages and source text preserves contextual relations for LLM inference.The study argues that natural-language relations can be too nuanced or compositional to reduce accurately to atomic triples.Source: §2.3 · p. 4

3 THE FRAMEWORK OF LINEARRAG

• LinearRAG builds a three-node-type graph and retrieves passages in two stages: semantic entity activation followed by personalized PageRank over entity–passage links.The design retains contextual relations in the original passages rather than explicitly extracting them.Source: §3 · p. 4

3.1 TOKEN-FREE GRAPH CONSTRUCTION

• Tri-Graph uses passage, sentence, and entity nodes, with containment and mention links; lightweight NER and sparse matrices support linear updates without LLM token costs.Retaining the original passages preserves contextual information, making the graph construction information-lossless.Source: §3.1 · p. 5

3.2 PASSAGE RETRIEVAL

• Retrieval separates precise entity activation through local semantic bridging from retrieval of globally important passages.The two-stage design is intended to balance precision and recall, particularly for multi-hop queries.Source: §3.2 · p. 5

3.2.1 FIRST STAGE: RELEVANT ENTITY ACTIVATION VIA SEMANTIC BRIDGING

• Semantic bridging seeds query-matched entities, propagates query–sentence relevance through the sentence–entity graph, and prunes activations below threshold δ to find multi-hop connectors.The resulting entities implicitly match relations without requiring an explicitly constructed relational graph.Source: §3.2.1 · pp. 5–6

3.2.2 SECOND STAGE: PASSAGE RETRIEVAL VIA GLOBAL IMPORTANCE AGGREGATION

• Activated entities seed a passage–entity graph, where Personalized PageRank aggregates global importance and ranks passages for top-k retrieval.Entity nodes are initialized with first-stage relevance scores; passage nodes use hybrid initialization.Source: §3.2.2 · p. 6

4.1 EXPERIMENTAL SETTING

• Experiments compare LinearRAG with zero-shot, vanilla-RAG, and GraphRAG baselines on four QA datasets using shared 1,000-question validation samples and generation and retrieval metrics.Source: §4.1 · pp. 7–8

4.2 GENERATION ACCURACY (Q1)

• 63.70% GPT-based accuracy on 2Wiki and 70.20% Contain-based accuracy; LinearRAG outperforms all baselines across datasets, with 3.80% absolute improvement over the second-best baseline.Source: §4.2 · p. 8

4.3 EFFICIENCY ANALYSIS (Q2)

• Complicated graph construction can incur substantial runtime, while processing large retrieved contexts adds fees and latency; lower token costs need not reduce performance.Source: §4.3 · pp. 8–9
• LinearRAG is fastest across the whole pipeline and uses zero tokens; it avoids LLM calls during indexing and retrieval.E2GraphRAG and RAPTOR are more time-efficient during retrieval, but at the cost of reduced model performance.Source: §4.3 · p. 9

4.4 ABLATION STUDY (Q3)

• The ablation identifies semantic-similarity propagation for entity activation and personalized PageRank for global document importance as complementary, critical modules.Source: §4.4 · pp. 9–10, Figure 4 · p. 9

• LinearRAG replaces costly, error-prone relation extraction with lightweight entity extraction and builds a hierarchical graph of entities, sentences, and passages.Source: §5 · p. 10
• Its two-stage retrieval jointly leverages local and global structural information, and experiments report gains in retrieval precision, generation accuracy, and scalability.Source: §5 · p. 10

• The study uses public-resource medical benchmark data, adheres to the ICLR Code of Ethics, and involved no participants.Source: ETHICS STATEMENT · p. 10

• The paper reports data splits, hyperparameters, computational resources, and public sources for baselines, and makes its code and dataset available.Source: REPRODUCIBILITY STATEMENT · p. 10

A DATASETS

• HotpotQA, 2WikiMultiHopQA, MuSiQue, and a medical dataset cover multi-document reasoning and four medical task types.The medical subset contains 4,076 questions across fact retrieval, complex reasoning, contextual summarization, and creative generation.Source: A DATASETS · p. 15

B BASELINE DETAILS

• The baselines include LLM-driven graph traversal, graph neural network retrieval, hierarchical clustering and summarization, and entity-based hierarchical retrieval.These approaches correspond to KGP, G-Retriever, RAPTOR, and E2GraphRAG.Source: B BASELINE DETAILS · p. 15
• Other baselines use entity-relation and thematic structures, Personalized PageRank, document graphs, or enhanced paragraph integration.These descriptions cover LightRAG, HippoRAG, GFM-RAG, and HippoRAG2.Source: B BASELINE DETAILS · p. 15

C MACHINE CONFIGURATION

• The experiments use the machine configuration detailed in Table 3.The supplied passage does not specify the hardware components.Source: C MACHINE CONFIGURATION · p. 16, Table 3 · p. 16

D EFFICIENCY ANALYSIS OF GRAPH CONSTRUCTION: ALL-STAGE LINEAR SCALABILITY

• Graph construction uses O(|P| · T) time and memory, while retrieval has O(|P|) computational complexity.Construction uses lightweight sentence segmentation and named entity recognition, and incurs no LLM token consumption; T is average passage length.Source: D EFFICIENCY ANALYSIS OF GRAPH… · p. 16
• Sparse propagation and Personalized PageRank underpin retrieval's linear-time computation on the bipartite graph.Each propagation step costs O(nnz), with nnz the number of non-zero entries in sparse matrices; PPR computation is O(|P|).Source: D EFFICIENCY ANALYSIS OF GRAPH… · p. 16
• Vectorized graph structures allow parallel computation to accelerate both construction and retrieval.The paper reports empirical verification in its efficiency experiments and Appendix E.4.Source: D EFFICIENCY ANALYSIS OF GRAPH… · p. 16

E.1 RETRIEVAL QUALITY EVALUATION (Q4)

• 87.03% recall and 81.58% relevance for LinearRAG in complex reasoning exceed GFM-RAG's 85.03% recall and 33.06% relevance.The table compares recall and relevance across fact retrieval, complex reasoning, contextual understanding, and creative generation.Source: Table 4 · p. 17, §E.1 · p. 17
• GFM-RAG's creative-generation recall rises from 44.88% to 83.51%, while relevance falls from 58.73% to 22.87%.The passage describes GraphRAG models as improving recall particularly in creative generation while falling behind in relevance metrics.Source: §E.1 · pp. 16–17
• The authors attribute the task differences to simpler fact retrieval needing direct semantic retrieval, while creative generation benefits from documents with strong logical dependencies.They contrast simpler tasks with complex generation needs, rather than reporting a separate measured causal test.Source: §E.1 · p. 17

E.2 HYPER-PARAMETER SENSITIVITY (Q5)

• The hyperparameter experiments use average GPT-Acc. and Contain-Acc. scores on 2WikiMultiHopQA.Source: §E.2 · p. 17
• δ = 4 is the selected threshold: too-small values add noise and reduce retrieval efficiency, while too-large values exclude relevant entities.The threshold controls entity-score retention during dynamic pruning and whether expansion continues.Source: §E.2 · p. 17, Figure 5 · p. 17
• λ = 0.05 is an example of a relatively small value at which performance is optimal, with entity information primary and DPR similarity auxiliary.λ balances DPR-based passage similarity against entity-level information in initial passage scoring.Source: Figure 5 · p. 17, §E.2 · p. 18

E.3 EFFECTIVENESS OF DIFFERENT SENTENCE EMBEDDINGS (Q6)

• Performance varies modestly across sentence embeddings, with all-mpnet-base-v2 superior on most datasets and selected as the default for computational efficiency.The comparison covers all-mpnet-base-v2, bge-large-en, all-MiniLM-L6-v2, and e5-large-v2.Source: §E.3 · p. 18, Table 5 · p. 18

E.4 LARGE-SCALE EFFICIENCY ANALYSIS (Q7)

• LinearRAG uses 0 prompt and completion tokens and is 12.8× and 15.1× faster than RAPTOR on the 5M- and 10M-token datasets, respectively.The evaluation uses two ATLAS-Wiki subsets for indexing-phase analysis.Source: §E.4 · p. 18

E.5 CASE STUDY (Q8)

• In the 2WikiMultihopQA case, LinearRAG captures implicit relationships through entity activation and contextual chaining, while HippoRAG2 misses evidence when a needed pre-extracted relation is absent.The example contrasts retrieval dependent on explicit relations such as “husband” with contextual chaining that does not require pre-extracted relational tuples.Source: Table 7 · p. 19, §E.5 · p. 19

F RELATED WORK

• The related-work discussion distinguishes graph-based approaches that explicitly structure corpora from reasoning-enhanced RAG approaches that use LLM reasoning without explicitly structuring corpora.Source: F RELATED WORK · p. 19

F RELATED WORK — Clustering-based hierarchy construction

• Clustering-based hierarchy construction groups related entities into topic communities, but can propagate relationship errors and presents scalability challenges for real-time use.Source: F RELATED WORK · pp. 19–20

F RELATED WORK — Relation-extraction-based knowledge graph construction

• Relation-extraction-based graph construction extracts triples from passages and links them by entity alignment, but independently processed passages can yield inconsistent triples.Schema-guided construction is described as requiring costly, time-consuming expert annotation and generalizing poorly across domains.Source: F RELATED WORK · p. 20

F RELATED WORK — Reasoning-enhanced RAG

• Reasoning-enhanced RAG decomposes complex queries into subqueries or intermediate steps and retrieves documents to address their logical dependencies.Examples include dependency-ordered subqueries, sequential notes, and iterative self-reflection.Source: F RELATED WORK · p. 20

G THE USE OF LARGE LANGUAGE MODELS

• The authors report using LLMs only to polish manuscript wording, not to generate research ideas, results, or claims.Source: G THE USE OF LARGE LANGUAGE MODELS · p. 20