Technical Summary: LUCID - Detecting Hallucinations for LLM-based Knowledge Graph Reasoning

1. Problem Statement

While Large Language Models (LLMs) integrated with Knowledge Graphs (KGs) have advanced reasoning tasks like question answering (QA) and decision support, they remain susceptible to hallucinations. Even when relevant KG triples are retrieved and incorporated into prompts, LLMs may generate factually incorrect responses that contradict the retrieved evidence.

Existing hallucination detection methods face significant limitations in this specific domain:

• General methods (e.g., EigenScore, Perplexity) focus on internal LLM states but ignore external KG context.
• RAG-specific methods (e.g., RAGAs, Trulens) verify consistency between responses and retrieved text but overlook the structural information inherent in KGs.
• Gap: No existing method jointly leverages LLM internal attention, KG semantics, and KG structural topology to detect hallucinations in LLM-KG reasoning frameworks.

The authors quantify this issue by manually annotating responses from three frameworks (Readi, ToG, StructGPT) across three datasets (GrailQA, WebQSP, QALD-10), revealing an average hallucination rate of 29.65%.

2. Methodology: LUCID

The paper proposes LUCID (halLUcination deteCtIon method for LLM-based knowleDge graph reasoning), the first method designed specifically for this scenario. LUCID operates by fusing three distinct information sources into a Graph Neural Network (GNN) to predict hallucination probability.

2.1 Feature Extraction

The method processes the interaction between the LLM and the retrieved KG subgraph ($G = (V, E)$) through three stages:

1. LLM Internal State Information (Attention Scores):

   • The model extracts attention scores from the LLM's multi-layer, multi-head architecture during response generation.
   • It calculates the average attention score for each response token over all tokens corresponding to KG nodes (entities) and edges (relations).
   • These are aggregated into two mean attention matrices: $M_e$ (for nodes) and $M_r$ (for edges) across all layers and heads.

2. KG Semantic Information:

   • To distinguish task-relevant from task-irrelevant edges, the method computes the semantic similarity between the query and the relations (edges) in the KG.
   • Using a pre-trained language model (all-MiniLM-L6-v2), embeddings are generated for the query and relations.
   • Cosine similarity scores $s(r, Q)$ are computed. Note: Semantic relevance is computed for relations, not entities, as entity surface forms are often ambiguous.

3. Feature Construction:

   • Node Features ($x_e$): Formed by flattening the node attention matrix $M_e$.
   • Edge Features ($x_r$): Formed by concatenating the flattened edge attention matrix $M_r$ with the semantic similarity score $s(r, Q)$.

2.2 Detection Model (GNN)

• The enriched subgraph, equipped with the constructed node and edge features, is fed into a Graph Isomorphism Network with Edge features (GINE).
• GINE is chosen over standard GIN because it explicitly incorporates edge features into the message-passing mechanism, allowing it to leverage the rich structural and semantic attributes of the KG.
• The GNN aggregates graph information through $K$ layers of message passing. A graph-level representation is obtained by summing node features, which is then passed through a classifier (MLP + Sigmoid) to output the probability of hallucination.
• The detection threshold is determined by maximizing the geometric mean of sensitivity and specificity on the ROC curve.

3. Key Contributions

1. Problem Identification & Benchmarking: The authors are the first to systematically identify and quantify hallucinations in LLM-based KG reasoning frameworks. They constructed manually annotated benchmark datasets across three frameworks and three QA datasets, establishing a baseline hallucination rate of 29.65%.
2. Novel Method (LUCID): They propose LUCID, a detection framework that uniquely integrates:
   • LLM internal state (attention mechanisms).
   • KG semantic information (relation-query similarity).
   • KG structural information (graph topology).
3. State-of-the-Art Performance: Extensive experiments demonstrate that LUCID outperforms 15 baselines (including general detection methods and RAG-specific tools) across all tested frameworks and datasets.
4. Practical Utility: The paper demonstrates that LUCID's hallucination probabilities can be used to refine QA strategies, significantly reducing inference costs while maintaining high accuracy.

4. Experimental Results

Experiments were conducted on GrailQA, WebQSP, and QALD-10 using three reasoning frameworks: Readi, ToG, and StructGPT.

• Performance: LUCID achieved State-of-the-Art (SOTA) performance on all datasets.
  • On average, it outperformed the best baseline (SelfCheckGPT) by 6.76% and REDEEP (chunk) by 5.48% in terms of the average metric (AVG of ACC, AUC, PCC).
  • It showed the most significant gains on the Readi framework (+2.81% average gain), attributed to Readi's denser KG subgraphs which better suit LUCID's message-passing mechanism.
  • On WebQSP, LUCID achieved a +2.57% average gain, effectively handling relation-centric questions where hallucinations often stem from incorrect relation selection.
• Cost-Efficiency Application: A "Mixed" strategy was tested where Qwen2.5-7B generates initial answers, and LUCID flags high-probability hallucinations for re-generation by a larger model (Qwen3-235B).
  • This approach achieved accuracy comparable to using the large model for all queries (within 1.18% difference).
  • It reduced monetary costs by an average of 55.4% compared to using the large model exclusively.
• Ablation Studies:
  • Features: Removing semantic similarity or replacing attention matrices with random/hidden-layer scores significantly degraded performance, confirming the necessity of both attention and semantic signals.
  • Model Architecture: GINE outperformed GCN, GAT, and MLP, validating the importance of explicitly modeling edge features and graph topology.
  • Hyperparameters: Optimal performance was achieved with 2 GINE layers, 512 hidden channels, and a learning rate of $1 \times 10^{-3}$.

5. Significance and Claims

The paper claims that LUCID addresses a critical gap in the reliability of LLM-based KG reasoning. By moving beyond surface-level consistency checks to analyze the structural and semantic alignment between the LLM's attention and the KG, LUCID provides a more robust mechanism for detecting misinformation.

The authors position LUCID not just as a detection tool, but as a foundational component for improving downstream applications. The ability to filter hallucinations allows for:

• More reliable decision support and automated knowledge discovery.
• Cost-effective deployment strategies (using smaller models with selective refinement).
• A necessary basis for future improvements in LLM-KG integration.

The work concludes by noting that while LUCID is effective, future work will focus on fine-grained hallucination attribution for better interpretability and extending evaluation to multilingual and cross-domain environments.