Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work suggests a general framework for deriving complex information-theoretic queries using probabilistic circuits (PCs). This framework represents a complex query as a pipeline of operations. The manuscript also provides algorithms for applying these operations to PCs as well.
main_review: This work is original in its unifying characteristic. The contributions presented here provide a simple and helpful tool for tractability analysis of common queries in Machine Learning (ML) and related fields.

The manuscript has an excellent technical quality. The theoretical contributions are non-trivial. Moreover, the work discusses different cases, such as deterministic and non-deterministic PCs. Derived theoretical results are sound, to the best of my knowledge.

This paper is well-written, and it has a clear presentation. For instance, Table 1 summarizes sufficient conditions for the tractability of typical circuit operations.

This work is relevant to a broader audience besides the PC community. Indeed, the manuscript summarizes in Table 2 tractability results for various commonly used machine learning functions.
limitations_and_societal_impact: The paper does not explicitly discuss the limitations of the general framework. It would be interesting to see possible assumptions required for adopting this unifying perspective using PCs.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: A general framework for developing tractable models using circuits. The main contributions are defining the building blocks for tractable models such that queries can be expressed as compositions of these blocks and also open-source software for building these models quickly with tractable guarantees.
main_review: The paper proposes a general framework for tractable queries based on a circuit representation. The main contribution is to abstract out a set of operations and new queries that can be composed using these abstractions are provably tractable. Thus, new tractable algorithms can be easily developed by composing the operations. Tractability conditions and hardness results are proved for operations. The results are applied to prove hardness or tractability results for several common queries. The main takeaway is that these proofs are quite easy since they build upon the basic operations. It is shown that some information theoretic queries for which tractable algorithms were not available before can be tractably computed using the proposed framework. Experiments are performed as part of an open source package to demonstrate the practical implementation of tractable algorithms.

The paper is very well written and clear in terms of contributions. While it does cover a lot of material given the page limit, the organization seems very nice with details in the appendix. In terms of overall significance, having the abstraction for tractable models is a valuable contribution along with an open source software package that one can use to quickly implement tractable models. This could potentially have impact in various important sub-fields such as XAI and Fairness in AI. 

Overall, I did not see many weaknesses in this paper. One aspect that could be improved is if algorithms may not fit into the proposed tractable framework through the defined operations, some comments on how they could be approximated in the pipeline may also be useful for practical relevance.
limitations_and_societal_impact: It is hard to see any potential negative societal impact with this work since it seems quite foundational in nature.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a general framework to trace the tractability of complex queries involving circuit representations in a unified manner over model classes and query classes, and to automatically distill tractable inference functions. Using the framework, the paper unifies and generalizes existing inference algorithms in the literature, and presents new tractability and hardness results of many information-theoretic queries.
main_review: The proposed framework is novel, and can be very useful for understanding the tractability of complex queries involving circuit representations, as well as deriving tractable inference algorithms. I did not check all the details in the proofs, but the paper seems technically sound, and is clearly written and well organized. The empirical results showing the practicality of the framework is a nice addition.

Some questions to the authors/that need more clarifications:
1. Is there any redundancy involved in the automatically derived inference algorithms? In other words, are there still advantages in some of the manually derived inference algorithms, even through they are essentially calculating the same thing? What are some sources of this redundancy? There are some brief discussions in L370-377 but it would be informative to include a brief discussion on how the distilled inference algorithm and the highly optimized implementation differ.
2. It looks like most of the results give sufficient conditions. To what extent are these conditions also necessary? In other words, to what extent is the framework complete? And what are some cases that are not covered by the framework?

=================================

Update after rebuttal: I thank the authors for the clarifications. I still think this is a good paper and would recommend acceptance.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper investigate the tractability of arithmetic operations on circuits for probabilistic inference.  There is considerable similar work when it comes to operators on logical circuits, and this paper generalises this to operators such as powers, logarithm and exponentials. The paper also considers these operations in a computational graph, which means that the results of this paper can be used to prove tractability conditions for many queries, in particular divergences and entropy calculations. The paper discusses various examples of such tractability results.

main_review: The paper is well-written, and despite its technical nature, is quite easy to follow. The main ideas are discussed in the paper, and sometimes intuitive ideas behind proofs are explained. I thought the general ideas were clear. 

The key concept that seems to be introduced in this paper is compatibility, which turns out to be important to prove many of the tractability results. As far as I can see, this idea is novel and certainly non-trivial. In my estimation, this is a major step forward in this research area. I would expect that this will have significant impact in designing new methods that rely on tractable computations of information-theoretic queries. 

As far as I can see, the paper is technically sound. The experimental results are obviously limited for this type of paper. Some preliminary observations are made from experiments, which I think is sufficient at this point.
limitations_and_societal_impact: Societal impact is not relevant for this paper. The authors do address various hardness results, which are limitations for probabilistic inference in general. This is fine.
review_title: null

Meta-review: Very interesting solid work with potential impact. Please take all comments in consideration.
Decision: Accept (Oral)