Andrii Bidochko

• Updated: June 15, 2026
• 7 min read

Satisfiability Solving with LLMs: A Matched-Pair Evaluation of Reasoning Capability

Direct Answer

The paper introduces a paired‑formula evaluation protocol for measuring large language models’ (LLMs) true reasoning ability on Boolean satisfiability (SAT) problems, and it shows that conventional accuracy metrics can be misleading. By requiring models to correctly differentiate minimally altered satisfiable and unsatisfiable instances, the authors provide a more faithful benchmark that also holds across different problem representations.

Background: Why This Problem Is Hard

Boolean satisfiability (SAT) sits at the core of many AI tasks—constraint solving, verification, planning, and even prompting strategies that implicitly encode logical constraints. Despite the rapid adoption of LLMs for “reasoning‑heavy” applications, there is no consensus on whether these models genuinely understand the underlying combinatorial structure or merely exploit statistical shortcuts.

Traditional evaluation of LLMs on SAT has relied on aggregate metrics such as accuracy, precision, and recall. These numbers, however, mask two critical issues:

• Class‑imbalance bias: Models can inflate scores by over‑predicting the “satisfiable” class, which is often easier to guess.
• Lack of phase‑transition testing: The classic easy‑hard‑easy pattern around the 3‑SAT clause‑to‑variable ratio is a litmus test for genuine reasoning. Most LLM benchmarks ignore this, missing a key diagnostic signal.

Consequently, practitioners lack a reliable yardstick to decide whether an LLM can be trusted for downstream systems that depend on sound logical inference.

What the Researchers Propose

The authors present a two‑pronged framework:

1. Matched‑Pair Formula Protocol: For each SAT instance, they generate a twin—identical except for a single clause flip that toggles satisfiability. The pair is minimal, ensuring that any correct model must detect the subtle logical change.
2. Accurate Differentiation Rate (ADR): ADR measures the proportion of pairs where the model classifies both formulas correctly. Unlike raw accuracy, ADR penalizes models that succeed by chance or by systematic bias.

Beyond CNF SAT, the study also translates formulas into two canonical NP‑complete problems—Vertex Cover (graph representation) and 3‑D discrete packing (geometric representation)—to test whether a model’s decision rule is invariant to representation.

How It Works in Practice

The workflow can be broken down into four conceptual stages:

1. Instance Generation

Random 2‑SAT and 3‑SAT formulas are sampled across a range of clause‑to‑variable ratios, including the critical region around the 3‑SAT phase transition. For each formula, a minimally altered counterpart is produced by toggling a single clause, guaranteeing opposite satisfiability.

2. Cross‑Representation Mapping

Each CNF pair is algorithmically reduced to an equivalent Vertex Cover instance (graph edges ↔ clauses) and to a discrete 3‑D packing problem (boxes ↔ literals). This step ensures that the logical core remains unchanged while the surface representation varies.

3. Model Querying

LLMs—ranging from instruction‑tuned variants to chain‑of‑thought enabled prompts—receive the textual encoding of each instance. The model outputs a binary decision (“SAT” or “UNSAT”). No external solver is consulted; the judgment is purely model‑inferred.

4. Scoring with ADR

For every matched pair, the system checks whether the model’s two predictions are opposite and correct. ADR is the ratio of such successful pairs to the total number of pairs. A high ADR indicates that the model truly distinguishes the logical boundary rather than relying on heuristics.

What sets this approach apart is its focus on *relative* correctness within a tightly controlled logical neighborhood, rather than absolute correctness on a heterogeneous test set.

Evaluation & Results

The authors evaluated several state‑of‑the‑art LLMs, including instruction‑tuned GPT‑4‑style models and open‑source alternatives. The experiments covered three dimensions:

• Conventional metrics: Accuracy, precision, recall, and F1 across the full dataset.
• Phase‑transition behavior: Performance as the clause‑to‑variable ratio sweeps through the critical 3‑SAT threshold.
• Cross‑representation consistency: Agreement between decisions on CNF, Vertex Cover, and packing instances.

Key observations:

