CS Paper Radar

Structure-Preserving Uncertainty Propagation in First-Order Proof Search

Tanel Tammet

cs.AI cs.LO ·submitted 2026-08-10 07:00 UTC · v1
code/data

Abstract

GK is a query-directed first-order prover that extends ordinary resolution-based proof search with explicit positive and negative claims, numerical confidence values, and prioritized default rules with exceptions. It works directly with non-ground clauses, including equality and function terms. Candidate proofs are found by bounded first-order proof search; exception conditions of defaults are checked by further bounded searches, recursively when exceptions themselves depend on defaults. This avoids requiring a finite global grounding, while allowing incomplete searches to be reported as such. This paper adds structure-preserving quantitative reporting to that framework. Retained proof histories are used in two calculations. The first reconstructs the uncertain ground premises used by each proof and computes the probability that at least one retained proof is available, without counting shared premises independently. The second resolves positive and negative support at intermediate atoms before that support is propagated through later rules; the same calculation evaluates uncertain exception conditions for individual rule applications. Reports separate positive support, negative support, conflict, and ignorance and identify detected incomplete calculations or fallbacks. The implementation performs bounded reconstruction and dependency traversal after proof search and still requires no global grounding. Analytic examples and independent simulators reproduce the reference calculations on their stated fragments. Comparisons with probabilistic logic, probabilistic ASP, default logic, and goal-directed ASP identify cases of agreement, semantic difference, unsupported translation, and incomplete computation.

Comment
79 pages, 6 figures. Executable binaries, documentation, examples, and public samplers: https://github.com/tammet/gkreasoner

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

Minimum-Cost Robust Evidence Certificates for Horn Reasoning under Correlated Source Failures

cs.AI ·2026-10-19 ·Yukun Yang
theory similarity 0.61
Abstract · 9 pages, 2 figures

A small justification for a rule-based conclusion may disappear when a source is withdrawn, and multiple derivations need not provide independent evidence. We study minimum-cost certificates that preserve a Horn conclusion under every withdrawal of at most k source domains. Evidence records remain distinct from asserted facts, supporting replicated attestations and overlapping failure dependencies. Transversals of minimal-support footprints characterize robustness and explain why disjoint-proof requirements can reject valid certificates. An exact procedure alternates weighted evidence selection with a source-failure oracle. A rule-closed counterinterpretation yields a globally valid selection cut without enumerating supports or failure scenarios. We prove correctness, finite termination, and cost optimality, establish coNP-completeness of unrestricted verification and NP-completeness of synthesis for every fixed budget, and identify a tractable reachability restriction. Experiments on controlled benchmarks, reachability graphs, and ontology-derived instances demonstrate that our counterinterpretation-guided synthesis achieves up to 92% optimum coverage within practical resource bounds, outperforming scenario expansion and general abduction while confirming the necessity of transversal-based reasoning over proof-packing heuristics.

0.22

Reward-Oracle MCTS for Formal Theorem Proving: Sample-Efficient Search and the Need for Kernel-Level Proof Auditing

cs.AI cs.LGcs.LO ·2026-08-11 ·Bodla Krishna Vamshi, Haizhao Yang
theory similarity 0.60
Abstract

Formal theorem proving with large language models remains challenging due to the difficulty of navigating large proof search spaces efficiently. Existing tree search approaches either feed verbose compiler error messages directly into the generation context, increasing context usage during search, or employ non-standard evaluation protocols that prevent direct comparison with established baselines. We propose a three-role Monte Carlo Tree Search (MCTS) framework that treats the Lean 4 compiler purely as a reward oracle using compiler output as a scalar signal for UCB-guided tree updates without feeding error content into the generation context. Our framework decomposes proof search into three roles: a generator for proof attempts, a decomposer for subgoal decomposition, and a critic for subgoal quality evaluation. We evaluate across 4 benchmarks spanning competition mathematics and physics (MiniF2F, PutnamBench, LeanPhysBench, PhysLeandata) with three prover models at standard proof attempt budgets (PAB@16 to PAB@256). Our method achieves 87.1\% on MiniF2F with Goedel-Prover-V2-8B at PAB@256 and solves 26/659 PutnamBench problems at PAB@32 surpassing base sampling 18/659 at same proof attempt budget. Through an exhaustive axiom-level audit of every compiled proof, we further identify reward hacking in search-based theorem proving: DeepSeek-Prover-V2-7B produces proofs on PutnamBench that pass compilation and the standard sorry-token scan while depending on sorryAx. The audit removes 4 and 8 such proofs from whole-proof sampling at PAB@32 and PAB@128, and 11 and 19 from MCTS. We do not attribute these counts to the search procedure; we report them to establish that kernel-level auditing is necessary for compiler-verified evaluation.

0.38

CompProv Produces Machine Readable Graphs Encoding Microscopic Algebraic Provenance for Reproducible Computation

cs.SE cs.CE ·2026-10-01 ·Minas Abramyan, Mohammed Alaa Ala'anzy, Nasir Saeed
similarity 0.60
Abstract

