PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hrad Ghoukasian, Anastasis Kratsios

arXiv:2609.13439v1cs.LGcs.AIstat.ML

TL;DR

Limited interpretability of increasingly complex models motivates learning Boolean predictors from partial truth tables within a structured, certifiable network class. MACCHIATO learns a residual-based Boolean circuit and compiles it exactly into a ReLU-MLP. Experiments report benefits in data-sparse or projection-aligned regimes and computational feasibility where flat Espresso fails.

  • Problem

    The paper addresses how to generalize from partial truth-table observations while producing a predictor in an interpretable class that exactly computes compositions of AND, XOR, and OR.

    Source: §1 · pp. 1–2

  • Method

    MACCHIATO learns low-dimensional Boolean corrections from projected residuals and compiles the resulting circuit into a ReLU-MLP with exact logical modules.

    Source: §1 · p. 2, §3.2 · p. 9, §4.2 · p. 15

  • Results

    The method improves accuracy in data-sparse and projection-aligned configurations and remains computationally feasible in configurations where flat Espresso fails.

    Source: §5.5 · pp. 23–24

  • Takeaways & Limitations

    The experiments indicate the method is most effective when its low-dimensional Boolean inductive bias matches the target structure, combining predictive accuracy, computational scalability, and certifiable interpretability.

    Source: §5.5 · pp. 23–24

    The practical algorithm reuses observations across stages, whereas the stated generalization argument uses sample splitting to remove adaptivity.

    Source: §4.1.2 · p. 13

Abstract

from arXiv · show

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/\delta))/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.

1 Introduction

The paper responds to concerns about interpreting increasingly complex AI by learning Boolean circuits from partial truth tables and compiling them into neural networks whose computations are interpretable by construction. Its approach combines residual-based circuit learning, influence-based variable selection, and exact ReLU realization, with comparisons to related logic, boosting, and neural-reasoning work.

1 Introduction

  • Limited ability to interpret complex models motivates learning Boolean functions from partial truth tables within a class of networks that exactly compute AND, XOR, and OR compositions.The paper also notes that gradient-trained networks can interpolate data or exploit shortcuts without recovering the underlying task rule [99] [29] [56] [92] [36].Source: §1 · pp. 1–2

1.1 Main Contributions

  • MACCHIATO iteratively selects influential coordinates of each residual, learns low-dimensional Boolean corrections with Espresso, and aggregates them by XOR before exactly compiling the circuit into a ReLU-MLP.The method avoids sending the full ambient-dimensional truth table to Espresso; the paper reports that flat Espresso misses its computational budget in its largest experiments while MACCHIATO completes.Source: §1.1 · pp. 2–3
  • The certificate applies to identifiable neurons or small subnetworks that implement AND, OR, and XOR modules, not to every neuron independently.The paper describes learning the Boolean circuit first and compiling its ReLU realization afterward, reversing the direction of post hoc interpretation pipelines.Source: §1.1 · p. 3

1.2 Semantic motivation for the choice of connectives.

  • The chosen primitives reflect the paper's rationale that AND and XOR have natural-language motivations, while OR remains a standard primitive of formal mathematical reasoning.The authors contrast these connectives with majority, which they describe as having less direct interpretability in ordinary English.Source: §1.2 · pp. 3–4

1.3.1 Connections to Logic Minimization and Espresso

  • Unlike high-dimensional logic-minimization approaches, MACCHIATO uses residual-adaptive, low-dimensional Espresso calls and compiles the inferred logic into a certifiably interpretable ReLU-MLP.The related-work discussion notes that heuristic Espresso is not guaranteed to find a globally minimal representation [9, 77].Source: §1.3.1 · p. 4

1.3.2 Connections to Boosting

  • Unlike boosting methods that aggregate stage predictors through weighted voting or majority voting, MACCHIATO combines Boolean residual corrections by XOR.The cited discussion says such voting can hinder interpretability in the paper's sense [79, 25, 27, 38].Source: §1.1 · p. 2, §1.3.2 · p. 4

