Overview
This research investigates the reasoning ability of large language models (LLMs) when applied to Boolean Satisfiability (SAT) problems and related canonical reductions. The study employed 2-SAT and 3-SAT instances, alongside reductions to Vertex Cover and discrete 3D packing problems, to examine representation-invariant reasoning. It assesses conventional metrics' effectiveness and introduces a novel paired-formula protocol with Accurate Differentiation Rate (ADR) for a more precise evaluation of LLM reasoning capabilities.
Research Context
LLMs are increasingly utilized for tasks that implicitly involve Boolean satisfiability (SAT). However, their specific reasoning abilities concerning SAT problems have not been clearly established. This study addresses this gap by systematically evaluating LLMs on SAT and its canonical reductions. The objective is to understand how LLMs perform on such reasoning-intensive tasks and to develop more reliable assessment methodologies.
Approach
The study adopted a multi-faceted approach to evaluate LLM reasoning on SAT problems:
- Problem Instances: The evaluation included 2-SAT and 3-SAT problems. Additionally, two canonical reductions were used: Vertex Cover, derived from Conjunctive Normal Form (CNF) instances, and discrete 3D packing problems, derived from 3-SAT instances. This allowed for probing representation-invariant reasoning.
- Conventional Metrics: Initial model evaluations utilized standard metrics such as accuracy, precision, recall, and F1 score. These metrics were also applied within the SAT phase-transition setting.
- Limitations of Conventional Metrics: The research identified several issues with conventional metrics, including:
- Many models achieving high scores by over-predicting satisfiable formulas.
- Failure to reproduce the classical easy-hard-easy signature around the 3-SAT threshold.
- Sharp degradation of performance as the number of variables increased.
- Paired-Formula Protocol: To address the shortcomings of conventional metrics, a novel paired-formula protocol was introduced. This protocol relies on minimally different satisfiable and unsatisfiable instances.
- Accurate Differentiation Rate (ADR): As part of the paired-formula protocol, ADR was developed. This metric requires both members of each paired instance (one satisfiable, one unsatisfiable) to be classified correctly. ADR is designed to differentiate between reasoning-oriented models and heuristic-driven ones. The study found that ADR correlates with witness validity.
- Cross-Representation Consistency Test: The study tested consistency across different problem representations. This involved converting CNF instances to Vertex Cover problems and 3-SAT instances to discrete 3D packing problems. The agreement between model decisions on CNF and their corresponding graph or packing instances was measured.
Findings
- Conventional metrics, including accuracy, precision, recall, and F1, when applied to LLMs solving SAT problems, were found to be potentially misleading.
- Many LLM models achieved high scores on SAT problems by frequently over-predicting satisfiable formulas.
- LLMs often failed to reproduce the expected easy-hard-easy performance signature around the 3-SAT phase transition threshold, a characteristic observed in classical SAT solvers.
- Model performance, as assessed by conventional metrics, degraded sharply as the number of variables in the SAT instances increased.
- The introduction of the paired-formula protocol, combined with the Accurate Differentiation Rate (ADR), provided a more faithful and robust assessment of LLM reasoning capabilities.
- ADR successfully separated models that exhibited reasoning-oriented behavior from those relying on heuristic approaches.
- A correlation was observed between ADR and the validity of the witnesses generated by the models.
- On cross-representation consistency tests, most models demonstrated stable decision rules across representations, with agreement exceeding 80 percent of instances when converting CNF to Vertex Cover and 3-SAT to discrete 3D packing.
- Overall, SAT problems served as a conservative probe for evaluating LLM reasoning, indicating these problems are challenging tests for reasoning capacity.
- Paired evaluation using ADR offers a more representation-robust assessment method compared to conventional metrics for evaluating LLM reasoning.
Why This Matters
This research highlights that traditional metrics can misrepresent the actual reasoning capabilities of LLMs in complex logical tasks like Boolean satisfiability. By introducing a more rigorous evaluation method (paired-formula protocol with ADR), the study provides a clearer distinction between models that genuinely reason and those that rely on heuristics, which is crucial for developing LLMs capable of robust problem-solving across various representations.