mlsanityData to 7 Oct 2026

Fast Analysis of the OpenAI O1-Preview Model in Solving Random K-SAT Problem: Does the LLM Solve the Problem Itself or Call an External SAT Solver?

arXiv 2409.11232 ↗First posted 17 Sep 2024cs.CL cond-mat.dis-nn cs.AIcited by 3

Not on the map. Why?

Abstract (arXiv)

In this manuscript, I present an analysis on the performance of OpenAI O1-preview model in solving random K-SAT instances for K∈ 2,3,4 as a function of α=M/N where M is the number of clauses and N is the number of variables of the satisfiable problem. I show that the model can call an external SAT solver to solve the instances, rather than solving them directly. Despite using external solvers, the model reports incorrect assignments as output. Moreover, I propose and present an analysis to quantify whether the OpenAI O1-preview model demonstrates a spark of intelligence or merely makes random guesses when outputting an assignment for a Boolean satisfiability problem.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 13 of its 32 references that are in the map. First posted on arXiv 17 Sep 2024.

Builds on

13 of 32 references.

References · 13

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  4. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  6. 2017Solving high-dimensional partial differential equations using deep learningcited by 549
  7. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  8. 2023Representational Strengths and Limitations of Transformerscited by 132
  9. 2015The backtracking survey propagation algorithm for solving random K-SAT problemscited by 14
  10. 2020Learning from Survey Propagation: a Neural Network for MAX-E-3-SATcited by 11
  11. 2020Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemescited by 11
  12. 2023Phase transitions in the mini-batch size for sparse and dense two-layer neural networkscited by 9
1 more
  1. 2024Enhancing LLM Problem Solving with REAP: Reflection, Explicit Problem Deconstruction, and Advanced Promptingcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 1.

3 papers.

  1. 2024A Systematic Assessment of OpenAI o1-Preview for Higher Order Thinking in Educationcited by 16
  2. 2025PEA: Enhancing LLM Performance on Computational-Reasoning Taskscited by 1
  3. 2024System 2 Reasoning for Human-AI Alignment: Generality and Adaptivity via ARC-AGIcited by 0