1.3.3 Related Work on Neural Algorithmic Reasoning

  • Unlike approaches that prescribe a circuit or train a neural realization of one, MACCHIATO infers relevant variables and circuit structure from partial truth tables.Related neural algorithmic reasoning work includes Boolean-circuit execution and fixed computational graphs [48] [50].Source: §1.3.3 · p. 4

1.3.4 Connections to Influence-Based Variable Selection

  • Influence rankings are recomputed from each residual using observed Hamming-neighbor pairs, restricting each Espresso call to at most K variables rather than one fixed relevant set.The paper contrasts this with approaches using query access or specially generated perturbations.Source: §1.3.4 · p. 5

2 Problem Setting and Preliminaries

This section formalizes learning Boolean functions from partially observed truth tables and introduces structural notions and a logic-minimization procedure used by the method. Its setup treats unspecified entries as don’t-cares and uses Espresso to produce consistent, typically compact representations.

2.1 Learning Boolean Functions from Partial Truth Tables

  • The learning task is to predict a Boolean function from partially observed truth-table entries, with the stated main-body sampling setting drawing inputs independently and uniformly.The analysis also gives extensions to a general input distribution.Source: §2 · p. 5, §2.1 · p. 6

2.2 Boolean Representations and Structural Preliminaries

  • A junta depends on a limited set of relevant coordinates, and coordinate influence measures sensitivity to perturbing an input bit.Under the uniform measure, a coordinate is irrelevant exactly when its influence is zero.Source: §2.2 · pp. 6–7
  • The Boolean preliminaries define literals, cubes, minterms, and sum-of-products representations, with size measured by product terms and literal occurrences.For partial truth tables, unspecified inputs form a don’t-care set, and a completion may assign them arbitrary values while preserving specified labels.Source: §2.2 · p. 7

2.3 Espresso Logic Minimization

  • Espresso heuristically minimizes two-level logic and returns an SOP completion consistent with specified entries, using don’t-cares to simplify it without guaranteeing global minimality.The paper motivates this heuristic alternative by the poor scaling of classical exact minimization methods.Source: §2.3 · p. 7

3 Combinatorial Training from Partial Truth Tables

MACCHIATO avoids applying Espresso to the exponentially large ambient truth table by repeatedly learning low-dimensional corrections to Boolean residuals. It combines those corrections by XOR, preserving an explicitly inspectable logical representation.

3 Combinatorial Training from Partial Truth Tables

  • MACCHIATO repeatedly selects influential residual coordinates, learns a low-dimensional Espresso correction, and combines lifted corrections by XOR.Each stage selects coordinates anew, allowing the predictor to capture functions over many ambient coordinates while each Espresso call remains low-dimensional.Source: §3 · p. 8, §3.3 · p. 10

3.1 Influence-Based Dimension Reduction

  • Restricting each stage to at most K coordinates reduces each projected truth table to at most 2^K entries instead of the ambient 2^B entries.The dimension budget addresses the computational burden of applying Espresso directly to a B-dimensional partial truth table.Source: §3.1 · p. 8, §3 · p. 8

3.2 Projected Residual Learning

  • For each residual, observations sharing a projection are grouped; strict-majority labels fill cells, while ties and unobserved cells become don’t-cares.Every Boolean completion consistent with specified cells minimizes empirical 0–1 loss among functions depending only on the selected coordinates.Source: §3.2 · p. 9
  • XOR-aligning each correction with the current residual makes the accumulated predictor’s error exactly the correction’s mismatch with that residual.The procedure repeats on remaining error, with coordinates reselected at each stage.Source: §3.2 · p. 9

