Elamur Research⌕
☰
home / papers / 2025 / Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring

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

Paper · 2025 · Alex Heyman and Joel Zylberberg

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 AngelesLos Angeles · United States110 works · 58,035 citations🔬Canadian Institute for Advanced ResearchToronto · Canada36 works · 19,320 citations🎓York UniversityToronto · Canada18 works · 3,378 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

🧭 Topics 3Research subjects and languages the work is about.Language models & pretraining · 4,145 worksReasoning · 1,948 worksEvaluation & 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. DOI 10.48550/arxiv.2502.07087 · arXiv 2502.07087

@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}
}

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. ↗
  2. Arkoudas, K. GPT-4 can’t reason. arXiv:2308.03762, 2023. 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, 2025a. URL https://github.com/deepseek-ai/ DeepSeek-R1/blob/main/DeepSeek_R1. pdf. ↗
  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
  5. DeepSeek-AI. DeepSeek-R1 model card, 2025b. URL https://huggingface.co/deepseek-ai/ DeepSeek-R1. ↗
  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. 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/ v202/shi23a.html. ↗
  8. Stechly, K., Valmeekam, K., and Kambhampati, S. On the self-verification limitations of large language models on reasoning and planning tasks. 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
  10. Wang, B., Yue, X., Su, Y., and Sun, H. Grokked transformers are implicit reasoners: A mechanistic journey to the edge of generalization. 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
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/heyman-2025-evaluating-systematic-reasoning-abilities-large/