Refutation Width as the Floor on Useful Reasoning Granularity

When a language model is asked to show that a set of constraints has no solution, it has to produce a chain of intermediate deductions. Work on chain-of-thought finds that such chains have a sweet spot. Steps that are too small pile up errors, and steps that are too large ask the model to make leaps it cannot make reliably. Proof complexity is the branch of theory that measures how long and how wide any formal proof must be. It says something sharper for random 3-SAT, the canonical hard constraint problem in which every constraint mentions only three variables. Because the constraints form an expander graph, where every small group of constraints touches many distinct variables, any refutation must at some point reason about a large fraction of the variables at once. The constraints are tiny, yet no proof can be cut into uniformly tiny pieces.

This note proposes treating that forced global step as the missing variable in the granularity tradeoff. We define the minimum refutation width $w^*(F)$ of an unsatisfiable formula $F$: the smallest $w$ such that some resolution proof of $F$ never writes down a derived clause with more than $w$ literals. Our claim is that $w^*(F)$ sets a hard lower limit on how finely a verified reasoning chain can be decomposed. The empirical optimum of the U-shaped error curve should therefore track $w^*$, and not only the model's local error profile. If this holds, it gives a computable, instance-level predictor of when step-by-step LLM reasoning on constraint problems will fall off a cliff. It also gives a principled rule for setting step size.

Core Claim

The two research directions supply the two halves of the argument.

How does Chain of Thought decompose complex tasks? models reasoning as a tree of classification steps. From that model it derives an optimal branching degree $m^* = e^{d/2}$, where $d$ is an intrinsic data dimension, and it observes U-shaped test error in chain length. Designing Algorithms Empowered by Language Models shows that pipelines built from LLM calls with nonzero false-positive rates degrade when split too finely. Both analyses assume a decomposition of any granularity is available, and they ask only which granularity minimizes error.

Proof complexity says that assumption fails on constraint problems with expander structure. Random Θ(log n)-CNFs Are Hard for Cutting Planes and Extended Formulation Lower Bounds for Refuting Random CSPs both trace hardness to expansion: no small subproblem can be isolated without pulling in many fresh variables. For constant clause size the open problems concern the strongest proof systems. For resolution-style step-by-step deduction, the regime closest to what an LLM writes, the consequence is already concrete: some derived clause must be wide.

We formalize the interaction with a deliberately simple model. Let $g$ be the step granularity, meaning the maximum width of any lemma the model may assert in one step. Let $\varepsilon(g)$ be the per-step error rate, measured by an external checker. Let $L(g)$ be the number of steps needed at that granularity. The probability that the model produces a valid refutation is then roughly

$$P_{\text{valid}}(g) \approx \mathbf{1}[g \ge w^*(F)] \,(1-\varepsilon(g))^{L(g)}.$$

The indicator term is the new ingredient. Without it, one predicts a smooth U-curve whose optimum depends only on the model. With it, the optimum is pushed to at least $w^*(F)$. If $\varepsilon(w^*)$ is already large, no granularity rescues the model, and this is the cliff. The model predicts that two formulas with identical size, clause size and density, but different $w^*$, will have different optimal granularities and different collapse points.

Relation to Prior Work

The closest empirical work motivates the study but does not test this claim. Have Large Language Models Learned to Reason? A Characterization via 3-SAT evaluates LLMs on random 3-SAT across the phase transition. It finds non-reasoning models fall to about 10% in the hard region, DeepSeek-R1 does much better through long backtracking traces, and solver translation reaches about 100%. It stays at $n \le 10$, never checks whether traces are valid proofs, and never varies granularity.

ZebraLogic uses search-space size and Z3 conflict count as difficulty indices and documents a "curse of complexity." Those indices describe one solver's run, not a property of the proof itself. Divide and Translate (CLOVER) shows that fine-grained translation into first-order logic beats monolithic translation. It hands reasoning to a black-box solver, so it says nothing about the granularity of the reasoning itself.

Ehrenfeucht-Haussler Rank and Chain of Thought supplies a precedent for what we want. It gives a function-level quantity, rank, that lower-bounds the number of chain-of-thought steps. That bound applies to idealized single-layer hard-attention models and explicit functions. We seek a width analogue for refutation that can be measured on real models. Finally, Easily refutable subformulas is a constraint on our design. It shows efficient refutation becomes possible only at density around $n^{3/2}$, by discarding most of the formula. We therefore expect no method to make linear-density instances easy, and we evaluate predictions of difficulty rather than claims of tractability.

Research Program

We will build a verified-refutation harness. A model receives an unsatisfiable CNF formula and must emit a sequence of lemmas, each a clause, ending in the empty clause. Each lemma must be accompanied by the set of earlier clauses it claims to follow from. A small SAT check verifies each step, testing whether the cited clauses together with the negated lemma are unsatisfiable. The granularity knob $g$ caps lemma width and the number of cited premises. At $g=2$ or $3$ the steps are close to single resolution steps. At large $g$ the model may assert big jumps that the checker still verifies locally.

The harness gives three things: exact per-step error $\varepsilon(g)$, step counts $L(g)$, and end-to-end valid-refutation rates. The checker catches spurious "contradictions," so it measures the false-positive accumulation described in Designing Algorithms Empowered by Language Models directly rather than by guesswork.

The key instance families hold clause size fixed and vary $w^*$.