3.3 Sample-Based Multi-Stage Espresso Training

  • Training stops when the observed residual vanishes, no eligible coordinate remains, or the stage limit is reached; the output retains each stage’s inspectable coordinates and logical correction.No eligible coordinate may reflect weak residual structure or insufficient observed Hamming-neighbor pairs; setting τ = 0 makes this stopping criterion least restrictive.Source: §3.3 · pp. 9–10

4 Main Results

The main results pair statistical guarantees for learning from partial truth tables with an exact, certifiably interpretable ReLU-MLP realization of the learned circuit.

4.1 Statistical Guarantees

  • The statistical analysis separates recovery of residual-governing coordinates from generalization of the projected Boolean correction learned by Espresso.The stated main results use uniform sampling, with analogous guarantees for general input distributions provided in Appendix F.2.Source: §4.1 · p. 11

4.1.1 Influence Recovery for Low-Dimensional Boolean Functions

  • With sufficiently many paired samples, all coordinate influences can be estimated uniformly over S-juntas, with sample complexity exponential in S rather than ambient dimension B.When S = O(log B), the required paired-sample count is polynomial in B and 1/ε, and logarithmic in 1/δ.Source: §4.1.1 · p. 12

4.1.2 Coordinate Recovery and Truth-Table Accuracy

  • Influence estimates recover the population-selected coordinates across stages when the stated accuracy and influence-separation assumptions hold.The procedure’s sample-splitting analysis removes adaptivity, while the practical algorithm reuses observations across stages.Source: §4.1.2 · p. 13
  • With sample splitting and influence-recovery conditions, residuals depending on at most S coordinates have prediction complexity governed by S and selecting coordinates from B inputs, not the ambient truth-table size.The guarantee applies to completed stages whose residuals satisfy the low-dimensional condition.Source: §4.1.2 · pp. 13–14

4.2 Certifiably Interpretable Neural Realization

  • The learned Boolean circuit is compiled into a ReLU network without changing predictions on the Boolean cube; the certificate concerns the composed logical modules, not standalone neuron meanings.The construction can also provide a structured initialization, but unconstrained fine-tuning need not preserve its certificate.Source: §4.2 · p. 14, §4.2.1 · p. 17

4.2.1 Circuit-to-Network Compilation

  • The compiled ReLU-MLP exactly matches the learned circuit on the Boolean cube, so the circuit’s statistical guarantees transfer unchanged.The network has five non-input layers and width O(mB) when S ≤ log2 B.Source: §4.2.1 · pp. 16–17

5 Experiments

The experiments test residual learning, scalability, and exact neural realization on synthetic random-junta tasks across data-sparse, projection-aligned, and large-scale regimes. Results depend on how well the method’s low-dimensional structural bias matches the target.

5 Experiments

  • The 11 random-junta configurations vary ambient dimension, target complexity, data availability, projection alignment, stage requirements, and scale.Configs. 10–11 use the complete Boolean cube for training, so their evaluation measures reconstruction rather than out-of-sample generalization.Source: §5 · p. 18

5.2 Effect of Residual Stages

  • In Configs. 1 and 10, test accuracy rises rapidly over the first few residual stages and then improves more gradually.This is an empirical pattern, not a guarantee: fitting each stage to the training residual does not ensure improved population accuracy.Source: §5.2 · p. 20, Figure 2 · p. 21

5.3 Influence Selection versus Random Selection

  • Influence-based coordinate selection improves test accuracy over random selection in the representative settings, while its runtime effect varies by configuration.Estimating and ranking influences adds cost, although informative projections may make downstream Espresso problems easier in some settings.Source: §5.3 · pp. 21–22

5.4 Comparison with Trained Neural Networks

  • The exact circuit-derived ReLU realization beats the matched gradient-trained ReLU MLP in Configs. 6–9, while the trained ReLU MLP leads in Configs. 1–5 and 10–11.The realization preserves the Boolean predictor exactly, so its gains reflect the Boolean learner rather than neural compilation.Source: §5.4 · p. 22

