To Zip Through the Cost Analysis of Probabilistic Programs CCS: Theory of computation Program verification

Matthias Hetzenberger, Georg Moser, Florian Zuleger · 2025

Read To Zip Through the Cost Analysis of Probabilistic Programs CCS: Theory of computation Program verification by Matthias Hetzenberger, Georg Moser, Florian Zuleger (2025) 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-2508-14249.txt.

Introduction

Matthias Hetzenberger, Georg Moser, and Florian Zuleger teach a typed programming framework to reason about the expected cost of programs that flip coins, in a 2025 paper. Probabilistic programs are everywhere, yet proving how long they run on average lags far behind proving them correct. Their tool is a refinement-typed probability monad inside Liquid Haskell, a language whose types carry checkable claims. Random behavior is encoded in the types themselves.

An automated solver then discharges many cost claims with little human annotation. Four case studies test the range: meldable heaps and the coupon collector run nearly automatically, while randomized quicksort and zip trees mix automation with interactive proof. The zip tree result is the first formal check of its expected runtime. The authors pitch the monad as a bridge between programming practice and proof.

Catalog record

CREATORMatthias Hetzenberger, Georg Moser, Florian Zuleger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-14249

Browse the full library · About the Tower of Babel

Full text

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

To Zip Through the Cost Analysis of Probabilistic Programs CCS: Theory of computation Program verification Matthias Hetzenberger, Georg Moser, Florian Zuleger Abstract . Probabilistic programming and the formal analysis of probabilistic algorithms are active areas of research, driven by the widespread use of randomness to improve performance. While functional correctness has seen substantial progress, automated reasoning about expected runtime remains comparatively limited. In this work, we address this challenge by introducing a refinement-typed probability monad in Liquid Haskell. Our monad enables automated reasoning about expected values and costs by encoding probabilistic behaviour directly in types. Initially defined for discrete distributions over finite support, it is extended to support infinite distributions via an axiomatic approach. By leveraging Liquid Haskell’s SMT-based refinement type checking, our framework provides a high degree of automation. We evaluate our approach through four case studies: meldable heaps, coupon collector, randomised quicksort, and zip trees. The first two demonstrate automation with minimal annotation overhead. The latter two showcase how our monad integrates with interactive proofs, including the first formal verification of the expected runtime of zip trees. 1. Introduction Table 1. LOC of Liquid Haskell Formalisations Probability Monad 370 Probability Monad Theorems 2 960 Meldable Heaps 122 Coupon Collector’s Problem 27 Quicksort: Functional Correctness 117 Quicksort: Expected Cost 305 Zip Trees: Functional Correctness 591 Zip Trees: Expected Cost 7 539 Finite Sum Library 602 Logarithm Axiomatisation 150 Probabilistic programming and the automated analysis of probabilistic programs have become increasingly prominent in programming languages and formal verification research (see e.g. ( BKS:2020 ; NipkowB19 ; EberlHN20 ; LMZ:2022 ; VasilenkoVB22 ; AvanziniBGMV24 ) ). This growing interest is driven by the need to rigorously reason about systems that incorporate randomness, whether in decision-making, randomised algorithms, or data structures. Recent advances in semantics, verification frameworks, and type systems have enabled deeper insights into such systems. However, achieving high degrees of automation in this domain remains challenging due to the inherent complexity of probabilistic reasoning and the mathematical sophistication required to handle distributions, expected values and (expected) cost models. Probabilistic algorithms and data structures offer substantial performance benefits by leveraging randomness. The prototypical example of the former is randomised quicksort ( Cormen:2009 ) , where the use of a random seed to choose the pivot uniformly yields the expected complexity of \bO(n\log n) for a list of length n . Further notable examples include coupon collector schemes ( MitzenMacherU05 ) , meldable heaps ( MartinezR98 ) , skip lists ( Pugh90 ) and zip trees ( TarjanLT21 ) , all of which exhibit favourable expected runtime behaviour. While their theoretical efficiency is well established, the automated verification of their expected runtime has received comparatively less attention. This paper addresses this gap by presenting formal analyses of four prominent probabilistic case studies: meldable heaps, the coupon collector problem, randomised quicksort, and zip trees. These case studies serve as benchmarks to demonstrate our method’s applicability and scalability. To facilitate the automated analysis of probabilistic cost, we propose a novel probability monad embedded in Liquid Haskell. Our approach builds on refinement types, a lightweight formalism that supports expressive specifications and leverages SMT solvers for automated verification. By encoding expected cost bounds and functional correctness directly in types, our probabilistic cost monad enables Liquid Haskell to discharge complex probabilistic reasoning tasks automatically. This work advances prior efforts by extending Liquid Haskell’s capabilities to reason about probabilistic computations, thus narrowing the gap between manual proofs and fully automated verification. We demonstrate that our monadic approach achieves a high degree of automation through detailed case studies on meldable heaps and the coupon collector problem. In these instances, the refinement types provide enough guidance for Liquid Haskell to verify expected runtime bounds with minimal user annotations. 1 1 1 One may say “we zip trough” the formalisation effort in these case studies. Our results show that the ratio of proof annotations to program code remains low, indicating a substantial degree of automation in verifying probabilistic cost. To further showcase the robustness of our approach, we extend our evaluation to randomised quicksort and zip trees. These examples highlight how our framework can combine automated refinement-type checking with more involved interactive proofs. Notably, our formalisation of zip trees is, to the best of our knowledge, the first complete formal verification of their expected runtime performance. Given that zip trees are functionally isomorphic to skip lists and share their desirable performance characteristics, this formal verification constitutes a significant milestone in the verification of modern probabilistic data structures. In Table 1 we summarise the lines of code representing our formalisations, counting both Haskell code and refinement annotations. Our contributions We present a general-purpose library – encoded as a probability monad – for implementing and verifying probabilistic algorithms in Liquid Haskell, supporting reasoning about both expected values and expected costs. Our contributions are as follows: (1) A refinement-typed probability monad. We design a probability monad tailored for discrete distributions over finite support, leveraging refinement types to enable a high degree of automation. To extend its applicability, we later combine this monad with an axiomatic treatment of infinite structures, thereby supporting discrete distributions with infinite support (see ). (2) Automation in probabilistic cost analysis. We demonstrate the effectiveness of our approach through two case studies: meldable heaps and the coupon collector problem. In both cases, our system verifies expected runtime bounds with minimal annotation and proof effort, evidencing strong automation capabilities. (3) Integration with interactive verification. We show that our probability monad integrates well with Liquid Haskell’s interactive proof features, enabling the verification of sophisticated probabilistic data structures. Notably, we present the first formal verification of the expected runtime of zip trees. Additionally, we provide a Liquid Haskell library for reasoning about finite sums, which supports the verification of randomised quicksort and zip trees. Outline We start with motivating the central contribution of our work: a novel probability monad for Liquid Haskell, allowing us to reason about expected costs and values simultaneously. Section 3 provides a gentle introduction in the use of refinement types for program verification, exemplified by establishing a library for dealing with finite lists, as well as the axiomatisation of the logarithmic function. The main technical contribution of this work is presented in , while details the short case study on randomised meldable heaps. The Sections and deal with the case study of the Coupon Collector’s problem as well as with the novel formalisation of zip trees. details soundness of our conservative extension of Liquid Haskell. Finally, after discussing related work in , we conclude in . In the Appendix, , we discuss the case study of randomised quicksort and give the full proofs formalised in Liquid Haskell for the theorems used in this paper. Further, we make the implementation of the probability monad available as (online) Supplementary Material. 2. Overview ⬇ 1 {- @ 2 data Heap # a = Empty 3 | Heap { key :: # a , left :: Heap { v :# a | key \leqslant v }, right :: Heap { v :# a | key \leqslant v } } 4 5 meld :: Ord # a \Rightarrow h1 : Heap # a \to h2 : Heap # a 6 \to { result : ProperDist

Read the complete text