- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This work considers Boolean reasoning tasks, which compute a Boolean function. The authors argue that it is hard to identify what Boolean reasoning occurs in neural networks, and hence propose a new architecture: Stochastic Boolean Circuits (SBCs). SBCs define a distribution over Boolean funtions (implemented as circuits), and can hence always be interpreted as Boolean functions. Theoretical results show that this model of computation is universal and efficient in a sense. On small synthetic experiments, the SBCs achieve comparable accuracy with MLPs.
Critical strengths
- In my opinion, the question of designing architectures that are more interpretable by construction is important. The proposed SMC method leads to a straightforward extraction of a single Boolean circuit, which could perhaps be analysed and verified to some extent (although this is not attempted in this work).
- The paper properly formalized the introduced architecture and the theorems. The theorems seem precise and correct to me.
Critical weaknesses
The paper starts with a broad motivation for certifiable reasoning that is universal for any Boolean task. The paper then immediately jumps to this as: the model needs to compute a Boolean circuit. I think this jump is poorly motivated in the paper. A good example of this confusion is the notion of Boolean Neural Representability (Def. 1), which as the authors state, captures “what does it mean for a non-Boolean function to latently perform Boolean reasoning?”. But this definition mostly just says that the neural network should have an immediate mapping to a Boolean circuit representation. Let’s take the task of Boolean matrix multiplication. A model could implement this with the naive cubic algorithm. But Boolean matrix mulitplication can also be implemented with say Strassen’s algorithm, which does not conform to your notion of Boolean representability (as it inherently uses integers in intermediary computation). Nonetheless, I would say Strassen’s algorithm is precisely a non-Boolean way to latently perform Boolean matrix multiplication.
Barring the concerns on the motivation above, the paper then introduces a model which places a distribution over circuits. The result of Theorem 1 then seems somewhat circular, as it says that the model always does certifiable reasoning, because you precisely defined certifiable reasoning as being a circuit. Computing a marginal on a distribution over circuits is intractable, so the paper then introduces some relaxations. Worryingly, this loses the probabilistic interpretation, however, and it is not clear what theory still applies to the empirical implementation. (The paper does talk about it, but it’s hidden in App F.6)
Continuing with the experiments, the setup is very toy with only a very small synthetic benchmark. Furthermore, there are no baselines of other models that learn circuit (such as e.g. the cited logic-gate networks of Petersen et al.) I could also not find if the baselines received the same hyperparameter tuning budget as the proposed architecture. Combined with the tenuous connection to the theory, this makes it unclear to me what the advantage of the proposed architecture really is.
W.r.t. the presentation, there are various incorrect or misleading claims. Some examples:
- “Since C has depth Δ, the vertex set admits a layering …” This seems like an assumption, and not something that follows from having a depth. A general DAG can be split into layers by longest-path depth, but edges may then skip layers (i.e. the 2 parents are not in the same layer). (I think this assumption gives a quadratic blowup in the worst case?)
- “We say that a Boolean function is computable if there exists a Boolean circuit (…)” Isn’t each Boolean function computable? (as the domain is even finite)
- “TC$^k$ allows the use of more powerful gates such as threshold (majority) gates, which are not computable (…) in polynomial time” This claim is misleading as it is only true for constant-depth circuits.
Besides this, I think some things didn’t really need to be introduced in the paper. For example, the boolean complexity classes (AC, NC, etc.) are not actually used anywhere? Some notation also confused me, for example Δ is both used for the circuit depth and the probability simplex.
Finally, I think the paper could engage more with related work. For example, probabilistic circuits are cited in appendix, but are not really compared to the proposed stochastic circuits. I think there might be interesting results for this papers in the PC literature. For example, the marginal is a weighted model count, #P-hard in general. The relaxation is exact under decomposability with a multilinear gate, which is the standard result from the probabilistic-circuit literature.
Questions for authors
See weaknesses.
5 comments
Response to reviewer 6zPG - Part 2/3: Weaknesses 3-4
Weakness#3: The synthetic benchmark is limited, logic-gate baselines are missing, and tuning fairness is unclear.
The benchmark tests the realization problem in the constructive theorem: fitting 2,000 specified Boolean functions with . Complete truth tables allow us to check correctness over the entire domain.
DLGN comparison. We use Petersen et al.'s gate implementation with three fixed-wiring configurations. Random-wiring DLGN uses a random graph. Universal-Tree DLGN uses a target-independent tree sufficient to represent every benchmark target. Oracle-Structure DLGN receives the target tree and input placements, but must learn the gates and literal signs. SBC learns routing as well as gates.
| Model | Mean trainable parameters | Soft EM (%) |
|---|---|---|
| SBC (paper Table 1) | 812.5 | |
| Random-wiring DLGN | 510.2 | |
| Universal-Tree DLGN | 3,824.0 | |
| Oracle-Structure DLGN | 70.2 |
Soft EM requires correctness on every truth-table row after thresholding the relaxed predictor. Results are means and standard deviations across five seeds; parameter counts are means across the 2,000 targets.
Hyperparameter tuning. To address tuning fairness, each model receives six configurations, 3,000 updates per fit, and the same 100 targets with , using one seed.
| Model | Mean trainable parameters | Best soft EM (%) |
|---|---|---|
| SBC | 609.6 | 100 |
| Random-wiring DLGN | 305.3 | 76 |
| Universal-Tree DLGN | 1,929.6 | 100 |
| Oracle-Structure DLGN | 75.2 | 89 |
| Neuron-matched MLP | 157.9 | 100 |
| Parameter-matched MLP | 581.1 | 100 |
Each row reports the best mean soft EM from one configuration across all 100 targets. Parameter counts are averaged over those same targets. The tree controls use their prescribed structures rather than a matched parameter budget. MLP EM uses the same thresholded-prediction criterion.
Mean neuron counts are 18.64 for SBC, 19.08 for Random-wiring DLGN, and 18.09 for the neuron-matched MLP. We will include the search spaces in the revision.
Weakness#4: A DAG's depth does not imply a layering without skip connections; removing skips may increase circuit size.
We thank the reviewer for pointing this out. We agree that a general DAG of depth does not necessarily have edges connecting only consecutive layers. Our theoretical construction, however, works directly with layered Boolean circuits, rather than assuming that every DAG naturally admits such a representation.
More generally, a DAG with gates, fan-in two, and depth can be transformed into an equivalent layered circuit by inserting identity gates along edges that skip layers. Since there are at most incoming edges to computational gates, and each edge requires at most additional gates, this transformation introduces at most gates, giving an overall size of , up to auxiliary padding. Importantly, our universality and efficiency results do not rely on this transformation: the proofs construct layered circuits directly, with the size bounds stated in Theorem 3. We will clarify this distinction in the paper.
Response to reviewer 6zPG - Part 3/3: Weaknesses 5-8 and Question 1
Weakness#5: Every Boolean function on a fixed finite domain is computable, so the computability definition needs clarification.
We agree with the reviewer that every Boolean function on a fixed finite domain is computable by some Boolean circuit. Our intention in introducing this definition was to formally establish the connection between a Boolean function and its circuit representation , through the induced function rather than to distinguish between computable and noncomputable Boolean functions. In particular, we wanted to make explicit what it means for a circuit to compute a given Boolean function. We will replace "computable" with "-computable," meaning that the specified circuit computes : for every .
Weakness#6: The statement about threshold gates and polynomial-time computation is misleading.
We thank the reviewer for pointing out this imprecision. We agree that threshold (majority) functions can be computed in polynomial time using standard Boolean gates. Our intended distinction was in terms of circuit complexity under depth restrictions: while majority functions cannot be computed by polynomial-size, constant-depth circuits, they can be computed by polynomial-size, constant-depth circuits. We will revise the statement to clarify this distinction. This correction does not affect our theoretical results, which do not rely on such depth restrictions.
Weakness#7: Unused complexity classes and the double use of make the presentation harder to follow.
We thank the reviewer for these suggestions. The Boolean circuit complexity classes were introduced to provide background on the computational expressivity of different gate sets and to contextualize our framework within classical circuit complexity. However, we agree that they are not directly used in our theoretical results, and we will streamline this discussion. Regarding notation, we use to denote the probability simplex and for circuit depth. Although these are distinct, we agree that the notation could be confusing and will replace with throughout the paper for clarity.
Weakness#8: The connection to probabilistic circuits, weighted model counting, and exactness under decomposability needs discussion.
We thank the reviewer for highlighting this connection. While probabilistic circuits typically represent distributions with structures enabling tractable inference [2], SBCs define distributions over Boolean circuits, emphasizing structural interpretability and universality. We agree that computing the exact marginal is generally intractable [3], and that multilinear relaxations can be exact under appropriate independence conditions, such as decomposability [2]. Our framework does not impose these restrictions, motivating the use of differentiable relaxations. We will expand the related-work discussion to clarify these connections.
References
[2] Choi, Y., Vergari, A., and Van den Broeck, G. (2020). Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models.
[3] Chavira, M., and Darwiche, A. (2008). On Probabilistic Inference by Weighted Model Counting. Artificial Intelligence, 172(6-7), 772-799.
Question#1: See weaknesses.
Addressed item by item above.
Response to reviewer 6zPG - Part 1/3: Weaknesses 1-2
We thank the reviewer for the detailed feedback and for highlighting several important points regarding the motivation, theoretical framework, and experimental evaluation. We have conducted additional experiments to address the concerns about baselines and tuning fairness, and provide further clarifications on the theoretical claims and their relationship to the practical implementation. We address each point below.
Weakness#1: Boolean circuit structure is too narrow a definition of reasoning; the BNR criterion excludes algorithms such as Strassen's.
This is a very interesting point, and we are happy that it was brought up; indeed, we will bring more focus to it in the update.
Perhaps there is a difficulty due to a misinterpretation of quantifiers. Indeed, in our formalism all steps/computations in such a Boolean circuit have simple interpretations for all configurations.
While there do exist interpretable algorithms with more complicated gates (e.g., Strassen's algorithm, which uses only the gates {+2,×2,x↦k}k∈Z) there also exist functions in those gates which can be arbitrarily complicated. For example, let {Mi}i=1n be distinct non-universal Turing machines (whose halting problem is undecidable) and define
F(b):=∏i=1nI{Mi halts on b}.
Furthermore, define f:=F∣{0,1}, i.e., the restriction of F to just {0,1}. Notice that because f has a finite domain, it admits some Boolean circuit representation with gates in {AND,OR,PROJA} on the variables {x,NOT(x)}. That is, f is decidable. But the function F, which encodes the intention/general reasoning behind f, cannot be represented by any algorithm as it is undecidable (here the gates are {+,×} and Turing machines).
Allowing for more general operations, while deeply interesting to us, has the drawback that only some algorithms have an intuitive interpretation but not all.
This can never happen in our setting since our SBC model maps into a class of representations of functions which are end-to-end interpretable. Expanding this class or perhaps choosing a different one over more complicated gates that retains this interpretability constraint can be a subject of future work, and indeed we specify this in the conclusion; perhaps we can elucidate this point more there.
Weakness#2: Theorem 1 appears circular, and the relaxation obscures which guarantees apply to the implementation.
We are not clear about the circularity claim. The workflow is the following: we define (deterministic) interpretable reasoning as corresponding to a Boolean circuit with our simple gates. We then note that every distribution over circuits can be sampled to yield a Boolean circuit, so the natural probabilistic relaxation is that a random Boolean circuit computes a function if it correctly samples a circuit getting the right computation for all inputs more than 3/4 of the time (or any value strictly above 50%). This is the standard idea borrowing from Jukna's book, page 14 of [1] (just above the very elegant majorization trick in Lemma 1.5).
We then introduce our model, and prove that its gates and temperature parameters can be selected so that it samples the intended Boolean circuit with arbitrarily high probability, given enough capacity.
Thus, there is no circularity in the argument and the definition of computability of random Boolean functions (up to a distributional formulation).
Regarding the relaxation, computing the exact predictive marginal requires taking an expectation over the distribution of Boolean circuits, which is generally computationally intractable. This motivates our use of a differentiable relaxation that can be efficiently optimized using gradient-based methods. As discussed in Appendix F.2, the relaxed predictor does not necessarily coincide with the exact marginal. While our theoretical results characterize the properties of the underlying stochastic circuit model, as discussed in Appendix F.6, our experiments investigate the practical effectiveness of its differentiable relaxation. In particular, the results demonstrate that the relaxed SBC predictor achieves competitive performance compared to standard MLPs on Boolean reasoning tasks. Moreover, the implementation allows the extraction of valid Boolean circuits through hard decoding, although their predictive performance may differ from that of the relaxed predictor. We will clarify the relationship between the theoretical framework and its practical implementation in the main text.
Reference
[1] Jukna, S. (2012). Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics, 27.