Research map / Graph learning / Knowledge and temporal graphs
Microstructures and Accuracy of Graph Recall by Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how LLMs (GPT-3.5, GPT-4, Gemini-Pro) recall graphs described in text, measuring recall accuracy and ERGM-based microstructure biases (triangles, alternating 2-paths) and comparing with human social-network recall.
Problem
LLMs must accurately recall graphs described in earlier text for graph reasoning, but how accurate their recall is and what structural biases it has (compared with humans) is unknown.
Approach
Adapts cognitive-science human graph recall protocols (vignette presentation, word-span memory clearance, ERGM microstructure analysis with edge probabilities) to LLMs across real-world and random graph domains, and cross-evaluates narrative styles against domains.
Key results
- GPT-4 reaches 99.80% accuracy on Facebook and 98.11% on CA Road, but only 60.34% on Erdős–Rényi and 77.04% on Reactome.
- LLMs tend to forget edges rather than hallucinate them, and favor triangles and alternating 2-paths.
- GPT-4 achieves the best recall accuracy when narrative style matches the graph's source domain (diagonal of cross-evaluation heatmaps).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a narrative style matching the graph's application domain | GPT-4 graph recall · Real-world graph datasets | Accuracy | Helped |
| Use a narrative style matching the graph's application domain | GPT-3.5 graph recall · Real-world graph datasets | Accuracy | Helped |
| Increase memory-clearance strength | Gemini-Pro graph recall · Graph recall datasets | Accuracy | Hurt |
| Increase memory-clearance strength | GPT models' graph recall · Graph recall datasets | Accuracy | Mixed |
| Add a male or female role prime | LLM graph recall · Graph recall datasets | Accuracy | No clear effect |
| Use GPT-4 instead of GPT-3.5 | Graph recall · Facebook | Accuracy (%): 71.60 ± 4.07; 99.80 ± 0.11 | Helped |
| Use GPT-4 instead of GPT-3.5 | Graph recall · CA Road | Accuracy (%): 95.52 ± 2.67; 98.11 ± 2.54 | Helped |
| Use GPT-4 instead of GPT-3.5 | Graph recall · Reactome | Accuracy (%): 53.68 ± 3.32; 77.04 ± 4.13 | Helped |
| Use GPT-4 instead of GPT-3.5 | Graph recall · DBLP | Accuracy (%): 72.47 ± 3.61; 98.70 ± 0.74 | Helped |
| Use GPT-4 instead of GPT-3.5 | Graph recall · Erdős–Rényi | Accuracy (%): 55.20 ± 3.32; 60.34 ± 2.37 | Helped |
| Recall graphs tend to contain more triangles than the ground truth | LLM graph recall · Graph recall datasets | Triangle ERGM coefficient | Mixed |
| Recall graphs tend to contain more alternating 2-paths than the ground truth | LLM graph recall · Graph recall datasets | Alt-2-Path ERGM coefficient | Mixed |
Surprising findings
- Sex role priming had insignificant effect on LLM graph recall, contrary to human findings.
- Gemini-Pro's recall performance drops sharply with small amounts of memory-clearance noise, while GPT models remain stable.
Limitations
- Limited to five domains and a limited number of graph samples due to budget.
- Did not test other popular LLMs such as Claude 3 or Llama-3.
- Graph recall with simple fixed narratives differs from graph retrieval in noisy real-world text.
Experimental setup
Datasets: DBLP coauthorship Facebook ego networks CA road network Reactome protein interactions Erdős–Rényi random graphs Brashears social networks
Benchmarks: Facebook CA Road Reactome DBLP Erdős–Rényi Brashears two 15-node social networks
Metrics: accuracy F1 ERGM microstructure coefficients (edge, triangle, star, alt-
Baselines: Llama-2-13B Brashears et al. human recall results
Builds on: Exponential Random Graph Model Brashears human social network recall study word span test
Closest papers by meaning
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.90)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.89)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.89)
- Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data (ICML 2025 · similarity 0.89)
- ICLR: In-Context Learning of Representations (ICLR 2025 · similarity 0.87)
- $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.