Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization

Hrad Ghoukasian; Anastasis Kratsios

cs.LGSep 11, 2026

Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization

Authors: Hrad Ghoukasian, Anastasis Kratsios

Organizations: Department of Electrical & Computer Engineering University of Toronto 40 St George St, Toronto, Ontario, M5S 2E4, Canada · Department of Mathematics McMaster University and Vector Institute 1280 Main Street West, Hamilton, Ontario, L8S 4K1, Canada

Abstract

As compute scales, models evolve, and training algorithms advance, our ability to explain the increasingly powerful AI systems they enable is eroding. To help safeguard interpretability, we introduce a specialized training algorithm (MACCHIATO) that jointly constructs (i) an explicitly structured $\operatorname{ReLU}$ -MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$ gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$ -circuit classes and exactly compile the resulting circuit into a $\operatorname{ReLU}$ -MLP; we combine $\operatorname{ReLU}$ -MLP circuit compilation, ESPRESSO logic minimization, and influence-based variable selection. Roughly speaking, our interpretability certificate is complemented by a statistical guarantee: under the theorem's influence-recovery conditions, if each of the $m$ stage-wise residuals depends on at most $\log_2(B)$ bits, a sample-splitting variant of our algorithm trained on $T$ observations returns a six-layer $\operatorname{ReLU}$ -MLP (counting the input layer) of width $\mathcal{O}(mB)$ with truth-table error $\mathcal{O}\bigl(\sqrt{m(B+\log(m/δ))/T}\bigr)$ . On synthetic random-junta tasks, our networks outperform depth- and hidden-width-matched Adam-trained MLPs in several data-sparse or projection-aligned regimes, while the trained ReLU-MLPs are stronger in others. Moreover, in our explicit PyEDA truth-table implementation, the iterative procedure completes in regimes where flat ambient-dimensional ESPRESSO exceeds the three-hour computational budget.

Figures & tables

Figure 1: The Boolean connectives on three predicates (

A

B

, and

C

) which we consider.

Config.	Target	$B$	$T$	Test size	$K$
Config. 1	$8$ -junta	$12$	$1000$	$2^{12}$	$6$
Config. 2	$6$ -junta	$12$	$1000$	$2^{12}$	$4$
Config. 3	$8$ -junta	$15$	$4000$	$2^{15}$	$6$
Config. 4	$8$ -junta	$20$	$4000$	$2^{17}$	$6$
Config. 5	$8$ -junta	$23$	$4000$	$2^{17}$	$6$
Config. 6	$8$ -junta	$12$	$500$	$2^{12}$	$6$

Table 1: Experimental configurations. The configurations cover moderate-dimensional, data-sparse, projection-aligned, higher-complexity, and large-scale regimes.

Config.	Method	Stage 1	Stage 5	Stage 20 / Flat
Config. 1	Proposed	$0.708\pm 0.021$	$0.823\pm 0.027$	$0.842\pm 0.032$
	Flat	—	—	$\mathbf{0.965\pm 0.021}$
Config. 2	Proposed	$0.731\pm 0.053$	$0.844\pm 0.038$	$0.848\pm 0.043$
	Flat	—	—	$\mathbf{1.000\pm 0.000}$
Config. 3	Proposed	$0.704\pm 0.018$	$0.821\pm 0.017$	$0.838\pm 0.027$
	Flat	—	—	$\mathbf{1.000\pm 0.000}$

Table 2: Predictive accuracy of the proposed method and flat ambient-dimensional Espresso . Results are mean

\pm

standard deviation over

20

seeds. “Failed” indicates that flat Espresso did not return a predictor within the computational budget.

