Deterministic CDCL with VSIDS and restarts: polynomial-size refutations on bounded-treewidth CNFs

What is known. CDCL refutations are resolution proofs, so exponential resolution lower bounds apply to every CDCL solver. With nondeterministic decisions and restarts CDCL polynomially simulates general resolution (Pipatsrisawat and Darwiche, AIJ 2011), and with random decisions and many restarts it refutes formulas of bounded resolution width in polynomial time (Atserias, Fichte and Thurley, JAIR 2011); these idealisations do not cover deterministic VSIDS. Atserias and Müller (FOCS 2019; J. ACM 2020) proved that finding a refutation at most polynomially longer than the shortest is NP-hard (resolution is not automatable unless P = NP), so no proof-search heuristic is optimal on all inputs. Ben-Sasson and Wigderson showed that resolution proof size is governed by width.

Structure hypotheses. Industrial instances have high modularity and small treewidth-like parameters, and community structure correlates with solver speed. Mull, Fremont and Seshia (SAT 2016, arXiv:1602.08620) showed that formulas with high modularity can still be NP-hard and that a random community model with few communities and high modularity almost surely requires exponential resolution proofs, so community structure alone does not explain CDCL's success. Vinyals (AAAI 2020) constructed formulas with polynomial-size resolution refutations on which CDCL with VMTF, CHB and certain VSIDS and LRB implementations needs exponential time, so deterministic VSIDS-style CDCL does not simulate resolution; this is why the target above is restricted to a structural class. In the positive direction, Samar, Vinyals and Ganesh (arXiv:2603.16156, SAT 2026) give a deterministic CDCL configuration with a VSIDS variant that solves Ordering Principle formulas in polynomial time, exponentially separating it from DPLL, and Singh, Liew, Vinyals and Ganesh (arXiv:2603.26286, 2026, preprint) prove that a certain CDCL configuration refutes formulas with small "proofdoors" (chunk-wise interpolant decompositions) in polynomial time. An empirical study of 76,600 bounded-model-checking instances (Zhang et al., arXiv:2605.15506, 2026, preprint) finds that treewidth and community structure do not separate linearly from exponentially scaling families, so a bounded-treewidth theorem would explain only part of practice.

Practice. Kissat won the SAT Competition 2024. Solvers certify answers with DRAT proofs, and SAT-based results such as Boolean Pythagorean triples (about 200 terabytes of proof) and the empty hexagon number have been verified. No theorem explains why the same heuristics work across these families.

A proof would be the first guarantee that practical SAT solving is efficient on a natural structural class, and would indicate which heuristic components (activity decay, restart policy) are necessary. It would inform solver design only modestly; the main benefit is a theoretical foundation for a technology used in hardware verification, planning and mathematics.

A proof that a precisely specified deterministic CDCL model (VSIDS, restarts, phase saving) refutes every unsatisfiable CNF of treewidth $\le k$ using $\mathrm{poly}(n)2^{O(k)}$ conflicts, or an explicit family of bounded-treewidth CNFs on which that model needs superpolynomial-in- conflicts for . Either direction resolves the problem for the stated model.