Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires & Luc De Raedt · 2025
Read Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition by Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires & Luc De Raedt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03930.txt.
Introduction
Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires, and Luc De Raedt test whether large language models reason or merely pattern-match, using the hardest corner of a classic problem. Their 2025 paper builds the test on 3-SAT, the standard NP-complete logic puzzle. Random instances of it pass through a phase transition, from easy to nearly unsolvable, as clauses pile onto variables.
Across that dial, the models' accuracy fell steeply on the hard side, where statistical shortcuts run out. That was true for the field generally. One model stood apart: DeepSeek's R1 showed signs of having learned something like the underlying reasoning, holding up better where the others collapsed. The authors present the phase transition as a principled gauge for reasoning claims, sharper than the usual benchmarks. The result maps where today's models stop reasoning and start guessing.
Catalog record
| CREATOR | Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires & Luc De Raedt |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-03930
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires & Luc De Raedt 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. 1 Introduction The success and versatility of Large Language Models (LLMs) have sparked widespread interest and debate on whether LLMs are capable of reasoning. Recent studies suggest that LLMs are inherently capable of zero-shot reasoning ( Kojima et al., 2022 ) . This ability has been shown to emerge and improve with scale ( Wei et al., 2022a ; Srivastava et al., 2023 ) , and can be further enhanced by using smart prompting techniques that encourage LLMs to think step-by-step ( Wei et al., 2022b ; Yao et al., 2023b ) . Demonstrations include, inter alia, planning ( Huang et al., 2022 ; Ahn et al., 2022 ; Hazra et al., 2024b ) , theorem proving ( Jiang et al., 2023 ; Welleck et al., 2022 ; Yang et al., 2022 ) , search and optimization ( Yang et al., 2024 ; Romera-Paredes et al., 2024 ; Hazra et al., 2024a ) , self-reflection ( Yao et al., 2023a ; Madaan et al., 2023 ) , and tool usage ( Schick et al., 2023 ) . Conversely, a growing body of research presents a more critical view of these reasoning abilities. For instance, LLMs may exhibit limitations in consistent logical reasoning ( Arkoudas, 2023 ; Saparov & He, 2023 ) , effective planning ( Valmeekam et al., 2022 ) , and accurate self-evaluation of their outputs ( Stechly et al., 2023 ) . So, to what extent can LLMs reason? To answer this question, recent works have resorted to characterizing the theoretical capabilities and limitations of LLMs through worst-case complexity analysis. Peng et al. (2024) demonstrated that multi-layer transformers cannot solve problems such as Derivability, 2-SAT, Horn SAT, and Circuit Evaluation. However, with T -chain of thought (CoT) steps, transformers’ abilities can be extended up to those solvable by Boolean circuits of size T ( Li et al., 2024 ) . Moreover, with polynomially many correct intermediate CoT steps, an LLM can compute all circuits in polynomial size, P/poly, a superclass of P. As a consequence, LLMs should be able to solve reasoning problems falling into these complexity classes such as 2-SAT and Horn-SAT. It is also expected to solve some instances of 3-SAT, but not all – since certain 3-SAT problems may require circuit complexities that exceed polynomial bounds. Empirically, this aligns with test-time compute scaling studies that show improved reasoning performance with increased computational resources ( Lightman et al., 2024 ; Snell et al., 2025 ) . Thus, from a theoretical standpoint, LLMs equipped with CoT possess the capacity to solve reasoning problems falling in P or P/Poly . However, despite this, recent works have shown that LLMs are not learning to reason , by fitting on statistical features and not internalizing the logic (i.e. learning to reproduce the style and not logic) ( Zhang et al., 2023 ) much like the Clever Hans Cheat ( Bachmann & Nagarajan, 2024 ) . With the advent of Large Reasoning Models (LRMs) like DeepSeek R1 ( DeepSeek-AI, 2025a ) which leverage more test-time compute, there is renewed optimism about enhancing reasoning capabilities. However, it is unclear if this marks a real step change, due to limitations in current reasoning benchmarks like (1) growing concerns about dataset contamination 1 1 1 Data closely resembling the benchmark leaks into the training data. ( Zhang et al., 2024 ) that can inflate the reasoning performance; (2) conflation of commonsense reasoning rooted in retrieving world knowledge, and logical or deductive reasoning – requiring algebraic manipulation of knowledge ( Genesereth & Nilsson, 1987 ) – making it challenging to decouple the two. To move beyond these limitations, a more principled approach to evaluating reasoning is needed. We adopt Leon Bottou’s definition, which defines reasoning as “ algebraically manipulating previously acquired knowledge to answer a new question ” ( Bottou, 2014 ) . This closely aligns with Russell and Norvig’s description of AI as rational thinking ( Russell & Norvig, 2010 ) . Building on this, we ask: Have LLMs learned to reason, and if so, to what extent? We answer through the following contributions: (1) Characterizing LLM-reasoning from a computational theory perspective. Adhering to Leon Bottou’s definition, we propose an experimental framework centered on 3-SAT, to evaluate reasoning. Introduced in Figure 1 , 3-SAT is a foundational problem in computational complexity, and many problems in AI such as (propositional fragments of) logical reasoning, planning, and constraint satisfaction can be reduced to 3-SAT. We also extend our analysis to tractable fragments like 2-SAT (NL-Complete) ( Bollobás et al., 2001 ) and 1-3 Horn-SAT (P-Complete) ( Demopoulos & Vardi, 2006 ) which also exhibit phase transitions, revealing interesting observations across complexity classes. Our approach provides a formal and robust evaluation of reasoning abilities and bridges computational theory with modern AI. (2) Studying Phase Transition Characteristics of LLMs. We investigate the phase transition characteristics of LLMs ( Cheeseman et al., 1991 ) , i.e., how LLMs’ performance varies in the easy and hard regions of the problem space, unlike standard reasoning benchmarks that overlook variations due to inherent hardness of problems. We observe that LLM performance declines in the hard region where statistical features are largely absent. (3) Comprehensive evaluation of state-of-the-art open-source and proprietary LLMs. We conducted extensive experiments across state-of-the-art open-source and proprietary LLMs. We find a significant gap between the performances of DeepSeek R1 ( DeepSeek-AI, 2025a ) to other LLMs like GPT-4o ( OpenAI, 2024 ) , Claude 3.7 Sonnet ( Anthropic, 2025 ) , Gemini 2.0 Flash ( Google, 2024 ) , and DeepSeek V3 ( DeepSeek-AI, 2025b ) . Interestingly, the CoT traces produced by DeepSeek R1 reveal patterns suggestive of an in-context tree search with backtracking, which may account for its superior performance. In contrast, the other models consistently fail to demonstrate comparable reasoning capabilities. This leads us to believe that LRMs like R1 could be a step-change in reasoning abilities . Figure