Config.	Proposed	Flat Espresso
Config. 1	$0.42\pm 0.04$	$\mathbf{0.11\pm 0.01}$
Config. 2	$0.34\pm 0.02$	$\mathbf{0.09\pm 0.02}$
Config. 3	$1.62\pm 0.19$	$\mathbf{1.28\pm 0.15}$
Config. 4	$\mathbf{1.79\pm 0.13}$	$66.90\pm 6.17$
Config. 5	$\mathbf{1.07\pm 0.19}$	$578.41\pm 52.65$
Config. 6	$0.22\pm 0.02$	$\mathbf{0.10\pm 0.01}$

Table 3: Cumulative stage-

20

runtime of the proposed method and runtime of flat Espresso , in seconds. Results are mean

\pm

standard deviation over

20

seeds. Boldface denotes the faster completed method.

Panel of Figure 2 — Figure 2: Test accuracy across residual stages for Configs. 1 and 10. Curves show the mean over $20$ seeds and shaded regions show $95\%$ confidence intervals for the mean.

Config.	Selection rule	Test accuracy	Runtime (s)
Config. 3	Influence top- $K$	$\mathbf{0.838\pm 0.027}$	$\mathbf{1.62\pm 0.19}$
	Random $K$	$0.595\pm 0.118$	$1.65\pm 0.12$
Config. 6	Influence top- $K$	$\mathbf{0.798\pm 0.026}$	$\mathbf{0.22\pm 0.02}$
	Random $K$	$0.567\pm 0.033$	$0.26\pm 0.02$
Config. 10	Influence top- $K$	$\mathbf{0.918\pm 0.014}$	$830.84\pm 69.02$
	Random $K$	$0.666\pm 0.033$	$\mathbf{371.24\pm 19.90}$

Table 4: Influence-selection ablation at the stage-

20

reporting point. Results are mean

\pm

standard deviation over

20

seeds. Boldface denotes the better value within each configuration and metric.

Config.	Method	Test accuracy	Runtime (s)
Config. 1	Exact ReLU	$0.842\pm 0.032$	$\mathbf{0.46\pm 0.06}$
	Trained ReLU, 1000 ep.	$\mathbf{0.917\pm 0.025}$	$8.25\pm 0.78$
	Trained sigmoid, 1000 ep.	$0.669\pm 0.046$	$8.31\pm 0.80$
Config. 2	Exact ReLU	$0.848\pm 0.043$	$\mathbf{0.35\pm 0.05}$
	Trained ReLU, 1000 ep.	$\mathbf{1.000\pm 0.001}$	$7.95\pm 1.38$
	Trained sigmoid, 1000 ep.	$0.828\pm 0.090$	$8.03\pm 1.11$

Table 5: Exact circuit-derived ReLU realization versus depth- and hidden-width-matched gradient-trained MLPs. Results are mean

\pm

standard deviation over

20

seeds. Boldface denotes the highest accuracy and lowest runtime within each configuration.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Test accuracy across residual stages for Configs. 2–3. Curves show the mean over $20$ seeds and shaded regions show $95\%$ confidence intervals for the mean.

Panel of Figure 4 — Figure 4: Test accuracy across residual stages for Configs. 4–5. Curves show the mean over $20$ seeds and shaded regions show $95\%$ confidence intervals for the mean.

Panel of Figure 5 — Figure 5: Test accuracy across residual stages for Configs. 6–7. Curves show the mean over $20$ seeds and shaded regions show $95\%$ confidence intervals for the mean.

Panel of Figure 6 — Figure 6: Test accuracy across residual stages for Configs. 8–9. Curves show the mean over $20$ seeds and shaded regions show $95\%$ confidence intervals for the mean.

Figure 7: Test accuracy across residual stages for Config. 11. The curve shows the mean over

20

seeds and the shaded region shows the

95\%

confidence interval for the mean.

Config.	Selection rule	Test accuracy	Runtime (s)
Config. 1	Influence top- $K$	$\mathbf{0.842\pm 0.032}$	$0.42\pm 0.04$
	Random $K$	$0.606\pm 0.039$	$\mathbf{0.41\pm 0.02}$
