You Don't Need Pre-built Graphs for RAG: Retrieval Augmented Generation with Adaptive Reasoning Structures

LogicRAG replaces costly pre-built knowledge graphs in GraphRAG with dynamically constructed, query-specific reasoning structures (DAGs) generated at inference time, enabling adaptive, logically-ordered retrieval without offline graph construction.

Problem Statement

LLMs hallucinate on knowledge-intensive queries, and while RAG mitigates this, existing GraphRAG methods require expensive corpus-to-graph transformation that incurs high token cost and update latency. Furthermore, a single static pre-built graph cannot flexibly match the diverse logical structures required by different query types, leading to misaligned and ineffective retrieval for complex multi-step reasoning.

Key Novelty

Inference-time construction of query-specific DAGs that model logical dependencies between decomposed subproblems, eliminating the need for expensive offline graph-building over the entire corpus
Topological-sort-based linearization of the reasoning DAG to enforce a logically consistent order for multi-step subproblem resolution and retrieval
Joint graph pruning and context pruning mechanisms that remove redundant retrieval paths and irrelevant retrieved content, substantially cutting token cost while preserving accuracy

Evaluation Highlights

Outperforms state-of-the-art GraphRAG and RAG baselines on complex reasoning/QA benchmarks in answer accuracy
Achieves substantially lower token cost and inference overhead than graph-based RAG baselines due to elimination of pre-built graphs and use of pruning

Signal Assessment

6/10 The paper offers a well-motivated, practically impactful reformulation of GraphRAG that removes costly pre-built graphs via dynamic, query-adaptive reasoning structures, but it builds on established techniques (query decomposition, DAG dependency modeling, topological sort, pruning) rather than introducing a fundamentally new paradigm.

Methodology

Decompose the input query into a set of interrelated subproblems
Construct a directed acyclic graph (DAG) capturing logical dependencies among the subproblems
Linearize the DAG via topological sort to determine a logically consistent subproblem-solving order
Apply graph pruning to eliminate redundant nodes/edges and reduce unnecessary retrieval calls
Apply context pruning to filter irrelevant retrieved passages before feeding them to the LLM
Sequentially resolve subproblems using retrieved, pruned context to generate the final answer

System Components

Query Decomposer

Breaks the input query into a set of logically related subproblems

DAG Constructor

Builds a directed acyclic graph encoding dependency relationships among subproblems to guide reasoning order

Topological Sort Linearizer

Converts the DAG into a linear sequence of subproblems to ensure coherent, dependency-respecting multi-step reasoning

Graph Pruning Module

Removes redundant nodes/edges in the reasoning graph to avoid unnecessary retrieval operations

Context Pruning Module

Filters out irrelevant retrieved context passages to reduce token usage passed to the LLM

Results

Metric/Benchmark	Baseline (GraphRAG/SOTA)	LogicRAG	Delta
Answer accuracy on complex/multi-hop QA	Standard performance of pre-built GraphRAG methods	Higher accuracy reported	Qualitative improvement (no exact numbers in abstract)
Token cost	High, due to graph construction and retrieval overhead	Significantly reduced via graph/context pruning	Notable reduction
Graph maintenance/update latency	Requires costly re-building for corpus updates	Eliminated (no pre-built graph needed)	Latency removed

Key Takeaways

Effective graph-based retrieval reasoning does not require an expensive, pre-built corpus-wide knowledge graph; lightweight, query-specific DAGs generated on-the-fly can suffice
Combining query decomposition with dependency-aware ordering (DAG + topological sort) provides a structured way to handle multi-step, logically dependent reasoning in RAG pipelines
Graph-level and context-level pruning are practical levers for controlling token cost in retrieval-augmented systems without sacrificing accuracy
This approach is especially attractive for dynamic or frequently updated knowledge bases where maintaining a static graph index is impractical or costly

Abstract

Large language models (LLMs) often suffer from hallucination, generating factually incorrect statements when handling questions beyond their knowledge and perception. Retrieval-augmented generation (RAG) addresses this by retrieving query-relevant contexts from knowledge bases to support LLM reasoning. Recent advances leverage pre-constructed graphs to capture the relational connections among distributed documents, showing remarkable performance in complex tasks. However, existing Graph-based RAG (GraphRAG) methods rely on a costly process to transform the corpus into a graph, introducing overwhelming token cost and update latency. Moreover, real-world queries vary in type and complexity, requiring different logic structures for accurate reasoning. The pre-built graph may not align with these required structures, resulting in ineffective knowledge retrieval. To this end, we propose a Logic-aware Retrieval Augmented Generation framework (LogicRAG) that dynamically extracts reasoning structures at inference time to guide adaptive retrieval without any pre-built graph. LogicRAG begins by decomposing the input query into a set of subproblems and constructing a directed acyclic graph (DAG) to model the logical dependencies among them. To support coherent multi-step reasoning, LogicRAG then linearizes the graph using topological sort, so that subproblems can be addressed in a logically consistent order. Besides, LogicRAG applies graph pruning to reduce redundant retrieval and uses context pruning to filter irrelevant context, significantly reducing the overall token cost. Extensive experiments demonstrate that LogicRAG achieves both superior performance and efficiency compared to state-of-the-art baselines.