Leveraging Graph Structures to Detect Hallucinations in Large Language Models

Noa Nonkes, Sergei Agaronian, Evangelos Kanoulas, Roxana PetcuACL 2024

TL;DR

This paper introduces a novel method for detecting hallucinations in Large Language Models (LLMs) by representing text generations as a graph and using Graph Attention Networks (GATs). The approach leverages the idea that hallucinated content might exhibit structural similarities in the latent space, outperforming traditional methods without relying on external knowledge or LLM logits.

What Problem Does This Paper Address?

Large Language Models (LLMs) are increasingly powerful and widely used, but they suffer from a significant drawback: hallucination. This means LLMs can generate plausible-sounding but factually incorrect information, which erodes user trust and can lead to poor decision-making. While existing methods exist to detect these hallucinations, they often require access to external knowledge bases, LLM internals (like logits), or multiple inference passes, which can be computationally expensive and complex. This paper tackles the challenge of detecting LLM hallucinations in a more efficient and self-contained manner by exploring the structural properties of the latent space of LLM generations.

Methods

The core of this paper's methodology lies in constructing a graph representation of LLM generations and applying a Graph Attention Network (GAT).

  1. Graph Construction:
    • LLM generations are first converted into sentence-level embeddings using BERT.
  2. A graph is built where each generation is a node.
  3. Edges are formed between nodes if their semantic similarity (cosine similarity) exceeds a predefined threshold. This leverages the principle of homophily, assuming similar sentences will be closer in the embedding space.
  4. The graph structure is designed to reduce computational costs by only connecting similar nodes, avoiding a fully connected graph.
  5. Graph Attention Network (GAT):
    • A GAT is employed to learn from this graph structure.
  6. To handle high-dimensional embeddings, a basic MLP is used to reduce dimensionality before applying the GAT.
  7. The GAT uses message passing and attention mechanisms to aggregate information from neighboring nodes, learning to assign importance based on relevance.
  8. The model is trained to map sentence embeddings to an ordinal label indicating the degree of hallucination.
  9. Contrastive Learning:
    • To enhance the discriminative power of embeddings, contrastive learning is incorporated. This helps the model better distinguish between true and hallucinated statements.
  10. Label Recovery Task:
    • The trained GAT model is then used to infer labels for new, unseen generations by performing a forward pass on an augmented graph.

Datasets

The authors utilized a combination of self-generated and existing datasets:

  • Self-Generated Dataset: Created by prompting an LLM to generate statements for a multiple-choice exam, including both true and misleading (hallucinated) answers. This dataset allowed for controlled generation and evaluation of specific prompting strategies (with and without context).
  • Benchmark Datasets:
    • FEVER: Used for evaluating the model's generalizability on a real-world dataset for fact extraction and verification.
  • SelfCheckGPT: Another benchmark dataset used to assess performance on hallucination detection.

The paper notes that for these benchmark datasets, labels were re-defined to fit the ordinal regression task of their model.

Key Insights and Ideas

  • Hallucinations have structure: The central hypothesis is that LLM hallucinations are not random but exhibit discernible patterns and shared characteristics within the latent embedding space.
  • Graphs reveal hidden connections: Representing generations as graphs allows for the capture of complex semantic relationships that might be missed by simpler models.
  • GATs excel at leveraging graph structure: Graph Attention Networks are particularly effective at learning from these graph structures, identifying important neighbors and aggregating information for better classification.
  • Contrastive learning boosts discriminability: Enhancing embeddings with contrastive learning significantly improves the model's ability to differentiate between true and hallucinated content.
  • Self-contained detection: The method demonstrates that hallucination detection can be achieved effectively without relying on external knowledge bases or direct access to LLM internals, making it more efficient and versatile.

Key Results

  • Superior Performance: The GAT model consistently outperformed baseline models (3-layer MLP and DeBERTa-QA) on recall, precision, and AUC-PR metrics, particularly on the validation set. For instance, GAT achieved approximately 17% higher recall than baseline models.
  • Impact of Contrastive Learning: Incorporating contrastive learning led to significant improvements. On the training set, recall increased by a remarkable 32% for GAT. Overall, CL improved performance across metrics, with a 20% increase in precision and recall for the train set.
  • Graph Structure is Crucial: Ablation studies showed that while contrastive learning is beneficial, the graph structure itself is essential. The GAT model, leveraging spatial similarity and attention, significantly outperformed a kNN baseline, highlighting the importance of graph-based aggregation.
  • Competitive on Benchmarks: When evaluated on FEVER and SelfCheckGPT datasets, the proposed method achieved competitive results, often outperforming existing approaches in precision, while operating in a closed-book setting (without external data). For FEVER, the model achieved higher precision than the UNC-NLP baseline.

Limitations and Future Work

  • Modeling Effort: The current approach requires effort to model data, create ordinal categorical labels, and construct the graph.
  • Lack of Transparency: The method is a "black-box" and does not offer transparency into why a statement is classified as hallucinated.
  • Scalability Challenges: Adding new nodes to the graph involves an exponential number of embedding comparisons, making real-time classification difficult.
  • Dynamic GATs: The authors suggest exploring dynamic Graph Attention Networks (GATs) as a potential solution for real-time classification and handling new nodes.
  • Query-Answer Baseline: Simulating a query-answer baseline setting with the attention mechanism could be an interesting future direction to analyze performance changes.

Summary updated

BibTeX
@inproceedings{nonkes2024leveraging,
  author = {Noa Nonkes and Sergei Agaronian and Evangelos Kanoulas and Roxana Petcu},
  title = {{Leveraging Graph Structures to Detect Hallucinations in Large Language Models}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2024},
}
Figure