CS Paper Radar

IsaGraphLib: Formally Verified Efficient Graph Algorithms in Isabelle/HOL

Mohammad Abdulaziz, Thomas Ammer, Adem Rimpapa, Peter Lammich

cs.DS cs.MS ·submitted 2026-11-15 14:33 UTC · v1

Abstract

We present a library of formally verified graph algorithms in Isabelle/HOL. The library covers the main problems of combinatorial optimisation on graphs: reachability, shortest paths, minimum spanning trees, matching, maximum flow, and minimum-cost flow. The algorithms in the library use most of the standard algorithm design techniques: graph search, greedy algorithms on matroids, dynamic programming, augmenting paths, blossom contraction, blocking flows, push-relabel, scaling, the primal-dual method, randomisation, and certificate checking. The library has adaptors between different types of graphs (directed, undirected, multigraphs), which allow results to be reused. Each algorithm is verified independently of its data structures, and the main algorithms are refined to efficient imperative implementations, from which we generate code in Standard ML, Scala, and Go. We developed parts of the library with large language models (LLMs), improved the quality of their proofs with a method based on statistics of our own proofs, and labelled which parts were developed by humans, by LLMs, or collaboratively. We perform a detailed experimental analysis of representative algorithms in our library, comparing it with state-of-the-art mainstream libraries, showing that our implementations are practical.

Closest papers

Nearest neighbours by meaning across the whole index.

Python Code Generation for Isabelle/HOL

cs.PL cs.LOcs.SE ·2026-11-17 ·Nikolaus Huber, Roly Perera, Dominic Orchard
theory similarity 0.68
Abstract · 20 pages, 19 figures, 2 tables. Software artefact: https://doi.org/10.5281/zenodo.24106993

The Isabelle theorem prover provides an environment for formalising mathematics and reasoning about programs. To make verified implementations practically usable, its code generator translates functions expressed in the executable fragment of its logic into conventional programming languages. Its targets have traditionally been functional languages (Standard ML, OCaml, Haskell, and Scala), recently joined by Go. Python, which is becoming the dominant language of scientific computing, data science, and education, has remained out of reach. In this work, we close this gap with a Python backend for Isabelle's code generator. This generator enables verified algorithms to be used in Python applications, or to serve as verified references against which established Python libraries can be differentially tested, without leaving the Python ecosystem. We validate the backend on regression suites covering large parts of the HOL library and by testing six verified data structures and algorithms against established Python libraries. The generated code is slower than hand-written libraries, but well suited as a verified reference.

0.24

Lean Graph Search for Formal Theorem Proving

cs.LG ·2026-10-15 ·Yihan Xu, Jia-Chen Gu, Junyi Zhang, Di Wu, Haikang Deng +5 more
theorycode/data similarity 0.65
Abstract · Code is available at https://github.com/PlusLabNLP/LeanGraphSearch

Retrieving relevant lemmas is crucial for formal theorem proving, enabling provers to build machine-checkable proofs from established mathematical results. Recent retrieval systems match library declarations to a target theorem or its intermediate proof steps, but make limited use of multi-hop dependencies among declarations. These dependencies can reveal supporting lemmas that are not necessarily lexically similar to the target theorem but recur in proofs of related problems. To this end, we propose LeanGraphSearch, a graph-based retrieval method for Lean 4 that constructs a graph from Mathlib's forward dependencies and traverses it to uncover supporting lemmas through multi-hop dependency chains. Specifically, LeanGraphSearch links each declaration to the premises it depends on, uses a graph-based ranking algorithm to propagate relevance from semantically matched declarations to their dependencies, and reranks the expanded candidates against the original query. Across two mathematical retrieval benchmarks, LeanGraphSearch improves recall by up to 12% over the strongest baseline, LeanSearch v2, on MathlibQR and increases coverage of complete annotated proof routes on MathlibMPR, covering up to 3.7% of extra groups. More importantly, we evaluate whether these retrieval gains translate into improved end-to-end theorem proving by integrating LeanGraphSearch into an iterative proving loop guided by Lean feedback. Across three theorem proving benchmarks, LeanGraphSearch improves pass rate at {8, 16, 32} reflection turns by as much as 40% compared to vanilla prover and at most 10% compared to LeanSearch v2, showing higher accuracy-cost efficiency. These findings highlight the value of dependency graph search for theorem proving and motivate further research on structure-aware search for proof discovery.