5.5 Discussion

  • The structural bias can restrict performance when influential coordinates are hard to identify or K-dimensional corrections poorly capture the residual.Sparse observations can limit usable Hamming-neighbor pairs for influence estimation, while small K can exclude joint structure available to ambient-dimensional methods.Source: §5.4 · p. 22, §5.5 · p. 24

5.1 Comparison with Flat Espresso

  • The comparison is regime-dependent: the proposed method improves accuracy in data-sparse, projection-aligned Configs. 6–9 and completes in Configs. 10–11, where flat Espresso fails within the three-hour budget.In Config. 8, accuracy is 0.993 versus 0.839 for flat Espresso; in Configs. 10–11, the method reaches 0.918 and 0.904, respectively.Source: §5.1 · p. 20, §5.5 · p. 23

5.5 Discussion

  • The ablations support residual refinement and influence-based selection, and the exact neural realization preserves the logical certificate when its low-dimensional bias matches the target.The experiments do not establish uniform superiority over flat Espresso or gradient-trained networks.Source: §5.5 · pp. 23–24

6 Conclusion and Future Work

The paper presents MACCHIATO for Boolean classification, combining iterative low-dimensional logical corrections with exact ReLU-MLP compilation and an explicit circuit certificate. It reports useful inductive bias and computational feasibility in some regimes, while identifying theoretical and domain extensions as open questions.

Conclusion

  • MACCHIATO learns residual corrections on influential coordinates using Espresso, then exactly compiles the resulting AND–OR–XOR circuit into a sparsely connected ReLU-MLP with an explicit logical certificate.The paper reports guarantees for influence recovery and truth-table prediction.Source: §6 · p. 24
  • The method provides a useful inductive bias in some partially observed regimes and remains computationally feasible where direct ambient-dimensional Espresso fails.Source: §6 · p. 24

Future Work

  • Future work includes extending beyond Boolean classification, characterizing when the stage-wise bias is favorable, and weakening the thresholded top-K influence-separation condition.The paper also points to transferring the compiled computation to ReLU-Transformers while preserving the learned Boolean computation.Source: §6 · p. 24

Appendix A. Proofs of the Statistical Guarantees

Appendix A proves the statistical guarantees by establishing coordinate recovery from paired-sample influence estimates and combining influence-recovery and generalization events to bound truth-table error. It also analyzes projected majority completion and S-junta residual approximation, including the stated probability guarantee for (5) when t ≤ S.

A.1.2 A General Finite-Class Influence-Recovery Theorem

  • A uniform finite-class influence-recovery theorem controls all coordinates with probability at least 1 − δ when each receives enough paired observations.An occupancy bound ensures every coordinate receives the required number of paired samples.Source: §A.1.1 · p. 25, §A.1.2 · p. 27

A.1.3 Specialization to Juntas

  • Specializing finite-class recovery to S-juntas gives the stated polynomial dependence when S = O(log B).The proof bounds the number of Boolean functions depending on at most S coordinates before applying the general theorem.Source: §A.1.3 · pp. 27–28

A.2.1 Recovery of the Population-Selected Coordinates

  • Whenever condition (4) and Assumption 7 hold, the algorithm recovers the population-selected coordinates exactly at every completed stage.Zero-influence coordinates remain at empirical influence zero, supporting the threshold-based recovery argument.Source: §A.2.1 · pp. 28–29

A.2.2 Projected Majority as an Empirical Risk Minimizer \b

  • Every Boolean completion of the projected partial truth table that agrees with strict-majority labels is an empirical risk minimizer over GJ.Tied or unobserved projected cells are don’t-cares, since either label minimizes their empirical error.Source: §A.2.2 · p. 29

A.2.3 Generalization of the Projected Stage Learner

  • For stage-wise sample splitting, uniform generalization over supports of size at most K yields a guarantee simultaneously for all completed stages.The bound applies to the data-dependent support selected by the algorithm because it holds over every admissible support.Source: §A.2.3 · pp. 30–31

