CS Paper Radar

On Structure-Aware SAT Solving

Eugene Goldberg

cs.LO ·submitted 2026-11-13 10:43 UTC · v1
hot direction

Abstract

Although modern SAT solvers have made remarkable progress, they still exploit formula structure only to a limited extent. We present two techniques that make SAT solving more structure-aware and provide experimental results showing their promise. The first technique ``$\mathit{melts}$'' the formula by reducing interaction between its parts. This is achieved by adding new variables, using existential quantifiers, and applying a procedure called partial quantifier elimination. The second technique exploits the notion of a $\mathit{local}$ $\mathit{proof}$. The latter establishes that a formula is unsatisfiable by proving that certain literals of its clauses are redundant. We show that using local proofs makes SAT solving more formula-specific.

Closest papers

Nearest neighbours by meaning across the whole index.

Extending SMT Solving with Non-Ground Clause Learning

cs.AI cs.LO ·2026-09-10 ·Yasmine Briefs, Christoph Weidenbach
theory similarity 0.66
Abstract · Extended version of LPAR 2026 paper

Quantifier instantiation is currently the main approach to non-ground SMT solving: solvers generate ground instances and solve the resulting ground SMT problems with CDCL(T)-style reasoning. When a conflict is found, conflict analysis learns only a ground clause, even though the conflict comes from instances of non-ground clauses. Yet non-ground reasoning can give exponentially shorter proofs than purely ground reasoning. We propose a calculus that consists of ground instantiations, CDCL(T)-style rules, and non-ground conflict analysis. The solver reasons on ground instances, but the resolution steps of conflict analysis are performed on their original non-ground clauses. This produces learned clauses that are typically more general than the ground conflict. With a suitable strategy, the learned clauses are even non-redundant. We also show how chronological backtracking can be included in SMT solving. Our calculus gives a common setting for CDCL(T)-style SMT solving, a range of instantiation-based procedures, and non-ground clause learning, and we prove that it simulates CDCL, SCL(FOL), SCL(T), and even Resolution.

0.14

Verifiable LLM-Guided Focal SMT Solving for Quantified Arrays

cs.AI ·2026-10-29 ·Kunhang Lv, Rui Han, Fuqi Jia, Yuhang Dong, Feifei Ma +1 more
similarity 0.66
Abstract

Large language models can often identify useful semantic structure in formal artifacts, but their outputs cannot be trusted as proofs or solver decisions. We study whether LLMs can instead guide formal reasoning systems through a narrow, solver-verifiable interface. We instantiate this idea in quantified array SMT solving, where modern instantiation-based techniques can fail when key ground terms and equalities are hidden by auxiliary variables, axiom guards, and nested array terms. We observe that many instances are largely driven by a small set of focal ground terms or constraints, similar to the backdoor sets in SAT solving. Building on this, we present LinguaArray, a framework where an LLM proposes a small Semantic Focus Set (ground terms/constraints), while a conventional SMT solver remains the sole proof engine and certifies all results. LinguaArray uses these LLM-suggested, solver-validated finite sets to significantly enhance solver capability, solving additional satisfiable and unsatisfiable instances that the backend alone fails to solve. It interacts within a finite time and then falls back to the backend solver to mitigate potential regressions. Evaluation on 1015 SMT-LIB instances across five logics under 1200s timeout (including LLM latency) shows that LinguaArray solves up to 69.1% of instances and increases solved-instance counts by 105%--397% over the corresponding backends.

0.22

Apply All, Prove Once: Embedding Parameterized Lemmas in DRAT

cs.LO ·2026-11-17 ·Randal E. Bryant, Zachary Battleman, Marijn J. H. Heule
similarity 0.65
Abstract

The deletion-resolution-asymmetric-tautology (DRAT) proof format is widely used to express unsatisfiability proofs of Boolean formulas. Our DRATL format extends DRAT with parameterized lemmas, allowing a single proof to succinctly capture the common case where multiple instances of a pattern occur in a formula, differing in the identities and phases of the variables. Proofs expressed in DRATL can be hierarchical, with the proof of one lemma containing instantiations of others. Our elaborator program expands a DRATL proof containing multiple, nested lemmas into a standard DRAT proof. Most significantly, the elaboration yields compact proofs, where a single sequencing of the proof steps for each lemma covers all of its instantiations. Several case studies demonstrate that lemmas can provide a powerful method to generate short proofs for challenging problems.

0.35

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.65
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.64
Abstract

Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

0.22

Automated Theorem Generation in First-Order Logic by Construction from Triangular Standard Contradictions

cs.AI ·2026-10-30 ·Yang Xu, Shuwei Chen, Hailin Guo, Jun Liu
theory similarity 0.64
Abstract · 46 pages, 11 figures

