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

We thank the reviewer for taking the time to review our manuscript. We hope to address any concerns through our answers.

• No formal analysis connecting transformer architecture limitations to the observed empirical behavior We respectfully point the reviewer to the theoretical guarantees stated in our Introduction (L35-48) and Related Works section which we base our work on.

Specifically, we refer to (Li et al., 2024), which said that T-chain of thought (CoT) steps can extend transformers’ abilities beyond TC0 – With T being polynomial in the input size, LLMs can, in theory, solve problems in P class like 2-SAT and Horn SAT. However, to the best of our knowledge, there are no empirical works that show to what extent these work in practice, since it is not a binary answer but rather requires a more comprehensive study to evaluate its limits. Our SAT experiments support this, showing improved reasoning with extended CoT steps. Figures 3 and 9 (in Appendix) show that with more CoT steps, R1 completely outperforms other LLMs that use fewer CoT steps. Importantly, in Figure 9, R1 performs with near-perfect accuracy on Horn-SAT and 2-SAT, which is completely aligned with theory. In contrast, LLMs are unable to show perfect solver-like accuracy even for tractable fragments like Horn-SAT (P-Complete) and 2-SAT (NL-Complete).

---

• Insufficient ablation to isolate whether the improvement comes from architecture, training data, RL fine-tuning, or test-time compute We agree that disentangling the exact sources of performance improvement is a valuable research direction. However, the goal of our manuscript is not to pinpoint the origins of R1’s performance gains, but rather to evaluate and characterize the reasoning in LLMs and LRMs in a more principled way. Our focus is thus on capability evaluation, not causal attribution. We argue that rigorous ablation studies—while important—require access to pretraining configurations, architectures, and fine-tuning data pipelines, which are often proprietary. Even in open-source settings, isolating individual contributions demands extensive retraining and computational resources, which are beyond the scope of this paper and have been independently analyzed in recent works (cf., Stechly et al., 2025, Gandhi et al., 2025).

Instead, our work aims to establish a framework for reasoning evaluation and to highlight both the limitations and capabilities of current models. We hope this foundation will support and motivate future work that explores architectural or training-related contributions through more detailed ablation.

[1] Li et al., 2024, Chain of thought empowers transformers to solve inherently serial problems
[2] Stechly et al., 2025, Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens
[3] Gandhi et al., 2025, Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs.

We thank the reviewer for taking the time to review our paper and giving us detailed feedback. We hope to answer your questions and clarify any doubts here.

• Although the implementation of this study is quite good, the idea is not novel. Thank you for pointing out these works. We note that NPHardEval (Fan et al., 2024) was included in an earlier draft of our manuscript, but was unintentionally omitted during revisions. We will reintegrate it into the revised version. Closest to our work is the NPHardEval (Fan et al. (2024)), which examines reasoning across various computational complexity classes, but we additionally explore phase transition characteristics and investigate how the performance varies with inherent hardness of problems. Our evaluation centers on a range of complexity classes known to exhibit phase transitions (Schaefer 1978) including 2-SAT (NL-Complete), 1-3 Horn-SAT (P-Complete), and 3-SAT (NP-Complete). Our comparison of LRMs (R1) with LLMs provide better insights into the effectiveness of longer reasoning traces and establishes better reasoning abilities on the easier and hard regions – and how performance varies with model count (i.e. number of solutions) of a problem.

The same distinctions apply to “RETHINKING LOGIC IN AI” (Nechesov et al., 2025) which is mainly restricted to P-class. That said, the latter manuscript appears to remain unpublished in a peer-reviewed venue (including a recent rejection from ICLR 2025) and is not currently available on preprint servers such as arXiv.

---

• Test-time techniques like Tree-of-thoughts nor evaluated As stated in Lines 170–177 (including Footnote 3), our primary objective is to evaluate the native reasoning capabilities of autoregressive LLMs, independent of external scaffolding or symbolic wrappers.

