🤖 machine learning

Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoning

This paper demonstrates that large language models' performance on constraint reasoning tasks is not determined by the underlying solver hardness of the problem instances, as evidenced by the lack of correlation between proof-hardness proxies and model accuracy or token expenditure across carefully controlled, density-matched benchmarks.

Original authors: Lucky Verma

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lucky Verma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a super-smart robot how to solve logic puzzles. In the world of computer science, there's a famous type of puzzle called "SAT" (Satisfiability), which is basically asking: "Can I fill in these blanks with 'True' or 'False' so that every single rule in this giant list is satisfied?" For decades, scientists have noticed something weird: when these puzzles get just the right amount of complicated—neither too easy nor impossibly hard—both humans and computers tend to hit a wall. It's like a traffic jam in the brain.

To understand why, researchers usually look at two things. First, there's density, which is just a fancy word for "how crowded the rules are." If you have a lot of rules packed into a small space, it feels harder. Second, there's structural hardness, which is about the hidden shape of the puzzle. Some puzzles look simple but have a twisted, knotted structure that makes them impossible to untangle quickly, while others look messy but have a straight, easy path through them. The big question is: when AI models fail, is it because the puzzle is too crowded (density), or because the puzzle's hidden shape is too tricky (structure)?

This paper is like a detective story where the author sets up a very specific trap to catch the AI in the act. The researcher, Lucky Verma, wanted to see if AI models actually understand the "twisted shape" of a logic puzzle, or if they are just guessing based on how "crowded" the rules look. To do this, they created two types of puzzles that look almost identical on the surface—they have the same number of rules and the same "crowdedness"—but are secretly very different underneath. One type is a "Ladder" puzzle, which is easy to solve because it has a simple, straight structure. The other is an "Expander" puzzle, which is a nightmare for traditional computers because its structure is so tangled that solving it requires exponential effort (think of it as trying to untangle a ball of yarn that keeps getting bigger the more you pull).

The experiment was a showdown between a classic computer solver (a tool called Glucose) and several large AI models (like Llama 3.3, Llama 4, and Mistral 3). First, they tested the classic solver. As expected, the solver struggled massively with the "Expander" puzzles, taking up to 51 times more effort (measured in "conflicts," or moments where the solver hits a dead end) to solve them compared to the "Ladder" puzzles. The solver clearly knew the difference between the easy shape and the hard shape.

