acceptodds
Under review as a conference paper at ICLR 2027

Universal Boolean Reasoning is Certifiable via Stochastic Boolean Circuits

Abstract

The proliferation of agentic systems has thrust the reasoning capabilities of AI into the forefront of contemporary machine learning. While it is known that there exist neural networks which can reason through any Boolean task , in the sense that they emulate Boolean circuits composed of binary, single-output Boolean gates, trained models have been repeatedly demonstrated to fall short of these theoretical ideals. This raises the question: Can one exhibit a deep learning model which always certifiably reasons and can universally reason through any Boolean task? Moreover, such a model should ideally require few parameters to solve simple Boolean tasks. We answer this question affirmatively by exhibiting a deep learning architecture which parameterizes distributions over Boolean circuits with the guarantee that, for every parameter configuration, a sample is almost surely a valid Boolean circuit (and hence admits an intrinsic circuit-level certificate). We then prove a universality theorem: for any Boolean , there exists a parameter configuration under which the sampled circuit computes with arbitrarily high probability. When is an -junta, the required neuron count and circuit-description size scale near-linearly with the input dimension . Empirically, we evaluate the induced probabilistic predictor on truth-table realization benchmarks. Under neuron-matched budgets, our stochastic Boolean circuits achieve strong predictive performance while retaining intrinsic circuit-level stochastic semantics. Matched MLPs remain competitive as unconstrained predictors, but typically do not yield Boolean-valued hidden representations. This highlights the central tradeoff of this work: unconstrained real-valued prediction versus probabilistic circuit-structured reasoning.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Reasoning, Boolean, Interpretability, Universal Approximation, Logic

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6zPGOpenReview ↗
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 f:{0,1}B→{0,1}f: \{ 0, 1 \}^B \to \{0,1\} 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 pθp_\theta 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
AuthorsOpenReview ↗

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\lbrace +_{2}, \times_{2}, x\mapsto k\rbrace_{k\in\mathbb{Z}}) there also exist functions in those gates which can be arbitrarily complicated. For example, let {Mi}i=1n\lbrace M_{i}\rbrace_{i=1}^{n} be distinct non-universal Turing machines (whose halting problem is undecidable) and define

F(b):=∏i=1nI{Mi halts on b}.F(b) := \prod_{i=1}^{n} I_{\lbrace M_{i}\text{ halts on }b\rbrace}.

