💻 computer science

A cubical formalisation of conditional independence, Bayesian conditioning, and Pearl's d-separation soundness

This paper presents a constructive formalization in Cubical Agda that identifies the insufficiency of the standard convex-algebra interchange axiom for full Bayesian conditioning, proposes a minimal generalization to resolve the resulting structural mismatch, and verifies the soundness of Pearl's d-separation theorem and related probabilistic axioms over an abstract ordered-field interface.

Original authors: Karen Sargsyan

Published 2026-07-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Karen Sargsyan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Hidden Rules of Chance

Imagine you are a detective trying to solve a mystery, but instead of fingerprints, your clues are probabilities. In the world of statistics and artificial intelligence, there is a powerful tool called a "Bayesian Network." Think of it as a map of how different events influence one another. If it rains, the grass gets wet; if the grass is wet, the dog gets muddy. These maps rely on a concept called "conditional independence," which is a fancy way of saying: "If I know it's raining, knowing the grass is wet doesn't tell me anything new about the dog's mud."

For decades, scientists have used these maps to build self-driving cars, diagnose diseases, and understand cause-and-effect. But to make these maps work on a computer, the math behind them has to be perfect. If the rules are slightly off, the computer might draw the wrong conclusions, leading to a car crashing or a doctor misdiagnosing a patient. The big question has always been: Are the mathematical rules we've been using for years actually strong enough to handle every possible scenario, especially when we try to update our beliefs with new evidence (a process called "conditioning")?

The Paper's Discovery: A Flaw in the Foundation

This paper, written by Karen Sargsyan, dives deep into the mathematical foundation of these probability maps using a very modern, rigorous style of math called "Cubical Type Theory." You can think of this theory as a way to build mathematical structures where every rule is checked by a computer to ensure it never breaks. The author built a digital "Lego set" for probability distributions, where every piece fits together perfectly according to strict laws.

The main finding is a bit of a shock to the math world: the standard rulebook that everyone has been using for probability is actually too weak to handle the full complexity of updating beliefs. Specifically, there is a rule called the "interchange axiom" (which sounds like a traffic rule for swapping the order of events). The paper proves that this standard rule assumes that when you swap things around, the "weights" (the importance or probability) of the pieces stay the same. However, when you actually perform a Bayesian update (like saying, "Okay, given that the grass is wet, what is the chance it rained?"), those weights change in a specific, complex way that the old rule doesn't account for.

The author shows that if you try to use the old, standard rule to do this kind of updating, the math falls apart. It's like trying to build a house with a hammer that only works on straight nails; it works fine for simple tasks, but the moment you need to drive a curved nail (which is what real-world probability updates often are), the hammer breaks.

The Solution: A New, Stronger Rule