1. There are theoretical bounds for autogressive LLMs in what they can compute (cf., L 35-48). Investigating their reasoning capabilities in isolation allows us to better understand these inherent bounds without confounding effects introduced by external scaffolds; This is exactly why we evaluate models which we know are autoregressively generating tokens like R1 – and not models like o1 for which we cannot determine the same.
2. Techniques such as Tree-of-Thoughts, Best-of-N sampling, or other tree-based search frameworks effectively wrap LLMs in an external symbolic search. These methods use the LLM to generate ideas (nodes of the tree) while orchestrating search or backtracking over a tree data structure. Crucially, the graph algorithm (e.g., tree traversal, backtracking) is not internally generated or maintained by the LLM. Instead, it is externally imposed. Our goal is to assess whether LLMs can natively reason — for example, whether they can internally generate multiple candidate solutions, maintain them in memory, reason over them, and converge to a consistent answer, within the constraints of autoregressive generation (Figures 4, 7). Even Best-of-N sampling — often treated as a minimal enhancement — effectively introduces a single-layer tree where the LLM samples multiple independent completions. This is still not native reasoning, as the LLM does not internally track or compare alternatives.
3. While we acknowledge that test-time techniques can significantly improve performance, recent literature suggests their effectiveness is tied to the reasoning ability of the base model (Gandhi et al., 2025). Therefore, it is crucial to test these baseline abilities.

We will add these points to the manuscript for further clarification for the readers.

[1] Fan et al., 2024, NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
[2] Nechesov et al., 2025, Rethinking logic in AI: A novel benchmark inspired by polynomial analogue of Gandy's fixed point theorem
[3] Schaefer, T. J. (1978,). The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing.
[4] Gandhi et al., 2025. Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs.

We thank the reviewer for their positive evaluation of our paper. We hope to clarify the scope of our claims here

Drawing the conclusion that *Large Language Models have Learned to Reason* solely based on 3-SAT problems seems a bit far-fetched We respectfully clarify that our claim is more nuanced: we DO NOT assert that LLMs have learned to reason. Rather, we argue that Large Reasoning Models (LRMs) such as R1 exhibit a step-change in reasoning ability compared to previous LLMs (cf., Conclusion section). Our conclusion is not based solely on performance over 3-SAT instances, but rather grounded in a broader, theoretically informed framework for evaluating reasoning across different complexity classes and problem types, including 2-SAT and Horn-SAT.

1. 3-SAT is not an arbitrary task—it is the prototypical NP-Complete problem in complexity theory. As discussed in AI literature, including by Russell & Norvig [2] and Bottou [1], reasoning is characterized by the capacity to solve problems that require compositional, multi-step inference and search. 3-SAT satisfies all these properties, and other (propositional fragments of) reasoning problems such as logic inference, AI planning, and constraint satisfaction, can be mapped to 3-SAT. Thus, it serves as a principled and computationally meaningful testbed for evaluating reasoning capabilities.
2. Our evaluation is not limited to NP-complete problems. We also extend our analysis to problems in lower complexity classes—such as 2-SAT (NL-complete) and 1-3 Horn-SAT (P-complete)—as shown in Figure 9. The fact that R1 achieves near-perfect accuracy on tractable classes and maintains stability in the hard region of 3-SAT strongly suggests the learning of structured reasoning behavior rather than just fitting on statistical patterns like GPT-4o, Gemini 2.0, and Claude 3.7 Sonnet.

In summary, our claim is not that LLMs have universally solved reasoning, but rather that models like R1 exhibit a step-change in reasoning behavior when evaluated under well-defined computational criteria – that is suggestive of them having learned the reasoning rather than fitting on statistical patterns. Our results are also aligned with theoretical limits of transformer architecture (Li et al., 2024), where T-CoT steps (T being polynomial in input) can make transformers strictly more expressive. The methodology and results are aligned with theoretical definitions of reasoning.

That said, as noted in our Conclusion, our 3-SAT benchmarks are bounded (10 variables, 110 clauses), and R1 still struggles in the Hard region. Thus, we acknowledge that R1 is still far from mastering reasoning in a general sense. We will revise the conclusion to better reflect these limitations and further clarify the scope of our claims.

[1] Bottou, Léon, 2014. "From machine learning to machine reasoning: An essay."
[2] Stuart Russell and Peter Norvig, 2010. "Artificial Intelligence: A Modern Approach."
[3] Li et al., 2024, Chain of thought empowers transformers to solve inherently serial problems