A.2.4 Recovery-to-Accuracy Guarantee

  • With probability at least 1 − δinf − δgen, every completed stage’s risk is controlled by its projected-stage guarantee and population approximation error.The proof combines simultaneous influence recovery with the projected-stage generalization result.Source: §A.2.4 · pp. 31–32

A.2.5 Proof of Accuracy under an S-Junta Residual

  • When a residual is an S-junta on the population-selected coordinates, its population approximation error is zero, enabling sharper dependence on support size.The proof applies uniform convergence to the class of functions on the residual’s selected support.Source: §A.2.5 · p. 32
  • Under t ≤ S, enlarging the universal constant if necessary yields (5), while combining the influence-recovery and generalization events gives probability at least 1 − δ_inf − δ_gen.Source: §A.2.5 · p. 32

Appendix B. Proofs for the Certifiably Interpretable Neural Realization

Appendix B proves gate identities and the exact circuit-to-network compilation, establishing how the statistical guarantees transfer to the neural realization.

Appendix B. Proofs for the Certifiably Interpretable Neural Realization

  • The appendix establishes the gate identities, exact circuit-to-network compilation, and transfer of statistical guarantees from the neural-realization results.Source: Appendix B · p. 32

B.1 Proof of the Gate-Realization Proposition

  • The gate-realization proof uses ReLU expressions to implement NOT, AND, and OR, and constructs an alternating Boolean-valued expression for XOR.For XOR, the proof considers the integer sum of the inputs and shows the constructed value alternates between 0 and 1.Source: §B.1 · p. 33

B.2 Proof of the Exact Neural Realization

The proof shows that the learned Boolean stages can be compiled into a ReLU network that agrees exactly with their XOR composition on Boolean inputs. The accompanying Espresso discussion explains how partial truth tables and heuristic cover optimization produce consistent Boolean completions.

B.2 Proof of the Exact Neural Realization

  • The compiled network exactly matches the Boolean predictor on {0, 1}^B and has non-input layer widths (2B, 2P, 2M, M, 1).Its total number of non-input neurons is 2B + 2P + 3M + 1.Source: §B.2 · p. 34

C.1 Implicants, Prime Implicants, and Covers

  • A cube is an implicant when it covers no OFF-set entries, and a cover is a collection of implicants whose union includes the ON-set.Prime implicants cannot be enlarged while remaining implicants; essential ones uniquely cover at least one ON-set point.Source: §C.1 · p. 35

C.2 Core Espresso Operations

  • Espresso iteratively reduces and expands cover cubes, then removes redundant cubes; auxiliary routines retain essential cubes or perturb a stable cover.Expand avoids the OFF-set, while Reduce preserves sufficient ON-set coverage to enable alternative expansions.Source: §C.2 · p. 35
  • Espresso preserves specified truth-table entries but does not guarantee minimizing product-term count or total literal occurrences.Its cover optimization is heuristic.Source: §C.2 · p. 35

C.3 Partial Truth Tables and the EspressoLearn Convention

  • For a partial truth table, Espresso may choose any output on don’t-care entries while preserving every specified ON- and OFF-set label.The learning analysis requires only a Boolean completion consistent with specified entries, not a globally minimum representation.Source: §C.3 · p. 36

C.4 Implementation

The implementation uses PyEDA to run Espresso on projected partial truth tables, with influence-based coordinate selection and residual-stage stopping. The appendix also specifies target generation, software, and the ambient-dimensional flat baseline.

C.4 Implementation

  • PyEDA returns Espresso’s minimized SOP expression, which serves both as the stage predictor and as the logic compiled into the exact ReLU realization.Partial tables use 0, 1, and don’t-care symbols.Source: §C.4 · p. 36, §D.3 · p. 37

