A Compositional Atlas for Algebraic Circuits
Authors: Benjie Wang
Denis Mauá
Guy Van den Broeck
YooJung Choi
Venue: NeurIPS 2024 poster (2024)
Keywords: semiring
probabilistic circuits
logic circuits
probabilistic inference
algebraic
Primary area: probabilistic_methods
TL;DR: We introduce a unifying framework for deriving algorithms and tractability conditions for complex compositional inference queries, such as marginal MAP, logic programming inference and causal inference.

Abstract: Circuits based on sum-product structure have become a ubiquitous representation to compactly encode knowledge, from Boolean functions to probability distributions. By imposing constraints on the structure of such circuits, certain inference queries become tractable, such as model counting and most probable configuration. Recent works have explored analyzing probabilistic and causal inference queries
as compositions of basic operators to derive tractability conditions. In this paper, we take an algebraic perspective for compositional inference, and show that a large class of queries—including marginal MAP, probabilistic answer set programming inference, and causal backdoor adjustment—correspond to a combination of basic operators over semirings: aggregation, product, and elementwise mapping. Using this framework, we uncover simple and general sufficient conditions for tractable composition of these operators, in terms of circuit properties (e.g., marginal determinism, compatibility) and conditions on the elementwise mappings. Applying our analysis, we derive novel tractability conditions for many such compositional queries. Our results unify tractability conditions for existing problems on circuits, while providing a blueprint for analysing novel compositional inference queries.