The first family is random 3-CNF with $n$ from 10 to about 40, at densities 4.3, 6 and 10. Here $w^*$ grows with $n$ through expansion.

The second family is Tseitin parity formulas, which encode a parity constraint at each vertex of a graph. We build them on 3-regular graphs, giving clauses of size 3. We use two graph types at matched $n$: grid-like graphs, where width stays small, and random expanders, where width grows. This pairing is the cleanest ablation, because the formulas look locally identical.

The third family consists of 2-SAT and Horn-SAT controls with trivially small width.

We will compute $w^*$ exactly by running bounded-width resolution at increasing $w$. This takes time roughly polynomial in $n$ with exponent $w$, which is feasible at these sizes.

To probe the clause-size direction, we will vary $k \in \{3,4,5\}$ at matched unsatisfiability probability. Theory places the hardest open questions at constant $k$, so we can ask whether larger clauses with the same $w^*$ change $\varepsilon(g)$ independently of the width floor.

The transfer stage asks whether $w^*$ predicts failures on natural-language constraint benchmarks. We will ground ZebraLogic puzzles and AR-LSAT questions into CNF. For each wrong answer option, we compute the width of refuting "this option holds." We then regress the failure of existing models on $w^*$, Z3 conflict count, and search-space size.

Baselines

The naive reference point is direct prompting and free-form chain-of-thought with no granularity control, run on GPT-4o-class and Claude-class models. On random 3-SAT, the 3-SAT characterization reports these fall to about 10% accuracy in the hard region. We will rerun them on our instances and score them only on verified refutations, since a correct "UNSAT" label is not a proof.

The strongest reasoning competitor is DeepSeek-R1, run free-form with its own internal backtracking. We give it the same total token budget as our granularity-controlled runs and the same instances, and we pass its trace through the same lemma extractor and checker. On ZebraLogic the file reports 78.7% overall accuracy for DeepSeek-R1 and 81.0% for o1-full (ZebraLogic). The strongest decomposed neurosymbolic system is CLOVER at 75.4% on ZebraLogic and 62.8% on AR-LSAT (Divide and Translate). For verified-refutation rate on random 3-SAT, no reported result found on Lacuna, so our harness establishes the first numbers.

The key ablation compares fixed granularity, at a single $g$ tuned once on a development split, against width-matched granularity, where $g$ is set to $\max(w^*, \hat g)$ and $\hat g$ is the model's empirically best step size. Both receive the same tuning budget. Beating the free-form R1 baseline means a higher verified-refutation rate at equal tokens on instances with $w^*$ above the fixed-$g$ setting.

For the predictive claim, the baselines are Z3 conflict count and search-space size, the two indices ZebraLogic uses. Beating them means $w^*$ adds significant held-out explanatory power for model failure after controlling for both.

Why not just…?

Why not just hand the formula to a SAT solver? For deciding small CNF instances, a solver wins outright. SAT-Translate reaches about 100%, and we include it as a ceiling, not a competitor. The proposal does not aim to replace solvers. It asks when LLM step-by-step reasoning is trustworthy and how to set its step size. That question matters wherever no clean formal encoding exists, and AR-LSAT shows translation errors drag neurosymbolic accuracy to 30.9%. If the transfer stage shows $w^*$ adds nothing on natural-language benchmarks, this objection wins and the work reduces to a characterization of synthetic SAT.

Why not just let a reasoning model think longer? Longer free-form traces are the main reason R1 beats other models in the 3-SAT and ZebraLogic studies, so this is a real threat. Our model predicts that extra tokens help only while the width floor is reachable. Past that point, longer traces should contain invalid lemmas at the wide step. The Tseitin grid-versus-expander pairs settle this. If R1's verified success degrades with $w^*$ at matched $n$ and matched token budget, length alone is not the explanation. If it does not degrade, our claim is wrong.

Why not just sample many chains and vote? ZebraLogic reports that Best-of-N helps on medium puzzles but does not break the cliff on the hardest ones. Designing Algorithms Empowered by Language Models argues voting fails when step errors are correlated. We will run self-consistency at matched compute as an extra baseline. Our prediction is that it shifts curves upward without moving the collapse point in $w^*$.

Why not just use Z3 conflict count as the difficulty measure? Conflict count is cheap and already predicts failure in ZebraLogic. It may capture most of the same signal, since solver effort and proof width are related. The regression with both predictors decides this. If $w^*$ is redundant given conflict count, we will report that. The granularity prescription, setting $g$ from $w^*$, would then lose its main justification.

Decisive Checks

Three results would establish the claim, and their failure would refute it. First, on Tseitin formulas over grids versus expanders at matched $n$ and clause size 3, the empirically optimal $g$ should shift with $w^*$, and fixed-$g$ success should collapse once $w^*$ exceeds $g$. Second, on random 3-CNF, fitting $\varepsilon(g)$ from per-step checker data and plugging it into the model above should predict the location of the end-to-end accuracy cliff in held-out $(n,\Delta)$ cells better than a width-free U-curve fit. Third, on ZebraLogic and AR-LSAT, $w^*$ should explain failures of R1, o1-class models and CLOVER beyond Z3 conflict count and search-space size.

A positive result would give the granularity literature an instance-level quantity from proof complexity, playing the role that intrinsic dimension $d$ plays in the CoT scaling analysis. A negative result would also be useful. It would show that LLM failure on these problems is governed by something other than the structure of the required proof.