D.1 Software and Computing Environment

  • Experiments use Python, PyEDA, and PyTorch; reported runtimes include the specified training and construction steps but exclude test evaluation.Algorithm 2 runtime includes exact neural-parameter construction, while trainable-MLP runtime includes gradient-based training.Source: §D.1 · pp. 36–37

D.2 Generation of Random Junta Targets

  • Random S-junta targets use S sampled coordinates and independently sampled Boolean outputs, so their realized effective dimension may be below S.Training inputs are sampled without replacement, test inputs independently, and compared methods share the same target and data within each seed.Source: §D.2 · p. 37

D.3 Espresso through PyEDA

  • PyEDA invokes compiled Espresso, and flat-baseline calls are timed out after three hours because the interface cannot return an intermediate cover.A timed-out call is recorded as a timeout rather than yielding a partial solution.Source: §D.3 · p. 37

D.4 Implementation of Algorithm 1

  • At each residual stage, the implementation selects up to K coordinates with the largest empirical residual influences and marks tied or unobserved projected cells as don’t-cares.Experiments use τ = 0, making every coordinate with positive empirical residual influence eligible.Source: §D.4 · p. 38
  • The algorithm allows at most 20 stages and stops when the observed residual vanishes or no correction is identified; later reported stages carry the terminal predictor forward.Thus, a reported stage-20 accuracy need not follow twenty nontrivial corrections.Source: §D.4 · p. 39

D.5 Flat Espresso Baseline

  • The flat baseline passes Espresso a single B-variable partial truth table, requiring Θ(2^B) entries before minimization.Runs that exceed the three-hour budget produce neither an accuracy value nor a partial predictor.Source: §D.5 · p. 39

D.6 Residual-Stage Ablation

The appendix specifies how residual-stage curves and coordinate-selection ablations are evaluated, and how exact networks are compared with trainable baselines. It also clarifies how variability and confidence intervals are reported.

D.6 Residual-Stage Ablation

  • The residual-stage experiment records successive stages from one execution, not independently retrained models.If training stops early, the terminal predictor is carried forward for later reported stage indices.Source: §D.6 · p. 39
  • Stage-wise shaded regions are 95% Student’s t confidence intervals for mean accuracy across 20 seeds, not standard deviations.The intervals quantify uncertainty in the estimated mean across randomly generated targets and datasets.Source: §D.6 · pp. 39–40

D.7 Random-K Coordinate-Selection Ablation

  • The random-K ablation changes only coordinate selection, sampling projections uniformly rather than ranking coordinates by empirical residual influence.Both procedures retain the same residual computation, projected majority, Espresso minimization, XOR aggregation, stopping rule, and stage budget.Source: §D.7 · p. 40

D.8 Exact ReLU Construction and Trainable MLPs

  • Exact networks are constructed deterministically from learned stage functions and agree with the Boolean predictor on Boolean inputs, up to floating-point evaluation error.Trainable ReLU and sigmoid baselines use the corresponding exact network’s hidden-layer count and widths, with randomly initialized parameters optimized using Adam.Source: §D.8 · p. 40
  • Trainable baselines run for 1,000 epochs in Configs. 1–9 but one epoch in full-cube Configs. 10–11, because examples per epoch differ greatly.The choice keeps update budgets within the same broad scale, without enforcing identical update counts across configurations.Source: §D.8 · pp. 40–41

D.9 Reproducibility and Reported Statistics

  • Tables report mean ± sample standard deviation across 20 seeds, whereas confidence intervals are used only for stage-wise curves.The appendix supplies additional results for configurations omitted from the main-text figures and tables.Source: §D.9 · p. 41, Appendix E · p. 41

E.1 Residual-Stage Results for All Configurations

Residual-stage trajectories vary across configurations: some improve early and plateau, while others improve more gradually or remain nearly unchanged. In the additional coordinate-selection configurations, influence-based selection has higher mean test accuracy in every configuration, though relative runtime varies.

