Weighted Model Counting

Weighted model counting is the problem of taking a logical formula—typically expressed with Boolean variables and logical connectives—and summing up weights for every assignment that makes the formula true. Each variable or literal carries a numerical weight, often interpreted as a probability, and the count becomes the total weight obtained by multiplying the appropriate weights for each satisfying assignment and then adding those products together. In this way the operation generalises ordinary model counting, which merely tallies how many assignments satisfy the formula, by turning the tally into a weighted sum.

The reason this idea matters is that it bridges crisp logical reasoning with the softer notions of uncertainty that underpin probabilistic inference. By encoding a probabilistic model as a weighted Boolean formula, one can compute exact probabilities for complex queries simply by performing a weighted count. This makes it possible to answer questions about likelihoods, reliabilities, or risks in domains ranging from diagnosis of faulty systems to analysis of Bayesian networks, all without resorting to sampling approximations.

Weighted model counting shows up wherever a system needs both logical structure and quantitative assessment. It is the engine behind many probabilistic programming languages that compile models into Boolean form, it underlies exact inference algorithms for graphical models such as Bayesian networks after they are transformed into conjunctive normal form, and it appears in hardware verification tasks where one wants to know how likely a circuit is to fail given component failure probabilities. In safety‑critical AI research the technique is also used to evaluate risk measures by counting weighted scenarios that violate safety constraints.