The Limits of Tractable Marginalization

Thank you for your considered review.

On 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.

As 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].

We 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.

[0] Bläser. Not all strongly Rayleigh distributions have small probabilistic generating circuits. ICML 2023.

[1] Agarwal et al. Probabilistic Generating Circuits - Demystified. ICML 2024.

[2] Wedenig et al. Exact Soft Analytical Side-Channel Attacks using Tractable Circuits. ICML 2024.

[3] Liu et al. Scaling Tractable Probabilistic Circuits: A Systems Perspective. ICML 2024.

[4] Zhang et al. Probabilistic Generating Circuits. ICML 2021.

[5] Loconte et al. Subtractive Mixture Models via Squaring: Representation and Learning. ICLR 2024.

[6] Wang et al. On relationship between monotone and squared circuits. AAAI 2025.

[7] Loconte et al. Sum of Squares Circuits. AAAI 2025.

[8] Martens et al. On the expressive-efficiency of sum-product networks. NeurIPS 2013.

[9] Wang et al. A Compositional Atlas of Algebraic Circuits. NeurIPS 2024.

[10] Vergari et al. A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference. NeurIPS 2021.

[11] Zhang et al. Tractable Control for Autoregressive Language Generation. NeurIPS 2023.

[12] Zhang et al. Adaptable Logical Control for Large Language Models. NeurIPS 2024.

[13] Liu et al. Image Inpainting via Tractable Steering of Diffusion Models. ICLR 2024.

[14] Saad et al. SPPL: Probabilistic Programming with Fast Exact Symbolic Inference. PLDI 2021.

Thank you for your considered review.

We see no questions or concerns in your review needing response. We nonetheless welcome any further discussion, e.g., as prompted by the other reviews.

Thank you for your considered review.

We see no questions or concerns in your review needing response. We nonetheless welcome any further discussion, e.g., as prompted by the other reviews.

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.

[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.

[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.

We thank you for your other notes on minor typos.

[1] Shpilka and Yehudayoff. Arithmetic Circuits: a survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 2010.