Config. 2	Influence top- $K$	$\mathbf{0.848\pm 0.043}$	$0.34\pm 0.02$
	Random $K$	$0.677\pm 0.126$	$\mathbf{0.30\pm 0.02}$
Config. 4	Influence top- $K$	$\mathbf{0.763\pm 0.049}$	$1.79\pm 0.13$
	Random $K$	$0.536\pm 0.032$	$\mathbf{1.68\pm 0.11}$

Appendix

Table 6: Influence-selection ablation for the remaining configurations at the stage-

20

reporting point. Results are mean

\pm

standard deviation over

20

seeds. Boldface denotes the better value within each configuration and metric.

Interpretable ML

Interpretable machine learning develops models and explanations that make predictions, evidence, and decision processes understandable to people.

See all 306 papers

Feb 22, 2026

Why ReLU? A Bit-Model Dichotomy for Deep Network Training

Theoretical analyses of Empirical Risk Minimization (ERM) are standardly framed within the Real-RAM model of computation. In this setting, training even simple neural networks is known to be

\exists \mathbb{R}

-complete -- a complexity class believed to be harder than NP, that characterizes the difficulty of solving systems of polynomial inequalities over the real numbers. However, this algebraic framework diverges from the reality of digital computation with finite-precision hardware. In this work, we analyze the theoretical complexity of ERM under a realistic bit-level model (

\mathsf{ERM}_{\text{bit}}

), where network parameters and inputs are constrained to be rational numbers with polynomially bounded bit-lengths. Under this model, we reveal a sharp dichotomy in tractability governed by the network's activation function. We prove that for deep networks with {\em any} polynomial activations with rational coefficients and degree at least

2

, the bit-complexity of training is severe: deciding

\mathsf{ERM}_{\text{bit}}

\#P

-Hard, hence believed to be strictly harder than NP-complete problems. Furthermore, we show that determining the sign of a single partial derivative of the empirical loss function is intractable (unlikely in BPP), and deciding a specific bit in the gradient is

\#P

-Hard. This provides a complexity-theoretic perspective for the phenomenon of exploding and vanishing gradients. In contrast, we show that for piecewise-linear activations such as ReLU, the precision requirements remain manageable:

\mathsf{ERM}_{\text{bit}}

is contained within NP (specifically NP-complete), and standard backpropagation runs in polynomial time. Our results demonstrate that finite-precision constraints are not merely implementation details but fundamental determinants of learnability.

Ilan Doron-Arad, Elchanan Mossel

MIT, Cambridge, MA, USA

Empirical Risk Minimization ReLU Neural Networks Polynomial Neural Networks

Ask PDF

Aug 12, 2026

The Boolean Power of ReLU

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in

Σ

-MPLang, for any collection

Σ

of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than trReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than {TrReLU,id}-GNNs with respect to Boolean queries on Boolean-featured graphs.

Pablo Barceló, Floris Geerts, Matthias Lanzinger +2

Pontifical Catholic University · IMFD & CENIA, Chile · University of Antwerp +4

ReLU Neural Networks GNN Expressivity Neural Network Expressivity

Ask PDF

Jul 15, 2026

Random Parameter Noise Does Not Make Exact ReLU Verification Easy

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to

[-2,2]

, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption

\mathrm{NP}\not\subseteq\mathrm{BPP}

, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level

σ_\star=2^{-11}

for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in

[-1,1]

. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula

Φ

with

m

clauses, a four-ReLU-per-clause construction satisfies

\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3

, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in

m

survives the aggregate perturbation of all coefficients with probability at least

1-e^{-m/8}

. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.

Mojtaba Soltanalian

Department of Electrical and Computer Engineering University of Illinois Chicago

Neural Network Verification ReLU Neural Networks

Ask PDF

Abstract

Interpretable ML

Explore similar work

Why ReLU? A Bit-Model Dichotomy for Deep Network Training

The Boolean Power of ReLU

Random Parameter Noise Does Not Make Exact ReLU Verification Easy