E.1 Residual-Stage Results for All Configurations

  • Configs. 2–4 and 6 improve rapidly before plateauing, while Configs. 9 and 11 improve more gradually across residual stages.Configs. 5 and 8 remain essentially unchanged, for different reasons; Config. 7 improves only at its first additional stage. Figure 3 covers Configs. 2–3 and Figure 4 covers Configs. 4–5; both show mean test accuracy over 20 seeds with 95% confidence intervals.Source: §E.1 · p. 41, Figure 3 · p. 42, Figure 4 · p. 42
  • Additional residual stages help most when meaningful residual structure remains; after it is largely exhausted, further stages provide little or no improvement.Config. 8 is already near-perfect from its first stage despite relatively few training samples, while Config. 5’s later-stage corrections may be limited by its sparse data relative to the ambient cube.Source: §E.1 · p. 41

E.2 Influence Selection versus Random Selection: Additional Configurations

  • Influence-based selection achieves higher mean test accuracy in every additional configuration, while its relative runtime varies across settings.Table 6 reports the remaining configurations for the influence-selection ablation.Source: §E.2 · p. 42

Appendix F. Auxiliary Results

Appendix F refines the statistical analysis for influential juntas and extends influence-recovery and prediction results beyond the uniform Boolean cube. It also records auxiliary results on exact ReLU realizations and their architectural tradeoffs.

Appendix F. Auxiliary Results

  • Figures 5–7 report test accuracy across residual stages for Configs. 6–9 and 11, with means over 20 seeds and 95% confidence intervals.Table 6 is an influence-selection ablation at the stage-20 reporting point; its caption specifies mean ± standard deviation over 20 seeds but gives no values here.Source: Figure 5 · p. 43, Figure 6 · p. 43, Figure 7 · p. 44

F.1 Refined Counting for Influential Juntas

  • The refined count restricts S-juntas to functions whose relevant coordinates each have influence at least ρ, counting them by support size.The proof decomposes by relevant-coordinate set and sums over support sizes, adding the two constant functions.Source: §F.1 · pp. 43, 45

F.2 Extension to General Input Distributions

  • Appendix F extends influence-recovery and prediction analysis to arbitrary input distributions, assuming the corresponding influence-estimation conditions.The paired estimator preserves zero influence, and the proof carries over with distribution-dependent influences without changing stated failure probabilities.Source: §F.2 · pp. 45–46
  • The general-distribution extension includes a change-of-measure comparison between μ-influences and uniform influences when the measures have a bounded density ratio.The appendix also notes that μ-influence can measure sensitivity to a bit flip outside the support of μ.Source: §F.2 · p. 47

F.3 Auxiliary Results for the Certifiably Interpretable Neural Realization

  • The appendix collects neural-representation results that clarify limits of small ReLU modules and provide alternative exact realizations with different depth–width tradeoffs.These results are auxiliary to the main circuit-to-network compilation.Source: §F.3 · p. 47

F.3.1 Additional Gate Realizations and Impossibility Results

The auxiliary neural-realization results identify gate-specific limits for single ReLU units and describe exact alternatives. For XOR, those alternatives trade depth, width, and local arity.

F.3.1 Additional Gate Realizations and Impossibility Results

  • A single affine–ReLU unit cannot realize multi-input XOR or OR, while multi-input AND has a width-one realization.OR can instead use width one with depth two; the algorithm's width-two OR module is not generally reducible to one unit.Source: §F.3.1 · p. 48

F.3.2 Alternative Exact XOR Realizations

  • Exact XOR alternatives trade architecture: one has maximum width two and depth 2⌈log2 r⌉, while a depth-parameterized construction bounds depth by 2d and width by r.Increasing the composition depth reduces the largest local parity arity; these alternatives are not used in Algorithm 2.Source: §F.3.2 · p. 50
Loading 2609.13439v1…