# Graph Reasoning with Large Language Models via Pseudo-code Prompting

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 26 Sep 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

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

- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning](https://mlsanity.com/paper/2308.02565/) (2023)
- [GraphEdit: Large Language Models for Graph Structure Learning](https://mlsanity.com/paper/2402.15183/) (2024)
- [Large Language Models as Topological Structure Enhancers for Text-Attributed Graphs](https://mlsanity.com/paper/2311.14324/) (2023)

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

- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Graph Counselor: Adaptive Graph Exploration via Multi-Agent Synergy to Enhance LLM Reasoning](https://mlsanity.com/paper/2506.03939/) (2025)
- [Graph Linearization Methods for Reasoning on Graphs with Large Language Models](https://mlsanity.com/paper/2410.19494/) (2024)
- [MultiLingPoT: Enhancing Mathematical Reasoning with Multilingual Program Fine-tuning](https://mlsanity.com/paper/2412.12609/) (2024)
- [Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs](https://mlsanity.com/paper/2509.12743/) (2025)
- [Factual and Edit-Sensitive Graph-to-Sequence Generation via Graph-Aware Adaptive Noising](https://mlsanity.com/paper/2604.24104/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have recently achieved remarkable success in various reasoning tasks in the field of natural language processing. This success of LLMs has also motivated their use in graph-related tasks. Among others, recent work has explored whether LLMs can solve graph problems such as counting the number of connected components of a graph or computing the shortest path distance between two nodes. Although LLMs possess preliminary graph reasoning abilities, they might still struggle to solve some seemingly simple problems. In this paper, we investigate whether prompting via pseudo-code instructions can improve the performance of LLMs in solving graph problems. Our experiments demonstrate that using pseudo-code instructions generally improves the performance of all considered LLMs. The graphs, pseudo-code prompts, and evaluation code are publicly available.