The Limits of Tractable Marginalization
Authors: Oliver Broadrick
Sanyam Agarwal
Guy Van den Broeck
Markus Bläser
Venue: ICML 2025 poster (2025)
Keywords: probabilistic inference
tractable models
expressive-efficiency
Primary area: theory->probabilistic_methods
TL;DR: We show that the many known models for tractable marginalization have not yet captured all functions with tractable marginalization.

Abstract: Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to formal verification.
Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can all be commonly expressed by arithmetic circuits computing multilinear polynomials.
This raises the question, can *all* functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\\mathsf{FP} \\neq \\#\\mathsf{P}$ (an assumption implied by $\\mathsf{P} \\neq \\mathsf{NP}$). 
To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. 
We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small arithmetic circuits for that function's multilinear representation.

The Limits of Tractable Marginalization
Oliver Broadrick" Sanyam Agarwal
Guy Van den Broeck Markus Bläser #2
Abstract
their latent space; autoregressive and discrete diffusion mod- els are trained to predict (conditional) marginal probabilities (Kingma et al., 2019; Bishop & Bishop, 2023). In the case of boolean valued functions, marginalization corresponds to the well known task of model counting, with applica- tions from formal verification to cryptography (Gomes et al., 2021; Arteta et al., 2016).
Marginalization summing function over all assignments to subset of its inputs - is a funda- mental computational problem with applications from probabilistic inference to formal verifica- tion. Despite its computational hardness in gen- eral, there exist many classes of functions (e.g.. probabilistic models) for which marginalization remains tractable, and they can be commonly ex- pressed by polynomial size arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly ex- pressed by such circuits? We give a negative an- swer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming FP & #P (an assump- tion implied by P * NP). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known eircuit models. We conclude with completeness result, showing that whenever there is efficient real RAM performing virtual evidence marginaliza- tion for function, then there are small circuits for that function's 's multilinear representation.
Unfortunately, marginalization is a notoriously hard prob- lem in general. As models become increasingly expressive- efficient, able to succinctly express larger classes of distribu- tions, they often sacrifice the tractability of marginalization (Cooper, 1990; Roth, 1996). However, there is a vast body of work aimed at identifying classes of functions for which efficient marginalization remains tractable, including well known probabilistic models like hidden Markov models, determinantal point processes, and probabilistic circuits in general, well as logical representation languages like d- DNNF (Rabiner & Juang, 1986; Kulesza et al., 2012; Choi et al., 2020; Darwiche, 2001). Moreover, a recent line of work has shown how known models with tractable marginal- ization can be commonly viewed as arithmetic circuits com- puting multilinear polynomials, resulting in unified model that formalize uniform finally multilinear arithmetic circuits ( (UFMACs) (Zhang et al., 2020; 2021; Agarwal & Bläser, 2024; Broadrick et al., 2024b).
The fact that known functions with tractable marginaliza- tion can be expressed by polynomial size UFMACs begs the question. Do all probability distributions over binary random variables with tractable marginalization have poly- nomial size (uniform) finally multilinear arithmetic circuits? A positive answer to this question would show that the long line of work on tractable models has successfully ar- rived at a maximally expressive-efficiet modeling language for tractable marginalization. We give a negative answer, suggesting the possibility of yet more expressive-efficien tractable models.
1. Introduction
Marginalization is a fundamental computational problem. In machine learning for example, many architectures are designed around an instance of marginalization. In Bayesian learning (e.g.. Bayesian neural networks), model parameters are marginalized to obtain a posterior distribution; vari- ational autoencoders approximate a marginalization over
"*Equal contribution. 'Department Computer Sci- ence, University of California, Los Angeles, United States DDepattment of Computer Science, Saarland University, Saarbrücken, Germany. Correspondence Oliver Broadrick <odbroadrick @ @aecck/@@@@aammm...m gmail.com>>, Sanyam Agarwal <agarwal@ uniiii dearland.de>.
To rigorously answer this question, define the tractability of marginalization for function in terms of its polynomial time computability. Then, we observe that functions with UFMACs are actually tractable for more powerful forms of marginalization than standard variable marginalization. Specifically, we show that UFMACs support tractable sum- mation over inputs of a given Hamming weight (Section 4)
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Limits of Tractable Marginalization
USMAC d-DNNFs, SPNs
UFMAC
PVM
PHM
PM
FP
PGCs
Satt
verifiers
Figure 1. Relationships between complexity classes for tractable marginalization. UFMAC contains functions efficiently expressible using known tractable models including determinantal point processes (DPPs) and probabilistic generating circuits (PGCs) well as the subclass USMAC containing for example, deterministic decomposable negation normal forms (d-DNNFs) and sum product networks (SPNs). PM is the set of all functions with polynomial time marginalization. PHM and PVM consist of functions that are tractable for Hamming weight marginalization and virtual evidence marginalization respectively (see Sections 4 and 5). We exhibit the function far which is contained in PMrPHH assuming FP + #P. FP the class of polynomial time computable functions, included for context.
and support marginalization in the presence of virtual ev- idence (Section 5). We show that the class of functions tractable for each of these queries form hierarchy of inclu- sions, and we prove that certain inclusions are strict by ex- hibiting separating functions assuming standard complexity- theoretic conjectures (i.e., P + NP): see Figure for visual summary. This reveals distributions that are tractable for marginalization but cannot be computed by a UFMAC, answering our central question.
common language, including -reeweddtr graphical models (Chow & Liu, 1968; Mcila & Jordan, 2000; Rabiner & Juang, 1986; Koller, 2009), determinantal point processes (Kulesza al., 2012), probabilistic sentential decision dia- grams (Kisa et al., 2014), sum- cum-product networks (Poon & Domingos, 201 1), cutset networks (Rahman et al., 2014), characteristic circuits (Yu et al., 2024), and probabilistic generating circuits (Zhang et al., 2021; Harviainen et al., 2023; Bläser, 2023; Broadrick et al., 2024a). this section, we formalize the unified tractable model as finally multilin- ear arithmetic circuits (UFMACs). UFMAC expresses function f {0, 10 - Q by its multilinear polynomial and represents the polynomial by an arithmetic circuit.
While turns out that not all distributions with tractable marginalization be expressed by UFMACs, then ask the corresponding question for the stronger forms of marginalization. We find that UFMACs are complete for tractable virtual evidence marginalization in the real RAM model of computation in the sense that if there a polyno- mial time real RAM that performs virtual evidence marginal- ization for function, then the function has UFMACs.
2.1. Multilinear Polynomials
Consider function f 10, - Q. Among infinitely many polynomials that compute f on {0, 13"" there is unique multilinear polynomial (a fundamental object; for example, see O' D'Dnnelll (2014)). A polynomial is multi- linear its degree in every individual variable at most one. The unique multilinear polynomial computing f can be found by interpolation:
2. Tractable Arithmetic Circuits
Classical probabilistic models like hidden Markov models (Rabiner& & Juang, 1986) and Chow-Liu trees (Chow & Liu, 1968) have efficient algorithms for marginalization based on sums and products of probabilities. For general graph- ical models this remains true, albeit with the caveat that the efficiency of the algorithm depends the underlying graph structure. In the ninetics, it was observed that such algorithms naturally correspond to the computation of cer- tain multilinear polynomials (Castillo et al., 1995; Darwiche & Provan, 1997). Actually, a direct representation of such a polynomial can be exponentially more succinet than an equivalent graphical model (Roth Samdani, 2009), and so recent tractable probabilistic models have focused repre- senting the underlying polynomial as arithmetic circuit, computation graph consisting of sums and products. Кnown models with tractable marginalization can be viewed in this
p( ......... Inn
Σ 8g
f(vs)
24 II iES
II
x.)
where [n] = {1, .2] and Us denotes the characteristic vector of the set S, that is, the element of {0, 1)" with ith
entry for i E S and ith entry 0 for $ S. It turns out that the tractability of marginalization for a function f can characterized to some extent in terms of the ability to evaluate its multilinear polynomial on elements of Q" beyond just {0, 13", "," as we will see in Sections to
2

---

The Limits of Tractable Marginalization
2.2. Arithmetic Circuits
points. Indeed, it is an open question whether polynomials like the determinant can be efficiently computed without this additional flexibility (Shpilka et al., 2010, Open Prob- lem 3). In the following we deal with families of circuits (Cn) m, = (C1, .2....) with each C, a circuit, often using (C,,) as shorthand for (C,),=1,2....
Arithmetic circuits are thoroughly studied model for the computation of polynomials, algebraic analogue to boolean circuits: see Shpilka et al. (2010) and Saptharishi (2015) for surveys.
Definition 2.1 (Arithmetic Circuits). An arithmetic circuit over a field IF in variables X is directed acyclic graph. A node with in-degree O is an input node and is labeled with an element in IF or X. All other nodes are sum or product nodes, labeled accordingly by + or x. The node with out-degree 0 is the outpul node.'
Definition 2.2 (Finally Multílinear Circuits), The arithmetic
circuit family (C₂) is finally multilinear if for n = 1, ........
. Cn computes a multilinear polynomial, and
after replacing each of the constants in Cn. cl...., F, by fresh variables 21,-.... Zks the poly- nomial computed by any internal node (in variables Fi.... En, 2,,..., 24. has total degree at most poly- nomial in n.
Each node in an arithmetic circuit computes a polynomial: (i) each leaf computes the polynomial by which it is la- beled, (ii) each sum node computes the sum of the poly- nomials computed by its children, and (iii) each product node computes the product of the polynomials computed by its children. The polynomial computed by a circuit is the polynomial computed by its output node.
The only additional restriction needed to ensure that a cir- cuit family can be efficiently evaluated at rational points is uniformity, which requires that there be an efficient method for obtaining a description of any circuit from the family, Uniformity rules out the unrealistic power of nonuniform cir- cuit families which can, for example, compute undecidable languages.
Classes of arithmetic circuits that compute multilinear poly- nomials are themselves well studied (Nisan & Wigderson, 1996; Raz, 2009; Raz et al., 2008). A circuit is called syn- tactically multilinear if every product node has the property that its children mention disjoint sets of variables. An arith- metic circuit is called (semantically) multilinear if every node in the circuit computes a multilinear polynomial. How- ever, there exist multilinear polynomials for which the only known polynomial size circuits do not conform to either of these (syntactic or semantic) multilinearity properties. One notable example is the determinant, multilinear polyno- mial central to determinantal point processes (Kulesza et al., 2012), popular tractable probabilistic model.
Definition 2.3 (Uniform Circuits). An arithmetic circuit family (c,),= is uniform if there exists polynomial time Turing machine which input 1" outputs C, (in some reasonable fixed representation: see Appendix A.
We note that if an arithmetic circuit family (C,) is uniform, then (C₂,) is of polynomial size (since time bounds space), Definitions 2.2 and 2.3 together provide sufficient conditions for a circuit to be efficiently evaluated at rational points.
Lemma 2.4. Let (C₂) be uniform finally multilinear arith- metic circuit family. Then there exists a polynomial time Turing machine which on input Ir, T2,..., Fn E Q com- pules Cn "2,.,,,,
2.3. Uniform Finally Multilinear Arithmetic Circuits
In this work we consider class of arithmetic circuits com- puting multilinear polynomials with (minimal) restrictions to guarantee efficient evaluation by uniform algorithm, general enough to express known probabilistic models with tractable marginalization. In particular, while syntactically and semantically multilinear circuits force all internal nodes to compute multilinear polynomials, we allow intermediate nodes to accumulate higher degree in each variable. How- ever, if intermediate degrees are allowed to grow arbitrarily, then the circuits can compute polynomials like z²" + 2 which cannot be efficiently evaluated (in polynomial time). We thus strike a balance, defining fininin multilinear arith- metic circuits whose internal nodes compute polynomials of polynomially bounded degree, high enough to allow flexible algorithms like determinants, but low enough to guaran- tee polynomial time evaluation of the circuit at rational
The efficient evaluation algorithm promised by Lemma 2.4 is simple: input n rationals, first obtain the circuit C., by uniformity, and then evaluate it in the natural way. We give the full proof that this is guaranteed to take polynomial time in Appendix A.2. The class of functions whose multi- linear polynomial is computable by uniform finally multi- linear arithmetic circuits constitutes the class of functions for which efficient marginalization algorithms are currently known, and thus the class of circuits central to this paper. Definition 2.5 (The Class UFMAC). A function family (fr) with fa {0, 1)2 - Q is in UFMAC if there exists a uni- form finally multilinear arithmetic circuit family computing the family of multilinear representations of (fn).
We consider arithmetic circuits with single output node, though in general they can have multiple.
Note that fixing an encoding Q - {0, 1)- allows functions {0, 13" + Q to be viewed as functions 1). > {0, 13".
3

---

The Limits of Tractable Marginalization
X1
X2
X3
f
0
0
0
0.05
0
0
0.15
0.05
0.02
0
1
0
0.1
1
1
0
0.3
0
0
1
0.06
2
0
0.18
0
0.04
1
1
0.12
3/2
D3
22,
111
.55r2 + 12 .1..
.772243
4242 + .05
M1 22, 12, 23, F3)
0.05 + 0.15m 0.1 + 0.3 0.06T, + 0.18x)
+ 0.044 0.12rj4243.
An example function f (probability mass function over three binary random variables) and its multilincar polynomial network polynomial p. a multilinear arithmetic circuit computing p.
Figure 2.
An important subclass of UFMAC is the analogously defined class of uniform syntactically multilinear arithmetic circuits (USMAC). majority of known tractable models (both probabilistic and logical) belong this subclass including probabilistic sentential decision diagrams (Kisa et al., 2014), sum-product networks (Poon & Domingos, 20, d-DNNF (Darwiche, 2001), and more. Determinantal point processes are the best known example of tractable model known to live in UFMAC but not known live USMAC.
problem is polynomial time computable.
Definition 3.1 (MAR(f)). Let f (fx) with fn {0, 13"H + Q. The marginalization problem for f. de- noted MAR(f), gets input E {,,1, +)" and outputs Σxex,, fn(x) where
Xm = {0, if (0,1)).
Intuitively, m, {0, 1} means that the ith input is fixed (z; m,). and m. means the ith input is marginalized, taking values freely in {0, 1}.
In the next section formalize the problem of marginal- ization, and show that efficient marginalization is easy for functions in UFMAC, giving simple, unified view of exist- ing marginalization algorithms.
Example 3.2 (Marginalization) Consider the function shown for 3 in Figure Suppose we wish to marginal- ize over X2 and X3 with the evidence X; = 0. Specifically, on input m (0, *, +) to MAR(f), we get
Complexity basics. For notions from basic computational complexity theory, including complexity classes P, FP, NP, and #P, we use standard definitions and notation (Arora & Barak, 2009). We note that while the famous classes P and NP contain decision problems (functions of the form f: (0, + (0, 1)), FP and #P can be viewed as natural analogues for general functions, f: {0, 1}* + 10 In particular, FP contains all functions/ f {0, 13' - 10, computable in polynomial time. Moreover, FP # #P is a well known conjecture computational complexity theory and is weaker assumption than P 7 NP in the sense that f NP implies FP * #P. Therefore, results which assume FP * #P also hold if P & NP.
Xm {000, 010, 001, 011}
MAR(f)(m) = Σ p(u) = 0.05
0.25.
X
Definition 3.3 (The Class PM). Let = (fr) with fn. [0, Q. Then E PM MAR(F) is polynomial time computable.
If f E PM, we say f is tractable for variable marginaliza- tion. If f has boolean codomain, then variable marginaliza- tion can be viewed as the task of model counting on f after the substitution of variables given by any (partial) assign- ment. Of course, if a boolean function (family) f is tractable for variable marginalization, then the function itself, f(x), can be computed in polynomial time, by taking Proposition 3.4. PM C FP.
3. Tractable Marginalization
We define tractable marginalization natural way. For every function family f = (fw) with f. {0, 13" Q we define corresponding marginalization problem and then call tractable for marginalization if its marginalization
Moreover, is not hard to see that a function being tractable for marginalization is a much stronger condition than the

---

The Limits of Tractable Marginalization
function itself being tractable compute. There exist many natural problems in FM) For example, if FP * #P, then every # #coopleeee problem provides function in PM.
Proof. Let s E UFMAC be computed by the UFMAC (C.).: We need to provide a polynomial time Turing machine that computes MAR(f). On input m E {0, 1, }} first obtain C. by uniformity of f. Then, for any m, E {0, 1), replace any node in C, labeled by I; with mę. Note that multi- linearity of the polynomial computed is preserved under this substitution, and all remaining variables now need to be marginalized. By Lemma 3.6, suffices to evaluate the remaining circuit with all inputs set to 1/2, which takes polynomial time by Lemma 2.4.
Proposition 3.5. IfFP A #P, then for every # P-comllete function f. there is a function g E PP..M.
Examples of functions in PM given by Proposition 3.5 include verifiers for NP-complete problems (e.g., satisfia- bility problems) as well as functions that do not correspond to NP-complete problems (e.g., suitably defined indicator function for perfect matchings).
4. Hamming Weight Marginalization
A key observation of our work is that UFMACs actually enable more powerful forms of marginalization. In this section we introduce the first such form, Hamming weight marginalization. The Hamming weight of a binary string x. E (0. 1) is the number of ones in it. Where standard marginalization asks for the sum of a function's 's values over all assignments with some subset of the inputs fixed, Ham- ming weight marginalization asks for the sum of its values only over the inputs of given Hamming weight. In the case that the underlying function represents probability distribu- tion, Hamming weight marginalization enables conditioning the Hamming weight of the binary random variables, or on the size of the random set, if the variables are interpreted as the characteristic vector of a set. Algorithms for this problem are known in some special cases of UFMACs, for example in 'structured' syntactically multilinear circuits (Vergari al., 2021) and in determinantal point processes (Kulesza & Taskar, 201 1; Calandriello et al., 2020).
3.1. UFMAC has Tractable Marginalization
Having shown functions in FP\PM (assuming FP A #P), we now consider functions in PM. Such functions include those expressible by the many existing tractable models that can be commonly viewed as uniform finally multilinear circuits. Efficient marginalization for functions in UFMAC follows from (i) the fact that FMACs can be evaluated at ra- tional points in polynomial time and (ii) that to compute any marginalization of f it suffices to evaluate the multilinear polynomial representation of f at a single point. The former follows from Lemma 2.4. The elegant latter fact follows from a very simple argument using linearity of expectation given below for completeness, which has been observed before (Juma et al., 2009).
Lemma 3.6. Let f {0, 13" + Q have multilinear polyno- mial p. Then,
Σ
f(x)= - 20)=22'((1/) 221/1 1/2).
Definition 4.1 (HMAR(F) and PHM). Let f= (fx) with fn {0, 11ah - Q The Hamming weight marginal- ization problem for f. denoted HMAR(f), takes input m E 1, and A E 10.1,....,, and gives output ΣxEx.. fn(x) where
zE(0.17"
Proof. We have
Σ
p(z) - 20"p((1p ................................ In)
Xm,k = Xm n for E (0, 1)" |x| = k}.
aE 1)
-2"p(EEz1.....
E Exn)
Moreover, f E PHM if HMAR(F) (f) is polynomial time com- putable.
= (112, 1/2)
Intuitively, the input m is the same as in MAR(J), and the additional input & further restricts the x E Xm,,k be- ing summed over to those with Hamming weight |x] = k. If f E PHM, we say f is tractable for Hamming weight marginalization.
where the expectation is over the uniform distribution, and the middle equality follows by linearity of expectation. D
(The above lemma can also be viewed as extracting the first Fourier coefficient of f. by first translating the domain {0, 1} to 1) by x + 1 - 2x and evaluating at zero.) With the ability to compute sums of multilinear polyno- mial with a single evaluation, we get that functions with uniform finally multilinear arithmetic circuits are tractable for marginalization.
Example 4.2 (Hamming Weight Marginalization) Recall the distribution shown in Figure 2. Suppose we want to sum over X2 and X3. fixing X1 all strings of Hamming weight k 1. Specifically, we have input
0 * *, k to HMAR(f). From Example 3.2, Xm = {000, 001, 010, 011). So.
Proposition 3.7. UFMAC C PM.
X = (010,001)
5

---

The Limits of Tractable Marginalization
HMAR()) 1) (m,,)) Σ vEXm,
p(v)= 0.1 + 0.06 0.16
and extract the coefficient of t L. Hence, (MAR(f)(m,1) 0.16, as in Example 4.2.
We first observe that a function tractable for Hamming weight marginalization, is also tractable for variable marginalization, since any variable marginalization query is the sum of n + Hamming weight marginalization queries for all & E {0, n.. Proposition 4.3. PHM C PM.
4.1. Separating PHM from PM with CSPs
Our construction of function that is tractable for marginals but #P-hard for Hamming queries exploits known di- chotomy theorems for constraint satisfaction problems (CSPs). Constraint satisfaction problems concern conjunc- tions of constraints, each an application of some boolean relation R S {0, 1] to variables Z1.... 22k (not nec- essarily distinct), i.e., R(F I&) = if and only if (I1...., E R. For some finite set I of boolean relations (called a constraint language), a r-formula is conjunction of constraints each application of some relation in I'. The constraint satisfaction problem CSP(T) gives I-ffrmula & as input and asks whether there is a satisfying assignment for Φb The problem O-ONES(T) gives a r-formula & and an integer as input and asks whether there is a satisfying assignment for & with exactly ones. The counting versions of these problems #CSP(T) and #X=ONES(T) ask for the number of satisfying assignments (in total and with k ones respectively). Clearly, the complexity of these problems depends on the set of relations I..
We now show that UFMACs support tractable Hamming weight marginalization. To do so, we use useful circuit transformation. For any multilinear polynomial p(.1,.... ,r)) = Ssn(m) cs Iless with cs E F, the net- work polynomial for p is the multilinear polynomial
f(1,, 31, ... In, T.)
Σ p(us) SCIM
II EES
III
T
where us E [0, 1)" is the characteristic vector of S. There is a polynomial time algorithm for transforming an arith- metic circuit computing a multilinear polynomial to circuit computing its network form.
Lemma 4.4 (Broadrick et al. (2024b)). Given arithmetic circuit of size computing polynomial in variables, arithmetic circuit computing the network polynomial for p can be constructed in time (sn).
There are elegant dichotomy theorems for these problems, stating that, depending on r, these problems are either poly- nomial time computable or # P-hhadd We say a relation affine if it is logically equivalent to system of linear equa- tions over GF(2), the finite field containing two elements.
With the ability to efficiently transform UFMACs to com- pute their network polynomials, we can efficiently perform Hamming weight marginalization for UFMACs. Proposition 4.5. UFMAC S PHM.
Theorem 4.7 (Creignou & Hermann (1996)). IfT contains only affine relations, then #CSP(T) is computable in poly- nomial time. Otherwise, #CSP(T) is #P-complete.
Proof. Let f E UFMAC. We need to provide a polynomial time Turing machine that computes HMAR(f). On input m E {0, x) & E 1,, n). first obtain a FMAC that computes fn by uniformity of f. Using Lemma 4.4, obtain a FMAC computing its network polynomial p(x, We will now evaluate
To the extent that #CSP(TT CSP analogue to variable marginalization, #K-ONES(L') is an analogue Hamming weight marginalization. There is similar dichotomy, but with fewer tractable cases, for #X-ONNES(T). We say a relation is width-k affine if it is logically equivalent to a system of linear equations over GF(2) with each equation having at most variables with a nonzero coefficient.
follows. For each i, if m, 0, set x; = 0 and T. = 1; if m; = 1, set 2; t and T; 0: if m, = *, set indeterminate/symbol used for all such vi. Evaluating the circuit produces a univariate polynomial in t. The coefficient of the monomial of degree ie is the desired quantity. To see this, consider some monomial p(vs) Thes 2. IL 3. in p. The monomial evaluates to zero if vts does not agree with (i.e., if there is some m, 1 but i S or m, but i E S). Moreover, the degree of the monomial after the substitution is [S] the Hamming weight of v.s as needed.
and F; = 1. Note that t is single
Theorem 4.8 (Creignou et al. (2010)). If contains only width-2 affine relations, then #k- #K-ONES(T)) is computable in polynomial time. Otherwise, # ONE((T) is #P-complete.
D
Leveraging these results from the CSP literature, we now construct a simple function for which standard variable marginalization is tractable but Hamming weight marginal- ization is #P-hard; in other words, we find function tractable for marginals for which the existence of a UF. MAC would imply FP #P. Consider the func- tion sar : {0, 1]22 2 - (0. 1) in variables (xs)k())
Example 4.6 (Hamming Weight Marginalization). Recall Example 4.2. We summed over X2 and X3 with X2 = 0, only strings of Hamming weight equal to 1. Following the proof of Proposition 4.5, we compute
(00 1,4, 1, 1) 1) = 0.05 + 0.1t + 0.06t + 0.04r
6

---

The Limits of Tractable Marginalization
(Mok)sseeenps and (ZE abbreviated to x, y, z:
whichever value (0 or 1) is necessary. The values Zijk are then set to the opposite of the values of Yijk which satisfies the remaining width-2 clauses of f. For every i,j, E [n] we have 2izk # Vijk. and so ly| + |z] = =n².
f,)( - A
Diik ① x4 2z @ 25
Mijk + Zigk.
(1)
Having shown that HMAR( is #P-hard, we have es- tablished that, unless FP = #P, the function fatt is not in UFMAC. In partieular, this means that faw cannot be efficiently represented by known tractable logical represen- tation languages like d-DNNF or BDD, nor by tractable probabilistic models like SPNs or DPPs. This answers our central question negatively, showing that known models for tractable marginalization do not characterize the class of functions with tractable marginalization, suggesting the potential for yet more expressive-effiiies tractable models. We remark that our separating example avoids the known efficient reductions from weighted to unweighted variants of counting problems, for example in weighted model counting (Chakraborty et al., 2015) and weighted CSP counting vari- ants (Bulatov et al., 2012). We also note that Theorem 4.10 partially resolves an open question on the succinctness of languages in the knowledge compilation literature (Koriche et al., 2013) as described in Appendix D.
We first observe that marginalization of fart is computable in polynomial time, mirroring tractable case of Theorem 4.7. After substituting in any partial assignment, fat specifies linear system over GF(2). Performing Gaussian elimination reveals & linearly independent equations. If k 2 n, then there are no satisfying assignments. If k < n, then there are 2n- satisfying assignments, as each affine equation (parity constraint) independently halves the number of solutions. Proposition 4.9. fag E PM.
To see that Hamming weight marginalization on Satt is hard, we reduce from (L-ONES(L') for a chosen I' consisting of only width-three affine relations. The reduction encodes a width-three formula as evidence (a partial assignment) to fan, maintaining a relationship between the Hamming weight of the original formula and the resulting query. Intu- itively, this may work because of the additional width of fan. though we do not rule out the possibility of lower-width function also working. In the reduction, the variables Yijk used 'turn on' and 'turn off' the width-3 equations in variables 2; as needed. The variables Zijk and the con- straints Vijk @ Ziyk: are then used to "balance" the Hamming weight of satisfying assignments since exactly one of yigk and Zisk will be one.
5. Virtual Evidence Marginalization
Interestingly, the computational problems we have studied so far can be characterized by the ability to evaluate the mul- tilinear polynomial representation of the underlying func- tion on increasingly large domains. To efficiently compute f itself, one need only efficiently evaluate its multilincar polynomial p on (0, 1)". To efficiently compute MAR (f), it suffices efficiently evaluate p on {0, 1/2, 1)". For HMAR()), it suffices to evaluate p on set of the form 140, 1, );)") for distinct a, R as shown below in Proposition 5.3. This begs the question: What power is af- forded by the ability to evaluate the multilinear polynomial at all rational points? Nicely, this task corresponds naturally to probabilistic inference in the presence of virtual evidence.
Theorem 4.10. HMAR(fas) is #P-hard. That is, fag & PHM unless FP #P.
Proof. Consider the following constraint language:
--= [abboc}= = {{( 0, 1), (0, (1,00, 1))}.
By Theorem 4.8, (N) is #P-ompllte. We show the #P-hardness of (MMAR(fat) by providing a deter- ministic, polynomial time reduction from #K-ONES(T)- We get input a I'fooruula (f and an integer .n). We construct an 'evidence string' m for HMAR(f) as follows, consisting of an entry in {o, }3 for each variable Hi, Virk. Zijk- For any constraint 2; @ 4y @ d2 = in o, set Yiik = 0 and zijk- = 1. All other variables are marginalized, i... their entry in m is set to *. Then (L-ONES(L))o, k) (f.R(f + n²). To see this, suppose Φ(z) = 1; we find the only y and such that f(x,y,2) z) = 1, and we then observe that |x, y, z| = |x|+n'. Every constraint of ó is satisfied, and so every width-4 constraint in f with yijk = 0 is satisfied. For constraints x; Zz 4 I not in o, the corresponding width-4 clause in f is satisfied by setting the free variable Yijk to
Virtual evidence is well known generalization of the stan- dard notion of (hard) evidence (Bilmes, 2004). Where ob- serving hard evidence means that the probabilities for some subset of outcomes in a distribution be 'zeroed out', virtual evidence allows the rescaling of the probabilities by arbi- trary (nonnegative) weights. Given a probability distribution over variables XI,... X.. observing - conditioning on- the hard evidence that X, can be viewed as scaling the probability for all outcomes with X * 1 by a factor of 0 (and then renormalizing the distribution). On the other hand, it is often necessary, for example in Bayesian belief updates, to multiply the probability of outcomes with X; o 1 by factors other than O.
k E
We consider general version of the problem of updat-
7

---

The Limits of Tractable Marginalization
ing distribution given virtual evidence, though multiple formulations are possible (Chan & Darwiche, 2005). Let .I...., X. be random variables supported on {0, 1 with joint probability mass function p p(z11.....T In). Given scal- ing factors o1, .1:..., Obn, On E IR20 with either O; > 0 or O₂ > 0 for each i, the mass function obtained after ob- serving (i: ,,, (tp) -iirtull evidence is given by
marginalization problem in every VMAR query. On the one hand, multiplying the inputs by arbitrary rationals can be viewed as updating the distribution given virtual evidence, but on the other hand, we have observed (Lemma 3.6) that marginalization of f can be reduced to evaluating the mul- tilinear polynomial p for ff at 1/2,............... 1/2. Therefore the evaluation of p at arbitrary rational points di,..., an can be viewed as first applying virtual evidence corresponding to 2a1, -.......: 2a, to 31y---- In to get 21, ,20,, Dr and then evaluating at ing. In particular, to compute marginal probability given some virtual evidence, a single VMAR(f) query suffices.
p(Z Lnd II (aaa + +a((1 - xx:))
(2)
In, 1/2, i.e., marginaliz-
up to normalization. (Note that ignoring normalization for distributions in PM is not computational issue, normal- ization requires single call to MAR(f), namely with all coordinates marginalized.) We formulate the problem of virtual evidence marginalization as follows.
Intuitively, VMAR(f) captures the computational power afforded by a UFMAC, which raises the question: are UF-
MACS 'complete' for virtual evidence marginalization in the sense that any function f with an efficient algorithm (Turing machine) for VMAR(J) (f) in fact has a UFMAC? That is, do we have UFMAC = PVM? This is the version of a question (restricted to multilinear polynomials) which has been asked before and appears challenging to answer (Koiran & Perifel, 201 1). We are able, however, to give such a completeness result in the real RAM model of computation.
Definition 5.1 (VMAR(J) and PVM). Let ( with fn {0, 1)" - Q, and let (pn)) be the family of mul- tilinear polynomials computing f. The virtual evidence marginalization problem for f. denoted VMAR(F), gets input 1 .2...... Fyn E Q and outputs p(x1,-... :.n. ..). More- over, f E PVM if VMAR(f) is polynomial time com- putable.
If E PVM, we say f is tractable for virtual evidence marginalization. That VMAR(J) enables the incorporation of virtual evidence in the sense of Equation (2) follows by a straightforward application of Lemma 4.4 which we give in Appendix B. We immediately get that VMAR(f) can be solved for UFMACs by simply evaluating (Lemma 2.4).
5.1. Completeness for Real RAMs
Given the apparent difficulty of answering this question for discrete computation models (i.c., Turing machines) and that the question naturally extends to real inputs, we consider the real RAM model of computation in which real numbers are stored in constant space and manipulated by constant time arithmetic. See Appendix C for a brief introduction to the model, though we refer the reader to Erickson et al. (2024) for a full presentation. First, we extend the notion of UFMACs to the real RAM model. We say a function family S= (J.) with ʃ: {0, -> IR with multilinear represen- tation p = (px) has real RAM UFMAC if there exists a polynomial time real RAM which on input 1" outputs an arithmetic circuit Cn computing pn,, in some fixed standard representation (see Appendix C.1). Note that we no longer require the bound on degree since intermediate values are al- ways a single word in the real RAM computation, avoiding the problem of circuit evaluation by Turing machines. We also extend the definitions of MAR, HMAR, and VMAR in the natural way to the real RAM model. We then ob- serve that if f has polynomial time real RAM computing VMAR(f): then the f has real RAM UFMACs, showing that UFMACs are in that sense complete for virtual evidence marginalization. The proof, given in Appendix C, observes that if the real RAM computes the polynomial correctly on all points, then there is some branch of the computation (i.e., ignoring comparisons) which computes it on all points, from which an arithmetic circuit can be recovered.
Proposition 5.2. UFMAC C PVM.
The fact that functions in UFMAC permit efficient condition- ing on virtual evidence generalizes known algorithms for special cases, including Bayesian networks with bounded treewidth (Bilmes, 2004) and certain syntactically multilin- ear circuits (Chan, 2017: Liu & Van den Broeck, 2021), with Proposition 5.2 giving a generalization of them. It is also straightforward to reduce Hamming weight marginalization to virtual evidence marginalization.
Proposition 5.3. PVM C PHM.
Proof. Suppose VMAR(f) is polynomial time computable. Consider the algorithm given in the proof of Proposition 4.5.
This algorithm defines a univariate polynomial (t) in terms of the multivariate (multilinear) polynomial p(a1,..... .n)) by setting each x; to either a constant or to The degree of (()) is at most n. Therefore, all the coefficients of (() can be recovered by interpolation by evaluating at + 1 distinct points using the polynomial time algorithm for VMAR Now, HMAR()) is simply the appropriate coefficient, as per the proof of Proposition 4.5.
Intuitively, this shows that despite Definition 5.1 contain- ing no explicit summation, there is in some sense a hidden
Proposition 5.4. Let f = (fa) with fn : {0, + Q If there exists a polynomial time real RAM computing
8

---

The Limits of Tractable Marginalization
VMAR(S), then there exists a real RAM UFMAC comput- ing f.
specifically highlighted here.
References
6. Related Work and Conclusion
Agarwal, and Bläser, M. Probabilistic generating circuits -emmystffied. In Salakhurdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 329-342. PMLR, 21- 27 Jul 2024. URL ht / http://pooccciceeeeeee mmlr. press/ press/v235// vtt///235///////// http///aaaaaa2aa2aaa.m html..
We highlight some closely related research areas. While we focus on theoretical limits of marginalization, there is much work on leveraging theoretical progress in practice (Sladek et al., 2023; Loconte et al., 2023; 2024; Wang & Van den Broeck, 2025). Moreover, probabilistic models with tractable marginalization, in addition to quickly devel- oping as performant probabilistic models in their own right (Liu et al., 2024a), also appear as integral components in re- cent proposals for control and alignment of deep generative models (Zhang et al., 2023; 2024; Liu et al., 2024b; Ahmed et al.. 2022) as well as numerous other applications (We- denig al., 2024; Saad et al., 2021). Where we study exact marginalization, approximate methods form their own vast area (Hoffman et al., 2013; Liu et al., 2023). We considered functions of binary variables and note work on productive reductions to this setting (Garg et al., 2024; Cao et al., 2023). Given our use of affine relations, we observe that such par- ity constraints appear in other work on boolean knowledge representation both in algorithms and languages (Fargier & Marquis, 2008; Koriche al., 2013; Fargier & Marquis, 2014; de Colnet & Mengel, 2021: Chakraborty et al., 2021).
Ahmed, K., Teso, S., Chang, K.-W., Van den Broeck, G., and Vergari, A. Semantic probabilistic layers for neuro- symbolic learning. Advances Neural Information Pro- cessing Systems, 35:29944-29959, 2022.
Arora, S. and Barak, B. Computational complexity: a mod- ern approach. Cambridge University Press, 2009.
Arteta, C., Lempitsky, V., and Zisserman, A. Counting in the wild. In Computer Vision-ECCV 2016: 14th Euro- pean Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part VII 14, pp. 483-498. Springer, 2016.
Bilmes, J. On virtual evidence and soft evidence in bayesian networks. University of Washington Electrical Engineer- ing Technical Report UWEETR SWVEETR-200-000 2004-0016, 2004.
In summary, despite known models with tractable marginal- ization being expressible as UFMACs, we show that there exist functions with tractable marginalization, yet no UF- MAC assuming FP * #P. On the other hand, UFMACS support the more powerful Hamming weight marginaliza- tion and virtual evidence marginalization, being complete for the latter in the real RAM model of computation.
Bishop, C. M. and Bishop. H. Deep learning: Foundations and concepts. Springer Nature, 2023.
Bläser, M. Not all strongly rayleigh distributions have small probabilistic generating circuits. In Proceedings of the 40th International Conference on Machine Learning, (CML'23. JMLR.org. 2023.
We conclude with two open questions. First, is the inclusion PVM C PHM strict? Second, observing that all marginal- ization algorithms in this paper are amenable to paralleliza- tion, do there exist sequential (P-hard) marginalization prob- lems?
Broadrick, O., Cao. W., Wang, B., Trapp, M., and Van den Broeck, G. Probabilistic circuits for cumula- tive distribution functions. In Proceedings of the UAI Workshop on Tractable Probabilistic Modeling (TPM), aug 2024a, URL URL ht.p:: /ttp:///////////a/eeeeee cs. ucl..edu/ pdf.
Acknowledgements
papers/ /tt///Brrrrrcccccccc
This work was funded in part by the DARPA ANSR, CODORD, and SAFRON programs under awards FA8750- 23-2-0004, HR001 12590089, and HR001 NSF grant IIS1943641, and gifts from Adobe Research, Cisco Research, and Amazon. Approved for public release; distri- bution is unlimited.
Broadrick, O., Zhang, H., and Van den Broeck, G. Poly- nomial semantics of tractable probabilistic circuits. In 40th Conference on Uncertainty in Artificial Intelligence, 2024b.
Bulatov, A., Dyer, M., Goldberg, L. A.,, Jalsenius, M., Jer- rum, M., and Richerby, D. The complexity of weighted and unweighted# esp. Journal of Computer and System Sciences, 78(2):681-688, 2012.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be
Calandriello, D., Derezinski, M., and Valko, M. Sampling from a k-dpp without looking at all items. Advances in

---

The Limits of Tractable Marginalization
Neural Information Processing Systems, 33:6889-6899, 2020.
$805950.1805955 URL https://doi org/10. 1 1145/1805950.1 1805954.
Cao, W. X., Garg, P., Tjoa, R., Holtzen, S., Millstein, T., and Van den Broeck, G. Scaling integer arithmetic in proba- and Shpitser, (eds.), Proceedings of the Thirty-Ninth Conference Uncer- tainty in Artificial Intelligence, volume 216 of Proceed- ings of Machine Learning Research, pp. 260-270. PMLR, 31 Jul-04 Aug 2023. URL https: httptttsssppppeeeeeeeeeeeeeeeeee /ttp//peoeeegs.... mlr. www.ppres//ee / v21 6/ ca.23b...b............ html.
Darwiche, A. On the tractable counting of theory models and its application to truth maintenance and belief revi- sion. Journal of Applied 11-34, 2001.
bilistic programs. In Evans,
Logics, 11(1-2):
Darwiche, A. and Provan, G. Query dags: A practi- cal paradigm for implementing belief-network inference. Journal of Artificial Intelligence Research, 6:147-176, 1997.
Castillo, E., Gutiérrez, J. M.. and Hadi, A. S. Para- metric structure of probabilities in bayesian networks. In European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pp. 89-98.
de Colnet, A. and Mengel, S. A compilation of succinctness results for arithmetic circuits. Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, 2021.
Springer, 1995.
Chakraborty, S., Fried, D., Meel, K. S., and Vardi, M. Y. From weighted to unweighted model counting. In ICCAI, pp. 689-695, 2015.
Erickson, J., van der Hoog. I., and Miltzow, T. Smoothing the gap between np and er. SIAM Journal Computing, 3366:FF0S220-102-F00500----0-110 20M1 385287.
2024. doi: 10.1137/
Chakraborty, S., Meel, K. S., and Vardi, M. Y. Approximate model counting. In Handbook of Satisfiability pp. 1015- 1045. IOS Press, 2021.
Fargier, H. and Marquis, Extending the knowledge com- pilation map: Krom, hor,, affine and beyond. In 23th AAAI Conference on Artificial Intelligence (AAAI'08), pp- 442 447, 2008.
Chan, H. Incorporating uncertain evidence into arithmetic circuits representing probability distributions. In Ad- vanced Methodologies for Bayesian Networks, pp. 105- 116. PMLR, 2017.
Fargier, H. and Marquis, P. Disjunctive closures for knowl- edge compilation. Artificial Intelligence, 216:129-162, 2014.
Chan, H. and Darwiche, On the revision of probabilistic beliefs using uncertain evidence. Artificial Intelligence, 163(1):67-99)) 2005.
Garg, P., Holtzen, S., Van den Broeck, G., and Millstein, T. Bit blasting probabilistic programs. Proceedings of the ACM on Programming Languages, 8(PLDI):865-88 2024.
Choi, Y., Vergari, A., and Van den Broeck, G. Probabilis- tic circuits: unifying framework for tractable prob- abilistic models. UCLA. URL.: http:/starai. cs. ucla. edddpappersPPoocCin22. pdf. pp. 6, 2020.
Gomes, C. P., Sabharwal, A., and Selman, B. Model count- ing. In Handbook of satisfiability, pp. 993-1014. IOS press, 2021.
Chow, C. and Liu, C. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory, 14(3):462-46) 1968.
Harviainen, J., Ramaswamy, V. P., and Koivisto, M. On inference and learning with probabilistic generating cir- cuits. In Uncertainty in Artificial Intelligence, pp. 829- 838. PMLR, 2023.
Cooper, G. F. The computational complexity of probabilis- tic inference using bayesian belief networks. Artificial intelligence, 42(2-3):393 405, 1990.
Hoffman, M. D., Blei, D. M., Wang, C., and Paisley, J. Stochastic variational inference. Journal of Machine Learning Research, 2013.
Creignou, N. and Hermann, M. Complexity of generalized satisfiability counting problems. Information and compu- tation, 125(1):1-12, 1996. doi: 10. 00.11006/mco.19996000 URL https: //oaii///.... wrr. 100.0 /inoo.///noooooo 1996. 0016.
Juma, A., Kabanets, V., Rackoff, C., and Shpilka, A. The black-box query complexity of polynomial summation. computational complexity, 18(1):59-79, 2009.
Creignou, N., Schnoor, H., and Schnoor, I. Nonuni- form boolean constraint satisfaction problems with car- dinality constraint. ACM Trans. Comput. Logic, 11
Karp, R. M. and Lipton, R. J. Some connections between nonuniform and uniform complexity classes. Proceed- ings of the tweifth annual ACM symposium on Theory of computing, pp. 302-309, 1980.
(4), jul 2010. ISSN 1529-3785.
doi: 10.1145/
10

---

The Limits of Tractable Marginalization
Kingma, D. P., Welling, M., et al. An introduction vari- ational autoencoders. Foundations and Trends in Ma- chine Learning, 1274)3307-392, 2019.
via squaring: Representation and learning. arXiv preprint arXiv:2310.00724 2023.
Loconte, L.., Mengel, S., and Vergari, A. Sum of squares circuits. arXiv preprint arXiv:2408. 117778 2024.
Kisa, D., Van den Broeck, G., Choi, A., and Darwiche, A. Probabilistic sentential decision diagrams. In Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning, 2014.
Meila, M. and Jordan, M. I. Learning with mixtures of trees. Journal of Machine Learning Research, 1(Oct); 1-48, 2000.
Koiran, P. and Perifel, S. Interpolation in valiant's theory. Computational Complexity, 20:1 2011.
Nisan, N. and Wigderson, A. Lower bounds on arithmetic circuits via partial derivatives. Computational complexity, 6:217-234, 1996.
Koller, D. Probabilistic graphical models: Principles and techniques, 2009.
O' O'Donnell, R. Analysis of boolean functions. Cambridge University Press, 2014.
Koriche, F., Lagniez, J.-M., Marquis, P., and Thomas, S. Knowledge compilation for model counting: Affine deci- sion trees. In IJCAI, pp. 947-953, 2013.
Poon, H. and Domingos, P. Sum- Sum--roductt networks: A new deep architecture. In / IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689-690. IEEE, 2011.
Kulesza, and Taskar, B. k-dpps: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 1193- 1200, 2011.
Preparata, F. P. and Shamos, I. Compulational geometry: an introduction. Springer Science & Business Media, 2012.
Kulesza, A., Taskar, B., et al. Determinantal point pro- cesses for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3):123-286, 2012.
Rabiner, L. and Juang, B. An introduction to hidden markov models. ieee assp magazine, 3(1):4 16, 1986.
Liu, A. and Van den Broeck, G. Tractable regularization of probabilistic cireuits. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 3558 3570. Curran Associates, Inc., 2021. URL https: http::///creeeeiig...... neurips. cc/ cc/paper_fille wtwpeerffillleepprr///// palls//paeer/22///ieee (at.2a0966faa444ceeee8ee8.. Pafer.pdf.
Rahman, T., Kothalkar, P., and Gogate, V. Cutset networks:
A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Machine Learning and Knowledge Discovery in Databases: European Confer- ence, ECML PKDD 2014, Nancy, France, September 15- 19, 2014. Proceedings, Part II 14, pp. 630-645. Springer, 2014.
Raz, R. Multi-linear formulas for permanent and determi- nant are of super-polynomia size. Journal of the ACM (JACM), 56(2) 2009.
Liu, A. Ahmed, K., and Van den Broeck, G. Scal- ing tractable probabilistic circuits: A systems per- spective. In Proceedings of the 41th International Conference on Machine Learning (ICML), jul 2024a. ucla. edu/papers/
Raz, R., Shpilka, A., and Yehudayoff, A. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM Journal on Computing. 38(4):1624-1647, 2008.
URL http:/ LA L.UTCML.24.pm fd.f.
Roth, D. On the hardness of approximate reasoning. Ar- tificial Intelligence, 82(1):273-302, 1996. ISSN 0004- 3702, doi: http://hh..a////..00000044770000
Liu, A., Niepert, M., and Van den Broeck, G. Im- age inpainting via tractable steering of diffusion mod- els. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR), May 2024b. URL http: http///taaaiicco wwwa.edul papers/LiuICLE2. pdf.
1. URL
sci ittien///rrtaaaeepp////000000000
Roth, D. and Samdani, R. Learning multi-linear represen- tations of distributions for efficient inference. Machine Learning, 76:195-209, 2009.
Liu, S., Ramadge, J., and Adams, R. P. Gen- erative marginalization models. arXiv preprint arXiv:2310.12920. 2023.
Saad, F. A., Rinard, M. C., and Mansinghka, V. K. Sppl: probabilistic programming with fast exact symbolic in- ference. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language
Loconte, L., Sladek, A. M., Mengel, S., Trapp, M., Solin, A., Gillis, N., and Vergari, A. Subtractive mixture models

---

The Limits of Tractable Marginalization
Design and Implementation, PLDII 2021, pp. 804-819, New York, NY, USA, 2021. Association for Comput- ing Machinery, ISBN 978 978145038391 doi: 10.1145/
Conference on Machine Learning (ICML), jul 2023.
URL http://staraie www.aaaaai.s.caaaaaa..a......... www.:ulll.....a........ edu/ paders/ ZhangICML23.
3453483.3454078. URL
Zhang. H., Kung. P.-N,, Yoshida, M.,
Van den Broeck, G., and Peng, N. Adaptable logical control for large language models. In Advances in Neural Infor- mation Processing Systems 37 (NeurIPS), dec 2024. URL https: /ttp://sstaaaaa..ae cs. www.aaaaiiss.cllaaa.aaaaaaa..ale www.uclaeeee hwa.adddddppppaapp ZhangNeurIPS24 .ddf.
Saptharishi, R. A survey of lower bounds in arithmetic circuit complexity. Github survey, 95, 2015.
Shpilka, A., Yehudayoff, A., et al. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends@ in Theoretical Computer Science, 5(3-4): 207-388, 2010.
Sladek, A. M., Trapp. M., and Solin, Encoding nega- tive dependencies probabilistic circuits. In The 6th Workshop Tractable Probabilistic Modeling, 2023.
Strassen, Vermeidung von Divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. URL hwtp::ttp///... / /edmmllmmm... wr.g 1153944
Vergari, A., Choi, Y., Liu, A., Teso, S., and Van den Broeck, G. compositional atlas of tractable circuit operations for probabilistic inference. Advances in Neural Information Processing Systems, 34:131 1111889-11011 2021.
Wang, B. and Van den Broeck, G. On the relationship between monotone and squared probabilistic circuits. In Proceedings of the 39th Annual AAAI Conference on Artificial Intellignce, feb 2025.
Wedenig, T. Nagpal, R., Cassiers, G., Mangard, S., and Pe- harz, R. Exact soft analytical side-channel attacks using tractable circuits. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, (eds.), Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 52472-52483. PMLR, 21- 27 Jul 2024. URL https: /ttp///rooceeeesseeoeoo//os/. mlr. press/ /v3ss/v235// 4edenig24a .tmmm.l...
Yu, Z., Trapp, M., and Kersting, Characteristic circuits. Advances in Neural Information Processing Systems, 36, 2024.
Zhang, H., Holtzen, S., and Broeck, G. On the relationship between probabilistic cireuits and determinantal point processes. In Conference on Uncertainty in Artificial Intelligence, pp. 1188-1197. PMLR, 2020.
Zhang, H., Juba, B., and Van den Broeck, G. Probabilis- tic generating circuits. In International Conference on Machine Learning, pp. 12447-12457. PMLR, 2021.
Zhang, H., Dang, M., Peng. N., and Van den Broeck, G. Tractable control for autoregressive language gen- eration. Proceedings of the 40th International
12

---

The Limits of Tractable Marginalization
A. Uniform Finally Multilinear Arithmetic Circuits
A.1. Note on Representation
The choice of representation is not important up to polynomial changes in length. For example and completeness, one can take the description following (Arora Barak, 2009, Definition 6.5), substituting node types in the natural way, and indicating edge not with zero or but with rational a/b with a, b & given in base two.
A.2. Efficient Circuit Evaluation
We show that uniform finally multilinear arithmetic circuits can be evaluated at rational points in polynomial time. To do so, we first show that if circuit family can be evaluated at integral points in polynomial time then it can be evaluated rational points in polynomial time, reduction which indeed holds for general arithmetic circuit families. (We also remark that multilinearity is not used in any of the proceeding arguments, and so, indeed, any uniform arithmetic circuit family with the degree bound of Definition 2.2 can be efficiently evaluated in the same way.)
Lemma A.1. If there a polynomial time Turing machine for evaluating the arithmetic circuit family C (Cn)n= at integral points ; In E Z, then there is a polynomial time Turing machine that evaluates C at rational points Fi...., In Q
II== by common denominator. Let C; Proof. Consider the input @1 02 Cn with each a, b, E Z. Let De
b1 2...... ".
b
a M by E z and so using a new variable i, observe that
G. Denote by p the polynomial computed by Cn with the degree of p being d². Then,
C1 p (10
D
Σ
Od
II D
de
(3)
di dend ((
b)
t
(c)
D
O dd dn
k=0
di.....dh E Ejo. ""I 11 E: d,
where Ord d,, E Q In particular, consider the univariate polynomial in f,
f(t) = p (tc1...... tCx) =
Σ
Or Odi.....d da
(tc)) dh
di....dn 1.............ddd-111
Odd Odd.....dd du II (c) i=1
k= d,.....d. Ej0.1 1. d
The polynomial f(t) is of degree at most and thus can explicitly by interpolation given the evaluation of p n + distinct (indeed, integral) points. Then, having ft), the value p (B...., . ②) = (#) ..... an Equation (3), by multiplying the coefficient of t in f(t by D- for k 0, 1,.....,7 and summing. (Note that, while recovering f(t) in this block-box manner suffices in general, ft) can be obtained more directly in the case of uniform circuits by evaluating the circuit "symbolically" according to Equation (3), requiring rather than n + evaluations.)
can be recovered, following by
We now show that uniform finally multilinear arithmetic circuits can be efficiently evaluated at rational points, Lemma 2.4, restated here for convenience.
Lemma 2.4. Let (C.)n=12.... be a uniform finally multilinear arithmetic circuit family. Then there exists a polynomial time Turing machine which on input xı, , y Fn Q computes T2,,,.
Proof. By Lemma A.1, it suffices show that C can be evaluated integral points. First, obtain the circuit Cn in polynomial time by the uniformity of C. Next, we show that evaluating (T,,,...., in the natural way takes polynomial time, owing to the polynomial bound on the degree of internal nodes.
Assume inputs aj,.... On E Z are given in base two (with an additional sign bit). For a E Z, denote by ||a|| the number of bits needed to write a in this way (c.g.. ||a||| < 2 log, a). Then, for integers a, b, we have ||a + bll < 1+ max[|la]], ||6]]] (Fact 1) and ||lb|| < ||a|| + +|bb] (Fact 2), and, moreover, such additions and multiplications are polynomial time computable.
13

---

have The Limits of Tractable Marginalization
Consider the augmented circuit C% obtained by replacing the constants of Cn by fresh variables. We say node is of degree d if the polynomial it computes is of degree d (in both the original and fresh variables). Let B(d) be the maximum number of bits needed to write the integer computed by any node of degree d in C² We show by induction that B(d) S (3d 1).N where N is the length of the input (i.e., N = Ei=1 ||a;]]) This completes the proof since the additions and multiplications vee are polynomial time computable in this bitwidth, and d is bounded by polynomial in n S N by Definition 2.3. Note that by uniformity of C' there exists a (univariate) polynomial g upper bounding the size of the representation C²2 by q(n).
For the base case, we upper bound (1) by considering all nodes of degree 1 by cases (there are no nodes in C₁ of degree zero). For input nodes 2; in C²2 which were already variables in C.. the bitwidth is at most N I ((N) since they evaluated as ú,. For input nodes 2j in C, corresponding to the constants of Cn. the bitwidth is at most ((n) S ((N) by uniformity of C. The nodes of degree one considered so far thus require at most ((V) bits each. All other nodes must be the sum of two² degree one nodes and since there are at most ((n) S ((N) nodes total in C,,, and by Fact 1, we get (11) & 2g(NV [). Proceeding by induction, assume Bkk) I (3d - (NV, and consider B(k 1/6e+11 1). Nodes of degree k ++ 1 are obtained either (i) as a product of lower degree nodes or (ii) as sum of nodes with degree at most & + 1. For case (i) and by Fact 2, the maximum resulting bitwidth is at most max (ii) ((0))++0) BKk - i) - (3(k + 1) - ()V( where the incquality follows from the inductive hypothesis. For case (ii), since there
most q(n) ((N) nodes in the circuit,
at most (NN) many additions of degree k + 1 nodes. Hence, by Fact 1 we have B(k + 1) S ((N) + (3(k + 1) (N) (3(k + 1) - 1)g(N) N) as needed.
B. Virtual Evidence
Consider function f = (fxx with fn : f0. 13" + Q with multilinear polynomial p = (Pn.). Here, we interpret the function as probability mass function. We show how to use VMAR(f) observe virtual evidence on this distribution, in way which allows multiple such observations of virtual evidence (by its commutativity) and so maintaining the ability to compute VMAR queries (and so HMAR and MAR queries) on the resulting distributions. Consider the following expression with 0;2, and ā,ē; not both zero (i.e., 2, E {0, Ig- = 1 - 24, and as ā₂ not both zero as is guaranteed for valid virtual evidence scaling factors).
1I (a + a p
011
(4)
01 + "1
In + o Zyp
II 1=1
03:04 + (xTit)
Σ p(u.)
0g
II
Ore27 0,3; + a,
by interpolation
04
0g44 ig5
SCIn
KES
Σ p(us)
II
(5)
$ES
i48
(a:a + @:Ti))
Σ p(us)
using + F. and x² = x for x E {0,
SCIm
VES
KES
n1
= =p(11, Ti.... ...., Fny F.n)
II (ara, + (,,5,)
by definition
p(=1,,..... Fnn II (a,s, + +ā5:))
by definition
Thus evaluating the expression Equation (4) allows one condition on virtual evidence given an algorithm for VMAR(f). Note that Equation (5) can be written as Esgr p(Ts) ([lies a; Ilggs āz) Iliss 2; Isgs Zt. By inspection, this already gives the desired effect of virtual evidence (i.e., scaling the probabilities of outcomes by the corresponding factor); we show the final three steps to demonstrate alignment with the definition given in Equation (2) (and so relying on 2,, F, E {0, 1)).
Enforcing at most children per node straightforward in polynomial time (and so changing the size of the circuit by at most polynomial factor).
14

---

The Limits of Tractable Marginalization
C. Real RAM
The real RAM is a standard computational model used extensively for modeling computations involving real numbers, widely popular in the computational geometry community; we refer to Preparata & Shamos (2012) for more details. Several variants of the model have been developed, and here we briefly describe recent formalization provided by (Erickson et al., 2024), which has the advantage of describing uniform algorithms. Every real RAM algorithm takes as imput pair of vectors (a, b) E I x z and has fixed bit size of every word. Essentially, a word is any integer in {0.... ..... 2 - }1] which can be represented as sequence of u bits. A word size w = [n + m)) suffices, with the additional ad advantage of providing ((1) access to input data. The machine contains two random access arrays W W - 1] and I 11, to store words and exact real values, respectively. There is a machine program counter that is incremented at each step, and at any point the machine executes the step indicated by this counter. The runtime of the machine is the number of instructions executed by the machine before halting. On the word array, we are allowed constant and memory assignments, comparisons between different word values, rounded arithmetic operations like addition, subtraction, multiplication, and division, and bitwise boolean operations. For the real array, we are allowed constant assignments to 0 or 1, memory assignments, comparison with O, and exact arithmetic operations such as addition, subtraction, multiplication, and division. Note that here we consider real RAMs without the ability to perform square roots on real inputs. The major points of difference between the real array and the word array are: while we are allowed to cast integers as reals, we do not allow casting reals to integers (for example, by using floor function), testing whether a real register stores an integer value, or any access to the binary representation of the real numbers.
C.1. Real RAM UFMACS
We say that /= (fn) with f: {0, 13 - R has a real RAM UFMAC if there exists a polynomial time real RAM which on input 1" outputs an arithmetic circuit C, computing fu. The real RAM operates on the padded input (1P(m), jP(a)), where p(n) is a polynomial bound on the size of Ca. i.e., at most the running time of the real RAM. The output is circuit in some standard representation, with the gates, edge relations, and edge weights encoded in the memory array on output, using real registers to store edge weights of the circuit.
C.2. Proof of Proposition 5.4
Proof. Consider any input for VMAR(f) given to the real RAM as the tuple (W, R) where W represents the word array (storing w-bit numbers), and R represents the array of reals. The important thing to note is that the input points for the VMAR query are given to us in R, and W is empty initially. Also, as mentioned in Appendix C above, the only real operation affected by the word array is when we cast integers to reals. However, this can be replicated purely on the real registers by creating the constant (by repeated multiplication and addition) on the reals, and then using that. Since, any word size is bounded by 2", we can make the constant in poly(w) time by repeated multiplication. Hence, any computation on the word array doesn't 't actually contribute to the final output. For the sake of completeness, we do note that since all words are w-bit integers, any computation involving them is bit operation, and hence can be arithmetized with only polynomial blowup. We now move to the main argument of the proof: showing how to convert any arithmetic operations on the reals to an arithmetic circuit computation in polynomial time. We are allowed four operations: addition, subtraction, multiplication, and division. Clearly, the first three easily give rise to an arithmetic circuit. Whenever we see a division operator, we use the famous result of Strassen (1973) to eliminate the division operator. Since, by assumption, the real RAM computes a multilinear polynomial in the end, we know that the degree is bounded by n. and hence to remove the division operator we only need to consider truncations up to degree n. Further, avoid degree blowup on the intermediate nodes, we only need to consider homogenous parts up to degree n. This can be achieved with only a polynomial blowup in size (Lemma 5.2 in Saptharishi (2015)).
Finally, let us now look at the computation of the real RAM. First assume that the real RAM does not make any comparison operations. Then the computation of the real RAM can be turned into an arithmetic circuit computing some polynomial q, by the arguments above. Note, at each point we only compute the homogenous parts upto degree n. By the definition of virtual evidence, q(z) coincides with p(z) for all x E Q" where p is the multilinear polynomial representation of f. Since q and p are polynomials, they also have be the same as polynomials. Since p is multilinear, the obtained circuit is finally multilinear by definition.
Now assume that the real RAM does make comparisons. We get some computation tree. At each leaf u, we compute a polynomial qu- This polynomial coincides with for each input æ that takes the path to u. For each leaf u, the set of
15

---

The Limits of Tractable Marginalization
all such form semialgebraic set. Since all these together cover the whole R", there at least one such that the corresponding semialgebraic contains the product /1 ... x I of nonempty open intervals. On this product, qu (z) = p(z), and therefore, Qu and are the same polynomials.
D. Succinctness Corollary
In the literature on knowledge compitation, representation languages for boolean functions are compared in their tractability for various transformations and queries as well as their suceinctness. Marginalization corresponds the query of counting in the boolean setting (up to partial assignments), and Theorem 4. 10 settles open question the succinctness of languages with tractable counting. There several well known languages that support polynomial time counting (e.g., OBDD, SDD), but most of them are special cases of (and so not more succinet than) d-DNNN. Moreover, d-DNNF straightforwarly translates (in linear time) into syntactically multilinear arithmetic circuits, thus falling within UFMAC. However, Koriche et al. (2013) introduced the representation language Extended Affine Decision Tree (EADT) which supports polynomial time counting, and they left open the succinctness relationship between d-DNNF and EADT. While we refer the reader to Koriche al. (2013) for full definitions, it not hard to see that our function fan can represented efficiently in EADT (in fact even in the much less succinct though incomplete language AFF (Fargier & Marquis, 2008)). We are therefore able partially resolve the succinctness relationship between d d-DNNF and EADT.
For formula @ in some representation language L, let ( denote the size of é (say, the number of bits in some reasonable fixed representation). For representation languages L1, L2, we say L1 is at least as suceinct as L2 (denoted L₁ S. L2) if there is a polynomial p such that for any d2 L2, there exists a Ø1 L1 with Φ1 = Φ2 such that |0ıl S p(lø2)). Here 6 = 22 means that Φ1 and d2 represent the same boolean function.
Corollary D.1. Unless PH Ez, d-DNNF 4s EADT.
Proof. Let fan be as defined in Equation (1), and so HMAR(far) is #P-hard by Theorem 4.10. Note that fan can be represented in polynomial size in either AFF or EADT. But, fart can be represented by a polynomial size d-DNNF, then by the algorithm of Proposition 4.5 we have (MAR(fat) Pipoly. In particular, this gives #P C FPl.poly and so NP S poly, collapsing the polynomial hierarchy Eg by the Karp-Lipton Theorem (Karp & Lipton, 1980).
16


Reviews:
[{"review_id": "iH0vHpeQtB", "reviewer": "Reviewer_jvgm", "summary": "This paper proposes and studies UFMAC, a unifying arithmetic circuit formalism for representing functions that support tractable marginalization. It shows that UFMACs subsume prior such tractable classes, proves that all UFMACs support polynomial time marginalization, and also shows that the reverse isn't true -- that not all funcations with tractable marginalization have UFMACs. There are some additional contributions as well.\n\nThis work substantially enhances our understanding of tractable marginalization. Additionally, the paper is carefully written (modulo some small typos in a later part) and uses neat and elegant arguments in all major proofs.\n\nE.g., the argument that UFMACs support tractable marginalization (Prop 3.7) is refreshingly simple, leveraging an earlier observation of Juma et al (2009). Similarly, while I wasn't quite sure what the motivation for studying Hamming Weight Marginalization is, it became evident later that this tool (besides being of interest by itself) will help prove that not all tractable functions have UFMACs --- because if they have a UFMAC, then even HMAR would be tractable, which conflicts with standard complexity assumptions on certain specific problems.\n\nI enjoyed reading the arguments, even though I am not very familiar with the area.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your considered review. We are glad you found our work “neat,” “precise,” and “elegant,” even sometimes “refreshingly simple.” We provide answers to your questions below and welcome any further discussion.\n\n[The “finally” in UFMAC] The choice to allow polynomial degree (i.e., the “Finally” in UFMAC) has indeed been made to allow for flexible circuits like those known for the determinant. The question of separating finally multilinear circuits from multilinear circuits is currently still an open problem [1, Open Problem 3], and we agree that this can be stated more clearly in the paper and we will do so.\n\n[Virtual evidence marginalization] This is a good question; we will clarify this in the paper. The point is as follows. On the one hand, multiplying the inputs by arbitrary rationals can be viewed as updating the distribution given virtual evidence, but on the other hand, we have observed (Lemma 3.6) that marginalization of f can be reduced to evaluating the multilinear polynomial for f at 1/2,…,1/2. Therefore the evaluation of p at arbitrary rational points a_1,…,a_n can be viewed as first applying virtual evidence corresponding to 2a_1,…,2a_n to x_1,…,x_n to get 2a_1x_1,…,2a_nx_n and then evaluating at x_1=…=x_n=1/2, i.e., marginalizing. Thus there is, in a sense, an implicit summation in every evaluation of the multilinear polynomial at rational points, i.e., in every VMAR(f) instance. In particular, to observe some virtual evidence and then compute a marginal probability, a VMAR(f) query suffices.\n\nWe thank you for your other notes on minor typos.\n\n[1] Shpilka and Yehudayoff. Arithmetic Circuits: a survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 2010.", "claims_and_evidence": "Yes. As noted above, the arguments are made very clearly and the proofs generally precise and elegant.", "methods_and_evaluation_criteria": "The paper is theoretical and provides appropriate definitions, formalisms, and proofs.", "theoretical_claims": "Mostly yes, except I only lightly skimmed the proof of Theorem 4.10 (hardness of HMAR(f_aff) and the material in section 5 (virtual evidence marginalization). The findings in section 5 are a useful addition the main paper, though I think the paper is already strong even by the end of section 4.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The proposed formalism of UFMACs generalizes, to my knowledge, all prior classes for which tractability of marginalization was known.", "essential_references_not_discussed": "None to my knowledge.", "other_strengths_and_weaknesses": "One thing I felt the paper doesn't motivate or revisit enough (other than in the initial part of section 2.3) is the \"finally\" part of UFMACs. The motivation of allowing polynomial degree at the intermediate nodes is good -- but even the fact that determinants would be hard (impossible?) to cover without it is only lightly mentioned within a paragraph. Later sections don't refer to the \"finally\" part at all (I suppose it's not directly relevant anymore for tractability bounds? But then it must make the proofs a little bit harder / more general than assuming linearity even on internal nodes. So it feels to me that something can still be said about it.)\n\nI wonder if even a proposition can be stated that UFMACs are strictly more expressive than UMACs.\n\nFig 1 is useful to have but doesn't seem to be discussed directly after the appropriate notions have been defined and/or results stated.", "other_comments_or_suggestions": "Some typos to revisit:\n\n* page 5, defn 4.1: \"f \\in PHM is HMAR(f) is...\" => should this be \"f \\in PHM if FMAR(f) is...\" ?\n\n* page 8, defn 5.1: similar note as above\n\n* page 5, 2nd line after defn 4.1: should M_{m,k} be X_{m,k}?\n\n* page 5, line after prop 4.3: should FMACs be UFMACs? Similarly in the paragraph after lemma 4.4 and the proof of prop 4.5.", "questions_for_authors": "I didn't look carefully but with a quick pass, I couldn't quite connect with section 5, virtual evidence marginalization, in part because Defn 5.1 defines a \"marginalization\" problem without any \"summation\" in it. Compare, e.g., to defns. 3.1 and 4.1, which both have a clear summation as expected. Can you clarify what exactly is the marginalization problem here? Which variables are we marginalizing over, under what setting?", "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": "dKa9fummob", "reviewer": "Reviewer_PYPx", "summary": "This paper tackles the problem of characterizing the class of functions on which marginalization can be performed in polynomial time. Previous work describes a construction with polynomial size arithmetic circuits computing multilinear polynomials. The authors demonstrate that this construction is incomplete and produce a broader class of functions with polynomial marginalization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your considered review.\n\nWe see no questions or concerns in your review needing response. We nonetheless welcome any further discussion, e.g., as prompted by the other reviews.", "claims_and_evidence": "Claims are supported by propositions, lemmas, theorems, etc.", "methods_and_evaluation_criteria": "Not applicable since the paper is theoretical.", "theoretical_claims": "Regrettably, I haven't got the background to easily follow the theorems and proofs so defer to other reviewers on this.", "experimental_designs_or_analyses": "There are no experiments since the paper is theoretical.", "relation_to_broader_scientific_literature": "With theoretical papers like this it is difficult to assess contributions to the broader scientific literature, as they may only become apparent in the future when the results are used in a more applied context.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "bNM3Eev4t5", "reviewer": "Reviewer_DbFA", "summary": "The paper \"The Limits of Tractable Marginalization\" explores the computational complexity of marginalization, a fundamental operation in probabilistic inference and formal verification. \n\nThe authors focus on the relationship between functions with tractable marginalization and their representation using uniform finally multilinear arithmetic circuits (UFMACs)—a class encompassing known probabilistic models like hidden Markov models, determinantal point processes, and sum-product networks. \n\nThey show that while all known tractable models can be captured by UFMACs, not all functions with efficient marginalization necessarily admit such circuit representations. \n\nBeyond standard variable marginalization, the authors examine two stronger forms of marginalization: Hamming weight marginalization and virtual evidence marginalization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your considered review.\n\nWe see no questions or concerns in your review needing response. We nonetheless welcome any further discussion, e.g., as prompted by the other reviews.", "claims_and_evidence": "### **Claim 1: Not all functions with polynomial-time marginalization (PM) can be efficiently represented by uniform finally multilinear arithmetic circuits (UFMACs).**\n   - **Evidence:** The paper constructs a function \\( f_{\\text{aff}} \\) that has tractable marginalization but does not belong to UFMAC, assuming **FP ≠ #P**. The function \\( f_{\\text{aff}} \\) is defined using **constraint satisfaction problems (CSPs)** with parity constraints.\n\n---\n\n### **Claim 2: UFMACs allow more powerful forms of marginalization than standard variable marginalization, such as Hamming weight marginalization.**\n   - **Evidence:** The authors show that any function in **UFMAC** can efficiently compute **Hamming weight marginalization (HMAR)** queries using a transformation to **network polynomials**. They prove that for any function \\( f \\) represented as a UFMAC, its Hamming weight marginalization can be computed via polynomial-time interpolation.\n\n---\n\n### **Claim 3: There exists a strict separation between PM and PHM (assuming FP ≠ #P).**\n   - **Evidence:** The function \\( f_{\\text{aff}} \\) is used as a **separating example**. It is shown to be in PM (tractable for variable marginalization) but **not** in PHM, since computing Hamming weight marginalization on \\( f_{\\text{aff}} \\) is #P-hard.\n\n---\n\n### **Claim 4: UFMACs allow efficient computation of virtual evidence marginalization (VMAR).**\n   - **Evidence:** The paper proves that any function in UFMAC can efficiently compute virtual evidence marginalization via standard polynomial evaluation.\n\n\n---\n\n### **Claim 5: UFMACs are **complete** for virtual evidence marginalization in the real RAM model.**\n   - **Evidence:** The paper proves that if a function has a polynomial-time **real RAM** algorithm for virtual evidence marginalization, then it has an efficient UFMAC representation.\n\n---\n\n### **Claim 6: The class of functions tractable for virtual evidence marginalization (PVM) is at least as large as the class of functions tractable for Hamming weight marginalization (PHM).**\n   - **Evidence:** The authors prove **PVM ⊆ PHM** by showing that Hamming weight marginalization can be efficiently computed via virtual evidence marginalization.", "methods_and_evaluation_criteria": "This paper is purely theoretical, so no benchmark data is proposed and no empirical evaluation is conducted.", "theoretical_claims": "Yes. I have checked the proof  of theoretical claims:\n\n\n- Claim 1: Not all functions with polynomial-time marginalization (PM) can be efficiently represented by uniform finally multilinear arithmetic circuits (UFMACs).\n- Claim 2: UFMACs allow more powerful forms of marginalization than standard variable marginalization, such as Hamming weight marginalization.\n- Claim 3: There exists a strict separation between PM and PHM (assuming FP ≠ #P).\n- Claim 4: UFMACs allow efficient computation of virtual evidence marginalization (VMAR).\n- Claim 5: UFMACs are **complete** for virtual evidence marginalization in the real RAM model.\n- Claim 6: The class of functions tractable for virtual evidence marginalization (PVM) is at least as large as the class of functions tractable for Hamming weight marginalization (PHM).", "experimental_designs_or_analyses": "NA.\nNo experiments are conducted in this paper.", "relation_to_broader_scientific_literature": "This paper addressed an important problem of computing marginalization of probabilistic models.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA.", "questions_for_authors": "NA", "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": "Pe9xAoVfis", "reviewer": "Reviewer_WSxE", "summary": "This paper defines three computation classes inclusing PM for tractable marginalization, PHM for Hamming marginalization and PVM for virtual evidence marginalization. The authors manage to show that class UFMAC is in all three classes mentioned before. Further, the authors show that PVM \\subseteq PHM \\subseteq PM. With the two conclusions above, the authors manage to provide a hierarchy of complexity class between UFMAC and FP.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your considered review. \n\nOn our paper’s relation to the conference theme, we recall that ICML has recently featured other papers entirely focused on the theory of tractable marginalization [0, ICML 2023; 1, ICML 2024] (with similarly focused papers appearing at closely related conferences [8,9,10]). Moreover, we emphasize the fruitful tradition of a close connection between the theory and practice of tractable models, with theoretical insights inspiring practical breakthroughs. For example, [4, ICML 2024] leveraged theoretical expressivity theorems to inform the design of state-of-the-art tractable models (with similar examples appearing at closely related conferences [5,6,7]). More generally, we remark that marginalization is an essential task (i.e., computing the normalizing constant or partition function) for any probabilistic model; the question of tractable marginalization is therefore as old as probabilistic reasoning as a field.\n\nAs for appeal to the broader community, we note that tractable models, in addition to quickly developing as performant probabilistic models in their own right [3], also appear as integral components in recent proposals for control and alignment of deep generative models [11,12,13] as well as numerous other applications [2,14]. \n\nWe therefore view our work as fundamental and relevant to ICML, developing our understanding of tractable models by formalizing (and making progress in answering) the most basic questions about when marginalization is and isn’t computationally tractable. As reviewer jvgm writes, our work “substantially enhances our understanding of tractable marginalization” while managing to remain “neat,” “precise,” and “elegant,” at times even “refreshingly simple”. We hope this further context is helpful in addressing your questions and concerns, and we welcome any further discussion.\n\n[0] Bläser. Not all strongly Rayleigh distributions have small probabilistic generating circuits. ICML 2023.\n\n[1] Agarwal et al. Probabilistic Generating Circuits - Demystified. ICML 2024.\n\n[2] Wedenig et al. Exact Soft Analytical Side-Channel Attacks using Tractable Circuits. ICML 2024.\n\n[3] Liu et al. Scaling Tractable Probabilistic Circuits: A Systems Perspective. ICML 2024.\n\n[4] Zhang et al. Probabilistic Generating Circuits. ICML 2021.\n\n[5] Loconte et al. Subtractive Mixture Models via Squaring: Representation and Learning. ICLR 2024.\n\n[6] Wang et al. On relationship between monotone and squared circuits. AAAI 2025.\n\n[7] Loconte et al. Sum of Squares Circuits. AAAI 2025.\n\n[8] Martens et al. On the expressive-efficiency of sum-product networks. NeurIPS 2013.\n\n[9] Wang et al. A Compositional Atlas of Algebraic Circuits. NeurIPS 2024.\n\n[10] Vergari et al. A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference. NeurIPS 2021.\n\n[11] Zhang et al. Tractable Control for Autoregressive Language Generation. NeurIPS 2023. \n\n[12] Zhang et al. Adaptable Logical Control for Large Language Models. NeurIPS 2024.\n\n[13] Liu et al. Image Inpainting via Tractable Steering of Diffusion Models. ICLR 2024.\n\n[14] Saad et al. SPPL: Probabilistic Programming with Fast Exact Symbolic Inference. PLDI 2021.", "claims_and_evidence": "The authors provide proves for all their claims.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I think the paper is nicely written, and the result is clear and easy to understand. The three ways of marginalization are also interesting and intuitive. However, it is unclear how the paper relates to the theme of this conference. It seems to me the paper fits better for a conference like CCC. I wonder if the authors could explain more about why complexity classes relate to marginalization, which is interesting for people who work in learning theory or even machine learning.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I wonder if there are any possible implications or applications of the result in machine learning or learning theory. I think it would be helpful if the authors could give some explanation on why PVM, PHM, and PM are important complexity classes.", "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:

Meta-review: This work studies the computational complexity of *marginalization* --- the computational problem of summing a function over al possible assignments to a subset of inputs.
It is a clean self-contained work that presents a negative result to the question: ``Can all functions with polynomial-time marginalization algorithms be expressed with polynomial-sized arithmetic circuits?''
In particular, the authors show that there exists a simple family of functions with tractable marginalization (i.e., can efficiently compute its sum over a subset of all possible inputs)
that does not have an efficient representation (i.e., polynomial-sized circuit), assuming FP != #P (which is implied by P != NP).

After the rebuttal phase, all reviewers lean towards acceptance (scores: 5, 3, 4, 3). All reviewers commented that it was a pleasure to read, but some pointed out that the connections to ICML's topics of interest seem tenuous. In the rebuttal to Reviewer WSxE, the authors presented a list of papers related to the theory of tractable marginalization that have recently been published in ICML/ICLR/NeurIPS.
Decision: Accept (poster)