💻 computer science

Reasoning with Probabilities: Relating Weighted Model Counting and Probabilistic Model Checking

This paper establishes a formal bidirectional mapping between weighted model counting and probabilistic model checking by translating cycle-free parametric Markov chains to arithmetic circuits and vice versa, thereby enabling the cross-framework transfer of optimization techniques like bisimulation minimization.

Original authors: Bahare Salmani, Vincent Derkinderen

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bahare Salmani, Vincent Derkinderen

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

In the vast landscape of modern computing, two powerful methods have emerged to help machines reason about uncertainty. One approach, known as weighted model counting, treats a problem like a complex puzzle made of logical statements. It asks: if we assign a specific likelihood to every possible piece of the puzzle, what is the total weight of all the ways the puzzle can be solved? This method is excellent for calculating probabilities in systems where the rules are fixed and the structure is a straight line, moving from start to finish without looping back. The other approach, called probabilistic model checking, views a system as a map of states and transitions. Imagine a traveler moving through a series of rooms, where the doors they take are determined by chance. This method is designed to verify whether a traveler will eventually reach a specific destination, even if the map contains loops or unexpected detours. For decades, these two fields developed in parallel, each with its own tools and experts, solving similar problems about chance and logic but rarely speaking to one another.

A team of researchers at KU Leuven in Belgium has now built a bridge between these two worlds. They discovered that these seemingly different methods are actually two sides of the same coin, capable of translating into one another under specific conditions. The researchers demonstrated that for systems that do not contain loops—where the path always moves forward without circling back—the complex task of calculating the chance of reaching a goal in a state-based map can be converted into a weighted model counting problem. Conversely, they showed that certain types of logical circuits used for counting can be reimagined as these state-based maps. This is not just a theoretical curiosity; it means that the powerful optimization tricks developed for one field can now be applied to the other. If a computer scientist can simplify a complex map by merging identical rooms, they can now apply that same simplification to a logical circuit, and vice versa.

The core of this work involves a precise translation process. The researchers took a model of a system that moves through states with unknown probabilities—represented by variables rather than fixed numbers—and converted it into an arithmetic circuit. In this circuit, the movement between states becomes a series of additions and multiplications. The probability of reaching a goal is no longer found by solving a system of equations, but by evaluating the circuit with specific values. The team proved that the result of this evaluation is exactly the same as the probability calculated in the original state-based model. They also went the other way, taking specific types of logical circuits and turning them back into state-based maps. This bidirectional translation allows the researchers to treat the problem of finding a probability as a journey through a map, or as a calculation through a circuit, depending on which tool is more efficient for the job at hand.

This connection is particularly useful for understanding how systems handle independence. In many real-world scenarios, such as predicting the weather or analyzing a network of sensors, different factors operate independently of one another. In the world of logical circuits, this independence is handled by a mathematical property called factorization, where the calculation for one part of the system does not need to be repeated for another. In the world of state-based maps, this same independence is handled by a technique called bisimulation, which identifies and merges states that behave identically. The researchers showed that these two concepts are deeply linked. When a logical circuit is translated into a state-based map, the factorization in the circuit appears as a specific pattern of identical states in the map. This explains why simplifying a map by merging identical states often leads to massive speedups in calculation; it is essentially the map version of the circuit's ability to factorize independent events.

The implications of this work extend beyond simple theory. The researchers noted that while weighted model counting is incredibly fast for large, loop-free systems, it struggles with models that contain cycles or loops, which are common in dynamic systems like traffic networks or biological processes. Probabilistic model checking, however, handles these loops naturally. By establishing this formal link, the researchers suggest that techniques for handling loops in model checking could eventually be adapted to help weighted model counting tackle more complex, cyclic problems. They also highlighted that this translation preserves the structure of the original problem, meaning that if a system is known to be easy to solve in one framework, it will likely remain easy to solve in the other. This opens the door for transferring advanced optimization strategies across the divide, potentially making it possible to analyze much larger and more intricate systems than was previously feasible.

Ultimately, this research provides a unified language for probabilistic reasoning. It clarifies that the difference between counting solutions and checking paths is often just a matter of perspective. By showing how to move seamlessly between these perspectives, the researchers have provided a toolkit that allows experts to choose the most efficient method for their specific problem, or to combine the strengths of both. The work suggests that the future of probabilistic inference may lie not in choosing one method over the other, but in understanding how they complement each other, allowing for more robust and scalable analysis of the uncertain world around us.

Technical Summary: Reasoning with Probabilities: Relating Weighted Model Counting and Probabilistic Model Checking

