Bayesian Separation Logic: A Logical Foundation and Axiomatic Semantics for Probabilistic Programming
Shing Hin Ho, Nicolas Wu, Azalea Raad
Abstract
Bayesian probabilistic programming languages (BPPLs) let users denote statistical models as code while the interpreter infers the posterior distribution. The semantics of BPPLs are usually mathematically complex and unable to reason about desirable properties such as expected values and independence of random variables. To reason about these properties in a non-Bayesian setting, probabilistic separation logics such as PSL and Lilac interpret separating conjunction as probabilistic independence of random variables. However, no existing separation logic can handle Bayesian updating, which is the key distinguishing feature of BPPLs. To close this gap, we introduce Bayesian separation logic ( BaSL ), a probabilistic separation logic that gives semantics to BPPL. We prove an internal version of Bayes’ theorem using a result in measure theory known as the Rokhlin-Simmons disintegration theorem. Consequently, BaSL can model probabilistic programming concepts such as Bayesian updating, unnormalised distribution, conditional distribution, soft constraint, conjugate prior and improper prior while maintaining modularity via the frame rule. The model of BaSL is based on a novel instantiation of Kripke resource monoid via 𝜎-finite measure spaces over the Hilbert cube, and the semantics of Hoare triple is compatible with an existing denotational semantics of BPPL based on the category of s-finite kernels. Using BaSL , we then prove properties of statistical models such as the expected value of Bayesian coin flip, correlation of random variables in the collider Bayesian network, the posterior distributions of the burglar alarm model, a parameter estimation algorithm, and the Gaussian mixture model.
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.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Lilac: A Modal Separation Logic for Conditional Probability cites A probabilistic separation logic
- Lilac: A Modal Separation Logic for Conditional Probability cites A separation logic for negative dependence
- Lilac: A Modal Separation Logic for Conditional Probability cites A Bunched Logic for Conditional Independence
- Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic cites Lilac: A Modal Separation Logic for Conditional Probability
- Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic cites Semantics of higher-order probabilistic programs with conditioning
- A separation logic for negative dependence cites A probabilistic separation logic
- A separation logic for negative dependence cites A Bunched Logic for Conditional Independence
- A Bunched Logic for Conditional Independence cites A probabilistic separation logic
- A Bunched Logic for Conditional Independence cites Semantics of higher-order probabilistic programs with conditioning
Cited by top-tier papers1
Builds on11
- A probabilistic separation logicGilles Barthe, Justin Hsu, Kevin LiaoPOPL 2020 · 35 citations
- Semantics of higher-order probabilistic programs with conditioningFredrik Dahlqvist, Dexter KozenPOPL 2020 · 35 citations
- Lilac: A Modal Separation Logic for Conditional ProbabilityJohn M. Li, Amal Ahmed, Steven HoltzenPLDI 2023 · 22 citations
- A separation logic for negative dependenceJialu Bao, Marco Gaboardi, Justin Hsu, Joseph TassarottiPOPL 2022 · 17 citations
- A Bunched Logic for Conditional IndependenceJialu Bao, Simon Docherty, Justin Hsu, Alexandra SilvaLICS 2021 · 15 citations
Related papers
- Contextual Refinement of Higher-Order Concurrent Probabilistic ProgramsKwing Hei Li, Alejandro Aguirre, Joseph Tassarotti, Lars BirkedalPLDI 2026
- Inference and Learning with Model Uncertainty in Probabilistic Logic ProgramsVictor Verreet, Vincent Derkinderen, Pedro Zuidberg Dos Martires, Luc De RaedtAAAI 2022 · 4 citations
- SPPL: probabilistic programming with fast exact symbolic inferenceFeras A. Saad, Martin C. Rinard, Vikash K. MansinghkaPLDI 2021 · 38 citations
- Bluebell: An Alliance of Relational Lifting and Independence for Probabilistic ReasoningJialu Bao, Emanuele D'Osualdo, Azadeh FarzanPOPL 2025 · 6 citations
- A Nominal Approach to Probabilistic Separation LogicJohn M. Li, Jon Aytac, Philip Johnson-Freyd, Amal Ahmed et al.LICS 2024 · 8 citations