The reliability of computational results in scientific research and financial modeling increasingly depends on verifiable traceability, not merely on trust in a reported output. Existing provenance systems operate at the granularity of files, datasets, or pipeline stages, leaving the internal sequence of algebraic transformations connecting an algorithm's inputs to its outputs unrecorded; a rounding error, an undocumented substitution, or a missing intermediate value can propagate to a final result with no recoverable trace. This work presents CompProv, a Java-based, audit-oriented provenance framework that captures lineage at the atomic level of individual algebraic operations by encapsulating numerical values in high-precision wrapper objects, producing a serializable Calculation Provenance Graph (CPG) that persists as a self-contained artifact rather than a discarded byproduct. The framework is evaluated through three heterogeneous case studies: a decentralized-finance NAV calculation, a reconstruction of an interferometric gauge-block calibration in metrology under explicitly documented input assumptions, and a hydrological model performance evaluation. Deterministic replay reproduced each result exactly in a fresh environment, and CPG-based input substitution supported sensitivity analysis without exposing the underlying source code. These results indicate that, provided the CompProv runtime and wrapper classes are available in the replay environment, a CPG allows numerical integrity to be audited without disclosing proprietary business logic, and that its self-contained structure supports temporal auditability once an execution environment has become deprecated. This framework establishes an operation-level foundation for auditable-by-design computational systems, with scaling to high-throughput computing identified as a direction for future work.

0.27

Incrementally Verifiable Oracle Aided Computation

cs.CR ·2026-11-10 ·Shafi Goldwasser, Yael Kalai
theory similarity 0.60
Abstract

Incrementally verifiable computation (IVC) allows a prover to maintain a short proof that can be efficiently updated after each computation step, without retaining or recomputing the preceding execution. Standard IVC schemes do not directly address a crucial feature of AI tasks: their dependence on external information and expertise. We construct IVC schemes for oracle-aided computations under the LWE assumption by first constructing SNARGs, and then extending them to IVC. We consider the following two settings, where below, k is the security parameter, n is the input length, and T, S, and Q are the time, space, and oracle-query bounds. 1. Robust computations: For bounded-space computations, including non-deterministic computations, in which every accepting purported execution on a false input contains at least an eps-fraction of incorrect oracle answers, we construct privately verifiable SNARGs and IVC. Public parameters, private verification keys, and proofs have length poly(k ,S, log T,1/eps), and verification uses O(k/eps) oracle calls. We complement this result with a lower bound ruling out (deterministic) publicly verifiable SNARGs and IVCs with public parameters of length o(n), and o(Q) verifier oracle queries. 2. Signed oracles: For oracles that digitally sign their query-answer pairs, we construct publicly verifiable SNARGs and IVC without a robustness assumption, and with oracle-free setup and verification. Public parameters and proofs have length poly(k,S,log T). For deterministic computations with oracle query and answer lengths poly(k,log T), we remove the dependence on S, obtaining public parameter and proof lengths poly(k,log T). All our constructions have adaptive completeness and soundness.

0.28

A Multi-Prover Interactive Protocol for Certification of Resolution Refutations

cs.LO ·2026-11-10 ·Philipp Czerner, Adrian Krauss, Josia Pietsch, Javier Esparza
similarity 0.60
Abstract · 33 pages, 7 figures, extended version to CSL 2027 version

A resolution refutation of a SAT-formula $\varphi$ is an independently checkable certificate proving that $\varphi$ is unsatisfiable. However, the refutations of $\varphi$ can be exponentially larger than $\varphi$. So, a verifier needs worst-case exponential time in the size of $\varphi$ to check their correctness. We present ResCertify, an interactive probabilistic protocol in which the verifier interacts with multiple independent, untrusted provers (MIP) to check the refutation with very low probability of error. The verifier runs in linear time in the size of $\varphi$. The provers require time $\mathcal{O}(n \cdot |Φ|)$, where $Φ$ is the resolution refutation and $n$ is the number of variables of $\varphi$. If they can be trusted to act as a multilinear oracle on certain queries, a single prover suffices, and the runtime can be improved to $\mathcal{O}(|Φ|)$. Finally, while the focus of our work is theoretical, we also report on a proof-of-concept implementation of ResCertify.

0.40

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

Contract-Aware Rescue of a Drifted Isabelle Development: The Double-Tank Case Study

cs.SE ·2026-08-19 ·Jim Woodcock, Gabriel Leite, Augusto Sampaio, Ran Wei
theory similarity 0.59
Abstract · 15 pages. Submitted to Formal Methods for Autonomous Systems 2026 (FMAS 2026). Reproducibility artefact: DOI 10.5281/zenodo.21981425

Large language models can propose proofs for interactive theorem provers, but a successful build does not show the surrounding verification task was preserved. We study this problem in an Isabelle development of a sampled-data double-tank controller. The work began with nine theories and ten unfinished obligations, grew to a 16-theory build without sorry, oops, added axiomatisation, or oracle use, and accumulated 23 stable and 36 broken proof states. A retrospective audit found material changes in 16 of the 100 original declarations, including a weakened end-to-end assurance theorem that assumed three of the four requirements in its conclusion. We used CAPRI, a contract-aware proof-repair tool, to govern a reconstruction by combining Isabelle acceptance with an independent check of repository changes against machine-readable edit contracts. The reconstruction discharged all ten scoped obligations within the original nine-theory structure. A secondary replay by a co-author reproduced the R10 build, contract checks, control tests, and principal audit findings; independent replication remains future work. Operational end-to-end verification remains incomplete: we still need to connect operational executions to the reconstructed quantitative trace contract, a task requiring an extended contract.

0.23