We'd like to thank the reviewer for taking the time to review our paper and asking interesting questions.

• Evaluation of reasoning abilities of pretrained models that may have data leakage issues If we understand correctly, the reviewer suspects that SAT data might be present in the training corpus of the pretrained models. If so, this is a great question that we intend to clarify, but we might have fallen short in the paper.

We, too, suspect that ALL models have likely encountered SAT data during pretraining. This is evidenced by their immediate use of terminology and strategies (e.g., tree search, backtracking) when presented with SAT instances in CNF form. However, the core concern is not whether SAT-related content exists in the training data (which it likely does), but whether our specific evaluation is compromised by data leakage.. We address this by considering two scenarios:

1. Exact data overlap. The strongest form of data leakage occurs when the evaluation set contains identical instances present in the model’s training data. This scenario is highly unlikely in our case. We use a custom SAT data generator, and neither the data nor the generator has been open-sourced or publicly released. This rules out direct memorization.

2. In-distribution, but non-identical data. The most plausible scenario is that the evaluation data shares a distributional similarity with pretraining data. Even in this case, our use of 3-SAT—particularly instances from the hard region—minimizes reliance on shallow statistical patterns. In the easy region, LLMs can exploit superficial heuristics (e.g., associating longer input lengths with unsatisfiability, or randomly assigning variables in the satisfiable Easy region). However, in the hard region, such patterns break down, and models must engage in actual multi-step reasoning and search to succeed. This is precisely why we focus on these harder instances.

A third possibility is Out-of-distribution generalization, where models must rely on reasoning rather than statistical shortcuts. This is consistent with prior work (Zhang et al., 2022; Dziri et al., 2023), which demonstrates that LLMs trained on reasoning tasks suffer sharp performance degradation under even modest distribution shifts when fitting on statistical patterns.

We also highlight our SAT-Menu setup, where the problem is reframed as a menu-based preference selection task. It is extremely unlikely that such a format appears in pretraining data, yet we still observe a clear performance gap between R1 and other models (see Figures 3,7).

---

• Based on the reported performance (e.g., Figure 3), it's not very obvious to conclude that R1 is more like true reasoning.

Tendency similar to other LLMs and the performance gap is roughly stable We emphasize that our claim is NOT that R1 has achieved complete reasoning ability (see Conclusion), but that it exhibits a step-change compared to other LLMs. This is not merely based on its performance on 3-SAT (Figure 3), but also its near-perfect performance on 2-SAT (NL-Complete) and 1-3 Horn-SAT (P-Complete) as shown in Figure 9 (in Appendix). Importantly, the stability of R1’s performance across both the easy and hard regions in Figure 3 – and the fact that its hard region performance surpasses even the easy region performance of other LLMs – is not a limitation—it is precisely what characterizes a step-change in reasoning.* Moreover, we show that the performance remains stable regardless of the number of solutions of a problem instance (Fig. 3 right, 11). Our empirical results are further justified by the qualitative analysis of the reasoning traces of R1 and GPT-4o that show that R1 indeed performs a more consistent tree search in an autoregressive manner. Taken together—strong empirical results, consistent behavior traces, and theoretical limits of transformer architecture (Li et al., 2024 and Peng et al., 2024) — we argue that R1 marks a meaningful advancement in the reasoning abilities of LLMs.

Statistical significance missing We have now added confidence intervals to Figures 3 and 9. We use 90% confidence intervals to quantify uncertainty around the estimated accuracy. In the plots, these intervals help assess the reliability of accuracy estimates—narrow bands indicate high certainty, while wider bands suggest greater variability. The figures are available via this anonymous link: https://anonymous.4open.science/r/COLM-rebuttal-figures-95E3/README.md

We thank the reviewer for their suggestion and will include it in the revised version.

[1] Zhang et al., 2022, On the paradox of learning to reason from data
[2] Dziri et al., 2023, Faith and fate: Limits of transformers on compositionality
[3] Li et al., 2024, Chain of thought empowers transformers to solve inherently serial problems
[4] Peng et al., 2024, On limitations of the transformer architecture