Variance Computation for Weighted Model Counting with Knowledge Compilation Approach

Kengo Nakamura; Masaaki Nishino; Norihito Yasuda

arxiv: 2601.03523 · v2 · submitted 2026-01-07 · 💻 cs.AI · cs.DS

Variance Computation for Weighted Model Counting with Knowledge Compilation Approach

Kengo Nakamura , Masaaki Nishino , Norihito Yasuda This is my paper

Pith reviewed 2026-05-16 17:22 UTC · model grok-4.3

classification 💻 cs.AI cs.DS

keywords weighted model countingvariance computationknowledge compilationstructured d-DNNFBayesian networksprobabilistic inferenceuncertainty quantificationd-DNNF

0 comments

The pith

The variance of weighted model counting can be computed in polynomial time when the input is a structured d-DNNF circuit.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives a polynomial-time algorithm for computing the variance of a weighted model count when the underlying representation is a structured d-DNNF. This matters because parameters in probabilistic models are typically learned from data and carry uncertainty, so the variance in the resulting inference value indicates how reliable that value is. The algorithm works by extending the standard bottom-up evaluation of the circuit to also track the second moment needed for variance. The authors prove that the same variance task is intractable for structured DNNFs, general d-DNNFs, and FBDDs, despite weighted model counting itself being tractable on the latter two classes. They illustrate the method by computing variances of marginal probabilities on real-world Bayesian networks.

Core claim

When the input is given as a structured d-DNNF, the variance of the weighted model count can be computed in time polynomial in the size of the circuit. The procedure recursively computes both the expected value and the second moment of the count by exploiting the determinism and decomposability properties of the circuit structure, treating each parameter as a random variable drawn from a known distribution.

What carries the argument

The structured d-DNNF circuit, which permits a linear-time recursive propagation of both the first and second moments of the weighted count through its sum and product nodes.

Load-bearing premise

The input must already be compiled into a structured d-DNNF circuit with the parameter distributions supplied in advance.

What would settle it

A family of polynomial-sized structured d-DNNF circuits on which the variance of the weighted model count requires super-polynomial time would falsify the polynomial-time claim.

read the original abstract

One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian networks. In practical situations on inference tasks, the model's parameters have uncertainty because they are often learned from data, and thus we want to compute the degree of uncertainty in the inference outcome. One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome. Unfortunately, the tractability of computing such a variance is hardly known. Motivated by this, we consider the problem of computing the variance of WMC and investigate this problem's tractability. First, we derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF. Second, we prove the hardness of this problem for structured DNNFs, d-DNNFs, and FBDDs, which is intriguing because the latter two allow polynomial time WMC algorithms. Finally, we show an application that measures the uncertainty in the inference of Bayesian networks. We empirically show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and analyze the impact of the variances of parameters on the variance of the marginal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a poly-time variance algorithm for WMC on structured d-DNNF plus hardness results for d-DNNF and FBDD.

read the letter

This paper delivers a polynomial-time algorithm for computing the variance of weighted model counting on structured d-DNNF circuits, together with hardness proofs for plain d-DNNF and FBDD. The core idea is to extend the existing bottom-up dynamic programming for WMC so that it also tracks the second moment E[WMC²] and then subtracts the square of the mean; independence of the parameters lets the cross terms factor according to the deterministic and structured decomposition, keeping the same asymptotic cost. That is the actual new piece, since tractability of variance had not been established before. The authors also include an application to marginal probabilities in Bayesian networks and some real-world runs that show the numbers are computable in practice. The hardness contrast is interesting because WMC itself stays easy on those weaker structures. The main soft spot is that the abstract gives no explicit recurrence or complexity bound for the second-moment pass, so it is hard to judge the precise degree of the polynomial or any practical overhead without the full derivation. The reductions for hardness are stated but not sketched here, which leaves open whether they are tight or carry large constants. No load-bearing assumptions look circular or invented. This is for people already working with knowledge compilation for probabilistic inference. A reader who compiles models to structured d-DNNF and wants to attach uncertainty estimates will find the algorithm directly usable. It deserves a serious referee because the central claim is specific, the extension follows from the circuit properties in a straightforward way, and the hardness results add a useful boundary. Send it to peer review.

Referee Report

2 major / 3 minor

Summary. The paper claims a polynomial-time algorithm for computing the variance of weighted model counting (WMC) on structured d-DNNF inputs by extending bottom-up dynamic programming to track the second moment, hardness results for variance computation on structured DNNFs, d-DNNFs, and FBDDs (despite poly-time WMC on the latter two), and an empirical application to uncertainty quantification in Bayesian network marginal inference.

