Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning
Ruiyi Yang, Hao Xue, Imran Razzak, Shirui Pan, Hakim Hacid, Flora D. Salim
cs.AI, cs.IR, cs.MA
2025-05-20
SPLIT-RAG splits a KG by training-question paths and wakes only the matching subgraph agents. On WebQSP it hits 89.4 Hit and 85.3 Hits@1, +2.5/+3.5 over SubgraphRAG.
GraphRAG hangs a knowledge graph off an LLM so the model can fetch triples instead of guessing. Once the graph is Freebase-sized, two failure modes show up together: a one-hop fact still pays for a full-graph walk, and a four-hop question gets its reasoning path shredded across an oversized search. The paper names three constraints: retrieval latency, hallucination even after correct evidence arrives, and conflicts between stale or inconsistent triples.
Topology partitioners such as METIS cut edges without looking at questions. KG+LLM systems such as RoG, ToG, and SubgraphRAG already walk paths or extract subgraphs, but at query time they still treat the store as one piece. WebQSP and CWQ share a Freebase dump with about 2.57 million entities and 8.31 million triples. Extra search both costs seconds and leaves room for the model to ignore retrieved facts.
The cut should follow how a class of questions walks the graph, not the graph's own shape.
SPLIT-RAG stands for Semantic Partitioning of Linked Information for Type-Specialized Multi-Agent RAG. Training questions carve the graph offline. At query time only a few agents wake up.
Each training item is stored as three views: a semantic string with stopwords dropped, an entity-type string where mentions become KB types, and the gold KG path that reaches the answer. Paths are sliced into at-most-2-hop fragments. A greedy merge then grows subgraphs by information gain: fragments of similar questions should concentrate (low conditional entropy), while a size penalty and a max-entity cap stop one subgraph from swallowing the whole graph. Tiny leftovers merge into neighbors.
Subgraphs are packed onto lightweight agents. The assignment tries to keep each training question touching as few agents as possible, under a per-agent capacity and a coherence floor. Subgraphs that co-occur on the same questions tend to land together.
A new question is encoded the same way. Cosine similarity on the type view plus path overlap finds training neighbors. If a neighbor is close enough, its decomposition and agent set are reused. Otherwise the planner maps predicted path fragments back to subgraphs and agents.
Each woken agent searches only its own subgraphs, scores paths by entity overlap, pulls triples, and verbalizes them with relation templates. Aggregation scores every triple by agent reliability, how often it appears, and whether the evidence text entails it. Contradictory triples go into a compatibility graph; the max-weight clique keeps a conflict-free set. A head LLM writes the final answer from that clean set plus the evidence text.
The cut is supervised by historical QA traces. Retrieval is selective. Conflict handling sits in aggregation, not in the generator's goodwill.
Four KGQA benchmarks: WebQSP, CWQ, MetaQA-2hop, MetaQA-3hop. Baselines include embedding models, closed-book LLMs, and KG+LLM systems (StructGPT, RoG, ToG, SubgraphRAG, GcR).
| Method | WebQSP Hit / H@1 / F1 | CWQ Hit / H@1 / F1 |
| Graph-RAG | 77.2 / 73.1 / 67.7 | 58.8 / 54.6 / 53.9 |
| RoG | 85.7 / 80.0 / 70.8 | 62.6 / 57.8 / 56.2 |
| SubgraphRAG | 86.9 / 81.8 / 71.5 | 65.4 / 61.3 / 57.8 |
| ToG | 82.1 / 78.5 / 69.8 | 63.3 / 59.8 / 56.4 |
| SPLIT-RAG | 89.4 / 85.3 / 75.6 | 66.1 / 63.0 / 60.7 |
Against the strongest baseline, SubgraphRAG, WebQSP gains are +2.5 Hit, +3.5 Hits@1, +4.1 F1. CWQ still ranks first, but Hit only moves +0.7. MetaQA-2hop is Hit 96.9 / H@1 94.5; 3hop is 91.4 / 88.3. On the small movie graph, TransferNet still reports H@1 100. The paper says embedding methods cling to graph size and structure and collapse on Freebase.
End-to-end latency under a shared budget:
| Method | WebQSP | CWQ |
| ToG | 41.6 s | 47.6 s |
| RoG | 34.7 s | 41.3 s |
| SPLIT-RAG | 31.6 s | 35.9 s |
That is about 10 s faster than ToG and 3.1 / 5.4 s faster than RoG. A WebQSP query activates 4.6 subgraphs on average, each about 67k entities. Collapse those subgraphs into one agent and Hits@1 falls from 85.3 to 67.9, with the search region growing to 303k entities. Replace question-similarity routing with subgraph labels and Hit falls from 89.4 to 82.1, while more subgraphs get pulled in. Drop conflict checks and Hit lands at 85.1, the smallest drop; the authors note conflicting triples appear on only a few questions.
Coverage is the quiet miss. Combined subgraphs cover 99.9% of MetaQA needs, 91.3% on WebQSP, and 72.8% on CWQ. Complex questions outside the training walk patterns leak.
Agents do not need equal strength. On MetaQA-3hop, Gemini 2.0 Flash-Lite on subgraphs plus Gemini 2.5 Flash Preview as head scores Hit 92.1 in 28.6 s. Upgrade subgraph agents to Flash as well and Hit becomes 93.9 in 37.1 s: two points for 8.5 seconds. Keep the head strong; the edge can be thin.
Three takeaways for anyone shipping GraphRAG.
If the partitioner is still a topology cut, swap the signal for paths that training questions actually walked, provided gold paths exist. Without that supervision, the offline split has no anchor.
Do not put a frontier model on every agent. Subgraph workers extract triples; the head synthesizes. The Lite-plus-strong-head Pareto is closer to a production budget than an all-flagship swarm.
Conflict filtering helps, but it is not the engine. Ablation attributes the collapse to merging subgraphs and dropping multi-agent retrieval.
This is an incremental GraphRAG recipe. The WebQSP gap is real; the CWQ gap is thin. Thirty-plus seconds per question is faster than ToG, still far from interactive search.
The authors flag two follow-ups: online rebalancing for streaming graphs, and stronger checks for rare-entity conflicts that current logic misses.
A larger assumption sits in the method. Partitioning and the retrieval plan both need training questions with gold KG paths. Production RAG rarely has that trace. Section 3.3 falls back to predicted paths, and that fallback is not reported on its own.
CWQ coverage at 72.8% means the partition misses knowledge on harder multi-hop items. The body text also disagrees with Table 2 (87.7 / 64.2 Hit versus 89.4 / 66.1). Trust the table, and treat the draft as unfinished: no public code, ACM headers still say Woodstock 2018.
The claimed search complexity, O((N/k) log k) versus O(N), assumes B-tree lookup over a subgraph of size k. WebQSP still wakes 4.6 subgraphs, and wall-clock time is dominated by multiple LLM calls, not graph indexing.