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

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 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 O(mB) with truth-table error O (sqrt m(B+ (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.