Verification of the CVM Algorithm with a Functional Probabilistic Invariant

Emin Karayel, Seng Joe Watt, Derek Khu, Kuldeep S. Meel, Yong Kiam TanITP 2025 · OpenReview

TL;DR

This paper introduces a novel proof technique called "functional probabilistic invariants" to formally verify a simple yet powerful streaming algorithm for counting distinct elements (the CVM algorithm). This new method significantly simplifies the verification process and enables the development and proof of a more robust variant of the CVM algorithm that is both total and unbiased.

What Problem Does This Paper Address?

Estimating the number of unique items in a massive data stream is a fundamental problem in computer science with applications ranging from network traffic analysis to database query optimization. While many algorithms exist, they often rely on complex techniques like hashing or intricate derandomization. The CVM algorithm, introduced by Chakraborty, Vinodchandran, and Meel, stood out for its simplicity and efficiency, achieving near-optimal space complexity without these complexities. However, its direct formal analysis was challenging due to the inherent dependencies between its internal state variables, making standard probabilistic analysis techniques (which assume independence) difficult to apply. The original proof required a series of transformations to circumvent these dependencies.

Methods

The core contribution of this paper is the development of a new proof technique: functional probabilistic invariants. This method draws inspiration from loop invariants used in deterministic program verification. Instead of proving properties about the exact distribution of the algorithm's state (which can be intractable), the authors define invariants of the form $E[h] \le h(c)$, where $E$ is the expectation over the algorithm's state distribution, $h$ is a function (a "functional") mapping states to real numbers, and $c$ is a fixed state. By establishing such invariants inductively over the algorithm's steps, they can derive concentration bounds (tail bounds) for the algorithm's output.

This technique was used to:

  • Formally verify the original CVM algorithm: The authors show how their functional probabilistic invariants simplify the analysis compared to the original transformation-based proof.
  • Introduce and verify a new CVM variant: This variant is "total" (never fails) and "unbiased" (its expected output is exactly the true count). This required formalizing a library of results on negatively associated random variables, a generalization of independence that still allows for strong probabilistic bounds.

The entire formalization was carried out using the Isabelle/HOL proof assistant.

Datasets

Not discussed in the paper. The paper focuses on the theoretical verification of an algorithm operating on abstract data streams.

Key Insights and Ideas

  • Functional Probabilistic Invariants as a Powerful Verification Tool: The paper demonstrates that this new class of invariants can simplify the analysis of complex randomized algorithms, particularly those with dependent state variables, by focusing on properties of functions of the state rather than the state distribution itself.
  • Bridging the Gap to Unbiasedness and Totality: The invariant-based approach naturally led to the design of a new CVM variant that is both total (always produces an estimate) and unbiased (the expected estimate is correct). This is a significant improvement over the original algorithm, which could fail and was not guaranteed to be unbiased.
  • Negative Association as a Generalization of Independence: The formalization of negatively associated random variables provided the necessary theoretical foundation to prove properties of the new CVM variant, highlighting its utility in probabilistic reasoning.
  • Mechanized Verification for Robustness: The use of Isabelle/HOL not only confirmed the correctness of the algorithms but also provided a rigorous and reproducible proof, reducing the risk of errors common in manual proofs.

Key Results

  • Simplified Formalization: The authors' invariant-based approach resulted in a significantly shorter formalization of the original CVM algorithm (1003 lines of Isabelle/HOL code) compared to the original transformation-based proof (2634 lines).
  • Verification of a Total and Unbiased CVM Variant: A new variant of the CVM algorithm was introduced and formally verified to be both total and unbiased, a property not present in the original.
  • Formalized Library for Negative Association: A comprehensive library of results on negatively associated random variables was formalized in Isabelle/HOL, contributing to the formal verification community.

Limitations and Future Work

  • Generalizability of the Technique: While the paper demonstrates the technique's effectiveness for the CVM algorithm, the authors suggest that identifying suitable functionals for other randomized algorithms is an interesting avenue for future work. They believe this could lead to further refinements of their method and a better understanding of its applicability.
  • Artificial Examples: The authors note that they have yet to apply their proof technique to examples beyond CVM, suggesting that constructing artificial examples could help in exploring the method's capabilities.
  • Further CVM Variations: The paper mentions that formalizing other variations of subsampling for CVM would be an interesting future direction.

Summary updated

Abstract

Estimating the number of distinct elements in a data stream is a classic problem with numerous applications in computer science. We formalize a recent, remarkably simple, randomized algorithm for this problem due to Chakraborty, Vinodchandran, and Meel (called the CVM algorithm). Their algorithm deviated considerably from the state of the art, due to its avoidance of intricate derandomization techniques, while still maintaining a close-to-optimal logarithmic space complexity. Central to our formalization is a new proof technique based on functional probabilistic invariants, which allows us to derive concentration bounds using the Cramér-Chernoff method without relying on independence. This simplifies the formal analysis considerably compared to the original proof by Chakraborty et al. Moreover, our technique opens up the possible algorithm design space; we demonstrate this by introducing and verifying a new variant of the CVM algorithm that is both total and unbiased - neither of which is a property of the original algorithm. In this paper, we introduce the proof technique, describe its use in mechanizing both versions of the CVM algorithm in Isabelle/HOL, and present a supporting formalized library on negatively associated random variables used to verify the latter variant.
BibTeX
@inproceedings{karayel2025verification,
  author = {Emin Karayel and Seng Joe Watt and Derek Khu and Kuldeep S. Meel and Yong Kiam Tan},
  title = {{Verification of the CVM Algorithm with a Functional Probabilistic Invariant}},
  booktitle = {ITP},
  year = {2025},
  url = {https://openreview.net/forum?id=F4oCgB2aF8},
}
Figure