On the Hardness of Approximating Distributions with Tractable Probabilistic Models
Authors: John Leland
YooJung Choi
Venue: NeurIPS 2025 spotlight ()
Keywords: probabilistic circuits
approximation
size lower bounds
Primary area: probabilistic_methods

Abstract: A fundamental challenge in probabilistic modeling is to balance expressivity and inference efficiency. Tractable probabilistic models (TPMs) aim to directly address this tradeoff by imposing constraints that guarantee efficient inference of certain queries while maintaining expressivity. In particular, probabilistic circuits (PCs) provide a unifying framework for many TPMs, by characterizing families of models as circuits satisfying different structural properties. Because the complexity of inference on PCs is a function of the circuit size, understanding the size requirements of different families of PCs is fundamental in mapping the trade-off between tractability and expressive efficiency. However, the study of expressive efficiency of circuits are often concerned with exact representations, which may not align with model learning, where we look to approximate the underlying data distribution closely by some distance measure. Moreover, due to hardness of inference tasks, exactly representing distributions while supporting tractable inference often incurs exponential size blow-ups. In this paper, we consider a natural, yet so far underexplored, question: can we avoid such size blow-up by allowing for some small approximation error? We study approximating distributions with probabilistic circuits with guarantees based on $f$-divergences, and analyze which inference queries remain well-approximated under this framework. We show that approximating an arbitrary distribution with bounded $f$-divergence is NP-hard for any model that can tractably compute marginals. In addition, we prove an exponential size gap for approximation between the class of decomposable PCs and that of decomposable and deterministic PCs.

