CS Paper Radar

Extending SMT Solving with Non-Ground Clause Learning

Yasmine Briefs, Christoph Weidenbach

cs.AI cs.LO ·submitted 2026-09-10 13:17 UTC · v1
theory

Abstract

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.

Comment
Extended version of LPAR 2026 paper

Closest papers

Nearest neighbours by meaning across the whole index.

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.68
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

A Non-CDCL SAT Solver with Early Conflict Detection: The Watched-Literal-Based CSFLOC Solver

cs.LO ·2026-08-25 ·Gábor Kusper
published similarity 0.67
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

CSFLOC is a non-CDCL SAT decision procedure based on counting subsumed full-length ordered clauses. The classical CSFLOC loop traverses the ordered space of full-length clauses by a monotone counter: if the current full-length clause is not subsumed by the input formula, its negation is a satisfying assignment; otherwise, a subsuming clause determines a counter jump. The main bottleneck is the repeated search for such a subsuming clause. This paper presents CSFLOC-WL, and its current implementation CSFLOC-WL3, in which this search is replaced by watched-literal prefix propagation over the negation of the current full-length clause represented by the counter. The central mechanism is early conflict detection: if propagation under a common prefix derives opposite unit consequences for the same variable, then the two reason clauses are resolved immediately and the resolvent is used as a new counter-jump cause. The resulting solver is not a CDCL solver: it has no CDCL decision tree, no restart policy, and no first-UIP backjumping loop. It remains a counter-guided full-length-clause-counting solver, but it imports the watched-literal data structure and reason clauses as engineering tools for discovering jumps. Experiments on selected UNSAT SATLIB instances compare CSFLOC-WL3 with CSFLOC21TU and CaDiCaL 3.0.0. The results are mixed: CSFLOC-WL3 is strong on several random 3-SAT instances near the random-3-SAT satisfiability threshold, whereas CSFLOC21TU remains faster on several structured cases, apparently because it contains a more mature cache mechanism that is not yet present in CSFLOC-WL3.

0.37

On Structure-Aware SAT Solving

cs.LO ·2026-11-13 ·Eugene Goldberg
hot direction similarity 0.66
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.

0.44

ProofGap: Benchmarking Step-Level Formal Reasoning with Local Obligations Derived from Natural-Language Solutions

cs.PL ·2026-09-24 ·Lihan Xie, Zhicheng Hui, Yingjun Lan, Zhehao Li, Xingzhi Qi +5 more
benchmarktheory similarity 0.66
Abstract

Existing formal mathematics benchmarks, such as miniF2F, ProofNet, and PutnamBench, primarily evaluate models on constructing complete formal proofs for challenging problems. Because success is measured at the theorem level, these benchmarks offer limited insight into models' step-level formal reasoning. Evaluating this capability separately enables finer-grained diagnosis of model limitations than theorem-level evaluation alone. To fill this evaluation gap, we introduce ProofGap, a fine-grained benchmark for step-level formal reasoning. ProofGap is constructed through a natural-language proof-processing pipeline that decomposes each reasoning step into one or more aligned proof gaps. Applying this pipeline to natural-language solutions to 3,015 exercises in B. P. Demidovich's Problems in Mathematical Analysis yields 26,116 gaps. The benchmark focuses on mathematical analysis, a domain that remains challenging for current models. By supplying the local context and target explicitly, gap completion isolates local formal proof construction from end-to-end proof composition, enabling more precise localization of model failures. Natural-language solutions serve as the provenance of these obligations, while the benchmark task itself starts from an already formalized local context and goal. Beyond benchmarking, the same pipeline may support future proof-verification systems, provided that semantic translation and sequential proof composition are handled reliably.

0.13

Active Learning of Temporal Specifications through Distinguishing Queries

cs.LO cs.AI ·2026-11-13 ·Rajarshi Roy, Xiaowei Huang
theory similarity 0.65
Abstract

Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.

0.21

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

LLM-Assisted Bi-Approximate CHC Solving

cs.LO cs.AI ·2026-10-16 ·Baiting Jiang
similarity 0.64
Abstract · 22 pages, 8 figures, 5 tables

Constrained Horn clause (CHC) solvers often struggle to discover deep counterexamples whose derivations may require extensive rule unfolding. Although large language models (LLMs) can propose long-range symbolic relations, prior work on formally checked LLM-assisted verification has mainly focused on generating inductive invariants and concrete traces. We exploit this broader capability through Derivation Power Under-approximations (DPUs). Each DPU is a solver-certified under-approximation of the relation induced by a multi-step CHC derivation. An LLM proposes each DPU with symbolic intermediate-state witnesses that enable SMT validation without introducing additional quantifiers. Validated DPUs can be composed and reused soundly. Building on this mechanism, our LLM-assisted framework HornCraft combines invariant generation for over-approximation with DPU generation for under-approximation in CHC solving. On 260 linear and nonlinear integer-arithmetic CHC-COMP benchmarks left unresolved by a 30-minute Spacer run, HornCraft returns certified verdicts for 228 instances. It certifies 42 instances as unsafe, compared with 22 when DPU construction and reuse are disabled.

0.23

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.64
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.30