Universal Boolean Reasoning is Certifiable via Stochastic Boolean Circuits

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 $$\begin{gathered} f: \\ {0,1 \\ }^B\to \\ 0,1 \end{gathered}$$, 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 $$\begin{gathered} f: \\ {0,1 \\ }^B\to \\ 0,1 \end{gathered}$$, there exists a parameter configuration under which the sampled circuit computes $f$ with arbitrarily high probability. When $f$ is an $\mathcal{O}(\log B)$-junta, the required neuron count and circuit-description size scale near-linearly with the input dimension $B$. 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.