Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition

• URL: http://arxiv.org/abs/2504.03930v1
• Date: Fri, 04 Apr 2025 20:57:36 GMT
• Title: Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
• Authors: Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires, Luc De Raedt,
• Abstract summary: Large Language Models (LLMs) have been touted as AI models possessing advanced reasoning abilities.<n>In theory, autoregressive LLMs with Chain-of-Thought (CoT) can perform more serial computations to solve complex reasoning tasks.<n>Recent studies suggest that, despite this capacity, LLMs do not truly learn to reason but instead fit on statistical features.
• Score: 11.422434149376478
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) have been touted as AI models possessing advanced reasoning abilities. In theory, autoregressive LLMs with Chain-of-Thought (CoT) can perform more serial computations to solve complex reasoning tasks. However, recent studies suggest that, despite this capacity, LLMs do not truly learn to reason but instead fit on statistical features. To study the reasoning capabilities in a principled fashion, we adopt a computational theory perspective and propose an experimental protocol centered on 3-SAT -- the prototypical NP-complete problem lying at the core of logical reasoning and constraint satisfaction tasks. Specifically, we examine the phase transitions in random 3-SAT and characterize the reasoning abilities of state-of-the-art LLMs by varying the inherent hardness of the problem instances. By comparing DeepSeek R1 with other LLMs, our findings reveal two key insights (1) LLM accuracy drops significantly on harder instances, suggesting all current models struggle when statistical shortcuts are unavailable (2) Unlike other LLMs, R1 shows signs of having learned the underlying reasoning. Following a principled experimental protocol, our study moves beyond the benchmark-driven evidence often found in LLM reasoning research. Our findings highlight important gaps and suggest clear directions for future research.

Related papers

• Unveiling the Magic of Code Reasoning through Hypothesis Decomposition and Amendment [54.62926010621013]
  We introduce a novel task, code reasoning, to provide a new perspective for the reasoning abilities of large language models. We summarize three meta-benchmarks based on established forms of logical reasoning, and instantiate these into eight specific benchmark tasks. We present a new pathway exploration pipeline inspired by human intricate problem-solving methods.
  arXiv  Detail & Related papers  (2025-02-17T10:39:58Z)
• Critical-Questions-of-Thought: Steering LLM reasoning with Argumentative Querying [0.3659498819753633]
  State-of-the-art Large Language models (LLMs) continue to struggle when performing logical and mathematical reasoning. This paper makes use of the notion of critical questions from the literature on argumentation theory, focusing in particular on Toulmin's model of argumentation. We show that employing these critical questions can improve the reasoning capabilities of LLMs.
  arXiv  Detail & Related papers  (2024-12-19T18:51:30Z)
• What Makes In-context Learning Effective for Mathematical Reasoning: A Theoretical Analysis [81.15503859645149]
  In this paper, we aim to theoretically analyze the impact of in-context demonstrations on large language models' reasoning performance. We propose a straightforward, generalizable, and low-complexity demonstration selection method named LMS3.
  arXiv  Detail & Related papers  (2024-12-11T11:38:11Z)
• Can Large Language Models Reason? A Characterization via 3-SAT [11.422434149376478]
  Large Language Models (LLMs) have been touted as AI models possessing advanced reasoning abilities. Recent works have shown that LLMs often bypass true reasoning using shortcuts, sparking skepticism. We propose an experimental protocol centered on 3-SAT -- the NP-complete problem lying at the core of logical reasoning and constraint satisfaction tasks.
  arXiv  Detail & Related papers  (2024-08-13T21:54:10Z)
• LogicBench: Towards Systematic Evaluation of Logical Reasoning Ability of Large Language Models [52.03659714625452]
  Recently developed large language models (LLMs) have been shown to perform remarkably well on a wide range of language understanding tasks. But, can they really "reason" over the natural language? This question has been receiving significant research attention and many reasoning skills such as commonsense, numerical, and qualitative have been studied.
  arXiv  Detail & Related papers  (2024-04-23T21:08:49Z)
• A Closer Look at the Self-Verification Abilities of Large Language Models in Logical Reasoning [73.77088902676306]
  We take a closer look at the self-verification abilities of large language models (LLMs) in the context of logical reasoning. Our main findings suggest that existing LLMs could struggle to identify fallacious reasoning steps accurately and may fall short of guaranteeing the validity of self-verification methods.
  arXiv  Detail & Related papers  (2023-11-14T07:13:10Z)
• Improving Large Language Models in Event Relation Logical Prediction [33.88499005859982]
  Event relation extraction is a challenging task that demands thorough semantic understanding and rigorous logical reasoning. In this paper, we conduct an in-depth investigation to systematically explore the capability of LLMs in understanding and applying event relation logic. Our study reveals that LLMs are not logically consistent reasoners, which results in their suboptimal performance on tasks that need rigorous reasoning.
  arXiv  Detail & Related papers  (2023-10-13T14:53:06Z)
• Towards LogiGLUE: A Brief Survey and A Benchmark for Analyzing Logical Reasoning Capabilities of Language Models [56.34029644009297]
  Large language models (LLMs) have demonstrated the ability to overcome various limitations of formal Knowledge Representation (KR) systems. LLMs excel most in abductive reasoning, followed by deductive reasoning, while they are least effective at inductive reasoning. We study single-task training, multi-task training, and "chain-of-thought" knowledge distillation fine-tuning technique to assess the performance of model.
  arXiv  Detail & Related papers  (2023-10-02T01:00:50Z)
• Exploring Self-supervised Logic-enhanced Training for Large Language Models [59.227222647741094]
  In this paper, we make the first attempt to investigate the feasibility of incorporating logical knowledge through self-supervised post-training. We devise an auto-regressive objective variant of MERIt and integrate it with two LLM series, i.e., FLAN-T5 and LLaMA, with parameter size ranging from 3 billion to 13 billion. The results on two challenging logical reasoning benchmarks demonstrate the effectiveness of LogicLLM.
  arXiv  Detail & Related papers  (2023-05-23T06:13:10Z)

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.