Furthermore, define f:=F∣{0,1}f := F\vert_{\lbrace 0,1\rbrace}, i.e., the restriction of FF to just {0,1}\lbrace 0,1\rbrace. Notice that because ff has a finite domain, it admits some Boolean circuit representation with gates in {AND,OR,PROJA}\lbrace\mathrm{AND},\mathrm{OR},\mathrm{PROJ}_{A}\rbrace on the variables {x,NOT(x)}\lbrace x,\mathrm{NOT}(x)\rbrace. That is, ff is decidable. But the function FF, which encodes the intention/general reasoning behind ff, cannot be represented by any algorithm as it is undecidable (here the gates are {+,×}\lbrace +,\times\rbrace 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.

AuthorsOpenReview ↗

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 B=2,4,…,20B=2,4,\ldots,20. 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.

ModelMean trainable parametersSoft EM (%)
SBC (paper Table 1)812.596.1±0.3\mathbf{96.1\pm0.3}
Random-wiring DLGN510.234.48±0.2134.48\pm0.21
Universal-Tree DLGN3,824.091.19±0.4691.19\pm0.46
Oracle-Structure DLGN70.282.66±0.6782.66\pm0.67

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 B≤10B\le10, using one seed.

ModelMean trainable parametersBest soft EM (%)
SBC609.6100
Random-wiring DLGN305.376
Universal-Tree DLGN1,929.6100
Oracle-Structure DLGN75.289
Neuron-matched MLP157.9100
Parameter-matched MLP581.1100

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 Δ\Delta 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 NN gates, fan-in two, and depth Δ\Delta can be transformed into an equivalent layered circuit by inserting identity gates along edges that skip layers. Since there are at most 2N2N incoming edges to computational gates, and each edge requires at most Δ−1\Delta-1 additional gates, this transformation introduces at most 2N(Δ−1)2N(\Delta-1) gates, giving an overall size of O(NΔ)O(N\Delta), 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.

AuthorsOpenReview ↗

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 ff and its circuit representation C\mathcal{C}, through the induced function fCf_{\mathcal{C}} 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 "C\mathcal{C}-computable," meaning that the specified circuit C\mathcal{C} computes ff: fC(x)=f(x)f_{\mathcal{C}}(x)=f(x) for every x∈{0,1}Bx\in\lbrace 0,1\rbrace^B.

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 AC0\mathrm{AC}^0 circuits, they can be computed by polynomial-size, constant-depth TC0\mathrm{TC}^0 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 Δ\Delta 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 ΔN\Delta_N to denote the probability simplex and Δ\Delta for circuit depth. Although these are distinct, we agree that the notation could be confusing and will replace ΔN\Delta_N with SN\mathcal{S}_N 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.

Reviewer_8RKgOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Stochastic Boolean Circuits (SBCs), a trainable architecture that learns probability distributions over Boolean gates, connections, and input literals. The authors provide theoretical guarantees for circuit validity, universal Boolean function representation, and efficient representation of certain sparse functions. Experiments on generated Boolean truth-table tasks show competitive predictive performance against MLPs.

Critical strengths

The paper presents a mathematically well-structured approach to learning Boolean circuits, with theoretical guarantees for structural validity and universal representation. The combination of stochastic gate selection, learnable connections, and input selection is interesting.

The theoretical analysis is reasonably extensive, and the experimental evaluation covers 2,000 Boolean-function tasks. The results demonstrate competitive predictive performance against conventional MLPs, particularly for larger input dimensions.

Critical weaknesses

My main concern is the limited experimental evidence supporting the proposed approach. The experiments evaluate a continuous differentiable predictor rather than the actual sampled Boolean circuits, and training and evaluation use complete truth tables without demonstrating generalization. Comparisons with existing differentiable logic gate networks are also missing, making the practical contribution difficult to assess.

A second concern is the interpretation of certifiable reasoning. The guarantee establishes valid Boolean circuit structure, but not necessarily correct reasoning or an explanation of why particular gates and connections were learned. The BNR comparison largely confirms a property guaranteed by construction rather than demonstrating improved reasoning capabilities.

Questions for authors
  1. Why are existing differentiable logic gate networks, such as Soft-Mix and Gumbel-based approaches, not included as baselines? Could the authors also clarify how SBC compares when evaluating deployed Boolean circuits on standard classification tasks?

  2. The experiments evaluate a thresholded differentiable predictor rather than sampled Boolean circuits. How well do the actual learned circuits reproduce the target functions, and how does their performance compare with the relaxed predictor?

  3. What does certifiable reasoning establish beyond valid circuit structure? Does the proposed approach provide any explanation for why particular gates or connections are selected, or why a specific prediction is produced?

8 comments
AuthorsOpenReview ↗

Response to reviewer 8RKg - Part 1/2: Weaknesses 1-2

We thank the reviewer for the thoughtful feedback and constructive suggestions. In response to the concerns about experimental evaluation, we conducted additional comparisons with differentiable logic-gate networks and evaluated the performance of extracted Boolean circuits. We present these new results below and clarify the scope of our theoretical guarantees.

Weakness#1: Limited experimental evidence: circuit performance, generalization, and missing logic-gate baselines.

The experiments address the realization problem underlying our constructive theorem: fitting a specified Boolean function from its complete truth table. We fit each of the 2,000 targets separately. Exact match (EM) requires correctness on every row.

Predicting held-out rows is a different statistical task. A partial truth table is consistent with many Boolean functions; changing even one output defines a different function. Learning a shared model that maps unseen truth tables to circuits is a cross-task synthesis problem. Both are natural extensions, whereas this paper studies per-function realization.

SBC learns both gates and routing, while Petersen et al.'s DLGN learns gates on fixed wiring. We compare three DLGN configurations using the authors' gate implementation:

  • Random-wiring DLGN: a fixed random graph.
  • Universal-Tree DLGN: a target-independent complete tree with input-selection subtrees, sufficient to represent every benchmark target.
  • Oracle-Structure DLGN: the target tree and input placements are supplied; gate identities and literal signs must be learned.
ModelMean trainable parametersSoft EM (%)
SBC (paper Table 1)812.596.1±0.3\mathbf{96.1\pm0.3}
Random-wiring DLGN510.234.48±0.2134.48\pm0.21
Universal-Tree DLGN3,824.091.19±0.4691.19\pm0.46
Oracle-Structure DLGN70.282.66±0.6782.66\pm0.67

Soft EM thresholds the relaxed predictor before checking the full truth table. Results are means and standard deviations across five seeds; parameter counts are means across the 2,000 targets.

Weakness#2: Certifiable reasoning guarantees structure, not correctness; BNR largely measures a property imposed by construction.

We thank the reviewer for raising this important distinction. Certifiable reasoning, as defined in our work, guarantees the validity of the underlying Boolean circuit structure; indeed one function may have several Boolean algorithms/circuits computing it and our model always obtains one such interpretable option; which need not be the case for black-box neural networks. Our goal is to develop an architecture in which computations are explicitly represented through Boolean gates and their connections, making them structurally interpretable and amenable to further formal verification. We do not claim that this structural guarantee alone establishes correctness. In addition, as motivated in Section 2.3, we introduce BNR as a concrete criterion for determining whether individual neurons admit a Boolean interpretation, even in architectures that are not explicitly Boolean. This allows us to investigate whether standard neural networks naturally learn such internal representations when trained on Boolean tasks.

Guaranteeing Boolean structure by construction is the architectural contribution. Every discrete SBC execution specifies its gates and connections explicitly. BNR asks whether comparable predictive accuracy yields the same neuronwise Boolean structure in an unconstrained MLP. Table 2 shows average hidden-layer BNR of only 20.9% and 19.9% for the neuron- and parameter-matched MLPs, respectively, despite their competitive EM. Thus, output accuracy alone does not establish Boolean internal computation. EM and BNR assess the predictive and structural sides of this comparison.

AuthorsOpenReview ↗

Response to reviewer 8RKg - Part 2/2: Questions 1-3

Question#1: Why are logic-gate baselines missing, and how do deployed circuits compare on standard classification tasks?

The DLGN comparisons in Weakness#1 address the missing logic-gate baseline. The matched-MLP experiment asks what predictive cost circuit structure imposes; the DLGN comparison examines gate learning with fixed wiring versus SBC's learned routing.

Our DLGN baseline uses softmax gate mixtures. Yousefi et al. (NeurIPS 2025) study Gumbel-based training, while Kim (ICML 2026) compares Soft-Mix, Gumbel, and straight-through methods. These approaches address the discretization gap and are relevant to circuit recovery in SBC. We will discuss this connection in the revision.

Standard classification evaluates generalization from sampled examples, rather than realization of a specified Boolean function. Extending SBC to that setting is a natural direction beyond the present study.

Question#2: How accurately do actual learned circuits reproduce the targets, compared with the relaxed predictor?

The predictive-marginal corollary motivates the paper's evaluation of thresholded predictions. The constructive results establish that suitable parameters exist; they do not assert convergence of gradient descent or exact recovery by local argmax. We evaluate predictive fitting with the differentiable relaxation and assess discrete circuit recovery below.

We compare relaxed, argmax, and sampled predictions on 100 targets, ten at each B∈{2,4,…,20}B \in \lbrace 2,4,\ldots,20 \rbrace, using three seeds. SBC uses full layered routing, RBF interpolation with bandwidth 0.25, and RMSProp.

PredictionRow accuracy (%)Exact match (%)
Relaxed score, thresholded99.9197.33±1.1597.33 \pm 1.15
Argmax circuit92.8143.67±2.0843.67 \pm 2.08
Sampled circuit, averaged over draws90.7244.12±2.5244.12 \pm 2.52

For each fitted model, sampled EM averages 32 circuit draws, each fixed across the entire truth table. It measures the fraction of circuits that compute the target exactly. Error bars are standard deviations across training seeds. Improving exact circuit recovery motivates dedicated training objectives and decoding methods.

Question#3: What does certifiable reasoning establish beyond valid structure, and does it explain the learned gates or a prediction?

We thank the reviewer for this question. Our notion of certifiability goes beyond the existence of a valid circuit by making the computation explicitly inspectable: each discrete SBC realization specifies its Boolean gates and connections, allowing its output to be traced and independently verified for a given input. This provides a concrete representation of how a prediction is computed, rather than treating the model as a black box. However, we distinguish this structural and computational transparency from explaining why the learning procedure selects particular gates or connections, or guaranteeing correctness with respect to the target function. We do not claim these stronger properties. We will clarify the scope of certifiability and distinguish the interpretability of discrete circuit realizations from that of the differentiable relaxation used in training.

Very sorry for the delayed response. I just realized that the comment I posted a few days ago was not visible to the authors because I had selected the wrong reader settings.

Thank you for the detailed response and additional experiments. The new comparisons with differentiable logic gate networks and the clarification of certifiable reasoning address several of my concerns.

However, the additional results show a substantial gap between the differentiable predictor and the extracted or sampled Boolean circuits. The soft predictor matched the full truth table on 97.33% of tasks, while only 44.12% of sampled Boolean circuits did so. The comparisons with other logic-gate networks report only soft predictor scores. This remains my main concern, as the practical effectiveness of the learned discrete circuits is central to the paper's contribution.

While I appreciate the additional evidence and clarifications, I am not sure if they are sufficient to change my overall assessment. I therefore maintain my original rating for the time being.

Reviewer_WsNhOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Stochastic Boolean Circuits (SBCs), a deep learning model that can express all Boolean functions and uses Boolean reasoning to do it. While it is known that neural networks can emulate Boolean circuits and compute all Boolean functions, networks obtained via training do not live up to this theoretical limit. The proposed model parameterizes distributions over Boolean circuits. Each parameterization produces a Boolean circuit with arbitrarily high probability. For each Boolean function there exists a parameterization producing a circuit that computes it. When the Boolean function is a logarithmic junta, the size of the corresponding circuit is almost linear. SBCs outperform neuron-matched neural networks. SBCs are outperformed by parameter-matched networks, but still only a fraction of the nodes in these networks compute Boolean gates.

Critical strengths
  • Clarity: The paper is easy to follow with intuitive explanations that help understand the technical parts. The topic of study is well-motivated.
  • Significance: The study of deep learning models that use Boolean reasoning is interesting and goes back a long way (e.g., the cited article by McCulloch and Pitts). Such models are more easily interpretable, helping to alleviate the black-box problem of neural networks.
Critical weaknesses
  • Soundness: The main theorems are lacking proof sketches, making it difficult to verify the theoretical claims. There are also some issues with the preliminaries; while it is easy enough to understand what the intended definitions are, the formal details do not always seem to match the intent. For example, it is stated that the existence of a directed path between nodes induces a partial order. Since partial orders are reflexive and graphs do not have self-loops, this seems to imply that an empty path is possible, but according to the definition of roots and leaves this would mean that every vertex of a directed tree is a root and none of them are leaves. For another example, it is claimed that every Boolean circuit as defined in the paper admits a vertex layering without skip connections, but the formal definition does not actually seem to rule out the possibility of skip connections (nor does it seem to quite guarantee connectedness). The definition of directed trees is also quite general and non-standard, admitting multiple roots per tree and multiple parents per vertex with no restrictions on the directions of edges.
Questions for authors

What are the main ideas behind the proofs of the theoretical results and would it be feasible to include them in the paper?

3 comments
AuthorsOpenReview ↗

Response to reviewer WsNh - Part 1/2: Proof sketches

We thank the reviewer for the positive assessment of our work and for carefully examining the theoretical details. We appreciate the suggestions regarding the formal definitions and proof presentation, and address these concerns below. We will also incorporate the relevant clarifications into the revised manuscript.

Weakness#1: Missing proof sketches and ambiguities in the graph definitions.

We are happy to provide proof sketches.

Theorem 1 proof sketch. The proof demonstrates that, almost surely, the stochastic construction of Definition 2 yields an interpretable function in a particular circuit complexity class. Step 1 establishes that the event Ωall\Omega_{\text{all}} containing outcomes for which the random variables for bit lifting, gate selection, and edge selection evaluate cleanly, i.e., as lifted bits, gate activations in G⋆\mathbb{G}^\star, and one-hot edge rows, respectively, happens almost surely. This follows directly from the definition of each random variable. Given ω∈Ωall\omega \in \Omega_{\text{all}}, lifting channel X↑:W\mathbf{X}^{\uparrow : W}, edge matrices E(l:j:e)\mathbf{E}^{(l:j:e)}, and gate activations σWj(l:σ)\mathbf{\sigma}^{W_j^{(l:\sigma)}}, in Step 2 we construct a corresponding layered DAG defined by a lifted layer, edges between nodes, and gates at nodes for each subsequent layer. In Step 3 we show by induction that this construction yields a function equivalent in terms of output at each node, in particular at the output node.

Theorem 2 proof sketch. The proof is actually a special case of Proposition 9. Let δ∈(0,1)\delta \in (0, 1) be any failure probability. In Step 0, we extract the vertices VV and edges EE from the circuit C\mathcal{C} (which is a rooted complete binary formula tree) computing our function ff. In particular, we label each vertex and edge making up the complete binary tree. In Step 1, we first apply a union bound over all gates and edges to obtain a bound δ1(η)\delta_1(\eta) on the probability that the sampled circuit disagrees with the target function on at least one input. We then apply another union bound across the input lifting channel such that the bit lifting fails with probability at most δ2(η)\delta_2(\eta). We can then find η\eta large enough such that the combined error from both parts is smaller than δ\delta, concluding the proof.

Theorem 3 proof sketch. The first part of Theorem 3, namely, the success probability bound, is obtained with the same technique as in Theorem 2, i.e., we use Proposition 9 in full generality. The accounting component regarding the SBC's depth, width, and neuron count is handled by the (circuit) complete binary tree construction of Lemma 6.

AuthorsOpenReview ↗

Response to reviewer WsNh - Part 2/2: Definitions and terminology

Weakness#1 (continued): Graph definitions.

For example, it is stated that the existence of a directed path between nodes induces a partial order. Since partial orders are reflexive and graphs do not have self-loops, this seems to imply that an empty path is possible, but according to the definition of roots and leaves this would mean that every vertex of a directed tree is a root and none of them are leaves.

Inducing a partial order is not the same as corresponding to a partial order; the former is an implicit embedding and the latter is a bijection. So the DAG embeds into the poset with the same vertex set which is completed with all compositions and self-loops (i.e., the small category on that vertex set; which has strictly more arrows). We chose not to flesh out this comment more, since it is purely technical and is not formally needed for the paper's understanding. Our goal is to cater to the largest feasible audience; i.e., the broader ML community. Nevertheless, we understand the reviewer's concerns regarding how the semantics of partial orders (reflexivity and antisymmetry) may confuse readers. We will use "strict partial order" for the reachability relation defined by positive-length directed paths.

For another example, it is claimed that every Boolean circuit as defined in the paper admits a vertex layering without skip connections, but the formal definition does not actually seem to rule out the possibility of skip connections (nor does it seem to quite guarantee connectedness).

We are unaware of where this is claimed, but would be grateful if the reviewer can point out the location. Perhaps what is being referred to is Lemma 4; namely that any Boolean function may be computed with a complete binary tree with gates in {AND,OR,PROJA}\{\mathrm{AND},\mathrm{OR},\mathrm{PROJ}_A\} and with lifted literals in variables xix_i and ¬xi\neg x_i for each i∈{1,…,B}i\in\{1,\ldots,B\}. So, it's not that every Boolean circuit can be "flattened" out/made multipartite by adding in skip connections; but simply that (in the worst-case) there is always another circuit whose graph has a compatible structure with our model and computes the same function.

The definition of directed trees is also quite general and non-standard, admitting multiple roots per tree and multiple parents per vertex with no restrictions on the directions of edges.

Thank you for pointing out this overloading of semantics. We will use "polytree" for a DAG whose underlying undirected graph is a tree. In instances where we wish to refer to properties of trees such as completeness in the context of a polytree, we can specify that this is a property of the underlying undirected graph rooted at the output. We note that this change in syntax strictly increases readability and does not change our theoretical claims and guarantees.

Question#1: What are the main proof ideas, and can they be included in the paper?

We have provided proof sketches in Weakness#1 and will include concise versions in the revised manuscript.

Thank you for the thorough response. The proof sketches are much appreciated.

Regarding the graph definitions:

Inducing a partial order is not the same as corresponding to a partial order; the former is an implicit embedding and the latter is a bijection.

The word "induce" was the wrong word to use in my review, since it is not used in rows 144-146 of the paper which is what was being referenced. There it is defined/stated that two nodes are partially ordered if there is a directed path between them. But writing "strict partial order" is a reasonable way to remove any ambiguity.

We are unaware of where this is claimed, but would be grateful if the reviewer can point out the location.

The location referred to is on rows 170-173, although rephrased in an effort to clarify the issue. Here it is said that a Boolean circuit admits a vertex layering where each edge goes from one layer VlV_l to the very next one Vl+1V_{l+1}. This was also pointed out by reviewer 6zPG, and I am satisfied with the rebuttal given there.

We will use "polytree" for a DAG whose underlying undirected graph is a tree.

This seems like a good solution.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.