Formally Certified Approximate Model Counting

The paper presents a novel certification framework for approximate model counting in conjunctive normal form (CNF) formulas. The approach combines a formally verified proof of the algorithm's PAC guarantee using Isabelle/HOL with dynamic verification of interactions with an incremental solver. This hybrid method ensures output quality through proof certificates, with minimal overhead. The framework, ApproxMCCert and CertCheck, successfully verifies 84.7% of instances, addressing the need for trustworthy approximate counts. The work includes efficiency improvements, bug fixes, and formalizations, with applications in formal verification and AI. A benchmark evaluation compares the performance of different methods, showing practicality of the approach.