💻 computer science

Bayesian Networks and Proof-Nets: the proof-theory of Bayesian Inference

This paper establishes a proof-theoretical framework for Bayesian inference by mapping Bayesian Networks to linear logic proof-nets, aiming to provide compositional graphical methods that balance structural flexibility with computational efficiency.

Original authors: Rémi Di Guardia, Thomas Ehrhard, Jérôme Evrard, Claudia Faggian

Published 2026-02-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rémi Di Guardia, Thomas Ehrhard, Jérôme Evrard, Claudia Faggian

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

Imagine you are trying to solve a giant, complex puzzle. In the world of probability, this puzzle is a Bayesian Network. It's a map of how different things in the world are connected and how likely they are to happen. For example, does the grass being wet mean it rained, or did the sprinkler turn on?

Usually, solving these puzzles is like trying to eat a whole elephant in one bite. You have to calculate the probability of every single possible combination of events at once. If you have many variables, the math explodes, and computers get overwhelmed.

This paper introduces a clever new way to look at these puzzles. The authors, Remi Di Guardia and his team, propose a bridge between two very different fields: Bayesian Networks (used for probability) and Proof-Nets (a fancy way of drawing logic proofs).

Here is the breakdown of their idea using simple analogies:

1. The Two Languages: Maps vs. Logic Trees

Bayesian Networks are like road maps. They show you the connections between cities (variables). They are great because they let you break a huge journey into smaller, manageable legs.
Proof-Nets are like blueprints for logic. They are usually drawn as trees (branching out from a single root). In traditional logic, you build a proof tree step-by-step.

The authors say: "Why not treat our probability maps like logic blueprints?" They found that if you draw a Bayesian Network as a specific kind of logic diagram (a Proof-Net), you can use the powerful rules of logic to solve probability problems.

2. The Magic Trick: Cutting and Gluing

The core of their discovery is about efficiency.

In traditional logic, you build a proof tree. It's rigid. You can't easily chop a tree in half and glue it back together in a new shape without breaking the rules.

But Proof-Nets are more like Lego structures. They are graphs (webs of connections) rather than strict trees.

The Problem: If you try to calculate the answer for a huge network all at once, it's slow and memory-heavy.
The Solution: Because Proof-Nets are flexible webs, you can "cut" the web into smaller, independent chunks (sub-nets), solve each chunk separately, and then "glue" the answers back together.

Think of it like a group of friends trying to solve a massive jigsaw puzzle.

