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 operatornameReLU-MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with operatornameAND,operatornameOR,operatornameXOR gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional operatornameAND,operatornameOR,operatornameXOR-circuit classes and exactly compile the resulting circuit into a operatornameReLU-MLP; we combine operatornameReLU-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 operatornameReLU-MLP (counting the input layer) of width O(mB) with truth-table error Obigl(√m(B+log(m/δ))/Tbigr). 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.