# Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring

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

## Key facts

- Cited by 10 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 22 references that are in the map.
- First posted on arXiv 10 Feb 2025.

## 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)

- [A Comprehensive Overview of Large Language Models](https://mlsanity.com/paper/2307.06435/) (2023)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [The Butterfly Effect of Altering Prompts: How Small Changes and Jailbreaks Affect Large Language Model Performance](https://mlsanity.com/paper/2401.03729/) (2024)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization](https://mlsanity.com/paper/2405.15071/) (2024)
- [GPT-4 Can't Reason](https://mlsanity.com/paper/2308.03762/) (2023)

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

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features](https://mlsanity.com/paper/2505.12151/) (2025)
- [Reasoning Models Reason Well, Until They Don't](https://mlsanity.com/paper/2510.22371/) (2025)
- [ReEfBench: Quantifying the Reasoning Efficiency of LLMs](https://mlsanity.com/paper/2601.03550/) (2026)
- [Evaluating Robustness of Reasoning Models on Parameterized Logical Problems](https://mlsanity.com/paper/2602.12665/) (2026)
- [HyperGuide: Hyperbolic Guidance for Efficient Multi-Step Reasoning in Large Language Models](https://mlsanity.com/paper/2605.24140/) (2026)
- [PlanarBench: Evaluating LLM Spatial Reasoning via Planar Graph Drawing](https://mlsanity.com/paper/2606.02010/) (2026)
- [LLMs for Resource Allocation: A Participatory Budgeting Approach to Inferring Preferences](https://mlsanity.com/paper/2508.06060/) (2025)
- [On Asymmetric Optimization of Reasoning and Perception in Vision-Language Model Post-Training](https://mlsanity.com/paper/2605.29496/) (2026)
- [RamseyGadgets: A Graph Construction Dataset for LLMs](https://mlsanity.com/paper/2608.14999/) (2026)

## Abstract (arXiv)

Contemporary large language models are powerful problem-solving tools, but they exhibit weaknesses in their reasoning abilities which ongoing research seeks to mitigate. We investigate graph coloring as a means of evaluating an LLM's capacities for systematic step-by-step reasoning and possibility space exploration, as well as effects of semantic problem framing. We test Claude 3.5 Sonnet, Llama 3.1 405B, Gemini 1.5 Pro, GPT-4o, o1-mini, and DeepSeek-R1 on a dataset of k-coloring problems with 2 ≤ k ≤ 4 and vertex count 4 ≤ n ≤ 8, using partial algorithmic solvers to further categorize problems by difficulty. In addition to substantial but varying framing effects, we find that all models except o1-mini and R1 exhibit >60% error rates on difficult problem types in all frames (>15% for o1-mini and >10% for R1), and no model achieves perfect accuracy even in the simple domain of 2-coloring 4-vertex graphs. Our results highlight both the considerable recent progress in LLM systematic reasoning and the limits of its reliability, especially in relation to increasing computational costs. We expect that more complex graph coloring problems, and procedural generation of arbitrary-complexity reasoning problems more broadly, offer further untapped potential for LLM benchmarking.