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

LinearRAG replaces the costly, error-prone relation-extraction step in GraphRAG with a lightweight, relation-free hierarchical graph ('Tri-Graph') built purely from entity extraction and semantic linking, paired with a two-stage retrieval process for scalable, precise passage retrieval.

Problem Statement

Traditional RAG breaks down on large, fragmented corpora, and existing GraphRAG solutions that add relational structure depend on unstable, expensive LLM-based relation extraction, which injects noise and inconsistency into the graph and degrades retrieval quality. This makes current GraphRAG pipelines impractical to scale economically and reliably to large-scale, unstructured corpora for multi-hop reasoning.

Key Novelty

Tri-Graph: a relation-free hierarchical graph construction paradigm that uses only entity extraction and semantic linking, eliminating unstable relation modeling entirely
Graph construction that scales linearly with corpus size and requires no extra LLM token consumption, making indexing economically viable at scale
Two-stage retrieval strategy combining local semantic bridging (entity activation) with global importance aggregation (passage retrieval) to enable precise multi-hop retrieval without relying on explicit relations

Evaluation Highlights

Outperforms baseline RAG and GraphRAG methods across four benchmark datasets
Demonstrates efficiency advantages via linear scaling with corpus size and no additional token overhead compared to relation-extraction-based GraphRAG pipelines

Signal Assessment

6/10 The paper offers a practical, well-motivated simplification of GraphRAG that directly tackles cost and reliability issues plaguing the field, representing a solid engineering and architectural contribution rather than a fundamentally new paradigm.

Methodology

Perform lightweight entity extraction over passages without attempting relation/triple extraction
Construct a hierarchical Tri-Graph linking passages and entities via semantic similarity (semantic linking) instead of explicit relations
Stage 1 retrieval: activate relevant entities through local semantic bridging between the query and graph entities
Stage 2 retrieval: aggregate global importance signals across activated entities to rank and retrieve the most relevant passages
Feed retrieved passages into the LLM for grounded generation

System Components

Tri-Graph

A relation-free, hierarchical graph structure connecting passages and entities, avoiding costly and noisy relation extraction

Lightweight Entity Extraction

Extracts entities from passages without modeling relations, reducing LLM token usage and instability

Semantic Linking

Connects entities and passages using semantic/embedding similarity rather than explicit extracted relations

Local Semantic Bridging

First-stage retrieval mechanism that activates query-relevant entities within the Tri-Graph

Global Importance Aggregation

Second-stage retrieval mechanism that aggregates entity-level signals to identify and rank the most relevant passages

Results

Metric/Benchmark	Baseline (GraphRAG)	LinearRAG	Delta
Retrieval/QA performance (4 datasets)	Standard GraphRAG accuracy	Significantly higher accuracy	Consistent improvement across datasets
Graph construction cost	Relies on costly relation extraction	No extra token consumption	Reduced construction cost
Scalability with corpus size	Non-linear, unstable scaling	Linear scaling	Improved scalability

Key Takeaways

Relation extraction may be an unnecessary bottleneck in GraphRAG—entity extraction plus semantic linking can achieve comparable or better retrieval quality at much lower cost
Linear scaling in graph construction cost is a critical property for deploying GraphRAG on truly large-scale, real-world corpora
Decoupling retrieval into entity activation (local) and passage aggregation (global) stages offers a practical blueprint for scalable multi-hop retrieval
Practitioners facing high token costs or unreliable graphs from LLM-based relation extraction should consider relation-free graph designs as a drop-in alternative

Abstract

Retrieval-Augmented Generation (RAG) is widely used to mitigate hallucinations of Large Language Models (LLMs) by leveraging external knowledge. While effective for simple queries, traditional RAG systems struggle with large-scale, unstructured corpora where information is fragmented. Recent advances incorporate knowledge graphs to capture relational structures, enabling more comprehensive retrieval for complex, multi-hop reasoning tasks. However, existing graph-based RAG (GraphRAG) methods rely on unstable and costly relation extraction for graph construction, often producing noisy graphs with incorrect or inconsistent relations that degrade retrieval quality. In this paper, we revisit the pipeline of existing GraphRAG systems and propose LinearRAG (Linear Graph-based Retrieval-Augmented Generation), an efficient framework that enables reliable graph construction and precise passage retrieval. Specifically, LinearRAG constructs a relation-free hierarchical graph, termed Tri-Graph, using only lightweight entity extraction and semantic linking, avoiding unstable relation modeling. This new paradigm of graph construction scales linearly with corpus size and incurs no extra token consumption, providing an economical and reliable indexing of the original passages. For retrieval, LinearRAG adopts a two-stage strategy: (i) relevant entity activation via local semantic bridging, followed by (ii) passage retrieval through global importance aggregation. Extensive experiments on four datasets demonstrate that LinearRAG significantly outperforms baseline models. Our code and datasets are available at https://github.com/DEEP-PolyU/LinearRAG.