What Breaks Knowledge Graph based RAG? Empirical Insights into Reasoning under Incomplete Knowledge

📝 Paper Summary

Graph-based RAG pipeline Benchmark datasets

BRINK is a benchmark for Knowledge Graph RAG that systematically evaluates reasoning capabilities by removing direct links to answers and forcing models to infer them through multi-hop logical rules.

Core Problem

Existing KG-RAG benchmarks use complete graphs where answers are often directly connected to the query entity, failing to distinguish between simple lookup and actual reasoning over incomplete knowledge.

Why it matters:

Real-world Knowledge Graphs are notoriously incomplete, making reasoning over missing links essential for practical deployment
Current benchmarks inflate performance by allowing models to retrieve direct answers rather than inferring them, masking poor reasoning capabilities
Inconsistent evaluation protocols (ambiguous metric definitions, code-paper discrepancies) make cross-paper comparisons unreliable

Concrete Example: For the question 'Who is the brother of Justin Bieber?', standard benchmarks provide the triple 'hasBrother(Justin, Jaxon)'. A model can answer via simple lookup. In BRINK, this direct triple is removed, forcing the model to reason: 'hasParent(Justin, Jeremy) AND hasChild(Jeremy, Jaxon) implies hasBrother(Justin, Jaxon)'.

Key Novelty

Benchmark for Reasoning under Incomplete Knowledge (BRINK)

