---
title: "Evaluating the Systematic Reasoning Abilities of Large Language"
description: "Heyman and Zylberberg use graph coloring to test whether large language models can reason step by… 12 references, cited by 4 papers here."
authors: ["Alex Heyman", "Joel Zylberberg"]
year: 2025
venue: "arXiv:2502.07087"
source: "https://arxiv.org/abs/2502.07087"
doi: "10.48550/arxiv.2502.07087"
arxiv: "2502.07087"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/heyman-2025-evaluating-systematic-reasoning-abilities-large/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/heyman-2025-evaluating-systematic-reasoning-abilities-large/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2025](https://md.research.elamur.ai/free/en/papers/2025/page/14/) / Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring

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

**Authors:** Alex Heyman and Joel Zylberberg · **Year:** 2025 · **Venue:** arXiv:2502.07087 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2502.07087) · [PDF](https://arxiv.org/pdf/2502.07087) · [DOI 10.48550/arxiv.2502.07087](https://doi.org/10.48550/arxiv.2502.07087) · [arXiv 2502.07087](https://arxiv.org/abs/2502.07087) · [OpenAlex](https://openalex.org/W4407424147)

**Citations:** 0 citations (OpenAlex, 2026-10-14) · [4](https://md.research.elamur.ai/free/en/papers/heyman-2025-evaluating-systematic-reasoning-abilities-large/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Heyman and Zylberberg use graph coloring to test whether large language models can reason step by step and search through alternatives when a first attempt fails. Graph coloring suits this purpose because it is NP-complete. New instances are cheap to generate at any chosen complexity, which limits data contamination, and the same structure can be described in different everyday scenarios.

The authors built five k-coloring problem sets with 4–8 vertices and 2–4 colors. They scored difficulty with a randomized greedy solver and posed each problem in up to four semantic frames. Six models were evaluated: Claude 3.5 Sonnet, Llama 3.1 405B, Gemini 1.5 Pro, GPT-4o, o1-mini and DeepSeek-R1.

The reasoning-oriented models (o1-mini, DeepSeek-R1) clearly beat the standard LLMs. Still, every model made errors even on the simplest problems, and framing changed results noticeably. The authors conclude that recent progress in LLM reasoning is real but not yet reliable. They caution that making chains of thought longer is a costly route that probably will not fix robustness. Instead, they recommend new architectures and training methods.

## Key points
- **Problem sets:**
  - 4v2c: all 63 non-empty 4-vertex graphs.
  - 5v2c: all 1023 non-empty 5-vertex graphs.
  - 6v3c, 7v3c, 8v4c: sampled sets of 631, 943 and 1307 graphs.
  - Some graphs are non-planar, so not all are 4-colorable.
- **Difficulty scoring:**
  - Each colorable graph gets a "greedy score" g, the success rate over 10,000 runs of a randomized greedy solver. Problems are binned as g ≥ 0.9, 0.5 ≤ g \< 0.9 and g \< 0.5.
  - Uncolorable graphs are split into C-uncolorable and D-uncolorable, the second type being less obviously impossible.
- **Frames:** Math, Cities (monuments in cities linked by highways), Friends (shirt colors in a friendship network), and Math (demanding). The last differs from Math only by a small change in wording.
- **Error rates on hard categories:** the four standard LLMs exceeded 60% in every frame, o1-mini exceeded 15% and DeepSeek-R1 exceeded 10%. No model was error-free even on 4v2c.
- **Framing effects:** all models showed substantial framing effects, but the patterns differed between models. Even the minor Math vs. Math (demanding) wording change shifted performance in some settings.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of California, Los Angeles](https://md.research.elamur.ai/free/en/universities/university-of-california-los-angeles/) — University, Los Angeles, United States · 110 works · 58,034 citations
- [Canadian Institute for Advanced Research](https://md.research.elamur.ai/free/en/labs/canadian-institute-for-advanced-research/) — Research institute, Toronto, Canada · 36 works · 19,320 citations
- [York University](https://md.research.elamur.ai/free/en/universities/york-university/) — University, Toronto, Canada · 18 works · 3,378 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,959 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,789 works

🧭 Topics (3): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 4,145 works · [🧮 Reasoning](https://md.research.elamur.ai/free/en/topics/reasoning/) · 1,948 works · [📏 Evaluation & benchmarks](https://md.research.elamur.ai/free/en/topics/evaluation-benchmarks/) · 1,394 works

## Cite

Cite as: Alex Heyman and Joel Zylberberg. 2025. Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring. arXiv:2502.07087.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{heyman2025evaluating,
  title = {{Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring}},
  author = {Alex Heyman and Joel Zylberberg},
  year = {2025},
  doi = {10.48550/arxiv.2502.07087},
  eprint = {2502.07087},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2502.07087}
}
```

- [← previous Evaluating the Effectiveness of Direct Preference Optimization for Personalizing German Automatic Text Simplifications for Persons with Intellectual Disabilities](https://md.research.elamur.ai/free/en/papers/gao-2025-evaluating-effectiveness-direct-preference-optimization/)
- [next → Every FLOP Counts: Scaling a 300B Mixture-of-Experts LING LLM without Premium GPUs](https://md.research.elamur.ai/free/en/papers/ling-team-2025-every-flop-counts-scaling/)
- [↑ back to papers of 2025](https://md.research.elamur.ai/free/en/papers/2025/page/14/)

## References

12 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Anthropic. Claude 3.5 Sonnet, 2024. URL [https://www.anthropic.com/news/claude-3-5-sonnet](https://www.anthropic.com/news/claude-3-5-sonnet). [↗](https://www.anthropic.com/news/claude-3-5-sonnet)
2. Arkoudas, K. GPT-4 can’t reason. arXiv:2308.[03762, 2023](https://md.research.elamur.ai/free/en/papers/arkoudas-2023-gpt-4-t-reason/). arXiv preprint Press, O., Zhang, M., Min, S., Schmidt, L., Smith, N., and Lewis, M. Measuring and narrowing the compositionality gap in language models. Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 5687– 5711, 202…
3. DeepSeek-AI. [DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning](https://md.research.elamur.ai/free/en/papers/deepseek-ai-2025-deepseek-r1-incentivizing-reasoning-capability/), 2025a. URL [https://github.com/deepseek-ai/](https://github.com/deepseek-ai/) DeepSeek-R1/blob/main/DeepSeek_R1. pdf. [↗](https://github.com/deepseek-ai/)
4. Salinas, A. and Morstatter, F. The butterfly effect of altering prompts: How small changes and jailbreaks affect large language model performance. arXiv preprint arXiv:2401.03729, 2024. [find](https://scholar.google.com/scholar?q=Salinas%2C+A%2E+and+Morstatter%2C+F%2E+The+butterfly+effect+of+altering+prompts%3A+How+small+changes+and+jailbreaks+affect+large+language+model+performance%2E+arXiv+preprint+arXiv%3A2401%2E03729%2C+2024%2E)
5. DeepSeek-AI. DeepSeek-R1 model card, 2025b. URL [https://huggingface.co/deepseek-ai/](https://huggingface.co/deepseek-ai/) DeepSeek-R1. [↗](https://huggingface.co/deepseek-ai/)
6. Shi, F., Chen, X., Misra, K., Scales, N., Dohan, D., Chi, E. H., Schärli, N., and Zhou, D. [Large language models can be easily distracted by irrelevant context](https://md.research.elamur.ai/free/en/papers/shi-2023-large-language-models-easily-distracted/). In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conferen…
7. Learning Research, pp. 31210–31227. PMLR, 23–29 Jul 2023. URL [https://proceedings.mlr.press/](https://proceedings.mlr.press/) v202/shi23a.html. [↗](https://proceedings.mlr.press/)
8. Stechly, K., Valmeekam, K., and Kambhampati, S. [On the self-verification limitations of large language models on reasoning and planning tasks](https://md.research.elamur.ai/free/en/papers/stechly-2024-self-verification-limitations-large-language/). arXiv preprint arXiv:2402.08115, 2024.
9. Valmeekam, K., Stechly, K., and Kambhampati, S. LLMs still can’t plan; can LRMs? a preliminary evaluation of OpenAI’s o1 on PlanBench. arXiv preprint arXiv:2409.13373, 2024. — [arXiv:2409.13373](https://arxiv.org/abs/2409.13373) [find](https://scholar.google.com/scholar?q=Valmeekam%2C+K%2E%2C+Stechly%2C+K%2E%2C+and+Kambhampati%2C+S%2E+LLMs+still+can%E2%80%99t+plan%3B+can+LRMs%3F+a+preliminary+evaluation+of+OpenAI%E2%80%99s+o1+on+PlanBench%2E+arXiv+preprint+arXiv%3A2409%2E13373%2C+2024%2E+%E2%80%94+%5BarXiv%3A2409%2E13373%5D%28https)
10. Wang, B., Yue, X., Su, Y., and Sun, H. [Grokked transformers are implicit reasoners: A mechanistic journey to the edge of generalization](https://md.research.elamur.ai/free/en/papers/wang-2024-grokked-transformers-implicit-reasoners-mechanistic/). arXiv preprint arXiv:2405.15071, 2024.
11. Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024. [find](https://scholar.google.com/scholar?q=Yao%2C+S%2E%2C+Yu%2C+D%2E%2C+Zhao%2C+J%2E%2C+Shafran%2C+I%2E%2C+Griffiths%2C+T%2E%2C+Cao%2C+Y%2E%2C+and+Narasimhan%2C+K%2E+Tree+of+thoughts%3A+Deliberate+problem+solving+with+large+language+models%2E+Advances+in+Neural+Information+Processing+Sy)
12. Zhou, L., Schellaert, W., Martı́nez-Plumed, F., Moros-Daval, Y., Ferri, C., and Hernández-Orallo, J. Larger and more instructable language models become less reliable. Nature, pp. 1–8, 2024. [find](https://scholar.google.com/scholar?q=Zhou%2C+L%2E%2C+Schellaert%2C+W%2E%2C+Mart%C4%B1%CC%81nez%2DPlumed%2C+F%2E%2C+Moros%2DDaval%2C+Y%2E%2C+Ferri%2C+C%2E%2C+and+Herna%CC%81ndez%2DOrallo%2C+J%2E+Larger+and+more+instructable+language+models+become+less+reliable%2E+Nature%2C+pp%2E+1%E2%80%938%2C+2024%2E)

*Updated 3 November 2026*