0.38

Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification

cs.AI cs.LOcs.PLcs.SE ·2026-10-07 ·Shuangjie Yao, Nikolaus Holzer, Mark Paul Santolucito, Baishakhi Ray, Suman Jana +1 more
benchmarktheory similarity 0.64
Abstract

Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers. It's a guarantee especially valuable for code generated by large language models (LLMs), which is fluent but carries no assurance of correctness. Almost all existing provers, however, pursue pass rates alone at whatever sampling or search budget it takes, and overlook the success-vs-cost frontier; yet real software often carries hundreds of interdependent proof obligations, so what matters at scale is not whether one theorem can be proved, but how many can be proved economically. We introduce CoCo-Prover, which formalizes cost-efficient program proving as metalevel decision-making under cost, grounded on two-level proof graphs: an AND/OR proof hypergraph within each declaration is joined to a lemma-dependency graph across declarations; and at each step, it answers two questions: which open goals to select, and which actions to purchase on these goals. Selection stays symbolic as a topological pass over the proof graphs. Action choice is agent orchestration via metalevel decision-making: an agentic router treats every bounded specialist invocation as a separately priced, best-effort computation, matching heterogeneous specialist agents together with configurations, under evolved routing rules as evidence accumulates. On five program verification benchmarks in Lean 4 including function-level CLEVER, VERINA, and AlgoVeri, and repository-level NTP4VC and Vero, we show that CoCo-Prover achieves a better success-vs-cost frontier than baselines including frontier coding agents and state-of-the-art LLM-based provers: it achieves the best solve rate on every benchmark and up to 100% on two benchmarks. It also reduces cost by up to 30.9% compared to the strongest baseline with the strongest LLM in our evaluation.

0.12

Sundance: A Simple SMT Solver for Program Verification

cs.LO ·2026-11-03 ·Amar Shah, Benjamin F. Jones, Can Cebeci, Jason Z. S. Hu, Lee A. Barnett +4 more
similarity 0.63
Abstract

We present Sundance, an SMT solver for program verification written in about 13,600 lines of Rust. Sundance combines the Cadical SAT solver with congruence closure, linear arithmetic, algebraic datatypes, and pattern-based quantifier instantiation. Sundance produces eDRAT proofs for every unsat answer. On 21,531 queries from Verus, Dafny, and F*, Sundance is comparable to existing solvers, with 26--38 times fewer lines of code than Z3 and cvc5. We further show that its components can be swapped for Z3's arithmetic solver, MiniSat, and the Semper e-graph. We have open sourced Sundance.

0.11

LLM-Assisted Verification in Dafny

cs.LO cs.AIcs.SE ·2026-11-12 ·Wieger Wesselink, Kees Huizing, Huub van de Wetering
theory similarity 0.63
Abstract · 16 pages (excluding references), 20 pages including references; 1 figure, 2 tables. Submitted to FSEN 2027

Formal verification of complex algorithms requires expertise in program specification, invariant construction, mathematical proof, and the management of automated theorem provers. Although large language models (LLMs) can generate program code and proof fragments, reliably developing complete machine-checked verifications remains challenging: it requires an iterative process of constructing and validating specifications and invariants, building proofs, diagnosing solver failures, and optimizing verification performance. This paper presents a systematic ten-step workflow for LLM-assisted verification of scientific algorithms using the Dafny verification system. The workflow integrates algorithm formalization, contract development, empirical invariant validation, proof construction, bottleneck profiling, and resource-driven proof optimization. We applied the workflow using Antrhopic's Claude Opus 5 and Opus 5.5 models, combining LLM-driven development with automated testing and verification feedback, while retaining human oversight for correctness-critical decisions and strategic interventions. We evaluate the approach on 37 complex algorithms from graph theory and labelled transition systems. Notably, we verified the Hopfcroft-Tarjan triconnectivity test, demonstrating that even highly challenging algorithmic verification tasks can be carried out through a structured LLM-assisted workflow. Many of our machine-checked verifications were obtained within hours to a few days of interactive development. Our results suggest that LLM-assisted workflows can shift the role of the human verifier from detailed proof construction toward supervision, specification review, and strategic guidance.