A Compositional Atlas for Algebraic Circuits
Benjie Wang
Denis Deratani Mauá University of São Paulo ddm@ime usp. br
University of California, Los Angeles benjiewanguucla.ed
Guy Van den Broeck
YooJung Choi Arizona State University yj choi Choi@asu.co edu
University of California, Los Angeles guyvdbêes. wwtpootsssscllle..oom ucla.edu
Abstract
Circuits based on sum-prodee sum-product structure have become ubiquitous representation to compactly encode knowledge, from Boolean functions to probability distribu- tions. By imposing constraints on the structure of such circuits, certain inference queries become tractable, such as model counting and most probable configuration. Recent works have explored analyzing probabilistic and causal inference queries compositions of basic operators to derive tractability conditions. In this paper, we take an algebraic perspective for compositional inference, and show that a large class of queries includingg marginal MAP, probabilistic answer set programming inference, and causal backdoor adjustment correspond to combination of basic operators semirings: aggregation, product, and elementwise mapping. Using this framework, we uncover simple and general sufficient conditions for tractable composition of these operators, terms of circuit properties (e.g.. marginal deter- minism, compatibility) and conditions on the elementwise mappings. Applying our analysis, we derive novel tractability conditions for many such compositional queries. Our results unify tractability conditions for existing problems on circuits, while providing blueprint for analysing novel compositional inference queries.
Introduction
Circuit-based representations, such as Boolean circuits, decision diagrams, and arithmetic circuits, of central importance in many areas AI and machine learning. For example, primary means of performing inference in many models, from Bayesian networks 16, 9 to probabilistic programs is convert them into equivalent circuits; this is commonly known as knowledge compilation. Inference via knowledge compilation has also been used for many applications in symooly AI, such as constrained generation 2
20
24
26
43
[54] and neural logic programming Circuits can also be learned as probabilistic generative models directly from data [25
28).
41
40 32 in
which context they are known as probabilistic circuits [T]. Compared with neural generative models, probabilistic circuits enjoy tractable evaluation of inference queries such as marginal probabilities, which has been used for tasks such fair machine learning [2 and causal reasoning [53 49
The key feature of circuits is that they enable one to precisely characterize tractability conditions (structural properties of the circuit) under which given inference query can be computed exactly and efficiently. One can then enforce these circuit properties when compiling or learning a model enable tractable inference. For many basic inference queries, such as computing a marginal probability, tractability conditions are well understood [48] g]. However, for more complex queries, the situation less clear, and the exercise of deriving algorithms and tractability conditions for given query has usually been carried out in an instance-speciff manner requiring significant effort.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

EXX,)(X,
6XX. Σx Σx3(X) Lx Ey A.X.9]
p(x, Y)
x Y)
Y
Tel
x
YY ~
q
w(X)
Figure 1: Example applications of our compositional inference framework for (Left) MMAP and
(Right) Success Probability in Prob. Logic Programing under the Stable Model semantics (MaxEnt).
In Figure | we illustrate two such queries. The marginal MAP (MMAP) 13
query takes probabilistic circuit p and some evidence e and asks for the most likely assignment of a subset of variables. The success probability inference in probabilistic logic programming 6 45 takes circuit representation & of a logic program, a weight function w and some query q. and computes the probability of the query under the program's semanties (MaxEnt, in the example). At first glance, these seem like very different queries, involving different types of input circuits (logical and probabilistic), and different types of computations. However, they share similar algebraic structure: logical and probabilistic circuits can be interpreted as circuits defined over different semirings, while maximization and summation can be viewed aggregation over different semirings. In this paper, inspired by the compositional atlas for probabilistic circuits 48), we take a compositional approach to algebraic inference problems, breaking them down into series of basic operators: aggregation, product, and elementwise mapping. For example, the MMAP and probabilistic logic programming queries involve multiple interleaved aggregations and products, along with one elementwise mapping each. Given a circuit algorithm (and associated tractability condition) for each basic operator, we can reuse these algorithms to construct algorithms for arbitrary compositions. The key challenge is then to check if each intermediate circuit satisfies the requisite tractability conditions.
Our contributions can be summarized as follows. We introduce a compositional inference framework for algebraic circuits (Section 3 over arbitrary semirings, generalizing existing results on logical 18 and probabilistic [48] circuits. In particular, we provide language for specifying inference composition of basic operators (Section B.1.. We then prove sufficient conditions for the tractability of each basic operator (Section 33.2 and novel conditions for composing such operators (Section 3.3). We apply our compositional framework to number of inference problems (Section 4). showing how our compositional approach leads to more systematic derivation of tractability conditions and algorithms, and in some cases improved complexity analysis. In particular, we discover a tractability hierarchy for inference queries captured under the 2AMC framework [29]. and reduce the complexity of causal backdoor/frontdoor adjustment on probabilistic circuits 38 49 from quadratic/cubic to linear/quadratic respectively.
queries involving different semirings
Preliminaries
Notation We use capital letters (e.g., X, Y) to denote variables and lowercase for assignments (values) of those variables (e.g., I, y). We use boldface to denote sets of variables/assignments (e.g.. X, y) and write Assign( V) for the set of all assignments to V. Given variable assignment of V. and a subset of variables W C V. we write uw to denote the assignment of W corresponding to v.
Semirings In this paper, we consider inference problems over commutative semirings. Semirings are sets closed w.r.t. operators of addition (() and multiplication (0) that satisfy certain properties:
Definition 1 (Commutative Semiring). A commulative semiring S is tuple (S, @ 8 Os, 1s), where @ and & are associative and commutative binary operators on a set S (called the domain) such that @ distributes over @ (i.e., & (b [) (a @ b) @ (a @ c) for all b, S); Og E S is the additive identity (i.e., Og @ a = a for all a E S) and annihilates through multiplication (i.e., Og @ a for all a E S): and 1 E S is the multiplicative identity (i.e., 1s
for all S).
For example, the probability semiring P = (R2o, +, 0, 1) employs standard addition and multiplica- tion ( + and @ -) over the non-negative reals, the (max, -) semiring M (Rzo, max, 0, 1)

---

XX1
Y1
[-Xi]
[-X]
[XX]]
PGG
[-Xal
[-Ya]
(a) A Boolcan circuit that is smooth, decompos- able, deterministic, but not (Xl-eeeeminiittc. (Xi, X2] deteermiiiiii [+]
(b) A probabilistic circuit that is smooth, decomposable, and maps 1 and T to O.
Figure 2: Examples of Algebraic Circuits. We use O, O, O to represent input, sum and product nodes respectively.
replaces addition with maximization, while the Boolean semiring B (J,,T)VV,A,) employs disjunction and conjunction operators (#) V and @ = A) over truth values.
Algebraic Circuits We now define the concept of an algebraic circuit, which are computational graph-based representations of functions taking values an arbitrary semiring.
Definition 2 (Algebraic Circuit). Given a semiring S = (S, @D, &, 0,0s, 1s). an algebraic circuit C over variables V is a rooted directed acyclic graph (DAG), whose nodes a have the following syntax:
::= 1| + x
where a; E C are circuit nodes, k E N20 and 1 Assign( - S is a function over a (possibly empty) subset W CV of variables, called its scope. That is, each circuit node may be input (l), sum (+), or a product ( (x). The scope of any internal node is defined to be vars(a:) := U var)(a;). Each node a represents function Pa laking values in S, defined recursively by: Po (w) := I(w) if
L, (w() ::= @ (w) if a + Qi and (w(w) ::= & Pa (w) if x where W the scope of a. The function pe represented by the circuit is defined to be the function of the root node. The size |C| of a circuit is defined to be the number of edges in the DAG.
For simplicity, will restrict circuits with binary products (i.e. k for products); this can be enforced with at most a linear increase in size. Prominent examples of algebraic circuits include negation normal forms (NNF) and binary decision diagrams 4 which are the Boolean semiring and represent Boolean functions- and probabilistic circuits [I]] wwich are over the probabilistic semiring and represent probability distributions ! which we call circuil properties, various inference queries that are computationally hard in general become tractable. In particular, smoothness and decomposability ensure tractable marginal inference:
By imposing simple restrictions on the circuit,
Definition 3 (Smoothness, Decomposability). its children have the same scope: Vi.j, vars(ax) = vars(a;). A circuit is decomposable for every product node a = 0₁ x 022, its children have disjoint scopes: vars(a,) n vars(a2) = V.
circuit is smooth for every sum node a = +.0
Aside from the scopes of circuit nodes, we can also specify properties relating to their supports 11 Definition 4 (X- -Supporr).. Given partition (X, Y) of variables V and node in circuit C, the X support of a is the projection of its support on X:
supp (a) (x Assign( (X vars(a)) By E AAssign(var((a) \ X) s.t. Pa (xx y) # Os}. Definition X--Determinism). Given a circuit C and a partition (X, Y) of V, we say that
C is X --deterministtcc if for all sum nodes a = + either: (i) vars(a) O X = 0; or (ii) supp x (a:) supp (a,) / for all $j. j.
X d-detrrminism refers family of properties indexed by sets X. In particular V -dettermiiism is usually referred to simply as determinism. Note that, as defined, scope and support, and thus these circuit properties, apply any semiring: the scope only depends on the variable decomposition circuit, while the support only refers to scope and the semiring additive identity 0s. Figure 2a shows simple example of a smooth, decomposable, and deterministic circuit that is not X -deetemministic, while Figure 2b shows a smooth, decomposable, and (X,, X2 deterministic circuit.
the
"Probabilistic circuits are sometimes written with weights on the edges; this can easily be translated to our formalism by replacing the child of a weighted edge with a product of itself and an input function with empty scope corrresponding to the weight 42).
3

---

3 Compositional Inference: A Unifying Approach
Many inference problems can be written as compositions of busic operalors, which take input one or more functions and output another function. For example, the marginal MAP query on probability distributions maxæ Ey p(., y) a composition of the Σ and max operators. Similarly, for Boolean functions Φ, t), the query Σ> By. o(x; y) A (0 y) composes the > and A operators. Although these queries appear to involve four different operators. three of them (2: max, 3) can be viewed as an aggregation operation over different semirings. Thus, we begin this section by consolidating to simple set of three operators applicable to functions taking values in some semiring: namely, aggregation, product, and elementwise mapping (Section B.I).
Equipped with this language for specifying compositional inference queries, we then move on to analyzing their tractability when the input functions are given as circuits. The thesis of this paper is that algebraic structure is often the right level of abstraction to derive useful sufficient (and sometimes necessary) conditions for tractability. We firstly show tractability conditions of each of the basic operators (Section 3.2), before deriving composability conditions showing how circuit properties are maintained through operators (Section 3.33.. This enables us to systematically derive conditions for the input circuits that enable efficient computation of a compositional inference query. Algorithms and detailed proofs of all theorems can be found in Appendix
3.1 Basic Operators
Aggregation Given function Assign( (V) + S, aggregating I over W S V returns the function Assign Z) + for = V W defined by f'(z) := θ f(z,w).
For example, aggregation corresponds to forgetting variables W in the Boolean semiring, marginaliz- ing out W the probability semiring, and maximizing over assignments in the (max, semiring. Next, some queries, such as divergence measures between probability distributions, take two functions as input, and many others involve combining two or more intermediate results, as is the case in probabilistic answer set programming inference and causal backdoor/frontdoor queries. We define the product operator to encapsulate such "combination" of functions general.
Product Given two functions : W) - S and f': Assign( W + S, the product of f and f' a function f" Asssinnn) (V) - S, where V = WUW', defined by f"(v) == f(ow) )(0 I' (www.).
For example, a product corresponds the conjoin operator A in the Boolean semiring, and standard multiplication in the probability semiring. Lastly, we introduce the elementwise mapping operator, defined by a mapping T from a semiring (possibly different) semiring. When applied to function f. it returns the function composition 7 o f. This is the key piece that distinguishes our framework from prior analysis of sum-of- sum-of-produut queries over specific semirings, allowing us to express queries such as causal inference and probabilistic logic programming inference under the same framework.
Elementwise Mapping Given function f: Assign(V) + S and a mapping 7 :: S >> S' from semiring S to S' satisfying (0s)) 0g. an elementwise mapping of by 7 results in a function f' Assign((/) (V) + 5" defined by f'(v) == ::::=:fff r(f()))
In practice, we use elementwise mappings as an abstraction predominantly for two purposes. The first is for switching between semirings, while the second is to map between elements of the same semiring. For the former, one of the most important elementwise mappings we will consider the support mapping, which maps between any two semirings as follows.
Definition 6 (Support Mapping). Given a source semiring S and a target semiring S', the support mapping [lss is defined as: [a]s=s: = 0s: if = 0s: [a]s-ss = Ls otherwise.
In particular we will often use the source semiring S = B, in which case the support mapping maps I to the Og and to the is in the target semiring. This is useful for encoding a logical function for inference in another semiring, e.g. probabilistic inference in the probabilistic semiring.
In slight abuse of notation, we will write S' to indicate that maps between the respective sets.

---

Example 1 (Marginal MAP). Suppose that we are given a Boolean formula Φf X, Y) and a weight function w Assignn X UY) + Rzo- The marginal MAP query for variables X defined by MMAP(Ó,w) mmax Ed(x. (.:.y))w(a3) w(x.))
where we interpret T as and 1. as We can break this down into a compositional query as follows:
- Tid.P-M
Alo(,, y)ls @0 w(w
The support mapping ensures & and w are both functions over the probabilistic semiring, so that we can apply the product operation. Notice also the inclusion of an identity mapping T. from the probability to the (max.-) semiring defined by Tupp-MM
x for all x E R20- While differentiating between semirings over the same domain may seem superfluous, the explicit identity operator will become important when we analyze the tractability of these compositions on circuits.
3.2 Tractability Conditions for Basic Operators
We now consider the tractability of applying each basic operator to circuits: that is, computing a circuit whose function corresponds to the result of applying the operator the functions given by the input circuit(s). First, it is well known that forgetting and marginalization of any subset of variables can be performed in polynomial time if the input circuits in the respective semirings (NNF and PC) are smooth and decomposable [18] I1. This can be generalized to arbitrary semirings:
Theorem 1 (Tractable Aggregation). Let C be smooth and decomposable circuit representing function p Assign(V) V) + Then for any W C V, it is possible to compute the aggregate as a smooth and decomposable circuit C' (i.e., pCr (Z) ① w PC [Z; w)) in O([CI) time and space.
Next, let us consider the product operator. In the Boolean eircuits literature, is well known that the conjoin operator can be applied tractably if the circuits both follow a common structure known as a viree [7.. In 48 a more general property known as compatibility was introduced that directly specifies conditions with respect to two (probabilistic) circuits, without reference to vtree. We now define generalization of this property (X- coopatibiliity and also identify a new condition (X support-commptiiility that enables tractable products.
Definition (X-Com Compatibility). Given two smooth and decomposable circuits C, C' over variables V. V' respectively, and a variable set X C VnV', we say that C, C' are X X-compatible for every product node a = an x 02 E C and a' = oi o22 E C' such that vars(a) X = vars(a') ))) n X, the scope is partitioned in the same way, i.e. vars(on) X vars(a)) ) n X and vars(oz) O X vars(a)) X. We say that C,C C' are compatible if they are (V V") "")o-compaibbee
Intuitively, compatibility states that the scopes of the circuits decompose in the same way at product nodes. Compatibility of two circuits suffices to be able to tractably compute their product:
Theorem 2 (Tractable Product Compatibility). Let C, C' be compatible circuits over variables V. V', respectively, and the same semiring. Then it is possible to compute their product circuit C' compatible with them (i.e., Pc" (VU(V = (V) )) @ Pc (V')) in O(CC)(C"I) time and space.
We remark that if we are given fully factorized function S(V) = & S((V.), this can be arranged circuit (series of binary products) compatible with any other decomposable circuit; thus, we say this type of function is omni-compatible. We also say that a circuit is structured decomposable if it is compatible with itself. Now, our more general definition of X -coopaatibliiyy states that the scopes of the circuits restricted to X decompose in the same way at product nodes. This will be important when we consider composing products with other operators, such as aggregation. The following result shows that compatibility w.r.t. a subset is a weaker condition:
Proposition 1 (Properties of X X-Compatibilityy. two circuits C, C' are X X-compatible, then they are X' X' ccmpatiible for any subset X' C X.
Compatibility is sufficient but not necessary condition for tractable products. Some non-compatible circuits can be efficiently restructured to be compatible, such that we can then apply Theorem 2
we refer readers to (55) for details. Alternatively, it is also known that deterministic circuits can be
multiplied with themselves in linear time, even when they are not structured decomposable [48] 27
We formalize this idea with property that we call support-compatbblliyy
5

---

Definition 8 (X- X-Support Compatibility). Given two smooth and decomposable circuits C, C' over variables V. V' respectively, and set of variables X S V n V'. let C C* be the DAGs obtained by restricting to nodes with scope overlapping with X. We say that C, C' are X -uppport- compatible if there is an isomorphism between C[X]
, C" ['[ such that: (0) for any node a E C (ax)) n supp x (1(a,)) 9 vars(a)) n X = vars(u(a)) n X; (ii) for any sum node a E C ([X), supp x
whenever i + j. We say that C, C' are support-compatible if they are (V V') -'s'VVV''"ot-ccoomiee support-compatible
To unpack this definition, we note that any smooth, decomposable, and X -ddetemministic circuit is X-support-compatte
with itself, with the obvious isomorphism. However, this property is more general in that it allows for circuits over different sets of variables and does not require that the nodes represent exactly the same function; merely that the sum nodes have "compatible" support decompositions, As we will later see, the significance of this property is that it can be often maintained through applications of operators, making it useful for compositions.
Theorem (Tractable Product- Support Compatibility). Let C, C' be support-compatibl circuits over variables V, V', respectively, and the same semiring. Then, given the isomorphism i, it is possible to compute their product as a smooth and decomposable circuit C" support-compatible with time and space.
them (i.e.. pC V V') = pc(V) (V) @ po pc.(V') in (mmax(IC),
We now examine the tractability of general elementwise mappings T S - S' on circuit C. It is tempting here to simply construct a new circuit C" over the semiring S' with the same structure as C, and replace each input function / in the circuit with rl). However, the resulting circuit pe ( (V) is not (V)) in general. For example, consider the support mapping
guaranteed to correctly compute T (Pcc ) Ils-s- which maps 1 to Og and T to 1s for the probability semiring S (Rzu. - 0. 1). Then the transformation of the smooth and decomposable circuit C = X V X produces C' = [X]] + [X],
which evaluates to Pcr (X = T) 2 whereas T (Po T)) 1. In order for this simple algorithm to be correct, we need to impose certain conditions on the elementwise mapping r and/or the circuit C it is being applied to.
Theorem 4 (Tractable Mapping). Let C. be a smooth and decomposable circuit over semiring S, and T: S + S' a mapping such that r0ss) = Os. Then it is possible to compute the mapping of C by as a smooth and decomposable circuit C' (i.e., per (V) = ((pp(V)) in O((Cl) time and space T distributes over sums and over products.
distributes over sums if: either (Additive) T is an additive homomorphism, i.e. T(a + b) T (a) @ T(b); or (Det) C is deterministic.
distributes over products if: either (Multiplicative) T is an multiplicatiie homomorphism, i.e. r(a@b) = r(a) @ rb)) or (Prod 0/1) r(1s) = Lg,, and for all product nodes a 01 x x02 E C, and for every value v E Assign( vars( either Pa, (Vrars(o)) E {0s. 1s} or Po. Po. (U)a)()))) E (0s, }s}
We can apply Theorem to immediately derive the following property of support mappings: Corollary (Support Mapping). Given a circuit C over a semiring S and any targel semiring S', a circuit representing [Pcls-s' can be computed tractably (i) S satisfies & b = Os = a. b= Og and S' is idempotent (i.e. Ls + Ls 1s²), or (ii) C is deterministic.
Proof. First note that [lss satisfies (Multiplicative), and thus distributes over products. (i) holds, consider [a + bls-s' If a = b = 0g, then this equal to [0s]s-s [a]s= + [b]s-s 0g: otherwise a, b, a + b+ # Og and [a e bls = s + [b]s = Ls. (by idempotence of S'). Thus sss-s satisfies (Additive). Alternatively, if (ii) holds, then (Det) holds. In either case sss distributes over sums in the circuit.
The following examples illustrate the generality of elementwise mappings and Theorem 4
Example 2 (Partition Function and MAP). Given probability distribution p(V P(V)), consider the task of computing the partition function E.p() and MAP max p(v). These can be viewed as aggregations over the probability and (max, semirings respectively.
p is often either a probabilistic circuit Cproh or a combination of a Boolean circuit Choot and weights w (in weighted model counting). In the former case, the partition fanction is tractable because the circuit already over the probability semiring, while in the latter case, MAP is tractable because the S' = (max,) -) semiring is idempotent so [[bood] s is tractable. On the other hand, the partition

---

Table 1: Tractability Conditions for Operations on Algebraic Cireuits. Sm: Smoothness, Dec: De-
composability: X- X-Det(erminism), X X-Cmp: X X-Coopatibility. X X-SCmp: X
If the Input Circuit(s) are
Conditions
X X-Det
X Cmp w/ Cather
X-SCmp w/ Cother
Complexity
Then the Output Circuit is
(A.4]
X-Det
X-Cmp w/ Cather
X-SCmp w/ Cother if WnX
Aggr. (W)
Sm, Dec
O((C))
A.I
WWX Wr
Cmp
X-De
X Cmp w/ Cather
NIA
O A.2.1
Product
SCmp
X-Det
X X-Cmp Cotter
SC5mp w/ Cotias
(mmax
C
A.2.2
Elem.
Sm, Dec,
Mapping
(Add/Det)
X-Det
X-Cmp Coner
X-SCmp w/ Cotier
O(IC1) A.3
(Mult/Prod01)
function for Boolean circuits and MAP for PCs require determinism for the conditions of Theorem to hold; in fact, these problems are known to be NP-hard without determinism [18 39/.
Example 3 (Power Function in Probability Semiring). For the probability semiring S =''
(R20, 0,,,, consider the power function TT(()) == {a² aa if # 0
if 0 for some B E R. This
mapping satisfies (Multiplicative), and is tractable if we enforce (Det) on the circuit.
is worth noting that semiring homomorphisms (i.e. additive and multiplicative) are always tractable. In the case when S = S' = P. it was shown in [88] that the only such mapping is the identity function. However this is not the case for other semirings: the power function 73 is an example in the (max, semiring. To summarize, we have shown sufficient tractability conditions for aggeregation, products, and elementwise mappings. Notice that the conditions for aggregation and products only depend on variable scopes and supports, and as such apply to any semiring; in contrast, for elementwise mappings, take advantage of specific properties of the semiring(S) in question.
3.3 Tractable Composition of Operators
We now analyze compositions of these basic operators. As such, we need consider not only eircuit properties that enable tractability, but how these properties are maintained through each operator, so that the output circuit can be used as input to another operator. We call these composability conditions. In all cases, the output circuit is smooth and decomposable. Thus, we focus on the properties of X -ddeterminism, X X--ompatibility, and singular properties, but rather families of properties indexed by variable set X. We present the intuitive ideas behind our results below, while deferring full proofs to the Appendix.
cuupport-comptiiiiin
We emphasize that these are not
Theorem 5 (Composability Conditions). The results in Table 7 hold.
X <-determinism Intuitively, X X-determinism is maintained through products because the resulting sum nodes partition the X -uppport in a "finer" way to the original circuits, and through elementwise mappings since they do not expand the support of any node (since 700s) 0g ). For aggregation, the X -support is maintained if aggregation does not occur over any of the variables in X.
X X-compatibility Here, we interested in the following question: if the input circuit(s) some operator are X-compatible with some other circuit Cother for any fixed X, is the same true of the output of the operator? X X-copaatiiliity with Cotter is maintained through aggregation because it weakens the condition (by Proposition (T] and through elementwise mapping as does not change variable scopes. As for taking the product of circuits, the output circuit will maintain similar variable partitionings at products, such that it remains X -compatible with Cother- Notably, this result does hold for compatibility where the scope X may be different for each pair of circuits under consideration; we show a counterexample in Example 4 in the Appendix.
X --sppioot-compattbbiity X -suuppot-compatiiiiie is maintained through elementwise mappings and aggregation (except on X) for similar reasons to ---eterminism. For products, the result retains similar X support structure, X -supporr compatibility is maintained.
We conclude by remarking that, once we determine that compositional query tractable, then one immediately obtains a correct algorithm for computing the query by application of the generic
7

---

Table Tractability Conditions and Complexity for Compositional Inference Problems. We denote new results with an asterisk.
Problem
Tractability Conditions
Complexity
PASP (Max-Credal)"
Sm, Dec, X-Det
O(C[)
2AMC
PASP (MaxEnt)", MMAP
Sm, Dec, Det, X-Det
O(C))
SDP*
Sm, Dec, Det, X-Del, X-First
((C))
Sm, Dec, SD, (X )
O(CCP)
Causal
Backdoor
Sm, Dec, Z-Det, (X U Z)-Del
O(C))
Inference
Frontdoor
Sm, Dec, SD, X-Det, (X U D-Deet
O(C
MFE*
Sm, Dec, H-Det I -Det, (H UI J-Det
((C)
Other
Reverse-MAP
Sm, Dec, X-
O(CC)
algorithms for aggregation, product, and elementwise mapping (see Appendix A). An upper bound on the complexity (attained by the algorithm) is also given by considering the complexities of each individual operator; in particular, the algorithm is polytime for a bounded number of operators.
4
Case Studies
In this section, we apply our compositional framework to analyze the tractability of several different problems involving circuits found in the literature (Table ( Some of the results are known, but can now be cast in a general framework (with often simpler proofs). We also present new results, deriving tractability conditions that are less restrictive than reported in existing literature.
Theorem 6 (Tractability of Compositional Queries). The results in Table 2 hold.
4.1 Algebraic Model Counting
In algebraic model counting (30 (a generalization of weighted model counting), one given Boolean function o(V), and fully-factorizee labeling function w( (V) 8 Viev wi (V;) in some semiring S, and the goal is to aggregate these labels for all satisfying assignments of Φ. This can be easily cast in our framework as + (I(((v))] @ w()). Here, the support mapping Fls-ss transfers the Boolean function to the semiring S over which aggregation occurs. Assuming that <(V) given as a smooth and decomposable Boolean circuit (DNNF), then by Corollary [ tractable if S is idempotent or if the circuit is additionally deterministic (note that w (V) is omni omni-com muni-compatible, so the product tractable); this matches the results of [30].
2AMC A recent generalization of algebraic model counting is the 2AMC (second-level algebraic model counting) problem (29), which encompasses number of important bilevel inference problems such as marginal MAP and inference in probabilistic answer set programs. Given partition of the variables V = (X, Y), a Boolean function o(X Y), outer and inner semirings Sx Sy, labeling functions wY (Y)= Yee wy.; (Y:) over Sy and (X) X x. wx,:(X;) over Sx, and an elementwise mapping TSy :Sy - Sx, the 2AMC problem given by:
-Sx
+ [o(x, y)ls @ w()) @ w((x))
(I)
To tackle this type of bilevel inference problem, 29 identified circuit property called X-firstness.
Definition 9 (X-Firstness), Suppose C' is circuit over variables V and (X, Y) a partition of V. We say that node a E C X-only if vars(a) X, Y-only if vars(a)) C Y, and mixed otherwise. Then we say that C is X-first if for all product nodes a 0i X 022, we have that either: (i) each o; X -only Y -only; (ii) or exactly one 04 is mixed, and the other is X-only.
It was stated in 29 that smoothness, decomposability, determinism, and X -ffrstnness suffice to ensure tractable computation of 2AMC problems, by simply evaluating the circuit in the given semirings (caching values if necessary). We now show that this is neither sufficient nor necessary in general. To build intuition, consider the simple NNF circuit Φ(X, Y) = (X A v) (X -Y). Note that ó trivially satisfics X Xffrrstness and is smooth, decomposable, and deterministic. Let S
8

---

(a) Boolean circuit (XX, Y)
(b) Inner semiring evaluation
(c) Outer semiring evaluation
Figure 3: Failure case of 2AMC algorithm on smooth, decomposable, X-first circuit.
be the probability semiring, S be the (max, --semiri,,, labeling functions be w(y) w(-y) w'(x) = w'(=z) = 1, and the mapping function be the identity T(a) = a. Then, noting that the labels are the multiplicative identity 1, the 2AMC value is maxx x 7 ( Y) B-)))
max(=([6(2, s)ls-s + [Ø(z, -y)l =-)], 7 ([[((z,, y)ls>s + [ x -y)]
max(r(1
10)) = On the other hand, the algorithm of (29) returns the value 2AMC 1, as shown in 3 This is not jotjust flaw in the specific evaluation algorithm, but rather provable intractability of the problem given these properties:
Figure
Theorem 7 (Hardness of 2AMC with X-firstness). 2AMC is #P-hard, even for circuits that are smooth, decomposable, deterministic, and X -ffirst, and a constant-time elementwise mapping.
Analyzing using our compositional framework, the issue is that the tractability conditions for do not hold; whilst the Boolean circuit is deterministic, this is not true once Y is aggregated. In fact, we show that also enforcing X -determinism suffices to tractably compute arbitrary 2AMC instances. Theorem (Tractability Conditions for 2AMC). Every 2AMC instance is tractable in O((C)) time for Boolean circuits that smooth, decomposable, deterministic, X first, and X --deterministic.
Proof sketch. The key point to notice is that the elementwise mapping relative to the transformation of inner to outer semiring operates over aggregation of an X -firtt and X -ddeterministic circuit, obtained by the product of a Boolean function (mapped to the inner semiring by support mapping) and weight function of Y. Hence, it satisfies (Det) and (Prod 0/1): all of the X X-only children of product node are 0/1 valued (in the inner semiring).
For specific instances of 2AMC, depending the semirings S, S' and mapping function т, also find that it is possible to remove the requirement of X -frrstnnss or (V)-determinism. as we summarize in Table One might thus wonder if there is difference in terms of compactness between requiring X --determmnism and X-firstness, as opposed to X X-determinism alone. For example, for sentential decision diagrams (SDD) [17]. popular knowledge compilation target, these notions coincide: a SDD is X-deterministic iff it is X-first (in which context this property is known as X c-constrainedness (37 (22)). However, as shown in Figure 2b there exist X -determinnistic but X -fristt circuits. We now show that X -determministic circuits can be exponentially more succinct than X -etterministic circuits that additionally X -frrst, the size of X grows
Theorem 9 (Exponential Separation). Given sets of variables xX), there exists a smooth, decomposable and X X-deterministic circuit C of size poly(n) such that the smallest smooth, decomposable, and X --first circuit C' such that PC = PC has size 20(n)
Y
Thus, to summarize, some instances of 2AMC can be solved efficiently when & is smooth, decom- posable and --etterministic, larger number instances can solved when additionally, & is deterministic; and all 2AMC problems are tractable if we also impose X -ffirstness.
4.2 Causal Inference
In causal inference, one is often interested in computing interventional distributions, denoted using the do(-) operator, as a function of the observed distribution p. This function depends on the causal graph linking the variables, and can be derived using the do-caleulus (38). For example, the well-known backdoor and frontdoor graphs induce the following formulae:
p(y)do(x))
Σ p(z)p(yla,,))
If' the size of X is fixed, circuit always be rearranged to be X first with most a X blowup.

---

[g)]do(z))= = === E(()) p(a')p((1 p(a')p(pyaa
Assuming that the observed joint distribution p(X, 2) is given as probabilistic circuit C, we consider the problem of obtaining a probabilistic circuit C' over variables X U Y representing (({(do(X)) )). Tractability conditions for the backdoor//rontdoor cases were derived by [9),, with quadratic/cubic complexity respectively. However, we observe that in some cases we can avoid the requirement of structured decomposability and/or obtain reduced complexity relative to their findings.
In the backdoor case, it is known that structured decomposabillty and (X U Z) ddettemminn suffices for a quadratic time algorithm. This can be seen by decomposing into a compositional query:
P(U)
2 p(u)
2 T-1 H p(
where V = YX, Z). and (a) a if
0 a Assuming (X U -e-dttrmminism and structured decomposability, then T-1 ( (())) (V)) is tractable by (Det) and (Multiplicative), the product PVV) @ D P(V) by support-compatibliy and the final product by compatibility, However, if we additionally have Z-determinism, then the final product becomes tractable by support compatibility, This has linear rather than quadratic complexity, and does not require the circuit to be structured decomposable, In the frontdoor case,
(4) showed that X X-deterninism, (X U 2)- determinism, and structured decomposability suffices for cubic complexity. However, we note that under such conditions, the inner product p (X') @ p(Y Z) is tractable by support-compatibiliyy As such, the complexity of this query is actually quadratic rather than cubic as previously shown. We summarize our findings in Table and refer the reader to the Appendix for full proofs.
5 Related Work
Our work builds upon the observation that many inference problems can be characterized as composition of basic operators. Prior works have considered compositional inference for circuits in the Boolean [88 and probabilistic semirings 48 49 deriving tractability conditions for operators specific to these semirings. Aside from generalizing to arbitrary semirings, we also introduce extended composability conditions that enable interleaving of aggregation, products, and mappings. Mcanwhile, algebraic model counting [3) deals (implicitly) with mappings from the Boolean semiring to an arbitrary semiring, but does not consider compositional queries. Closest to our work, (29 consider a generalization of algebraic model counting that allows for an additional semiring translation; however, this still assumes input Boolean circuits and has incomplete tractability characterizations. Our framework resolves these limitations, permitting arbitrary compositional queries over semirings.
Many works have considered (unbounded) sums-of-products queries on arbitrary semirings (21 23 , encompassing many important problems such constraint satisfaction problems (7], graphical model inference [56). and database queries [52], which are often computationally hard in the worst- case. Algorithms for such queries often utilize compact intermediate representations and/or assume compact input representations, such as circuits [35 17 36 3]. Our framework focuses on queries where the number of operators is bounded, and characterizes conditions under which inference is tractable in polynomial time. It also includes elementwise mappings as key additional abstraction that can be used to express queries involving more than sums and products.
Conclusion
In summary, we have introduced a framework for analysing compositional inference problems on circuits, based on algebraic structure. In doing so, we were able to derive new tractability conditions and simplified algorithms for number of existing problems, including 2AMC and causal inference. Our framework focuses on simple and composable sufficient tractability conditions for aggregations, products and elementwise mappings operators; a limitation of this generality is these conditions may not be necessary for specific queries on specific semirings. Our work motivates the development of knowledge compilation and learning algorithms that target the requisite circuit properties, such as X --determinism. Finally, while we focus on exact inference, for many problems (e.g. marginal MAP) approximate algorithms exist and are of significant interest; an interesting direction for future work to investigate if these can be also be generalized using the compositional approach.
10

---

Acknowledgements
We thank Antonio Vergari for helpful discussions, and acknowledge him for proposing an early version of support compatibility and Theorem 3, and for pointing out a potential reduction in complexity for the causal inference queries. This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing. This work was funded in part by the DARPA ANSR the DARPA PTG Program under award HR001 12220005, and NSF grant S3ISS-1433411 DM received generous support from the IBM Corporation, the Center for Artificial Intelligence at University of São Paulo (C4AI-USP), the São Paulo Research Foundation (FAPESP grants #2019/07665-4 and 2022/02937-9) the Brazilian National Research Council (CNPg grant no, 30513//2022-4) and CAPES (Finance Code 001). YC was partially supported by a gift from Cisco University Research Program.
program under award FA88700-23-2-000
References
[1] Mahmoud Abo Khamis, Hung Q Ngo. and Atri Rudra. Faq: questions asked frequently. In Proceedings of the 35th ACM STGMOD-SIGACTSSIGA Symposium on Principles of Database Systems, pages 13-28, 2016.
[2] Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems 35 (NeurlPS), dee 2022.
[3] Antoine Amarilli and Florent Capelli. Tractable circuits in database theory. ACM SIGMOD Record, 53(2);6-20 20,06662222200 2024.
[4] Antoine Amarilli, Marcelo Arenas, YooJung Choi, Mikaël Monet, Guy Van den Broeck, and Benjie Wang. A circus of circuits: Connections between decision diagrams, circuits, and automata. arXiv preprint arXiv:240..09674, 2024.
[5] Fahiem Bacchus, Shannon Dalmao, and Toniann Pitassi. Solving# sat and bayesian inference with backtracking search. Journal of Artificial Intelligence Research, 34:391-44) 2009.
[6] Chitta Baral, Michael Gelfond, and J. Nelson Rushton. Probabilistic reasoning with answer sets. Theory and Practice of Logic Programming, 9(1):77-444, 2009.
[7] Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring- based constraint satisfaction and optimization. Journal of the ACM (JACM), 44(2):201-236, 1997.
[8] Oliver Broadrick, Honghua Zhang, and Guy Van den Broeck. Polynomial semantics tractable probabilistic circuits. In Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence (UAI), july 2024.
[9] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6):772-799, 2008
[10] Arthur Choi, Yexiang Xue, and Adnan Darwiche. Same-decision probability: A confidence measure for threshold-based decisions. International Journal of Approximatee Reasoning, 53
(9):1415-1428, 2012. ISSN 0888-613X. doi: /tt.a/////.....aee///////////330 Fifth
URL
https::/www.. sci www.iinneeed......mmmmmmmmeee... cww wwwo///cienccee/ooooommoeoeeoeee
European Workshop on Probabilistic Graphical Models (PGM-2010).
[11] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. arXiv preprint, 2020.
[12] YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group fairness by probabilistic modeling with latent fair decisions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12051-12059, 2021.
[13] YooJung Choi, Tal Friedman, and Guy Van den Broeck. Solving marginal map exactly by probabilistic circuit transformations. Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.

---

[14] Fabio Gagliardi Cozman and Denis Deratani Mauá. On the semantics and complexity of probabilisticc logic programs. Journal of Artificial Intelligence Research, 60:221-2643 2017.
[15] Adnan Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. Journal of Applied Non-Classical Logics, 11(1-2)11-34, 2001. doi: 10.3 166/jancc. 11.11-34.
[16] Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), (0033)28003055 2003.
[17] Adnan Darwiche. Sdd: A new canonical representation of propositional knowledge bases, In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
[18] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229-2000 264, 2002.
[19] Cassio P De Campos. New complexity results for map in bayesian networks. In IJCAI, volume 11, pages 2100-2106. Citeseer, 2011.
[20] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: probabilistic prolog and its application in link discovery. In Proceedings of the International Joint Conference in Artificial Intelligence (IJCAI), volume 7, pages 2462-2467, 2007.
[21] Rina Dechter. Bucket elimination: unifying framework for reasoning. Artificial Intelligence. 113(1-2):41-33) 1999.
[22] Vincent Derkinderen and Luc De Raedt. Algebraic circuits for decision theoretic inference and learning. In ECAI 2020, pages 2569 2576. IOS Press, 2020.
[23] Thomas Eiter and Rafael Kiesel. On the complexity of sum-of--roduue problems over semirings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6304-631 1,, 2021.
[24] Daan Fierens, Guy Van den Broeck, Joris Renkens. Dimitar Shterionov, Bemdd Gutmann, Ingo Thon, Gerda Janssens, and Lue De Raedt. Inference and learning in probabilistic logic programs using weighted boolean formulas. Theory and Practice of Logic Programming, (53))3588400) 2015.
[25] Robert Gens and Domingos Pedro. Learning the structure of sum-product networks. In International conference on machine learning, pages 873-880. PMLR, 2013.
[26] 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.
[27] Haiying Huang and Adnan Darwiche. Causal unit selection using tractable arithmetic circuits. arXiv preprint 4rXiv:2404.0668/, 2024.
(28) Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. Advances in Neural Information Processing Systems, 34:25134 25145, 2021.
[29] Rafael Kiesel, Pietro Totis, and Angelika Kimmig. Efficient knowledge compilation beyond weighted model counting. In Proceedings of the 38th International Conference on Logic Programming (ICLP 2022), 2022.
[30] Angelika Kimmig, Guy Van den Broeck, and Lue De Raedt. Algebraic model counting. Journal of Applied Logic, 22:42-62, 2017.
[31] Johan Kwisthout. Most frugal explanations in bayesian networks. Artificial Intelligence, 218: 56-73, 2015. ISSN 0004-3702. doi: https://doi.or/11.10011 101.///.........2000 art.
[32] Anji Liu, Honghua Zhang, and Guy Van den Broeck. Scaling up probabilistic circuits by latent variable distillation. In Proceedings of the International Conference on Learning Representa- tions (ICLR), may 2023.
12

---

[33] T. Lukasiewicz. Probabilistic description logic programs. International Journal of Approximate Reasoning, 45(2):288-307, 2007.
[34] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in neural informa- tion processing systems, 31, 2018.
[35] Robert Mateescu, Rina Dechter, and Radu Marinescu. And/or multi-valued decision diagrams (aomdds) for graphical models. Journal of Artificial Intelligence Research, 33:465-519, 2008.
[36] Dan Olteanu and Maximilian Schleich. Factorized databases. ACM SIGMOD Record, 45(2): 5-16, 2016.
[37] Umut Oztok, Arthur Choi, and Adnan Darwiche. Solving PP pp-complete problems using knowledge compilation. In Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning. 2016.
[38] Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-688, 1995.
[39] Robert Peharz, Robert Gens, Franz Pernkopf, and Pedro Domingos. On the latent variable interpretation in sum-product networks. IEEE transactions on pattern analysis and machine intelligence, 39(10):2030-2000 2044, 2016.
[40] Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp. Kristian Kersting, and Zoubin Ghahramani. Random aum-product networks: A simple and effective approach to probabilistic deep learning. In Uncertainly in Artificial Intelligence, pages 334-344, PMLR, 2020.
[41] Tahrima Rahman, prasanna Kothalkar, and Vibhav Gogate. Cutset networks: simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part II 14, pages 630-645. Springer, 2014.
[42] Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In International Conference on Machine Learning, pages 710-718. PMLR, 2014.
[43] Feras A Saad, Martin C Rinard, and Vikash K Mansinghka. Sppl: probabilistic programming with fast exact symbolic inference. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation, pages 804-819, 2021.
[44] Amir Shpilka, Amir Yehudayoff, et al. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends@ in Theoretical Computer Science, 5(3 4):2073388 2010.
[45] Pietro Totis, Lue De Raedt, and Angelika Kimmig. smProbLog: Stable model semantics in problog for probabilistic argumentation. Theory And Practice Of Logic Programming, 23(6): 1198-1247, 2023.
[46] Lestie G Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410-21, 1979.
[47] Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the tractability of shap explanations. In Proceedings of the 35th AAAI International Conference Artificial Intelligence and Statistics (AAAI 202 1), 2021.
[48] Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy den Broeck. A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference. In Advances in Neural Information Processing Systems, volume 34, pages 13189-13201, 2021.
[49] Benjic Wang and Marta Kwiatkowska. Compositional probabilistic and causal inference using tractable circuit models. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 9488-9498 PMLR, 2023.
[50] Benjie Wang, Matthew R Wicker, and Marta Kwiatkowska. Tractable uncertainty for structure learning, In International Conference Machine Learning, pages 23131-233 1-21100. PMLR, 2022.
13

---

[51] Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: Embracing neural networks into answer set programming. In Proceedings of the twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), pages 1755-1762, 2020.
[52] Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, volume 81, pages 82-90 22-94, 1981.
[53] Matej Zečević, Devendra Dhami, Athresh Karanam, Sriraam Natarajan, and Kristian Kersting. Interventional sum-product networks: Causal inference with tractable probabilistic models. Advances in neural information processing systems, 34:15019-15031, 2021.
[54] Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In Proceedings of the 40th International Conference on Machine Learning (ICML), jul 2023.
[55] Honghua Zhang. Benjie Wang, Marcelo Arenas, and Guy Van den Broeck. Restructuring tractable probabilistic circuits. arXiv preprint arXiv:2411.12256 2024.
[56] Nevin L Zhang and David Poole. A simple approach to bayesian network computations. In Proc. of the Tenth Canadian Conference Artificial Intelligence, 1994.
14

---

Algorithm 1: AGG
Input: Smooth and decomposable algebraic circuit C(V); node a e C; Subset of variables
W S vars(a))
Output: Node encoding Ow (V)
if a is input node then
return AGG- (o; W)
else if or is product or sum node and (ar) = W then return NEWNODE (= 1 (..aaaaa(::WWaas(aa))) if a is product else NEWNODE @+ (1 PAGG(a,;W)) 5 else a is product or sum node and W C (ar)(a:) then
return x AGG(a;; W vars(a;)) a is product else + AGG(A; W)
Algorithm 2: PROD-CMP
Input:
Compatible algebraic circuits C(V), (V")); nodes C, a' E C" s.t. vars(a) n (V n V') = vars(a') n (V n V"
Output: Node encoding (V(V) @ (V())
vars(a:) n vars(a") = then
return X a
3 else if a is product or input node and = +K' is a sum node then return + + PROD- CMP CMP((M az)) else if a are input nodes then
return PROD-INPUT(C) a')
else if a: a1 X 022 a' = a² ag2 are product nodes then
return PROD-CMP(a1, a PROD-CMP(a2, o4)
else if a: + + 04. a' a are sum nodes then
return + サ= PROD-CMP(a,, a')
A Algorithms and Proofs
In Algorithms we present algorithms for the aggregation, product (with compatibility), product (with
and elementwise mapping operators respectively (the initial call is to the root of the circuit(s)). the following, we present proofs that the algorithms soundly compute smooth and decomposable output circuits for the respective operators.
A.1 Tractable Aggregation
Theorem (Tractable Aggregation). Let be a smooth and decomposable circuit representing function p Assign(V) S. Then for any W C V, it is possible to compute the aggregate smooth and decomposable circuit C' (i.e., Po (Z) = m Pc (Z,. w)) in O((C1) time and space.
Proof. We prove this inductively, starting from the input nodes of the circuit. Our claim is that for each node C, AGG(a; W) (Algorithm 1 returns node a' with scope vars(a') vars(a:) \ W such that pa (vars(a')) = θ Pa (vars(a)). and is decomposable (if product) and smooth (if sum).
If a is input node (Lines D then this is possible by assumption; we denote this with AGG-INPUT the algorithm. Note that (ars ) = W, then this is just a scalar/constant (i.e. input node with empty scope).
15

---

Algorithm 3: PROD-SCMI
Input: Support-compaible algebraic circuits C(V). nodes a E C, C" ((a) = a'
Output: Circuit encoding PC @ pC (V))
if vars(a) O vars(a')
then
return a X a²
else if a' are input nodes then
return PROD-INPUT(a;CC) a')
else if ar (t X 022, a' = o'_ a2 are product nodes then
return PROD-SCMP(a1.dO a( x (R0D- ag)
7 else a = - return PRODPDSSSMPPPC a()
+ af are sum nodes then
Algorithm MAPPING
Input: Smooth and decomposable algebraic circuit C(V) over semiring S; Node O; Mapping functtin T + S
Output: Node encoding T(pc(V)
a is input node then return AAPPING-INPUT(CL)
3 else a is product or sum node then
return MAPPING(O r) a is product else MAPPAAPTNG(
If is a product node dn X a22 then by decomposability, W n vars(a)) and W O vars(a2) partition W. Thus we have that:
+ Pa (vars(a))
(Pos (vars(ai)) @ Pas (vars((<2))
(pa: (vars(a1)) & Pas vars(aa)))
Pay (vars(a1))
Pag (vars((22)
Tivars (cgg
Pano(o Wrwars(as) (vars(a1)
@ PAca( (rraassgg)))) (vars(az)) \ W)
The second equality follows by the partition (and associativity of the addition and multiplication), while the third follows by distributivity of multiplication over addition. In the case where vars(a) then Paca(a.; (W)as((a))) (vars(a;)) is just a scalar for each i, so we can directly perform this computation, returning new scalar node a'. Otherwise (Lines 5 6). we construct a new product node a' = of a² AGG(au; W A vars(an)) x AGG(o2; W O vars( By the inductive hypothesis, af has scope var)(a/) = vars(a:) W. so a' clearly decomposable and has scope vars(a') (vars(a)) W) U (vars(az) \ W) vars(a) W.
(Lines 3 4
16

---

If = + is sum node, then we note that by smoothness, vars(a;) = vars(a) for all i. Thus we have that:
+ Pa (vars(a))
Pas (vars(a))
Pa: (ax)s(a))
Pa; vars((:))
== w
Paca( w) (vars(a:))
==1
In the case where (ars(a) W (Lines) then Paco(o;:)) (vars(a:)) is just a scalar, so we can directly perform this computation, returning new scalar node a'. Otherwise (Lines we construct a new sum node a' = + + = AGG(a,; W). By the inductive hypothesis, each a¹ has scope vars(a:) \ W vars(a) W, so is smooth and also has scope vars(a) W.
==
A.2 Tractable Product
A.2.1 Tractable Product with Compatibility
Theorem 2 (Tractable Product Compatibility). Let C, C' be compatible circuits over variables V. V', respectively, and the same semiring. Then it is possible to compute their product as a circuit C' compatible with them (i.e., pc" (C (V (V) @ po (V')) in O(CC)|C")) time and space.
Proof. We prove this inductively bottom up, for nodes a E C, C such that vars(a) vars(a') n (V n V'). Our claim is that PROD-SCMP (a, a') (Algorithm 2 returns a node a" such that Pa" Pa Par, has scope vars(a") = vars(a)) U vars(a'), ) and is decomposable (if product) and smooth (if sum).
If vars(a) ) (avrs(a') 9 (i.e. vars(a)n
is empty), then the algorithm (Lines 1 2 simply constructs a new product node a" = a a'. By definition, Pa" = Pa 2 Pa', has vars(a) U vars(a'), and a" is decomposable.
scope vars(a")
cx, a' are input nodes, then we can construct new input node a" satisfying the requisite properties
(Lines 6
a is an input or product node and a' = + e is a sum node, then the algorithm constructs new sum node a" PROD- az). This computes the correct function Pa"
ok-n (pa @ Po;) = Pa @ (0) (0)=)ox)) Pa @ Par. Each child has scope vars(a) U vars(a))) =
vars(a) U vars(a'), so smoothness is retained.
Ifa = 0j X22, a' = af x are product nodes such that (Vrs()) vans("")"(VVVVVV) is
non-empty, then writing X= == Vnv V', by compatibility
also have vars(a; ) X vars(a))
and vars(a>) 0 x = vars a4)) X, so we can apply the inductive hypothesis for PROD-CMP(21,. and PROD-CMP (02, ab). Algorithm constructs new product node a" PROD-CMP( a1) x
PROD-CMP ).). To show that this is decomposable, we need the following lemma:
Lemma (Decomposability of Product). Suppose E C, a' E C' are decomposable product nodes which decompose in the same way over X, i.e. vars(a)) nx vars(a') n X and vars(az2 O X vars(as) n X. Then (vars(on) U vars(a()) n (vars(o2) U vars(a))) = 0.
Proof. We have that:
(vars(a1) U vars(a()) n (vars(az) U vars(a)))
(airs(a1) n vars(a2)) U (vars(a() O vars(a))) U (vars(a1) n vars(a))) U (vars(az) O vars(a())
17

---

Note that the first two intersections are empty due to decomposability of a, a'. For the third intersection (vars(a)) ) vars(a))), vars((()))) any variable in this intersection must be in the common variables X. But we know that vars(ag) n X = vars(a2) n X in both cases above; by decomposability. (vars(a)) n X) n (vars(o1) X)) = 0. Thus the third intersection also empty; similar argument applies for the fourth.
L
Applying this Lemma, we see that a" is decomposable as vars(PROD-CMP(a)) ,f)) ((1))(())) U
vars(a()) and vars(PROD-CMP(C) a()) (vars(az) U vars(a()). ) We can also verify that pa" (aa0-c @ PPaoo- PrRaD-CMP(02,.0)) = Paj 69 Pat & Pag @ Pag = Pa @ Pa by the inductive hypothesis, and associativity of @.
If
nodes, then the algorithm produces new sum node a" + j= PROD CMDD-M of) (Lines 7 8 This computes the correct function as Pa"
+ i- ai a' +
a $ /=1 PROD-CMP (MP(as; af) o 0 PorPa; (#/__Po.)) @o (#)=1Pat) Pa @ Pat It also retains smoothness.
The complexity of this algorithm is O(IC1IC")) because we perform recursive calls for pairs of nodes in C' and C".
A.2.2 Linear-time Product with Support Comptibility
Theorem (Tractable Product- Support Compatibility). Let C, C' be support cupport-compatibe circuits over variables V, V', respectively, and the same semiring. Then, given the isomorphism it is possible to compute their product as a smooth and decomposable circuit C" support-oopptible with them (i.e., PC" (V U U') =Pc(V) VV&a & pc (V')) in ((max(IC),))) (C time and space.
Proof. We prove this inductively bottom up. for nodes E C such that a' E C either satisfies a' i(a) or vars(a) vars(a') D. Our claim is that PROD-SCMP (a, a') (Algorithm 33 returns a node a" such that Pa Pa @ Pax has scope vars(a") = vars(a) U vars(a'), and is decomposable (if product) and smooth (if sum).
If vars(a) n vars(a') = 0, then the algorithm (Lines simply constructs a new product node a" a a'. By definition, Pa" = Pa @ por, has scope vars(a") vars(a) U vars(a'), and a" is decomposable.
If the a, a' are input nodes, then can construct new input node a" satisfying the requisite properties (Lines 3
a 01 X a' = 0a x oa2 are product nodes and s(a) = a', then the Algorithm (Lines 5 6 constructs a product node a" PROD-SCMP (a1,af,
(a1, o1) x PROD-SCMP (arz, o²)). Define X V
By support compatibility (i.e. X -suppport compatibility), a, a are part of the restricted circuits C(x), C'[X] respectively and so vars(a)) n X # 0, vars(a") n X * 0. There are two cases to consider; we first show that in both of these cases, we can apply the inductive hypothesis to PROD-SCMP (a1, a²)) and PROD-SCMP (a22, a²).
Firstly, suppose that both a and a2 have scope overlapping with X. Then by the isomor- phism, we have af = ((a1). a²² = ((2)). ). By the definition of support compatibility, this also means vars(on) n X = vars(a n X and vars(a2) x = vars(a)) n X and these are both non-empty; thus we can apply the inductive hypothesis for PROD-SCMP(Cr (a (a1,a)) ) and PROD-SCMP(a2, a().
Second, suppose instead that only on has scope overlapping with X, and so vars( 0. Then af = ((a1) ) and vars(on) n X = vars(af) n vars(a) n X = vars(a ) n. vars(a') \ vars(a(), it follows that vars(a2) X (vars(a') n (vars(a()) n XX) = 0, i.c. al also does not have scope overlapping with X. Since X are the shared variables V, V", it follows that vars(ag) n vars(a)) 0, and so we can apply the inductive hypothesis for PROD-SCMP(ag,C4 ab) (and for PROD-SCMP(aL,44) a()).
Since vars(ag)
By the inductive hypothesis. PROD-SCMP (a), has scope vars(an) U vars(a)) and PROD-SCMP(12) (02, a²) has scope var)( U vars(a)). We can thus apply Lemma [ Thus PROD-SCM SCMP(a1, a and PROD-SCMP an) have disjoint scopes and a" is decomposable. We
18

---

can also verify that Par = PeRnD-SCMP (a0-p(a0x @ (PROD-CCP(Mz..1) = Pas Po; & Pp, = Pa 8 Par by the inductive hypothesis, and associativity of @
a + o' +H=naa are sum nodes and e(a) = a', then by smoothness, all of the children of a have the same support and all the children of a' have the same support; thus all the children in C|X], [' respectively, k = k', and ((a;) af. By support compatibility, we also that (i) vars(a;) n X vars(a()) n X for all i; and (ii) that supp (a:) n supp (a¹) for i i j.
We claim that Pa: Pa; Og whenever i # j. To see this, recall the definition of X X-support: have that:
suppx (as) f E Assign( X n vars(a:)) By E Assign(vars((nn X) s.t. Pa, (x. y) + 0s suppx (a() = far Assign X n vars(a/)) By Assign(vars(cu X) s.t. Pa; (æ. y) + 0.)
Since X n vars(ax)= = X n vars(a') and is nonempty, by (ii) we know that there is no assignment of X n (ar)(aa) such that Pa: and Pat can be simultancously not equal to Og. Thus there is no assignment of X n vars(a;) such that Pa. @ Pat is not Og, since Og is the multiplicative annihilator.
Thus, the product function is given by:
Pa Pa
(Pa & Pot)
j=1
+ (Pas @ Paa))
PROD-SCMP o4)
The second equality follows by the Lemma and the fact that Og is the additive identity, and the third equality by the inductive hypothesis. Thus a" = + PROD-SCMP(a;;, af) computes the correct function (Lines & We conclude by noting that vars(a") U (vars(ax) U vars(a:)) U var)(as)
U
& 1= (as) = vars(a) U vars(a').
The complexity of this procedure applied to the root nodes is (max((C)) IC"l), as we only perform recursive calls for (i) a E C[X] and its corresponding node a' x(xx) and (ii) nodes with non- overlapping scope, upon which the recursion ends; so the overall number of recursive calls is linear in the size of the circuits.
A.3 Tractable Elementwise Mapping
Theorem 4 (Tractable Mapping). Let C. be a smooth and decomposable circuit over semiring S, and
T: T:S + S' a mapping such that r(0s) = Ogr, Then it is possible to compute the mapping of C by as a smooth and decomposable circuit C' (i.e., pcr = (V))(V)) in O((C)) time and space if distributes over sums and over products.
distributes over sums if: either (Additive) T is an additive homomorphism, i.e. T(a + b) (a) @ r(b); or (Det) C' is deterministic.
distributes over products if: either (Multiplicative) is multiplicative homomorphism, i.e. T = T()) @ (b)) or (Prod 0/1) r(1s) = 1g. and for all product nodes a = an x a2 E C, and for every value E Assign( (ars(a))) either pa, (U))s(a1)) {0s, 1s) Paz (Vvars(oz)) (0s, 1s).
Proof. First, let us consider sum nodes. Given any sum node a = + E C, we consider computing circuit representing
b Pop (vars(a)))
T [pa (pv(vv(((a))))
(5)
i=1
19

---

If (Additive) holds, then we immediately have that 7( Pa, (vars(a))) = -i_1 T(a.. (vars(a)))
by associativity of @D Alternatively, if (Det) holds, then given any v E Assign (oriign((vrs(()) (vars( there is at most one child, say aj. such that Pa, (v) + Og. Then have that
T 7 (w)) = (oo, (v) +
Pa: (u))
(=1,
k
= =Tapa (v) E
0.)
i= 1,igj
= =T(pa
=r(pa (v)) +
0g)
(Pa,, +
-0s))
=T(aa(o))
T T(Pa (v))
1=,,
T(Pa, (v))
and so again 7 T( Pa. (v)
+i T(Pa, (v)).
Second, let us consider product nodes. If (Multiplicatiie) holds, then we immediately have that
r - Par, (vars(a))) =f T(aa (vars(a))) by associativity of &. Otherwise, if (Prod 0/1) holds, then given any assign(vars(a))) there is at most one child, say aj, such that Pay (v) (Os, 1s}. Thus, we have that:
Pas (v) r
(po, (v) &
(p),(0)
X
Pa: (v)
==1,iff
=((aa (v)) 8
X
Pas (v)
i=1iio
= =T(pas(0)) 8
7 (Pas (1)
1=1.8
T(Pa, (v))
1=1
The second equality follows because
i=1. Pa. (v) E {Os, 1s), and we have that r(a 2 0s) = 1s = (a) @ r (1s) ) for any a E S. The third equality follows
Og: = r(a) @ ((0s) and (a & 1s)
as both T f Po. (v) and x , T (Pa, (v)) are equal to I iff no Po; (v) is Os. Thus,
we have that 7 2 1 Po. (v)
k -= T(p., (v)).
By applying these identities recursively to and product nodes, and assuming that can be applied tractably to input nodes, we obtain circuit C" such that pe: (V) = T T(pc (V)).
A.4 Tractable Composition of operators
Theorem 5 (Composability Conditions). The results in Table 7 hold.
20

---

the Imput Circuitis) are
Tractability Conditions
Det
X- X-Cmp w/ Cater
X-SCmp w/ Cabe
Complexity
Then the Output Circuit is
DDt
X-Cmp w/ Caher
X SCmp w/ Caher
Ageregation (W)
Sm AND Dec
W n
W =
W n
O[CI)
(5.1)
(5.5)
(5.9)
X-Det
X-Cmp w/ Cata
Cmp
N/A
O ((C]))))
Product
(5.2)
(5.6)
X-Det
X-C w/ Caba
X SCmp w/ Cater 0[nax([C),I1))
SCmp
(5.3)
(5.7)
(5.10)
(Sm AND Dec) AND
Elem. Mapping
(Add OR Det) AND
X-Det
X-Cmp w/ Cata
X- X-SCmp w/ Cate: (5.11)
O(C))
(5.4)
(5.8)
(Mult OR Prod01)
Table 3: Tractability Conditions for Operations on Algebraic Circuits. Sm: Smoothness, Dec: De-
composability; X X-Det(erminism), X X-Cmp: X X-Compatibility X-SCmp: Suupoot-Compatibiiiyy
Proof. We look at each property in turn, and show that they are maintained under the aggregation, product, and mapping operators as stated in the Table. For convenience, we reproduce the table in Table 3
with each result highlighted with number that is referenced in the proof below.
X-determinism Suppose that eircuit is X X-deterministic; that is, for any sum node a + -- a4 C, either (i) vars(a) n X = 0, or else (ii) supp (ax) n supp (a,) = 0 for all + j.
(5.1) Consider aggregating with respect to set of variables W such that W n X = 0. According to Algorithm| | and the proof of Theorem [ this produces an output circuit where each node o' corresponds some node in the original circuit, such that po = @wrvans(a) Po and with scope vars(a) \ W. In particular, for sum nodes a = = E C, either vars(a) S W, in which case a' is an input node (and X-determinism is not applicable), or else a' = +h 1 is also a sum node, where each of corresponds og. If (i) vars(a:) O X = 0, then vars(o')) n X 0 also.
If (ii) suppx (ax) n supp (ay) = for all i * j. we claim that supp (a() S supp (as) for all i. To see this, first note that by smoothness, vars(a() = vars(a() HupPx(a() Then there exists y; E Assign(vars(a") X) such that Pay (I;; ye) + Og. Since af corresponds to ai in the original circuit, we have:
vars(a'). Suppose that
a; E Assign(X X O vars(a') satisfies
Pa.. (Ii, yi, w.) = Pas (z, y) #g
ap E E.Assiggn W) (vars(a)
This means that there must be some w, E Assign W) n vars(a)) such that Pa, (z, yı. w:) + Os (since Og is the additive identity); thus x E supp (a.). To finish the proof, note that supp x (at) S suppx (a:) and supp x (a() C supp (ai) are disjoint unless i = (by X -edtterminism of a, i.c.
suppx (a:) n supp = / unless 1). Thus (ii) holds for a'. In either case, we have shown that a' is also X -ddeterministic.
(5.2) Consider taking the product of two compatible circuits C, C' over variables V, V', outputting a circuit C". According to Algorithm 2 and the proof of Theorem 2 every sum node a" e C" corresponds to either the product of (a) an input or product node
C and sum node """j" or (b) two sum nodes a + E C and a'= +/= E C", such that a" = +h +K" ag. Further, and a' have the same scope over the i= common variables V n V', i.e. vars(a) n (V V") vars(a') (an())))r)))) n (V n V*).
a' + E C", such that a"
Assume that C' and C" are both X -ddeterministic; then X S V V We note that since a, a' have the same scope over the common variables, they also have the same scope over X, i.c vars(a) vars(a') n X.
nx In case (a), X -edeterminism of a' means that either (i) vars(a') n X = 0 or (ii) supp (a!) n supp (a²) / for all i + j. If (i), then vars(a") n X (vars(a) U note that (a.") C supp (a/) for all j as & Og Os for any semiring S and S. Thus supp (a.) 0 supp (a")) = 0 for all i + j. Thus a" is X -determmnisstic.
= 0 also. If (ii),
In case (b), since a, a' have the same scope over X, either (i) holds for both a,, a', or (ii) holds for both. If (i), then vars(a") n X = (vars(a) U vars(a')) n X also. If (ii), then for any i, consider the restricted support supp x (a.)). Noting that vars(a:) vars(af)n vars(a"))
21

---

X by smoothness, we claim that suppx (a _ suppx (upp((as) n suppx (g)). Suppose that a E s (a)))) Then there exists some y E vars(a"))) ) X such that Paij (2, (2, = Pas, (2, Uvars(os))) x))
Paj (ar, )) ) * Os. This means that both Po: (ae, )v)a((a)))) (x) Pa, (2:, Vvars(a))) x) cannot be Os. and so x E supp (as) and æ E suppx(a), also. To finish the proof, we note that supp x (a - suppx (a:) Nsupp (at) and supp (amm)) S suppx (up))(ax) Nsupp x (a'm) are disjoint unless = 1,j = m (by X X-determinism of a and a'). Thus a" is X -e-etermiiisttcc by (ii).
(5.3) Consider taking the product of two support-compation outputting a circuit C". According to Algorithm 3 and the proof of Theorem 3 every sum node a" + + E C" corresponds to some sum nodes + 0; E C and a' = =+ E C" such that a² = =(aa), Pu." = Po, @ Paç, and has scope var)(a)) U vars(a'). Further, a and a' have the same scope over the common variables V n V', i.c vars(a) (V n V') = vars(a') n (V n nV).
circuits C² over variables V, V',
Assume that C' and C" are both X -ddeterministie; then X SVnV. V'. We note that since a, a' have the same scope over the common variables, they also have the same scope over X, i.e vars(a) n X = vars(a') n X. Thus, either (i) holds for both a,,', or (ii) holds for both. If (i), then vars(a") n X = (vars(a) U vars(a')) n X = @ also. If (ii), then for any i, consider the restricted support supp x (o Noting that vars(as) nX = vars(a))) = vars(a n X by smoothness, we claim that suppx x (a.") C supp (os) n supp x (at). Suppose that æ E supp x (a²). Then there exists some y E vars(o"") \ X such that Pap (x. y) Pau (x,, Yvvrs(a.))) ) @ Pag (ar, (vars(a())xx) x) A Og- This means that both po; (ar, Vvars(a,)) ). Pac (x,, (vars(a())) cannot be 0g, and so x E supp x (as) and æ E supp (aá) also. To finish the proof, we note that supp (a!") S supp (a;) n supp (a/) and supp, (a)) C suppx (ar) n supp supp)(a() (at) are disjoint unless = | (by X -ddeterminism of and a'). Thus a" is X -ddetemministic by (ii).
(5.4) Consider applying an elementwise mapping to circuit C, outputting circuit C". According to Algorithm and Theorem 4 every sum node a' = + E C" corresponds to some node = + 1= E C", such that Pa = T(Pa,, and further pa: = T(Pa.) ) and vars(a?) vars(a;) for each i.
Assume that C is X-deterministic. If (i) vars(a) n x= 6. then vars(a') (X = 0 also. Otherwise, (ii) suppx (as) O suppx (az) 0 for all * j. We claim that suppx (a!) E supp x (as) for each i. To see this, recall that elementwise mappings satisfy r(0s)
=
Og If x E supp x (a.). then there exists s.t. Paς (x, y) j Og. Since Pa; (2: y) = T T(Po, (I. y)), Po. (x, y) # Os. So x E supp (ax). To finish the proof, note that supp.. (a{) S suppx (as) and supp.. (ai) S suppx (az) are disjoint unless i (by X -ddeterminism of Q). Thus a' is X -etermiinistic by (ii).
X- X-comaatiilitty Recall that two smooth and decomposable circuits C, Cother over variables V. Vother are -coopatiible for X C <Vr n Vater if for every product node a = on X 02 E C and O'other = Olother,1 Oother,2 E Cother such that vars(a) n X = vars(a O X, it holds that vars(an) X = vars(Ctother ) n X and vars(a2) x = vars (ars((atheer))) N.
(5.5) Suppose that C, Cother are X X-compatible. We wish to show that Cothery C" are X X-compatible where C" is the output circuit from Algorithm that aggregates C over W, where W n nx 0.
Suppose a' = a¹ x dn E C' and Crother = Okother,1 X Ckother, E Cother are product nodes such that vars(a') n X = vars((arther) n X. Let = ai X a2 be the corresponding node in C such that
Po
θ v Pa- The scope vars(a') = vars(a) W; since W n X = 0. we have vars(a) n X also. Thus, by X-compatibility of C, Cothers we have that vars(an) n X vars (Ortee))))))))) 1) n X and var)(az) n X = vars(( n X. Since vars = vars(on) \ W and vars(a<) = vars (22) \ W. this means that vars(a() ) X (ars((aottier.)) nx and vars(a)) nx = vars (arthorot))).2)) n X. Thus C", Cotter are X- X-compatible.
X = vars(
(5.6) Suppose that C' over V and C' over V' are both X --compttible with Colheg We wish to show that Cother, C" are X X-compatible where C" is the output circuit from Algorithm 2 that computes the product of the two compatible (i.e. (V U -'ocomaaiiblll circuits C, C..
Suppose a" = of x a² E C" is a product node, and Olateer = Olycher,1 X Oluther,2 E Cother such that vars(a") X = (ars(( n X; we need to show that these decompose in the same way over X. By Algorithm [ and the proof of Theorem 2 this was created as the product of nodes 01 X 02 C' and a af al C" such that vars (V
22

---

vars(a') n (V n n') (and similarly for their children). Thus by (V U ccompatibblyyy of C, C", and a' decompose the same way over (VUV",, i.e (ars(a))((VUU)
= vV) and vars(o2) n (V U V vars(a)) n (V U V'). Since X S CVVV' (by definition of compatibility), this also holds over X, i.e. vars (01) 0 X = vars(a1) n X and vars(
n nx = vars(a)) n X.
Now, since (ar) = vars(a U vars and vars(aς) = var)( U vars(a (a)), we have that: vars(a") n X (vars(a) 0 X) U (vars(a') X) vars(a) n X
n (vars(a1) X) ) U (vars (a/) x vars(a1) n X
vars(aς) n (vars(ag) n X) U (vars(a/) n X) vars(az) n X
By compatibility of C, Cother, we have that vars )nx = vars(a)))x and vars ( n vars(a2) n X. Thus vars (lother ) n X = vars(an) n X and vars(aatherr) n X = vars( (al) n X. This shows X -compatibilityy of C", Cother.
Example 4 (Counterexample to (5.6) for Compatibility). While X -compatibilliy is maintained through multiplying compatible circuits, the same is not true for compatibility, due the different variable overlaps between the circuits. For example, suppose that C over variable sets A, B, C has product nodes with scope decomposing as
(A) x 2r2 A, B, D has product nodes with scope decomposing as a' a1 (A) x oly (B U D). Then these circuits are compatible (i.e. A B-compatible), and their product is circuit with product nodes with scope decomposing as a" = (A) x ( (UCUD, Now consider Cother with product nodes with scope decomposing as Olthhe Ot C) X Oc (). This is compatible with and o', bul not with a".
U C). and C' over variable sets
(5.7) This holds by the same argument as (5.6).
(5.8) The circuit C' obtained by applying an elementwise mapping to C does not change the scopes of any node. Thus, if C' is compatible with Cother. then C" is also compatible with Cother-
X cospppott Recall that two smooth and decomposable circuits C, Cother over variables V. Vother are X X-support-compatible for X C V O Vother if there is an isomorphism i between the nodes C[X] and Cater X). such that:
For any node a E C(X), vars(a) n X vars(:(a)) n x:;
For all sum nodes a = + E C[X), we have that supp x (ax) n supp (((s))) =
whenever i + j.
(5.9) Suppose that C, Cother are X sosppoottcommpaibll;; and let 'Cinn.C be the isomorphism from Cother X to C| We wish to show that Cother, C" are -ompppitt-ommpaiiile where C" is the output circuit from Algorithm] that aggregates C' over W. where W r x 0.
We define the isomorphism as follows. Consider the set of nodes Cx [X]. Since W V = 0, these nodes are not scalars and so are not propagated away by Lines 3 Moreover, since the algorithm retains the node types and connectivity of the circuit, there is an isomorphism lc,c' between C and C' X There thus an isomorphism CCater, := LC,0' &Cara between Cother [X] and C" [ It remains to show the two conditions.
Given node Outther E Cuther: let us write a := I.Cunnr. (aiathe)) and a' == (C) By X- support compatibility of Cathers C, we have that vars vars(Qother) n X = vars(a) X. By the proof of Theorem we know that vars(a') vars(a') ) n X as required. For the second part, suppose that these are sum nodes, that
vars(a) \ W. Since W n x 0, this implies that
i.. Clother + Oother, a = + and a' = = aŞ. We know by X- --support-coppatibiee x (Oeahher,)) supp (a,) = 0 whenever * j. By the same argument in (5.1), we have that supp (af) C suppx x (a:) for all i. Thus we can conclude that supp x (Qsther,)) O supp x (a²) = whenever i + j. So Cothers C" are X ---suppot-comppaibbee.
(5.10) Suppose that C' over V and C' over V' are both --support-compptiile with Cother; write C for the isomorphism from Cather [X to C, and CCrau.. for the isomorphism from Cather[ [X] to C". We wish to show that Cother, O" are X -sspppbtt-coppaiible where C' is the output circuit
23

---

from Algorithm 3 that computes the product of the two support-compatibe (i.e. (V U V*) suppoor- compatible) circuits C".
We define the isomorphism as follows. Consider the set of nodes C"[X) The algorithm for multiplying C, C" makes use of the isomorphism &C,c' between C[V V") and CVVV V'J with C"IV n V'J retaining the same connectivity and node types; thus there is an isomorphism cc,C" from CVV V'J to ["[V n V'J, also. Since X C (V n VV),, this isomorphism also holds between the circuits restricted to X. Thus, we define the isomorphism = 1C,C" &CCaar between Cother [ It remains to show the two conditions.
and C" [
Given a node Qotther E Cotner. let us write a := LCC.e. ((aoter) a' (C)c:(a) and a" == (c.c.((a), By X
of Cothers C, we have that vars (aothe)))he)) X vars(a) n X. By support-compatiiiltyy of C, C", we have that vars(a) n (V n (V)
vars(a') n (V O V') and so vars(a) X vars(a' 'n'nn - and both are equal to vars(a") (n since vars(a") vars (a)) (vv)ssss(())) (as in Theorem 3p. Thus vars(Ciother) 0 X = vars(a" ") X as required. For the second part, suppose + 5m1 a". that supp (Crother, i) n suppxx (az) 0 whenever + j. By (a") S suppx x (a) n supp (a'). Thus we can conclude that supp x (Clodher, O supp (a") = 0. So Cother. C" are X -sspport-compatibl.
that these are sum nodes, i.e. Olother + Olthher a = + + (4 a' + j + We know by X support-compatibile the same argument as in (5.3), we have that supp x
and
(5.11) Suppose that C, Cather are X- X-support-compatiile and &Cata.C be the isomorphism from Cother X to C[X]. We wish to show that Cother, C' are --suppootcooppatibne where C" is the output circuit from Algorithm 4 that applies an elementwise mapping T to C. Algorithm f maps each node C' to another node a' E C, keeping the node type and connectivity; this defines isomorphism 1C,C" from [ to C'[x], Thus we have an isomorphism CC == LC,C' O &CCoaa.C. remains to show the two conditions.
Given node Oother Cothers let us write a == (Co,c((aoter) and a' := (C.c)(a). By X- cupport-compatiiliig of Cother; C, we have that vars( n X = vars(a) n X. The map- ping algorithm does not change the scope of the nodes, i.e. vars(a') = vars(a)), so we have that vars n X vars(a') n X as required. For the second part, suppose that these are sum nodes, ie. Clother + Cother, & = + and a' = We know by X -support-compaaiilliyy that suppx (Olahhe,ss n supp (ay) 0 whenever + j. We know by the same argument as in (5.4) that supP (a²) S supp x (ax) for all i. Thus we can conclude that supp x (Qlothers)) O supp x (a)) whenever i # j. So Cother, C" are X -uspport-compptible
Theorem 7 (Hardness of 2AMC with X X-firstness). 2AMC is #P-hard, even for circuits that are smooth, decomposable, deterministic, and X X-first, and a constant-time elementwise mapping.
Proof. Take DNF with terms Φ1,..., Pm over variables XI,..., X,, Let [log m 1. Let us construct another DNF ø' with terms &1, .....,d &'m over variables xI..., X, and VI...., Y such that each of is the conjunction of o.,, Y1+1 and term over ..,..., Yi encoding binary representation of i. For example:
& Φ5 AY -t2 AY
.. -Yi YL-1-
Now, efficiently manipulate ø' to make it smooth [5] The circuit ø' is thus smooth, decomposable, deterministic and trivially satisfies X-firstness (since the children to every A-gate are literals). Take
the probability semiring as Sx, and Sy = (N2 +2, X2, (0. O), (1, 1)) and 7(n11 = n1 n1/n2 (define 0/0 0). Also, define w(z) 1, and w a'(Y41 literals. Then 2AMC counts the models of o, which is #P-hard [46]
0) (0. 1) and w'(y) = 1 for all other
E Eym -1 o'(x,))
2AMC = Σ
Σ dlx),
Σ (x
where we assume 0/0- = 0. The last equality follows because the circuit is deterministic (hence
E, x2 v) maxy dxx. y) < 1) and logically equivalent to ø (i.e., Vo o(x) 1 + By 6'(2,y) = 1).
Theorem (Tractability Conditions for 2AMC). Every 2AMC instance is tractable in O((CI) time for Boolean circuits that smooth, decomposable, deterministic, X firss, and X detterministic.
24

---

X1
X2
Xn
X.
Y1
Y/
Y,
(a) HMM graphical model
(X,
X2: U Y2:n
0.3
0.7
X U Yu-1in
X
(Nn-1. Yn-13
C1(0)
C1(1)
(c) Vtree
0.2
0.8
0.6
0.4
C2U)
C2(0)
C2(1)
[X; 5]
[Y
[
1]
(b) Circuit
(d) Component
Figure 4: Illustration of PC computing hidden Markov model (HMM)
Algorithm 5: 2AMC
Input: Decomposable, smooth, deterministic, X-first and X -deeterministic logic circuit C over X U Y. weight eircuits wx wy, semirings Sx, Sy, mapping function TSy++x
Output: 2AMC value (scalar in semiring Sx).
Csy (X,
Y) f- MAPPING(C X, Y): [lB-sy))
Csv aay
X Y) + PROD CMP
( Csy X, Y), wY)
3 Cy X AGG(Csy ay (X,
Y)
X MAPPING(Co (Csy Sy way (X) TSY -5x
OSX wx
X)
f- PROD PROD-CMP(CC (Ms
),wx)
Result: AGG
( WY wx ux (X); X)
Proof. In Algorithm 5 we show the algorithm for 2AMC, which is simply composition of aggrega- tions, products, and elementwise mappings. To show tractability of 2AMC, we simply need show that the input circuits to each of these operators satisfy the requisite tractability conditions.
We start with smooth, decomposable, deterministic, X X-deterministic, and X -ffirst circuit C(X, Y).
In line I we use the support mapping (Definition from the Boolean to Sy semiring; this is tractable by Corollary due to determinism, and the output Csy (X.Y) retains all the properties by Table
In line 2 we take the product of Csy (X, Y) and w (X). wxx is omni-compatible, so we can apply PROD-CMT CMM. This results eircuit Cyywyl (X, Y) that smooth, decomposable and X -frsst (XX is both deterministic and X -deterministic as it has no sum nodes, so this output circuit also deterministic and X -deterministic by (5.2).
line 3 we aggregate Csy.ay (X, Y) over Y. The output circuit Csy (X) is smooth and decomposable. It is also X -determministic by (5.1), Y n 0.
25

---

Since OSy wy (X. Y) satisfied X f-firstness, each product node a1 X dg in that circuit had most one child (say an) with scope overlapping with Y Then, the product the previous step, (2 must have been produced through Lines 12 (otherwise it would contain some variable in Y); thus it was produced by applying s- to some node in C. Thus, for any value E Assign(az)) Pas E {0sy 1sy J. So (Prod 0/1) is satisfied.
In line 4 we apply the mapping +5x to wy (X). This circuit is over X and is X -ddeterministic, i.c. deterministic and satisfies (Additive). As shown in the previous step, also satisfies (Prod (V1). Thus the mapping algorithm produces the correct result, producing a smooth, decomposable and determinsitic circuit Csx wx (X) as output.
In line 5 we take the product of CSx, wY (X) with wx (X). wx is onni-compatible so we can apply PROD-CMP, producing a circuit CSx wa sxx that is smooth and decomposable (and also deterministic).
Finally, we aggregate Osx wx
(X) over X, producing scalar.
Theorem 9 (Exponential Separation). Given sets of variables X (X1, Xn), (Y,,.., Yn there exists a smooth, decomposable and X d-dtermmiiistic circuit C of size poly(n) such that the smallest smooth, decomposable, and X -frsst circuit C' such that PC = Per has size 20(m)
Proof. Consider representing the distribution given by hidden Markov model (HMM) (hidden) variables Xen = {X1,--., X,, and (observed) variables Ygn = (Y,,.., Yn }. as depicted in Figure
4a Figure 4b shows structured decomposable circuit that computes the hidden Markov model
distribution, where the components C₂(5) have scope {X,, YiJ. The corresponding vtree/scope-
decomposition (with nodes notated using their scopes) is shown in Figure 4c| can easily be checked that the circuit is X -et-eemtrmiiiiiccc and that the circuit size is linear in 71
It remains to show that the smallest X=x--ixi first and X deterministic circuit computing the HMM dis- tribution is exponential in size. Explicitly, we will choose a HMM such that the emission distribution given by x)) I = Then we have that per (I Ysn) pe (I )pC (=(())))== PCr (xrg))))) I Yg. =ag." for any circuit C" that expresses the distribution of the HMM.
Consider any such circuit C". Then, let (ai,..., agk } be the set of nodes with scope Y in the circuit. We will need the following lemma:
Lemma 2. For any value ven of X there exists constants C1,.,, CK RR20 such that:
pe (# Ysn)=
Σ CkPan (Ysa)
(6)
In other words, the output of the circuit is linear function of the nodes with scope Ygn-
Proof. We show this proof by bottom- up induction (child before parent), for the set of nodes whose scope contains Ysn:
Input node: the scope is Yzn. then it must some node a E o; then we take C₁ = 1 and Cr. for all K + k.
By smoothness, all the children must have the same scope (containing Ys.). The sum node is then just linear combination its children, so the result holds by the inductive hypothesis.
Sum node:
Product node P: Let P1, P2 be the children of P. By are pure (have scope entirely contained in X or Yzn), or one them is pure, and the scope of the other one (say Pi) contains Ysu.
either both children
In the first case, if there exactly one node (say Pi), with scope contained in Yzn- then must have scope exactly Yz.. Then we have that:
pp(0 Ysn) PP (Y (25n (2))
26

---

PP, (Tga O vars(P2)) here is constant, so by the inductive hypothesis we are done. If both nodes have scope contained in Ysn. then P in a, say ag. Then we set c₁: 1 and CK' = 0 for k * k.
In the second case, we have that:
pp(#gn, Ygn) pp, (Fgn n Y n vars (2))
(sn)
Here PP, (Fgn n vars (P2)) is constant, so by the inductive hypothesis we are done.
Note that Xgn firstness was crucial to avoid the case where product has two mixed nodes (containing variables in Xgn and Ysn) as children.
For any l: I,.., K, define v/ TR to be the vector with entries Uk,i ark (where we interpret i as value of Ysn). Then we have the following Corollary:
Corollary 2. The ser of vectors {ui...., 2K forms spanning set for IR?".
Proof. By the Lemma and the fact that C2 expresses the HMM distribution, we have that for any Tgnn E {0, 1)", there exists CI..., E 220 such that:
(a
CaPan
Rearranging, and writing in vector form, have:
Ck
ergn
Uk Pa (xgg)
where Eaga E ER is the standard basis vector corresponding to the value Tga Thus {Ui, Uk is a spanning set.
Any spanning set for R² must contain least 2n elements. Thus, K 2", and the circuit C' must be exponentially sized.
One might attempt to remedy the situation by replacing X-firstness with X -ddeterminism. For the general case, that however is insufficient:
Theorem 10 (Hardness of 2AMC with X --determinism) 2AMC is #P-hard even for decomposable, smooth, deterministic and X -determmiissicc circuits, and constant-ting elementwise transformation function.
Proof. By reduction from the counting version of number partitioning: Given positive integers k,,..., kn, count the number of index sets 5 C (1...., n. such that Exes hi = Eies ki = That problem is known be #P-hard 47 Define o A +> Y.). Then & is deterministic. X-deterministic, decomposable and smooth circuit
f Let the inner labeling function be w/ w'(y:) ks/c and w' (-),))= = 1. Then for a fixed configuration of the variables X {XI...., X. we have exactly one model for d whose value = If we select the inner semiring so that & is addition (c.g., the max tropical semiring or log semiring), then the inner AMC problem returns Exs,= ks/c, which equals 1 iff S {i x; 1) a solution to the number partitioning instance. Now, define the outer labeling function be w 1, and let the transformation function be T(s) = if s = 1 and r(s) 0 otherwise. Then the 2AMC problem with the probability semiring as outer semiring counts the number of solutions of the number partitioning instance
'While this circuit is not X first, it does satisfy property known as X Xifirtnesss modulo definability 29 thus that property insufficient for 2AMC together with X --dtterminism.
27

---

Table Tractability Conditions and Complexity for Compositional Inference Problems. We denote new results with an asterisk.
Problem
Tractability Conditions
Complexity
PASP (Max-Credal)"
Sm, Dec, X-Det
O[CC))
2AMC
PASP (MaxEnt)", MMAP
Sm, Dec, Det, X-Det
O[C])
SDP
Sm, Dec, Dct, X-Det, X-First
O((C))
Sm, Dec, SD, (X U D-DDet
Backdoor
Causal Inference
Sm, Dec, Z-Det,
D-De
O(CC)
Frontdoor
Sm, Dec, SD,, X -DDet, (X UZ--Det
MFE'
Sm. Dec, H-Det, -Det, (H U (U DeDt
O((C))
Other
Reverse- MAP
Sm, Dec, X-Det
O((C))
B
Case Studies
In this section, provide more details about the compositional inference problems in Table (reproduced Table(4) for convenience, and prove the tractability conditions for each (Theorem [). For all of them, assume that would usually come from knowledge compilation from some source language such as Bayesian Networks [9] or probabilistic logic programs [24]: our results thus show what properties the compiled circuit must have in order a query of interest to be tractable. Note that the problems are generally computationally hard 19 I0] on the source language, which means there do not exist compact circuits satsifying the properties in the worst-case.
given Boolean formula represented circuit. That
Theorem (Tractability of Compositional Queries). The results in Table 2 hold.
B.1 2AMC Queries
Firstly, we consider instances of 2AMC queries. Recall the general form of a 2AMC query. Given a partition of the variables V (X, Y ) Boolean function o(X,, Y), outer and inner semirings Sx,Sy Sy, labeling functions wy Y
Yey (X;) over S and w (X) X x,ex wx,(X,) over S', and an elementwise mapping TSy SY + Sx. the 2AMC problem is given by:
Try Sx
+
Lo s) @ ww()) @ (x)
revisited)
in
By Theorem any 2AMC problem is tractable if ø is given as a smooth, decomposable, deterministic, X dedeterministic, and X X-first circuit C. However, in some instances, relax these conditions, as we show shortly.
B.1.1 Marginal MAP
In the Marginal Maximum A Posteriori inference (MMAP), we are given a Boolean function ((V). (unnormalized) fully factorized distribution p( v(V) 11. (V:), partition X U V and some evidence e on É C V. The goal to compute the probability of the maximum probability assignment of X consistent with e:
max p( X =
= x
max d
Σ I
=/= YIne
To cast it as 2AMC problem, take the inner semiring Sy be the probability semiring and define the inner labelling function to assign wy (Y;) = 0 if Y; E and Y, is inconsistent with e and wy (Y,) (Y;) otherwise. The outer semiring is the (max, semiring with labeling function wx (X,) = 1. The elementwise mapping function TSy (a) = is the identity function.
The proof of the tractability conditions follows Theorem 8 except that we note that the mapping function -Sx from the outer to inner semiring satisifies (Multiplicative). As such, we do not need the (Prod 0/1) circuit property, which the reason needed the X X-firstness condition.
28

---

B.1.2 Probabilistic Answer Set Programming (PASP)
The Probabilistic Answer Set Programming Inference (PASP) query takes Boolean formula oi (V)). a partition X YY = V. a (unnormalized) fully factorized distribution p(X) = P(X,) and query
variable and value {Q= = q), for some Q V. The goal is to compute:
p(Q = 0) = II p(())
Σ
('(1)2))
The function (Y X) depends on the semantics adopted. Let (Y := {y the set of assignments of Y such that di ()x,)) .) is true. In the Maximum Entropy Semantics (MaxEnt) 6151 45]. one distributes the probability mass p( ()) uniformly over the models of e consistent with X, i.e. Xx)
( y)} be
imod(Y [I On the other hand, in the Credal Semantics B3 14 (Max-Credal)
one places all probability mass pl X) on some assignment y of Y consistent with X and q. To obtain an upper bound on the query probability regardless of which y is chosen, one sets p" (3/ XX) := 1 for all if there exists an assignment Y ( Y) A 9. and p" p' (Y
otherwise.
The 2AMC formulation of the problem uses the probability semiring as outer semiring Sx, with labeling function w (X;) = p(X,) for X; X.
In the (MaxEnt) semantics, for the inner semiring, we take as the semiring of pairs of naturals Sy (N2, +. (0, 0), (1,))). with coordinatewise addition and multiplication. The inner labeling function sets (Q) = (Iq=q: 1), and sets wy (Y:) (1,1) for all other variables Y; E Y. The mapping function is defined by TSy ((a, b)) = a/b (with
0/0- = 0).
In the (Max-Credal) semantics, we simply set the inner semiring to be the Boolean semiring
T if if = and sets wy (Y;)
SY = B. The inner labeling function sets wy (Q)
otherwise
T for all other variables Y, E Y. The mapping function is defined by TSy (a) [a]]sx-5xx
As with marginal MAP, we can see that in both cases, the mapping function - satisfies (Multiplicative)), X X-firstness of the circuit is required. In particular, for (MaxEnt) have TSr ((a, b) @ (c, d)) = TSy-Sy ((a-c, b-d)) = bd = f. TSx (a, -Sx (c. d) = TSy (a, b) @ TSy (c, d) (this holds also if (a, b) (0, and/or (c.d) (0, 0)). Meanwhile, for (Max-Credal) we have TSy (a 8 b) Tay Sx (a A b) [a A b] = [a]ss -S
[blsy-Sxx - -Sy (a) TSY (b) = -S (a) @ TSY (b).
For the (Max-Crec) Credall semantics, we note additionally since Sy is just the Boolean semiring, we do So the only conditions required are smoothness, not need determinism in Line of of Algorithm |
decomposability, and X --determmism.
B.1.3 Same-Decision Probability
In the Same Decision Probability (SDP) query B77, we are given a Boolean formula o( (VV). a fully factorized distribution pVV)= = =II p(V)), partition X, (Y) of V. a query {Y = y), some evidence on subset E C X of variables and a threshold value T E (0. 1]. The goal is to compute confidence measure on some threshold-basee classification made with the underlying probabilistic model:
Σ p(alee
To cast this as a 2AMC instance, we use the inner semiring S' = = + (0, (1, 1)), with coordinate- wise addition and multiplication. The inner labeling function assigns wy (Y) = (p(Y)Ly= = p(Y)). The outer semiring is the probability semiring and the mapping TSy from inner to outer semirings is -Sx (la, b)) = [a 2 bT]. Last, the outer labeling function assigns wx (X,) e if X, E E. and wx (X,) p(X,) otherwise.
Unlike marginal MAP and PASP inference, there is no special structure in SDP that allows us to relax the general tractability conditions for 2AMC. However, it is still 2AMC instance, and we have the tractability conditions from Theorem g particular this justifies the use of X -coostrriined sentential decision diagrams for this problem.
29

---

B.2 Causal Inference
In Section 4.2 we discussed computing causal interventional distributions. In particular, in the backdoor and frontdoor cases, we had the following formulae:
p(y]do([=))
Σ p(z)p(yla,
ply)do(x)) = = p(= (x)
Σ p( ((x))p(ylx',z))
(3)
B.2.1 Backdoor query
The backdoor query can be written as compositional query as follows:
BACKDOOR(p: æ. y) ① p(u) @ p(v) @ T-1 - p(v) p(v)))
if a + Note that T-1 satisfies (Multiplicative),
where V = (X, Y,K, Z), and 1-)
if aa==0 0
and so for this mapping to be tractable we just need the circuit it is applied to to be deterministic.
Assume that p(V) is given smooth, structured decomposable, and (X U Z -determinnistcc circuit (over the probabilistic semiring). We now show that this query is tractable, by showing that each operator in the composition is tractable. For readability, we label each circuit constructed with the function that represents [oxedd )
pXX, Z) C1(X, 2) == AGG(C, Y) is tractable by smoothness and decomposability. By (5.1) in Table
since Y n (X U Z) = C₁ is (X -ddetermniiittcc (i.e. deterministic). (x Z) == MAPPING (1,, r-1) ) tractable since C1 deterministic.
p
pYY| Z) C3 Y, Z) PROD MOMD-SCMP(C(XX
C2(, Z)). C (XUZ) Z Z)-
support-compatible with itself as is (X U -)-dtterministic = C is also (X U Z)- support-compatible with C₁ by (5.9) - C is also (X U --ssupport-compple by (5.11). As C and C2 share variables (X u Z), this means they are support-compatibe. Thus this product tractable in linear time.
with C2
z C. = AGG X U Y) is tractable by smoothness and decomposability.
( X Z) Cs 2) = PROD PROD-CMP(C4: C3). C is V-compatible with itself
(structured decomposable) = C c-oopptiblle with itself by Proposition I
C
is also Z-compatible with C₁ by (5.5) = C₁ is Z-compatible with C1 by (5.5) =
C1 is Z-compatible with C2 by (5.8) = C4 is Z c-oopatible with C's by (5.6). Since C₁ and C3 share variables Z, this means they are compatible and so this product is tractable in quadratic time.
x) C,(X, (=))))(Y)
= AGG(Cs, Cs2 Z) is tractable by smoothness and decompos-
ability.
Thus, we have recovered the tractability conditions derived by 44 with the same complexity of O((C)2 (induced by the compatible product to construct C²)). However, we also have an alterna- tive tractability condition. Suppose that C' were additionally Z-deterministic. but not necessarily structured decomposable. Then we could replace the derivation of Cs above with the following:
(( Xx Z) Cs(X,Y, Z) == SCMP (C4, C3). C' is Desupport-compatiee with Ca by (5.9)
with itself as is detterministic = C is also 2-support-compatiin
+ C4 is Z-support-comparibe with C by (5.9) = C4 is Z-compatible with C₂ by (5.11) = Ca Z-coppatible with C3 by (5.10). Since C2 and C3 share variables Z. this means they are compatible and so this product is tractable in linear time.
In this case, the overall complexity is also reduced to O((C)).
30

---

B.2.2
Frontdoor query
Now, consider the frontdoor case. In this case, we have the following compositional query:
FRONTDOOR(p; x, y, y,
p(o) @
- v.z
p(v)
& BACKDOOR(p; 2, v)
(8)
Assume that PVV is given as smooth, structured decomposable, XX -ddeterministic, and (X Z)- deterministic circuit (over the probabilistic semiring). We continue the analysis from the backdoor
case:
(x = AGG Y Z) tractable by smoothness and decomposability. By (5.1) in Table 3 since (Y Z) X 0, C7 is X --dttemministtcc (i.c. deterministic).
p(X)
(x MAPPING(Cr, T-1) is tractable since C7 deterministic.
p(X)
Co(X z) PROD PROD-SCMP(Ca, C1). C' X X-support-compatibe with itself as it is X -ddeterministic = is X --suppott-compatible with C1 by (5.9) = C1 is X --support-copptiibl with C7 by (5.9) = C₁ is X-support-compatibe with Cs by (5.11). Thus this product is tractable in linear time.
X
(( æz, Z) Cio(Y, Z). This is just like Co. but with variables X and Z swapped. Thus it is tractable for smooth, X X-deterministic and (X U -edttermniiist circuit in linear time.
X En. p(x))p(Y Z)
Cn Y, Z) := PROD PROD-CMP(Cg, Cio). We can chain
applications (5.5), (5.7) and (5.8) similar way to the other steps to show that Co, Cio are Z-compatible (i.e. compatible), so this product is tractable in quadratic time.
Σ. p(= Ens p(x') (Y ()) Ci2 Y) = AGG Z)- This tractable by
smoothness and decomposability.
Thus, this algorithm has complexity O((C)*, as opposed to the O(IC's) complexity algorithm in The key difference that we exploit support compatibility for linear time product when constructing C19.
49
B.3
Other Problems
B.3.1
Most Frugal Explanation
In 31), the most frugal explanation (MFE) query introduced. Given a partition of variables V
into (H, I+ I I- E), some evidence e E Assign( E), and a probability distribution p(V), the MFE query asks for the following:
Σ 1h E arg max p(h',
max h
In words, we want the explanation (assignment H) that is the most probable for the most number of assignments to I- when I+ is marginalized out. We can rewrite as follows:
p(h, i max p(h' i (
max h
Σn
(10)
This can be written as a compositional query as follows.
(As .e1) @ p(h, [,,e, (,)
+ TS!! S ① TS"-4S" T-1
TS"
(11)
h
where S is the probability semiring, S' is the (max, -emiiiing S" is ( 1], +, .0,1) (i.e. the probability semiring with domain [0, 1). and S" the counting semiring +. 0, and the mapping functions are defined as follows:
31

---

(a) =
(8)))(())
T-1(a) a
if + 0
-
TS"+s"((a (a) = 1==1 TS (a) a
Suppose given probabilistic circuit representing p [ ,). While this query appears extremely intimidating at first glance, we note that the only operators we need to consider are the mappings and single product. Note that all of these mappings satisfy (Multiplicative) (TS"-S") because the domain of S" is [0, 1] so Tg" (a b) = iff = b = 1); thus the mappings are tractable if the input circuits are deterministic. By checking the scopes of the inputs each mapping, -etterminism, and H -ddeterminismm suffices. This also enables tractability of the product in lincar time by support compatibility.
we can see that (H U [-] J
I
No tractability conditions for exact inference for this query were previously known. While the motivation behind the MFE query is means of approximating marginal MAP, and so this exact algorithm not practically useful in this case, this example illustrates the power of the compositional framework to tackle even very complex queries.
B.3.2 Reverse MAP
Recently, (27] the reverse-MAP query was introduced, defined by:
max p(e: X 62)
(12)
where the variables are partitioned as (E1, E2, X, H). In our compositional framework, this can be written as:
TP-M + p(e1 x, e2, h) T ① h.e
plen, x, e2, e2,
(13)
Here, the mapping T-1 tractable if the circuit for p is X -ddeterministic. Since p is X --deterministic, with itself; chaining this with (5.9) and (5.11) in Table 3 the inputs the product are X X-compatible; since they have scope X, this means the product is tractable by comport-cmmaatiiilit.. The resulting circuit remains X -ddeterministic (i.e. deterministic as the scope X), which means that the mapping T from the probability to (max, -) semiring is tractable. Thus, this query is tractable for smooth, decomposable and X deetermiiistic circuits in linear time (same as derived by the authors).
it is
32

---

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:
The abstract and introduction reference the results in the rest of the paper.
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 in 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.
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: Yes, in the conclusion we discuss the fact that while our results provide simple and general sufficient tractability conditions, these are necessary conditions.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

Yes, assumptions are laid out in the statements of the results, and proofs are provided in the supplementary material.
Justification:
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 in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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 properly referenced.
4. Experimental Result Reproducibility
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 of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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 all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
34

---

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 NeurIPS code and data submission guidelines (https://nips.cm
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppullc//uuuii wwwiiicgguie//eeeeeeeeeic CoodeSubeiiieeeec ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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 (e.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 contain 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 contain 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, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
35

---

It 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 enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does 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 compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The paper does conform to the NeurIPS Code 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 to preserve anonymity (e.g., - if there is 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: [No]
Justification: application/depllymentt there are no particular societal impacts that feel need to be
This paper presents foundational research that is not tied to any particular
highlighted.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal 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.
36

---

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 are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The paper does not propose to release any data or models that would pose such risk.
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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package 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 (e.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 Datasets.paaersstt paperswi thcode. cow/ datasets package should be provided. For popular 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.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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. Crowdsourcing 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 crowdsoureing 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 in the main paper.
According the NeurIPS Code of Ethies, 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 research with human subjects.
Depending on 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 we 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 as the institution conducting the review.
38


Reviews:
[{"review_id": "MMMN2eX25e", "reviewer": "Reviewer_x2Dq", "summary": "They investigate algebraic circuits on semi-rings (with sums and products).\nThey give criterions that allow efficient combinations of circuits and aggregation of the variables of one circuit (e.g. the sum over all inputs of the circuit).\nThey give algorithms and hardness results for Algebraic Model Counting.", "questions": "what is an \"atlas\"? the word is never used in the text\n\n\nthe classic circuit classes have an uniformity constraint, on the complexity of an algorithm that computes the circuit for a certain input length.\ndo these algebraic circuits not need uniformity ?\n\n\n>Theorem 2 \nwhy not just add one new product node as root node, and then make both C and C' children of this new node.\nit is a much simpler construction and would also compute the product.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "they give an unified view on different important problems which I did not expect to be related\n\nfoundamental research\n\nefficient algorithms\n\nwell-written", "weaknesses": "a lot of technical definitions\n\nthe conditions under which the algorithms are efficiently applicable seem rather restrictive", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">the conditions under which the algorithms are efficiently applicable seem rather restrictive\n\nWe agree that the sufficient conditions for tractability of many compositional queries can be strong. However, part of our contribution is that our framework is able to derive weaker tractability conditions than were previously known. For example, we show that $\\textbf{X}$-firstness is not necessary for probabilistic answer-set programming inference (under the max-credal or max-ent semantics), and that this can lead to exponentially smaller circuits (Thm 9). \n\nDespite the high complexity of these problems, there already exist tools for compiling or learning circuits satisfying these properties (e.g. PySDD [a] and PSDD [b, c] for $\\textbf{X}$-firstness and $\\textbf{X}$-determinism, MDNets [36] for $\\textbf{X}$-determinism). We believe that our work should motivate further study on compilation and learning algorithms for circuits satisfying these properties, given the generality of these properties across multiple inference tasks. j\n\n[a] Meert \\& Choi (2017) *PySDD.* In Recent Trends in Knowledge Compilation, Report from Dagstuhl Seminar 17381, Sep 2017.\n\n[b] Kisa et al. (2014) *Probabilistic Sentential Decision Diagrams.* In KR.\n\n[c] Liang et al. (2017) *Learning the structure of probabilistic sentential decision diagrams.* In UAI. \n\n>what is an \"atlas\"? the word is never used in the text\n\nWe use \"atlas\" to refer to the collection of operations and corresponding tractability conditions we derive (Table 1); it also refers to a closely related recent work [35] that considered compositional inference for probabilistic circuits.\n\n> the classic circuit classes have an uniformity constraint, on the complexity of an algorithm that computes the circuit for a certain input length. do these algebraic circuits not need uniformity ?\n\nIndeed, for Theorem 9, we use a family of algebraic circuits $C_1, ..., C_n$ to specify functions, such that the smallest $\\textbf{X}$-first circuits have an exponential lower bound on size. This family is indeed logspace-uniform; note however that we don't make any claims in terms of membership of languages in complexity classes, merely on the size of the circuits computing the function. We will make this point clearer in the revised version.\n\n> Theorem 2 why not just add one new product node as root node, and then make both C and C' children of this new node. it is a much simpler construction and would also compute the product.\n\nThis is possible, but the resulting circuit would not be decomposable if $C$ and $C'$ share variables. As the queries we (and the majority of other works in the knowledge compilation/tractable model literature) consider require aggregation subsequent to products, we restrict to algorithms producing decomposable and smooth circuits.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i2IznV9yW3", "reviewer": "Reviewer_41Ra", "summary": "The paper presents sufficient conditions under which certain problems (e.g. 2AMC are tractable when performed on circuits.", "questions": "Could the authors comment on the two points I raised under \"weaknesses\".", "limitations": "covered.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well-written and technically sound. It also makes a solid effort in trying to unify tractability conditions in the context of algebraic circuits.", "weaknesses": "1) My main problem with the paper is that it only discusses sufficient conditions (also acknowledged by the authors). This is constrast to teh probabilistic circuit atlas [1]. This in itself is not a problem, however, the paper does not discuss the problem of eighted model integratio, which has also been formulated as an AMC problem with integration as an extra operation [2]. In general WMI is intractable, however, it has been shown that there exist tractable fragments [3]. If I understand the paper correctly, the tractable fragment of WMI does not fall within the proposed framework. This is quite limiting as the framework does not even cover all tractable problems that can be formulated as 2AMC.\n\n2) Tractable algebraic circuits seem to be highly related to performing tractable inference on first-order circuits. [4] This relationship is not discussed at all.\n\n\n[1] Vergari, Antonio, et al. \"A compositional atlas of tractable circuit operations for probabilistic inference.\" Advances in Neural Information Processing Systems 34 (2021): 13189-13201.\n\n[2] Dos Martires, Pedro Zuidberg, Anton Dries, and Luc De Raedt. \"Exact and approximate weighted model integration with probability density functions using knowledge compilation.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.\n\n[3] Zeng, Zhe, et al. \"Probabilistic inference with algebraic constraints: Theoretical limits and practical approximations.\" Advances in Neural Information Processing Systems 33 (2020): 11564-11575.\n\n[4] Van den Broeck, Guy, et al. \"Lifted probabilistic inference by first-order knowledge compilation.\" IJCAI. 2011.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> My main problem with the paper is that it only discusses sufficient conditions (also acknowledged by the authors). This is contrast to the probabilistic circuit atlas [1].\n\nAlthough we only discuss sufficient conditions, for Table 1, the necessity of these conditions in general follows from the results in the PC atlas, as those are special cases in the probabilistic semiring. The point we are trying to make is that, inevitably, even though the conditions are necessary in general, they might not be for a specific semiring (and a specific elementwise mapping). \n\nFor the specific compositional queries in Table 2, we show hardness for 2AMC without these conditions in Theorem 7, while hardness results for the causal inference queries are given in [36].\n\n> This in itself is not a problem, however, the paper does not discuss the problem of eighted model integratio, which has also been formulated as an AMC problem with integration as an extra operation [2]. In general WMI is intractable, however, it has been shown that there exist tractable fragments [3]. If I understand the paper correctly, the tractable fragment of WMI does not fall within the proposed framework. This is quite limiting as the framework does not even cover all tractable problems that can be formulated as 2AMC.\n\nThank you for bringing up these works on WMI. We will add these references and a discussion to our related work section.\n\nIn [2], the authors propose to solve hybrid WMI problems by (i) performing AMC over the probability density semiring; and (ii) performing symbolic computation of the resulting expression. The first step (i) is captured by AMC, and thus in our framework (cf. lines 255-262), showing that d-DNNF suffices for valid evaluation (aggregation). We note that the integration step (ii) here uses a symbolic inference engine (or sampler), as opposed to being part of the AMC itself. \n\n[3] shows certain fragments of WMI are tractable through a message-passing algorithm; however, it is unclear if and how the WMI problems being considered could be represented as an AMC problem on circuits, and how the message-passing algorithm would translate to circuits. Our work concerns compositional inference problems (including AMC/2AMC) on circuit representations, and in particular it encompasses all AMC/2AMC problems on circuits, as we show in Theorems 7 and 8.\n\n> Tractable algebraic circuits seem to be highly related to performing tractable inference on first-order circuits. [4] This relationship is not discussed at all.\n\nOur work focuses on circuits where the nodes are algebraic expressions (e.g. propositional formulae in NNFs); in particular, the expressions are not defined over a domain as in first-order circuits. We would be happy to clarify any specific questions the reviewer has about the relationship of our work with this paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oqfb7nqnC9", "reviewer": "Reviewer_oGJN", "summary": "The paper mainly focuses on the problem of deriving tractability conditions for compositional operations over circuits as to solve a number of queries. By fixing the language of circuits over semirings, the paper generalizes known results and introduce novel ones regarding the tractability of queries solved via algebraic circuits. In addition, it analyzes scenarios where milder structural conditions might be required, when compared to previous results.", "questions": "1. If we restrict  $\\tau$ to be both additive and multiplicative homomorphisms, then does this imply it can only be identity function? It looks like it can only be identity function as for Lemma 3.8 in the appendix of [35]. Do the authors agree on this? If yes, then I think it is necessary to refine the conditions required by Theorem 4 as to include these results about the satisfaction of Cauchy functional equations.\n2. Following Question 1, are there examples of both additive and multiplicative homomorphisms for some particular choices of source and destination semirings?\n3. It seems the support-compatibility definition does not consider how scopes of products are factorized. What is the relationship between support compatibility between circuits and compatibility + determinism? Is structured decomposability PLUS determinism in a circuit more restrictive than support-compatibility with itself?", "limitations": "I have discussed the presence of limitations in the weaknesses section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The results of this paper are part of a series of many theoretical results regarding the tractability of complex operations over circuits. I think the paper positively contributes to the current research area, with a more general understanding of already known results but also new ones. For instance, the exponential separation (Theorem 9) provides an example where lifting the X-first property not needed for computing 2AMC queries on particular semirings might provide an exponential expressiveness advantage. However, note that I lack background regarding the causal probabilistic queries being considered in Section 4.2, and I am not able to fully check the claims regarding their complexity.\n\nI believe the paper is very well written: the notation is very clear, most of the claims are well motivated from the beginning, and there are concise examples across the paper. The proofs in the appendix are also easily readable once having understood the structural properties being used.\n\nThe reason of the lower scores related to soundness and contribution are listed in the weaknesses section. However, note that I am somewhat confident that the authors can solve the following issues during the rebuttal phase and therefore potentially improving my score.", "weaknesses": "I think that some results requiring particular semirings and homomorphisms require so many properties that make me wonder their actual contribution.\nTractable mapping (Theorem 4) requires the following combination of properties to be both true:\n1. $\\tau$ is additive OR $C$ is deterministic\n2. $\\tau$ is multiplicative OR ($\\tau$ maps the multiplicative identity AND for each product $\\alpha$, one of its input must output zero or one as a constant).\nI think that the authors should have stressed the limitations of the given properties on $\\tau$. E.g., if $C$ is not deterministic and there are no product units satisfying the above, then which functions $\\tau$ are we restricted to in practice? See the question 1 below for more on this.\n\nTheorem 3 claims that one can compute the product of support compatible circuits linearly in the maximum circuit size for both time and memory. However, I think the authors should state that this complexity assumes that (i) we already know the isomorphism between nodes, and (ii) we already know how to \"match\" the supports of sum nodes in the algorithm. I think that without (ii) one would definitely need linear space and quadratic time instead.\n\nIn line L298-L300, the authors claim that for particular semirings and mappings, one could relax the determinism property from the circuit for tractable 2AMC. However, this does not seem to be reflected in table 2, where X-Det is present in all 2AMC queries. I think the authors should either make a milder claim or explicitly show in table 2 a case of such a query.\n\nLooking at Algorithm 2 and 3, I think there are corner cases that are not covered neither by them nor by the proofs. For example, the case of multiplying a sum node and a product node is missing. The case of multiplying input nodes and sum/product nodes is also missing. In fact, these algorithms are way too small when compared to the algorithm of the product showed in [35] (Algorithm 3 in the appendix). I believe the cases must be covered for completeness.\n\nI believe a minor weakness of the presentation of this paper is that it mixes two kinds of theoretical results. It contains some results that leverage algebraic circuits and specific properties regarding semirings and morphisms (e.g., Theorem 4). However, it seems the majority of the other results do not actually need any specific property of the semiring being chosen, and could have been part of a work following the compositional atlas paper on circuits [35]. When reading the paper, I often found myself asking whether the theorems and proof I was looking at were the result of a property of semirings I was missing. This is because of the title and the definition of algebraic circuits is the first definition appearing, and I was expected the rest of the paper being very dependent on it. Instead, it seems many theorems can stand on their own with the usual circuit definition given in [35]. Although minor, I think it would be beneficial if the authors stressed at the beginning that the chosen semiring is not really important for many of the results being shown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I think that some results requiring particular semirings and homomorphisms require so many properties that make me wonder their actual contribution. Tractable mapping (Theorem 4) requires the following combination of properties to be both true...\n\nPlease see response to Q1/Q2 below.\n\n> Theorem 3 claims that one can compute the product of support compatible circuits linearly in the maximum circuit size for both time and memory...\n\nThis is a good point, thanks. We agree and will make this clear in the revised draft. \n\n> In line L298-L300, the authors claim that for particular semirings and mappings, one could relax the determinism property from the circuit for tractable 2AMC. However, this does not seem to be reflected in table 2, where X-Det is present in all 2AMC queries...\n\nBy this we mean that one can relax determinism (i.e. $\\textbf{V}$-determinism), while $\\textbf{X}$-determinism is always required. For example, for the PASP (Max-Credal) query, determinism is not required. We will rephrase to make this clearer.\n\n> Looking at Algorithm 2 and 3, I think there are corner cases that are not covered neither by them nor by the proofs. For example, the case of multiplying a sum node and a product node is missing...\n\nThanks for pointing this out. For Algorithm 2, we have now added the cases of multiplying an input or product node with a sum node (this corresponds simply to multiplying the input/product with the children of the sum). We have also made minor changes to the proofs for Thm 2 and Thm 5.2 to account for this corner case. Please see the PDF response for the full details. As for multiplying an input with a product, this also seems to be an omission in [35]. We will address this by adding the condition that input nodes do not have scope overlapping with both children of a product to the compatibility definition.\n\nAs for Algorithm 3 (support-compatible products), these cases are disallowed by the isomorphism scope condition (i), since for smooth and decomposable circuits, sum nodes have children with the same scope, product nodes have children with disjoint scopes, and input nodes do not have children. We will add this point in the proof of Theorem 3.\n\n> I believe a minor weakness of the presentation of this paper is that it mixes two kinds of theoretical results. It contains some results that leverage algebraic circuits and specific properties regarding semirings and morphisms (e.g., Theorem 4)...\n\nThank you, this is very helpful feedback presentation-wise. The results for aggregation and products are indeed semiring-agnostic, depending only on the generic semiring $\\oplus, \\otimes$ and circuit scope/support properties, while the results for elementwise mappings do depend on the specific mapping/semirings. We will clarify this at the start of Section 3.\n\n> **Q1/Q2**: If we restrict to be both additive and multiplicative homomorphisms, then does this imply it can only be identity function?... Following Question 1, are there examples of both additive and multiplicative homomorphisms for some particular choices of source and destination semirings?\n\nAs noted in [35], over the probability semiring the only additive and multiplicative homomorphism is the identity function. For other semirings, there are more such functions (known as semiring homomorphisms). For example:\n- Corollary 1 shows that the support mapping $\\[\\[p\\]\\]$$_{\\mathcal{S} \\to \\mathcal{S}'}$ always satisfies (Multiplicative), and satisfies (Additive) if (a) no element except $0 _{\\mathcal{S}}$ has an additive inverse in $\\mathcal{S}$ and (b) $\\mathcal{S}'$ is idempotent. \nExamples of such $\\mathcal{S}$ include the Boolean, probability and $(\\max, \\cdot)$ semirings, while examples of $\\mathcal{S}'$ include the Boolean, $(\\max, \\cdot)$, and tropical $(\\min, +)$ semirings. The support mapping is a semiring homomorphism in these cases, and is not the identity function unless $\\mathcal{S}, \\mathcal{S}'$ are both the Boolean semiring.\n- For the semiring $\\mathcal{S} = \\mathcal{S}' = (\\max, \\times)$ semiring, any function $f(x) = x^{\\beta}$ is a semiring homomorphism. \n- For the tropical semiring $\\mathcal{S} = \\mathcal{S}' = (\\min, +)$, any function $f(x) = c \\cdot x$ is a semiring homomorphism.\n- For the rings $\\mathcal{S} = \\mathbb{Z}$ and $\\mathcal{S'} = \\mathbb{Z} _{12}$ (the rings of integers, and integers modulo  $12$), then $f(x) = 4 \\cdot x \\text{ mod } 12$ is a (semi)ring homomorphism.\n\nThat said, semiring homomorphisms are a very restricted class of functions and for most of the useful mappings we consider (aside from the support mapping) at least one of the circuit-specific conditions (determinism or the product node condition) will need to hold.\n\n> **Q3** It seems the support-compatibility definition does not consider how scopes of products are factorized. What is the relationship between support compatibility between circuits and compatibility + determinism? Is structured decomposability PLUS determinism in a circuit more restrictive than support-compatibility with itself?\n\nThe reason that support-compatibility does not consider factorization of scopes is because of the isomorphism which requires scopes of isomorphic nodes to match; thus the necessary scope factorization is already satisfied. Support-compatibility and compatibility+determinism are different properties and incomparable in general; in particular, support-compatibility does not require compatibility (e.g. any decomposable, smooth, deterministic circuit is compatible with itself), while two circuits can be compatible and both deterministic, but not necessarily share the same \"support decomposition\". On the other hand, structured decomposability + determinism is strictly stronger than support-compatibility with itself (just decomposability + determinism would suffice).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xq42eN5xWL", "reviewer": "Reviewer_oPB2", "summary": "This paper unifies two lines of work:\n1) a compositional approach to tractability of queries over logical [12], probabilistic [35] and causal circuits [36] and\n2) a (commutative) semiring-based perspective over different computational tasks ([12] among many others).\n\nThe benefit is the characterization of certain probabilistic and causal tasks in terms of combinations of simple operations on algebraic circuits. Concretely, this approach is used to derive new complexity results in second-level algebraic model counting (including highlighting a wrong claim in [20]) and causal inference, among others.\n\n**update after rebuttal**\n\nThe response clarified a bit the scope of the contribution. I think that this is solid work overall and that adding parts of their response to the main text would make the paper more accessible. I raised my score accordingly.", "questions": "1. Could you clearly outline what are the novel notions that enable this generalized compositional framework?\n2. Could you similarly outline what are the key ideas / existing work this work builds upon?\n3. Could you provide examples (for the general NeurIPS audience rather than experts in AMC and AC) of the practical impact of this contribution?\n\n\n## Minors\n\nMultiple typos on Def. 1", "limitations": "The limitations of this work are adequately addressed in the conclusion.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper is overall well-written, albeit dense (which I think it is a necessity due to the limited space)\n- The novel properties of AC introduced here could lead to more effective compilation algorithms", "weaknesses": "- Novel and existing notions/definitions are mixed together, making it hard to give proper credit where it is due.\n- The high-level contributions are not very clear from the text (in particular in the first sections). [35] clearly listed their contributions at the end of their introduction, in contrast, I found lines 39-42 more vague in this sense, giving the (wrong) idea that the compositional approach is a novelty.\n- I think that the practical impact of this contribution is not be very clear to a general AI/ML audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The high-level contributions are not very clear from the text (in particular in the first sections). [35] clearly listed their contributions at the end of their introduction, in contrast, I found lines 39-42 more vague in this sense, giving the (wrong) idea that the compositional approach is a novelty.\n\nWe will add a contributions statement at the end of the introduction. To summarize, the key contributions are (1) a more general compositional inference framework that covers circuits over arbitrary semirings, including logical and probabilistic circuits; (2) a conceptually simple, yet general formulation in terms of just three basic operations (aggregation, products, elementwise mappings), with associated tractability and composability conditions (Table 1); (3) novel and systematically derived tractability conditions for a range of existing inference problems (Table 2).\n\n> **Q2** Could you similarly outline what are the key ideas / existing work this work builds upon?\n\nOur work mainly draws on three lines of existing work. \n\n- Firstly, work on new structural properties for tractable inference on circuits (e.g. $\\textbf{X}$-determinism [6] for marginal MAP and compatibility [35] for products).\n- Secondly, the compositional approach to inference [12, 35], which characterizes *tractability conditions* for individual operations  and which properties are maintained by the output of the operations (*composability conditions*). \n- Finally, algebraic model counting [21, 20], which casts many inference queries as aggregation over a particular semiring. \n\nOur conceptual contribution is to combine the generality of compositional inference with semiring structure. In the process, we make use of many of the recently introduced circuit properties (and extend them where required).\n\n> **Q1** Could you clearly outline what are the novel notions that enable this generalized compositional framework?\n\nThe key novel notions that enable the generalized compositional framework are (1) the elementwise mapping operation and (2) extended composability conditions. In more detail:\n\n- **Elementwise Mapping:** A key novel contribution is our definition of elementwise mappings as a *modular operation*, which covers e.g. the (implicit) transformation from the Boolean circuit in algebraic model counting, 2AMC when moving from the inner to the outer semiring, and various mappings on the probability semiring such as reciprocals.\n\n    * This abstraction is crucial in that it allows us to extend the compositional approach to inference to a much wider range of problems that were not addressed in [35]. In contrast to prior works on algebraic inference, this is independent of particular formalisms (e.g. labeling functions in AMC), whether the input circuit is a logic circuit (DNNF) or PC, etc. \n\n    * In terms of the practical impact, the compositional approach provides a *simple* and *robust* recipe for finding sufficient tractability conditions: simply write down the inference query in math, and apply Table 1 to each operation.  For example, this enabled us to discover a mistake in the 2AMC tractability conditions [20], and elegantly extends compositional inference for probabilistic circuits to maximization, which was mentioned in the conclusion of the PC atlas paper [35] as an open problem.\n\n- **Composability Conditions:** A limitation of [35] is that the analysis of *composability conditions* was incomplete. In particular, there was no result on transitivity of compatibility (in fact, we show in Example 3 in the Appendix that this is actually not true). This is critical for the proofs of tractability for the queries in Table 2 using the compositional approach. To this end, we introduced $\\textbf{X}$-compatibility and $\\textbf{X}$-support-compatibility as new properties which do satisfy ``transitivity'' conditions, and prove these in Table 1/Section 3.2.\n\n> **Q3** Could you provide examples (for the general NeurIPS audience rather than experts in AMC and AC) of the practical impact of this contribution?\n\nThe compositional queries we consider in this paper have many applications which are of interest to the NeurIPS community. For example, PCs have been used to compute interventional distributions in causal inference [36]. By reducing the complexity of backdoor adjustment for PCs from quadratic to linear (given $\\textbf{Z}$-determinism), we open up the possibility of scaling up PC models for causal inference. The probabilistic ASP queries we consider are of significant interest in neuro-symbolic AI \n[b,c,d], where circuit representations are widely used to encode symbolic knowledge. Our work clarifies which circuit types can be used depending on the desired semantics.\n\nGiven the connections that we establish between these disparate queries, we believe that our work will motivate more research on compiling as well as learning expressive circuits satisfying the properties that we identify.\n\nWe believe that our work will also open up new applications for circuits within ML. For example, recent work has examined using circuits for generating text satisfying logical conditions [a], with quality comparable to LLM approaches; this relies on tractable products between the logical and probabilistic circuits. The PC used is a HMM, which is $\\textbf{X}$-deterministic where $\\textbf{X}$ are the hidden states (e.g. Figure 4 in the Appendix); our compositional algebraic atlas shows that it would be tractable to find the most likely hidden state conditional on the logical constraint, which could be used for model explainability.\n\n[a] Zhang et al. ``Tractable Control for Autoregressive Language Generation'' ICML 2023. \n\n[b] Zhun et al. ``NeurASP: Embracing Neural Networks into Answer Set Programming'' IJCAI 2020.\n\n[c] Mahaeve et al. ``Neural probabilistic logic programming in DeepProbLog'' AIJ 2021.\n\n[d] Huang et al. ``Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning'' NeurIPS 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their time and effort spent reviewing our paper, and for their helpful feedback and comments. Please find individual responses to each reviewer below. 

We attach a PDF here addressing corner cases in Algorithm 2 mentioned by Reviewer oGJN.

Meta-review: The paper provides a unifying framework for algebraic circuits using compositional operation and claims to show new tractable classes for various probabilistic queries.  This is done by extending circuits to semi-rings.
 
The reviewers comments say that the strength is in the technical work. Yet the weakness is that it is not clear what the practical contribution is. It is not clear if the tractability conditions can be satisfied by any real circuits. Also, there are complaints that there is no clear separation between earlier and new contributions. There was a discussion with the authors and reviewers seemed to accept the clarifications provided.

There is a very large literature missing here on semiring, by Bistareli et. al: in the area of constraint and probabilistic reasoning by 

Semiring-based constraint satisfaction and optimization
Authors: Stefano Bistarelli, Ugo Montanari, Francesca Rossi 
Journal of the ACM (JACM), Volume 44, Issue 2
Pages 201 - 236
https://doi.org/10.1145/256303.256306
Decision: Accept (poster)