Caesar : A Deductive Verifier for Probabilistic Programs

Philipp Schröer ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Umut Yiğit Dural, Darion Haase, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja · 2026

Read Caesar : A Deductive Verifier for Probabilistic Programs by Philipp Schröer ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Umut Yiğit Dural, Darion Haase, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15827.txt.

Introduction

Philipp Schröer and six colleagues present Caesar, a deductive verifier for probabilistic programs. Its core language, HeyVL, is a quantitative intermediate verification language built on the real-valued logic HeyLo, letting users express programs, specifications and proof rules in programming-language style. Caesar translates HeyVL programs into verification conditions checked with the Z3 SMT solver, and adds a probabilistic model-checking backend for a subset of the language. The paper reports five years of development, including new proof rules and better diagnostics.

Catalog record

CREATORPhilipp Schröer ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Umut Yiğit Dural, Darion Haase, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34116
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15827

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Caesar : A Deductive Verifier for Probabilistic Programs Philipp Schröer ( 🖂 ) {}^{(\text{\Letter})}, Kevin Batz, Umut Yiğit Dural, Darion Haase, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja Abstract Caesar is a deductive verifier for probabilistic programs. At its core lies HeyVL , a quantitative intermediate verification language based on the real-valued logic HeyLo . HeyVL allows users to express a probabilistic program, its specifications, and proof rules in a programming-language style, so that new proof rules can be easily integrated into the verifier. Caesar translates HeyVL programs into verification conditions, which are then checked using the Z3 SMT solver. It also includes a backend based on probabilistic model checking for a subset of HeyVL . We report on the results of five years of development of Caesar , highlighting its main features and architecture. In particular, we describe recent improvements such as additional proof rules, a model-checking backend, and better diagnostics. \DeclareSourcemap \maps [datatype=bibtex] \map \step [fieldsource=url, match= \regexp _, replace=_] \map \step [fieldsource=doi, match= \regexp _, replace=_] 1 Introduction We present Caesar 1 1 1 https://www.caesarverifier.org , an open-source deductive verifier for probabilistic programs, written in Rust. It is designed as verification infrastructure for a variety of properties of probabilistic programs. Probabilistic programs. Probabilistic programs incorporate random choices whose outcomes can influence the control flow of loops and conditionals. For example, Figure 1 shows the bounded retransmission protocol [ 27 ] (BRP) with a noisy transmission channel, repeatedly trying to submit a number of packets with maxTries attempts per packet before aborting. The program is written in HeyVL , a quantitative verification-aware programming language, explained below . Design and verification objectives for probabilistic programs go beyond classical safety and liveness, and are quantitative rather than Boolean. For the BRP, one may bound the failure probability, lower-bound successful transmissions, or analyze expected runtime. Figure 1 checks the first: it specifies that fail == maxTries holds on termination with probability at most 1-(1-0.01^{\texttt{maxTries}})^{\texttt{packets}} . The coproc keyword requests verification of an upper bound (given by the pre ) on the expected value of the post expectation. Here, this post is the condition fail == maxTries . To reason about the expected number of failures instead, one would use the post fail . To obtain the expected value, we use the weakest pre-expectation semantics [ 61 ] , selected with the @wp annotation. The while -loop needs a proof rule; here Park induction ( {\color[rgb]{0,0.3105,0.2246}{\texttt{@}}}{}{{\color[rgb]{0,0.3105,0.2246}{\texttt{invariant}}}}({\dots})~{\!\!} ). Figure 1 : Excerpt of HeyVL code modeling the bounded retransmission protocol. ⬇ 1 @wp coproc brp ( packets : UInt , maxTries : UInt ) 2 -> ( sent : UInt , fail : UInt , totalFail : UInt ) 3 pre 1 - exp (1 - exp (0.01, maxTries ), packets ) 4 post [ fail == maxTries ] 5 { 6 sent = 0; fail = 0; totalFail = 0 7 @invariant (...) 8 while ( sent < packets && failed < maxTries ) { 9 var transmit : Bool = flip (0.99) 10 if transmit { 11 sent = sent + 1; failed = 0 12 } else { 13 fail = fail + 1; totalFail = totalFail + 1 } } } The Intermediate Verification Language HeyVL. To tackle the diversity of verification objectives and proof rules, Caesar uses the intermediate verification language (IVL) HeyVL [ 72 ] . Similar to other IVLs such as Boogie [ 54 ] , Why3 [ 31 ] , or Viper [ 66 ] , it serves as a common language to express programs, specifications, and proof rules. HeyVL uses the real-valued logic HeyLo to express quantitative specifications and verification conditions. Quantitative verification statements such as assert and assume generalize classical Hoare-style assertions and assumptions to the setting of expected values. Probabilistic Program Specification Proof Rules HeyVL HeyLo SMT-LIB Z3 JANI Storm \checkmark Verified \times Counterexample ? Unknown Expected Values Slicing VCG Quantifier Elimination VC valid? Caesar Figure 2 : Logical architecture of the Caesar verifier. The Caesar Verifier. Main aspects of Caesar ’s design are: (1) Probabilistic programs with \mathbb{R}_{\geq 0}^{\infty} -valued specifications, (2) quantitative verification statements to encode a range of proof rules (e.g., inductive rules for reasoning about loops), and (3) duality of constructs for reasoning about lower and upper bounds of expected values. Prior work has formalised this perspective [ 72 ] . Figure 2 shows the logical architecture of Caesar . The input to Caesar is a HeyVL program consisting of a probabilistic program, a specification (quantitative pre- and post-conditions), and proof rules to be used during verification, e.g., loop invariants for while -loops. Specific diagnostics about either successful or failed verification attempts are based on the HeyVL program, and will be provided by the slicing component ( Section 5.4 ). The verification condition generator (VCG) generates expressions in the HeyLo logic, whose validity implies correctness of the HeyVL program w.r.t. its specifications. For dispatching the validity check to a solver, an important optimization is the quantifier elimination component which tries to remove (quantitative) quantifiers in the verification conditions. Finally, validity is checked by translating the HeyLo validity problem into an input to the SMT solver Z3 [ 26 ] , following the SMT-LIB standard [ 12 ] . Outputs may be either successful verification, a counterexample, or an unknown result if the solver cannot decide the validity. We give more details on these components in Section 4.1 . Caesar also includes a translation from a subset of HeyVL to the JANI modeling language [ 23 ] for probabilistic models, which can be used to calculate expected values of probabilistic programs via the Storm model checker [ 37 ] . More details on this backend are given in Section 4.2 . Contributions. In this tool paper, we report on the current state of Caesar and focus on application and implementation aspects and features. Compared to the first publication with Caesar [ 72 ] , new features presented here include additional built-in proof rules ( Section 2.3 ), support for limited functions and much improved quantifier handling ( Section 4.1 ), a model checking backend via JANI/Storm ( Section 4.2 ), a novel Visual Studio Code extension ( Section 5.2 ), semantic guardrails to prevent unsound combinations of proof rules ( Section 5.3 ), and better diagnostics via program slicing ( Section 5.4 , [ 73 ] ). 2 Verifying Probabilistic Programs Caesar ’s input language HeyVL supports different program models and verification objectives and allows specifying proof rules that should be applied to enable automated verification. 2.1 Objectives HeyVL is designed with reasoning about expected values (random variables) of probabilistic programs as the core primitive. Verification is structured around (co-)procedures. Each unit of verification, either a proc or a coproc , can be specified with quantitative analogues of pre- and post-conditions ( pre and post for short) – generalizing classical Hoare logic specifications. A proc is used to verify lower bounds ( LB ) on expected values and checks whether the expected value of the post after termination is at least the pre ’s value before execution. Dually, a coproc verifies upper bounds ( UB ) on expected values, i.e., whether the expected value of the post after termination

Read the complete text