To fix this, the paper proposes a "generalized" version of that interchange rule. Instead of assuming the weights stay the same, the new rule allows the weights to change according to a specific formula (Bayes' formula) during the swap. The author proves that the old rule is just a special, simple case of this new, stronger rule—like how a square is just a special kind of rectangle.

With this new, stronger rule in place, the author successfully verified several major concepts that are crucial for AI and causal reasoning:

The Semi-Graphoid Axioms: These are the basic laws of conditional independence. The paper proves they hold true in this new, rigorous system without needing any "magic" assumptions.
Pearl's Do-Calculus: This is a set of three rules used to figure out what happens when you force an event to happen (like a scientist forcing a drug on a patient) versus just observing it. The paper proves these rules work perfectly in their new framework.
D-Separation: This is a method to check if two variables are independent just by looking at the shape of the map (the graph). The author proved that this method is sound for any possible map shape, ensuring that if the map says two things are unrelated, they truly are.

What This Means for the Future

The paper doesn't just point out a problem; it builds a working library of code (called CausalLib) that implements these corrected rules. This means that for the first time, we have a computer-verified guarantee that the math behind causal inference is solid.

The author explicitly rules out the idea that the old, standard math was sufficient for all cases. They also clarify that while they have fixed the foundation, they haven't solved every problem in the universe. For instance, they didn't tackle continuous data (like measuring exact temperature) or complex real-world data with hidden variables; they focused strictly on finite, discrete cases to prove the core logic is sound.

In short, this paper is like an engineer discovering that the blueprint for a bridge had a subtle flaw in how it handled wind loads. They didn't just patch the hole; they redesigned the blueprint with a stronger, more flexible rule, proved it works on a computer, and handed the new plans to the world so that future bridges (and AI systems) can be built safely. The result is a more trustworthy foundation for the machines that will one day make decisions for us.

Technical Summary: A Cubical Formalisation of Conditional Independence, Bayesian Conditioning, and Pearl's D-Separation Soundness

Problem Statement
The paper addresses a foundational gap in the formal verification of probabilistic reasoning: the standard convex-algebra interchange axiom, common to probability-monad formalizations since Stone, is provably too weak to support full Bayesian conditioning. While classical formalizations (e.g., in Coq) treat conditional independence (CI) as a propositional equality between real-valued probabilities, they rely on classical logic and extensionality, often requiring positivity hypotheses and division by non-zero probabilities to derive structural results like the intersection axiom. Furthermore, lifting recursive Bayesian conditioning to a higher inductive type (HIT) representation of distributions reveals a structural mismatch: the standard interchange axiom assumes a single shared inner weight for rearranged mixtures, whereas Bayesian conditioning naturally produces mixtures with distinct inner weights related by Bayes' formula.

Methodology
The author develops a constructive formalization in Cubical Agda, utilizing Cubical Type Theory and Higher Inductive Types (HITs). The methodology relies on three structural shifts from classical approaches:

Probability Monad as a HIT: Finite distributions (FDist) are defined as a HIT generated by point masses and a binary weighted-mixing operation. The standard convex-algebra laws (idempotence, skew-commutativity, boundary cases, interchange, and skew-associativity) are imposed as path constructors. This allows distributional equalities to be treated as runnable transformations (paths) rather than opaque propositional equalities.
Structural Conditional Independence: CI is defined as a path between distribution kernels (kXY z ≡ kX z ⊗D kY z) rather than a pointwise equality of real numbers. This enables compositional reasoning where CI witnesses can be transported through monadic operations.
Constructive Weight Handling: The development is polymorphic over an abstract Weight signature (an ordered field with decidable order), instantiated concretely at the rationals ( $\mathbb{Q}$ ). This avoids the undecidability of equality in constructive reals and allows for explicit handling of positivity and division.

Key Contributions and Results

The Interchange Mismatch and Generalization: The central technical finding is that the standard interchange axiom (medial law) is insufficient for full Bayesian conditioning. Conditioning a 4-leaf mixture creates two inner halves with distinct weights ( $q_1$ and $q_2$ ) related by Bayes' formula, whereas the standard axiom requires them to be identical ( $q_1 = q_2$ ). The author introduces a generalized interchange axiom (mix-bayes-interchange) that permits distinct inner weights. It is proven that the standard form is the degenerate case where these weights coincide.
Constructive Intersection Axiom: The paper provides a constructive proof of the intersection axiom (which classically requires positivity) by reducing it to contraction. Instead of Bayesian extraction via division, the proof uses structural $\Sigma$ -type witnesses of factorization and inhabitation hypotheses for conditioning variables. This recovers the full content of intersection for any concrete positive distribution model without postulates.
Pearl's Do-Calculus Verification: All three rules of Pearl's do-calculus are verified at the kernel level on small structural causal models (SCMs):
- Rules 1 & 3: Verified as corollaries of monad laws and the constBind lemma (intervention on independent variables leaves marginals unchanged).
- Rule 2: Verified on confounded SCMs using a structural CI witness that the joint prior factors. This establishes the equivalence between intervention and conditioning under independence.
Recursive Bayesian Conditioning: A total function for recursive Bayesian conditioning is defined on a full-support fragment of the HIT. The author discharges all six coherence obligations required to lift this function to the full HIT. The fifth coherence (interchange) necessitates the generalized axiom mentioned above.
Markov Category Alignment: The FDist monad is verified as a concrete instance of a Markov category (in the sense of Fritz and Cho–Jacobs). The non-trivial delete-naturality axiom (preservation of total mass) is proven via HIT induction, confirming that the path constructors correctly capture stochastic normalization.
D-Separation Soundness: The soundness of Pearl's d-separation theorem is verified constructively for arbitrary finite Directed Acyclic Graphs (DAGs). This covers both interventional forms (for multi-element sets $X, Y, Z$ ) and Bayesian forms (for elementary patterns), derived via ancestral factorization without per-path reduction.

Significance and Claims
The paper claims to provide the first constructive, machine-checked formalization of the soundness direction of Pearl's d-separation theorem at this level of generality, entirely within a type-theoretic framework.

Computational Content: Unlike classical formalizations where CI is an assertion, the cubical approach yields computational content. CI witnesses are runnable transformations; posterior distributions are executable terms computed by Agda's normalizer.
Foundational Correction: The work identifies that the standard algebraic foundation for probability monads is "too weak" for Bayesian conditioning. The proposed generalization of the interchange axiom is presented as a necessary structural refinement for any framework aiming to support full Bayesian inference within a monadic setting.
Verification of Mahadevan's Stack: The paper verifies the "bottom layer" of Mahadevan's Topos Causal Model (TCM) framework. It confirms that the kernel-form identities of the do-calculus and the commutative distribution monad hold constructively, serving as a verified substrate upon which the topos-theoretic machinery (sheaves, forcing semantics) can be built.
Zero Postulates: The entire development, including the d-separation soundness and Bayesian conditioning, is verified with zero postulates above the abstract ordered-field interface (instantiated at $\mathbb{Q}$ ). This includes the removal of previously used unsound bounds and the replacement of classical division with constructive, positivity-guarded operations.

The paper concludes that the constructive content of conditional independence and conditioning is best captured not by classical logic plus extensionality, but by the structural, path-based reasoning of cubical type theory, where the algebraic laws of probability are intrinsic to the type's definition.

The Hidden Rules of Chance

The Paper's Discovery: A Flaw in the Foundation

The Solution: A New, Stronger Rule

What This Means for the Future

Technical Summary: A Cubical Formalisation of Conditional Independence, Bayesian Conditioning, and Pearl's D-Separation Soundness

More like this