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

• URL: http://arxiv.org/abs/2502.07087v1
• Date: Mon, 10 Feb 2025 22:27:02 GMT
• Title: Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring
• Authors: Alex Heyman, Joel Zylberberg,
• Abstract summary: We investigate graph coloring as a means of evaluating an LLM's capacities for systematic step-by-step reasoning and possibility space exploration.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 \leq k \leq 4$ and vertex count $4 \leq n \leq 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.

Related papers

• Unleashing the Reasoning Potential of Pre-trained LLMs by Critique Fine-Tuning on One Problem [53.3188041952701]
  We show that Critique Fine-Tuning (CFT) on only one problem can effectively unleash the reasoning potential of LLMs.<n>With just 5 GPU hours of training, Qwen-Math-7B-CFT show an average improvement of 15% on six math benchmarks and 16% on three logic reasoning benchmarks.<n>Results are comparable to or even surpass the results from RL with 20x less compute.
  arXiv  Detail & Related papers  (2025-06-03T18:35:52Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale graph reasoning abilities.<n>With RL on Erdos, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size)<n>Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks.
  arXiv  Detail & Related papers  (2025-05-24T04:33:41Z)
• Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features [0.0]
  We test o1-mini, o3-mini, DeepSeek-R1, Claude 3.7 Sonnet, Gemini 2.5 Pro Preview, and Grok 3 Mini Beta on graph coloring as a variable-complexity constraint-satisfaction logic problem.<n>We find evidence from both error rate comparisons and CoT/explanation text analysis that RLLMs are prone to hallucinate edges not specified in the prompt's description of the graph.
  arXiv  Detail & Related papers  (2025-05-17T21:55:12Z)
• Climbing the Ladder of Reasoning: What LLMs Can-and Still Can't-Solve after SFT? [59.418994222096885]
  We conduct a detailed analysis of model performance on the AIME24 dataset. We categorize questions into four tiers (Easy, Medium, Hard, and Extremely Hard) We find that progression from Easy to Medium tier requires adopting an R1 reasoning style with minimal SFT-1K instances. Exh-level questions present a fundamentally different challenge; they require unconventional problem-solving skills.
  arXiv  Detail & Related papers  (2025-04-16T03:39:38Z)
• Seeing the Forest and the Trees: Solving Visual Graph and Tree Based Data Structure Problems using Large Multimodal Models [2.1894663332872932]
  We investigate the capabilities of large multimodal models (LMMs) to solve graph and tree data structure problems based only on images.<n>GPT-4o and Gemini 1.5 Flash performed best on trees and graphs respectively.<n>Our findings highlight the influence of structural and visual variations on model performance.
  arXiv  Detail & Related papers  (2024-12-15T07:15:19Z)
• Reasoning Paths Optimization: Learning to Reason and Explore From Diverse Paths [69.39559168050923]
  We introduce Reasoning Paths Optimization (RPO), which enables learning to reason and explore from diverse paths. Our approach encourages favorable branches at each reasoning step while penalizing unfavorable ones, enhancing the model's overall problem-solving performance. We focus on multi-step reasoning tasks, such as math word problems and science-based exam questions.
  arXiv  Detail & Related papers  (2024-10-07T06:37:25Z)
• Polymath: A Challenging Multi-modal Mathematical Reasoning Benchmark [53.61633384281524]
  PolyMATH is a benchmark aimed at evaluating the general cognitive reasoning abilities of MLLMs. The best scores achieved on PolyMATH are 41%, 36%, and 27%, obtained by Claude-3.5 Sonnet, GPT-4o and Gemini-1.5 Pro respectively. A further fine-grained error analysis reveals that these models struggle to understand spatial relations and perform drawn-out, high-level reasoning.
  arXiv  Detail & Related papers  (2024-10-06T20:35:41Z)
• GraphArena: Benchmarking Large Language Models on Graph Computational Problems [25.72820021030033]
  "arms race" of Large Language Models (LLMs) demands novel, challenging, and diverse benchmarks to examine their progresses. We introduce GraphArena, a benchmarking tool to evaluate models on graph computational problems using million-scale real-world graphs.
  arXiv  Detail & Related papers  (2024-06-29T09:19:23Z)
• Navigating the Labyrinth: Evaluating and Enhancing LLMs' Ability to Reason About Search Problems [59.72548591120689]
  We introduce a new benchmark, SearchBench, containing 11 unique search problem types. We show that even the most advanced LLMs fail to solve these problems end-to-end in text. Instructing LLMs to generate code that solves the problem helps, but only slightly, e.g., GPT4's performance rises to 11.7%.
  arXiv  Detail & Related papers  (2024-06-18T00:44:58Z)
• CogCoM: A Visual Language Model with Chain-of-Manipulations Reasoning [61.21923643289266]
  Chain of Manipulations is a mechanism that enables Vision-Language Models to solve problems step-by-step with evidence. After training, models can solve various visual problems by eliciting intrinsic manipulations (e.g., grounding, zoom in) actively without involving external tools. Our trained model, textbfCogCoM, achieves state-of-the-art performance across 9 benchmarks from 4 categories.
  arXiv  Detail & Related papers  (2024-02-06T18:43:48Z)
• Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis [7.099257763803159]
  We evaluate the capabilities of four Large Language Models (LLMs) in addressing several analytical problems with graph data. We employ four distinct evaluation metrics: Correctness, Fidelity, and Rectification. GPT models can generate logical and coherent results, outperforming alternatives in correctness.
  arXiv  Detail & Related papers  (2023-08-22T06:32:07Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)
• Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback [15.429356827868514]
  We introduce a new trade-off mechanism for exploration and exploitation of general feedback graphs. We prove the proposed algorithm simultaneously achieves $mathrmpoly-designed log T$ regret in the adversarial setting. This is the first best-of-both-worlds result for general feedback graphs.
  arXiv  Detail & Related papers  (2022-06-16T04:21:27Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  We derive novel, general upper bounds on the $ell_infty$ estimation error of the Bradley-Terry-Luce model. We demonstrate that the derived bounds perform well and in some cases are sharper compared to known results.
  arXiv  Detail & Related papers  (2021-10-20T23:46:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.