On the Hardness of Approximating Distributions with Tractable Probabilistic Models
John Leland
YooJung Choi
School of Computing and Augmented Intelligence Arizona State University jslelan 1aasu. edu, yj choichhiiaao aastaaauuu... edu
Abstract
A fundamental challenge probabilistic modeling is to balance expressivity and inference efficiency. Tractable probabilistic models (TPMs) aim to directly address this tradeoff by imposing constraints that guarantee efficient inference of certain queries while maintaining expressivity. In partieular, probabilistic circuits (PCs) provide a unifying framework for many TPMs, by characterizing families of models circuits satisfying different structural properties. Because the complexity of inference on PCs is a function of the circuit size, understanding the size require- ments of different families of PCs is fundamental in mapping the trade-off between tractability and expressive efficiency. However, the study of expressive efficiency of circuits are often concerned with exact representations, which may not align with model learning, where we look to approximate the underlying data distribution closely by some distance measure. Moreover, due to hardness of inference tasks, exactly representing distributions while supporting tractable inference often incurs exponential size blow-ups. this paper, we consider natural, yet so far under- explored. question: can we avoid such size blow-up by allowing for some small approximation error? We study approximating distributions with probabilistic cir- cuits with guarantees based on f-divergencess and analyze which inference queries remain well-approximated under this framework. We show that approximating an arbitrary distribution with bounded f f-divergence is NP-hard for any model that can tractably compute marginals. addition, we prove an exponential size gap for approximation between the class of decomposable PCs and that of decomposable and deterministic PCs.
Introduction
The expressive power of probabilistic and generative models has increased rapidly in recent years:
from Bayesian networks [18, GANs (26), VAES (29), and normalizing flows [35), to diffusion models [27 and transformers 46 have demonstrated remarkable success in capturing complex
distributions. Yet, despite their expressivity, many of these models do not support efficient computa- tion of fundamental probabilistic queries, such as marginals and conditionals, which are critical for inference in domains such as healthcare [40), neuro-symbolic AI [43). environmental science [5].
and algorithmic fairness 9
Tractable probabilistic models such as probabilistic circuits g probabilistic generating circuits [50] determinantal point processes [1) and aade-ss the need for probabilistic queries by balancing expressivity and tractable inference, achieved through enforcing constraints on the models. To more compactly describe the constraints enforced, we focus on probabilistic circuits, which also have extensive literature on the conditions of tractability [8). While these structural constraints enable efficient inference, they introduce tradeoff by potentially affecting the models' ability to compactly represent distributions (i.e., their expressive power). Naturally, there have been many
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

works characterizing the expressive efficiency of different circuit classes [9 ie.. their ability to compactly and exactly represent certain classes of functions or distributions. However, the approximate case-how structural constraints affect the ability to approximately represent distributions, remains comparatively underexplored. This motivates a shift in focus from exact to approximate modeling: representing a distribution approximately within a small distance under some metric.
2
8 48 49 20
This shift raises a fundamental question: does allowing a small approximation error alleviate the exponential separation between circuit classes observed in exact modeling. or does hardness persist even in the approximate setting? Our motivation for this study is two-fold. (1) In learning probabilistic eircuits from finite data, often the goal not necessarily to exactly represent some known distribution but rather to approximate it as closely as possible with PC of reasonable size. Thus, showing that certain distributions cannot be approximated within bounded distance by a compact PC satisfying some structural properties implies that any learning algorithm whose hypothesis space is that family of PCs would fail to learn the distribution with a bounded approximation error. (2) Moreover, probabilistic circuits can also be used to perform inference on other probabilistic models (such as Bayesian networks or probabilistic programs) by compiling them into PCs then running efficient inference the compiled circuits 4
28 16 25 This suggests the following approximate inference scheme: approximately compile a probabilistic model into a PC then run efficient exact inference the upproximately compiled PC. Moreover, if we could bound the distance between the target distribution and approximate model, we can hope to provide guarantees on the approximate inference results as well.
Our main contributions are as follows: (1) we prove that it is NP-hard to approximate distributions within a bounded f-divergence using any model that supports tractable marginals, with proof via a reduction from SAT (Theorem 3.4 and 3.3): (2) we derive an unconditional, exponential separation between decomposable PCs and decomposable & deterministic PCs for approximate modeling (Theorem 4.1): (3) we study the relationship between bounds on divergence measures for (MAP) inference, characterizing when one is or is not sufficient to guarantee the other (Sections 3.1 and 5
approximate modeling and approximation errors for marginal and
2
Preliminaries
Notations We use uppercase letters (X) to denote random variables and lowercase letters (z) to denote assignments to these random variables. Sets of random variables and assignments are denoted using bold letters (X and x). The accepting models (i.c., satisfying assignments) of a Boolcan function : (0, 1)" + {0, 1} over variables is denoted by f-)(1). The number of accepting models of f is referred to as MC()), a shorthand for its model count. Moreover, a Boolean function is the support of distribution P, if P is non-zero only over the models of f.
2.1 Probabilistic Circuits
Probabilistic circuits (PCs) S provide a unifying framework for a wide class of tractable proba- bilistic models, including arithmetic circuits [15), sum-product Networks (37), cutset networks [8] probabilistic sentential decision diagrams [30]. and bounded- graphical models [24
Definition 2.1 (Probabilistic circuits). probabilistic circuit (PC) == (G,0) represents joint probability distribution p(X) over random variables X through a directed acyclic graph (DAG) G parameterized by 9. The DAG is composed of 3 types of nodes: leaf, product @, and sum @ nodes. Every leaf node in G is an input, and every internal node receives inputs from its children in(n). The scope of given node, ((n). is recursively defined function which associates to each unit n a subset of X: for each non-input unit n, Φ(n) = Unein(n) é(c), and the scope of a leaf node is single variable in X. Naturally, the scope of the root node is X. Each node n of a PC then recursively defined as:
((x),
if is leaf if is a & if n a
(x(x) =
Heein(n) (x) Excin(r) (x)
(1)

---

where Bn, E [0, 1] is the parameter associated with the edge connecting nodes n, in G, and Encin(s) n.c 1. In this paper, we assume ((z) leaf node a Boolean indicator function: i...
1[x= = 1 or 1 I = 0j. The distribution represented by the circuit is the output at its root node.
key characteristic of PCs is that imposing certain structural properties on the circuit enables tractable (polytime) computation of various queries. In this paper we focus on two families of PCs: those that are tractable for marginal inference and for maximmm--4-posterionn (MAP) inference.
The class of marginal queries of a joint distribution p( p(X) over variables X refers the set of functions that can compute p(y) for some assignment y for Y C X. Marginalizatiin is a fundamental statistical operation which enables reasoning about subsets of variables, essential for tasks such as decision making, learning, and predicting under uncertainty. While marginal inference # P-hhard in general
39 [3]. the family of PCs satisfying the following structural conditions admit tractable marginal inference specifically in linear time in the size of the circuit [17].
Definition 2.2 (Smoothness and decomposabilityy. A sum unit smooth if its children have identical
scopes: ((c) = ((n), Vc E in(n). A product unit is decomposable if its children have disjoint scopes: (Cc:) n ((e)) = 0, Vc, A Cj E in(n). PC is smooth and decomposable iff every sum unit is smooth and every product unit is decomposable.
In addition, we are often interested in finding the most likely assignments given some observations. The class of maximum- a- posteriooi (MAP (MAP[qqericc queries of a joint distribution p(X) is the set of queries that compute maxgeval(Q) Q) p(q. e) where val E) is an assignment to some subset E X and Q = X Again, MAP inference is NP-hard in general [42] but can be performed tractably for certain class of PCs. In particular, smoothness and decomposability are no longer sufficient, and we must enforce an additional condition.
Definition 2.3 (Determinism), sum node is deterministic if. for any fully- inlly-instantiated input, the output of at most one of its children is nonzero. In other words, the supports of its children are mutually disjoint. A PC is deterministic iff all of its sum nodes are deterministic.
Figure 1: A smooth, decomposable, and deterministic PC (weights shown only for the root for conciseness).
Figure I depicts an example PC that is smooth, decomposable, and deterministic, which thus supports tractable marginal as well as MAP inference
Logical circuits Probabilistic circuits are closely related to logical circuits in the knowledge compilation literature 19.. Logical circuits encode Boolean functions directed acyclic graphs consisting of AND (A) and OR (V) gates with positive and negative literals as leaf nodes. We also characterize different families of logical circuits based on their structural properties: e.g., decomposable negation normal forms (DNNFs) and deterministic decomposable negation normal forms (d-DNNFs) E There is a rich literature studying different logical circuit families in terms of their tractability for inference and operations, as well as their relative succinctness (expressive efficiency) for both exact and approximate compilation, which we will leverage for our hardness results and size lower bounds on probabilistic circuits.
2.2 Measures of Difference between Probability Distributions
To study the hardness of approximating probability distributions, we first need to be able to measure how "good" approximation is. In particular, we focus the class of f-divergences.
'Soeetmess also called the most prohable explanation (MPE).
For PCs over Boolean variables, a weaker form of decomposability called consistency By g actually
suffices instead of decomposability for both tractable marginal and MAP inference. In this paper. we still focus classes of PCss that are decomposable as they the most commonly considered, both learning targets well as for characterizing expressive efficiency.
"Structural conditions are same as before (Detinitions 2.2 and 2.3 except that smoothness and determinism apply to OR gates and decomposability to AND gates.
3

---

Definition 2.4 (f -diieergence [36]), J Let f: (0, 00) + R be a convex function with f(1) = 0. and P. Q be two probability distributions over set of Boolean variables X. If Q > 0 wherever P > the f-divergence between P and Q is defined as Dy Q) = Σx Q()) Q(x)
P(x)).
Commonly used /-divergences include the Kullback- Leibler divergence, x² xi-divere,,ce, and total variation distance. The total variation distance is especially relevant to our results.
Definition 2.5 (Total variation distance). The total variation distance (TVD) between two prob- ability distributions P and Q over set of n Boolean variables X is defined DTv(PllQ)
ExEx P(x)) (x or equivalently Drv(PilQ) = maxsc(o.13" [P(S) Q(S)
We introduce the following notion to describe probabilistic models that approximate distributions within some bounded distance.
Definition 2.6 (c- (---AAproximatioon. Let P, Q be two probability distributions and D be distance measure between distributions. We say that Q is an c-D-approximator of P ((PI()) < c for some 0.
For instance, we refer to a probabilistic circuit Q that approximates our target distribution P such that Div(P)lQ) of the total variation distance, due to its nice properties as a distance metric. To extend our results to other f-divergences, utilize the following class, which provides an upper bound the total variation distance.
c-Div-approximmator. The majority of our results are derived using properties
Definition 2.7 (k-convex f-divergence 34 ). A R (o valued function f on a convex set C is ty) I (1 (f=t)(())+tf(())
k-convex æ. y E a E [0, 1] implies When / is twice differentiable, this is equivalent to (*)()) 2 k for all x E K. In the case that k 0
kt(1 t) (x (w-y)²
2
this reduces to the normal notion of convexity. An f-divergence Dj is k-convex over an interval K for k 2 0 if the function is k-convex K.
We provide a table in Appendix A.1 summarizing which f-divergence measures are k-convex and for which value of Throughout this paper, we express approximation bounds using k-convex f- divergences as they naturally encapsulate bounds on many common distance measures. For instance, for any k-convex f-divergence between P and Q, we have that DTv(P)) < (Pi /k (34. As we will see later, the bounds on the TV distance can naturally be connected to guarantees for approximation inference. For KL-divergence, which is the most commonly used objective for learning
probabilistic models, we can use Pinsker's inequality
45 to obtain Drv(PlIQ) < <v (PIIQ).
3 Approximate Modeling with Tractable Marginals is NP-hard
Most works characterizing the expressive efficiency of diffcrent circuit classes have been concerned with exact representations (9 2
49 20 While Chubarian and Turán [12] and De Colnet and Mengel 21 have recently studied the ability (and hardness) of logical circuit classes to compactly approximate Boolean functions, to the best of our knowledge, our results are the first to show hardness of compactly approximating probability distributions using different families of tractable PCs.
As discussed previously, the complexity of approximately modeling distributions with PCs is valuable for understanding: (1) potential limitations in the hypothesis space of PC learning algorithms, and (2) the feasibility of approximate inference with guarantees through approximate compilation. This section aims to answer this focusing on probabilistic models that are tractable for marginal queries. We first show that form of approximate marginal inference using this scheme requires non-trive non-trivial bound on the total variation distance between the target distribution and the approximate model, and next prove that finding such an approximator is NP-
3.1 Relative Approximation of Marginals
We consider relative approximation of marginal queries. Let P(X) be probability distribution over a set of variables X. Then we say another distribution Q(X) is a relative approximator of
Also called multiplicative approximation or approximation within factor.

---

marginals of P w.r.t. 0 S & T
PLY <1+c for every assignment y to subset of variables QV)
Y [ X. Relative approximation is often considered for approximate inference of graphical models and the closely related approximate (weighted) model counting [23 3 We first show that relative approximation for all marginal queries implies non-trivially bounded total variation distance.
Theorem 3.1 (Relative approximation implies bounded Dtv(PIIQ)) Let 0 and P, P.Q.A be two probability distributions over X. If Q is a relative approximator of marginals for P, then
(r)( 5
Proof. As Q is relative approximator of P. for all assignment we have that Itt S P(x)
1
Q(x) I 1 + c which implies IP(x) - Q(x)] S cmin(P(x), Q(x)). Therefore, Drv(PIIQ)
2x Pxx) Q(x) s Ex (amimm((xx))) Q(x)) S
In other words, (TV(P)))) S 2/2 is necessary condition for Q to be a relative approximator of marginals of P w.r.t. e. However, it is still not a sufficient condition as shown below.
Proposition 3.2 (Bounded (Tv(P) does not imply relative approximation). There exists a family of distributions P that have (-Dry-approimattoss yet for any such approximator Q, the relative approximation error of marginals between P and Q can be arbitrarily large.
We prove the above proposition by explicitly constructing family of distributions Q such that every an a-Dp-aaproximmator for any arbitrary arbitrarily large for some x. See Appendix A.3.1 for the full construction.
Q E
and distribution P yet P(x)/Q(xx) can be
is known that relative approximation of marginals is NP-hard for Bayesian networks [4] Thus, it immediately follows that approximately representing arbitrary distributions using polynomall sized PCs tractable for marginals (e.g., decomposable PCs) such that the PC is relative approximator of all marginals also NP-hard. However, approximating all marginal queries is quite a strong condition, and may still want closely approximate distributions they could be useful in approximating some marginal queries. In particular, because approximating a distribution P with bounded TV distance is necessary but not sufficient condition for the NP-hard problem of relative approximation of marginals, this raises the question whether it is still possible to efficiently approximate the distribution / with compact PC Q that is tractable for marginals. Unfortunately, we next answer this in the negative.
3.2 Hardness of Approximating Distributions using Tractable Models for Marginals
We consider approximating potentially unnormalized distributions, which can be considered generalization of probability distributions by omission of the normalizing constant.
Definition 3.3 (Unnormalized Distributions). Any (unnormalized) distribution P : val(X) - R
must satisfy the following: (1) P(x) 2 0 for any x: (2) The normalization constant Z =xExx P(x)
is well-defined and finite.
See from this definition that an unnormalized distribution can easily be converted to probability distribution P Z is computable in polynomial time: P(x) = P2x)/Z Unnormalized distributions relevant to the goal of tractable approximation, many probabilistic models that we may want to approximate -iciimatteiiinuiingg factor graphs [32] and energy- based models [44 represent unnormalized distributions.
Theorem 3.4 (Hardness of Dy-approximation) Given (potentially unnormalized) probability distribution P' and a k-convex f-divergence D,, for any < }. it is NP-hard to represent the ke--D, ae--D-aaproximmttin of its normalized distribution P as a model that can tractably compute marginals.
Proof. We will prove the above using reduction from SAT. Let P be Boolean formula over X (X1,...; Xn) and
}. See that P satisfies all requirements to be considered an unnormalized
"In fact, there also exists no randomized polynomial time algorithm for relative approximation of marginals unless RP- = NP 14.
5

---

probability distribution. We then define new Boolean formula f over X and an auxiliary variable Clearly P' has MC(P) + models. Let us now define uniform distribution P over these models of P (i.e., by normalizing P*). Suppose that we can efficiently obtain a probability distribution Q such that (P[l)) < ke. which in turn implies that Drv(P])Q) < c. From the definition of total variation distance, |P(YY = 1) Q(Y = 1)l < e < 7.
Y: P' =Y P) V-Y X1 A...A X,).
By construction, if P is unsatisfiable, there is no satisfying model of f such that Y = 1, and thus P(Y = 1) = 0 and Q(Y 1) < 1 Otherwise, if P is satisfiable, then there are MC(P) () many
MC(P) satisfying model of pr setting Y 1, and thus we have MC(P) 2 1 and P(Y 1) 1+MO(P) implying
MC(P)
1
Q(Y = 1 MC(P)
Therefore, P is satisfiable if and only if Q(Y 1) 2 1 In other words, decide SAT if we efficiently compute paprroxappooiiiitiin as model that supports tractable marginals. I7
The following corollary immediately follows from the above proof.
Corollary 3.5. Given (potentially unnormalized) probability distribution for 0 < <E< < is NP-hard to represent the e- e-Dry- Dpy-ppproximation of its normalized distribution as a model that can tractably compute marginals.
Thus, the class of polynomial-sine sized probabilistic models supporting tractable marginals cannot contain 2 -aprrxiaipossssasoo for all distributions unless P = NP. This includes decomposable PCs R. sum of squares circuits [11, probabilistic generating circuits [50], determinantal point processes (.) Inception PCs 47.. and positive unital circuits (2 Furthermore, by Pinsker's inequality this suggests that there exists distributions for which obtaining a decomposable PC with bounded KL-divergence
1/8 is NP-hard. While Martens and Medabalimi (33) previously showed a related result that there exists a function for which a sequence of decomposable PCs converging to approximate the function arbitrarily well requires an exponential size, our result applies more broadly to any class of models supporting tractable marginals as well as allowing for a bounded but non-vanishing approximation error. Thus, is difficult not only to exactly represent functions or distributions as compact decomposable PCs, but also to approximate within some small distance. Consequently, this presents major challenge to the idea of using approximate compilation of PCs for approximate inference if the desired error tolerance is sufficiently small.
4 Large Deterministic & Decomposable PCs for Approximate Modeling
Continuing our charactcrization of the approximation power of PCs, we now turn to the family of deterministic and decomposable PCs. We take inspiration from related results for logical circuits. In particular, Bova et al. 2 proved an exponential separation between DNNFs and d-DNNFs: i.e., there is family of Boolean functions that can be compactly represented by decomposable circuits but requires exponentially sized deterministic and decomposable circuits. Furthermore, De Colnet and Mengel [2]] showed that there exist functions that require exponential size to approximate with d-DNNFs under two notions of approximation for Boolean functions.
Nevertheless, this does not immediately imply the same separation for probabilistic circuits due to two key reasons: (I) approximation for PCs is measured in terms of divergences between distributions rather than some probabilistic eтror between Boolcan functions, and (2) our approximator sent arbitrary distributions instead of being limited to a Boolean function (or a uniform distribution over it). This section presents our proof of exponential separation between the class of decomposable PCs and that of deterministic and decomposable ones, by constructing a family of distributions that be represented by compact decomposable PCs, but any PC that is also deterministic and approximates within a bounded TV distance must have an exponential size.
repre-
We consider the Sauerhoff function 41 which was used to show the separation between DNNFs and d-DNNFs for exact compilation 1 if and only if the sum of its inputs is divisible by 3. The Sauerhoff function is defined S,
[2] Let Gn {0, 1)m - {0,1) be function evaluating to

---

{0.1) + {0, 1 over the n x n matrix X = (Itz)ısi, such that (x) = (x( (xx), where Ri: Cn 10, + {0, 1 are defined as (X) Dim In (Zi, 2i,2 ... Fi,a) and (x() R,,(X (x²). Here, @ represents addition modulo 2.
There exists a DNNF of size (nn²) that exactly represents the Sauerhoff function Sn, constructed as disjunction of two compact ordered binary decision diagrams (OBDDs) a more restrictive kind of deterministic and decomposable
that represent R. and Cn. respectively (2 Proposition 7]. We then define our family of target distributions P, follows: let C. be DNNF for S,, with size ( then P, is a decomposable PC obtained by replacing the literals of C, with corresponding indicator functions, A with @ and V with nodes with uniform parameters, followed by smoothing the circuit o Note that Pa outputs a positive value on an input x if and only if (x = 1. We will show that deterministic and decomposable PC approximating Pa requires exponential size.
Theorem 4.1 (Exponential-sizz deterministic PC). A deterministic and decomposable PC that is C-Dry-upproximatoo of P.. for some S To 22(1 /Poly(n²)) has size 20(n)
We will prove the above by first showing that approximation of Pn. with a deterministic and decom- posable PC implies a form of weak approximation [21] of S,, with d-DNNF of the same size, and next proving that such d-DNNF must be exponentially large.
Definition 4.2 (Weak approximation (2T). A Boolean formula g is a weak e-approximation of another Boolean formula if MC(J A mg) + MC(-f g) S c-2".
Proposition 4.3 (Bounded DTv implies weak approximation). Let 0 S. SE< &/ and P be uniform distribution whose support is given by a Boolean function f. Suppose that Q is a deterministic and decomposable PC representing an e- ayyyappproimmator of P. Then there exists d-DNNF g which has size polynomial in the size of Q that represents a appra-aaproximator of f.
Proof. Suppose that Pis uniform distribution over the support given by a Boolean function f. and Q probability distribution such that DTv(PIQ) < <<> 8. Then, can construct (unnormalized) deterministic and decomposable PC Q' by pruning the edges of Q such that any assignment is eliminated from the resulting support of Q' if and only if [(x) < Jn+T- We call this support g. We provide this pruning algorithm, which relies on determinism as key property, in Appendix AA.32 Clearly, the size of Q' is at most the size of Q. We will now briefly summarize how this pruning scheme induces a weak approximation and refer to Appendix A...3 for the full derivation. Intuitively, we know that the support of Q must cover most of the support of P. as P is a uniform distribution and D Drv(Pl(Q) is bounded. While it is possible for the support of Q to be much larger than the support of P. then the probability assigned by Q to assignments outside of the support of P must also be very small to maintain small TV distance. Thus, pruning away these assignments with small probability allows us to retrieve Q' whose support has only a small number with models of J. More formally, we know that by our pruning scheme, Q(x) 2 2 on g and Q(x) T on -g. Using this fact, we can lower bound our original total variation distance by (MC(JA /)/2n+1 + (g)) ///gg///++)))))))))//))) 12=+1), which implies that MC( (0)-gg-MMCMC//
conrrapplgpinng assignments
< 4e 2". Thus, y is 46- de-weak-apppnn weak-approoimator of f. and we can represent it as polynomially sized d-DNNF by taking the deterministic and decomposable PC Q' and converting it to a logical circuit.
Proposition 4.4 (d-DNNF approximating Sn has exponential size). A d-DNNF representing (1 - 2(1 (((1/Plly(n)) ()) -weak--pproximaaiii of Sn has size 20(())
Proof. Let C be a d-DNNF such that it is a (1 MLL/Polyn >-aak-approxximatoon of Sn.- Sauerhoff [4T] showed that any "two-sided" rectangle approximation (which matches the notion of weak approximation) of S. within showed that a d-DNNF C computing function f is a balanced rectangle partition of I with size at most IC. Thus, C must have size 20))
221 (1))))ly(n2)) must have size 28(x), Bova al. (2 further
We are now ready to prove our main result about exponential size lower bound on deterministic and decomposable PCs as approximators.
'Smoothing a decomposable PC takes polynomial (worst-case quadratic) time g "ee Appendix A.2 for details rectangle partitions.
7

---

Suppose that we have deterministic and decomposable PC Q that is an --Dvvapproximatoo of Pn. where = ( Q2L1 Patl/Poly(nn) ()²))) Consider then the uniform distri- bution U over Sn Then, by the triangle inequality, (Tv(U]lQ) < PTv(U]lPP.) + Prv(PallQ) < (r)(U))),,) + c. By Bova et al. [ Proposition 7], we know that the DNNF constructed to repre- sent the Sauerhoff function is a disjunction of two OBDDs, which respectively represent R,, Cn- As each OBDD can easily be translated to a d-DNNF with a polynomial size increase, their PC counterparts (OR to + and AND to &) will still represent the same Boolean functions [6]. Thus, the non-deterministic PC representing Pn based on this construction only has one non- deterministic sum node at the root, and can return values at most 2. This allows us to see that DTv(U]|P) < 18
Proof of Theorem 4.7
| < 17 where 1f = (1-1/V2)242 based on the fact that [S,1 > (1- 3)2" for 3 1/v2, derived from the low O-density property of Sn under the uniform distribution [41]. Therefore, (Tv(U]l < e + 1). Since, the ((1/Poly(r' Poly(n²)) term in e subsumes (o1/))ly((n)). Next, construct d-DNNF C' from Q by replacing indicators with literals, + with V, and with A. By Proposition 4.3 C' is
[8,1+T
v, we can more simply say DTv(U]lQ) <
(1 - Q11 (oll(pool)()))))e>)))) weeak-aprroximation of S,,. Thus, by Proposition 4.4 |Q| = C*I = - O
To sum up, we constructed a decomposable PC Pn that has size O( such that any deterministic and decomposable PC approximating it has size O(29(m)), thereby showing an unconditional ex- ponential gap for approximation between decomposable PCs and deterministic and decomposable PCs. This result highlights fundamental limitation: approximate modeling does not grant us an additional flexibility to overcome exponential expressive efficiency gaps. Moreover, we next show that approximate modeling, even when somehow obtained, is unfortunately still not enough to use PCs for efficient approximate inference with guarantees in general.
Relationship between Approximate Modeling and Inference
We have shown that even we allow some approximation error, it is hard to efficiently approximate distributions using tractable probabilistic circuits. Given that approximate modeling remains a hard task, one would hope that computing the approximators with bounded distance would allow us to approximate hard inference queries with bounded error. In this section, we study the relation- ship between approximate modeling and inference, in particular focusing on relative and absolute approximations of marginal, conditional, and maximum- - posteriori (MAP) queries.
prsstrinn---osstriiori
In Section 3.1 we showed that bounded total variation distance
necessary but not sufficient condition for relative approximation of marginals. We now consider slightly weaker notion of approximation called absolute approximation. Let P(X) be a probability distribution over a set of variables X. Then we say another distribution Q(X) is an absolute approximator of marginals of P with respect to S 6 S 1 if: [P(y) - Q(y) S for every assignment y to a subset of variables Y C X. We show that any model that is a ke -ap-Da-aproxiimator of P must also be an absolute approximator of marginals of with respect to e.
Theorem 5.1 (Bounded D, implics absolute approximation of marginals). Given two distributions P and Q over a set of variables X and 0 S e if < ke then for all assignments y to subset Y C X, we have [P(y) Q(y) <.
Proof. Note that while the absolute error of marginals is symmetric between P and Q. f-divergence between P and Q, such as the KL.-divergence, is not symmetric. Therefore, we utilize the implications Moreover, given that the total variation
derived in 344 that QP < ke² then Prv(PllQ) distance is an f-divergence, we know that by the monotonicity property (36) (P()), Q(Y)) <
(P Q()) for any Y C X. By definition, maxsc(0.1)" P(S) Q(S) < and thus Vy Py()) - Q(y) <c
From the above proof, we also immediately derive the following corollary.
Corollary 5.2 (Bounded DTv implies absolute approximation of marginals). Given two distributions
P and Q over a set of variables X and 0 S e < 1, if (Pv(()))) < e, then for all assignments y to Y C X. we have PPy)) - Q(x) <
8

---

Since marginals are tractable for decomposable PCs, approximating a target distribution with bounded f-divergence using a decomposable PC implies that marginals can be approximated in polynomial- time with bounded absolute error. This aligns with Dagum and Luby [14), who showed that there exists a randomized polynomial-time algorithm for the absolute approximation of marginals for Bayesian networks.
We next study approximate inference implications for MAP inference. Let P(X) be probability distribution over a set of variables X. We say another distribution (XX is an absolute approximator of the maximun-a-PP poottenrroooo of P with respect to 0 S c < if: for every assignment e (called the evidence) to subset E S X. maxy P(y, e) - maxy Q e)l S é where Y = X E. We next show that - - j-approximatoors are also absolute approximators of MAP with respect t.
Theorem 5.3 (Bounded D implies absolute approximation of MAP). Given two distributions P and Q over set of variables X and 0 S E S L, if ke? then for every assignment e to subset E S X, we have |maxyeY Ply.c) - maxyey Q e)] < where Y -XX,B.
Proof. Analogous to Theorem 5.1 we utilize the fact that if we have Dj (P(()) < ke?, we know DTv(P (P))) <
e, we have maxx [2(x) - Q(x) < E by definition. Then for all x. ((x) - < P(x) < ((x) + w.l.ogg. suppose max P(x) > max (xx). Then
Using (Tv(P (T))
|max P(x) max Q(x) (max Q(x) c) max Q(x) = Thus, this holds for all x, we can extend this to |maxyey P(y,e) e) m Q(y.e) < for every assignment to subset E C X and Y X E. Thus, approximating with bounded f f-divergence by a deterministic and decomposable PC implies polynomial minomial--iimeeeee approximation of MAP with bounded absolute error.
Again, we can restrict this to the special case of total variation distance via the above.
Corollary 5.4 (Bounded DTv implies absolute approximation of MAP). Given two distributions P and Q over a set of variables X and 0 I 6 S 1, if PPv((Pl1g < then for every assignment e to a subset C X, we have ImaxyeY P(y e) maxyeY Q e)l E where Y E.
Thus, a deterministic and decomposable PC that is an -ppr--appoox of a distribution P woould imply that exact MAP inference w.r.t. this PC grants us tractable approximate MAP inference w.r.t. the original distribution P. However, the converse does not hold: PC that can be used for approximate MAP inference is not necessarily a good approximation of the full distribution.
Counterexample 1. Consider a family of distributions P(x) such that max, P(x) < c. Then,
construct a distribution P' P'(X, Z) such that P(x, Z = 1) P(x) and P(x, Z = 0) = 0. Similarly,
let Q(X X, Z) be such that Q(x, Z 0) pxx) and Q(x, 7 - 1) 0. Thus, for any assignment
to E C X U [2). |maxy P(y,e, e) - maxy Q e)l < P(x) < so Q is an absolute approximator
of the MAP of P. However, DTv (PIlQ)
P and Q have disjoint supports.
Lastly, not all tractable queries for PCs are guaranteed to admit absolute approximation even under this framework of approximate modeling with bounded distance.
Theorem 5.5 (Bounded Drv does not imply absolute approx. of conditionals/conditiona MAP).
There exists a family of distributions P that have e- e-Drv- approximators, yet the absolute approxima- tion for conditional marginals and conditional MAP can be arbitrarily large.
Proof. Let P be a probability distribution over X such that P(c) < 1/k for some assign- ment E C X. Let Y X E. We construct another distribution Q such that: Q(y",e e) = ((y")) + keP(e) where y* maximizes P(yle); )(y,,e) = P(y) Note that Q is normalized by construction. Then the total variation distance between P and Q is: DTv(P)(Q) {(P((y e) Q(y", .e) + (P - ((yı,e))) = keP(e) < e. On the other hand, the absolute approximation error of conditional MAP can grow arbitrarily by increasing k: Imaxy P(yle) max, Q(yle)] Pey P(y le) ke| ke. Note that the same also holds for absolute approximation of conditionals.
keP(() for another assignment yı; and Q(x) = P(x) for all other assignments
Moreover, because relative approximation of conditionals imply their absolute approximation 14, bounded DTv also does not imply relative approximation of conditionals. It is well known that absolute and relative approximation of conditionals NP-hard in Bayesian networks [14]. Even though approximate modeling with bounded DTv is also an NP- task, solving it still does not

---

guarantee a polynomial -imei algorithm for approximating conditional queries. This highlights key limitation: while tractability queries is guaranteed by the structural properties of our learned PCs, some queries do not yield "good" approximations for all assignments even after learning within bounded distance.
Conclusion and Discussions
We established the hardness of approximating distributions with tractable probabilistic models such that the f-divergence small. First, we showed that this task NP-hard for any model supporting tractable marginal inference, including decomposable PCs. Then, we used the Sauerhoff function to demonstrate an exponential size gap between the class of decomposable PCs and that of deterministic and decomposable PCs when allowing for a bounded approximation error. This proves that the expressive efficiency gap that exists in exact compilation persists even under the relaxed approximation conditions. Finally, we characterized which queries remain well-approximated under the framework of approximate compilation.
These results highlight key challenges in learning compact and expressive PCs while maintaining tractable inference. light of this, we ask: can a polynomial- time algorithm enable learning an e-approximator for broad family of distributions with a more relaxed e? While this is trivial when total variation is near investigating whether structurally constrained PCs remain expressive under weaker approximation could reveal key limits of learnability. Furthermore, does there exist modeling conditions that are sufficient to guarantee relative approximation of various queries? Lastly, we see this work as a first step to encourage further theoretical studies on approximate modeling and inference with guarantees using tractable models. In this paper, we focused on PCs that are tractable for marginal and MAP queries, but there are large classes of tractable models whose efficient approximation power remain largely unknown.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their feedback towards improving this paper. We also thank Adrian Ciotinga for helpful feedback and discussion. This work was supported in part by the AFOSR grant FA9550-25-1-0320.
References
[1] Alexei Borodin. Determinantal point processes, arXiv preprint arXiv:0911.1155, 2009.
[2] Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. Knowledge compilation meets communication complexity. In IJCAI, volume 16, pages 1008-1014, 2016.
[3] Supratik Chakraborty, Kuldeep Meel, Rakesh Mistry, and Moshe Vardi. Approximate proba- bilistic inference via word-level counting. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
[4] Hei Chan and Adnan Darwiche. Reasoning about bayesian network classifiers. Proceedings of the Nineteenth conference Uncertainty in Artificial Intelligence, pages 107-115, 2002.
[5] Felicia Chiang, Peter Greve, Omid Mazdiyasni, Yoshihide Wada, and Amir AghaKouchak. multivariate conditional probability ratio framework for the detection and attribution of compound climate extremes. Geophysical Research Letters, (1115)))2222110094366 2021.
[6] Arthur Choi and Adnan Darwiche. On relaxing determinism in arithmetic circuits. In Interna- tional Conference on Machine Learning, pages 825-833. PMLR, 2017.
[7] YooJung Choi, Adnan Darwiche, and Guy Van den Broeck. Optimal feature selection for decision robustness in bayesian networks. Proceedings of the 26th International Joint Conference Artificial Intelligence (IJCAI), August 2017.
[8] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A uni- fying framework for tractable probabilistic models. UCLA. URL: hup://starai. es. ucla edu/papers/ProbCir220 pdf. page 6, 2020.
10

---

[9] YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group faireess by probabilistic modeling with latent fair decisions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, Feb 2021.
[10] YooJung Choi, Tal Friedman, and Guy Van den Broeck. Solving marginal map exactly by probabilistic circuit transformations. In International Conference on Artificial Intelligence and Statistics, pages 10196-10208. PMLR, 2022.
[11] C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions Information Theory, 14(3):462-455 467, 1968. doi: 10.1109/TIT.196.. 1054142.
[12] Karine Chubarian and György Turán. Interpretability of bayesian network classifiers: Obdd approximation and polynomial threshold functions. In ISAIM, 2020.
[13] Gregory F Cooper. The computational complexity of probabilistic inference using bayesian belief networks. Artificial intelligence, 42(2-3):393-444 405, 1990.
[14] Paul Dagum and Michael Luby. Approximating probabilistic inference in bayesian belief networks is np-hard. Artificial intelligence, 60(1):141-153, 1993.
[15] Adnan Darwiche. logical approach to factoring belief networks. KR, 2:409-420, 2002.
[16] Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50(3):280-33) 2003.
[17] Adnan Darwiche. A differential approach to inference in bayesian networks. J. I.A.M, 50 (3):280-305, May 2003. ISSN 0004-5411, doi: 10.1145766556..655570.. URL https
//doi. 1145/765568 765570
[18] Adnan Darwiche. Bayesian networks. Foundations of Artificial Intelligence, 3:467-509, 2008.
[19] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229 264, 2002.
[20] Alexis de Colnet and Stefan Mengel. A compilation of succinctness. results for arithmetic circuits. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 18, pages 205-215, 2021.
[21] Alexis De Colnet and Stefan Mengel. Lower bounds for approximate knowledge compilation. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence pages 1834-1840, 2021.
[22] Pedro Zuidberg Dos Martires. A quantum information theoretic approach to tractable proba- bilistic models. The 4 Conference on Uncertainty Artificial Intelligence.
[23] Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Anytime weighted model counting with approximation guarantees for probabilistic inference. In 30th International Conference on Principles and Practice of Constraint Progranming (CP 2024), pages 10-1, Schloss Dagstuhl- Leibniz-Zentrun für Informatik. 2024.
[24] Gal Elidan and Stephen Gould. Learning bounded treewidth bayesian networks. Advances in neural information processing systems, 21, 2008
[25] Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. Inference and learning in probabilistic logic programs using weighted boolean formulas. Theory and Practice of Logic Programming. 15(3):358-4p) 401, 2015.
[26] Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Commun. ACM, 63( 13:9-14144444, October 2020. ISSN 0001-0782, doi: 10.1 10.1145/342262.. URL hhtpps
//doi org 10. /3442622
11

---

[27] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
[28] Steven Holtzen, Guy Van den Broeck, and Todd Millstein. Scaling exact inference for discrete probabilistic programs. Proceedings of the ACM on Programming Languages, 4(0OPSLA): 1-31, 2020.
[29] Diederik P Kingma and Max Welling. Auto-encoding variational bayes, 2022. URL https //axxiv.org/
www.orgg////////e/e////o//eeeeee abs/ 1312. 6114
[30] Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In KR, 2014.
[31] Lorenzo Loconte, Stefan Mengel, and Antonio Vergari. Sum of squares circuits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 19077-19085, 2025.
[32] H.-A. Loeliger. An introduction to factor graphs. IEEE Signal Processing Magazine, 21(1):
28 41, 2004. doi: 10.1 10.1109//SP.2004112200 1267047.
[33] James Martens and Venkatesh Medabalimi. On the expressive efficiency of sum product networks, arXiv preprint 111 2014.
[34] James Melbourne. Strongly convex divergences. Entropy, 12:11)):337 2020.
[35] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan, Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57):1-66 2021.
[36] Yury Polyanskiy. Lecture notes on f-divergence, 2014. URL https://poople..ieee mit http://ypommagaaaaaaaaaaaeeaeeae Batpaggg//aat//N// www.iddffviipeie pdf Accessed: 2025-02-10.
[37] Hoifung Poon and Pedro Domingos. Sum-product networks: A deep architecture. In
2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pages 689-690, IEEE, 2011.
[38] Tahrima Rahman, Prasanna Kothalkar, and Vibhav Gogate. Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDI) 2014, Nancy, France, September 15-19, 2014. Proceedings, Part II 14, pages 630-645. Springer, 2014.
[39] Dan Roth. On the hardness of approximate reasoning. Artificial intelligence, 82(1-2):273-30. 1996.
[40] Paul Sanfilippo, Alex W Hewitt, and David A Mackey. The importance of conditional probability in diagnostic reasoning and clinical decision making: A primer for the eye care practitioner. Ophthalmic epidemiology, 24(2):81-89, 2017.
[41] Martin Sauerhoff. Approximation of boolean functions by combinatorial rectangles. Theoretical computer science, 301((-3):45-77, 2003.
[42] Solomon Eyal Shimony. Finding maps for belief networks is np-hard. Artificial intelligence, 68 (2):399-410, 1994.
[43] Arseny Skryagin, Daniel Ochs, Devendra Singh Dhami, and Kristian Kersting. Scalable neural- probabilistic answer programming. J. Artif. Int. Res., 78, January 2024. ISSN 1076-9757. doi: 10.1613/jair..11 150277.. URL httt/:://// htt::///oo..or//0/0/ 10111113aaaaa /ja///jjrr../ 1. 15027
[44] Yee Whye Teh, Max Welling, Simon Osindero, and Geoffrey E Hinton. for sparse overcomplete representations. Journal of Machine Learning Research, 4(Dec): 1235-1260. 2003.
Energy-based models
[45] Alexandre Tsybakov. Introduction to Nomparametric Estimation. Springer series in statistics. Springer, 2009. doi: 10.7944//13794.
12

---

[46] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[47] Benjie Wang and Guy Van den Broeck. On the relationship between monotone and squared prob- abilistic circuits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 21026-211 22034, 2025.
[48] Lang Yin and Han Zhao. On the expressive power of tree-structured probabilistic circuits. In The Thirty-eighuh Annual Conference on Neural Information Processing Systems, 2024. URL
[49] Honghua Zhang, Steven Holtzen, and Guy Broeck. On the relationship between probabilistic eir- cuits and determinantal point processes. In Conference on Uncertainty in Artificial Intelligence, pages 1188 1197. PMLR, 2020.
[50] Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating eircuits. In International Conference Machine Learning, pages 12447-12457. PMLR, 2021.
13

---

A Appendix
A.1 k--oovex /-dieereeees
Table 1: Examples of k-convex /divergeences
34
Divergence
f
k
Domain
Kullback-Leible
flo t
(0, MM]
37
Total variation
|t-1|
0
(0, o0)
Pearson's x2
1)2
2
(0, oo)
Squared Hellinger
2(1 Vt)
M $ #/2
(0, M]
Reverse KI
log t
(0, M]
M
Vincze- Le Cam
(t-1)²
8
(0,
111
Jensen- Shannon
(t + 1) log #+I + logg
(M]
M[(M+1]]
Neyman's x²
1-1
2
(0, M]
AZ3
Sason's
log(s +)(s+t))
log(s 1)(s+1))
2 log
M)
[M, o0), 8 > e 3/2
1to 1-t 3-
a-divergence
M "
[M,,,),
>>> 3
I-a7
(0, <
A.2 Rectangle Partitions
Rectangle partitions are a powerful tool used communication complexity to analyze the size of communication protocols. The main idea is to represent the communication protocol for a function f: (0, {0, 1} into 2n x matrix My where M x, y] f'(x, y), then partition M into set of monochromatic rectangles which cover the input space of all possible pairs. Here, monochromatic means that a given rectangle covers only the outputs equal to 0 or 1, but not both.This allows to derive lower bounds on the communication complexity of function f. Furthermore, Bova et al. 2 showed the relation between rectangle covers and partitions to the size of DNNF and d-DNNF formulas. For all definitions below, assume that X is finite set of variables.
We begin by describing partitions of X, corresponding to our partition of My. Definition A.1 (Partition (2]). A partition of X is a sequence of pairwise disjoint subsets X; of X such that U, X, = X. A partition of two blocks (X1,X, X2) is balanced if X /3 < min([X,] [Xa)).
can now define rectangles:
Definition A.2 (Combinatorial Rectangle 2). rectangle over X is a function f0, 1] (0, 1) such that there exists and underlying partition of X, called (X1, and functions ri (0, 1) > {0, 1) for i = 1, such that r (1) (1) ri- (()) x (1). A rectangle is bulanced if the underlying partition balanced.
Combining many of these rectangles together allows cover M,, effectively covering the function f. The size of these covers provides lower bounds on the communication complexity of f.
Definition A.3 (Rectangular Cover (2). Let f {0, 1] + {0,1} 1} be function. A finite set of rectangles {ri} over X is called a rectangle cover
-
The rectangle cover is referred to rectangle partition if the above union is disjoint. rectangle cover is balanced if each rectangle in the cover is balanced.
To understand how these rectangle partitions relate d-DNNFs and DNNFs, we utilize the following notions of certificates and elimination.
14

---

Definition A.4 (Certificate (2).. Let C be a DNNF on X. A certificate of C is DNNF T on X such that: T contains the output gate of C; T contains an A-gate, of C then T also contains every gate of C having an output wire to if I contains an V-gate of C, then 7 also contains exactly one gate of C having an output wire v. The output gate of coincides with the output gate of C, and the gates of 7 inherit their labels and wires from C. We let cert(C) denote the certificates of C.
See from the above definition that
(1)
U (1). TEOETT(C)
This is useful tool in relation to rectangle partitions due to the fact that given a DNNF C, T E cert(C) and gate 9. then Cg (1) = UU (ceer((,) (1) where Cy represents the sub-circuit C rooted at gate
Then we can represent Cg (1) as a rectangle which separates the variables in the sub-circuit rooted g. Using this in conjunction with the elimination operation gives us the ability to compute the size of our circuit using rectangles.
Definition A.5 (Elimination 2 Let C. be a DNNF and be non-input gate. Then,
C-a -1)=
U
(1)
TEcen(()))eer((C)))
In the case of a d-DNNF, by determinism we can write C-g (1) - (1)= Cg
Next we provide a short description the relationship between the size of rectangle covers and Boolean circuits; for the full detailed proofs see [2). Effectively, start with a d-DNNF C over variables X which computes a function f. Then, construct Ci+1 Cing. by eliminating 9i C until we hit
I I CC] such that C¹ = 0. It can be shown that R, C -1 (1) is balanced rectangle over X. The set {R, = = .,..., / 1} is then a balanced rectangle partition of C' since Ci+1 (1) 0. Therefore, can represent the size d-DNNFs representing functions as the size of a balanced rectangle partition said function. This implies that exponential size rectangle partition implies exponentially large d-DNNF.
A.3
Complete Proofs
A.3.1 Distribution Construction for Proposition 3.2
Proof. Let A be event such that P(A) and for some K 0,
P(x) K
Q(x)
Vx A.
Then, let Q(x) = AP(x), VX A for some constant To ensure that Q is normalized, see that we must have Σx Q(x) = Exen Q(x) ExEr Q(x) = 1. Therefore, we must have:
5 1 [(x)+ Σ Q(x) Σ P(x) Σ AP(x) K
+ X(1 Σ P(x))
8
+ A(1 - 88)
K
Hence
1-6/K I-3
and thus we can define
P(x)
E A x E A
Q(x)
1-8/K
P(x),
1-8
Therefore, just need to check then that the f-divergence between P and Q must be bounded.
15

---

P(x)
P(x)
P(x)
Σ Q(x))
Σ {(
+ Σ {(x)
1(x))
1(xx
A
Σ P(x),
/ ( (p(x)/K)
(P(x))
P(x)
6/K
( 1 1-
+
Σ
p(x)f
K
1- 8
1 11-6/K
A
f(K)
Σ P(x) 1- 66/K
1-6 8 /
(
1-8
PP(x)
Σ P(x)
K
1- 8/K
A=
5f(K)
1 - 8/K f ( 1 8
- 8/K8 ) (1 8)
K
1 1-8
8S(K)
-(1
8
11 8/K (1--7/
( 1 1
/
K
K
See that as 5 + 0, the above approaches 0+ f(1).
By definition of f-divergence, f(1) O. Thus, the dddivergence-includiin the total variation distance-between P and Q can be very small, approaching O, while the relative approximation error stays at constant factor K.
A.3.2 Pruning Deterministic PCs for the Proof of Proposition
Suppose that Q is a deterministic, decomposable and smooth probabilistic circuit. Given Q, wish to prune its edges such that in the resulting (unnormalized) PC Q', x is in the support of Q' if and only [((x= < ςоt.. We describe our pruning algorithm below.
First, we collect the an upper bound on each edge (n, c) that is the largest probability obtainable by any assignment x that uses that edge (propagates non-zero value through the edge in the forward pass for Q(x)). We denote this EB c), which stands for the in linear time in the size of the circuit using the Edge-Bounds algorithm [10]. This allows us to safely prune any edge whose Edge- Edge-Bound falls below given threshold; i.c., prune edge (n, c) if EB(n,c) c) < 2=+1-
This be done
Note that pruning some edges may cause the edge bounds for remaining edges to be tightened. Thus, we will repeat this process until all Qxx) < 2n-1 are pruned away. Upon completion of this process, we return back the new pruned circuit Q'.
We know that this algorithm halts as there can only be a finite number of x such that Q(x) < qTITT Moreover, given that we have only deleted edges from Q, our circuit Q' still a deterministic, decomposable and smooth probabilistic circuit and has size polynomial in the size of Q. We are also assured by determinism that we prune a path Q(x), there exists no other path that can evaluate (xx) 66) thus all (xx) < 2पFF are deleted. Furthermore, by the property that there is only one accepting path per assignment x, know that do not unintentionally delete any Q(x) 2-FT-
A.3.3
Connecting Total Variation Distance and Weak Approximation for the Proof of Proposition 4.3
Suppose that P is uniform distribution over the support given by a Boolean function f. and Q probability distributions over the support given by a Boolean funetion h. We look to analyze the total variation distance with respect support g. which is taken from Q'.
Drv(PI(Q) =
Σ IP(x) - +xx)+++++++++++++
Σ P(x) + Σ Q(x)
<E
FAR
XF-SAR
Σ IP(x) Q(x))
Σ P(x)
Σ Q(x) < 26
FAA
xF
XF
We partition into the disjoint sets g and -g A h (note that every model of g is already a model of h).
Σ
1
2(x))
Σ
MC(f) Q(x)) +
MC(S A -h)
Σ Q(x) < 2c
MC(F)
MC(f)
xF
xF -AA))
x= fAA
16

---

The LHS of above inequality is again lower bounded by:
MC( A -h)
Σ
Q(x)
Σ Q(x)
MC(J)
MC()
x= (A(3gA))
XF
Σ
1
MCUA -hi)
+
Σ
Q(x)
2
2
MC(F)
fM :gAh)
xF -fgg
Σ
1
MC(F -h)
MC(-FAg)
2
2
MC())
2n+1
x x-SA(-gAR)
as MC(J) S and ((x) < <1/2 for every x 1 -g A h. Thus,
+ MC(S A -h) MC ^ g)
Σ
20
2n
2
MC())
2
* *FfN(-gA))
MC(F A (-gA
MC -h) MC(-fAg)
2u+1
MC(F)
2n+1
MC(f (-gAA)
MC(f A A-) MC(-f A
MC(F A Ag) - MMC(- Ag)
2n+1
2n+1
2n+1
2n+1
implying MC(f A gg) + MCC(Ff Ag < = 2" (4c). Note that the last equality above is due to -h implying -g.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide theorems and results for all claims made in the abstract and intro- duction. Specifically, each section builds a result described in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We discuss all assumptions related to the hardness results provided. As well as the restriction to the form of f-divergence required for our results.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer: [Yes]
Justification: We provide both proof sketches and full proofs in the appendix of our paper. The assumptions are clearly stated for each theoretical result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
19

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeedouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
20

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics /tttps:///eurr// httpa//wpw.....ppaaoc.cccccaaaaa
Answer: [Yes]
Justification: This research as conducted in the paper conforms in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
23

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs not used in the core method development of this paper, and does not impact the originality or scientific rigorousness of the research.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httpp///eearrppsscc//oeeeeeeeeee for what should or should be described.
24


Reviews:
[{"review_id": "IdWA2HTDbs", "reviewer": "Reviewer_VR5d", "summary": "The paper investigates the ability of restricted classes of probabilistic circuits to model distributions. \n3 - Approximate the distribution with a smooth decomposable PC: hard\n4 - Convert decomposable PC to deterministic decomposable PC: hard\n5 - If you could approximate a distribution with bounded distance, you could do approximate inference with absolute error.", "questions": "1. When you consider relative approximation of a distribution, how are you assuming the distribution is represented or encoded? I ask because in theorem 3.3, you start with an arbitrary formula f and define P to be the uniform distribution on models of f. \n1a. Is it possible to convert a boolean formula into a PC that's uniform on models of the formula?\n1b. If no: how are you encoding probability distributions as inputs?\n1c. If yes: in 3.3, are you essentially showing that it's hard to convert a PC into a marginal-tractable PC?\n\n2.  What is different between your proofs in section 4 and the proofs in Bova et al and De Colnet and Mengel? Was there any insight in the conversion to PCs?\n\n3. Can you explain more about why hardness results for smooth decomposable PCs are significant?", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "+ I thought the results were well presented and organized.\n+ The questions addressed by the paper seem very relevant.\n\n? I don't know how significant the results are. The PC classes seem extremely restricted, so it doesn't surprise me that it's hard to approximate things with them, but I'm not familiar enough with the literature to say if the hardness results are interesting.\n? I'm still not convinced that Boolean functions are a good way of representing a distribution, but I don't have any specific reasons for disliking them either. If I had more time I would want to continue this discussion with the authors. It's entirely possible that I'm simply missing some background that makes it logical.\n? I got too stuck on theorem 3.3 to explore the rest of the paper in detail.\n\n- Section 4 seems to be mostly a rehash of a similar proof for logical circuits", "was_revised": true, "final_justification": "I now agree that Theorem 3.3 is correct as stated, and the authors have clarified to a great extent the wording that confused me. I still don't understand why their choice of a model for a distribution is a good one, but I don't know enough of the background here to consider it bad either.", "rebuttal": "Thank you for the constructive feedback. We answer individual questions below. \n\nQ1. When we consider relative approximation, we consider arbitrary distributions without assuming a particular representation form. For example, in Section 3.3 we consider a uniform distribution $P$ over the models of $f$, but we do not explicitly encode $P$ as a PC nor any other representation. In fact, representing this uniform distribution $P$ exactly is a non-trivial task because it would need to solve model counting which is #P-hard.\n\nQ2. The main difference between our proofs in Section 4 and those by Bova et al. [1] and De Colnet and Mengel [2] is two-fold. First, we use the Sauerhoff function, which Bova et al. used to show the exponential separation between DNNFs and d-DNNFs, to prove that the exponential gap exists even for weak approximation, defined by De Colnet and Mengel. The latter work in fact only showed that there exists a function that requires an exponential size for a d-DNNF to approximate, but not that such function can be represented by a polysized DNNF. Secondly, we extend this exponential separation to deterministic and decomposable PCs that can represent arbitrary distributions, where as previous results only applied to the case of PCs that are only allowed to represent uniform distributions over a logical formula.\n\nQ3. Understanding the expressive efficiency between different classes of PCs is of high interest to the community and well documented in the literature for the case of exact representations, but is significantly underexplored for approximations. The two PC classes that we consider are two of the most expressive efficient ones in the literature: for instance, all PC structure learning algorithms will output smooth and decomposable circuits. While the condition may seem restrictive, decomposable PCs have been shown to outperform even intractable models on density estimation tasks [3,4,5], while being tractable for marginals. Thus, finding that it is NP-Hard to approximate with decomposable PCs with a non-zero but bounded error is significant. Moreover, our NP-hardness result applies to any model that allows tractable marginal inference, and thus extends beyond decomposable PCs to a wide variety of models, such as determinantal point processes, probabilistic generating circuits, etc. \n    \nLastly, we would like to also reiterate that, to the best of our knowledge, we are the first to concretely establish relationships between approximate inference guarantees and bounded f-divergences. Previously, many types of approximate inference were implicitly assumed to hold when learning to achieve small f-divergences. This result applies generally to probabilistic models, not just PCs.\n\n\nTo address your formatting concerns, \n\n- The computational graph has a scope function $\\phi$ which associates each unit $n$ to a subset of the set of random variables $\\mathbf{X}$, defined recursively by $\\phi(n) = \\cup_{c \\in \\text{in}(c)} \\phi(c)$. The scope of a leaf node is simply the variable mentioned at that node. Alternatively, the scope of a node is the union of scopes of all leaf node with paths to that node. We will clarify this in the revision.\n    \n- $P$ being non-negative is a typo, this should instead say $P$ is positive only over the models of $f$. Thank you for catching this!\n\n- $Y$ in this case is only a single auxiliary variable, not a set of variables.\n\n[1] Bova, Simone, et al. \"Knowledge Compilation Meets Communication Complexity.\" IJCAI. Vol. 16. 2016.\n\n[2] De Colnet, Alexis, and Stefan Mengel. \"Lower bounds for approximate knowledge compilation.\" Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 2021.\n\n[3] Gala, Gennaro, et al. \"Probabilistic integral circuits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n[4] Liu, Anji, and Guy Van den Broeck. \"Tractable regularization of probabilistic circuits.\" Advances in Neural Information Processing Systems 34 (2021): 3558-3570.\n\n[5] Liu, Anji, Honghua Zhang, and Guy Van den Broeck. \"Scaling Up Probabilistic Circuits by Latent Variable Distillation.\" The Eleventh International Conference on Learning Representations."}, {"review_id": "EY1rnrcAL4", "reviewer": "Reviewer_Leaf", "summary": "This submission studies hardness of approximating probability distributions with probabilistic circuits (PCs). Prior work mostly studies *exact* representation of probability distributions with PCs. Approximation is considered with respect to f-divergences, which generalize KL divergence and TV distance.\n\nThe main contributions are:\n- Demonstrating NP hardness (reduction from SAT) of approximating an arbitrary distribution with bounded f-divergence, when the model class supports efficient computation of marginal queries.\n- Demonstrating an (unconditional) exponential separation between approximations using \"decomposable\" PCs and the even more restricted class of \"decomposable and deterministic\" PCs.\n- Showing that if approximate PCs are found for a given distribution, then absolute approximation guarantees can be given for marginal and MAP queries on the PC with respect to the real distribution.", "questions": "My questions surround the ability to prove stronger or broader hardness results.\n\n1. Have the authors considered proving some notion of average-case hardness to support the existing worst-case NP hardness? E.g., can you point to possible techniques / plans that could lead to proving that even randomly chosen distributions within some class are hard to approximate using a PC, with high probability over the random choice of distribution?\n2. In line with average case hardness, have the authors considered using well-studied cryptographic assumptions (e.g., factoring, learning with errors, etc.) which could support stronger hardness results (although with stronger assumptions than NP != P)?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. I agree with the authors that prior work has studied exact representation of distributions with PCs. In fact it is surprising that more work has not been done in the present setting, where approximation is considered. This paper makes a good step to filling that gap.\n2. I find the question of probabilistic modeling using data structures / architectures that support efficient queries to be well-motivated and timely. \n3. I find the paper to be written in a very clear manner, even as someone who was not intimately familiar with PCs prior to reading the paper.\n\n**Weaknesses**\n1. The main weakness I find is the fact that while foundational, NP-hardness suffers practical applicability due to its own worst-case nature. In particular, this does not necessarily give hardness for even the average distribution. This limits applicability in real life situations.", "was_revised": true, "final_justification": "I recommend a score of 5 (accept).\n\nI believe paper makes a good step towards filling the gap in the literature discussed by the authors (i.e., approximation of distributions with PCs.)\n \nI also believe the question of probabilistic modeling using data structures / architectures that support efficient queries to be very practical and timely. \n\nThe paper is clear and well-written throughout.", "rebuttal": "Thank you for the constructive feedback. We answer each question below. \n\nQ1. First, while NP-hardness is only concerned with worst-case complexity, we believe it is important to understand the limitations of the approximation scheme before we can move onto average cases. That being said, while outside the scope of this work, we think that this suggestion is very interesting. In fact, existing literature on expressive efficiency of different PC classes for exact representations is still limited to only worst-case complexity results. Average case complexity would be a good extension to this work, and would answer more questions about PC/tractable model representations in practice. The challenge would be in defining a good notion of ''average case'', for instance by limiting the set of distributions to be of a certain form and defining distributions over its parameter space.\n\nQ2. This is an interesting idea, we have not considered that in this work. We appreciate the suggestion and will consider this in the future."}, {"review_id": "UdSg8gDs6i", "reviewer": "Reviewer_sZag", "summary": "Probabilistic circuits (PCs) are appealing models because they support polynomial-time inference queries like marginalization under relatively mild structural assumptions. Their issue, however, is their limited expressive efficiency in the sense that there are probability distributions that cannot be encoded by a PC of polynomial size in the number of variables. This then motivates the problem of learning a circuit that *approximately* encodes the probability distribution under some distance metric such as the total variation distance, which in turn is bounded for any for any bounded $k$-convex $f$-divergence. The authors prove that it is unfortunately NP-hard to obtain such approximations of the probability distributions. The authors also show a gap in the expressive efficiency between the decomposable PCs and decomposable and deterministic PCs in an approximate setting, and study the relationship between the precision of the inference queries and the distance of the PC to the target distribution.", "questions": "To my understanding, total variation distance between two distributions is difficult to compute in general (and presumably the same holds for many other $f$-divergences). I would thus be curious to hear how the authors see the practical value of their work considering the intractability of evaluating the divergences when the probability distributions are given implicitly, e.g., as PCs.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think the present theoretical work studies an important problem of tractable probabilistic modelling and obtains nice novel results there, as discussed in the Summary. I would like to note, though, that the proof of your Theorem 3.3 resembles the proof of Proposition 1 in Appendix A.5 of Pote and Meel [1], so I would consider acknowledging that in some manner. Nevertheless, I think the paper would be worth citing since they study a related problem of whether there exists an efficient algorithm to test the closeness of two PC distributions.\n\nOverall, I think the paper is well-written and I see no immediate weaknesses. As a minor comment, please carefully check the capitalizations in the References, since e.g. \"Bayesian\" is consistently written in lowercase there.\n\n[1] Yash Pote, Kuldeep S. Meel:\nTesting Probabilistic Circuits. NeurIPS 2021: 22336-22347", "was_revised": true, "final_justification": "I maintain my earlier stance the work gives nice results on an important problem for tractable probabilistic modeling. While Reviewer VR5d had some concerns about Theorem 3.3, they appear to be mostly resolved now, so I see no issue for acceptance.", "rebuttal": "Thank you for the constructive feedback.\n\nWhile Pote and Meel are concerned with a different problem setup, we agree that the proof technique of thresholding using total variation distance and the area are related to our work. Thank you for the pointer, and we will cite the work in the revision. Furthermore, we will adjust the citations to ensure they have the correct capitalization, thank you for catching that mistake.\n\nTo answer your question: The total variation distance is indeed hard to compute for many probabilistic models. While some f-divergences such as the KL-divergence can be computed exactly between two PCs, this requires structural constraints that are more restrictive than those we consider in this paper. Nevertheless, note that upper-bounding the divergences suffices to apply our results. Thus, we hope that this work can motivate approximation/learning schemes that provide bounds on divergences which can derive some approximate inference bounds. Moreover, while we showed that approximate modeling with bounded f-divergences is NP-hard, the hope is that with further assumptions we can provide more guarantees that hold in practical settings."}, {"review_id": "7w1IEjOjPM", "reviewer": "Reviewer_om4K", "summary": "Probabilistic circuits (PCs) are a general class of distributions that enjoy linear time inference for several important query classes, such as computing marginal probabilities or MAP states, by enforcing structural properties. This work investigates what probability distributions can be approximated with guarantees using PCs. First, k-convex f-divergences, and in particular the special case of total variational distance (TVD), are established as a relevant criterion of approximation. Next, the paper investigates how a bound on the divergence of the distribution gives bounds on the approximation on the queries. In particular, when the TVD is bounded, the absolute error of the marginals (Thm 5.2) and MAP state (Thm 5.3) is also bounded, but not the relative error on the marginals (Prop 3.2) or the absolute error of conditionals (Thm 5.5). In the other direction, it’s shown that bounds on the relative error on the marginals lead to a bound on the f-divergence (Thm 3.1). Finally, it is shown that under bounded TVD, there is an exponential separation between arbitrary and decomposable PCs (Thm 3.3) and between decomposable and deterministic PCs (Thm 4.1).", "questions": "- Research on approximating weighted model counts [0] (very similar to approximating marginals on PCs) has shown that multiplicative $\\epsilon$ approximations do not give you much. Indeed, it is #P-hard just as exact WMC. However, when moving to $\\epsilon$ to $\\epsilon,\\delta$ approximations WMC becomes NP instead of #P [1] (still hard, but a very substantial difference). While reading the paper, I was wondering if similar could be taken for PCs?\n- (Lines 331-336) Dagum and Luby showed a FPRAS for marginals is possible, but you consider absolute approximation (i.e., FPAS) which is not possible. So I don’t get what this paragraph is supposed to say? Approximating with bounded f-divergence isn’t tractable, so I don’t see how this is an “*easy form of approximation*”?\n- On a more general note, the paper mostly contains negative results. I don’t have any problem with this but it begs the question what hope there is for approximations if they are still hard to construct and even cannot give approximation guarantees for many queries on them. Do the authors see any practical applications in the future?\n\n[0]: Chakraborty, Supratik, Kuldeep S. Meel, and Moshe Y. Vardi. \"Approximate model counting.\" *Handbook of Satisfiability*.\n\n[1]: Chakraborty, Supratik, Kuldeep S. Meel, and Moshe Y. Vardi. \"On the hardness of probabilistic inference relaxations.\" *Proceedings of the AAAI Conference on Artificial Intelligence*.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths.** The paper contains interesting theoretical results on approximating probability distributions and approximating inference, fundamental problems in machine learning. I was able to follow the paper fairly well, despite its very technical nature. To the best of my knowledge, the results are novel. Some results in the paper are not too surprising given existing results on approximate probabilistic inference. That being said, I still think that it’s useful to establish them, as this paper could form a basis for further study into approximate PCs.  \n\n**Weaknesses**. I feel the presentation could have been better on some points. I could follow fairly well as I’m familiar with the PC literature, but some concepts like conditional MAP might not be known to outsiders and are not introduced in the paper. The narrative and the overall picture was sometimes a bit lost among all the technical arguments. In my opinion, a graphical summary of the various results between the different approximations between circuit and inference types could make the paper more accessible. Furthermore, the paper is framed for PCs, but results outside of Sec. 4 are mostly not specific to PCs and could be of broader interest (this was not clear to me from the introduction). The paper also discusses little related work, even though e.g. there is work approximating weighted model counting that is very related to approximating marginals (c.f. questions).", "was_revised": true, "final_justification": "As the paper seems technically sound and I personally found the results sufficiently interesting, I recommend acceptance. \n\nReviewer VR5d raised some valid concerns on implicit assumptions, but I feel these have been addressed adequately by the authors. Unlike Reviewer VR5d, I do feel that PCs are an important class of distributions, due their unique trade-off in tractability vs expressivity.", "rebuttal": "Thank you for the constructive feedback. We will incorporate your suggestions to improve presentation in the revision. The additional page available for camera-ready versions upon acceptance would allow us to provide more background on different queries, add a graphical summary, and discuss more related work on approximate weighted model counting. In particular, we agree that our results outside of Section 4 are more broadly applicable beyond PCs, and we will revise to make this clearer. This would strengthen the significance of our contributions to a broader community.\n\nQ1. Thank you for the interesting suggestion. We had not considered probabilistic approximations for this paper, but this relaxation is a promising future direction. It could also be worthwhile to consider in conjunction with the average case complexity that Reviewer Leaf has brought to our attention.\n\nQ2. We agree that ''easy form of approximation'' is not exactly correct. More precisely, there exists a randomized algorithm for the absolute approximation of marginals. We still would not have absolute approximation from this in our sense, but this is one of the few types of approximation we discuss throughout our paper which even has a randomized algorithm. We will adjust the paragraph accordingly. \n\nQ3. While this paper mostly contains negative results, we hope that this will inspire future works on approximations to provide approximate inference guarantees, through relaxations such as probabilistic approximations or average-case guarantees or by considering a special case of target distributions."}]

Author rebuttal:

Meta-review: This work presents fundamental theoretical results on the hardness of approximating distributions with probabilistic circuits. The submission received strong support with three reviewers giving strong accepts and one borderline reject. During extensive exchange between the authors and Reviewer VR5d, the technical concerns were thoroughly discussed, leading to clarifications and a better understanding of the results. Reviewer VR5d also acknowledged the technical correctness of the proofs in the final justification of the review.

Overall, the paper makes significant contributions by establishing the first systematic study of approximation hardness for probabilistic circuits, proving NP-hardness for bounded f-divergence approximations and exponential separations between circuit classes. These theoretical foundations are crucial for understanding the fundamental limits of tractable probabilistic modeling. Given the overwhelming reviewer consensus, technical soundness, and importance of the contributions to the probabilistic modeling community, I recommend **ACCEPT**.
Decision: Accept (spotlight)