1. Inflated conventional scores: Many models reported >80% accuracy by predominantly labeling formulas as satisfiable, yet their ADR hovered around 45%, revealing a substantial gap between apparent and actual reasoning.
2. Missing easy‑hard‑easy signature: Unlike classical SAT solvers, LLMs did not exhibit a performance dip near the phase transition; instead, their accuracy remained relatively flat, suggesting reliance on surface patterns rather than combinatorial difficulty.
3. Sharp degradation with scale: As the number of variables grew beyond 30, ADR declined sharply for all models, indicating limited scalability of emergent reasoning.
4. High cross‑representation agreement: For the majority of models, decisions on CNF and the corresponding graph or packing versions matched in >80% of cases, implying that the learned decision rule is somewhat representation‑agnostic.
5. ADR correlates with witness validity: When a model’s “SAT” prediction was accompanied by a concrete variable assignment (a witness), higher ADR scores aligned with higher witness correctness, reinforcing ADR as a proxy for genuine logical insight.

Collectively, these results demonstrate that ADR provides a stricter, more informative lens on LLM reasoning than traditional metrics, and that SAT remains a conservative yet powerful probe for evaluating logical competence.

Why This Matters for AI Systems and Agents

For practitioners building AI agents that must reason about constraints—whether in automated planning, verification pipelines, or dynamic policy enforcement—the findings carry several practical takeaways:

• Benchmark selection matters: Relying solely on aggregate accuracy can give a false sense of security. Incorporating ADR‑style paired evaluations can surface hidden weaknesses before deployment.
• Model choice influences safety: Agents that need to guarantee unsatisfiability (e.g., “no conflict” checks) should be vetted with matched‑pair tests to avoid systematic over‑prediction of satisfiable outcomes.
• Cross‑representation robustness: The observed consistency across CNF, graph, and packing encodings suggests that a well‑trained LLM can maintain its decision logic even when the problem is presented in a different domain language. This property is valuable for UBOS platform overview where heterogeneous data sources are unified under a single reasoning engine.
• Integration pathways: Teams can embed ADR‑based validation into their Workflow automation studio pipelines, automatically flagging instances where the model’s confidence falls below a threshold.
• Strategic product positioning: Companies offering “intelligent” constraint solvers—such as AI marketing agents that schedule campaigns under budget and timing constraints—can differentiate by advertising ADR‑validated reasoning capabilities.

What Comes Next

While the paired‑formula protocol marks a significant step forward, several open challenges remain:

• Scaling to larger instances: Current ADR scores deteriorate beyond 30 variables. Future work should explore curriculum learning or hybrid neuro‑symbolic architectures that combine LLMs with traditional SAT solvers.
• Extending to richer logics: SAT is a Boolean fragment; real‑world constraints often involve arithmetic, temporal, or probabilistic elements. Adapting the matched‑pair methodology to SMT (Satisfiability Modulo Theories) could broaden its applicability.
• Automated witness generation: Integrating mechanisms that compel LLMs to produce explicit satisfying assignments would tighten the link between ADR and actionable outputs.
• Human‑in‑the‑loop evaluation: Incorporating expert feedback on ambiguous pairs could refine the protocol and help calibrate model confidence.
• Productization pathways: Embedding ADR checks into the Enterprise AI platform by UBOS could provide enterprises with a built‑in safety net for logic‑driven agents.

By addressing these gaps, the community can move toward LLMs that not only appear to reason but demonstrably solve combinatorial problems with provable guarantees.

References

• Zhang, L., Chen, S., & Chen, S. (2026). Satisfiability Solving with LLMs: A Matched-Pair Evaluation of Reasoning Capability. arXiv preprint.
• Cook, S. (1971). The complexity of theorem-proving procedures. Proceedings of the third annual ACM symposium on Theory of computing.
• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

Andrii Bidochko

CTO UBOS

Andrii Bidochko is an AI entrepreneur and researcher focused on AI agents, reinforcement learning, and autonomous systems. He writes about the technologies shaping the future of machine intelligence, from frontier models and agent architectures to real-world AI applications.