Lune

CAV2022Top-tier venue

Data-Driven Invariant Learning for Probabilistic Programs

Jialu Bao, Nitesh Trivedi, Drashti Pathak, Justin Hsu, Subhajit Roy

Abstract

Abstract Morgan and McIver’s weakest pre-expectation framework is one of the most well-established methods for deductive verification of probabilistic programs. Roughly, the idea is to generalize binary state assertions to real-valued expectations, which can measure expected values of probabilistic program quantities. While loop-free programs can be analyzed by mechanically transforming expectations, verifying loops usually requires finding an invariant expectation, a difficult task. We propose a new view of invariant expectation synthesis as a regression problem: given an input state, predict the average value of the post-expectation in the output distribution. Guided by this perspective, we develop the first data-driven invariant synthesis method for probabilistic programs. Unlike prior work on probabilistic invariant inference, our approach can learn piecewise continuous invariants without relying on template expectations. We also develop a data-driven approach to learn sub-invariants from data, which can be used to upper- or lower-bound expected values. We implement our approaches and demonstrate their effectiveness on a variety of benchmarks from the probabilistic programming literature.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

11 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • A pre-expectation calculus for probabilistic sensitivity cites Aiming low is harder: induction for lower bounds in probabilistic program verification
  • Learning Probabilistic Termination Proofs cites Neural termination analysis
  • Neural termination analysis cites Learning Probabilistic Termination Proofs
  • A Deductive Verification Infrastructure for Probabilistic Programs cites Relatively complete verification of probabilistic programs: an expressive language for expectation-based reasoning
  • A Deductive Verification Infrastructure for Probabilistic Programs cites Aiming low is harder: induction for lower bounds in probabilistic program verification
  • A Deductive Verification Infrastructure for Probabilistic Programs cites Learning Probabilistic Termination Proofs
  • A Deductive Verification Infrastructure for Probabilistic Programs cites Symbolic execution for randomized programs
  • Lower Bounds for Possibly Divergent Probabilistic Programs cites A pre-expectation calculus for probabilistic sensitivity
  • Lower Bounds for Possibly Divergent Probabilistic Programs cites Aiming low is harder: induction for lower bounds in probabilistic program verification
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers11

  1. This is the moment for probabilistic loopsMarcel Moosbrugger, Miroslav Stankovic, Ezio Bartocci, Laura KovácsOOPSLA 2022 · 30 citations
  2. A Deductive Verification Infrastructure for Probabilistic ProgramsPhilipp Schröer, Kevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen et al.OOPSLA 2023 · 22 citations
  3. Symbolic execution for randomized programsZachary Susag, Sumit Lahiri, Justin Hsu, Subhajit RoyOOPSLA 2022 · 17 citations
  4. Neural termination analysisMirco Giacobbe, Daniel Kroening, Julian ParsertFSE 2022 · 16 citations
  5. Lower Bounds for Possibly Divergent Probabilistic ProgramsShenghua Feng, Mingshuai Chen, Han Su, Benjamin Lucien Kaminski et al.OOPSLA 2023 · 14 citations

Builds on9

  1. Aiming low is harder: induction for lower bounds in probabilistic program verificationMarcel Hark, Benjamin Lucien Kaminski, Jürgen Giesl, Joost-Pieter KatoenPOPL 2020 · 47 citations
  2. Data-driven inference of representation invariantsAnders Miltner, Saswat Padhi, Todd D. Millstein, David WalkerPLDI 2020 · 33 citations
  3. Relatively complete verification of probabilistic programs: an expressive language for expectation-based reasoningKevin Batz, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph MathejaPOPL 2021 · 33 citations
  4. Learning Probabilistic Termination ProofsAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2021 · 26 citations
  5. A pre-expectation calculus for probabilistic sensitivityAlejandro Aguirre, Gilles Barthe, Justin Hsu, Benjamin Lucien Kaminski et al.POPL 2021 · 24 citations

Related papers

  1. Supermartingales for Unique Fixed Points: A Unified Approach to Lower Bound VerificationSatoshi Kura, Hiroshi Unno, Takeshi TsukadaPLDI 2026
  2. Foundations for Deductive Verification of Continuous Probabilistic Programs: From Lebesgue to Riemann and BackKevin Batz, Joost-Pieter Katoen, Francesca Randone, Tobias WinklerOOPSLA 2025 · 2 citations
  3. Automated Expected Value Analysis of Recursive ProgramsMartin Avanzini, Georg Moser, Michael SchaperPLDI 2023 · 6 citations
  4. Data-Driven Verification of Procedural Programs with Integer ArraysAhmed Bouajjani, Wael-Amine Boutglay, Peter HabermehlCAV 2025
  5. Exact Bayesian Inference for Loopy Probabilistic Programs using Generating FunctionsLutz Klinkenberg, Christian Blumenthal, Mingshuai Chen, Darion Haase et al.OOPSLA 2024 · 11 citations
Dusk over the sea between two cliffs drawn in fine vertical lines