When Should RAG Use Graphs? Complexity-Aware GraphRAG Routing and Answer Quality Prediction on GraphRAG-Bench-H

Abstract

Graph retrieval-augmented generation (GraphRAG) improves retrieval when questions require multi-hop relations, entity interactions, and evidence-level composition, but graph construction and traversal add cost when ordinary retrieval is sufficient. This paper presents CAR-GraphRAG, a complexity-aware routing and answer-quality prediction framework for deciding when a RAG query should use a graph. The evaluation uses a 4,072-row GraphRAG-Bench-H materialization with the fields id, source, question, answer, question_type, evidence, and evidence_relations. The dataset spans medical and novel domains and four task types: Fact Retrieval, Complex Reasoning, Contextual Summarization, and Creative Generation. We compare BM25-RAG, Dense-RAG, Hybrid-RAG, GraphRAG-Lite, and the proposed router using evidence recall@5, answer F1, ROUGE-L, faithfulness, accuracy, latency, and token cost. CAR-GraphRAG achieved 0.8665 mean answer F1, exceeding GraphRAG-Lite (0.8240), Hybrid-RAG (0.8028), Dense-RAG (0.7238), and BM25-RAG (0.6349). On the held-out test split, the router identified graph-beneficial queries with 0.9650 F1 and 0.9858 ROC-AUC, while the answer-quality predictor achieved 0.0298 MAE. The results show that graph retrieval is most valuable for relation-dense, evidence-heavy, high lexical-gap queries, whereas direct fact retrieval is better served by hybrid non-graph retrieval.