Significance. If correct, the result is significant because it identifies a precise structural condition (structured d-DNNF) under which variance of WMC becomes tractable, while remaining hard for closely related representations that support linear-time WMC. This sharpens the boundary between tractable and intractable uncertainty quantification in knowledge compilation and directly supports practical inference tasks where parameters are learned from data. The empirical demonstration on real-world Bayesian networks further strengthens the contribution.

major comments (2)

[§3.2] §3.2, Algorithm 1 and surrounding derivation: the extension of the DP to compute E[WMC²] is asserted to remain polynomial because cross terms factor under determinism and structure, but the manuscript does not explicitly bound the number of terms generated when parameters are independent yet the circuit contains shared subcircuits; a concrete complexity recurrence or size argument is needed to confirm no hidden exponential factor.
[§4] §4, Theorem 3 (hardness for d-DNNFs): the reduction constructs parameter distributions that encode a hard counting problem into the variance; it is unclear whether the hardness persists for arbitrary fixed distributions (e.g., uniform) or only for the specially chosen distributions used in the proof, which would affect the practical interpretation of the negative result.

minor comments (3)

[§3] Notation for the second-moment variable (e.g., V or E[W²]) is introduced inconsistently across §3 and the appendix; standardize and add a short table of symbols.
[§5] Figure 2 (BN marginal variance plot) lacks error bars or confidence intervals on the empirical variance estimates; add them or state the number of Monte-Carlo runs used for comparison.
[Abstract] The abstract states 'polynomial time algorithm' without specifying the degree; the body should state the precise complexity (e.g., O(n) or O(n²)) relative to circuit size.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and positive assessment of the significance of our results on the tractability boundary for variance computation of WMC. We address the two major comments below and will revise the manuscript to incorporate clarifications and additional analysis.

read point-by-point responses

Referee: [§3.2] §3.2, Algorithm 1 and surrounding derivation: the extension of the DP to compute E[WMC²] is asserted to remain polynomial because cross terms factor under determinism and structure, but the manuscript does not explicitly bound the number of terms generated when parameters are independent yet the circuit contains shared subcircuits; a concrete complexity recurrence or size argument is needed to confirm no hidden exponential factor.

Authors: We agree that an explicit complexity argument strengthens the claim. In structured d-DNNF, determinism ensures that children of AND nodes are mutually exclusive in their satisfying assignments, while the structured property guarantees that subcircuits under different branches are variable-disjoint. Consequently, when computing the second moment at an AND node, the cross terms factor into products of first and second moments of the independent subcircuits; no joint distribution over shared variables needs to be tracked. We will add a recurrence: let T(C) be the time to process circuit C. For OR nodes, T(C) = sum T(C_i) + O(1); for AND nodes with independent children, T(C) = sum T(C_i) + O(1) (multiplication of precomputed moments). Memoization over the DAG ensures total time is O(|C|), linear in circuit size, with no exponential term from shared subcircuits. A revised §3.2 will include this recurrence and a short proof sketch. revision: yes
Referee: [§4] §4, Theorem 3 (hardness for d-DNNFs): the reduction constructs parameter distributions that encode a hard counting problem into the variance; it is unclear whether the hardness persists for arbitrary fixed distributions (e.g., uniform) or only for the specially chosen distributions used in the proof, which would affect the practical interpretation of the negative result.

Authors: The reduction in Theorem 3 shows #P-hardness for the general problem in which parameter distributions are part of the input and may be chosen to embed a hard counting instance into the variance expression. We will revise the statement and discussion of Theorem 3 to explicitly note that the result does not claim hardness for every fixed distribution (e.g., uniform probabilities); whether variance remains hard under uniform parameters on d-DNNFs is left open. This clarification preserves the intended interpretation that variance is intractable in the general case even when WMC is tractable, while acknowledging the referee's point on fixed distributions. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation presents a bottom-up dynamic programming procedure on structured d-DNNF that computes both the first and second moments of WMC under independent parameter distributions, then subtracts the square of the mean to obtain variance. This extension preserves the linear-time complexity already known for WMC on the same representation and does not reduce to any fitted parameter, self-definition, or prior self-citation. Hardness proofs for unstructured DNNF, d-DNNF, and FBDD are established separately via reductions that do not invoke the positive result. No load-bearing self-citation, ansatz smuggling, or renaming of known results appears in the central algorithm or complexity claims. The procedure is self-contained given the stated circuit and independence assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract does not introduce or rely on any free parameters, axioms, or invented entities; the contribution is an algorithmic procedure and complexity classification for an existing representation.

pith-pipeline@v0.9.0 · 5523 in / 1069 out tokens · 45976 ms · 2026-05-16T17:22:49.614989+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.