# LLMs Prompted for Graphs: Hallucinations and Generative Capabilities

arXiv: https://arxiv.org/abs/2409.00159 · HTML: https://mlsanity.com/paper/2409.00159/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 30 Aug 2024.

## Builds on (most cited first, 17 of 17)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [State of What Art? A Call for Multi-Prompt LLM Evaluation](https://mlsanity.com/paper/2401.00595/) (2023)
- [A Comprehensive Survey of Hallucination Mitigation Techniques in Large Language Models](https://mlsanity.com/paper/2401.01313/) (2024)
- [Emergent Analogical Reasoning in Large Language Models](https://mlsanity.com/paper/2212.09196/) (2022)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Hot or Cold? Adaptive Temperature Sampling for Code Generation with Large Language Models](https://mlsanity.com/paper/2309.02772/) (2023)
- [GraphEval: A Knowledge-Graph Based LLM Hallucination Evaluation Framework](https://mlsanity.com/paper/2407.10793/) (2024)
- [Heads, Tails, and AI Fails: LLMs, Randomness, and Human Judgments](https://mlsanity.com/paper/2406.00092/) (2024)
- [Automatic Prompt Selection for Large Language Models](https://mlsanity.com/paper/2404.02717/) (2024)
- [Benchmarking Llama2, Mistral, Gemma and GPT for Factuality, Toxicity, Bias and Propensity for Hallucinations](https://mlsanity.com/paper/2404.09785/) (2024)
- [Leveraging Graph Structures to Detect Hallucinations in Large Language Models](https://mlsanity.com/paper/2407.04485/) (2024)
- [A Comparison of Large Language Model and Human Performance on Random Number Generation Tasks](https://mlsanity.com/paper/2408.09656/) (2024)

## Built on by (most cited first, 3 of 3)

- [A Survey on Evaluating Quality and Trustworthiness in LLM-Generated Data](https://mlsanity.com/paper/2601.17717/) (2026)
- [FLIPS: Instance-Fingerprinting for LLMs via Pseudo-random Sequences](https://mlsanity.com/paper/2606.03330/) (2026)
- [Remembering Unequally: Global and Disciplinary Bias in LLM Reconstruction of Scholarly Coauthor Lists](https://mlsanity.com/paper/2511.00476/) (2025)

## Abstract (arXiv)

Large Language Models (LLMs) are nowadays prompted for a wide variety of tasks. In this article, we investigate their ability in reciting and generating graphs. We first study the ability of LLMs to regurgitate well known graphs from the literature (e.g. Karate club or the graph atlas)4. Secondly, we question the generative capabilities of LLMs by asking for Erdos-Renyi random graphs. As opposed to the possibility that they could memorize some Erdos-Renyi graphs included in their scraped training set, this second investigation aims at studying a possible emergent property of LLMs. For both tasks, we propose a metric to assess their errors with the lens of hallucination (i.e. incorrect information returned as facts). We most notably find that the amplitude of graph hallucinations can characterize the superiority of some LLMs. Indeed, for the recitation task, we observe that graph hallucinations correlate with the Hallucination Leaderboard, a hallucination rank that leverages 10, 000 times more prompts to obtain its ranking. For the generation task, we find surprisingly good and reproducible results in most of LLMs. We believe this to constitute a starting point for more in-depth studies of this emergent capability and a challenging benchmark for their improvements. Altogether, these two aspects of LLMs capabilities bridge a gap between the network science and machine learning communities.