0.46

An algorithmic construction of Nullstellensatz certificates for graph automorphism groups

cs.SC cs.LO ·2026-10-20 ·Ivan Drecun
similarity 0.62
Abstract

Solvers for graph isomorphism and related problems are widely used in both theoretical and applied domains, but their complexity often requires users to trust their correctness without verification. We present a certifying algorithm for computing a generating set of the automorphism group of a given graph, meaning that it produces an independently verifiable certificate that the output list of automorphisms generates the entirety of the automorphism group. The problem of constructing a certificate is reduced to certifying that a system of multivariate polynomial equations is infeasible. An individualization-refinement algorithm produces a derivation within an algebraic proof system, representing a Nullstellensatz certificate of infeasibility. We provide an implementation of both the certifying algorithm and a certificate verifier, and demonstrate their viability on graphs with hundreds of vertices.

0.31

Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework

cs.DM cs.DSmath.OC ·2026-10-23 ·Bryant Gipson
similarity 0.62
Abstract · 24 pages, 8 figures

The subgraph isomorphism problem (SGI) asks a deceptively simple question: is a graph B found inside a parent graph A? Famously NP-complete and the subject of volumes of study, attempts to practically solve subgraph problems typically require specialized software or the focused application of problem-specific theoretical knowledge. Here we present a straightforward linear framework that neatly joins SGI to lattice theory and constrained satisfiability and, importantly, yields an easily implemented algorithm that naturally leverages consumer-grade hardware and off-the-shelf libraries to compete with state-of-the-art specialized solvers. We additionally show practical realizations in approachable settings, along with some benchmarks that reduce 6+ hour computations to seconds. Aimed at readability, we develop a series of computable algebraic invariants and demonstrate their application to familiar problems such as the Knight's Tour, with a focus on providing an accessible entry point for researchers in graph theory, abstract algebra, and students in general.

0.34

Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science

cs.AI cs.CLcs.LG ·2026-09-14 ·Honghao Lin, David P. Woodruff, Yuan Deng, Jieming Mao, Song Zuo +1 more
benchmarktheoryhighly cited similarity 0.62
Abstract

Language models can produce plausible short proofs, but may still be unreliable on long-horizon research problems, where progress depends on a sequence of uncertain and interdependent decisions. We introduce Stellar Colosseum, a model-agnostic harness for allocating inference across research in mathematics and theoretical computer science. Colosseum explores alternative strategies before proof construction, uses a readiness gate to decide when a route is mature enough to decompose, represents the proof plan as interdependent section-level subproblems, and routes verifier findings back to the affected part of the argument. Across these stages, it generates candidates in parallel, attacks them with targeted falsification, and combines candidates and their critiques into a single research artifact through overlapping random-sample tree aggregation. The Colosseum workflow has been integrated into Google Antigravity's Teamwork framework as the Long Proof pattern. We demonstrate the capabilities of Colosseum through open-ended research and evaluations on theorem-proving and competitive programming benchmarks. Using Colosseum with Gemini 3.1 Pro, we obtain several new results that address open problems arising from papers published at top venues such as FOCS and JMLR. On TCS-Bench, a benchmark of research-level theorem-proving tasks drawn from papers published at FOCS, STOC, and SODA, Colosseum achieves 71.0% accuracy using Gemini 3.1 Pro and Gemini 3.7 Flash. In a separate Codeforces evaluation using Gemini 3.1 Pro, the proof-oriented pipeline with execution feedback solves 218 of 222 problems.

0.38