mlsanityData to 14 Oct 2026

Can Transformers Reason Logically? A Study in SAT Solving

arXiv 2410.07432 ↗First posted 9 Oct 2024cs.LG cs.AI cs.LOcited by 16

On the map: LLM reasoning → Reasoning benchmarks and evaluation

Abstract (arXiv)

We formally study the logical reasoning capabilities of decoder-only Transformers in the context of the boolean satisfiability (SAT) problem. First, we prove by construction that decoder-only Transformers can decide 3-SAT, in a non-uniform model of computation, using backtracking and deduction via Chain-of-Thought (CoT). %We prove its correctness by showing trace equivalence to the well-known DPLL SAT-solving algorithm. Second, we implement our construction as a PyTorch model with a tool (PARAT) that we designed to empirically demonstrate its correctness and investigate its properties. Third, rather than textitprogramming a transformer to reason, we evaluate empirically whether it can be textittrained to do so by learning directly from algorithmic traces (``reasoning paths'') from our theoretical construction. The trained models demonstrate strong out-of-distribution generalization on problem sizes seen during training but has limited length generalization, which is consistent with the implications of our theoretical result

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. Builds on 27 of its 40 references that are in the map. First posted on arXiv 9 Oct 2024.

Builds on

27 of 40 references.

Closest ancestors · 7

Same direction, newest first

  1. 2024Can Large Language Models Reason? A Characterization via 3-SAT13 Aug
  2. 2023NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes22 Dec
  3. 2023Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examples24 May
  4. 2023Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning20 May
  5. 2023LLaMA: Open and Efficient Foundation Language Models27 Feb
  6. 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought3 Oct
  7. 2022On the Paradox of Learning to Reason from Data23 May

Other references · 20

  1. 2017Attention Is All You Needcited by 60,361
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  3. 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 324
  4. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  5. 2020Transformers as Soft Reasoners over Languagecited by 270
  6. 2022Transformers Learn Shortcuts to Automatacited by 268
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  8. 2023Looped Transformers as Programmable Computerscited by 237
  9. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  10. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  11. 2021Thinking Like Transformerscited by 184
  12. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
8 more
  1. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  2. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  3. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
  4. 2024Faithful Logical Reasoning via Symbolic Chain-of-Thoughtcited by 100
  5. 2023Code Execution with Pre-trained Language Modelscited by 34
  6. 2022SATformer: Transformer-Based UNSAT Core Learningcited by 14
  7. 2024Can Language Models Pretend Solvers? Logic Code Simulation with LLMscited by 4
  8. 2021MatSat: a matrix-based differentiable SAT solvercited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 6; 2026: 10.

16 papers.

Sort:

By area:

  1. 2025ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoningcited by 201
  2. 2025Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokenscited by 41
  3. 2025SATBench: Benchmarking LLMs' Logical Reasoning via Automated Puzzle Generation from SAT Formulascited by 33
  4. 2025Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexitycited by 9
  5. 2025Evaluating Implicit Biases in LLM Reasoning through Logic Grid Puzzlescited by 1
  6. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  7. 2026Evaluating Robustness of Reasoning Models on Parameterized Logical Problemscited by 1
  8. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Tracescited by 1
  9. 2026Self-Improvement for Fast, High-Quality Plan Generationcited by 1
  10. 2025Boolean Satisfiability via Imitation Learningcited by 0
  11. 2026Infeasibility Aware Large Language Models for Combinatorial Optimizationcited by 0
  12. 2026Early-Stage Product Line Validation Using LLMs: A Study on Semi-Formal Blueprint Analysiscited by 0
4 more
  1. 2026Learning How to Cubecited by 0
  2. 2026Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoningcited by 0
  3. 2026Learning Symbolic Constraint Representations from Examples: A Neuro-Symbolic Approachcited by 0
  4. 2026Conditional Transfer from Controlled Pretraining Mixtures to Codecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
  2. 2026Satisfiability Solving with LLMs: A Matched-Pair Evaluation of Reasoning Capability
  3. 2024Reasoning in Transformers -- Mitigating Spurious Correlations and Reasoning Shortcuts
  4. 2023Assessing Logical Reasoning Capabilities of Encoder-Only Transformer Models
  5. 2025Natural Language Satisfiability: Exploring the Problem Distribution and Evaluating Transformer-based Language Models
  6. 2026To See the Unseen: on the Generalization Ability of Transformers in Symbolic Reasoning
  7. 2026SAT-RL: Training Language Models for Logical Reasoning with Symbolic Solvers
  8. 2023The Expressive Power of Transformers with Chain of Thought