This paper, presented at NeurIPS 2024, investigates a fundamental but often overlooked bottleneck in how Large Language Models (LLMs) handle structured data: Graph Recall. While much research focuses on whether LLMs can solve complex graph problems (like finding the shortest path), this study asks a simpler question: Can the model even remember the graph described in the prompt?
TL;DR
Researchers found that LLMs frequently fail at accurately recalling graph structures described in text and exhibit systematic structural biases, such as "hallucinating" triangles and alternating paths. Crucially, a model's ability to recall a graph depends heavily on whether the narrative style of the text matches the graph's real-world domain (e.g., social networks are recalled better when described as "friendships" rather than "road maps").
What Problem Does This Paper Address?
Graph-structured information is everywhere—from social networks in stories to protein interactions in biology. For an LLM to reason about these graphs, it must first "encode" the relationships into its internal state and "recall" them when prompted.
Cognitive scientists have known for decades that humans are biased when remembering social networks; we tend to "fill in the gaps" to create balanced structures (like assuming two of our friends are also friends with each other). This paper investigates whether LLMs suffer from similar "microstructural" biases and how these errors propagate to downstream reasoning tasks.
Methods
The authors designed a multi-step experimental pipeline:
- Task Introduction: The LLM is told it will be tested on its ability to memorize relationships.
- Presentation: A "vignette" (a short story) describes a graph using a specific narrative style.
- Memory Clearance: To simulate real-world delays, the model performs a "word span test" (recalling the last words of unrelated sentences) before the main task.
- Recall & Probability Extraction: The model is asked to list the edges. For GPT models, the authors used API log-probabilities to see how "confident" the model was in each edge; for Gemini, they used Monte Carlo sampling.
- Structural Analysis (ERGM): They used Exponential Random Graph Models (ERGM) to statistically measure if the model was biased toward specific motifs, such as triangles, stars, or "alternating 2-paths."
Datasets
The study used five distinct graph domains, each with 100 sampled graphs (5–30 nodes):
- Social Networks: Facebook ego-networks.
- Co-authorship: DBLP citation data.
- Geological: California road networks.
- Biological: Reactome protein-protein interactions.
- Synthetic: Erdős–Rényi (random) graphs.
They also introduced a cross-evaluation framework where the same graph structure was described using different narrative "skins" (e.g., describing a road network using social friendship language).
Key Insights and Ideas
- The "Narrative Match" Effect: This is the paper's most striking finding. LLMs (especially GPT-4) perform significantly better when the narrative style matches the graph's origin. A social graph is recalled most accurately when described as a social network. This suggests LLMs have developed "domain-specific priors"—they expect certain shapes from certain types of stories.
- Selective Forgetting vs. Hallucination: LLMs generally tend to forget edges (omission) rather than invent them (commission). However, when they do hallucinate edges, they aren't random; they tend to "close" triangles or create specific local patterns, mirroring human cognitive biases.
- Sensitivity to Contextual Noise: While GPT models were relatively robust, Gemini-Pro’s performance plummeted after even a small amount of "memory clearance" (distraction) tasks.
- Recall as a Bottleneck: There is a strong correlation ($r \approx 0.8$) between a model's recall accuracy and its performance on downstream tasks like link prediction. If the model can't remember the graph, it can't reason about it.
Key Results
- Performance Gap: No model achieved perfect recall. GPT-4 was the top performer, often hitting 90%+ accuracy on social and co-authorship graphs, but struggled significantly on random graphs (~60% accuracy).
- Structural Bias: Models showed a statistically significant bias toward triangles and alternating 2-paths. In social domains, GPT-4's bias toward triangles was even stronger than that of humans.
- Human Comparison: Compared to human subjects from previous cognitive studies, LLMs are generally more accurate (less forgetting) but exhibit "stronger hallucinations" of specific microstructures.
Limitations and Future Work
The authors acknowledge several constraints:
- Graph Size: The study focused on small graphs (up to 30 nodes). Real-world applications often involve thousands of nodes.
- Simple Narratives: The text descriptions were generated from templates. Real-world text is much noisier and more complex.
- Model Selection: Due to the timing of the research, newer models like Llama 3 or Claude 3 were not included.
Future Direction: The authors suggest that "Graph Foundation Models" should be trained with balanced motifs to mitigate these systematic biases. They also propose that "graph-customized" versions of the "Needle in a Haystack" test could be a new benchmark for long-context LLM evaluation.
Summary updated