Then came the AI models. If the AI was truly reasoning like a logic expert, it should have found the "Ladder" puzzles easier and the "Expander" puzzles harder, just like the classic solver. But here's the twist: the AI models didn't care about the shape at all. In fact, their performance was all over the place. For one model, the "Ladder" puzzles were easier; for another, the "Expander" puzzles were easier; and when you averaged them all out, the difference was practically zero (a tiny +1.7 point gap that wasn't statistically significant). The AI models seemed to be ignoring the hidden structure entirely.

Even stranger, the researchers checked how much "thinking time" (measured in tokens, or words generated) the AI spent on these puzzles. You might expect the AI to spend more time on the hard "Expander" puzzles. Instead, the AI often spent more time on the "Ladder" puzzles or got stuck on the easiest puzzles of all, wasting its budget without actually solving them. The paper also tested if the AI was just memorizing the look of the puzzle by shuffling the letters around (a "proof-preserving relabeling"). One model's performance crashed by nearly 93 points when the puzzle was just re-arranged, proving it was relying on surface tricks rather than real logic.

The bottom line is that for these specific puzzles, "Solver-Hard is Not Model-Hard." Just because a puzzle is mathematically difficult for a traditional computer doesn't mean it's difficult for an AI, and vice versa. The AI isn't failing because the puzzle is too hard; it's failing because it's not actually tracking the logical structure the way we hoped. It's as if the AI is looking at the puzzle and saying, "This looks crowded, so it must be hard," or "This looks like a pattern I've seen before," without ever actually doing the deep, structural work required to solve it. The study suggests that we can't assume AI models are getting better at reasoning just because they are getting bigger; sometimes, they are just getting better at guessing based on surface clues.

Technical Summary: Solver-Hard Is Not Model-Hard

Problem Statement
Current evaluations of Large Language Models (LLMs) on Boolean satisfiability (SAT) and constraint satisfaction problems often conflate two distinct properties: clause density (the ratio of clauses to variables, $\alpha = m/n$ ) and proof complexity (the structural difficulty of refuting an unsatisfiable instance). On uniformly random formulas, these properties co-vary near the satisfiability phase transition, making it impossible to determine whether model failures are driven by surface-level density cues or by the underlying algorithmic hardness of the instance. This confound obscures whether LLMs track instance-level search costs or merely reproduce qualitative failure curves associated with density thresholds.

Methodology
The authors propose a construct-validity diagnostic that decouples clause density from proof complexity using controlled dissociations. The experimental design relies on three main contrasts:

C1 (Headline Contrast): Comparing Tseitin formulas on two graph structures with near-matched clause density ( $\alpha \approx 2.67$ $α \approx 2.67$ ) and maximum clause width (3), but differing resolution hardness:
- Expander Graphs: 3-regular expanders requiring exponential resolution (proof-hard).
- Ladder Graphs: Graphs with treewidth two, admitting polynomial proofs (proof-easy).
C2 (Density Control): Comparing the low-density Expander Tseitin formulas against high-density ( $\alpha \approx 6$ ) random UNSAT formulas. The latter are structurally easy for Conflict-Driven Clause Learning (CDCL) solvers despite their high density.
C3 (Pigeonhole Anchor): Using Pigeonhole Principle (PHP) formulas as a second proof-hard anchor with no graph structure, contrasted against random UNSAT.

Solver Validation:
Before evaluating LLMs, the authors verified the dissociation using the Glucose CDCL solver (and five others). They measured the conflict count as a solver-specific proxy for refutation cost. The construction successfully separated solver costs: at matched sizes, the median conflict ratio between Expander and Ladder formulas grew monotonically, reaching up to 51× in the largest bins. High-density random UNSAT formulas remained the easiest for the solver, confirming that density and solver cost are decoupled in this construction.

LLM Evaluation Protocol:

Models: Evaluated Llama 3.3 70B, Llama 4 Maverick 17B, and Mistral Large 3 675B (all autoregressive transformers) at temperature zero. A fourth model (gpt-oss-120b) was excluded due to high abstention rates.
Task: Models were asked to output a binary SAT/UNSAT verdict for 243 instances per model (60 from each large family, 3 PHP anchors).
Metrics: Verdict accuracy (with abstentions scored as incorrect), accuracy gaps between proof-hard and proof-easy families, and the correlation between correctness and solver conflict counts.
Token Spend Analysis: A pre-registered extension analyzed whether provider-reported completion tokens (a proxy for test-time compute) tracked the solver-cost proxy, controlling for formula length and censoring.

Key Results

Failure of Transfer: The ordering of difficulty observed in classical solvers did not transfer to LLMs.
- Accuracy Gaps: The predicted accuracy gap (Ladder > Expander) was inconsistent. Llama 3.3 showed a +20 point gap (in the predicted direction), Llama 4 showed a -32 point gap (reversed), and Mistral 3 showed +17 points. The pooled gap was +1.7 points ( $p=0.74$ ), failing to meet the pre-specified threshold for a significant transfer effect.
- Correlation: There was no negative association between solver conflict counts and model correctness. Instead, the pooled correlation was weakly positive ( $r = +0.15$ ), indicating that higher solver costs did not predict lower model accuracy.
- Density vs. Hardness: Models performed worst on the high-density random UNSAT family (which was easiest for the solver), further demonstrating that neither clause density nor proof complexity consistently orders model errors.
Surface Sensitivity: A proof-preserving relabeling experiment (shuffling variables and clauses without changing logical structure) revealed model-specific surface sensitivity. For Llama 3.3, accuracy dropped by a mean of 93 points across all clusters after relabeling, whereas Llama 4 remained largely unaffected. This suggests models may rely on surface forms rather than logical structure.
Token Spend Dissociation: Observed completion token spend did not consistently increase with solver cost.
- At 16k token budgets, the reasoning model (Nemotron) spent more tokens on the proof-easy Ladder formulas than the proof-hard Expander formulas.
- The most severe token consumption (hitting the 16k cap) occurred on the solver-easiest family (random UNSAT), where accuracy was near zero.
- Length-controlled correlations between tokens and solver conflicts were generally negative or null, failing to show that models allocate more compute to structurally harder instances.

Significance and Claims
The paper concludes that "Solver-Hard Is Not Model-Hard" within the tested regime. The primary contribution is a scoped diagnostic showing that classical instance hardness (defined by proof complexity and validated by CDCL solvers) does not predict LLM verdict accuracy or token allocation when clause density is controlled.

Construct Validity: The study demonstrates that previous evaluations relying on random formulas near the phase transition may be measuring sensitivity to density cues rather than reasoning capability.
Limitations: The authors explicitly state these results do not constitute a universal theory of reasoning failure or an impossibility result for autoregressive architectures. The findings are limited to the specific scale (12–30 variables), the specific families of formulas used, and the tested models.
Implication: Claims that LLMs fail due to proof complexity must first demonstrate that the hardness ordering transfers under controlled dissociations. The current evidence suggests that for these models, neither clause density nor proof complexity is a reliable predictor of performance, and models may be highly sensitive to surface-level variations in formula serialization.

Technical Summary: Solver-Hard Is Not Model-Hard

More like this