Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization
Hrad Ghoukasian, Anastasis Kratsios
cs.LG · cs.AI · stat.ML
Quick verdict
MACCHIATO boosts Espresso on low-dim residuals to learn AND/OR/XOR circuits exactly compiled into ReLU-MLPs; sound theory, evidence synthetic-only.
Summary
The paper introduces MACCHIATO, a training algorithm for B-bit Boolean classification that jointly produces an explicit {AND, OR, XOR}-circuit and a ReLU-MLP realizing that circuit exactly. The inference stage (Algorithm 1) is a residual booster: each stage ranks input coordinates by empirical influence estimated from Hamming-neighbor pairs in a passive truth-table sample, projects the residual onto the top-K coordinates, runs Espresso logic minimization on the resulting table of at most 2^K entries, and XORs the learned sum-of-products into the accumulated circuit. The compile stage (Algorithm 2) replaces every gate with exact ReLU modules (Proposition 9), and Theorem 10 certifies that the network computes the learned circuit. Under margin-style influence-separation assumptions and a sample-splitting variant, truth-table error O(sqrt(m(2^S + S log(eB/S) + log(m/δ))/T)) is proven when each of m stage residuals is an S-junta (Theorem 8), with 2^S-type influence-recovery sample complexity (Theorem 5). On synthetic random-junta tasks the method beats depth- and width-matched Adam-trained MLPs in data-sparse, projection-aligned regimes (Config 8: 0.993 vs 0.727) and completes where ambient Espresso exceeds a 3-hour budget (Configs 10-11), but loses elsewhere (Config 2: 0.848 vs 1.000). Stated limitations include the idealized paired-sampling analysis and strong margin assumptions; the shown evaluation is synthetic-only, with no code release stated.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Algorithm 1 (Macchiato - Inference) infers an explicit {AND, OR, XOR}-circuit from T partially observed truth-table rows using influence-guided low-dimensional Espresso calls, never invoking logic minimization on more than K coordinates.
- Algorithm 2 compiles the learned circuit exactly into a ReLU-MLP, yielding a modular gate-to-subnetwork interpretability certificate (Proposition 9, Theorem 10).
- Under Assumptions 6-7, the sample-splitting variant achieves truth-table error O(sqrt(m(2^S + S log(eB/S) + log(m/δ))/T)) when each of the m stage residuals is an S-junta (Theorem 8).
- Empirically, the method outperforms depth- and width-matched Adam-trained MLPs in several data-sparse, projection-aligned regimes (e.g., Config 8: 0.993 vs 0.727) and completes where ambient-dimensional Espresso exceeds a 3-hour budget (Configs 10-11).
Strengths
Exact, construction-level interpretability certificate
Algorithm 2 learns the circuit first and compiles it exactly into a ReLU-MLP (Theorem 10), using verified gate modules (Proposition 9: NOT one unit, AND/OR width-2, r-input XOR hidden width r) backed by impossibility lemmas (Lemmas 25, 27) and depth-width alternatives (Props. 29-30), reversing the usual post-hoc interpretation direction.
Practical scalability trick with empirical proof
Never passing more than K coordinates to Espresso (Section 3, Section 1.1): in full-cube Configs 10-11 ambient Espresso fails within the 3-hour budget (Appendix D.3, D.5) while Macchiato completes (Tables 2-3 as cited).
Honest, regime-dependent empirical reporting
Statistical theory with explicit sample complexity
Unusually detailed reproducibility conventions
Weaknesses
Synthetic-only evaluation as shown
Theory-practice gap, self-acknowledged
Narrow baseline set in the visible text
Thin statistical reporting
No code or data release stated
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This method paper (arXiv 2609.13439, cs.LG) addresses B-bit Boolean classification from T uniformly drawn rows of a (partial) truth table. It claims three coupled contributions. First, Algorithm 1 ('Macchiato - Inference') infers an explicit {AND, OR, XOR}-circuit by stage-wise boosting of low-dimensional corrections: it ranks coordinates of the current residual by empirical influence estimated from Hamming-neighbor pairs in the passive sample, projects onto the top-K coordinates, runs Espresso logic minimization on a table of at most 2^K entries, and XORs the resulting sum-of-products into the accumulated circuit - never handing Espresso more than K << B coordinates. Second, Algorithm 2 ('Macchiato - Compile') realizes the learned circuit exactly as a ReLU-MLP (Theorem 10; the abstract cites a six-layer network of width O(mB)), reversing the usual train-then-interpret pipeline. Third, under influence-accuracy Assumption 6 and margin Assumption 7, the sample-splitting variant achieves truth-table error R(H_t) <= C·sqrt(m(2^S + S log(eB/S) + log(m/δ))/T) when every stage residual is an S-junta (Theorem 8), with 2^S-type influence-recovery complexity (Theorem 5). Section 1.2 adds a psycholinguistic rationale for excluding MAJ - a refreshingly explicit design choice.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is MACCHIATO in machine learning?
MACCHIATO is a training algorithm that learns Boolean functions from partially observed truth tables. It repeatedly finds the most influential input bits of the current residual, runs the Espresso logic minimizer on the small projected problem, and XORs each learned correction into an explicit AND/OR/XOR circuit that is then compiled exactly into a ReLU neural network.
Does the compiled neural network exactly match the learned Boolean circuit?
Yes. Theorem 10 shows Algorithm 2 replaces every gate with exact ReLU modules (NOT: one unit; AND/OR: width two; r-input XOR: hidden width r), so the network reproduces the circuit's outputs on the Boolean cube by construction. The certificate applies before any gradient fine-tuning, which is not covered by it.
How does MACCHIATO compare to a normally trained neural network?
It depends on the regime. On synthetic random-junta tasks it beats depth- and width-matched Adam-trained MLPs in data-sparse, projection-aligned settings (e.g., accuracy 0.993 vs 0.727 in Config 8) but loses when data is plentiful (e.g., 0.848 vs 1.000 in Config 2, and 0.918 vs 1.000 in full-cube Config 10).
What theoretical guarantee does the paper prove?
Under margin-style influence-separation assumptions, if each stage residual depends on at most S bits, the sample-splitting variant attains truth-table error O(sqrt(m(2^S + S log(eB/S) + log(m/δ))/T)) with T observations and m stages (Theorem 8); influence itself is recovered with 2^S-type sample complexity (Theorem 5).
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a head-and-tail sample with three marked '[...sampling gap...]' breaks: Table 1's configuration parameters, Sections 5.1-5.3 (Tables 2-4 and the ablation tables), part of Section 4.2.1, and Appendices A.2 and D.5-F.2 were not visible, so baseline- and experiment-breadth statements are scoped to the visible text.
- Reference entries [29]-[70] fell inside a sampling gap and could not be checked.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.