Automated theorem generation (ATG) seeks to construct new theorems rather than merely prove given conjectures. Existing approaches typically generate candidate statements that require subsequent proof or formal verification. We propose a constructive framework for ATG in first-order logic based on triangular standard contradictions. The method constructs minimally unsatisfiable clause sets from selected first-order literals, then forms theorems by retaining some clauses as premises and taking the negation of one clause, or a conjunction of clauses, as the conclusion. Minimal unsatisfiability ensures that the remaining premises are satisfiable, avoiding trivial inference by explosion, while unsatisfiability of the full set guarantees the resulting entailment. Theorems are therefore correct by construction, without a separate proof procedure for each instance. Extending the previously developed $Δ_1$ generator, we introduce seven methods, $Δ_2$--$Δ_8$, forming a unified family of eight theorem-generation methods. Four generators, $Δ_1$--$Δ_4$, have been implemented and released. We also formulate a general $Δ$-class method encompassing the family. Combinatorial analysis demonstrates the capacity to generate large numbers of distinct theorems systematically. This framework offers a principled foundation for automated theorem discovery and the construction of logically guaranteed knowledge.

0.28

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity

cs.DS cs.CC ·2026-10-13 ·Jan Dreier, Robert Ganian, Marlene Gründel, Roohani Sharma, Simon Wietheger
similarity 0.63
Abstract

The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search and reasoning tasks. While $\mathrm{NP}$-complete in general, SAT is well known to be linear-time solvable on instances with bounded treewidth. This motivates the search for "hidden" tree-like structures in formulas---for instance by detecting so-called weak $t$-treewidth backdoors. Such backdoors are sets of $k$ variables that can be assigned in such a way that the remaining instance has treewidth at most $t$ and is satisfiable whenever the original instance is. Ever since Gaspers and Szeider [ICALP 2012] showed that finding a weak $t$-treewidth backdoor for a SAT formula is $\mathrm{W}[2]$-hard with respect to $k$, tractability results have been restricted to structurally sparse formulas---most notably, a linear-time algorithm for $d$-SAT (bounded clause-length SAT) by Fomin, Lokshtanov, Misra, Ramanujan, and Saurabh [SODA 2015] and a non-uniform polynomial-time algorithm when the incidence graph of the input formula belongs to a nowhere-dense graph class (or more generally is $K_{d,d}$-free) by Lokshtanov, Panolan, and Ramanujan [ICALP 2022]. In this paper, we push the tractability boundaries of finding weak $t$-treewidth backdoors beyond sparsity and into the regime of "well-behaved" dense formulas. Aiming towards relaxing structural input restrictions from nowhere-dense to edge-stable graph classes, as featured in the theory of beyond sparsity for FO model checking, or to bounded VC-dimension set systems, we identify signed semi-ladder-freeness as the correct dense structural restriction that establishes the boundary between tractability and intractability along this line.

0.48

Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving

cs.LO ·2026-09-28 ·Gábor Kusper
publishedtheory similarity 0.63
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

A resolvable network is a directed-graph representation of SAT: every SAT instance can be translated into an RN, and every RN has an associated CNF formula. Each reach represents one clause. In a mixed reach, the head and tail are disjoint sets of variables containing the variables occurring negatively and positively in the clause, respectively; the distinguished symbols Source and Sink represent a missing negative- or positive-literal side. RN-Solver is a proof-of-concept SAT solver based on this representation. Its all-positive clauses are represented by white reaches, and its token distributions are the inclusion-minimal hitting sets of the current white tails, generated by monotone CNF-DNF dualization. RN-Solver learns new white reaches by private-pivot resolution, a structured resolution sequence that uses old white reaches as pivot witnesses. In the original algorithm, every candidate white reach generated by such a chain was followed by a global subsumption test against the current network. Profiling showed that this subsumption test can dominate the runtime on random 3-SAT instances. We show that this check is unnecessary when the mixed reach used for learning is falsified by the current token distribution, meaning that the distribution makes all variables in the head true and all variables in the tail false. The key invariant is simple: the resulting white tail is disjoint from the triggering token distribution, while the same distribution intersects every old white tail. Hence no old white reach can subsume the generated reach. This structural observation allows us to construct a simpler, snapshot-based, subsumption-free variant of RN-Solver, where each main-loop iteration uses a fixed set of old reaches and installs newly generated white reaches only at the end of the iteration. We prove soundness of the revised algorithm. Empirical evaluation confirms the elimination of the targeted checks: within an 8 second budget, snapshot/full-DNF solves 963 of 1,000 uf20-91 instances, compared with 724 for the original control flow. A separate 100-instance comparison identifies exact incremental DNF as the most effective of the three tested configurations.

0.36