Old Way: Everyone stands around one giant table trying to fit every piece at once. It's chaotic and slow.
New Way (The Paper's Method): You cut the puzzle into three smaller piles. Friend A solves pile 1, Friend B solves pile 2, and Friend C solves pile 3. Then, they bring their finished sections together to complete the big picture. Because they worked on smaller pieces, they finished much faster.

3. The "Box" Concept

In these diagrams, the authors use special boxes to hold the "rules" (the probabilities).

Imagine a box labeled "Rain." Inside, it has a little note saying, "If it's Dry Season, there's a 20% chance of rain."
These boxes are connected by lines. The lines represent how information flows.
The magic is that you can move these boxes around, cut the lines, and re-arrange the whole structure without changing the final answer. It's like rearranging the furniture in a room; the room is still the same size, but the layout is now easier to navigate.

4. Why This Matters (The "Efficiency" Part)

The paper claims that by using this "graph" approach instead of the traditional "tree" approach, you can solve these probability problems much more efficiently.

The "Cost" of Thinking: In computer science, "cost" means how much time and memory a computer needs.
The Breakthrough: The authors show that by breaking the network into smaller pieces (a process they call factorization), the computer doesn't have to hold the entire massive puzzle in its memory at once. It only needs to hold the small pieces.
The Result: They prove that this method is mathematically sound (it gives the right answer) and computationally efficient (it's faster).

5. A Visual Proof of "Independence"

One of the coolest parts of the paper is how they use these diagrams to prove a concept called Conditional Independence.

The Concept: Sometimes, knowing about one thing (e.g., the traffic jam) tells you nothing about another thing (e.g., the sprinkler) if you already know a third thing (e.g., it's raining).
The Visual Proof: The authors show that if you look at the diagram and "cut out" the part representing the rain, the path between the traffic and the sprinkler disappears. The diagram literally shows the connection is broken. They provide a simple, visual way to prove this rule, which usually requires pages of complex math.

Summary

The paper says: "Let's stop treating probability problems like rigid trees and start treating them like flexible webs."

By translating probability networks into a specific type of logic diagram (Proof-Nets), we can:

Cut the problem into smaller, easier pieces.
Solve those pieces independently.
Reassemble the answers quickly.

This gives us a new, powerful toolkit that combines the best of probability (handling uncertainty) with the best of logic (structured, efficient reasoning). It's like upgrading from a manual screwdriver to a power drill for solving complex probability puzzles.

Technical Summary: Bayesian Networks and Proof-Nets: the proof-theory of Bayesian Inference

Problem Statement
Bayesian Networks (BNs) are a standard tool for probabilistic reasoning, offering compact, factorized representations of joint probability distributions and enabling efficient inference algorithms. However, existing categorical approaches to probabilistic reasoning, while providing a rich compositional and graphical language (e.g., string diagrams), often fail to account for the computational cost (time and space) of inference. Conversely, standard BN algorithms are efficient but lack a deep proof-theoretical foundation that unifies graphical reasoning with the structural properties of logic. The authors identify a gap in providing a framework that simultaneously accommodates compositional, graphical reasoning and computational efficiency, specifically addressing the "cost-aware" perspective often missing in categorical probability.

Methodology
The paper proposes a proof-theoretical account of Bayesian inference using Linear Logic (LL), specifically its graph syntax known as proof-nets. The methodology involves:

Formalism Extension: The authors extend Multiplicative Linear Logic (MLL) with probabilistic boxes. These boxes encode Conditional Probability Tables (CPTs) associated with nodes in a Bayesian Network. The syntax includes standard MLL nodes (tensor, par, cut, axiom) plus structural rules (weakening, contraction) and these new probabilistic boxes.
Correspondence: They establish a sound and complete correspondence between Bayesian Networks and Bayesian Proof-Nets (bpn). A bpn is defined as a proof-net where boxes store CPTs, positive conclusions are distinct, and all conclusions are positive.
Semantics via Factors: Adopting the factor-based semantics from prior work (e.g., [8]), the semantics of a bpn is defined as the product of the factors (CPTs) associated with its boxes, followed by marginalization (summing out) variables not present in the conclusions. This aligns the semantics directly with the standard definition of BNs.
Graph Decomposition: Unlike proof-trees, which decompose strictly according to inductive syntax, proof-nets allow for flexible graph decomposition. The authors utilize splitting (via ax-expansion) to decompose a bpn into sub-nets connected by cut-nodes, forming a structure called a cut-net.
Graph Rewriting: The paper employs cut-elimination (and its dual, cut-expansion) as a graph-rewriting process. This includes standard reduction rules and a specific box/weakening reduction used to "prune" the graph, effectively performing marginalization by removing irrelevant variables.

Key Contributions

Proof-Theoretical Account of Inference: The paper provides a foundational understanding where cut-elimination and cut-expansion play a central role in Bayesian inference. It frames inference not just as a calculation, but as a structural transformation of proofs.
Stronger Compositionality: The authors introduce a notion of "component" specific to graphs, which is stronger than previous tree-based definitions. They prove Theorem 5.2 (Graphs Compositionality), demonstrating that the semantics of a proof-net can be computed compositionally regardless of how the graph is decomposed into sub-nets connected by cuts. This validates the equation:
$\llbracket Cut(R_1, R_2) \rrbracket = \sum_Z (\llbracket R_1 \rrbracket \odot \llbracket R_2 \rrbracket)$
where $Z$ represents the names to be marginalized.
Graphical Proof of d-Separation: In Section 7, the authors provide a direct, diagrammatic proof of the soundness of d-separation (a criterion for conditional independence). By using graph decomposition and the compositionality of semantics, they show that if two sets of variables are disconnected in the graph (after removing edges labeled by a conditioning set), they are conditionally independent.
Efficient Inference via Cut-Nets: The paper demonstrates how to mimic efficient BN inference algorithms (like variable elimination) using proof-nets. By transforming a bpn into a rooted cut-net (a tree-like structure of sub-nets), the authors show that the computational cost can be significantly reduced. The cost is determined by the width of the cut-net (the maximum number of variables in any sub-net), rather than the total number of variables.
Typing and Sequentialization: The authors address the challenge that graph decompositions (cut-nets) do not always correspond directly to sequent calculus proof-trees. They prove (Theorem 8.3) that any cut-net can be transformed via $\otimes/\parr$ -expansions into an equivalent form where sub-nets are connected by at most one cut, thereby allowing the decomposition to be translated back into a valid sequent calculus proof-tree.

Results

Soundness and Completeness: The correspondence between BNs and bpn is proven to be sound and complete. Every BN maps to a positive bpn, and the normal form of any positive bpn maps back to a BN.
Termination and Confluence: The reduction systems (including standard cut-elimination and the new box/weakening reduction) are proven to be terminating and confluent.
Cost Efficiency: The paper shows that by factorizing a proof-net into a cut-net, the space and time complexity of computing the semantics drops from $O(m \cdot 2^n)$ (where $n$ is the total number of variables) to $O(n \cdot 2^w)$ , where $w$ is the width of the cut-net. This mirrors the efficiency gains of variable elimination in BNs.
Invariance: The semantics of a bpn is invariant under reduction and expansion, ensuring that the probabilistic meaning is preserved during the rewriting process.

Significance
The paper claims to "unlock the best of both approaches": the efficiency of factorized computation found in Bayesian Networks and the graphical, compositional reasoning of proof-theory. By grounding Bayesian inference in the rich toolbox of Linear Logic, the authors provide a framework that is intrinsically "resource-aware." This allows for a unified treatment where the structural manipulation of proofs (graph rewriting) directly corresponds to probabilistic inference steps (marginalization and conditioning). The work bridges the gap between the abstract, structural elegance of categorical probability and the practical, cost-conscious requirements of probabilistic reasoning, offering a new perspective where the "cornerstone of proof-theory" (cut-elimination) serves as the mechanism for efficient inference.