Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization
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 ReLU-MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with {AND,OR,XOR} gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional {AND,OR,XOR}-circuit classes and exactly compile the resulting circuit into a ReLU-MLP; we combine 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 log2(B) bits, a sample-splitting variant of our algorithm trained on T observations returns a six-layer ReLU-MLP (counting the input layer) of width 𝒪(mB) with truth-table error 𝒪(√(m(B+log(m/δ))/T)). 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.
Related
- Stability and Generalization of Straight-Through Estimators for Training Two-Layer Quantized Neural Networks
- Certifiably Correct Fréchet Means in Orbit Spaces
- Guaranteed Relative Accuracy Around a Real or Complex Zero without Extended Precision
- Optimal guaranteed sequential estimation for mean-reverting CEV diffusions
- High-order guaranteed lower bounds for the Schrödinger eigenvalue problem
BibTeX
@misc{ghoukasian2026certifiably,
title = {{Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization}},
author = {Hrad Ghoukasian and Anastasis Kratsios},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13439},
eprint = {2609.13439},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13439},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization
AU - Hrad Ghoukasian
AU - Anastasis Kratsios
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.13439
UR - https://arxiv.org/abs/2609.13439
AB - 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 ReLU-MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with {AND,OR,XOR} gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional {AND,OR,XOR}-circuit classes and exactly compile the resulting circuit into a ReLU-MLP; we combine 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 ReLU-MLP (counting the input layer) of width 𝒪(mB) with truth-table error 𝒪(√(m(B+log(m/δ))/T)). 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.
ER -