# Can Large Language Models Reason? A Characterization via 3-SAT

arXiv: https://arxiv.org/abs/2408.07215 · HTML: https://mlsanity.com/paper/2408.07215/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 5 of its 77 references that are in the map.
- First posted on arXiv 13 Aug 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 5 of 5)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [REvolve: Reward Evolution with Large Language Models using Human Feedback](https://mlsanity.com/paper/2406.01309/) (2024)
- [AutoSAT: Automatically Optimize SAT Solvers via Large Language Models](https://mlsanity.com/paper/2402.10705/) (2024)

## Built on by (most cited first, 12 of 12)

- [Inference-Time Scaling for Complex Tasks: Where We Stand and What Lies Ahead](https://mlsanity.com/paper/2504.00294/) (2025)
- [Can Transformers Reason Logically? A Study in SAT Solving](https://mlsanity.com/paper/2410.07432/) (2024)
- [Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs](https://mlsanity.com/paper/2504.11239/) (2025)
- [Large corpora and large language models: a replicable method for automating grammatical annotation](https://mlsanity.com/paper/2411.11260/) (2024)
- [Learning by Analogy: Enhancing Few-Shot Prompting for Math Word Problem Solving with Computational Graph-Based Retrieval](https://mlsanity.com/paper/2411.16454/) (2024)
- [Agentic Systems in Radiology: Design, Applications, Evaluation, and Challenges](https://mlsanity.com/paper/2510.09404/) (2025)
- [Symbol-Equivariant Recurrent Reasoning Models](https://mlsanity.com/paper/2603.02193/) (2026)
- [Foundation Models in Biomedical Imaging: Turning Hype into Reality](https://mlsanity.com/paper/2512.15808/) (2025)
- [Randomly Sampled Language Reasoning Problems Elucidate Limitations of In-Context Learning](https://mlsanity.com/paper/2501.02825/) (2025)
- [Training Transformers as a Universal Computer](https://mlsanity.com/paper/2604.25166/) (2026)
- [Verbalized Algorithms: Classical Algorithms are All You Need (Mostly)](https://mlsanity.com/paper/2509.08150/) (2025)
- [Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoning](https://mlsanity.com/paper/2607.17047/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have been touted as AI models possessing advanced reasoning abilities. However, recent works have shown that LLMs often bypass true reasoning using shortcuts, sparking skepticism. 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 LLMs by varying the inherent hardness of the problem instances. Our experimental evidence shows that LLMs are incapable of performing true reasoning, as required for solving 3-SAT problems. Moreover, we observe significant performance variation based on the inherent hardness of the problems -- performing poorly on harder instances and vice versa. Importantly, we show that integrating external reasoners can considerably enhance LLM performance. By following a principled experimental protocol, our study draws concrete conclusions and moves beyond the anecdotal evidence often found in LLM reasoning research.