Constructs questions by first mining logical rules (e.g., parent's child is a sibling) and then selectively removing the 'head' triple (direct answer) from the KG
Ensures the answer is still inferable by preserving the 'body' triples (evidence) required by the rule, forcing the model to traverse a reasoning path rather than a single edge
Standardizes evaluation by formally defining metrics like Hits@Any and Hard Hits Rate, addressing prevalent inconsistencies in prior work

Architecture

The logical flow for constructing the BRINK benchmark, illustrating the transition from a complete KG to an incomplete one via rule mining.

Evaluation Highlights

Most KG-RAG models suffer significant performance drops (e.g., -20% to -60% Hits@1) when direct links are removed, revealing reliance on lookup
Training-based methods like RoG and GNN-RAG show greater robustness to incompleteness compared to training-free prompting methods
Removing textual entity labels causes massive performance degradation, indicating models rely heavily on internal parametric memory rather than structured graph reasoning

Breakthrough Assessment

8/10

Identifies a critical flaw in existing evaluations (lookup vs. reasoning) and provides a rigorous method to fix it. The standardized protocol and findings on 'fake' reasoning are highly valuable.

⚙️ Technical Details

Problem Definition

Setting: Knowledge Graph Question Answering (KGQA) under incomplete knowledge settings

Inputs: Natural language question q, topic entity e, and an incomplete Knowledge Graph G where direct answers are removed

Outputs: Predicted answer entity set P_q

Pipeline Flow

Rule Mining (AMIE3)
Triple Removal (Incompleteness Simulation)
Question Generation (GPT-4)
Evaluation (Standardized Metrics)

System Modules

Rule Miner (Benchmark Construction)

Identify logical patterns (e.g., transitivity, symmetry) that allow inferring facts

Model or implementation: AMIE3 algorithm

Triple Remover (Benchmark Construction)

Create 'Incomplete KG' by removing triples that are inferable via mined rules

Model or implementation: Heuristic Script

Question Generator (Benchmark Construction)

Convert removed triples into natural language questions

Model or implementation: GPT-4

Novel Architectural Elements

Rule-based incompleteness injection: systematically removing direct answers while guaranteeing the existence of a multi-hop reasoning path (unlike random deletion)
Hard Hits evaluation protocol: specifically measuring success on inferred answers rather than general retrieval

Modeling

Base Model: Varies (Benchmarked models include RoG, GNN-RAG, ToG, StructGPT, etc.)

Comparison to Prior Work

vs. WebQSP/CWQ benchmarks: BRINK enforces incompleteness; WebQSP/CWQ only keep questions with direct SPARQL answers in the KG
vs. Random Deletion (e.g., Zhou et al. 2025): BRINK ensures sufficiency of remaining knowledge for inference; random deletion may make questions unanswerable
vs. RoG/ToG original evaluations: BRINK uses a standardized protocol (Hits@Any, Hard Hits) to fix inconsistent metric definitions in original papers

Limitations

Dependency on AMIE3 rule mining quality; if rules are spurious, the 'inference' path might not be valid
Focus on Horn rules limits the types of reasoning patterns tested (mostly deductive/logical)
Does not evaluate multimodal or temporal reasoning aspects of KGs
Requires high-quality base KGs to mine meaningful rules

Reproducibility

Code: https://github.com/zdzd1234/BRINK

Benchmark code and data generation scripts are publicly available at https://github.com/zdzd1234/BRINK. The paper uses standard datasets (Family, FB15k-237, Wikidata5m) and provides exact AMIE3 parameters for rule mining.

📊 Experiments & Results

Evaluation Setup

KGQA on three datasets (Family, FB15k-237, Wikidata5m) under 'Complete' vs 'Incomplete' KG settings

Benchmarks:

BRINK-Family (Synthetic familial reasoning) [New]
BRINK-FB15k-237 (General domain reasoning (Freebase)) [New]
BRINK-Wikidata5m (Large-scale real-world reasoning) [New]

Metrics:

Hits@Any (correct answer in prediction set)
Hits@Hard (specifically predicts the removed 'hard' answer)
Hard Hits Rate (proportion of correct answers that are 'hard')
Statistical methodology: Not explicitly reported in the paper

Key Results

Benchmark	Metric	Baseline	This Paper	Δ
Performance drops significantly for most models when moving from Complete to Incomplete KG, showing reliance on direct lookup.
BRINK-FB15k-237	Hits@Any	59.2	39.0	-20.2
BRINK-FB15k-237	Hits@Any	41.6	13.6	-28.0
BRINK-Family	Hits@Any	98.7	98.6	-0.1
Ablation study removing entity names (ID-only) shows models rely heavily on text memorization rather than graph structure.
BRINK-FB15k-237 (Incomplete)	Hits@Any	39.0	11.2	-27.8

Main Takeaways

Current KG-RAG models are fragile: performance collapses when direct supporting triples are removed, indicating they often 'cheat' via lookup.
Training-based methods (RoG, GNN-RAG) learn reasoning patterns better than prompting-based methods (ToG, StructGPT) which rely more on retrieval.
LLMs rely heavily on parametric memory (memorized facts) rather than reasoning over the provided graph structure, evidenced by the sharp drop when entity names are masked.
Standardized metrics are crucial: existing literature's inconsistent 'accuracy' and 'Hits@1' definitions have obscured these reasoning failures.

📚 Prerequisite Knowledge

Prerequisites

Knowledge Graph structure (entities, relations, triples)
Basic logic (Horn rules, atoms, body vs. head)
Retrieval-Augmented Generation (RAG) concepts

Key Terms

KG-RAG: Knowledge Graph-based Retrieval-Augmented Generation—using structured graph data to augment LLM generation

Horn rule: A logical rule of the form 'If A and B are true, then C is true', used here to define valid reasoning paths

AMIE3: A rule mining algorithm used to discover high-confidence logical patterns in large knowledge graphs

Hits@1: A metric measuring if the correct answer is the top-ranked prediction (often implemented inconsistently in prior work)

Hits@Hard: A metric specifically checking if the model predicts the 'hard answer'—the entity whose direct link was intentionally removed

Hard Hits Rate (HHR): The proportion of correct answers that specifically include the hard (inferred) answer

Triple: The fundamental unit of a Knowledge Graph, consisting of (Subject, Predicate, Object)

Parametric memory: Knowledge stored in the LLM's fixed weights during pre-training, as opposed to knowledge retrieved from external sources