Problem Statement
Weighted Model Counting (WMC) and Probabilistic Model Checking (PMC) are two established frameworks for probabilistic reasoning. WMC, rooted in propositional logic and arithmetic circuits (ACs), is a dominant method for probabilistic inference, particularly in machine learning and AI. PMC, traditionally used for verifying stochastic systems like Markov Chains (MCs) and Markov Decision Processes (MDPs), has recently been applied to inference tasks, including those in Bayesian networks. Despite their overlapping applications, the formal relationship between these two frameworks remains largely unexplored. Existing literature often focuses on specific instances (e.g., Bayesian networks) without providing a general conceptual bridge or a comparative view of how they model and compute probability distributions. This paper aims to lay the foundations for understanding the formal correspondence between WMC and PMC, specifically in the context of probabilistic inference.

Methodology
The authors establish a bidirectional formal mapping between cycle-free parametric Markov chains (pMCs) and arithmetic circuits (ACs).

Mapping pMCs to ACs: The paper defines a construction that transforms a cycle-free pMC into an arithmetic circuit. In this mapping:
- Each state in the pMC corresponds to a sum node ( $+$ ) in the AC.
- Each transition between states corresponds to a multiplication node ( $\times$ ).
- Transition probabilities (which may be polynomials over parameters in a pMC) and state labels (literals) are mapped to leaf nodes or weights within the circuit.
- The authors prove that computing the reachability probability in the pMC is equivalent to evaluating the corresponding AC under a specific weight function. This effectively reduces the reachability problem to a Weighted Model Counting problem.
Mapping ACs to pMCs: Conversely, the paper presents a mapping from specific subclasses of arithmetic circuits (those with probabilistic semantics, alternating sum/product nodes, and a sum root) back to pMCs.
- Sum nodes in the AC become states in the pMC.
- Multiplication nodes become transitions.
- The construction handles "independence-derived" multiplication nodes (those connecting to multiple sum nodes) by sequentially connecting sub-pMCs.
- A sink state is introduced to absorb probability mass where the sum of outgoing transition weights is less than 1.
- The authors demonstrate that evaluating the AC is equivalent to computing the reachability probability in the resulting pMC.
Semantic Correspondence: The paper discusses how concepts in one framework map to the other. Specifically, it relates probabilistic bisimulation (an equivalence relation used to minimize MCs) to factorization and conditional independence in the underlying probability distributions represented by ACs. This provides a semantic explanation for why bisimulation minimization improves inference efficiency in PMC-based approaches to Bayesian networks.

Key Contributions

Formal Mappings: The authors provide the first detailed formal mappings between cycle-free pMCs and ACs in both directions, enabling the reduction of reachability probability computations in pMCs to WMC on ACs, and vice versa.
Conceptual Bridge: The work establishes a detailed correspondence between the entities of WMC and PMC (e.g., mapping literals to state labels, transition probabilities to AC weights, and path probabilities to terms).
Transfer of Optimization Techniques: By preserving the structural properties of the input formalisms, the mappings suggest that tractability results and optimization techniques can transfer between frameworks. For instance, bisimulation minimization in PMC is shown to correspond to exploiting conditional independence in the probability distribution, explaining the efficiency gains observed in previous literature.
Generalization: Unlike prior comparative studies limited to Bayesian networks, these results apply to arbitrary acyclic probabilistic (logic) programs.

Results and Findings

The paper demonstrates that for cycle-free pMCs, the computation of reachability probabilities can be exactly reduced to evaluating an arithmetic circuit.
It illustrates through examples (including Bayesian networks) that the structural properties of the AC (such as determinism and decomposability) correspond to the structural properties of the pMC that allow for efficient computation.
The authors show that probabilistic bisimulation on the MCs derived from ACs yields sub-models containing only relevant states, mirroring the effect of factorization in WMC.
The paper notes that while WMC can be faster for large, non-cyclic models due to direct computational models and variable ordering heuristics, PMC offers native support for cyclic models and linear temporal logic (LTL) queries, which WMC lacks.

Significance and Claims
The paper claims to provide the first direct comparative study between WMC and PMC that goes beyond Bayesian networks to arbitrary acyclic probabilistic programs. The significance lies in the ability to transfer optimization techniques and tractability results between the two domains. Specifically:

Scalability: The mapping suggests that for sparse, acyclic MCs, ACs may offer more compact representations than transition matrices, potentially improving the scalability of model checking.
Parameter Synthesis: The encoding of pMCs and their polynomial transitions as ACs could leverage symbolic computation to accelerate parameter synthesis and mitigate memory consumption for large rational functions.
Heuristic Transfer: The bidirectional mapping facilitates the translation of heuristics, such as variable ordering strategies, between the two fields.

The authors emphasize that their work does not invent new applications but rather clarifies the theoretical underpinnings connecting two distinct communities, enabling the cross-pollination of techniques for probabilistic inference and synthesis. They acknowledge that their mappings are currently restricted to cycle-free models, with future work proposed to extend these concepts to cyclic MCs for finite-horizon reachability.

More like this