Bayesian Separation Logic

Shirley Ho, Nicolas Wu, Azalea RaadarXiv 2025 · DOI · arXiv

TL;DR

Bayesian Separation Logic (BaSL) is the first formal logic to successfully combine the modular reasoning of separation logic with the "updating" power of Bayesian inference. By proving an internal version of Bayes’ theorem using measure-theoretic disintegration, BaSL allows developers to formally verify statistical properties—like expected values and independence—in probabilistic programs that learn from data.

What Problem Does This Paper Address?

Probabilistic Programming Languages (PPLs) allow users to write statistical models as code. A key feature of these languages is Bayesian updating: you start with a "prior" belief, provide observed data (using constructs like observe or score), and the system infers a "posterior" distribution.

While we have tools to reason about standard programs, verifying PPLs is notoriously difficult. Existing "probabilistic separation logics" (like PSL or Lilac) are great at reasoning about independence—using the "separating conjunction" ($*$) to say two variables don't affect each other. However, they lack the mathematical machinery to handle the "mutation" of a distribution that happens during a Bayesian update. Before BaSL, there was no way to use the modular "frame rule"—the crown jewel of separation logic—to reason about Bayesian models.

Methods

The authors bridge the gap between logic and statistics through several novel contributions:

  • Internal Bayes’ Theorem: The core of the paper is a formal proof of Bayes’ theorem within the logic itself. To do this, they employ the Rokhlin-Simmons disintegration theorem from measure theory, which provides a rigorous way to "slice" a joint distribution into conditional distributions.
  • $\sigma$-Finite Measure Semantics: Most previous logics were restricted to probability measures (where everything sums to 1). BaSL moves to $\sigma$-finite measure spaces. This allows the logic to handle unnormalized distributions (common during intermediate calculation steps) and improper priors (like the Lebesgue measure), which are essential in "objective" Bayesian statistics.
  • Kripke Resource Monoid: They define a new semantic model for "randomness as a resource." In this view, a random number generator is a resource that can be split, used, and—critically—updated based on observations.
  • Axiomatic Semantics: They provide a set of Hoare rules (preconditions and postconditions) for PPL constructs. This allows for symbolic reasoning: instead of running a simulation, you can "calculate" the posterior distribution through logical steps.

Datasets

As a theoretical paper in formal methods, BaSL does not use traditional machine learning datasets. Instead, it evaluates its expressivity by proving properties of six classic statistical "benchmark" models:

  1. Bayesian Coin Flip: Calculating the fairness of a coin after multiple tosses.
  2. Burglar Alarm: A classic Bayesian network involving joint conditioning.
  3. Collider Network: Demonstrating how two independent variables become correlated after observing a common effect.
  4. GaussParam: A parameter estimation algorithm using conjugate priors.
  5. Lebesgue Measure: Handling improper priors.
  6. Gaussian Mixture Model (GMM): Reasoning about clustering and bounded loops.

Key Insights and Ideas

  • Conditioning as Mutation: The "aha moment" is treating a Bayesian update like a memory write. In standard separation logic, you reason about how a pointer changes; in BaSL, you reason about how an observe statement "mutates" the underlying measure of the state.
  • The Power of the Frame Rule: Because BaSL is a separation logic, it supports the frame rule. This means if you have a proof about a small sub-model, you can "frame it" into a larger program without re-proving everything. This is a massive win for the scalability of formal verification in AI.
  • Justifying Program Rewrites: The authors show BaSL can prove that a computationally expensive program (e.g., one with many loops and observations) is mathematically equivalent to a simpler, more efficient one (e.g., sampling directly from a conjugate posterior).

Key Results

  • Soundness: The authors proved that their logic is mathematically sound with respect to the standard denotational semantics of probabilistic programs (based on $s$-finite kernels).
  • Symbolic Verification: They successfully derived the posterior distributions for the six models mentioned above. For example, they formally proved that in a "collider" network, two independent coin flips become negatively correlated once you know the result of their logical OR.
  • Conjugate Priors as Rules: They showed that common statistical patterns, like the Normal-Normal or Beta-Bernoulli conjugate pairs, can be expressed as simple, reusable logical rules.

Limitations and Future Work

  • Mechanization: The proofs in this paper are currently "pen-and-paper." The authors identify mechanizing BaSL in a theorem prover like Coq (Rocq) as a high priority for future work.
  • Language Expressivity: The current version of the logic focuses on first-order programs. It does not yet support higher-order functions (functions that take other functions as arguments) or general recursion, though it does handle bounded loops.
  • Mutable State: While it is a "separation logic," it currently treats the distribution as the resource. Integrating this with actual mutable memory (heaps) is a logical next step.
  • Non-parametric Models: The authors aim to extend the logic to handle models with an unbounded number of random variables, which are common in modern Bayesian non-parametrics.

Summary updated

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.
BibTeX
@misc{ho2025bayesian,
  author = {Shirley Ho and Nicolas Wu and Azalea Raad},
  title = {{Bayesian Separation Logic}},
  year = {2025},
  eprint = {2507.15530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.15530},
  howpublished = {arXiv},
}
Figure