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

# Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization
Source: [https://arxiv.org/html/2609.13439](https://arxiv.org/html/2609.13439)
Hrad Ghoukasian hrad\.ghoukasian@mail\.utoronto\.caAffiliation:Department of Electrical & Computer EngineeringAffiliation:University of TorontoAffiliation:40 St George St, Toronto, Ontario, M5S 2E4, CanadaAnastasis Kratsios kratsioa@mcmaster\.caAffiliation:Department of MathematicsAffiliation:McMaster University and Vector InstituteAffiliation:1280 Main Street West, Hamilton, Ontario, L8S 4K1, Canada

###### 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 structuredReLU\\operatorname\{ReLU\}\-MLP from partial truth\-table observations and \(ii\) an explicit Boolean circuit over signed literals with\{AND,OR,XOR\}\\\{\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}gatescertifyingwhat its subnetworks compute and how they compose\. Intuitively, weiteratively project the residuals of a Boolean function onto low\-dimensional\{AND,OR,XOR\}\\\{\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}\-circuit classes and exactly compile the resulting circuit into aReLU\\operatorname\{ReLU\}\-MLP; we combineReLU\\operatorname\{ReLU\}\-MLP circuit compilation,Espressologic 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 themmstage\-wise residuals depends on at mostlog2⁡\(B\)\\log\_\{2\}\(B\)bits, a sample\-splitting variant of our algorithm trained onTTobservations returns a six\-layerReLU\\operatorname\{ReLU\}\-MLP \(counting the input layer\) of width𝒪⁡\(m​B\)\\mathcal\{O\}\(mB\)with truth\-table error𝒪⁡\(m⁡\(B\+log⁡\(m/δ\)\)/T\)\\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 explicitPyEDAtruth\-table implementation, the iterative procedure completes in regimes where flat ambient\-dimensionalEspressoexceeds the three\-hour computational budget\.

††shortheadings:Certifiably Interpretable Training of ReLU\-MLPs for Boolean Tasks / H\. Ghoukasian and A\. Kratsios††firstpage:1††editor:My editor###### keywords

AI interpretability; certifiable interpretability; logical reasoning; Boolean function learning; partial truth tables; interpretable neural networks; Boolean circuits; logic minimization\.

## 1Introduction

The remarkable gains in modern AI have been driven by rapid advances in compute[Owens et al\. \(2008\)](https://arxiv.org/html/2609.13439#bib.bib33), increasingly expressive model classes[Vaswani et al\. \(2017\)](https://arxiv.org/html/2609.13439#bib.bib34), and increasingly sophisticated gradient\-based training algorithms[Loshchilov and Hutter \(2019\)](https://arxiv.org/html/2609.13439#bib.bib35)\. Nevertheless, the rapid scaling of modern deep learning\([Hestness et al\., 2017](https://arxiv.org/html/2609.13439#bib.bib38);[Kaplan et al\., 2020](https://arxiv.org/html/2609.13439#bib.bib39);[Bahri et al\., 2024](https://arxiv.org/html/2609.13439#bib.bib40)\)has raised a number ofAI safetyconcerns, e\.g\.[Bengio et al\. \(2024\)](https://arxiv.org/html/2609.13439#bib.bib47);[Bengio et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib48), partly driven by our limited ability to interpret how increasingly complex models arrive at their predictions\.

These concerns are mirrored by recent legislative efforts to establish interpretability and transparency guardrails for AI systems across North America[Treasury Board of Canada Secretariat \(2026\)](https://arxiv.org/html/2609.13439#bib.bib41);[Secretaría de Gobernación \(2024\)](https://arxiv.org/html/2609.13439#bib.bib42);[Tabassi \(2023\)](https://arxiv.org/html/2609.13439#bib.bib37), Europe[European Parliament and Council of the European Union \(2024\)](https://arxiv.org/html/2609.13439#bib.bib36), China[Cyberspace Administration of China and Ministry of Industry and Information Technology and Ministry of Public Security and State Administration for Market Regulation \(2022\)](https://arxiv.org/html/2609.13439#bib.bib43), and Russia[President of the Russian Federation \(2024\)](https://arxiv.org/html/2609.13439#bib.bib45)\. Yet, partly because standardized tools for interpreting AI systems remain underdeveloped, such guidelines are often less concrete than regulatory frameworks governing other “mathematical technologies with widespread social impact\.” For instance, financial risk management has developed standardized quantitative tools, such as expected shortfall[Delbaen \(1998\)](https://arxiv.org/html/2609.13439#bib.bib61), together with comparatively explicit regulatory requirements introduced following the 2008 financial crisis, including Basel 2\.5[Basel Committee on Banking Supervision \(2009\)](https://arxiv.org/html/2609.13439#bib.bib44)and the FRTB[Basel Committee on Banking Supervision \(2012\)](https://arxiv.org/html/2609.13439#bib.bib46)\.

While equally tangible interpretability standards for AI remain a longer\-term objective, the goal of this paper is to make a concrete step toward models whose internal computations are interpretable by construction\. Rather than developing tools for interpreting models obtained through standard gradient\-based training, cf\. reasoning probes[Alain and Bengio \(2017\)](https://arxiv.org/html/2609.13439#bib.bib52);[Hewitt and Liang \(2019\)](https://arxiv.org/html/2609.13439#bib.bib53);[Burns et al\. \(2023\)](https://arxiv.org/html/2609.13439#bib.bib54)and attribution methods[Ribeiro et al\. \(2016\)](https://arxiv.org/html/2609.13439#bib.bib58);[Lundberg and Lee \(2017\)](https://arxiv.org/html/2609.13439#bib.bib59);[Sundararajan et al\. \(2017\)](https://arxiv.org/html/2609.13439#bib.bib60), we introduce a training algorithm that producesboth:

1. \(i\)a predictive neural network
2. \(ii\)an explicit decomposition of that network into components whose computations can be read off as logical formulas\.

We pursue this alternative route in light of growing evidence that gradient\-trained neural networks can interpolate training data or exploit statistical shortcuts without necessarily recovering the underlying rule governing the task[Zhang et al\. \(2017\)](https://arxiv.org/html/2609.13439#bib.bib49);[Geirhos et al\. \(2020\)](https://arxiv.org/html/2609.13439#bib.bib51);[McCoy et al\. \(2019\)](https://arxiv.org/html/2609.13439#bib.bib50);[Vershynin \(2020\)](https://arxiv.org/html/2609.13439#bib.bib56);[Vardi et al\. \(2022\)](https://arxiv.org/html/2609.13439#bib.bib55);[Hong and Kratsios \(2024\)](https://arxiv.org/html/2609.13439#bib.bib57)\.

Here, we focus on the simplest realistic version of this road to interpretability; namely, we considerBB\-bit Boolean classifiersf:\{0,1\}B→\{0,1\}f:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}observed throughTTsamples of their truth table, i\.e\., partially observed rows of the table\.

Ourobjectiveis to develop a training procedure that infers a model which is accurate enough togeneralizebeyond the data on which it was trained and flexible enough to reconstruct a broad range of Boolean tasksff, while satisfying theconstraintof belonging to the small “combinatorially meaningful” subset of interpretable networks: namely, those that exactly compute compositions ofAND\\operatorname\{AND\},XOR\\operatorname\{XOR\}, andOR\\operatorname\{OR\}\. We choose these elementary connectives based on thenatural\-languagemotivations discussed below \(cf\. §[1\.2](https://arxiv.org/html/2609.13439#S1.SS2)\)\.

### 1\.1Main Contributions

Our main practical contributions are Algorithms[1](https://arxiv.org/html/2609.13439#algorithm1)and[2](https://arxiv.org/html/2609.13439#algorithm2), together with their accompanying theoretical guarantees\. Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1),Macchiato111The name is inspired byEspresso:Macchiatobuilds on repeated low\-dimensionalEspressocalls to produce a more structured learning procedure\., infers an explicit\{AND,OR,XOR\}\\\{\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}\-circuit representation of a partially observed Boolean functionf:\{0,1\}B→\{0,1\}f:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}fromTTlabeled truth\-table observations\. It proceeds iteratively by identifying a small set of the most influential coordinates of the current residual, marginalizing over the remaining coordinates, and applyingEspresso[Brayton et al\. \(1982\)](https://arxiv.org/html/2609.13439#bib.bib24)222For a GPU implementation ofEspresso, see[Kanakia et al\. \(2021\)](https://arxiv.org/html/2609.13439#bib.bib83)\.to infer a low\-dimensional Boolean correction, which is then integrated into the accumulated circuit byXOR\\operatorname\{XOR\}\.

A critical practical feature of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)is that it never passes the full ambient\-dimensional truth table toEspresso: each call involves at mostK≪BK\\ll Bcoordinates\. This avoids the exponential ambient representation of size2B2^\{B\}and substantially extends the regime in whichEspresso\-based learning remains computationally feasible; in our largest experiments, direct ambient\-dimensionalEspressofails to return within the computational budget, while Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)completes successfully \(Tables[2](https://arxiv.org/html/2609.13439#S5.T2)–[3](https://arxiv.org/html/2609.13439#S5.T3)and Section[5\.1](https://arxiv.org/html/2609.13439#S5.SS1)\)\.

##### Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\(Macchiato – Inference\): Scalable Iterative Circuit Inference\.

Under a residual influence\-separation condition \(Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8)\), we establish a quantitative influence\-recovery guarantee \(Theorem[6](https://arxiv.org/html/2609.13439#Thmtheorem6)\) and show that, when the stage\-wise residuals have low effective dimension, Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)achieves a corresponding high\-probability truth\-table accuracy guarantee \(Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9)\)\. More generally, Theorem[14](https://arxiv.org/html/2609.13439#Thmtheorem14)gives simultaneous influence recovery over arbitrary finite Boolean function classes, while Theorem[20](https://arxiv.org/html/2609.13439#Thmtheorem20)quantifies the prediction error when the selected projection incurs nonzero approximation error\.

Although the main results are stated under uniform sampling on\{0,1\}B\\\{0,1\\\}^\{B\}, the analysis extends to arbitrary input distributions; see Appendix[F\.2](https://arxiv.org/html/2609.13439#A6.SS2)\. In particular, the corresponding distribution\-dependent influence\-recovery guarantee is given in Corollary[22](https://arxiv.org/html/2609.13439#Thmtheorem22), while Proposition[24](https://arxiv.org/html/2609.13439#Thmtheorem24)provides a direct comparison between uniform and distribution\-dependent influences\.

##### Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)\(Macchiato – Compile\): CertifiableReLU\\operatorname\{ReLU\}\-MLP Compilation\.

Our interpretability certificate is formalized by Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11), which shows that theReLU\\operatorname\{ReLU\}\-MLP produced by Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)exactly realizes the\{AND,OR,XOR\}\\\{\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}\-circuit learned in the first phase\. Briefly, using the “surgery” technique of\([Kratsios et al\., 2026a](https://arxiv.org/html/2609.13439#bib.bib62), Proposition 6\.6\), we construct standardized smallReLU\\operatorname\{ReLU\}subnetworks that exactly realize the required Boolean gates and replace the corresponding gates in the learned circuit\.

Thus, the Boolean circuit is learned first and itsReLU\\operatorname\{ReLU\}\-MLP realization is then*compiled*\. This reverses the direction of post hoc interpretability pipelines, in which a neural network is trained first and its internal computation is subsequently interpreted or approximated symbolically\.

We emphasize that our certificate is*modular*: we do not claim that every individual neuron has an independent semantic interpretation\. Rather, identifiable neurons or small subnetworks together exactly realize the elementary operationsAND\\operatorname\{AND\},OR\\operatorname\{OR\}, andXOR\\operatorname\{XOR\}, and their composition is known by construction\.

### 1\.2Semantic motivation for the choice of connectives\.

We focus on the connectivesAND\\operatorname\{AND\},OR\\operatorname\{OR\}, andXOR\\operatorname\{XOR\}since psychological research suggests that conjunction \(AND\\operatorname\{AND\}\) is a basic operation in ordinary propositional reasoning[Johnson\-Laird et al\. \(1992\)](https://arxiv.org/html/2609.13439#bib.bib26), while exclusive disjunction \(XOR\\operatorname\{XOR\}\) arises naturally as a pragmatic interpretation of ‘‘or’’ in everyday English333For example, “Would you like coffee or tea?” is ordinarily understood exclusively \(XOR\), rather than inclusively \(OR\)\.[Chevallier et al\. \(2008\)](https://arxiv.org/html/2609.13439#bib.bib27)\. Although inclusive disjunction \(OR\\operatorname\{OR\}\) is somewhat less natural in ordinary English, it is a standard primitive of formal mathematical reasoning and elementary logic[Dawkins and Cook \(2017\)](https://arxiv.org/html/2609.13439#bib.bib30)\.

By contrast, while more computationally efficient[Furst et al\. \(1984\)](https://arxiv.org/html/2609.13439#bib.bib31);[Håstad \(1986\)](https://arxiv.org/html/2609.13439#bib.bib25), the mathematical majority operationMAJ\\operatorname\{MAJ\}has no equally direct counterpart among elementary propositional connectives in English\. Its natural\-language realizations are instead proportional quantifiers such as “most” and “more than half,” with “mostAAareBB” evaluated by comparing\#⁡\(A∩B\)\\\#\(A\\cap B\)and\#⁡\(A∖B\)\\\#\(A\\setminus B\)[Pietroski et al\. \(2009\)](https://arxiv.org/html/2609.13439#bib.bib28)\. Moreover, English “most” need not correspond to the sharp50%50\\%threshold encoded byMAJ\\operatorname\{MAJ\}and is often interpreted as “significantly more than half”[Denić and Szymanik \(2022\)](https://arxiv.org/html/2609.13439#bib.bib32)\. Proportional quantifiers such as “more than half” are also verified more slowly and less accurately than simpler quantifiers such as “all” and “some”[Szymanik and Zajenkowski \(2010\)](https://arxiv.org/html/2609.13439#bib.bib29)\. Thus, majority may be less directly interpretable in ordinary English; for this reason, we have chosen not to include it\.

### 1\.3Related Work

#### 1\.3\.1Connections to Logic Minimization andEspresso

Recently,[Qiao et al\. \(2023\)](https://arxiv.org/html/2609.13439#bib.bib67)usedEspressoafter black\-box denoising to learn compact interpretable DNF classifiers\. More broadly, although heuristicEspressooften approaches the solutions of computationally prohibitive exact minimizers[McCluskey \(1956\)](https://arxiv.org/html/2609.13439#bib.bib16);[Rudell and Sangiovanni\-Vincentelli \(1987\)](https://arxiv.org/html/2609.13439#bib.bib81), its own scalability limitations have motivated SAT\-, GPU\-, and million\-scale variants[Sapra et al\. \(2003\)](https://arxiv.org/html/2609.13439#bib.bib82);[Kanakia et al\. \(2021\)](https://arxiv.org/html/2609.13439#bib.bib83);[Nazemi et al\. \(2021\)](https://arxiv.org/html/2609.13439#bib.bib84); unlike these works, we avoid high\-dimensional minimization through residual\-adaptive low\-dimensional calls and compile the inferred logic into a certifiably interpretableReLU\\operatorname\{ReLU\}\-MLP\.

#### 1\.3\.2Connections to Boosting

Our construction is related to classical boosting[Schapire \(1990\)](https://arxiv.org/html/2609.13439#bib.bib63), greedy residual decompositions such as matching pursuit[Mallat and Zhang \(1993\)](https://arxiv.org/html/2609.13439#bib.bib71), and classical Boolean logic minimization[McCluskey \(1956\)](https://arxiv.org/html/2609.13439#bib.bib16)\. Similar to Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1), classical boosting performs stage\-wise learning, but typically aggregates stage predictors through weighted voting[Schapire \(1990\)](https://arxiv.org/html/2609.13439#bib.bib63);[Freund and Schapire \(1997\)](https://arxiv.org/html/2609.13439#bib.bib4);[Friedman \(2001\)](https://arxiv.org/html/2609.13439#bib.bib64), rather than throughXOR\\operatorname\{XOR\}\. Such weighted aggregation can hinder “human” interpretability in the sense discussed in Section[1\.2](https://arxiv.org/html/2609.13439#S1.SS2)\. A similar limitation applies to the DNF boosting algorithm of[Jackson \(1997\)](https://arxiv.org/html/2609.13439#bib.bib66), which relies on majority\-voting aggregation\. While there are some specialized boosting algorithms for Boolean classification problems, e\.g\.,[Feldman \(2010\)](https://arxiv.org/html/2609.13439#bib.bib65), they typically do not perform influence\-estimation since interpretable parsimonious intermediate subcircuits and scalability are not their focus\.

Related approaches include binary variants of matching pursuit \(e\.g\.,[Chang et al\. \(2018\)](https://arxiv.org/html/2609.13439#bib.bib69);[Ramírez \(2018\)](https://arxiv.org/html/2609.13439#bib.bib68)\)\. While these methods likewise greedily construct structured representations from Boolean components, they seek compact factorizations of observed binary data rather than learning an unknown Boolean function from partial observations in a parsimonious fashion\. Recently,[Prairie and Tan \(2026\)](https://arxiv.org/html/2609.13439#bib.bib70)showed that boosting can be accelerated for concept classes closed under𝒪⁡\(log⁡\(1/γ\)\)\\mathcal\{O\}\(\\log\(1/\\gamma\)\)\-XOR\\operatorname\{XOR\}\. Their use of the connective is rather different: while we use it for stage\-wise boosting of Boolean residuals, they use XOR\-closure to efficiently convert a weak learner into a strong learner via list decoding\.

Finally, these methodsdo notproduceneural networks; thus, they do not address the problem of inferring an interpretable neural network with a formal certificate\. Their connection to our work is instead limited to the stage\-wise, boosting\-like treatment of residuals\.

#### 1\.3\.3Related Work on Neural Algorithmic Reasoning

Our perspective is closely related to*neural algorithmic reasoning*\(NAR\)[Veličković and Blundell \(2021\)](https://arxiv.org/html/2609.13439#bib.bib72);[Kratsios et al\. \(2026a\)](https://arxiv.org/html/2609.13439#bib.bib62), which studies neural networks as executors of algorithmic computations, including Boolean circuits[Jukna \(2012\)](https://arxiv.org/html/2609.13439#bib.bib73)\. Our main departure is that we do not prescribe the circuit and train its neural realization, e\.g\.[Li et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib14)\. Instead, from a partial truth table, we certifiably infer the relevant variables together with the size and structure of the circuit, rather than parameterizing networks with a fixed computational graph[Kohut and Steinbach \(2004\)](https://arxiv.org/html/2609.13439#bib.bib15)or constructing distributions over Boolean circuits of fixed size[Li et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib14)\.

The connection between neural and logical computation dates back to[McCulloch and Pitts \(1943\)](https://arxiv.org/html/2609.13439#bib.bib74)and underlies modern NAR[Veličković et al\. \(2020\)](https://arxiv.org/html/2609.13439#bib.bib75);[Veličković et al\. \(2022\)](https://arxiv.org/html/2609.13439#bib.bib76);[Ibarz et al\. \(2022\)](https://arxiv.org/html/2609.13439#bib.bib77);[Selsam et al\. \(2019\)](https://arxiv.org/html/2609.13439#bib.bib79);[Kratsios et al\. \(2025b\)](https://arxiv.org/html/2609.13439#bib.bib78)\. Related architectural approaches learn logical gates, rules, or sparse connectivity[Petersen et al\. \(2022\)](https://arxiv.org/html/2609.13439#bib.bib19);[Bührer et al\. \(2025\)](https://arxiv.org/html/2609.13439#bib.bib80);[Yue and Jha \(2024\)](https://arxiv.org/html/2609.13439#bib.bib92);[Perreault et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib93);[Ciravegna et al\. \(2023\)](https://arxiv.org/html/2609.13439#bib.bib94);[Soegeng et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib90); our procedure instead uses residual\-adaptive influence selection and low\-dimensional logic minimization before exactly compiling the inferred circuit into the final network\.

#### 1\.3\.4Connections to Influence\-Based Variable Selection

Our influence\-based dimension reduction is related to structural junta approximation\([Friedgut, 1998](https://arxiv.org/html/2609.13439#bib.bib99)\), junta learning\([Mossel et al\., 2004](https://arxiv.org/html/2609.13439#bib.bib6)\), and influential\-variable methods for Boolean\-function and DNF learning\([Servedio, 2004](https://arxiv.org/html/2609.13439#bib.bib7);[Feldman, 2012](https://arxiv.org/html/2609.13439#bib.bib8)\), and more broadly filter\-based feature selection and sensitivity analysis\([Guyon and Elisseeff, 2003](https://arxiv.org/html/2609.13439#bib.bib9);[Fleuret, 2004](https://arxiv.org/html/2609.13439#bib.bib10);[Sobol, 2001](https://arxiv.org/html/2609.13439#bib.bib11)\)\. Related approaches also rank variables using quantities such as mutual information\([Schnapp and Sabato, 2021](https://arxiv.org/html/2609.13439#bib.bib12)\)\. Our use of influence differs in that the selected coordinates are recomputed from the Boolean residual at each stage and therefore need not form a single fixed relevant set\. We estimate influence using Hamming\-neighbor pairs observed in a passive partial truth table, rather than assuming query access or specially generated perturbations, and use the resulting ranking to restrict eachEspressocall to at mostK≪BK\\ll Bvariables\.

#### 1\.3\.5Other Related Work

Closest to our setting,[Soegeng et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib90)learns sparse differentiable truth\-table rules, while[d’Ascoli et al\. \(2023\)](https://arxiv.org/html/2609.13439#bib.bib91)predicts Boolean formulas from incomplete truth tables;[Yue and Jha \(2024\)](https://arxiv.org/html/2609.13439#bib.bib92);[Perreault et al\. \(2026\)](https://arxiv.org/html/2609.13439#bib.bib93);[Ciravegna et al\. \(2023\)](https://arxiv.org/html/2609.13439#bib.bib94)instead learn interpretable logical neural models, and[Oliveira and Sangiovanni\-Vincentelli \(1993\)](https://arxiv.org/html/2609.13439#bib.bib95);[Boroumand et al\. \(2021\)](https://arxiv.org/html/2609.13439#bib.bib96)learn Boolean\-circuit structure from examples\. Related rule\-learning approaches include Boolean rule ensembles[Mita et al\. \(2020\)](https://arxiv.org/html/2609.13439#bib.bib98)and classical AND\-XOR representations[Sasao \(1993\)](https://arxiv.org/html/2609.13439#bib.bib97)\. Our method differs by combining residual\-adaptive influence selection with repeated low\-dimensionalEspressocalls and exactXOR\\operatorname\{XOR\}aggregation; moreover, under explicit assumptions we provide statistical guarantees and compile the learned circuit exactly into aReLU\\operatorname\{ReLU\}\-MLP with a gate\-to\-subnetwork certificate\. Thus, our contribution combines scalable circuit inference, statistical control, and exact neural realization\.

### Paper Organization

Section[2](https://arxiv.org/html/2609.13439#S2)introduces the learning problem and required preliminaries, and Section[3](https://arxiv.org/html/2609.13439#S3)develops our multi\-stage circuit\-learning algorithm\. Section[4](https://arxiv.org/html/2609.13439#S4)presents our main results, comprising the statistical guarantees in Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)and the certifiably interpretableReLU\\operatorname\{ReLU\}\-MLP realization in Section[4\.2](https://arxiv.org/html/2609.13439#S4.SS2)\. Section[5](https://arxiv.org/html/2609.13439#S5)presents our experiments, and Section[6](https://arxiv.org/html/2609.13439#S6)concludes\. Supporting proofs, details onEspresso, implementation details, additional experiments, and auxiliary results are deferred to the appendices\.

## 2Problem Setting and Preliminaries

This section introduces the learning problem and the Boolean concepts used throughout\. We first formalize learning a Boolean function from a partial truth table, with the goal of generalizing to unseen entries while producing a certifiably interpretable model expressed through explicit Boolean operations\. We then review the Boolean representations and structural notions used in our analysis and describe theEspressoalgorithm and the logic\-minimization subroutine used to construct compact Boolean representations from partially specified truth tables\.

### 2\.1Learning Boolean Functions from Partial Truth Tables

Letℕ\+:=\{1,2,…\}\\mathbb\{N\}\_\{\+\}:=\\\{1,2,\\ldots\\\}\. We consider the following elementarykk\-ary connectives fork∈ℕ\+k\\in\\mathbb\{N\}\_\{\+\}, as illustrated in Figure[1](https://arxiv.org/html/2609.13439#S2.F1)\. For a given input vectora=\(a1,…,ak\)∈\{0,1\}ka=\(a\_\{1\},\\ldots,a\_\{k\}\)\\in\\\{0,1\\\}^\{k\}, we define:

Figure 1:The Boolean connectives on three predicates \(AA,BB, andCC\) which we consider\.We observe a training setDtrain=\{\(Xi,f⁡\(Xi\)\)\}i=1TD\_\{\\mathrm\{train\}\}=\\\{\(X\_\{i\},f\(X\_\{i\}\)\)\\\}\_\{i=1\}^\{T\}\. Throughout the main body, the inputsX1,…,XTX\_\{1\},\\ldots,X\_\{T\}are sampled independently and uniformly from\{0,1\}B\\\{0,1\\\}^\{B\}\. A full truth table corresponds instead to observing every one of the2B2^\{B\}Boolean inputs\. However, our analysis is not restricted to the uniform setting: extensions to a general input distributionμ\\muare provided in the appendix\.

GivenDtrainD\_\{\\mathrm\{train\}\}, the objective is to construct a predictorH:\{0,1\}B→\{0,1\}H:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}with small truth\-table errorℛ\(H\)=def\.PrX∼Unif⁡\(\{0,1\}B\)\[H\(X\)≠f\(X\)\]\\mathcal\{R\}\(H\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\Pr\_\{X\\sim\\operatorname\{Unif\}\(\\\{0,1\\\}^\{B\}\)\}\[H\(X\)\\neq f\(X\)\]\.

### 2\.2Boolean Representations and Structural Preliminaries

ForB∈ℕ\+B\\in\\mathbb\{N\}\_\{\+\}, let\[B\]=def\.\{1,…,B\}\[B\]\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{1,\\ldots,B\\\}\. ForJ=\{j1<⋯<j\|J\|\}⊆\[B\]J=\\\{j\_\{1\}<\\cdots<j\_\{\|J\|\}\\\}\\subseteq\[B\]andx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}, defineprojJ⁡\(x\)=def\.\(xj1,…,xj\|J\|\)\\operatorname\{proj\}\_\{J\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\(x\_\{j\_\{1\}\},\\ldots,x\_\{j\_\{\|J\|\}\}\)as the projection ofxxonto the coordinates indexed byJJ\. We denote byx⊕ix^\{\\oplus i\}the vector obtained fromxxby flipping itsii\-th coordinate\. Following[Mossel et al\. \(2003\)](https://arxiv.org/html/2609.13439#bib.bib13), we use the standard notion of relevant coordinates and Boolean juntas\.

###### Definition 1\(Juntas and relevant coordinates\)\.

A Boolean functionf:\{0,1\}B→\{0,1\}f:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}depends on coordinatei∈\[B\]i\\in\[B\]if there existsx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}such thatf⁡\(x\)≠f⁡\(x⊕i\)f\(x\)\\neq f\(x^\{\\oplus i\}\)\. Such a coordinate is called*relevant*toff\. We denote the set of relevant coordinates by

Rel⁡\(f\)=def\.\{i∈\[B\]:∃x∈\{0,1\}B​such that​f​\(x\)≠f⁡\(x⊕i\)\}\.\\operatorname\{Rel\}\(f\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\bigl\\\{i\\in\[B\]:\\exists x\\in\\\{0,1\\\}^\{B\}\\text\{ such that \}f\(x\)\\neq f\(x^\{\\oplus i\}\)\\bigr\\\}\.The functionffis anSS\-junta if\|Rel⁡\(f\)\|≤S\|\\operatorname\{Rel\}\(f\)\|\\leq S\. Equivalently,ffis anSS\-junta if there existJ⊆\[B\]J\\subseteq\[B\]with\|J\|≤S\|J\|\\leq Sand a Boolean functiong:\{0,1\}\|J\|→\{0,1\}g:\\\{0,1\\\}^\{\|J\|\}\\to\\\{0,1\\\}such thatf⁡\(x\)=g⁡\(projJ⁡\(x\)\)f\(x\)=g\(\\operatorname\{proj\}\_\{J\}\(x\)\)for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}\. The smallest suchSSis the effective dimension offf\.

###### Example 2\(Dictator functions\)\.

A Boolean functionf:\{0,1\}B→\{0,1\}f:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}is a dictator function if there existsi∈\[B\]i\\in\[B\]such that eitherf⁡\(x\)=xif\(x\)=x\_\{i\}for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}, orf⁡\(x\)=1−xif\(x\)=1\-x\_\{i\}for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}\. Every dictator function is a11\-junta\.

###### Definition 3\(Literals, cubes, and minterms\)\.

A literal is either a variablexix\_\{i\}or its complement¬xi\\neg x\_\{i\}\. A cube, or product term, is a conjunction of literals and therefore represents a subcube of\{0,1\}B\\\{0,1\\\}^\{B\}\. A minterm is a cube containing one literal for every input coordinate and hence corresponds to a single point of the Boolean cube\.

###### Definition 4\(Sum\-of\-products representations\)\.

A sum\-of\-products \(SOP\) representation is a Boolean formula of the formG⁡\(x\)=⋁q=1Q⋀ℓ=1Lqzq,ℓ​\(x\),G\(x\)=\\bigvee\_\{q=1\}^\{Q\}\\bigwedge\_\{\\ell=1\}^\{L\_\{q\}\}z\_\{q,\\ell\}\(x\),where eachzq,ℓz\_\{q,\\ell\}is a literal\. Its size is measured by the numberQQof product terms and the total number∑q=1QLq\\sum\_\{q=1\}^\{Q\}L\_\{q\}of literal occurrences\.

For a completely specified Boolean functionff, define its ON\- and OFF\-sets byFON=def\.\{x:f⁡\(x\)=1\}F^\{\\mathrm\{ON\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{x:f\(x\)=1\\\}andFOFF=def\.\{x:f⁡\(x\)=0\}F^\{\\mathrm\{OFF\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{x:f\(x\)=0\\\}\. For a partial truth table, the unspecified inputs form thedon’t\-caresetFDCF^\{\\mathrm\{DC\}\}; therefore, these three sets partition\{0,1\}B\\\{0,1\\\}^\{B\}\. A Boolean completion is anyg:\{0,1\}B→\{0,1\}g:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}agreeing with the specified labels onFON∪FOFFF^\{\\mathrm\{ON\}\}\\cup F^\{\\mathrm\{OFF\}\}, with arbitrary values onFDCF^\{\\mathrm\{DC\}\}\.

A second structural notion central to our method is coordinateinfluence, which measures the sensitivity of a Boolean function to perturbations of individual input bits\. We use the standard Boolean\-cube notion\([O’Donnell, 2014](https://arxiv.org/html/2609.13439#bib.bib22)\)and its distribution\-dependent analogue\([Keller et al\., 2012](https://arxiv.org/html/2609.13439#bib.bib17)\)\.

###### Definition 5\(Coordinate influence\)\.

Letf:\{0,1\}B→\{0,1\}f:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}\. For a probability measureμ∈𝒫⁡\(\{0,1\}B\)\\mu\\in\\mathcal\{P\}\(\\\{0,1\\\}^\{B\}\), theμ\\mu\-influence of coordinatei∈\[B\]i\\in\[B\]is defined as

Infiμ\(f\)=def\.PrX∼μ\[f\(X\)≠f\(X⊕i\)\]\.\\operatorname\{Inf\}^\{\\mu\}\_\{i\}\(f\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\Pr\_\{X\\sim\\mu\}\\bigl\[f\(X\)\\neq f\(X^\{\\oplus i\}\)\\bigr\]\.Whenμ\\muis uniform on\{0,1\}B\\\{0,1\\\}^\{B\}, we simply writeInfi⁡\(f\)\\operatorname\{Inf\}\_\{i\}\(f\)and call it the uniform influence\.

Under the uniform measure, a coordinate is irrelevant toffif and only if its influence is zero\. We use uniform influence throughout the main body and treat the generalμ\\mu\-influenceInfiμ\\operatorname\{Inf\}^\{\\mu\}\_\{i\}in Appendix[F\.2](https://arxiv.org/html/2609.13439#A6.SS2)\.

### 2\.3Espresso Logic Minimization

Two\-level logic minimization seeks compact Boolean representations using two layers of logical operations; in sum\-of\-products \(SOP\) form, conjunctions of literals are combined by a final disjunction\. Classical exact methods include Karnaugh maps\([Karnaugh, 1953](https://arxiv.org/html/2609.13439#bib.bib21)\)and the Quine–McCluskey procedure\([McCluskey, 1956](https://arxiv.org/html/2609.13439#bib.bib16)\), but their poor scaling motivates heuristic alternatives\. We useEspresso\([Brayton et al\., 1984](https://arxiv.org/html/2609.13439#bib.bib1);[Sapra et al\., 2003](https://arxiv.org/html/2609.13439#bib.bib82)\), a standard heuristic for two\-level logic minimization\([Kanakia et al\., 2021](https://arxiv.org/html/2609.13439#bib.bib83);[Faroß and Schwarz, 2025](https://arxiv.org/html/2609.13439#bib.bib5)\), which typically produces compact SOP representations without guaranteeing global minimality\.

Given disjoint ON\-, OFF\-, and don’t\-care setsFONF^\{\\mathrm\{ON\}\},FOFFF^\{\\mathrm\{OFF\}\}, andFDCF^\{\\mathrm\{DC\}\},Espressoreturns an SOP completion consistent with the specified ON\- and OFF\-set entries while exploiting don’t\-care entries to simplify the representation\([Brayton et al\., 1984](https://arxiv.org/html/2609.13439#bib.bib1);[Rudell and Sangiovanni\-Vincentelli, 2004](https://arxiv.org/html/2609.13439#bib.bib20)\)\. Accordingly, for a partial truth tableg^:\{0,1\}q→\{0,1,DC\}\\widehat\{g\}:\\\{0,1\\\}^\{q\}\\to\\\{0,1,\\mathrm\{DC\}\\\}, we writeG=EspressoLearn​\(g^\)G=\\textsc\{EspressoLearn\}\(\\widehat\{g\}\)for the Boolean function represented by the returned SOP and require only thatG​\(u\)=g^​\(u\)G\(u\)=\\widehat\{g\}\(u\)wheneverg^​\(u\)∈\{0,1\}\\widehat\{g\}\(u\)\\in\\\{0,1\\\}\. Additional details onEspressoare deferred to Appendix[C](https://arxiv.org/html/2609.13439#A3)\.

## 3Combinatorial Training from Partial Truth Tables

A direct application ofEspressoto aBB\-dimensional partial truth table is governed by the ambient truth\-table size2B2^\{B\}and quickly becomes computationally prohibitive\. Our objective is therefore to retain the compact, explicit logical representations produced byEspressowhile avoiding high\-dimensional logic minimization\.

To this end, we iteratively identify a small set of influential coordinates of the current Boolean residual, applyEspressoonly to the corresponding low\-dimensional projected truth table, and repeat on the remaining error\. Since the selected coordinates may vary across stages, the resulting predictor can capture Boolean functions depending on many ambient coordinates while eachEspressocall remains low\-dimensional\. The stage\-wise predictors are combined byXOR\\operatorname\{XOR\}, ensuring the final model remains an explicit\{AND,OR,XOR\}\\\{\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}\-circuit\. The remainder of this section develops the influence\-based dimension reduction, projected residual\-learning step, and resulting training algorithm\.

### 3\.1Influence\-Based Dimension Reduction

If the targetffdepended on a known coordinate setJ⊆\[B\]J\\subseteq\[B\], one could learnG:\{0,1\}\|J\|→\{0,1\}G:\\\{0,1\\\}^\{\|J\|\}\\to\\\{0,1\\\}on the projected cube and lift it viax↦G⁡\(projJ⁡\(x\)\)x\\mapsto G\(\\operatorname\{proj\}\_\{J\}\(x\)\), reducing the truth\-table size from2B2^\{B\}to2\|J\|2^\{\|J\|\}\. Motivated by this observation, we impose a computational budgetK∈\[B\]K\\in\[B\]and restrict every stage to at mostKKcoordinates, ensuring eachEspressocall involves a projected partial truth table of size at most2K2^\{K\}\.

Since the relevant coordinates are unknown and may vary across residual stages, we prioritize them using coordinate influence\. By Definition[5](https://arxiv.org/html/2609.13439#Thmtheorem5),Infi⁡\(rt\)\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)measures the sensitivity of the current residualrtr\_\{t\}to flipping coordinateii, making high\-influence coordinates natural candidates for the stage\-wise projection\.

Population influences are not directly observable from a partial truth table because the Hamming neighborX⊕iX^\{\\oplus i\}of an observed inputXXneed not itself be observed\. We therefore estimate them using observed Hamming\-neighbor pairs\. Since repeated observations of the same input have identical labels, we deduplicate the training inputs and writeDtrainX=def\.\{Xj:j∈\[T\]\}D\_\{\\mathrm\{train\}\}^\{X\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{X\_\{j\}:j\\in\[T\]\\\}\. For eachi∈\[B\]i\\in\[B\], define

𝒫i=def\.\{x∈DtrainX:xi=0,x⊕i∈DtrainX\},\\mathcal\{P\}\_\{i\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{x\\in D\_\{\\mathrm\{train\}\}^\{X\}:x\_\{i\}=0,\\ x^\{\\oplus i\}\\in D\_\{\\mathrm\{train\}\}^\{X\}\\\},wherexi=0x\_\{i\}=0ensures that each undirected Boolean\-cube edge is counted once\. For any Boolean functionrrknown on the training inputs, set

Inf^i\(r\)=def\.\|𝒫i\|−1∑x∈𝒫i\{r\(x\)≠r\(x⊕i\)\}\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\|\\mathcal\{P\}\_\{i\}\|^\{\-1\}\\sum\_\{x\\in\\mathcal\{P\}\_\{i\}\}\\mathbbm\{1\}\\\!\\left\\\{r\(x\)\\neq r\(x^\{\\oplus i\}\)\\right\\\}when𝒫i≠∅\\mathcal\{P\}\_\{i\}\\neq\\varnothing, andInf^i​\(r\)=def\.0\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}0otherwise\. The latter is only an algorithmic convention and does not imply zero population influence; Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)gives conditions under which these empirical influences recover the relevant population ranking\.

Given a thresholdτ≥0\\tau\\geq 0, we define the active setCt=def\.\{i∈\[B\]:Inf^i​\(rt\)\>τ\}C\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{i\\in\[B\]:\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\>\\tau\\\}and selectJt⊆CtJ\_\{t\}\\subseteq C\_\{t\}to contain themin⁡\{K,\|Ct\|\}\\min\\\{K,\|C\_\{t\}\|\\\}coordinates with largest empirical influence\. Thus,τ\\tauscreens weak coordinates whileKKcontrols the dimension of each projectedEspressoproblem\. IfCt=∅C\_\{t\}=\\varnothing, the procedure terminates\.

### 3\.2Projected Residual Learning

A singleKK\-dimensional projection need not capture the entire target, since different components offfmay depend on different coordinate subsets\. We therefore repeatedly apply the dimension\-reduction procedure to the errors of the current predictor\. LetH0≡0H\_\{0\}\\equiv 0and, fort≥1t\\geq 1, define the Boolean residualrt=def\.f⊕Ht−1r\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}f\\oplus H\_\{t\-1\}\. Thus,rt​\(x\)=1r\_\{t\}\(x\)=1exactly whenHt−1​\(x\)≠f​\(x\)H\_\{t\-1\}\(x\)\\neq f\(x\), and its training labels are available directly asrt​\(Xj\)=f⁡\(Xj\)⊕Ht−1​\(Xj\)r\_\{t\}\(X\_\{j\}\)=f\(X\_\{j\}\)\\oplus H\_\{t\-1\}\(X\_\{j\}\)\. Applying Section[3\.1](https://arxiv.org/html/2609.13439#S3.SS1)tortr\_\{t\}yields a residual\-adaptive coordinate setJt⊆\[B\]J\_\{t\}\\subseteq\[B\]with\|Jt\|≤K\|J\_\{t\}\|\\leq K\.

Foru∈\{0,1\}\|Jt\|u\\in\\\{0,1\\\}^\{\|J\_\{t\}\|\}anda∈\{0,1\}a\\in\\\{0,1\\\}, define

Nt,a\(u\)=def\.\|\{j∈\[T\]:projJt\(Xj\)=u,rt\(Xj\)=a\}\|\.N\_\{t,a\}\(u\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\|\\left\\\{j\\in\[T\]:\\operatorname\{proj\}\_\{J\_\{t\}\}\(X\_\{j\}\)=u,\\ r\_\{t\}\(X\_\{j\}\)=a\\right\\\}\\right\|\.The projected partial truth tableg^t:\{0,1\}\|Jt\|→\{0,1,DC\}\\widehat\{g\}\_\{t\}:\\\{0,1\\\}^\{\|J\_\{t\}\|\}\\to\\\{0,1,\\mathrm\{DC\}\\\}is then

g^t​\(u\)=MajDC⁡\(Nt,0​\(u\),Nt,1​\(u\)\)=def\.\{arg​maxa∈\{0,1\}⁡Nt,a​\(u\),Nt,0​\(u\)≠Nt,1​\(u\),DC,Nt,0​\(u\)=Nt,1​\(u\)\.\\widehat\{g\}\_\{t\}\(u\)=\\operatorname\{Maj\}\_\{\\mathrm\{DC\}\}\\\!\\left\(N\_\{t,0\}\(u\),N\_\{t,1\}\(u\)\\right\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\begin\{cases\}\\displaystyle\\argmax\_\{a\\in\\\{0,1\\\}\}N\_\{t,a\}\(u\),&N\_\{t,0\}\(u\)\\neq N\_\{t,1\}\(u\),\\\\ \\mathrm\{DC\},&N\_\{t,0\}\(u\)=N\_\{t,1\}\(u\)\.\\end\{cases\}\(1\)Thus, observations sharing the same projection are empirically marginalized over the coordinates outsideJtJ\_\{t\}: cells with a strict majority receive the corresponding residual label, while tied or unobserved cells are treated as don’t\-cares\. Moreover, every Boolean completion consistent with the specified entries ofg^t\\widehat\{g\}\_\{t\}is an empirical risk minimizer among Boolean functions depending only onJtJ\_\{t\}, since the empirical00–11loss decomposes independently across projected cells\.

We obtainGt=def\.EspressoLearn​\(g^t\)G\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\textsc\{EspressoLearn\}\(\\widehat\{g\}\_\{t\}\)and lift it to the ambient cube byFt​\(x\)=def\.Gt​\(projJt⁡\(x\)\)F\_\{t\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}G\_\{t\}\(\\operatorname\{proj\}\_\{J\_\{t\}\}\(x\)\)\. Hence, each stage predictor depends on at mostKKcoordinates, even whenrtr\_\{t\}has a larger effective dimension\. We then updateHt=def\.Ht−1⊕FtH\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}H\_\{t\-1\}\\oplus F\_\{t\}, yieldingHs=⨁t=1sFtH\_\{s\}=\\bigoplus\_\{t=1\}^\{s\}F\_\{t\}afterssstages\.

The XOR update is exactly aligned with the Boolean residual: for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\},Ht​\(x\)≠f​\(x\)H\_\{t\}\(x\)\\neq f\(x\)if and only ifFt​\(x\)≠rt​\(x\)F\_\{t\}\(x\)\\neq r\_\{t\}\(x\)444Indeed, sincert=f⊕Ht−1r\_\{t\}=f\\oplus H\_\{t\-1\}, equivalentlyf=Ht−1⊕rtf=H\_\{t\-1\}\\oplus r\_\{t\}, cancellation under XOR givesHt−1​\(x\)⊕Ft​\(x\)≠Ht−1​\(x\)⊕rt​\(x\)H\_\{t\-1\}\(x\)\\oplus F\_\{t\}\(x\)\\neq H\_\{t\-1\}\(x\)\\oplus r\_\{t\}\(x\)if and only ifFt​\(x\)≠rt​\(x\)F\_\{t\}\(x\)\\neq r\_\{t\}\(x\)\.\. Consequently, forX∼Unif⁡\(\{0,1\}B\)X\\sim\\operatorname\{Unif\}\(\\\{0,1\\\}^\{B\}\),

Pr\[Ht\(X\)≠f\(X\)\]=Pr\[Ft\(X\)≠rt\(X\)\]\.\\Pr\\bigl\[H\_\{t\}\(X\)\\neq f\(X\)\\bigr\]=\\Pr\\bigl\[F\_\{t\}\(X\)\\neq r\_\{t\}\(X\)\\bigr\]\.\(2\)Each stage reduces the original learning problem to approximating the current Boolean residual by a low\-dimensional logical correction, with the influential coordinates reselected at every stage\.

### 3\.3Sample\-Based Multi\-Stage Espresso Training

We now combine influence\-based coordinate selection and projected residual learning into the complete training procedure\. Given the observed partial truth table, Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)iteratively fits low\-dimensionalEspressocorrections until either the maximum number of stages is reached or no further correction is identified from the training data\. Since the Hamming\-neighbor sets𝒫i\\mathcal\{P\}\_\{i\}depend only on the observed inputs, they are computed once before the residual iterations\.

##### HowMacchiato \- Inferenceworks\.

Macchiato\(Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\) iteratively identifies a small set of coordinates with the largest empirical influence on the current Boolean residual, constructs the corresponding low\-dimensional projected partial truth table by marginalizing over the remaining coordinates, and appliesEspressoto learn a logical correction\. The resulting correction is lifted to the ambient cube and combined with the accumulated predictor byXOR\\operatorname\{XOR\}, after which the procedure is repeated on the remaining residual\.

Algorithm 1Macchiato – Inference: Scalable Iterative Circuit InferenceInput:

Dtrain=\{\(Xj,f⁡\(Xj\)\)\}j=1TD\_\{\\mathrm\{train\}\}=\\\{\(X\_\{j\},f\(X\_\{j\}\)\)\\\}\_\{j=1\}^\{T\},

m∈ℕ\+m\\in\\mathbb\{N\}\_\{\+\},

K∈\[B\]K\\in\[B\],

τ≥0\\tau\\geq 0
Output:

TstopT\_\{\\mathrm\{stop\}\},

\(Jt,Gt,Ft\)t=1Tstop\(J\_\{t\},G\_\{t\},F\_\{t\}\)\_\{t=1\}^\{T\_\{\\mathrm\{stop\}\}\}, and

HTstopH\_\{T\_\{\\mathrm\{stop\}\}\}
1

DtrainX←\{Xj:j∈\[T\]\}D\_\{\\mathrm\{train\}\}^\{X\}\\leftarrow\\\{X\_\{j\}:j\\in\[T\]\\\},

H0←0H\_\{0\}\\leftarrow 0,

Tstop←0T\_\{\\mathrm\{stop\}\}\\leftarrow 0;

2

𝒫i←\{x∈DtrainX:xi=0,x⊕i∈DtrainX\}\\mathcal\{P\}\_\{i\}\\leftarrow\\\{x\\in D\_\{\\mathrm\{train\}\}^\{X\}:x\_\{i\}=0,\\,x^\{\\oplus i\}\\in D\_\{\\mathrm\{train\}\}^\{X\}\\\},

∀i∈\[B\]\\forall i\\in\[B\];

3for*t=1,…,mt=1,\\ldots,m*do

4

rt​\(Xj\)←f⁡\(Xj\)⊕Ht−1​\(Xj\)r\_\{t\}\(X\_\{j\}\)\\leftarrow f\(X\_\{j\}\)\\oplus H\_\{t\-1\}\(X\_\{j\}\),

∀j∈\[T\]\\forall j\\in\[T\];

5if*rt​\(Xj\)=0r\_\{t\}\(X\_\{j\}\)=0,∀j∈\[T\]\\forall j\\in\[T\]*thenbreak;

6

Inf^i\(rt\)←\|𝒫i\|−1∑x∈𝒫i𝟙\{rt\(x\)≠rt\(x⊕i\)\}\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\\leftarrow\|\\mathcal\{P\}\_\{i\}\|^\{\-1\}\\sum\_\{x\\in\\mathcal\{P\}\_\{i\}\}\\mathbbm\{1\}\\\{r\_\{t\}\(x\)\\neq r\_\{t\}\(x^\{\\oplus i\}\)\\\}if

𝒫i≠∅\\mathcal\{P\}\_\{i\}\\neq\\varnothing, and

00otherwise,

∀i∈\[B\]\\forall i\\in\[B\];

7

Ct←\{i∈\[B\]:Inf^i​\(rt\)\>τ\}C\_\{t\}\\leftarrow\\\{i\\in\[B\]:\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\>\\tau\\\};

8if*Ct=∅C\_\{t\}=\\varnothing*thenbreak;

9

Jt←J\_\{t\}\\leftarrowthe

min⁡\{K,\|Ct\|\}\\min\\\{K,\|C\_\{t\}\|\\\}highest\-influence coordinates in

CtC\_\{t\}555Ties are broken deterministically by increasing coordinate index, makingJtJ\_\{t\}a measurable function of the training data\.;

10

g^t​\(u\)←MajDC⁡\(Nt,0​\(u\),Nt,1​\(u\)\)\\widehat\{g\}\_\{t\}\(u\)\\leftarrow\\operatorname\{Maj\}\_\{\\mathrm\{DC\}\}\\\!\\left\(N\_\{t,0\}\(u\),N\_\{t,1\}\(u\)\\right\),

∀u∈\{0,1\}\|Jt\|\\forall u\\in\\\{0,1\\\}^\{\|J\_\{t\}\|\};//Eq\. \([1](https://arxiv.org/html/2609.13439#S3.E1)\)

11

Gt←EspressoLearn​\(g^t\)G\_\{t\}\\leftarrow\\textsc\{EspressoLearn\}\(\\widehat\{g\}\_\{t\}\),

Ft​\(x\)←Gt​\(projJt⁡\(x\)\)F\_\{t\}\(x\)\\leftarrow G\_\{t\}\(\\operatorname\{proj\}\_\{J\_\{t\}\}\(x\)\);

12

Ht←Ht−1⊕FtH\_\{t\}\\leftarrow H\_\{t\-1\}\\oplus F\_\{t\},

Tstop←tT\_\{\\mathrm\{stop\}\}\\leftarrow t;

13return*Tstop,\(Jt,Gt,Ft\)t=1Tstop,HTstopT\_\{\\mathrm\{stop\}\},\(J\_\{t\},G\_\{t\},F\_\{t\}\)\_\{t=1\}^\{T\_\{\\mathrm\{stop\}\}\},H\_\{T\_\{\\mathrm\{stop\}\}\}*;

The algorithm has two data\-dependent stopping conditions\. Ifrtr\_\{t\}vanishes on all observed inputs, thenHt−1H\_\{t\-1\}interpolates the observed partial truth table\. IfCt=∅C\_\{t\}=\\varnothing, no empirical influence exceedsτ\\tau, leaving no eligible coordinate for the next projected stage\. The latter may indicate either weak residual structure or insufficient observed Hamming\-neighbor pairs; settingτ=0\\tau=0yields the least restrictive version of this criterion\.

The output preserves the logical structure learned at every stage: eachFtF\_\{t\}is a liftedEspressoSOP depending on at mostKKcoordinates, andHTstop=⨁t=1TstopFtH\_\{T\_\{\\mathrm\{stop\}\}\}=\\bigoplus\_\{t=1\}^\{T\_\{\\mathrm\{stop\}\}\}F\_\{t\}\. Thus, both the selected coordinatesJtJ\_\{t\}and their corresponding logical corrections remain explicitly inspectable\. Moreover, Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)uses onlyDtrainD\_\{\\mathrm\{train\}\}; test data are introduced solely for evaluation in Section[5](https://arxiv.org/html/2609.13439#S5)\.

## 4Main Results

This section presents our main theoretical results: statistical guarantees for the learned Boolean predictor and an exact certifiably interpretableReLU\\operatorname\{ReLU\}\-MLP realization of the resulting circuit\.

### 4\.1Statistical Guarantees

This section establishes conditions under which the sample\-based procedure in Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)generalizes beyond the observed partial truth table\. The analysis separates two statistical requirements\. First, the empirical influence estimates must reliably identify the coordinates governing the current residual\. Second, once these coordinates have been selected, the projected Boolean rule learned byEspressomust generalize to unseen inputs\.

We state the main results under the uniform distributionν=def\.Unif⁡\(\{0,1\}B\)\\nu\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\operatorname\{Unif\}\(\\\{0,1\\\}^\{B\}\), which corresponds to the truth\-table risk defined in Section[2](https://arxiv.org/html/2609.13439#S2)\. The same analysis extends beyond the uniform setting; analogous influence\-recovery and prediction guarantees for a general input distributionμ\\muare provided in Appendix[F\.2](https://arxiv.org/html/2609.13439#A6.SS2)\. Throughout, all logarithms are natural, andC\>0C\>0denotes a universal constant whose value may vary from line to line\.

#### 4\.1\.1Influence Recovery for Low\-Dimensional Boolean Functions

The influence estimator in Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)is constructed from Hamming\-neighbor pairs occurring in the observed partial truth table\. To obtain a transparent statistical benchmark, we first analyze an idealized paired\-sampling model in which such perturbations are observed directly\. Independently drawXn∼νX\_\{n\}\\sim\\nuandIn∼Unif⁡\(\[B\]\)I\_\{n\}\\sim\\operatorname\{Unif\}\(\[B\]\)forn=1,…,Nn=1,\\ldots,N, and observe\(Xn,Xn⊕In\)\(X\_\{n\},X\_\{n\}^\{\\oplus I\_\{n\}\}\)\. For eachi∈\[B\]i\\in\[B\], letMi=def\.∑n=1N𝟙\{In=i\}M\_\{i\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{n=1\}^\{N\}\\mathbbm\{1\}\\\{I\_\{n\}=i\\\}\. WheneverMi\>0M\_\{i\}\>0, define

Inf^ipair\(h\)=def\.1Mi∑n:In=i𝟙\{h\(Xn\)≠h\(Xn⊕i\)\}\.\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\frac\{1\}\{M\_\{i\}\}\\sum\_\{n:I\_\{n\}=i\}\\mathbbm\{1\}\\left\\\{h\(X\_\{n\}\)\\neq h\(X\_\{n\}^\{\\oplus i\}\)\\right\\\}\.\(3\)IfMi=0M\_\{i\}=0, we setInf^ipair​\(h\)=def\.0\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}0, consistent with the empirical convention\. Conditional on\(In\)n=1N\(I\_\{n\}\)\_\{n=1\}^\{N\}, the summands indexed bynnwithIn=iI\_\{n\}=iare independent Bernoulli random variables with meanInfi⁡\(h\)\\operatorname\{Inf\}\_\{i\}\(h\), making this model particularly convenient for analyzing influence recovery\.

The paired model is an analytical device rather than an assumption on the training data used by Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\. There, the flipped inputXj⊕iX\_\{j\}^\{\\oplus i\}need not be observed for a given training pointXjX\_\{j\}, and an observed point may participate in several Hamming\-neighbor pairs across different coordinates\. Consequently, the usable pairs in a passive partial truth table need neither occur in the balanced form of the paired model nor share its independence structure\. Such idealized probabilistic regimes are standard analytical devices in statistical theory, including i\.i\.d\.[van der Vaart and Wellner \(2023\)](https://arxiv.org/html/2609.13439#bib.bib85), martingale\-difference[Hall and Heyde \(1980\)](https://arxiv.org/html/2609.13439#bib.bib86), and Markov models[Meyn and Tweedie \(2009\)](https://arxiv.org/html/2609.13439#bib.bib87);[Limmer et al\. \(2024\)](https://arxiv.org/html/2609.13439#bib.bib88)\. Here, the paired model isolates the sample information required to estimate coordinate\-wise Boolean sensitivity once suitable bit\-flip observations are available\. Section[5](https://arxiv.org/html/2609.13439#S5)demonstrates empirically that Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)remains effective with ordinary training samples when this idealized paired\-sampling structure is absent\.

For1≤S≤B1\\leq S\\leq B, recall the class ofSS\-juntas𝒥B,S=def\.\{h:\{0,1\}B→\{0,1\}:\|Rel\(h\)\|≤S\}\\mathcal\{J\}\_\{B,S\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{h:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}:\|\\operatorname\{Rel\}\(h\)\|\\leq S\\\}\. The following theorem gives the influence\-recovery guarantee needed in the low\-effective\-dimension regime motivating our algorithm\. The junta assumption is used only to obtain an explicit sample\-complexity bound through the cardinality of𝒥B,S\\mathcal\{J\}\_\{B,S\}\. The underlying argument applies more generally to any finite Boolean function class; the corresponding result is stated as Theorem[14](https://arxiv.org/html/2609.13439#Thmtheorem14)in Appendix[A\.1](https://arxiv.org/html/2609.13439#A1.SS1)\.

###### Theorem 6\(Influence recovery for juntas\)\.

Let1≤S≤B1\\leq S\\leq Bandε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\)\. There exists a universal constantC\>0C\>0such that, ifN≥C​Bε2​\(2S\+S​log⁡e​BS\+log⁡2​Bδ\)N\\geq C\\frac\{B\}\{\\varepsilon^\{2\}\}\\bigl\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\+\\log\\frac\{2B\}\{\\delta\}\\bigr\), then, with probability at least1−δ1\-\\delta,

max⁡suph∈𝒥B,Si∈\[B\]⁡\|Inf^ipair​\(h\)−Infi⁡\(h\)\|≤ε\.\\max\_\{i\\in\[B\]\}\\sup\_\{h\\in\\mathcal\{J\}\_\{B,S\}\}\\left\|\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\-\\operatorname\{Inf\}\_\{i\}\(h\)\\right\|\\leq\\varepsilon\.In particular, ifS=𝒪⁡\(log⁡B\)S=\\mathcal\{O\}\(\\log B\), the required number of paired samples is polynomial inBBand1/ε1/\\varepsilon, and logarithmic in1/δ1/\\delta\.

###### Proof\.

See Section[A\.1](https://arxiv.org/html/2609.13439#A1.SS1)\. ∎

Theorem[6](https://arxiv.org/html/2609.13439#Thmtheorem6)guarantees that, with sufficiently many paired samples, all coordinate influences are estimated to any prescribed accuracy uniformly over the class ofSS\-juntas, with high probability\. Crucially, the exponential dependence in the sample complexity is on the effective dimensionSS, rather than the ambient dimensionBB\. The proof combines uniform concentration over a finite Boolean function class via Hoeffding’s inequality and a union bound, an occupancy argument ensuring sufficiently many samples per coordinate, and a cardinality bound for𝒥B,S\\mathcal\{J\}\_\{B,S\}\. The complete proof is given in Appendix[A\.1](https://arxiv.org/html/2609.13439#A1.SS1)\.

#### 4\.1\.2Coordinate Recovery and Truth\-Table Accuracy

We now connect influence estimation to the prediction error of the multi\-stage procedure\. We restrict attention to the nondegenerate caseTstop≥1T\_\{\\mathrm\{stop\}\}\\geq 1, so that at least one stage is completed\. LetTstop≤mT\_\{\\mathrm\{stop\}\}\\leq mdenote the number of completed stages and, for eacht∈\[Tstop\]t\\in\[T\_\{\\mathrm\{stop\}\}\], recall thatrt=f⊕Ht−1r\_\{t\}=f\\oplus H\_\{t\-1\}\. The analysis uses two properties of the empirical influence estimator: the simultaneous stage\-wise accuracy of Assumption[7](https://arxiv.org/html/2609.13439#Thmtheorem7)and preservation of zero population influence\. For the pair\-based estimators considered here, the latter holds exactly under the uniform distribution:Infi⁡\(h\)=0\\operatorname\{Inf\}\_\{i\}\(h\)=0impliesInf^i​\(h\)=0\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(h\)=0; see Lemma[16](https://arxiv.org/html/2609.13439#Thmtheorem16)\. The argument therefore applies more generally to any influence estimator satisfying these two properties\.

###### Assumption 7\(Simultaneous stage\-wise influence accuracy\)\.

For someεinf,δinf∈\(0,1\)\\varepsilon\_\{\\mathrm\{inf\}\},\\delta\_\{\\mathrm\{inf\}\}\\in\(0,1\), with probability at least1−δinf1\-\\delta\_\{\\mathrm\{inf\}\},

maxt∈\[Tstop\]⁡maxi∈\[B\]​\|Inf^i​\(rt\)−Infi⁡\(rt\)\|≤εinf\.\\max\_\{t\\in\[T\_\{\\mathrm\{stop\}\}\]\}\\max\_\{i\\in\[B\]\}\\left\|\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\-\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)\\right\|\\leq\\varepsilon\_\{\\mathrm\{inf\}\}\.\(4\)

For each completed stage, letCt⋆=def\.\{i∈\[B\]:Infi⁡\(rt\)\>τ\}C\_\{t\}^\{\\star\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{i\\in\[B\]:\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)\>\\tau\\\}denote the population active set, definest⋆=def\.min⁡\{K,\|Ct⋆\|\}s\_\{t\}^\{\\star\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\min\\\{K,\|C\_\{t\}^\{\\star\}\|\\\}, and letJt⋆⊆Ct⋆J\_\{t\}^\{\\star\}\\subseteq C\_\{t\}^\{\\star\}contain thest⋆s\_\{t\}^\{\\star\}coordinates with largest population influence, using the same deterministic tie\-breaking rule as the algorithm\.

To ensure that estimation error does not alter the thresholding or top\-KKranking decisions, we impose a margin around the relevant positive population\-influence thresholds\. Zero\-influence coordinates are treated separately, since the pair\-based estimator preserves zero influence exactly\.

###### Assumption 8\(Thresholded top\-KKinfluence separation\)\.

For every completed stagett,Ct⋆≠∅C\_\{t\}^\{\\star\}\\neq\\varnothing, and

mini∈Jt⋆⁡Infi⁡\(rt\)\>τ\+εinf\.\\min\_\{i\\in J\_\{t\}^\{\\star\}\}\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)\>\\tau\+\\varepsilon\_\{\\mathrm\{inf\}\}\.Moreover, if\|Ct⋆\|≤K\|C\_\{t\}^\{\\star\}\|\\leq K, then, for everyj∉Ct⋆j\\notin C\_\{t\}^\{\\star\},

Infj⁡\(rt\)=0orInfj⁡\(rt\)<τ−εinf\.\\operatorname\{Inf\}\_\{j\}\(r\_\{t\}\)=0\\qquad\\text\{or\}\\qquad\\operatorname\{Inf\}\_\{j\}\(r\_\{t\}\)<\\tau\-\\varepsilon\_\{\\mathrm\{inf\}\}\.If\|Ct⋆\|\>K\|C\_\{t\}^\{\\star\}\|\>K, then

mini∈Jt⋆⁡Infi⁡\(rt\)−maxj∈Ct⋆∖Jt⋆⁡Infj⁡\(rt\)\>2​εinf\.\\min\_\{i\\in J\_\{t\}^\{\\star\}\}\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)\-\\max\_\{j\\in C\_\{t\}^\{\\star\}\\setminus J\_\{t\}^\{\\star\}\}\\operatorname\{Inf\}\_\{j\}\(r\_\{t\}\)\>2\\varepsilon\_\{\\mathrm\{inf\}\}\.

Thus, every population\-selected coordinate lies sufficiently above the threshold, while positive\-influence coordinates below the threshold are separated from it whenever recovery of the full active set is required\. Zero\-influence coordinates require no margin because, for the pair\-based estimator, zero population influence implies zero empirical influence exactly; see Lemma[16](https://arxiv.org/html/2609.13439#Thmtheorem16)\. In particular, whenτ=0\\tau=0, every coordinate outsideCt⋆C\_\{t\}^\{\\star\}has zero population influence, where the second condition in Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8)holds automatically\.

This margin condition is analogous to theε\\varepsilon\-separation assumption of[Kratsios et al\. \(2025a\)](https://arxiv.org/html/2609.13439#bib.bib18)for symmetric Boolean functions, where separation between influence levels likewise ensures stable identification\. Under Assumptions[7](https://arxiv.org/html/2609.13439#Thmtheorem7)and[8](https://arxiv.org/html/2609.13439#Thmtheorem8), the empirical procedure recoversJt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}simultaneously across all completed stages; the formal recovery lemma and proof are given in Appendix[A\.2\.1](https://arxiv.org/html/2609.13439#A1.SS2.SSS1)\.

To analyze generalization across adaptive residual stages, we use a stage\-wise sample\-splitting version of the algorithm\. LetT0=def\.⌊T/m⌋T\_\{0\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\lfloor T/m\\rfloor, discard at mostm−1m\-1observations if necessary, and partition the remaining sample into independent batches

D\(1\)∪˙⋯∪˙D\(m\),\|D\(t\)\|=T0\.D^\{\(1\)\}\\mathbin\{\\dot\{\\cup\}\}\\cdots\\mathbin\{\\dot\{\\cup\}\}D^\{\(m\)\},\\qquad\|D^\{\(t\)\}\|=T\_\{0\}\.At stagett, onlyD\(t\)D^\{\(t\)\}is used to estimate influences, selectJtJ\_\{t\}, construct the projected partial truth table, and learn the correction\. Conditional on the preceding batches,Ht−1H\_\{t\-1\}and hencert=f⊕Ht−1r\_\{t\}=f\\oplus H\_\{t\-1\}are fixed independently of the fresh batchD\(t\)D^\{\(t\)\}, on which the residual labels are then evaluated\.

As with paired sampling, sample splitting is an analytical device rather than a requirement of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\. The practical algorithm reuses the training observations across stages, introducing dependence between the current residual and the data used to learn its correction\. Sample splitting removes this adaptivity and permits a standard finite\-class generalization argument\. Since Section[5](https://arxiv.org/html/2609.13439#S5)evaluates the un\-split algorithm directly, the empirical results do not rely on this theoretical simplification\.

We now state the main prediction guarantee, which specializes the general recovery\-to\-accuracy result of Appendix[A\.2\.4](https://arxiv.org/html/2609.13439#A1.SS2.SSS4)to the regime in which each stage residual is low\-dimensional\.

###### Theorem 9\(Accuracy under anSS\-junta residual\)\.

Consider the stage\-wise sample\-splitting version of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1), and supposeT≥mT\\geq m\. Assume that Assumptions[7](https://arxiv.org/html/2609.13439#Thmtheorem7)and[8](https://arxiv.org/html/2609.13439#Thmtheorem8)hold\. Fix1≤S≤K1\\leq S\\leq K, and suppose that for every completed stagett, the residualrtr\_\{t\}depends only onJt⋆J\_\{t\}^\{\\star\}, withst⋆=\|Jt⋆\|≤Ss\_\{t\}^\{\\star\}=\|J\_\{t\}^\{\\star\}\|\\leq S\. Then, for everyδgen∈\(0,1\)\\delta\_\{\\mathrm\{gen\}\}\\in\(0,1\), with probability at least1−δinf−δgen1\-\\delta\_\{\\mathrm\{inf\}\}\-\\delta\_\{\\mathrm\{gen\}\}, simultaneously for every completed stagett,

ℛ⁡\(Ht\)≤C​m⁡\(2S\+S​log⁡e​BS\+log⁡mδgen\)T\.\\mathcal\{R\}\(H\_\{t\}\)\\leq C\\sqrt\{\\frac\{m\\left\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}\.\(5\)

###### Proof\.

See Sections[A\.2\.4](https://arxiv.org/html/2609.13439#A1.SS2.SSS4)and[A\.2\.5](https://arxiv.org/html/2609.13439#A1.SS2.SSS5)\. ∎

Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9)captures the regime motivating the algorithm\. Once the relevant stage coordinates are recovered, the learned correction belongs to a class of Boolean functions depending on at mostst⋆≤Ss\_\{t\}^\{\\star\}\\leq Scoordinates\. Its statistical complexity is therefore governed by2S2^\{S\}together with the cost of identifying anSS\-coordinate subset amongBBinputs, rather than by the ambient truth\-table size2B2^\{B\}\.

The effective dimensionSSenters twice\. First, Theorem[6](https://arxiv.org/html/2609.13439#Thmtheorem6)gives an explicit sufficient paired\-sample size for controlling the influence\-recovery failure probabilityδinf\\delta\_\{\\mathrm\{inf\}\}when the residuals belong to𝒥B,S\\mathcal\{J\}\_\{B,S\}\. Second, conditional on successful coordinate recovery, the prediction bound in \([5](https://arxiv.org/html/2609.13439#S4.E5)\) depends explicitly on the sameSS\. Thus,SScontrols both coordinate recovery and generalization of the projected stage learner\.

The proof first establishes recovery ofJt⋆J\_\{t\}^\{\\star\}\. Sincertr\_\{t\}depends only onJt⋆J\_\{t\}^\{\\star\}, the recovered projection incurs no population approximation error\. Uniform convergence over Boolean functions depending on at mostSScoordinates then controls the error of the learnedEspressocorrection, while the identityHt​\(x\)≠f​\(x\)H\_\{t\}\(x\)\\neq f\(x\)if and only ifFt​\(x\)≠rt​\(x\)F\_\{t\}\(x\)\\neq r\_\{t\}\(x\)transfers the stage\-wise residual error directly to the truth\-table error ofHtH\_\{t\}\. The complete proof, together with the corresponding result allowing nonzero projection error, is given in Appendix[A\.2\.5](https://arxiv.org/html/2609.13439#A1.SS2.SSS5)\. In the idealized case where the projected residual truth table is known exactly, one may takeFt=rtF\_\{t\}=r\_\{t\}, and henceHt=Ht−1⊕rt=fH\_\{t\}=H\_\{t\-1\}\\oplus r\_\{t\}=f, yielding exact truth\-table recovery at that stage\.

### 4\.2Certifiably Interpretable Neural Realization

The preceding sections provide the statistical and computational ingredients for learning an explicit Boolean rule from a partial truth table\. We now complete the pipeline by compiling the learned circuit exactly into aReLU\\operatorname\{ReLU\}\-MLP without changing its predictions on the Boolean cube\. Thus, Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)learns a structured Boolean circuit from data, Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)controls its generalization, and the present section gives its exact neural realization\.

Although the Boolean circuit is already a valid predictor, its neural realization can be embedded directly into standard differentiable learning pipelines\. In particular, the compiled network exactly reproduces the learned circuit and may serve as a structured initialization for subsequent gradient\-based fine\-tuning or as a component of a larger differentiable model\. The logical certificate applies to the compiled network before any unconstrained parameter update; arbitrary fine\-tuning need not preserve it\. Thus, the construction yields both a certified interpretable predictor and, when desired, a data\-derived neural initialization\.

LetM=def\.TstopM\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}T\_\{\\mathrm\{stop\}\}\. Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)returns the explicit circuitHM​\(x\)=⨁t=1MFt​\(x\)H\_\{M\}\(x\)=\\bigoplus\_\{t=1\}^\{M\}F\_\{t\}\(x\), where each stage is the lift of anEspressosum\-of\-products expression,

Ft​\(x\)=Gt​\(projJt⁡\(x\)\)=⋁q=1Qt⋀ℓ=1Lt,qzt,q,ℓ​\(x\)\.F\_\{t\}\(x\)=G\_\{t\}\(\\operatorname\{proj\}\_\{J\_\{t\}\}\(x\)\)=\\bigvee\_\{q=1\}^\{Q\_\{t\}\}\\bigwedge\_\{\\ell=1\}^\{L\_\{t,q\}\}z\_\{t,q,\\ell\}\(x\)\.Each literalzt,q,ℓ​\(x\)z\_\{t,q,\\ell\}\(x\)is either a coordinatexjx\_\{j\}or its negation1−xj1\-x\_\{j\}for somej∈Jtj\\in J\_\{t\}; consequently,HMH\_\{M\}is an explicit\{NOT,AND,OR,XOR\}\\\{\\operatorname\{NOT\},\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}\-circuit\. Our goal is to transfer this structure exactly to a feedforward ReLU network, rather than approximate it by a separately trained neural model\.

Throughout, letσ\\sigmadenote the rectified linear unit,σ⁡\(u\)=def\.ReLU⁡\(u\)=max⁡\{u,0\}\\sigma\(u\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\operatorname\{ReLU\}\(u\)=\\max\\\{u,0\\\}, with the same notation used coordinate\-wise for vector inputs\. The following identities provide the gate realizations required by the compilation algorithm\. They are asserted only on Boolean inputs; no logical interpretation of the off\-cube extension is required666Alternative exact gate realizations, limitations of single\-ReLU representations, and depth–width tradeoffs for XOR are collected in Appendix[F\.3](https://arxiv.org/html/2609.13439#A6.SS3); these alternatives do not change the certificate or the Boolean function represented by the compiled model\.\.

###### Proposition 10\(ReLU modules for the Boolean gates\)\.

Letr≥1r\\geq 1,a=\(a1,…,ar\)∈\{0,1\}ra=\(a\_\{1\},\\ldots,a\_\{r\}\)\\in\\\{0,1\\\}^\{r\}, ands⁡\(a\)=def\.∑j=1rajs\(a\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{j=1\}^\{r\}a\_\{j\}\. Then

ψNOT​\(a1\)\\displaystyle\\psi\_\{\\mathrm\{NOT\}\}\(a\_\{1\}\)=def\.σ⁡\(1−a1\)=¬a1,\\displaystyle\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\(1\-a\_\{1\}\)=\\neg a\_\{1\},\(6\)ψAND\(r\)​\(a\)\\displaystyle\\psi\_\{\\mathrm\{AND\}\}^\{\(r\)\}\(a\)=def\.σ⁡\(s⁡\(a\)−r\+1\)−σ⁡\(s⁡\(a\)−r\)=⋀j=1raj,\\displaystyle\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\\bigl\(s\(a\)\-r\+1\\bigr\)\-\\sigma\\bigl\(s\(a\)\-r\\bigr\)=\\bigwedge\_\{j=1\}^\{r\}a\_\{j\},\(7\)ψOR\(r\)​\(a\)\\displaystyle\\psi\_\{\\mathrm\{OR\}\}^\{\(r\)\}\(a\)=def\.σ⁡\(s⁡\(a\)\)−σ⁡\(s⁡\(a\)−1\)=⋁j=1raj,\\displaystyle\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\\bigl\(s\(a\)\\bigr\)\-\\sigma\\bigl\(s\(a\)\-1\\bigr\)=\\bigvee\_\{j=1\}^\{r\}a\_\{j\},\(8\)ψXOR\(r\)​\(a\)\\displaystyle\\psi\_\{\\mathrm\{XOR\}\}^\{\(r\)\}\(a\)=def\.σ⁡\(σ⁡\(s⁡\(a\)\)\+2​∑k=1r−1\(−1\)k​σ​\(s⁡\(a\)−k\)\)=⨁j=1raj\.\\displaystyle\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\\bigg\(\\sigma\\bigl\(s\(a\)\\bigr\)\+2\\sum\_\{k=1\}^\{r\-1\}\(\-1\)^\{k\}\\sigma\\bigl\(s\(a\)\-k\\bigr\)\\bigg\)=\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}\.\(9\)Thus, NOT uses one ReLU unit, AND and OR each use a one\-hidden\-layer width\-two module, andrr\-input XOR uses a two\-layer module with hidden widthrr\.

###### Proof\.

The proof is given in Appendix[B](https://arxiv.org/html/2609.13439#A2)\. ∎

#### 4\.2\.1Circuit\-to\-Network Compilation

We now replace the gates of the learned circuit by the modules in Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)\. For a uniform layerwise realization, we write each stage in SOP form withQt≥1Q\_\{t\}\\geq 1andLt,q≥1L\_\{t,q\}\\geq 1, using the natural conventions⋀ℓ=11zt,q,ℓ=zt,q,1\\bigwedge\_\{\\ell=1\}^\{1\}z\_\{t,q,\\ell\}=z\_\{t,q,1\}and⋁q=11Ct,q=Ct,1\\bigvee\_\{q=1\}^\{1\}C\_\{t,q\}=C\_\{t,1\}\. Thus, single literals and single conjunctions fit the same notation\. Before compilation, duplicate and redundant product terms are removed from each nonconstant stage\-wise SOP without changing the represented Boolean function\. DegenerateEspressooutputs require only a syntactic normalization: for any fixedj∈Jtj\\in J\_\{t\}, the constant\-zero and constant\-one functions may be written asxj∧\(1−xj\)x\_\{j\}\\wedge\(1\-x\_\{j\}\)andxj∨\(1−xj\)x\_\{j\}\\vee\(1\-x\_\{j\}\), respectively, without changingFtF\_\{t\}\.

##### HowMacchiato – Compileworks\.

Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)compiles these normalized stage\-wise SOP representations into a single feedforwardReLU\\operatorname\{ReLU\}\-MLP\. It first forms the positive and negated literal signals, realizes each product term with anAND\\operatorname\{AND\}module, combines the product terms within each stage with anOR\\operatorname\{OR\}module, and finally aggregates the stage outputs byXOR\\operatorname\{XOR\}\. The linear readouts in theAND\\operatorname\{AND\}andOR\\operatorname\{OR\}modules introduce no additional network layers, since their coefficients can be absorbed into the affine transformations of subsequent layers\. ForM≥1M\\geq 1, Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)constructs the resulting neural realization; for the degenerate caseM=0M=0, we setH^0≡0\\widehat\{H\}\_\{0\}\\equiv 0, consistently withH0≡0H\_\{0\}\\equiv 0\.

Algorithm 2Macchiato – Compile:CertifiableReLU\\operatorname\{ReLU\}\-MLP CompilationInput:

MMand

Ft​\(x\)=⋁q=1Qt⋀ℓ=1Lt,qzt,q,ℓ​\(x\)F\_\{t\}\(x\)=\\bigvee\_\{q=1\}^\{Q\_\{t\}\}\\bigwedge\_\{\\ell=1\}^\{L\_\{t,q\}\}z\_\{t,q,\\ell\}\(x\),

∀t∈\[M\]\\forall t\\in\[M\]
Output:A ReLU network

H^M\\widehat\{H\}\_\{M\}such that

H^M​\(x\)=HM​\(x\)\\widehat\{H\}\_\{M\}\(x\)=H\_\{M\}\(x\),

∀x∈\{0,1\}B\\forall x\\in\\\{0,1\\\}^\{B\}
1

pj​\(x\)←σ⁡\(xj\)p\_\{j\}\(x\)\\leftarrow\\sigma\(x\_\{j\}\),

nj​\(x\)←σ⁡\(1−xj\)n\_\{j\}\(x\)\\leftarrow\\sigma\(1\-x\_\{j\}\),

∀j∈\[B\]\\forall j\\in\[B\];

2for*t=1,…,Mt=1,\\ldots,M*do

3for*q=1,…,Qtq=1,\\ldots,Q\_\{t\}*do

4

z^t,q,ℓ​\(x\)←pj​\(x\)\\widehat\{z\}\_\{t,q,\\ell\}\(x\)\\leftarrow p\_\{j\}\(x\)if

zt,q,ℓ​\(x\)=xjz\_\{t,q,\\ell\}\(x\)=x\_\{j\}, and

nj​\(x\)n\_\{j\}\(x\)if

zt,q,ℓ​\(x\)=1−xjz\_\{t,q,\\ell\}\(x\)=1\-x\_\{j\},

∀ℓ∈\[Lt,q\]\\forall\\ell\\in\[L\_\{t,q\}\];

5

st,q​\(x\)←∑ℓ=1Lt,qz^t,q,ℓ​\(x\)s\_\{t,q\}\(x\)\\leftarrow\\sum\_\{\\ell=1\}^\{L\_\{t,q\}\}\\widehat\{z\}\_\{t,q,\\ell\}\(x\);

6

Ct,q​\(x\)←σ⁡\(st,q​\(x\)−Lt,q\+1\)−σ⁡\(st,q​\(x\)−Lt,q\)C\_\{t,q\}\(x\)\\leftarrow\\sigma\\\!\\left\(s\_\{t,q\}\(x\)\-L\_\{t,q\}\+1\\right\)\-\\sigma\\\!\\left\(s\_\{t,q\}\(x\)\-L\_\{t,q\}\\right\);

7

ct​\(x\)←∑q=1QtCt,q​\(x\)c\_\{t\}\(x\)\\leftarrow\\sum\_\{q=1\}^\{Q\_\{t\}\}C\_\{t,q\}\(x\);

8

ot\+​\(x\)←σ⁡\(ct​\(x\)\)o\_\{t\}^\{\+\}\(x\)\\leftarrow\\sigma\(c\_\{t\}\(x\)\),

ot−​\(x\)←σ⁡\(ct​\(x\)−1\)o\_\{t\}^\{\-\}\(x\)\\leftarrow\\sigma\(c\_\{t\}\(x\)\-1\);

9

sM​\(x\)←∑t=1M\(ot\+​\(x\)−ot−​\(x\)\)s\_\{M\}\(x\)\\leftarrow\\sum\_\{t=1\}^\{M\}\\left\(o\_\{t\}^\{\+\}\(x\)\-o\_\{t\}^\{\-\}\(x\)\\right\);

10

hk​\(x\)←σ⁡\(sM​\(x\)−k\)h\_\{k\}\(x\)\\leftarrow\\sigma\(s\_\{M\}\(x\)\-k\),

∀k=0,…,M−1\\forall k=0,\\ldots,M\-1;

11

H^M​\(x\)←σ⁡\(h0​\(x\)\+2​∑k=1M−1\(−1\)k​hk​\(x\)\)\\widehat\{H\}\_\{M\}\(x\)\\leftarrow\\sigma\\\!\\left\(h\_\{0\}\(x\)\+2\\sum\_\{k=1\}^\{M\-1\}\(\-1\)^\{k\}h\_\{k\}\(x\)\\right\);

12return*H^M\\widehat\{H\}\_\{M\}*;

On Boolean inputs, the affine combination in the final line of Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2),h0​\(x\)\+2​∑k=1M−1\(−1\)k​hk​\(x\)h\_\{0\}\(x\)\+2\\sum\_\{k=1\}^\{M\-1\}\(\-1\)^\{k\}h\_\{k\}\(x\), already takes values in\{0,1\}\\\{0,1\\\}and equals the XOR of the stage outputs\. Thus, the final ReLU is unnecessary for exact agreement on the Boolean cube, but we retain it so that the scalar output is itself produced by a ReLU unit, consistently with the preceding layers\. Alternatively, the final layer may be taken to be linear\. Since the affine readout is required in either case, this choice does not change the network depth\.

###### Theorem 11\(Exact neural realization\)\.

LetM≥1M\\geq 1, and letHMH\_\{M\}be the predictor returned by Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1), and letP=def\.∑t=1MQtP\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{t=1\}^\{M\}Q\_\{t\}denote the total number of product terms across the stage\-wise SOP representations\. Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)returns a ReLU MLPH^M\\widehat\{H\}\_\{M\}satisfying:

1. \(i\)Depth:five non\-input layers;
2. \(ii\)Width:layer widths\(2​B,2​P,2​M,M,1\)\(2B,\\,2P,\\,2M,\\,M,\\,1\), where the final scalar layer may equivalently be taken to be linear;
3. \(iii\)Exact realization:H^M​\(x\)=HM​\(x\)\\widehat\{H\}\_\{M\}\(x\)=H\_\{M\}\(x\)for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}\.

The five non\-input layers respectively contain the positive and negated literal features, product\-term AND features, stage\-level OR features, parity features, and the final XOR output\. Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11)is therefore a representation result rather than an additional approximation result: the circuit\-to\-network compilation incurs zero error on\{0,1\}B\\\{0,1\\\}^\{B\}\. Consequently, all statistical guarantees for the learned circuit transfer directly to its neural realization\.

###### Corollary 12\(Transfer of statistical guarantees\)\.

LetH^M\\widehat\{H\}\_\{M\}be the neural realization ofHMH\_\{M\}constructed by Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)\. Then, for every random variableXXsupported on\{0,1\}B\\\{0,1\\\}^\{B\},

Pr⁡\(H^M​\(X\)≠f⁡\(X\)\)=Pr⁡\(HM​\(X\)≠f⁡\(X\)\)\.\\Pr\\\!\\left\(\\widehat\{H\}\_\{M\}\(X\)\\neq f\(X\)\\right\)=\\Pr\\\!\\left\(H\_\{M\}\(X\)\\neq f\(X\)\\right\)\.

Consequently, every accuracy or generalization bound forHMH\_\{M\}established in Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)holds verbatim forH^M\\widehat\{H\}\_\{M\}\.

In particular, under Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9), ifS≤log2⁡BS\\leq\\log\_\{2\}B, thenQt≤2S≤BQ\_\{t\}\\leq 2^\{S\}\\leq Bat every completed stage, yielding the compiled network of width𝒪⁡\(m​B\)\\mathcal\{O\}\(mB\)\.

##### The Interpretability Certificate Implied by Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)\.

Our interpretability claim is deliberately modular\. We do*not*require every individual neuron to have a standalone semantic meaning\. Instead, identifiable neurons or small subnetworks form modules with exact logical meanings: literal formation, AND, OR, and XOR\. The interpretable object is therefore the decomposition of the network into these certified modules, rather than an independent interpretation of every hidden unit\.

More precisely, the certificate associated with the compiled network is

𝒞M=def\.\(\(Jt,Gt\)t=1M,the gate\-to\-ReLU correspondence of Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)\)\.\\mathcal\{C\}\_\{M\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\(\(J\_\{t\},G\_\{t\}\)\_\{t=1\}^\{M\},\\text\{the gate\-to\-ReLU correspondence of Proposition\\penalty\\ \\ref\{prop:relu\-gate\-modules\}\}\\right\)\.At stagett,JtJ\_\{t\}identifies the selected input coordinates andGtG\_\{t\}specifies the corresponding symbolic correction, while the gate\-to\-ReLU correspondence identifies the subnetwork realizing each literal, conjunction, disjunction, and XOR operation\. By Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10), these subnetworks exactly realize their Boolean gates on Boolean inputs, and Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11)guarantees that their composition agrees exactly with the learned circuit on\{0,1\}B\\\{0,1\\\}^\{B\}\. The updateHt=Ht−1⊕FtH\_\{t\}=H\_\{t\-1\}\\oplus F\_\{t\}further exposes how each stage modifies the accumulated predictor, allowing the complete computation to be traced through an explicit sequence of Boolean operations\.

This construction differs from post hoc symbolic extraction or neural interpretation methods that begin with a trained network and subsequently seek symbolic descriptions of its internal computation\. Here, the circuit is itself an output of the training procedure, and the neural network is compiled from that circuit with a known module\-by\-module correspondence\. No separate interpretation step is therefore required to identify which subnetworks implement the learned logical operations\.

The certificate should be distinguished from the statistical guarantee\. Exact circuit–network equivalence does not imply that the learned rule agrees with the unknown target on every unobserved input; this is controlled by the assumptions and results of Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)\. Moreover, the certificate applies on the Boolean cube: althoughH^M\\widehat\{H\}\_\{M\}defines a piecewise\-linear function onℝB\\mathbb\{R\}^\{B\}, we assign no Boolean interpretation to its off\-cube extension\. Finally, unconstrained fine\-tuning of the compiled network need not preserve the original exact logical certificate\.

## 5Experiments

We now evaluate the influence\-based residual training procedure, its computational scalability, and the performance of its exact neural realization relative to conventionally trained neural networks\. Our experiments use randomly generatedSS\-junta targetsf:\{0,1\}B→\{0,1\}f:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}\. For each seed, we sampleSScoordinates uniformly without replacement and independently assignBernoulli⁡\(1/2\)\\operatorname\{Bernoulli\}\(1/2\)labels to their2S2^\{S\}projected inputs\. Training inputs are sampled uniformly without replacement from the Boolean cube, while evaluation uses the full cube whenever feasible and an independent uniform test set otherwise\. Unless stated otherwise, results are averaged over2020seeds and reported as mean±\\pmstandard deviation, with compared methods using the same target, training set, and test set\.777The source code for reproducing the experiments is publicly available at:[https://github\.com/hradghoukasian/espresso](https://github.com/hradghoukasian/espresso)\.

Table[1](https://arxiv.org/html/2609.13439#S5.T1)spans regimes designed to stress different aspects of the method\. Configs\. 1–5 vary ambient dimension and target complexity; Configs\. 6–7 examine data\-sparse regimes; Config\. 8 matches the projection budget to the junta dimension; Config\. 9 considers a target requiring multiple projected stages; and Configs\. 10–11 probe the computational limits of the ambient truth\-table representation using very large training sets\. Configs\. 10–11 use the complete Boolean cube for training; their reported evaluation accuracy therefore measures reconstruction rather than out\-of\-sample generalization\.

Throughout the residual experiments, we setτ=0\\tau=0, ensuring every coordinate with positive empirical residual influence remains eligible and no threshold hyperparameter is tuned\. We use a maximum stage budget ofm=20m=20and report the predictor at common stage indices up to2020; if the empirical residual vanishes orCt=∅C\_\{t\}=\\varnothing, training terminates and the terminal predictor is carried forward unchanged for subsequent reported stages\. Ties between equal empirical influences are resolved deterministically by increasing coordinate index, and projected cells with tied residual counts are treated as don’t\-cares as in Equation \([1](https://arxiv.org/html/2609.13439#S3.E1)\)\. Further implementation details are given in Appendix[D](https://arxiv.org/html/2609.13439#A4)\.

### 5\.1Comparison with FlatEspresso

We first compare Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)with flatEspresso\. The flat baseline constructs aBB\-variable partial truth table, assigns the observed labels, treats all unobserved inputs as don’t\-cares, and invokesEspressoonce\. In contrast, our method repeatedly appliesEspressoto projected truth tables of dimension at mostKK\. This comparison therefore isolates the statistical and computational effects of replacing a single ambient\-dimensional minimization problem with a sequence of structured low\-dimensional corrections\.

Table 1:Experimental configurations\. The configurations cover moderate\-dimensional, data\-sparse, projection\-aligned, higher\-complexity, and large\-scale regimes\.Config\.TargetBBTTTest sizeKKConfig\. 188\-junta1212100010002122^\{12\}66Config\. 266\-junta1212100010002122^\{12\}44Config\. 388\-junta1515400040002152^\{15\}66Config\. 488\-junta2020400040002172^\{17\}66Config\. 588\-junta2323400040002172^\{17\}66Config\. 688\-junta12125005002122^\{12\}66Config\. 788\-junta15155005002152^\{15\}66Config\. 888\-junta1515100010002152^\{15\}88Config\. 91515\-junta20202152^\{15\}2172^\{17\}1010Config\. 1088\-junta20202202^\{20\}2172^\{17\}66Config\. 111010\-junta21212212^\{21\}2172^\{17\}88Table[2](https://arxiv.org/html/2609.13439#S5.T2)compares predictive accuracy, while Table[3](https://arxiv.org/html/2609.13439#S5.T3)reports the corresponding computational cost\. For each configuration, boldface identifies the better available method\.

Table 2:Predictive accuracy of the proposed method and flat ambient\-dimensionalEspresso\. Results are mean±\\pmstandard deviation over2020seeds\. “Failed” indicates that flatEspressodid not return a predictor within the computational budget\.Table 3:Cumulative stage\-2020runtime of the proposed method and runtime of flatEspresso, in seconds\. Results are mean±\\pmstandard deviation over2020seeds\. Boldface denotes the faster completed method\.Tables[2](https://arxiv.org/html/2609.13439#S5.T2)–[3](https://arxiv.org/html/2609.13439#S5.T3)reveal a clear accuracy–scalability tradeoff\. In Configs\. 1–4, flatEspressohas access to all ambient coordinates and attains higher accuracy, but its computational cost grows rapidly with the ambient representation\. This is especially pronounced in Config\. 4, where flatEspressoattains perfect accuracy but requires66\.966\.9seconds, compared with1\.791\.79seconds for the proposed method\.

Config\. 5 illustrates a statistical limitation of the proposed method\. WithB=23B=23and onlyT=4000T=4000passive observations, Hamming\-neighbor coverage is expected to become sparse, limiting the information available for empirical influence estimation\. Correspondingly, the proposed method attains only0\.6070\.607accuracy, while flatEspressoremains perfectly accurate but requires approximately578578seconds\.

The opposite accuracy pattern appears in Configs\. 6–9\. In the data\-sparse Configs\. 6–7, projection maps multiple ambient observations to the same low\-dimensional pattern, yielding denser projected partial truth tables forEspresso\. Config\. 8 provides the clearest example of this structural inductive bias: sinceK=S=8K=S=8, a correctly selected projection can contain the entire target support, yielding0\.9930\.993accuracy compared with0\.8390\.839for flatEspresso\. Config\. 9 further shows that residual refinement remains useful whenS\>KS\>K, with accuracy increasing from0\.5500\.550after one stage to0\.6060\.606after2020reported stages, compared with0\.5710\.571for flatEspresso\.

Finally, Configs\. 10–11 demonstrate the principal scalability advantage\. FlatEspressofails to return within the three\-hour computational budget, whereas the proposed method completes with accuracies0\.9180\.918and0\.9040\.904, respectively\. Further implementation details, including the failure criterion, are given in Appendix[D\.3](https://arxiv.org/html/2609.13439#A4.SS3)\. Thus, although projection can sacrifice accuracy in some regimes, the residual\-adaptive construction substantially enlarges the range of problems for whichEspresso\-based learning remains computationally feasible\.

### 5\.2Effect of Residual Stages

We next isolate the effect of residual refinement by varying the number of stages\. SinceFtF\_\{t\}is learned from the current residualrt=f⊕Ht−1r\_\{t\}=f\\oplus H\_\{t\-1\}, each additional stage targets errors left by the preceding predictor rather than relearningfffrom scratch\. We therefore evaluate the same residual\-learning sequence at successive stage indices to quantify the contribution of additional corrections\. Figure[2](https://arxiv.org/html/2609.13439#S5.F2)shows two representative configurations; results for the remaining configurations are reported in Appendix[E\.1](https://arxiv.org/html/2609.13439#A5.SS1)\.

\(a\)Config\. 1\.\(b\)Config\. 10\.
Figure 2:Test accuracy across residual stages for Configs\. 1 and 10\. Curves show the mean over2020seeds and shaded regions show95%95\\%confidence intervals for the mean\.As shown in Figure[2](https://arxiv.org/html/2609.13439#S5.F2), most of the improvement occurs in the early residual stages\. In both Configs\. 1 and 10, test accuracy rises rapidly over the first few stages and then improves more gradually\. This pattern suggests that the early stages capture the dominant residual structure, while later stages provide progressively smaller corrections\. The trend is empirical rather than guaranteed: because each stage is fitted to the training residual, an additional correction need not improve population accuracy\.

### 5\.3Influence Selection versus Random Selection

We next isolate the effect of influence\-based coordinate selection\. The random\-KKablation retains residual learning, projection,Espressominimization, and XOR aggregation, but replaces influence ranking by uniformly samplingKKcoordinates at each stage\. Table[4](https://arxiv.org/html/2609.13439#S5.T4)reports three representative configurations; results for the remaining configurations are given in Appendix[E\.2](https://arxiv.org/html/2609.13439#A5.SS2)\.

Table 4:Influence\-selection ablation at the stage\-2020reporting point\. Results are mean±\\pmstandard deviation over2020seeds\. Boldface denotes the better value within each configuration and metric\.Influence\-based selection substantially improves test accuracy in all three representative settings\. By concentrating the projection budget on coordinates with high empirical residual influence, each stage presentsEspressowith variables that are more informative for correcting the current residual\. Random selection discards this information and therefore more often allocates the limited budget to less useful coordinates\.

The runtime comparison is more nuanced\. Influence selection incurs the additional cost of estimating and ranking coordinate influences, yet it is slightly faster in Configs\. 3 and 6\. One possible explanation is that more informative projections lead to easier downstreamEspressoproblems, partially offsetting the influence\-estimation overhead\. This effect is not uniform: in Config\. 10, influence selection is substantially slower than random selection\. Thus, its primary empirical benefit is the consistent improvement in predictive accuracy, while its runtime effect depends on the projected residual problems encountered across stages\.

### 5\.4Comparison with Trained Neural Networks

Finally, we compare the exact ReLU realization produced by Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)with depth\- and hidden\-width\-matched dense ReLU and sigmoid MLPs trained using Adam\. By Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11), the compiled network introduces no additional approximation error: on the Boolean cube, its predictions coincide exactly with those of the learned Boolean circuit\. The comparison therefore contrasts two distinct inductive biases and training paradigms rather than two parameterizations trained by the same optimization procedure\.

The trainable networks use Adam with learning rate10−310^\{\-3\}, batch size256256, and binary cross\-entropy loss\. We train for10001000epochs except in the full\-cube configurations\. For example, one epoch over2202^\{20\}examples with batch size256256already comprises40964096gradient updates, comparable in order to10001000epochs on a dataset withT=1000T=1000\. Hence, the smaller epoch count used in Config\. 10 reflects the substantially larger number of optimization steps per epoch rather than an intentionally weaker baseline\. The complete training protocol is given in Appendix[D\.8](https://arxiv.org/html/2609.13439#A4.SS8)\.

Table 5:Exact circuit\-derived ReLU realization versus depth\- and hidden\-width\-matched gradient\-trained MLPs\. Results are mean±\\pmstandard deviation over2020seeds\. Boldface denotes the highest accuracy and lowest runtime within each configuration\.Table[5](https://arxiv.org/html/2609.13439#S5.T5)reveals a regime\-dependent comparison\. In Configs\. 1–5, the gradient\-trained ReLU MLP attains higher accuracy, showing that the low\-dimensional projection bias can be restrictive\. In Configs\. 6–9, however, the exact realization is more accurate; these are also precisely the configurations in which the underlying Boolean learner outperforms flatEspresso\. Since Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)preserves the Boolean predictor exactly, these gains are inherited from the combinatorial learner rather than introduced by neural compilation\. In the full\-cube Configs\. 10–11, the trained ReLU again attains perfect accuracy, while the exact realization reaches0\.9180\.918and0\.9040\.904, respectively\.

These results illustrate the structural inductive bias of the proposed method\. The learner assumes that useful residual structure can be exposed through successive low\-dimensional sets of influential coordinates\. When this structure is well aligned with the target, projection concentrates observations into denser low\-dimensional truth tables and leavesEspressoto infer the corresponding logical corrections\. A conventionally trained MLP receives no such structural restriction and must instead learn the relevant coordinates and their Boolean interactions through gradient optimization\. Config\. 8, whereK=SK=S, provides the clearest example: the exact realization attains0\.9930\.993accuracy, compared with0\.7270\.727for the trained ReLU MLP\.

The same inductive bias can become restrictive when informative coordinates are difficult to identify from the available Hamming\-neighbor pairs or when the residual is poorly captured byKK\-dimensional corrections, as illustrated by Config\. 5\. Accordingly, Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)is not intended to improve the accuracy of the learned Boolean predictor: its role is to transfer that predictor exactly into a neural architecture while preserving an explicit AND–OR–XOR certificate\. The resulting model therefore trades the flexibility of unconstrained gradient training for a strong logical inductive bias and an exact, construction\-level interpretation of its computation\.

### 5\.5Discussion

The experiments show that the proposed method is best understood through its structural inductive bias rather than as a uniformly superior alternative to eitherEspressoor gradient\-trained neural networks\. It assumes that the target, or its successive residuals, contains useful low\-dimensional structure identifiable through empirical influence\. When this assumption is well aligned with the problem, projection both reduces the computational burden onEspressoand produces denser projected partial truth tables\. This yields improved accuracy in the data\-sparse and projection\-aligned Configs\. 6–9 and preserves computational feasibility in Configs\. 10–11, where flatEspressofails\.

The same inductive bias imposes limitations\. With sparse passive observations, few usable Hamming\-neighbor pairs may be available for estimating influence, while a small projection budgetKKcan exclude joint structure accessible to ambient\-dimensionalEspressoor unconstrained neural training\. The method therefore trades unrestricted ambient fitting for a structured sequence of low\-dimensional residual corrections\.

The ablations support both components of this construction: additional residual stages progressively refine the predictor, while influence\-based coordinate selection substantially outperforms random selection in accuracy\. Finally, Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)transfers the learned Boolean predictor exactly to a neural architecture while preserving the logical certificate of Section[4\.2](https://arxiv.org/html/2609.13439#S4.SS2)\. Taken together, the experiments indicate that the method is most effective when its low\-dimensional Boolean inductive bias matches the target structure, yielding a combination of computational scalability, predictive accuracy, and certifiable interpretability\.

## 6Conclusion and Future Work

We introduced a specialized training procedure for Boolean classification that balances predictive generalization and expressive power with the constraint of belonging to a combinatorially meaningful class of interpretable neural networks\. Our procedure iteratively identifies influential coordinates of the current residual and learns low\-dimensional logical corrections usingEspresso\(Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\), with guarantees for influence recovery \(Theorem[6](https://arxiv.org/html/2609.13439#Thmtheorem6)\) and truth\-table prediction \(Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9)\)\. The resulting\{AND,OR,XOR\}\\\{\\operatorname\{AND\},\\operatorname\{OR\},\\operatorname\{XOR\}\\\}\-circuit is then compiled exactly into a sparsely connectedReLU\\operatorname\{ReLU\}\-MLP \(Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2); Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11)\), yielding an explicit logical certificate for the network’s computation\. Empirically, this structure provides a useful inductive bias in several partially observed regimes, while the residual\-adaptive construction remains computationally feasible in ambient dimensions where direct application ofEspressofails\.

Several directions remain open\. Most fundamentally, extending the framework beyond Boolean classification to real\-valued regression requires identifying an appropriate analogue of the logical circuit: it is unclear which interpretable primitive “gates,” circuit class, and corresponding training procedure should replaceAND\\operatorname\{AND\},OR\\operatorname\{OR\}, andXOR\\operatorname\{XOR\}in the real\-valued setting\. A second direction is to characterize theoretically when the stage\-wise logical structure yields a favorable inductive bias relative to flat logic minimization or gradient\-trained neural networks\. It would also be useful to weaken the thresholded top\-KKinfluence\-separation condition underlying the current prediction guarantee \(Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9)\), for example by allowing approximate variable recovery or by controlling prediction directly through the influence captured at each stage\.

Finally, the exact neural compilation suggests extensions beyond MLP architectures\. In particular, one could transfer the resultingReLU\\operatorname\{ReLU\}\-MLP and its compiled logical computation to aReLU\\operatorname\{ReLU\}\-Transformer using the exactReLU\\operatorname\{ReLU\}\-MLP\-to\-ReLU\\operatorname\{ReLU\}\-Transformer conversion of\([Kratsios et al\., 2026b](https://arxiv.org/html/2609.13439#bib.bib89), Proposition A\.1\)\. This introduces the possibility of extending the present certification framework to Transformer architectures while preserving the explicitly learned Boolean computation\.

###### acknowledgments\-disclosure\-of\-funding\.

A\. Kratsios and H\. Ghoukasian acknowledge financial support from an NSERC Discovery Grant No\. RGPIN\-2023\-04482 and No\. DGECR\-2023\-00230\. They acknowledge that resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute888[https://vectorinstitute\.ai/partnerships/current\-partners/](https://vectorinstitute.ai/partnerships/current-partners/)\.

## Appendix AProofs of the Statistical Guarantees

This appendix contains the proofs of the statistical guarantees stated in Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)\. In this appendix,ν=Unif⁡\(\{0,1\}B\)\\nu=\\operatorname\{Unif\}\(\\\{0,1\\\}^\{B\}\), and probabilities without an explicit input distribution are taken with respect toX∼νX\\sim\\nu\.

### A\.1Proofs of Uniform Influence Recovery and Junta Specialization

We first establish a uniform influence\-recovery result for an arbitrary finite Boolean function class\. Theorem[6](https://arxiv.org/html/2609.13439#Thmtheorem6)then follows by specializing this result to the class ofSS\-juntas\.

#### A\.1\.1An Occupancy Bound

The paired\-sampling model assigns every observation to a uniformly selected coordinate\. We first ensure that every coordinate receives sufficiently many paired observations\.

###### Lemma 13\(Uniform occupancy lower bound\)\.

LetI1,…,INI\_\{1\},\\ldots,I\_\{N\}be independent random variables uniformly distributed on\[B\]\[B\], and defineMi=def\.∑n=1N𝟙\{In=i\}M\_\{i\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{n=1\}^\{N\}\\mathbbm\{1\}\\\{I\_\{n\}=i\\\}, for alli∈\[B\]i\\in\[B\]\. For everyq∈ℕ\+q\\in\\mathbb\{N\}\_\{\+\}andδ∈\(0,1\)\\delta\\in\(0,1\), there exists a universal constantC\>0C\>0such thatN≥C​B​\(q\+log⁡Bδ\)N\\geq CB\\left\(q\+\\log\\frac\{B\}\{\\delta\}\\right\)implies

Pr\[mini∈\[B\]Mi≥q\]≥1−δ\.\\Pr\\left\[\\min\_\{i\\in\[B\]\}M\_\{i\}\\geq q\\right\]\\geq 1\-\\delta\.

###### Proof\.

For eachi∈\[B\]i\\in\[B\],Mi∼Bin⁡\(N,1/B\)M\_\{i\}\\sim\\operatorname\{Bin\}\(N,1/B\), with meanλ=N/B\\lambda=N/B\. ChooseCCsufficiently large that the assumed lower bound impliesλ≥2​q\\lambda\\geq 2qandλ≥8​log⁡Bδ\\lambda\\geq 8\\log\\frac\{B\}\{\\delta\}\. Sinceq≤λ/2q\\leq\\lambda/2, by the multiplicative Chernoff bound\([Mitzenmacher and Upfal, 2005](https://arxiv.org/html/2609.13439#bib.bib3)\), we have

Pr⁡\(Mi<q\)≤Pr⁡\(Mi<λ2\)≤exp⁡\(−λ8\)≤δB\.\\Pr\(M\_\{i\}<q\)\\leq\\Pr\\left\(M\_\{i\}<\\frac\{\\lambda\}\{2\}\\right\)\\leq\\exp\\left\(\-\\frac\{\\lambda\}\{8\}\\right\)\\leq\\frac\{\\delta\}\{B\}\.A union bound overi∈\[B\]i\\in\[B\]therefore yields

Pr\[mini∈\[B\]Mi<q\]≤∑i=1BPr\(Mi<q\)≤δ\.\\Pr\\left\[\\min\_\{i\\in\[B\]\}M\_\{i\}<q\\right\]\\leq\\sum\_\{i=1\}^\{B\}\\Pr\(M\_\{i\}<q\)\\leq\\delta\.∎

#### A\.1\.2A General Finite\-Class Influence\-Recovery Theorem

###### Theorem 14\(Simultaneous influence recovery\)\.

Letℋ\\mathcal\{H\}be a finite class of Boolean functions on\{0,1\}B\\\{0,1\\\}^\{B\}\. For everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\), there exists a universal constantC\>0C\>0such that, if

N≥C​Bε2​\(log⁡\|ℋ\|\+log⁡2​Bδ\),N\\geq C\\frac\{B\}\{\\varepsilon^\{2\}\}\\left\(\\log\|\\mathcal\{H\}\|\+\\log\\frac\{2B\}\{\\delta\}\\right\),\(10\)then, with probability at least1−δ1\-\\delta, everyMiM\_\{i\}is positive and

max⁡suph∈ℋi∈\[B\]⁡\|Inf^ipair​\(h\)−Infi⁡\(h\)\|≤ε\.\\max\_\{i\\in\[B\]\}\\sup\_\{h\\in\\mathcal\{H\}\}\\left\|\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\-\\operatorname\{Inf\}\_\{i\}\(h\)\\right\|\\leq\\varepsilon\.\(11\)

###### Proof\.

Forh∈ℋh\\in\\mathcal\{H\}andi∈\[B\]i\\in\[B\], defineϕh,i\(x\)=def\.𝟙\{h\(x\)≠h\(x⊕i\)\}\\phi\_\{h,i\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\mathbbm\{1\}\\\{h\(x\)\\neq h\(x^\{\\oplus i\}\)\\\}, so thatInfi⁡\(h\)=𝔼X∼ν​\[ϕh,i​\(X\)\]\\operatorname\{Inf\}\_\{i\}\(h\)=\\mathbb\{E\}\_\{X\\sim\\nu\}\[\\phi\_\{h,i\}\(X\)\]\. Fixi∈\[B\]i\\in\[B\]\. Conditional onMi=qM\_\{i\}=q, the set\{n:In=i\}\\\{n:I\_\{n\}=i\\\}has cardinalityqq\. SinceX1,…,XNX\_\{1\},\\ldots,X\_\{N\}are independent ofI1,…,INI\_\{1\},\\ldots,I\_\{N\}, the corresponding inputs\{Xn:In=i\}\\\{X\_\{n\}:I\_\{n\}=i\\\}remainqqindependent draws fromν\\nu\. Hence, for every fixedh∈ℋh\\in\\mathcal\{H\},Inf^ipair\(h\)=q−1∑n:In=iϕh,i\(Xn\)\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)=q^\{\-1\}\\sum\_\{n:I\_\{n\}=i\}\\phi\_\{h,i\}\(X\_\{n\}\)is the empirical mean ofqqindependent\{0,1\}\\\{0,1\\\}\-valued random variables with meanInfi⁡\(h\)\\operatorname\{Inf\}\_\{i\}\(h\)\. By Hoeffding’s inequality,

Pr⁡\(\|Inf^ipair​\(h\)−Infi⁡\(h\)\|\>ε\|Mi=q\)≤2​e−2​q​ε2\.\\Pr\\\!\\left\(\\left\|\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\-\\operatorname\{Inf\}\_\{i\}\(h\)\\right\|\>\\varepsilon\\,\\middle\|\\,M\_\{i\}=q\\right\)\\leq 2e^\{\-2q\\varepsilon^\{2\}\}\.A union bound overh∈ℋh\\in\\mathcal\{H\}therefore gives

Pr⁡\(suph∈ℋ\|Inf^ipair​\(h\)−Infi⁡\(h\)\|\>ε\|Mi=q\)≤2​\|ℋ\|​e−2​q​ε2\.\\Pr\\\!\\left\(\\sup\_\{h\\in\\mathcal\{H\}\}\\left\|\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\-\\operatorname\{Inf\}\_\{i\}\(h\)\\right\|\>\\varepsilon\\,\\middle\|\\,M\_\{i\}=q\\right\)\\leq 2\|\\mathcal\{H\}\|e^\{\-2q\\varepsilon^\{2\}\}\.
So far, for a fixed coordinateii, we have shown that the influence estimates are uniformly accurate over allh∈ℋh\\in\\mathcal\{H\}, provided that coordinateiireceives sufficiently many paired samples\. We next choose the required number of samples per coordinate so that this failure probability can later be union bounded over allBBcoordinates\.

Setqreq=def\.⌈\(2​ε2\)−1​log⁡\(4​B​\|ℋ\|/δ\)⌉q\_\{\\mathrm\{req\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\\lceil\(2\\varepsilon^\{2\}\)^\{\-1\}\\log\(4B\|\\mathcal\{H\}\|/\\delta\)\\right\\rceil, so that2​\|ℋ\|​e−2​q​ε2≤δ/\(2​B\)2\|\\mathcal\{H\}\|e^\{\-2q\\varepsilon^\{2\}\}\\leq\\delta/\(2B\)for everyq≥qreqq\\geq q\_\{\\mathrm\{req\}\}\. Therefore, wheneverMi≥qreqM\_\{i\}\\geq q\_\{\\mathrm\{req\}\}, the probability that coordinateiiviolates the desired uniform influence\-recovery bound is at mostδ/\(2​B\)\\delta/\(2B\)\.

It remains to ensure that this condition holds simultaneously for every coordinate\. Applying Lemma[13](https://arxiv.org/html/2609.13439#Thmtheorem13)withq=qreqq=q\_\{\\mathrm\{req\}\}and failure probabilityδ/2\\delta/2, it suffices that

N≥C0​B​\(qreq\+log⁡2​Bδ\)\.N\\geq C\_\{0\}B\\left\(q\_\{\\mathrm\{req\}\}\+\\log\\frac\{2B\}\{\\delta\}\\right\)\.\(12\)Sinceqreq≤1\+12​ε2​\(log⁡\|ℋ\|\+log⁡4​Bδ\)q\_\{\\mathrm\{req\}\}\\leq 1\+\\frac\{1\}\{2\\varepsilon^\{2\}\}\\left\(\\log\|\\mathcal\{H\}\|\+\\log\\frac\{4B\}\{\\delta\}\\right\)andε∈\(0,1\)\\varepsilon\\in\(0,1\), there exists a universal constantC\>0C\>0such that

C0​B​\(qreq\+log⁡2​Bδ\)≤C​Bε2​\(log⁡\|ℋ\|\+log⁡2​Bδ\)\.C\_\{0\}B\\left\(q\_\{\\mathrm\{req\}\}\+\\log\\frac\{2B\}\{\\delta\}\\right\)\\leq C\\frac\{B\}\{\\varepsilon^\{2\}\}\\left\(\\log\|\\mathcal\{H\}\|\+\\log\\frac\{2B\}\{\\delta\}\\right\)\.Therefore, the sample\-size condition \([10](https://arxiv.org/html/2609.13439#A1.E10)\) implies \([12](https://arxiv.org/html/2609.13439#A1.E12)\)\. Applying Lemma[13](https://arxiv.org/html/2609.13439#Thmtheorem13)with failure probabilityδ/2\\delta/2then yields

Pr⁡\(Mi≥qreq​for all​i∈\[B\]\)≥1−δ2\.\\Pr\\\!\\left\(M\_\{i\}\\geq q\_\{\\mathrm\{req\}\}\\text\{ for all \}i\\in\[B\]\\right\)\\geq 1\-\\frac\{\\delta\}\{2\}\.
Hence, with probability at least1−δ/21\-\\delta/2, every coordinate receives at leastqreqq\_\{\\mathrm\{req\}\}paired samples\. On this event, the bound derived above applies to everyi∈\[B\]i\\in\[B\]: for each coordinate, the probability of failure, uniformly overh∈ℋh\\in\\mathcal\{H\}, is at mostδ/\(2​B\)\\delta/\(2B\)\. Since the occupancy event depends only onI1,…,INI\_\{1\},\\ldots,I\_\{N\}, conditioning on it does not change the distribution of the independent inputsX1,…,XNX\_\{1\},\\ldots,X\_\{N\}\. A union bound over theBBcoordinates therefore gives

Pr⁡\(max⁡suph∈ℋi∈\[B\]⁡\|Inf^ipair​\(h\)−Infi⁡\(h\)\|\>ε\|Mi≥qreq​for all​i∈\[B\]\)≤δ2\.\\Pr\\\!\\left\(\\max\_\{i\\in\[B\]\}\\sup\_\{h\\in\\mathcal\{H\}\}\\left\|\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\-\\operatorname\{Inf\}\_\{i\}\(h\)\\right\|\>\\varepsilon\\,\\middle\|\\,M\_\{i\}\\geq q\_\{\\mathrm\{req\}\}\\text\{ for all \}i\\in\[B\]\\right\)\\leq\\frac\{\\delta\}\{2\}\.
We have therefore identified two possible sources of failure: the occupancy event may fail, which occurs with probability at mostδ/2\\delta/2, or the occupancy event may hold while at least one coordinate violates the influence\-recovery bound, whose conditional probability is at mostδ/2\\delta/2\. Combining these two failure probabilities yields

Pr⁡\(max⁡suph∈ℋi∈\[B\]⁡\|Inf^ipair​\(h\)−Infi⁡\(h\)\|\>ε\)≤δ\.\\Pr\\\!\\left\(\\max\_\{i\\in\[B\]\}\\sup\_\{h\\in\\mathcal\{H\}\}\\left\|\\widehat\{\\operatorname\{Inf\}\}^\{\\mathrm\{pair\}\}\_\{i\}\(h\)\-\\operatorname\{Inf\}\_\{i\}\(h\)\\right\|\>\\varepsilon\\right\)\\leq\\delta\.Hence \([11](https://arxiv.org/html/2609.13439#A1.E11)\) holds with probability at least1−δ1\-\\delta\. Moreover, on the occupancy event,Mi≥qreq≥1M\_\{i\}\\geq q\_\{\\mathrm\{req\}\}\\geq 1for everyi∈\[B\]i\\in\[B\]\. Hence, all paired influence estimators are well defined\. ∎

#### A\.1\.3Specialization to Juntas

We next bound the number of Boolean functions depending on at mostSScoordinates\.

###### Lemma 15\(Cardinality of the junta class\)\.

For1≤S≤B1\\leq S\\leq B,

\|𝒥B,S\|≤∑s=0S\(Bs\)​22s≤22S​\(e​BS\)S\.\|\\mathcal\{J\}\_\{B,S\}\|\\leq\\sum\_\{s=0\}^\{S\}\\binom\{B\}\{s\}2^\{2^\{s\}\}\\leq 2^\{2^\{S\}\}\\left\(\\frac\{eB\}\{S\}\\right\)^\{S\}\.Consequently,

log⁡\|𝒥B,S\|≤C⁡\(2S\+S​log⁡e​BS\)\\log\|\\mathcal\{J\}\_\{B,S\}\|\\leq C\\left\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\\right\)for a universal constantC\>0C\>0\.

###### Proof\.

For a fixed coordinate set of sizess, there are22s2^\{2^\{s\}\}Boolean functions on the corresponding projected cube\. Summing over all coordinate sets of size at mostSSgives

\|𝒥B,S\|≤∑s=0S\(Bs\)​22s\.\|\\mathcal\{J\}\_\{B,S\}\|\\leq\\sum\_\{s=0\}^\{S\}\\binom\{B\}\{s\}2^\{2^\{s\}\}\.Since22s≤22S2^\{2^\{s\}\}\\leq 2^\{2^\{S\}\}fors≤Ss\\leq S,

\|𝒥B,S\|≤22S​∑s=0S\(Bs\)≤22S​\(e​BS\)S,\|\\mathcal\{J\}\_\{B,S\}\|\\leq 2^\{2^\{S\}\}\\sum\_\{s=0\}^\{S\}\\binom\{B\}\{s\}\\leq 2^\{2^\{S\}\}\\left\(\\frac\{eB\}\{S\}\\right\)^\{S\},where the last inequality follows from the standard binomial\-sum bound∑s=0S\(Bs\)≤\(e​BS\)S\\sum\_\{s=0\}^\{S\}\\binom\{B\}\{s\}\\leq\\left\(\\frac\{eB\}\{S\}\\right\)^\{S\}, see, e\.g\.,[Haussler \(1995, Lemma 1\)](https://arxiv.org/html/2609.13439#bib.bib2)\. Taking logarithms proves the claim\. ∎

###### Proof of Theorem[6](https://arxiv.org/html/2609.13439#Thmtheorem6)\.

Apply Theorem[14](https://arxiv.org/html/2609.13439#Thmtheorem14)withℋ=𝒥B,S\\mathcal\{H\}=\\mathcal\{J\}\_\{B,S\}\. By Lemma[15](https://arxiv.org/html/2609.13439#Thmtheorem15),

log⁡\|𝒥B,S\|≤C⁡\(2S\+S​log⁡e​BS\)\.\\log\|\\mathcal\{J\}\_\{B,S\}\|\\leq C\\left\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\\right\)\.Substituting this bound into \([10](https://arxiv.org/html/2609.13439#A1.E10)\) givesN≥C​Bε2​\(2S\+S​log⁡e​BS\+log⁡2​Bδ\)N\\geq C\\frac\{B\}\{\\varepsilon^\{2\}\}\\bigl\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\+\\log\\frac\{2B\}\{\\delta\}\\bigr\), after adjusting the universal constant\.

IfS=𝒪⁡\(log⁡B\)S=\\mathcal\{O\}\(\\log B\), then2S2^\{S\}is polynomial inBB, while

S​log⁡e​BS=𝒪⁡\(\(log⁡B\)2\)\.S\\log\\frac\{eB\}\{S\}=\\mathcal\{O\}\(\(\\log B\)^\{2\}\)\.The stated polynomial dependence follows\. ∎

### A\.2Proofs of Coordinate Recovery and Truth\-Table Accuracy

We first establish exact recovery of the population\-selected coordinates and then use this result to derive the corresponding truth\-table accuracy guarantees\.

#### A\.2\.1Recovery of the Population\-Selected Coordinates

###### Lemma 16\(Zero\-influence preservation\)\.

Leth:\{0,1\}B→\{0,1\}h:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}, and letInf^i​\(h\)\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(h\)be the pair\-based empirical influence estimator used in Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\. IfInfi⁡\(h\)=0\\operatorname\{Inf\}\_\{i\}\(h\)=0, thenInf^i​\(h\)=0\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(h\)=0\. The same conclusion holds for the paired\-sampling estimatorInf^ipair​\(h\)\\widehat\{\\operatorname\{Inf\}\}\_\{i\}^\{\\mathrm\{pair\}\}\(h\)whenever it is defined\.

###### Proof\.

Under the uniform distribution on\{0,1\}B\\\{0,1\\\}^\{B\}, every input has strictly positive probability\. Hence

Infi\(h\)=Pr\[h\(X\)≠h\(X⊕i\)\]=0\\operatorname\{Inf\}\_\{i\}\(h\)=\\Pr\\\!\\left\[h\(X\)\\neq h\(X^\{\\oplus i\}\)\\right\]=0implies

h⁡\(x\)=h⁡\(x⊕i\)for every​x∈\{0,1\}B\.h\(x\)=h\(x^\{\\oplus i\}\)\\qquad\\text\{for every \}x\\in\\\{0,1\\\}^\{B\}\.Therefore, every disagreement indicator appearing in either pair\-based empirical estimator is zero\. If no observedii\-edge is available, Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)sets the empirical influence to zero by convention\. ThusInf^i​\(h\)=0\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(h\)=0, and the same argument applies toInf^ipair​\(h\)\\widehat\{\\operatorname\{Inf\}\}\_\{i\}^\{\\mathrm\{pair\}\}\(h\)\. ∎

###### Lemma 17\(Recovery of population\-selected coordinates\)\.

Whenever \([4](https://arxiv.org/html/2609.13439#S4.E4)\) holds, Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8)ensures that Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)selectsJt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}for every completed stagett\.

###### Proof\.

Fix a completed stagett, and writeai=def\.Infi⁡\(rt\)a\_\{i\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)anda^i=def\.Inf^i​\(rt\)\\widehat\{a\}\_\{i\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\. On the event \([4](https://arxiv.org/html/2609.13439#S4.E4)\),\|a^i−ai\|≤εinf\|\\widehat\{a\}\_\{i\}\-a\_\{i\}\|\\leq\\varepsilon\_\{\\mathrm\{inf\}\}for everyi∈\[B\]i\\in\[B\]\. First, everyi∈Jt⋆i\\in J\_\{t\}^\{\\star\}passes the empirical threshold, since Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8)givesai\>τ\+εinfa\_\{i\}\>\\tau\+\\varepsilon\_\{\\mathrm\{inf\}\}, and hencea^i≥ai−εinf\>τ\\widehat\{a\}\_\{i\}\\geq a\_\{i\}\-\\varepsilon\_\{\\mathrm\{inf\}\}\>\\tau\.

Suppose first that\|Ct⋆\|≤K\|C\_\{t\}^\{\\star\}\|\\leq K, so thatJt⋆=Ct⋆J\_\{t\}^\{\\star\}=C\_\{t\}^\{\\star\}\. Fixj∉Ct⋆j\\notin C\_\{t\}^\{\\star\}\. Ifaj=0a\_\{j\}=0, then Lemma[16](https://arxiv.org/html/2609.13439#Thmtheorem16)givesa^j=0≤τ\\widehat\{a\}\_\{j\}=0\\leq\\tau, andjjdoes not pass the empirical threshold\. Otherwise, Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8)givesaj<τ−εinfa\_\{j\}<\\tau\-\\varepsilon\_\{\\mathrm\{inf\}\}, and thereforea^j≤aj\+εinf<τ\\widehat\{a\}\_\{j\}\\leq a\_\{j\}\+\\varepsilon\_\{\\mathrm\{inf\}\}<\\tau\. Thus, every coordinate inCt⋆C\_\{t\}^\{\\star\}and no coordinate outsideCt⋆C\_\{t\}^\{\\star\}passes the empirical threshold\. HenceCt=Ct⋆C\_\{t\}=C\_\{t\}^\{\\star\}, and since\|Ct⋆\|≤K\|C\_\{t\}^\{\\star\}\|\\leq K,Jt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}\.

Now suppose that\|Ct⋆\|\>K\|C\_\{t\}^\{\\star\}\|\>K\. Then\|Jt⋆\|=K\|J\_\{t\}^\{\\star\}\|=KandCt⋆∖Jt⋆≠∅C\_\{t\}^\{\\star\}\\setminus J\_\{t\}^\{\\star\}\\neq\\varnothing\. For everyi∈Jt⋆i\\in J\_\{t\}^\{\\star\}andj∈Ct⋆∖Jt⋆j\\in C\_\{t\}^\{\\star\}\\setminus J\_\{t\}^\{\\star\}, Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8)givesai−aj\>2​εinfa\_\{i\}\-a\_\{j\}\>2\\varepsilon\_\{\\mathrm\{inf\}\}, and hencea^i−a^j≥ai−aj−2​εinf\>0\\widehat\{a\}\_\{i\}\-\\widehat\{a\}\_\{j\}\\geq a\_\{i\}\-a\_\{j\}\-2\\varepsilon\_\{\\mathrm\{inf\}\}\>0\. To compare with coordinates outsideCt⋆C\_\{t\}^\{\\star\}, letaout=def\.maxℓ∈Ct⋆∖Jt⋆⁡aℓa\_\{\\mathrm\{out\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\max\_\{\\ell\\in C\_\{t\}^\{\\star\}\\setminus J\_\{t\}^\{\\star\}\}a\_\{\\ell\}\. Sinceaout\>τa\_\{\\mathrm\{out\}\}\>\\tauwhileaj≤τa\_\{j\}\\leq\\taufor everyj∉Ct⋆j\\notin C\_\{t\}^\{\\star\}, we haveaj<aouta\_\{j\}<a\_\{\\mathrm\{out\}\}\. Therefore, for everyi∈Jt⋆i\\in J\_\{t\}^\{\\star\}andj∉Ct⋆j\\notin C\_\{t\}^\{\\star\},ai−aj\>ai−aout\>2​εinfa\_\{i\}\-a\_\{j\}\>a\_\{i\}\-a\_\{\\mathrm\{out\}\}\>2\\varepsilon\_\{\\mathrm\{inf\}\}, which impliesa^i\>a^j\\widehat\{a\}\_\{i\}\>\\widehat\{a\}\_\{j\}\. Thus every coordinate inJt⋆J\_\{t\}^\{\\star\}has strictly larger empirical influence than every coordinate outsideJt⋆J\_\{t\}^\{\\star\}\. Since all coordinates inJt⋆J\_\{t\}^\{\\star\}also pass the empirical threshold, the algorithm selects exactlyJt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}\. Sincettwas arbitrary, the conclusion holds simultaneously for every completed stage\. ∎

#### A\.2\.2Projected Majority as an Empirical Risk Minimizer

ForJ⊆\[B\]J\\subseteq\[B\], define𝒢J=def\.\{x↦g\(projJ\(x\)\):g:\{0,1\}\|J\|→\{0,1\}\}\\mathcal\{G\}\_\{J\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\\\{x\\mapsto g\(\\operatorname\{proj\}\_\{J\}\(x\)\):g:\\\{0,1\\\}^\{\|J\|\}\\to\\\{0,1\\\}\\right\\\}\.

###### Lemma 18\(Projected majority completion is an ERM\)\.

FixJ⊆\[B\]J\\subseteq\[B\]and observations\{\(Xℓ,Yℓ\)\}ℓ=1n\\\{\(X\_\{\\ell\},Y\_\{\\ell\}\)\\\}\_\{\\ell=1\}^\{n\}, whereXℓ∈\{0,1\}BX\_\{\\ell\}\\in\\\{0,1\\\}^\{B\}andYℓ∈\{0,1\}Y\_\{\\ell\}\\in\\\{0,1\\\}\. Construct the projected partial truth table by assigning each projected cell its strict empirical majority label and declaring tied or unobserved cells to be don’t\-cares\. Then every Boolean completion of this partial truth table is an empirical risk minimizer over𝒢J\\mathcal\{G\}\_\{J\}\.

###### Proof\.

Foru∈\{0,1\}\|J\|u\\in\\\{0,1\\\}^\{\|J\|\}anda∈\{0,1\}a\\in\\\{0,1\\\}, let

Na\(u\)=def\.\|\{ℓ∈\[n\]:projJ\(Xℓ\)=u,Yℓ=a\}\|\.N\_\{a\}\(u\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\|\\left\\\{\\ell\\in\[n\]:\\operatorname\{proj\}\_\{J\}\(X\_\{\\ell\}\)=u,\\,Y\_\{\\ell\}=a\\right\\\}\\right\|\.For anyg:\{0,1\}\|J\|→\{0,1\}g:\\\{0,1\\\}^\{\|J\|\}\\to\\\{0,1\\\}, the number of empirical errors is

∑u∈\{0,1\}\|J\|\[N1\(u\)𝟙\{g\(u\)=0\}\+N0\(u\)𝟙\{g\(u\)=1\}\]\.\\sum\_\{u\\in\\\{0,1\\\}^\{\|J\|\}\}\\left\[N\_\{1\}\(u\)\\mathbbm\{1\}\\\{g\(u\)=0\\\}\+N\_\{0\}\(u\)\\mathbbm\{1\}\\\{g\(u\)=1\\\}\\right\]\.The minimization therefore separates over projected cells\. A strict majority label uniquely minimizes the error of its cell, while either label minimizes a tied or unobserved cell\. Consequently, every completion agreeing with the strict\-majority entries minimizes the total empirical error\. ∎

#### A\.2\.3Generalization of the Projected Stage Learner

For later reference, define𝒢≤K=def\.⋃J⊆\[B\]\|J\|≤K𝒢J\\mathcal\{G\}\_\{\\leq K\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\bigcup\_\{\\begin\{subarray\}\{c\}J\\subseteq\[B\]\\\\ \|J\|\\leq K\\end\{subarray\}\}\\mathcal\{G\}\_\{J\}\. Its cardinality satisfies

log⁡\|𝒢≤K\|≤C⁡\(2K\+K​log⁡e​BK\)\.\\log\|\\mathcal\{G\}\_\{\\leq K\}\|\\leq C\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\\right\)\.\(13\)Indeed,

\|𝒢≤K\|≤∑k=0K\(Bk\)​22k≤22K​∑k=0K\(Bk\)≤22K​\(e​BK\)K,\|\\mathcal\{G\}\_\{\\leq K\}\|\\leq\\sum\_\{k=0\}^\{K\}\\binom\{B\}\{k\}2^\{2^\{k\}\}\\leq 2^\{2^\{K\}\}\\sum\_\{k=0\}^\{K\}\\binom\{B\}\{k\}\\leq 2^\{2^\{K\}\}\\left\(\\frac\{eB\}\{K\}\\right\)^\{K\},where the last inequality follows from the standard binomial\-sum bound∑k=0K\(Bk\)≤\(e​BK\)K\\sum\_\{k=0\}^\{K\}\\binom\{B\}\{k\}\\leq\\left\(\\frac\{eB\}\{K\}\\right\)^\{K\}; see, e\.g\.,[Haussler \(1995, Lemma 1\)](https://arxiv.org/html/2609.13439#bib.bib2)\. Taking logarithms and absorbing the factorlog⁡2\\log 2into a universal constant gives \([13](https://arxiv.org/html/2609.13439#A1.E13)\)\.

###### Theorem 19\(Generalization of the projected stage learner\)\.

For an arbitrary completed stagett, consider the stage\-wise sample\-splitting version of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1), assumingT≥mT\\geq m\. LetJt⊆\[B\]J\_\{t\}\\subseteq\[B\], with\|Jt\|≤K\|J\_\{t\}\|\\leq K, denote the coordinate set selected by the algorithm, and letGt:\{0,1\}\|Jt\|→\{0,1\}G\_\{t\}:\\\{0,1\\\}^\{\|J\_\{t\}\|\}\\to\\\{0,1\\\}denote the corresponding Boolean completion returned byEspresso\. Defineβt=def\.infg:\{0,1\}\|Jt\|→\{0,1\}Pr\[g\(projJt\(X\)\)≠rt\(X\)\]\\beta\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\inf\_\{g:\\\{0,1\\\}^\{\|J\_\{t\}\|\}\\to\\\{0,1\\\}\}\\Pr\[g\(\\operatorname\{proj\}\_\{J\_\{t\}\}\(X\)\)\\neq r\_\{t\}\(X\)\]\. Letδgen∈\(0,1\)\\delta\_\{\\mathrm\{gen\}\}\\in\(0,1\)\. Then, with probability at least1−δgen1\-\\delta\_\{\\mathrm\{gen\}\}, simultaneously for all completed stages,

Pr\[Gt\(projJt\(X\)\)≠rt\(X\)\]≤βt\+Cm⁡\(2K\+K​log⁡e​BK\+log⁡mδgen\)T\.\\Pr\\left\[G\_\{t\}\(\\operatorname\{proj\}\_\{J\_\{t\}\}\(X\)\)\\neq r\_\{t\}\(X\)\\right\]\\leq\\beta\_\{t\}\+C\\sqrt\{\\frac\{m\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}\.\(14\)

###### Proof\.

Letℱt−1\\mathscr\{F\}\_\{t\-1\}be the sigma\-algebra generated by the preceding batchesD\(1\),…,D\(t−1\)D^\{\(1\)\},\\ldots,D^\{\(t\-1\)\}\. Conditional onℱt−1\\mathscr\{F\}\_\{t\-1\}, the predictorHt−1H\_\{t\-1\}, and hencert=f⊕Ht−1r\_\{t\}=f\\oplus H\_\{t\-1\}, is fixed\. Moreover,D\(t\)D^\{\(t\)\}consists ofT0=⌊T/m⌋T\_\{0\}=\\lfloor T/m\\rfloorindependent samples fromν\\nu\.

Forq∈𝒢≤Kq\\in\\mathcal\{G\}\_\{\\leq K\}, defineRt\(q\)=def\.Pr\[q\(X\)≠rt\(X\)\]R\_\{t\}\(q\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\Pr\[q\(X\)\\neq r\_\{t\}\(X\)\], and letR^t​\(q\)\\widehat\{R\}\_\{t\}\(q\)denote the corresponding empirical error onD\(t\)D^\{\(t\)\}\. Conditional onℱt−1\\mathscr\{F\}\_\{t\-1\}, the residualrtr\_\{t\}is fixed andD\(t\)D^\{\(t\)\}is a fresh sample of sizeT0T\_\{0\}fromν\\nu\. Hence, for any fixedq∈𝒢≤Kq\\in\\mathcal\{G\}\_\{\\leq K\}, Hoeffding’s inequality gives

Pr⁡\(\|Rt​\(q\)−R^t​\(q\)\|\>η\|ℱt−1\)≤2​e−2​T0​η2\.\\Pr\\\!\\left\(\|R\_\{t\}\(q\)\-\\widehat\{R\}\_\{t\}\(q\)\|\>\\eta\\,\\middle\|\\,\\mathscr\{F\}\_\{t\-1\}\\right\)\\leq 2e^\{\-2T\_\{0\}\\eta^\{2\}\}\.Since the predictor ultimately selected at stagettis data\-dependent, we require this concentration bound to hold uniformly over allq∈𝒢≤Kq\\in\\mathcal\{G\}\_\{\\leq K\}\. A union bound therefore yields

Pr⁡\(supq∈𝒢≤K\|Rt​\(q\)−R^t​\(q\)\|\>η\|ℱt−1\)≤2​\|𝒢≤K\|​e−2​T0​η2\.\\Pr\\\!\\left\(\\sup\_\{q\\in\\mathcal\{G\}\_\{\\leq K\}\}\|R\_\{t\}\(q\)\-\\widehat\{R\}\_\{t\}\(q\)\|\>\\eta\\,\\middle\|\\,\\mathscr\{F\}\_\{t\-1\}\\right\)\\leq 2\|\\mathcal\{G\}\_\{\\leq K\}\|e^\{\-2T\_\{0\}\\eta^\{2\}\}\.Using \([13](https://arxiv.org/html/2609.13439#A1.E13)\), we have\|𝒢≤K\|≤exp⁡\(C0​\(2K\+K​log⁡e​BK\)\)\|\\mathcal\{G\}\_\{\\leq K\}\|\\leq\\exp\\\!\\left\(C\_\{0\}\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\\right\)\\right\)for some universal constantC0\>0C\_\{0\}\>0\. Hence

2​\|𝒢≤K\|​e−2​T0​η2≤2​exp⁡\(C0​\(2K\+K​log⁡e​BK\)−2​T0​η2\)\.2\|\\mathcal\{G\}\_\{\\leq K\}\|e^\{\-2T\_\{0\}\\eta^\{2\}\}\\leq 2\\exp\\\!\\left\(C\_\{0\}\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\\right\)\-2T\_\{0\}\\eta^\{2\}\\right\)\.To make this quantity at mostδgen/m\\delta\_\{\\mathrm\{gen\}\}/m, it is sufficient that

2​exp⁡\(C0​\(2K\+K​log⁡e​BK\)−2​T0​η2\)≤δgenm\.2\\exp\\\!\\left\(C\_\{0\}\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\\right\)\-2T\_\{0\}\\eta^\{2\}\\right\)\\leq\\frac\{\\delta\_\{\\mathrm\{gen\}\}\}\{m\}\.Taking logarithms and rearranging gives

2​T0​η2≥C0​\(2K\+K​log⁡e​BK\)\+log⁡2​mδgen,2T\_\{0\}\\eta^\{2\}\\geq C\_\{0\}\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\\right\)\+\\log\\frac\{2m\}\{\\delta\_\{\\mathrm\{gen\}\}\},and therefore it suffices to take

η≥C0​\(2K\+K​log⁡e​BK\)\+log⁡\(2​m/δgen\)2​T0\.\\eta\\geq\\sqrt\{\\frac\{C\_\{0\}\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\\right\)\+\\log\(2m/\\delta\_\{\\mathrm\{gen\}\}\)\}\{2T\_\{0\}\}\}\.Absorbing the numerical constants and the factorlog⁡2\\log 2into a universal constantC\>0C\>0, we obtain, with conditional probability at least1−δgen/m1\-\\delta\_\{\\mathrm\{gen\}\}/m,

supq∈𝒢≤K\|Rt​\(q\)−R^t​\(q\)\|≤C​2K\+K​log⁡\(e​B/K\)\+log⁡\(m/δgen\)T0\.\\sup\_\{q\\in\\mathcal\{G\}\_\{\\leq K\}\}\|R\_\{t\}\(q\)\-\\widehat\{R\}\_\{t\}\(q\)\|\\leq C\\sqrt\{\\frac\{2^\{K\}\+K\\log\(eB/K\)\+\\log\(m/\\delta\_\{\\mathrm\{gen\}\}\)\}\{T\_\{0\}\}\}\.Because𝒢≤K\\mathcal\{G\}\_\{\\leq K\}contains the classes𝒢J\\mathcal\{G\}\_\{J\}for everyJ⊆\[B\]J\\subseteq\[B\]with\|J\|≤K\|J\|\\leq K, this event holds simultaneously for every admissible support and therefore also for the data\-dependent setJtJ\_\{t\}selected by the algorithm\.

By Lemma[18](https://arxiv.org/html/2609.13439#Thmtheorem18), the liftedEspressocompletionqt​\(x\)=def\.Gt​\(projJt⁡\(x\)\)q\_\{t\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}G\_\{t\}\(\\operatorname\{proj\}\_\{J\_\{t\}\}\(x\)\)is an empirical risk minimizer over𝒢Jt\\mathcal\{G\}\_\{J\_\{t\}\}\. The standard ERM comparison therefore yields

Rt​\(qt\)≤βt\+C​2K\+K​log⁡\(e​B/K\)\+log⁡\(m/δgen\)T0\.R\_\{t\}\(q\_\{t\}\)\\leq\\beta\_\{t\}\+C\\sqrt\{\\frac\{2^\{K\}\+K\\log\(eB/K\)\+\\log\(m/\\delta\_\{\\mathrm\{gen\}\}\)\}\{T\_\{0\}\}\}\.A union bound overt=1,…,mt=1,\\ldots,mmakes the result simultaneous across stages\. Finally,T0=⌊Tm⌋≥T2​mT\_\{0\}=\\left\\lfloor\\frac\{T\}\{m\}\\right\\rfloor\\geq\\frac\{T\}\{2m\}whenT≥mT\\geq m, which gives \([14](https://arxiv.org/html/2609.13439#A1.E14)\)\. ∎

#### A\.2\.4Recovery\-to\-Accuracy Guarantee

For each completed stage, define

αt=def\.infg:\{0,1\}\|Jt⋆\|→\{0,1\}Pr\[g\(projJt⋆\(X\)\)≠rt\(X\)\]\.\\alpha\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\inf\_\{g:\\\{0,1\\\}^\{\|J\_\{t\}^\{\\star\}\|\}\\to\\\{0,1\\\}\}\\Pr\\left\[g\(\\operatorname\{proj\}\_\{J\_\{t\}^\{\\star\}\}\(X\)\)\\neq r\_\{t\}\(X\)\\right\]\.\(15\)Thus,αt\\alpha\_\{t\}is the population approximation error incurred when the stage predictor is restricted to the population\-selected coordinates\.

###### Theorem 20\(Recovery\-to\-accuracy guarantee\)\.

Consider Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)with stage\-wise sample splitting andT≥mT\\geq m\. Suppose Assumptions[7](https://arxiv.org/html/2609.13439#Thmtheorem7)and[8](https://arxiv.org/html/2609.13439#Thmtheorem8)hold\. Letδgen∈\(0,1\)\\delta\_\{\\mathrm\{gen\}\}\\in\(0,1\)\. Then, with probability at least1−δinf−δgen1\-\\delta\_\{\\mathrm\{inf\}\}\-\\delta\_\{\\mathrm\{gen\}\}, simultaneously for every completed stagett,

ℛ⁡\(Ht\)≤αt\+C​m⁡\(2K\+K​log⁡e​BK\+log⁡mδgen\)T\.\\mathcal\{R\}\(H\_\{t\}\)\\leq\\alpha\_\{t\}\+C\\sqrt\{\\frac\{m\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}\.\(16\)

###### Proof\.

Letℰinf=def\.\{maxtmaxi∈\[B\]\|Inf^i\(rt\)−Infi\(rt\)\|≤εinf\}\\mathcal\{E\}\_\{\\mathrm\{inf\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{\\max\_\{t\}\\max\_\{i\\in\[B\]\}\|\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\-\\operatorname\{Inf\}\_\{i\}\(r\_\{t\}\)\|\\leq\\varepsilon\_\{\\mathrm\{inf\}\}\\\}\. By Assumption[7](https://arxiv.org/html/2609.13439#Thmtheorem7),Pr⁡\(ℰinf\)≥1−δinf\\Pr\(\\mathcal\{E\}\_\{\\mathrm\{inf\}\}\)\\geq 1\-\\delta\_\{\\mathrm\{inf\}\}\. On this event, Lemma[17](https://arxiv.org/html/2609.13439#Thmtheorem17)givesJt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}simultaneously over all completed stages, and henceβt=αt\\beta\_\{t\}=\\alpha\_\{t\}\.

Letℰgen\\mathcal\{E\}\_\{\\mathrm\{gen\}\}denote the event on which the bound in Theorem[19](https://arxiv.org/html/2609.13439#Thmtheorem19)holds simultaneously for all completed stages; by that theorem,Pr⁡\(ℰgen\)≥1−δgen\\Pr\(\\mathcal\{E\}\_\{\\mathrm\{gen\}\}\)\\geq 1\-\\delta\_\{\\mathrm\{gen\}\}\. Onℰinf∩ℰgen\\mathcal\{E\}\_\{\\mathrm\{inf\}\}\\cap\\mathcal\{E\}\_\{\\mathrm\{gen\}\}, the identitiesrt=f⊕Ht−1r\_\{t\}=f\\oplus H\_\{t\-1\}andHt=Ht−1⊕FtH\_\{t\}=H\_\{t\-1\}\\oplus F\_\{t\}imply pointwise thatHt​\(x\)≠f​\(x\)H\_\{t\}\(x\)\\neq f\(x\)if and only ifFt​\(x\)≠rt​\(x\)F\_\{t\}\(x\)\\neq r\_\{t\}\(x\)\. Therefore,ℛ\(Ht\)=Pr\[Ft\(X\)≠rt\(X\)\]\\mathcal\{R\}\(H\_\{t\}\)=\\Pr\[F\_\{t\}\(X\)\\neq r\_\{t\}\(X\)\]\. Applying Theorem[19](https://arxiv.org/html/2609.13439#Thmtheorem19)and usingβt=αt\\beta\_\{t\}=\\alpha\_\{t\}gives \([16](https://arxiv.org/html/2609.13439#A1.E16)\)\. Finally,Pr⁡\(ℰinf∩ℰgen\)≥1−δinf−δgen\\Pr\(\\mathcal\{E\}\_\{\\mathrm\{inf\}\}\\cap\\mathcal\{E\}\_\{\\mathrm\{gen\}\}\)\\geq 1\-\\delta\_\{\\mathrm\{inf\}\}\-\\delta\_\{\\mathrm\{gen\}\}\. ∎

#### A\.2\.5Proof of Accuracy under anSS\-Junta Residual

###### Proof of Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9)\.

Consider the eventℰinf\\mathcal\{E\}\_\{\\mathrm\{inf\}\}from Assumption[7](https://arxiv.org/html/2609.13439#Thmtheorem7)\. On this event, together with Assumption[8](https://arxiv.org/html/2609.13439#Thmtheorem8), Lemma[17](https://arxiv.org/html/2609.13439#Thmtheorem17)givesJt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}for every completed stage\. Fix such a stagett, and writest⋆=def\.\|Jt⋆\|≤Ss\_\{t\}^\{\\star\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\|J\_\{t\}^\{\\star\}\|\\leq S\. The residualrtr\_\{t\}depends only on the coordinates inJt⋆J\_\{t\}^\{\\star\}\. Hence there exists a Boolean functiongt⋆:\{0,1\}st⋆→\{0,1\}g\_\{t\}^\{\\star\}:\\\{0,1\\\}^\{s\_\{t\}^\{\\star\}\}\\to\\\{0,1\\\}such thatrt​\(x\)=gt⋆​\(projJt⋆⁡\(x\)\)r\_\{t\}\(x\)=g\_\{t\}^\{\\star\}\(\\operatorname\{proj\}\_\{J\_\{t\}^\{\\star\}\}\(x\)\)for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}\. Thus, the population approximation errorαt\\alpha\_\{t\}in \([15](https://arxiv.org/html/2609.13439#A1.E15)\) is zero\. Moreover, onℰinf\\mathcal\{E\}\_\{\\mathrm\{inf\}\},Jt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}, soβt=αt=0\\beta\_\{t\}=\\alpha\_\{t\}=0\.

To obtain the sharper dependence onst⋆s\_\{t\}^\{\\star\}, let𝒢≤st⋆=def\.⋃J⊆\[B\]\|J\|≤st⋆𝒢J\\mathcal\{G\}\_\{\\leq s\_\{t\}^\{\\star\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\bigcup\_\{\\begin\{subarray\}\{c\}J\\subseteq\[B\]\\\\ \|J\|\\leq s\_\{t\}^\{\\star\}\\end\{subarray\}\}\\mathcal\{G\}\_\{J\}\. As in \([13](https://arxiv.org/html/2609.13439#A1.E13)\),

log⁡\|𝒢≤st⋆\|≤C⁡\(2st⋆\+st⋆​log⁡e​Bst⋆\)\.\\log\|\\mathcal\{G\}\_\{\\leq s\_\{t\}^\{\\star\}\}\|\\leq C\\left\(2^\{s\_\{t\}^\{\\star\}\}\+s\_\{t\}^\{\\star\}\\log\\frac\{eB\}\{s\_\{t\}^\{\\star\}\}\\right\)\.Conditional on the preceding stage batches, the current residual is fixed\. Applying the same finite\-class uniform\-convergence argument as in Theorem[19](https://arxiv.org/html/2609.13439#Thmtheorem19)to𝒢≤st⋆\\mathcal\{G\}\_\{\\leq s\_\{t\}^\{\\star\}\}therefore gives, simultaneously over stages with probability at least1−δgen1\-\\delta\_\{\\mathrm\{gen\}\},

Pr\[Ft\(X\)≠rt\(X\)\]≤Cm⁡\(2st⋆\+st⋆​log⁡e​Bst⋆\+log⁡mδgen\)T\.\\Pr\[F\_\{t\}\(X\)\\neq r\_\{t\}\(X\)\]\\leq C\\sqrt\{\\frac\{m\\left\(2^\{s\_\{t\}^\{\\star\}\}\+s\_\{t\}^\{\\star\}\\log\\frac\{eB\}\{s\_\{t\}^\{\\star\}\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}\.Onℰinf\\mathcal\{E\}\_\{\\mathrm\{inf\}\},Jt=Jt⋆J\_\{t\}=J\_\{t\}^\{\\star\}; therefore, the learned stage predictor indeed belongs to𝒢≤st⋆\\mathcal\{G\}\_\{\\leq s\_\{t\}^\{\\star\}\}\. Finally, the XOR residual identity givesℛ\(Ht\)=Pr\[Ft\(X\)≠rt\(X\)\]\\mathcal\{R\}\(H\_\{t\}\)=\\Pr\[F\_\{t\}\(X\)\\neq r\_\{t\}\(X\)\], and hence

ℛ⁡\(Ht\)≤C​m⁡\(2st⋆\+st⋆​log⁡e​Bst⋆\+log⁡mδgen\)T\.\\mathcal\{R\}\(H\_\{t\}\)\\leq C\\sqrt\{\\frac\{m\\left\(2^\{s\_\{t\}^\{\\star\}\}\+s\_\{t\}^\{\\star\}\\log\\frac\{eB\}\{s\_\{t\}^\{\\star\}\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}\.Sincest⋆≤Ss\_\{t\}^\{\\star\}\\leq S, enlarging the universal constant, if necessary, implies \([5](https://arxiv.org/html/2609.13439#S4.E5)\)\. Combining the influence\-recovery and generalization events gives total probability at least1−δinf−δgen1\-\\delta\_\{\\mathrm\{inf\}\}\-\\delta\_\{\\mathrm\{gen\}\}\. ∎

## Appendix BProofs for the Certifiably Interpretable Neural Realization

This appendix proves the gate identities, the exact circuit\-to\-network compilation, and the transfer of the statistical guarantees from Section[4\.2](https://arxiv.org/html/2609.13439#S4.SS2)\. Auxiliary impossibility results and alternative XOR constructions are given separately in Appendix[F\.3](https://arxiv.org/html/2609.13439#A6.SS3)\.

### B\.1Proof of the Gate\-Realization Proposition

###### Proof of Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)\.

Fixa=\(a1,…,ar\)∈\{0,1\}ra=\(a\_\{1\},\\ldots,a\_\{r\}\)\\in\\\{0,1\\\}^\{r\}and writes=def\.∑j=1raj∈\{0,…,r\}s\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{j=1\}^\{r\}a\_\{j\}\\in\\\{0,\\ldots,r\\\}\.

For NOT, Booleanity givesσ⁡\(1−a1\)=1−a1=¬a1\\sigma\(1\-a\_\{1\}\)=1\-a\_\{1\}=\\neg a\_\{1\}\.

For AND, ifs≤r−1s\\leq r\-1, then boths−r\+1≤0s\-r\+1\\leq 0ands−r<0s\-r<0, soσ⁡\(s−r\+1\)−σ⁡\(s−r\)=0\\sigma\(s\-r\+1\)\-\\sigma\(s\-r\)=0\. Ifs=rs=r, the same difference isσ⁡\(1\)−σ⁡\(0\)=1\\sigma\(1\)\-\\sigma\(0\)=1\. HenceψAND\(r\)\(a\)=𝟙\{s=r\}=⋀j=1raj\\psi\_\{\\mathrm\{AND\}\}^\{\(r\)\}\(a\)=\\mathbbm\{1\}\\\{s=r\\\}=\\bigwedge\_\{j=1\}^\{r\}a\_\{j\}\.

For OR, ifs=0s=0, thenσ⁡\(s\)−σ⁡\(s−1\)=0\\sigma\(s\)\-\\sigma\(s\-1\)=0; ifs≥1s\\geq 1, thenσ⁡\(s\)−σ⁡\(s−1\)=s−\(s−1\)=1\\sigma\(s\)\-\\sigma\(s\-1\)=s\-\(s\-1\)=1\. ThereforeψOR\(r\)\(a\)=𝟙\{s≥1\}=⋁j=1raj\\psi\_\{\\mathrm\{OR\}\}^\{\(r\)\}\(a\)=\\mathbbm\{1\}\\\{s\\geq 1\\\}=\\bigvee\_\{j=1\}^\{r\}a\_\{j\}\.

For XOR, letgr​\(s\)=def\.σ⁡\(s\)\+2​∑k=1r−1\(−1\)k​σ​\(s−k\)g\_\{r\}\(s\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\(s\)\+2\\sum\_\{k=1\}^\{r\-1\}\(\-1\)^\{k\}\\sigma\(s\-k\), fors∈\{0,…,r\}s\\in\\\{0,\\ldots,r\\\}\. Sincessis a nonnegative integer,σ⁡\(s\)=s\\sigma\(s\)=s, andσ⁡\(s−k\)=s−k\\sigma\(s\-k\)=s\-kexactly whenk<sk<s\. Hence

gr​\(s\)=s\+2​∑k=1s−1\(−1\)k​\(s−k\),g\_\{r\}\(s\)=s\+2\\sum\_\{k=1\}^\{s\-1\}\(\-1\)^\{k\}\(s\-k\),where the sum is empty whens∈\{0,1\}s\\in\\\{0,1\\\}\. In particular,gr​\(0\)=0g\_\{r\}\(0\)=0\. We now show thatgr​\(s\)g\_\{r\}\(s\)alternates between00and11\. Fors∈\{0,…,r−1\}s\\in\\\{0,\\ldots,r\-1\\\},

gr​\(s\+1\)−gr​\(s\)\\displaystyle g\_\{r\}\(s\+1\)\-g\_\{r\}\(s\)=1\+2​∑k=1s\(−1\)k=\{1,s​even,−1,s​odd,=\(−1\)s\.\\displaystyle=1\+2\\sum\_\{k=1\}^\{s\}\(\-1\)^\{k\}=\\begin\{cases\}1,&s\\text\{ even\},\\\\ \-1,&s\\text\{ odd\},\\end\{cases\}=\(\-1\)^\{s\}\.Thus, starting fromgr​\(0\)=0g\_\{r\}\(0\)=0, the sequence satisfies

gr\(0\)=0,gr\(1\)=1,gr\(2\)=0,gr\(3\)=1,…,g\_\{r\}\(0\)=0,\\quad g\_\{r\}\(1\)=1,\\quad g\_\{r\}\(2\)=0,\\quad g\_\{r\}\(3\)=1,\\quad\\ldots,and therefore

gr​\(s\)=\{0,s​even,1,s​odd\.g\_\{r\}\(s\)=\\begin\{cases\}0,&s\\text\{ even\},\\\\ 1,&s\\text\{ odd\}\.\\end\{cases\}Sinces=∑j=1rajs=\\sum\_\{j=1\}^\{r\}a\_\{j\}, its parity is exactly⨁j=1raj\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}\. Moreover,gr​\(s\)∈\{0,1\}g\_\{r\}\(s\)\\in\\\{0,1\\\}; thus, the outer ReLU does not change its value\. Consequently,

ψXOR\(r\)​\(a\)=σ⁡\(gr​\(s\)\)=smod2=⨁j=1raj\.\\psi\_\{\\mathrm\{XOR\}\}^\{\(r\)\}\(a\)=\\sigma\(g\_\{r\}\(s\)\)=s\\bmod 2=\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}\.∎

### B\.2Proof of the Exact Neural Realization

###### Proof of Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11)\.

Fixx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}\. We verify the construction layer by layer\.

##### Literal layer\.

For eachj∈\[B\]j\\in\[B\],pj​\(x\)=σ⁡\(xj\)=xjp\_\{j\}\(x\)=\\sigma\(x\_\{j\}\)=x\_\{j\}andnj​\(x\)=σ⁡\(1−xj\)=1−xjn\_\{j\}\(x\)=\\sigma\(1\-x\_\{j\}\)=1\-x\_\{j\}\. Hence the first non\-input layer contains all positive and negated literals and has width2​B2B\.

##### Product\-term layer\.

For stagettand termqq, letst,q​\(x\)=def\.∑ℓ=1Lt,qz^t,q,ℓ​\(x\)s\_\{t,q\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{\\ell=1\}^\{L\_\{t,q\}\}\\widehat\{z\}\_\{t,q,\\ell\}\(x\), where eachz^t,q,ℓ\\widehat\{z\}\_\{t,q,\\ell\}is the corresponding literal signal from the first layer\. By Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10),

Ct,q​\(x\)=σ⁡\(st,q​\(x\)−Lt,q\+1\)−σ⁡\(st,q​\(x\)−Lt,q\)=⋀ℓ=1Lt,qzt,q,ℓ​\(x\)\.C\_\{t,q\}\(x\)=\\sigma\\left\(s\_\{t,q\}\(x\)\-L\_\{t,q\}\+1\\right\)\-\\sigma\\left\(s\_\{t,q\}\(x\)\-L\_\{t,q\}\\right\)=\\bigwedge\_\{\\ell=1\}^\{L\_\{t,q\}\}z\_\{t,q,\\ell\}\(x\)\.There areP=∑t=1MQtP=\\sum\_\{t=1\}^\{M\}Q\_\{t\}product terms, each represented by two ReLU units\. Therefore, this layer has width2​P2P\. The difference definingCt,qC\_\{t,q\}is a linear readout and is absorbed into the affine preactivations of the next layer\.

##### Stage\-output layer\.

For eachtt, setct​\(x\)=def\.∑q=1QtCt,q​\(x\)c\_\{t\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{q=1\}^\{Q\_\{t\}\}C\_\{t,q\}\(x\)\. Since eachCt,q​\(x\)C\_\{t,q\}\(x\)is Boolean, Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)gives

ot\+​\(x\)−ot−​\(x\)=σ⁡\(ct​\(x\)\)−σ⁡\(ct​\(x\)−1\)=⋁q=1QtCt,q​\(x\)=Ft​\(x\)\.o\_\{t\}^\{\+\}\(x\)\-o\_\{t\}^\{\-\}\(x\)=\\sigma\(c\_\{t\}\(x\)\)\-\\sigma\(c\_\{t\}\(x\)\-1\)=\\bigvee\_\{q=1\}^\{Q\_\{t\}\}C\_\{t,q\}\(x\)=F\_\{t\}\(x\)\.Thus this layer has width2​M2M\. Again, the linear differenceFt=ot\+−ot−F\_\{t\}=o\_\{t\}^\{\+\}\-o\_\{t\}^\{\-\}is absorbed into the affine preactivations of the parity layer\.

##### Parity\-feature layer\.

LetsM​\(x\)=def\.∑t=1M\(ot\+​\(x\)−ot−​\(x\)\)=∑t=1MFt​\(x\)∈\{0,…,M\}s\_\{M\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{t=1\}^\{M\}\(o\_\{t\}^\{\+\}\(x\)\-o\_\{t\}^\{\-\}\(x\)\)=\\sum\_\{t=1\}^\{M\}F\_\{t\}\(x\)\\in\\\{0,\\ldots,M\\\}\. The layer containshk​\(x\)=def\.σ⁡\(sM​\(x\)−k\)h\_\{k\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\(s\_\{M\}\(x\)\-k\)fork=0,…,M−1k=0,\\ldots,M\-1, and therefore has widthMM\.

##### Output layer\.

Applying the XOR identity of Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)to the Boolean stage outputs gives

H^M​\(x\)=σ⁡\(h0​\(x\)\+2​∑k=1M−1\(−1\)k​hk​\(x\)\)=⨁t=1MFt​\(x\)=HM​\(x\)\.\\widehat\{H\}\_\{M\}\(x\)=\\sigma\\left\(h\_\{0\}\(x\)\+2\\sum\_\{k=1\}^\{M\-1\}\(\-1\)^\{k\}h\_\{k\}\(x\)\\right\)=\\bigoplus\_\{t=1\}^\{M\}F\_\{t\}\(x\)=H\_\{M\}\(x\)\.On Boolean inputs, the affine combination inside the final ReLU already equals the XOR of the stage outputs and therefore takes values in\{0,1\}\\\{0,1\\\}\. Hence the final ReLU is not required for exact Boolean agreement; it is retained only so that the output is itself produced by a ReLU unit\. Equivalently, the fifth layer may be taken to be a linear output layer without changing the depth or the computed function on\{0,1\}B\\\{0,1\\\}^\{B\}\. Sincexxwas arbitrary,H^M=HM\\widehat\{H\}\_\{M\}=H\_\{M\}on\{0,1\}B\\\{0,1\\\}^\{B\}\. The five non\-input layer widths are therefore\(2​B,2​P,2​M,M,1\)\(2B,2P,2M,M,1\), and the total number of non\-input neurons is2​B\+2​P\+3​M\+12B\+2P\+3M\+1\.

Finally, consider a nonconstant stageGtG\_\{t\}\. After removing duplicate and redundant product terms, each remaining product term uniquely covers at least one input in\{0,1\}\|Jt\|\\\{0,1\\\}^\{\|J\_\{t\}\|\}\. HenceQt≤2\|Jt\|Q\_\{t\}\\leq 2^\{\|J\_\{t\}\|\}\. For the constant\-zero and constant\-one normalizations described above,Qt=1Q\_\{t\}=1andQt=2Q\_\{t\}=2, respectively\. Since every completed stage has\|Jt\|≥1\|J\_\{t\}\|\\geq 1, the same boundQt≤2\|Jt\|Q\_\{t\}\\leq 2^\{\|J\_\{t\}\|\}holds\. Therefore,P=∑t=1MQt≤M​2KP=\\sum\_\{t=1\}^\{M\}Q\_\{t\}\\leq M2^\{K\}, and2​B\+2​P\+3​M\+1=𝒪⁡\(B\+M​2K\)2B\+2P\+3M\+1=\\mathcal\{O\}\(B\+M2^\{K\}\)\.

∎

###### Proof of Corollary[12](https://arxiv.org/html/2609.13439#Thmtheorem12)\.

Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11)givesH^M​\(x\)=HM​\(x\)\\widehat\{H\}\_\{M\}\(x\)=H\_\{M\}\(x\)for everyx∈\{0,1\}Bx\\in\\\{0,1\\\}^\{B\}\. Hence, for any Boolean targetffand any random variableXXsupported on the Boolean cube,

𝟙\{H^M\(X\)≠f\(X\)\}=𝟙\{HM\(X\)≠f\(X\)\}\.\\mathbbm\{1\}\\\{\\widehat\{H\}\_\{M\}\(X\)\\neq f\(X\)\\\}=\\mathbbm\{1\}\\\{H\_\{M\}\(X\)\\neq f\(X\)\\\}\.Taking expectations yieldsℙ⁡\(H^M​\(X\)≠f⁡\(X\)\)=ℙ⁡\(HM​\(X\)≠f⁡\(X\)\)\\mathbb\{P\}\\\!\\left\(\\widehat\{H\}\_\{M\}\(X\)\\neq f\(X\)\\right\)=\\mathbb\{P\}\\\!\\left\(H\_\{M\}\(X\)\\neq f\(X\)\\right\)\. Therefore, every accuracy or generalization guarantee forHMH\_\{M\}transfers unchanged toH^M\\widehat\{H\}\_\{M\}\. ∎

## Appendix CAdditional Details on Espresso Logic Minimization

This appendix provides additional background on theEspressoheuristic introduced in Section[2\.3](https://arxiv.org/html/2609.13439#S2.SS3)\. We first introduce the cover terminology used in the classical description ofEspresso, then summarize its principal operators and the input–output convention used throughout this paper\.

### C\.1Implicants, Prime Implicants, and Covers

Let a partially specified Boolean function onqqvariables be represented by the disjoint partition

\{0,1\}q=FON∪˙FOFF∪˙FDC\.\\\{0,1\\\}^\{q\}=F^\{\\mathrm\{ON\}\}\\mathbin\{\\dot\{\\cup\}\}F^\{\\mathrm\{OFF\}\}\\mathbin\{\\dot\{\\cup\}\}F^\{\\mathrm\{DC\}\}\.A*cube*is a conjunction of literals and represents the subset of\{0,1\}q\\\{0,1\\\}^\{q\}satisfying those literals\. A cubeccis an*implicant*ifc∩FOFF=∅c\\cap F^\{\\mathrm\{OFF\}\}=\\varnothing; equivalently, every point represented bycclies inFON∪FDCF^\{\\mathrm\{ON\}\}\\cup F^\{\\mathrm\{DC\}\}\. An implicant is*prime*if it cannot be strictly enlarged while remaining an implicant\.

A*cover*is a collection of implicants whose union containsFONF^\{\\mathrm\{ON\}\}\. Thus, a cover determines an SOP representation that evaluates to11on every ON\-set entry and to00on every OFF\-set entry\. A prime implicant is*essential*if it contains at least one ON\-set point that is not contained in any other prime implicant\.

Espressobegins from an initial cover, commonly obtained from the ON\-set minterms, and iteratively modifies this cover while maintaining consistency with the specified truth table\([Brayton et al\., 1984](https://arxiv.org/html/2609.13439#bib.bib1);[Rudell and Sangiovanni\-Vincentelli, 2004](https://arxiv.org/html/2609.13439#bib.bib20)\)\.

### C\.2Core Espresso Operations

The classicalEspressoprocedure is organized around three principal operations:Expand,Reduce, andIrredundant\.

##### Expand\.

Given the current cover,Expandenlarges its cubes while preventing them from intersectingFOFFF^\{\\mathrm\{OFF\}\}\. This tends to replace more specific product terms by more general ones and typically moves the corresponding cubes toward prime implicants\.

##### Reduce\.

TheReduceoperation contracts selected cubes while retaining sufficient coverage of the ON\-set\. Its purpose is not necessarily to simplify the current representation immediately, but to allow a subsequentExpandstep to explore alternative enlargements that may lead to a smaller cover\.

##### Irredundant\.

TheIrredundantoperation removes cubes that are unnecessary for covering the ON\-set\. After this step, each remaining cube contributes to the current representation\.

These operations are applied iteratively\. A typical optimization cycle first reduces the current cover, then expands the resulting cubes against the OFF\-set, and finally removes redundant cubes\. The cycle is repeated while improvements in the chosen cover cost are obtained\.

Espressoalso employs auxiliary routines\. TheEssentialsstep identifies cubes that uniquely cover particular ON\-set entries and may retain them separately while the remaining cover is optimized\. After the principal optimization cycle stabilizes,Last\_Gaspapplies a more aggressive reduce–expand perturbation in an attempt to escape the current locally stable representation and obtain a simpler one\.

The resulting procedure is heuristic\. It preserves consistency with the specified ON\- and OFF\-set entries, but it does not guarantee minimization of either the number of product terms or the total number of literal occurrences\.

### C\.3Partial Truth Tables and theEspressoLearnConvention

For a partial truth tableg^:\{0,1\}q→\{0,1,DC\}\\widehat\{g\}:\\\{0,1\\\}^\{q\}\\to\\\{0,1,\\mathrm\{DC\}\\\}, defineFON=def\.\{u:g^​\(u\)=1\}F^\{\\mathrm\{ON\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{u:\\widehat\{g\}\(u\)=1\\\},FOFF=def\.\{u:g^​\(u\)=0\}F^\{\\mathrm\{OFF\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{u:\\widehat\{g\}\(u\)=0\\\}, andFDC=def\.\{u:g^​\(u\)=DC\}F^\{\\mathrm\{DC\}\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\\{u:\\widehat\{g\}\(u\)=\\mathrm\{DC\}\\\}\. These sets form a partition of\{0,1\}q\\\{0,1\\\}^\{q\}\. RunningEspressoon this partially specified function produces a cover𝒞\\mathcal\{C\}satisfying

FON⊆⋃c∈𝒞c,\(⋃c∈𝒞c\)∩FOFF=∅\.F^\{\\mathrm\{ON\}\}\\subseteq\\bigcup\_\{c\\in\\mathcal\{C\}\}c,\\qquad\\left\(\\bigcup\_\{c\\in\\mathcal\{C\}\}c\\right\)\\cap F^\{\\mathrm\{OFF\}\}=\\varnothing\.For anyu∈\{0,1\}qu\\in\\\{0,1\\\}^\{q\}, the corresponding Boolean function isG\(u\)=def\.𝟙\{u∈⋃c∈𝒞c\}G\(u\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\mathbbm\{1\}\\left\\\{u\\in\\bigcup\_\{c\\in\\mathcal\{C\}\}c\\right\\\}\. Consequently,G⁡\(u\)=1G\(u\)=1for everyu∈FONu\\in F^\{\\mathrm\{ON\}\}andG⁡\(u\)=0G\(u\)=0for everyu∈FOFFu\\in F^\{\\mathrm\{OFF\}\}\. No restriction is imposed onG⁡\(u\)G\(u\)foru∈FDCu\\in F^\{\\mathrm\{DC\}\}\. These unconstrained entries allowEspressoto enlarge cubes through unobserved regions of the truth table and thereby obtain a simpler SOP completion\.

Throughout the paper, we use the notationG=EspressoLearn​\(g^\)G=\\textsc\{EspressoLearn\}\(\\widehat\{g\}\)for the Boolean completion returned by this procedure\. The only property required by our learning algorithm and statistical analysis isG​\(u\)=g^​\(u\)G\(u\)=\\widehat\{g\}\(u\)wheneverg^​\(u\)∈\{0,1\}\.\\widehat\{g\}\(u\)\\in\\\{0,1\\\}\.Thus, our results do not rely onEspressofinding a globally minimum representation; they require only a Boolean completion consistent with the specified entries of the partial truth table\.

### C\.4Implementation

In our experiments, we accessEspressothroughPyEDA, which provides a Python interface to the underlying Espresso implementation\. Partial truth tables are encoded using00,11, and don’t\-care symbols, and the resulting minimized expression is returned in sum\-of\-products \(SOP\) form\. We use this expression both as the stage\-wise predictor in Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)and as the logical representation subsequently compiled into the exact ReLU realization of Section[4\.2](https://arxiv.org/html/2609.13439#S4.SS2)\.

SinceEspressois a heuristic logic\-minimization procedure, we do not assume a worst\-case guarantee on the optimality of its returned SOP\. In our method, its computational role is instead governed by its runtime on the lower\-dimensional projected truth tables produced by the training procedure\.

## Appendix DExperimental and Implementation Details

This appendix provides the implementation and reproducibility details for the experiments in Section[5](https://arxiv.org/html/2609.13439#S5)\. We first describe the computing environment, target generation, andEspressointerface\. We then give the implementation details for Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1), the flat\-Espressobaseline, the residual\-stage and coordinate\-selection ablations, and the neural\-network comparison\. Finally, we report additional experimental results for configurations omitted from the corresponding main\-text figures and tables\.

### D\.1Software and Computing Environment

All experiments were conducted on a system running Ubuntu 22\.04\.4 LTS, equipped with an Intel\(R\) Xeon\(R\) CPU at2\.202\.20GHz and1616GB of RAM\. The experiments were implemented in Python\. Boolean truth\-table minimization was performed using thePyEDAinterface toEspresso, and the neural\-network experiments were implemented in PyTorch\.

Runtime was measured as elapsed wall\-clock time\. For Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1), training time includes residual computation, influence estimation, coordinate selection, construction of the projected partial truth table, and theEspressocall at every completed stage\. For Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2), the reported runtime additionally includes construction of the exact neural parameters\. Test\-set evaluation is excluded from all reported training and construction times\. For the trainable MLPs, runtime includes gradient\-based training and excludes test evaluation\.

### D\.2Generation of Random Junta Targets

For each seed, anSS\-junta target is generated in two steps\. First, a generating coordinate setJ⋆⊆\[B\]J^\{\\star\}\\subseteq\[B\]of cardinalitySSis sampled uniformly without replacement\. Second, the values of a Boolean functiong⋆:\{0,1\}S→\{0,1\}g^\{\\star\}:\\\{0,1\\\}^\{S\}\\to\\\{0,1\\\}are sampled independently fromBernoulli⁡\(1/2\)\\operatorname\{Bernoulli\}\(1/2\)\. The ambient target is then defined byf⁡\(x\)=g⋆​\(projJ⋆⁡\(x\)\)f\(x\)=g^\{\\star\}\\bigl\(\\operatorname\{proj\}\_\{J^\{\\star\}\}\(x\)\\bigr\)\.

This procedure generates a random Boolean function depending only on the sampled coordinates\. It does not explicitly condition on every sampled coordinate being relevant; consequently, the realized effective dimension may occasionally be smaller thanSS\.

Training inputs are sampled uniformly without replacement from\{0,1\}B\\\{0,1\\\}^\{B\}\. Sampled test inputs are generated independently in the same manner\. When full\-cube evaluation is used, the test set contains all2B2^\{B\}Boolean inputs\. Within each seed, every compared method uses exactly the same target function, training set, and test set\.

The eleven configurations used throughout the experiments are summarized in Table[1](https://arxiv.org/html/2609.13439#S5.T1)\. Their ordering is chosen to group qualitatively similar regimes\. Configs\. 1–5 are settings in which flatEspressoattains higher predictive accuracy than the proposed method, Configs\. 6–9 are settings in which the proposed structural dimension reduction is beneficial, and Configs\. 10–11 are large\-scale full\-cube training settings in which flatEspressofails to return within the computational budget\.

### D\.3EspressothroughPyEDA

A partial truth table overqqvariables is represented by a string of length2q2^\{q\}with entries in\{0,1,\-\}\\\{0,1,\\texttt\{\-\}\\\}, where00and11denote specified outputs and\-denotes a don’t\-care\. We construct the correspondingPyEDAtruth\-table object and callespresso\_tts, which invokes the underlyingEspressominimizer and returns a simplified Boolean expression\.

PyEDAacts only as an interface to the compiledEspressoimplementation; the minimization itself is not performed in Python\. Moreover, the interface does not expose a native mechanism for returning the best intermediate cover after a prescribed time limit\. Consequently, an ambient\-dimensional call may remain insideEspressofor an extended period without returning a partial solution\. We therefore impose a fixed three\-hour computational budget on each flat\-baseline call; runs that do not terminate within this budget are recorded as timeouts\.

Degenerate projected truth tables are handled before invokingEspresso\. If all specified entries equal zero, we return the constant\-zero function, while if all specified entries equal one, we return the constant\-one function\. An all\-don’t\-care table is assigned the constant\-zero completion\. These conventions avoid implementation\-dependent behavior on constant or completely unspecified tables\.

### D\.4Implementation of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)

Inputs are represented as integers in\{0,…,2B−1\}\\\{0,\\ldots,2^\{B\}\-1\\\}, with individual coordinates accessed using bit operations\. Projection ontoJ=\{j1,…,jk\}J=\\\{j\_\{1\},\\ldots,j\_\{k\}\\\}is implemented by packing the selected coordinates into an integer in\{0,…,2k−1\}\\\{0,\\ldots,2^\{k\}\-1\\\}\.

Because all experimental training inputs are sampled without replacement, they are distinct, soDtrainXD\_\{\\mathrm\{train\}\}^\{X\}contains exactly the observed training inputs\. Thus, the set\-based implementation below coincides with Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\.

For each coordinatei∈\[B\]i\\in\[B\], the implementation precomputes the observedii\-edge set

𝒫i=\{x∈DtrainX:xi=0,x⊕i∈DtrainX\}\.\\mathcal\{P\}\_\{i\}=\\left\\\{x\\in D\_\{\\mathrm\{train\}\}^\{X\}:x\_\{i\}=0,\\;x^\{\\oplus i\}\\in D\_\{\\mathrm\{train\}\}^\{X\}\\right\\\}\.The restrictionxi=0x\_\{i\}=0ensures that each undirected Hamming\-neighbor pair is counted once\. These sets depend only on the observed input assignments and are therefore computed once before the stage\-wise residual iterations\. At stagett, residual labels are evaluated on the observed training inputs asrt​\(x\)=f⁡\(x\)⊕Ht−1​\(x\)r\_\{t\}\(x\)=f\(x\)\\oplus H\_\{t\-1\}\(x\)\. For each coordinateii, the empirical residual influence is then

Inf^i​\(rt\)=\{1\|𝒫i\|∑x∈𝒫i𝟙\{rt\(x\)≠rt\(x⊕i\)\},\|𝒫i\|\>0,0,\|𝒫i\|=0\.\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)=\\begin\{cases\}\\displaystyle\\frac\{1\}\{\|\\mathcal\{P\}\_\{i\}\|\}\\sum\_\{x\\in\\mathcal\{P\}\_\{i\}\}\\mathbbm\{1\}\\left\\\{r\_\{t\}\(x\)\\neq r\_\{t\}\(x^\{\\oplus i\}\)\\right\\\},&\|\\mathcal\{P\}\_\{i\}\|\>0,\\\\\[10\.00002pt\] 0,&\|\\mathcal\{P\}\_\{i\}\|=0\.\\end\{cases\}
All experiments useτ=0\\tau=0\. Under this choice, every coordinate with strictly positive empirical residual influence is eligible for selection\. In principle, one could instead chooseτ\>0\\tau\>0when prior structural information suggests that every relevant coordinate has population influence bounded below by some positive level, thereby screening out coordinates whose estimated influence is too small to be considered meaningful\. We useτ=0\\tau=0to avoid introducing an additional threshold hyperparameter and to isolate the effect of influence ranking and the projection budgetKK\.

The active set isCt=\{i∈\[B\]:Inf^i​\(rt\)\>0\}C\_\{t\}=\\left\\\{i\\in\[B\]:\\widehat\{\\operatorname\{Inf\}\}\_\{i\}\(r\_\{t\}\)\>0\\right\\\}\. IfCt≠∅C\_\{t\}\\neq\\varnothing, the implementation selects\|Jt\|=min⁡\{K,\|Ct\|\}\|J\_\{t\}\|=\\min\\\{K,\|C\_\{t\}\|\\\}coordinates with the largest empirical residual influences\. Ties between coordinates with equal empirical influence are broken by increasing coordinate index, making the tie\-breaking deterministic and reproducible across repeated runs\.

OnceJtJ\_\{t\}has been selected, the residual observations are grouped by their projections ontoJtJ\_\{t\}\. For everyu∈\{0,1\}\|Jt\|u\\in\\\{0,1\\\}^\{\|J\_\{t\}\|\}, the implementation computes

Nt,a\(u\)=\|\{x∈DtrainX:projJt\(x\)=u,rt\(x\)=a\}\|,a∈\{0,1\}\.N\_\{t,a\}\(u\)=\\left\|\\left\\\{x\\in D\_\{\\mathrm\{train\}\}^\{X\}:\\operatorname\{proj\}\_\{J\_\{t\}\}\(x\)=u,\\;r\_\{t\}\(x\)=a\\right\\\}\\right\|,\\qquad a\\in\\\{0,1\\\}\.A strict empirical majority determines the specified residual label\. IfNt,0​\(u\)=Nt,1​\(u\)N\_\{t,0\}\(u\)=N\_\{t,1\}\(u\), the projected cell is marked as a don’t\-care\. In particular, an unobserved projected pattern hasNt,0​\(u\)=Nt,1​\(u\)=0N\_\{t,0\}\(u\)=N\_\{t,1\}\(u\)=0and is therefore also a don’t\-care\. This implements Equation \([1](https://arxiv.org/html/2609.13439#S3.E1)\) exactly; no random label is assigned to a tied projected cell\.

The resulting projected partial truth table contains at most2K2^\{K\}entries and is passed toEspresso\. Stage predictions are cached over the projected cube after eachEspressocall\. The accumulated predictor is evaluated asHt​\(x\)=⨁s=1tFs​\(x\)H\_\{t\}\(x\)=\\bigoplus\_\{s=1\}^\{t\}F\_\{s\}\(x\)\. The reported runtime at stagettis cumulative over all stages completed up to that point\.

##### Stage budget and early stopping\.

All residual experiments use a maximum stage budget ofm=20m=20\. Using a common maximum stage index permits direct comparison across configurations and produces comparable stage\-wise curves\. We nevertheless retain the stopping conditions of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\. If the residual vanishes on all observed training inputs orCt=∅C\_\{t\}=\\varnothing, the algorithm terminates and no additionalEspressocorrections are fitted\.

For reporting results at a later common stage index, the terminal predictor is carried forward unchanged\. More precisely, if training stops afterTstop<20T\_\{\\mathrm\{stop\}\}<20completed stages, then for reporting purposes we set

Ht=def\.HTstop,t=Tstop\+1,…,20\.H\_\{t\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}H\_\{T\_\{\\mathrm\{stop\}\}\},\\qquad t=T\_\{\\mathrm\{stop\}\}\+1,\\ldots,20\.Thus, a reported “stage\-20” accuracy does not imply that twenty nontrivial corrections were necessarily learned\. This convention preserves the algorithm’s stopping rule while allowing every configuration to be compared at the same reported stage indices\.

### D\.5FlatEspressoBaseline

The flat baseline allocates an ambient truth table of length2B2^\{B\}\. Every entry is initially marked as a don’t\-care, after which the observed training labels are inserted at their corresponding indices\. The resultingBB\-variable partial truth table is passed toespresso\_ttsin a single call\.

This baseline givesEspressoaccess to every ambient coordinate and therefore does not incur the projection restriction imposed byKK\. Its principal limitation is the explicit ambient representation: allocating the partial truth table already requiresΘ⁡\(2B\)\\Theta\(2^\{B\}\)entries before the cost of logic minimization itself is considered\. This implementation matches the full\-dimensional baseline discussed in Section[5\.1](https://arxiv.org/html/2609.13439#S5.SS1)\.

If a flat\-Espressorun did not complete within three hours, it was terminated and recorded as “Failed\.” SincePyEDAdoes not expose an intermediate valid cover from the runningEspressoprocess, such a run produces neither an accuracy value nor a partial predictor\.

### D\.6Residual\-Stage Ablation

The residual\-stage experiment evaluates a single execution of Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)at successive stage indices\. Thus, the stage\-one, stage\-five, and stage\-twenty values reported in Table[2](https://arxiv.org/html/2609.13439#S5.T2)are points along the same residual\-learning sequence rather than results from independently retrained models\.

For the stage\-wise curves, test accuracy is recorded after every reported staget=1,…,20t=1,\\ldots,20\. If the algorithm terminates before stage2020, the terminal predictor is carried forward as described in Appendix[D\.4](https://arxiv.org/html/2609.13439#A4.SS4)\.

Ifμ^t\\widehat\{\\mu\}\_\{t\}ands^t\\widehat\{s\}\_\{t\}denote the sample mean and sample standard deviation of test accuracy acrossn=20n=20seeds, the shaded region in the corresponding figures is the95%95\\%confidence interval for the meanμ^t±t0\.025,19​s^t20\\widehat\{\\mu\}\_\{t\}\\pm t\_\{0\.025,19\}\\frac\{\\widehat\{s\}\_\{t\}\}\{\\sqrt\{20\}\}, wheret0\.025,19≈2\.093t\_\{0\.025,19\}\\approx 2\.093is the upper\-tail critical value of the Student’stt\-distribution with1919degrees of freedom \(Pr⁡\(T19\>t0\.025,19\)=0\.025\\Pr\(T\_\{19\}\>t\_\{0\.025,19\}\)=0\.025\)\. We use the Student’stt\-interval because the across\-seed population variance is unknown and is estimated by the sample variancest2^\\widehat\{\{s\_\{t\}\}^\{2\}\}\. These confidence intervals quantify uncertainty in the estimated mean across randomly generated targets and datasets and should be distinguished from the standard deviations reported in the tables\.

### D\.7Random\-KKCoordinate\-Selection Ablation

The random\-KKablation isolates the contribution of the influence\-ranking step\. It retains the residual computation, projected empirical majority,Espressominimization, XOR aggregation, residual\-zero stopping rule, and maximum stage budget\. The only change is the coordinate\-selection rule\. At each completed stage, the random\-KKmethod samplesmin⁡\{K,B\}\\min\\\{K,B\\\}distinct coordinates uniformly without replacement from\[B\]\[B\], independently of their empirical influence values\. Thus, unlike the proposed method, the ablation does not useCtC\_\{t\}or the influence ranking to restrict the stage projection\.

Separate random\-number generators are used for the influence\-based and random\-KKprocedures so that internal random choices in one method do not affect those in the other\. For each seed, both methods nevertheless use the same target function, training set, and test set\.

The purpose of this ablation is to test the inductive bias introduced by residual influence selection\. Both methods restrict every stage to a low\-dimensional projection; the difference is whether that projection is directed toward coordinates exhibiting large empirical residual sensitivity or chosen without reference to the residual structure\.

### D\.8Exact ReLU Construction and Trainable MLPs

The circuit\-derived neural network is constructed deterministically from the stage functions learned by Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)\. Its predictions are numerically checked against those of the Boolean predictor on Boolean test inputs\. By Theorem[11](https://arxiv.org/html/2609.13439#Thmtheorem11), the two predictors agree exactly on\{0,1\}B\\\{0,1\\\}^\{B\}, up to floating\-point evaluation error\.

For each seed, the trainable ReLU and sigmoid baselines use the same number of hidden layers and the same hidden\-layer widths as the corresponding exact network produced for that seed\. Their parameters are initialized randomly and optimized using Adam\. The training loss is binary cross\-entropy, implemented using logits:

L^​\(θ\)=1T​∑i=1T\[−yi​log⁡ρθ​\(Xi\)−\(1−yi\)​log⁡\(1−ρθ​\(Xi\)\)\],\\widehat\{L\}\(\\theta\)=\\frac\{1\}\{T\}\\sum\_\{i=1\}^\{T\}\\left\[\-y\_\{i\}\\log\\rho\_\{\\theta\}\(X\_\{i\}\)\-\(1\-y\_\{i\}\)\\log\\bigl\(1\-\\rho\_\{\\theta\}\(X\_\{i\}\)\\bigr\)\\right\],whereρθ​\(x\)=11\+exp⁡\(−zθ​\(x\)\)\\rho\_\{\\theta\}\(x\)=\\frac\{1\}\{1\+\\exp\(\-z\_\{\\theta\}\(x\)\)\}andzθ​\(x\)z\_\{\\theta\}\(x\)denotes the scalar output logit\. The learning rate is10−310^\{\-3\}, the batch size is256256, and no weight decay is used\. Training examples are randomly permuted at every epoch\. At evaluation time, the predicted label is𝟙\{ρθ\(x\)≥12\}\\mathbbm\{1\}\\\{\\rho\_\{\\theta\}\(x\)\\geq\\frac\{1\}\{2\}\\\}\.

The trainable networks are run for10001000epochs in Configs\. 1–9\. Configs\. 10–11 use full\-cube training sets and therefore require a different interpretation of an epoch\. The number of gradient updates per epoch is approximately⌈T/256⌉\\left\\lceil T/256\\right\\rceil\.

For example, one epoch in Config\. 10, whereT=220T=2^\{20\}, contains220256=4096\\frac\{2^\{20\}\}\{256\}=4096Adam updates\. By comparison,10001000epochs withT=1000T=1000and the same batch size contain approximately1000​⌈1000256⌉=40001000\\left\\lceil\\frac\{1000\}\{256\}\\right\\rceil=4000updates\. Similarly, one epoch withT=221T=2^\{21\}contains81928192updates\. Thus, a single full\-cube epoch already performs thousands of parameter updates and should not be interpreted as comparable to a single epoch in the smaller\-data configurations\.

We therefore use one full\-cube epoch for Configs\. 10–11\. This choice keeps the gradient\-update budget within the same broad scale as the long small\-sample training runs while avoiding a prohibitively large optimization budget created solely by measuring training length in epochs\. The comparison is not intended to enforce an exactly identical number of gradient updates across every configuration; rather, the large discrepancy in examples per epoch makes a fixed epoch count across allTTinappropriate\. The number of epochs is therefore reported explicitly whenever neural\-network results are presented\.

For the exact method, runtime includes both Algorithm[1](https://arxiv.org/html/2609.13439#algorithm1)and the deterministic circuit\-to\-network compilation\. For the trainable neural baselines, runtime includes gradient\-based optimization and excludes test evaluation\.

### D\.9Reproducibility and Reported Statistics

Unless otherwise stated, the experiments use seeds0,…,190,\\ldots,19\. For a reported quantityZ1,…,Z20Z\_\{1\},\\ldots,Z\_\{20\}, the tables displayZ¯±sZ\\overline\{Z\}\\pm s\_\{Z\}, whereZ¯=120​∑i=120Zi\\overline\{Z\}=\\frac\{1\}\{20\}\\sum\_\{i=1\}^\{20\}Z\_\{i\}and

sZ=119​∑i=120\(Zi−Z¯\)2s\_\{Z\}=\\sqrt\{\\frac\{1\}\{19\}\\sum\_\{i=1\}^\{20\}\\left\(Z\_\{i\}\-\\overline\{Z\}\\right\)^\{2\}\}is the sample standard deviation\. Thus, the table entries describe variability across randomly generated junta targets and datasets; they are not confidence intervals\. Confidence intervals are used only for the stage\-wise curves, as described in Appendix[D\.6](https://arxiv.org/html/2609.13439#A4.SS6)\.

## Appendix EComplementary Experimental Results

The main text retains representative results for the residual\-stage and coordinate\-selection experiments to keep Section[5](https://arxiv.org/html/2609.13439#S5)compact\. This section reports the corresponding results for the remaining configurations\. The configuration numbering is identical to Table[1](https://arxiv.org/html/2609.13439#S5.T1)\.

### E\.1Residual\-Stage Results for All Configurations

Figure[2](https://arxiv.org/html/2609.13439#S5.F2)in the main text displays representative stage\-wise trajectories, while the remaining configurations are shown below for completeness\. Configs\. 2–4 and 6 exhibit rapid improvements during the first few residual stages followed by a plateau, whereas Configs\. 9 and 11 improve more gradually over a larger number of stages\. Configs\. 5 and 8 remain essentially unchanged, although for different reasons: Config\. 8 achieves near\-perfect accuracy from the first stage despite using relatively few training samples\. Config\. 5 operates in a more challenging regime with relatively few training samples compared with the size of the ambient Boolean cube, which may limit the ability of later stages to identify and correct the remaining residual structure\. Config\. 7 improves only at the first additional stage and then stabilizes\. Overall, these trajectories show that additional residual stages are most useful when meaningful residual structure remains to be captured; once that structure has been largely exhausted, further stages provide little or no improvement\.

\(a\)Config\. 2\.\(b\)Config\. 3\.
Figure 3:Test accuracy across residual stages for Configs\. 2–3\. Curves show the mean over2020seeds and shaded regions show95%95\\%confidence intervals for the mean\.\(a\)Config\. 4\.\(b\)Config\. 5\.
Figure 4:Test accuracy across residual stages for Configs\. 4–5\. Curves show the mean over2020seeds and shaded regions show95%95\\%confidence intervals for the mean\.\(a\)Config\. 6\.\(b\)Config\. 7\.
Figure 5:Test accuracy across residual stages for Configs\. 6–7\. Curves show the mean over2020seeds and shaded regions show95%95\\%confidence intervals for the mean\.\(a\)Config\. 8\.\(b\)Config\. 9\.
Figure 6:Test accuracy across residual stages for Configs\. 8–9\. Curves show the mean over2020seeds and shaded regions show95%95\\%confidence intervals for the mean\.\(a\)Config\. 11\.Figure 7:Test accuracy across residual stages for Config\. 11\. The curve shows the mean over2020seeds and the shaded region shows the95%95\\%confidence interval for the mean\.
### E\.2Influence Selection versus Random Selection: Additional Configurations

Table[4](https://arxiv.org/html/2609.13439#S5.T4)in the main text reports three representative configurations from the influence\-selection ablation\. Table[6](https://arxiv.org/html/2609.13439#A5.T6)provides the corresponding results for the remaining configurations\. The same qualitative accuracy trend persists: influence\-based selection achieves higher mean test accuracy in every configuration, whereas the relative runtime varies across settings\.

Table 6:Influence\-selection ablation for the remaining configurations at the stage\-2020reporting point\. Results are mean±\\pmstandard deviation over2020seeds\. Boldface denotes the better value within each configuration and metric\.

## Appendix FAuxiliary Results

This appendix collects extensions and refinements of the statistical results in Section[4\.1](https://arxiv.org/html/2609.13439#S4.SS1)\. These results are not required for the proofs of the main theorems\. We first record a refined counting bound for juntas whose relevant coordinates have nonnegligible influence\. We then extend the influence\-recovery and prediction guarantees from the uniform Boolean cube to a general input distribution\.

### F\.1Refined Counting for Influential Juntas

The cardinality bound in Lemma[15](https://arxiv.org/html/2609.13439#Thmtheorem15)treats allSS\-juntas equally\. A more refined count is possible when every relevant coordinate is required to have influence bounded away from zero\. Forρ∈\(0,1\]\\rho\\in\(0,1\], define

𝒥B,S,ρinf=def\.\{h:\{0,1\}B→\{0,1\}:\|Rel\(h\)\|≤S,Infi\(h\)≥ρfor everyi∈Rel\(h\)\}\.\\mathcal\{J\}^\{\\mathrm\{inf\}\}\_\{B,S,\\rho\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\\\{h:\\\{0,1\\\}^\{B\}\\to\\\{0,1\\\}:\|\\operatorname\{Rel\}\(h\)\|\\leq S,\\,\\operatorname\{Inf\}\_\{i\}\(h\)\\geq\\rho\\ \\text\{for every \}i\\in\\operatorname\{Rel\}\(h\)\\right\\\}\.
###### Proposition 21\(Counting influential juntas\)\.

For eachs∈\[S\]s\\in\[S\], letns=def\.2s−1n\_\{s\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}2^\{s\-1\}andqρ,s=def\.⌈ρ​ns⌉q\_\{\\rho,s\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\lceil\\rho n\_\{s\}\\rceil; then

\|𝒥B,S,ρinf\|\\displaystyle\|\\mathcal\{J\}^\{\\mathrm\{inf\}\}\_\{B,S,\\rho\}\|≤2\+∑s=1S\(Bs\)⁡\[22s−2ns​∑k=0qρ,s−1\(nsk\)\],\\displaystyle\\leq 2\+\\sum\_\{s=1\}^\{S\}\\binom\{B\}\{s\}\\left\[2^\{2^\{s\}\}\-2^\{n\_\{s\}\}\\sum\_\{k=0\}^\{q\_\{\\rho,s\}\-1\}\\binom\{n\_\{s\}\}\{k\}\\right\],\(17\)\|𝒥B,S,ρinf\|\\displaystyle\|\\mathcal\{J\}^\{\\mathrm\{inf\}\}\_\{B,S,\\rho\}\|≥2\+∑s=1S\(Bs\)​\[22s−s​2ns​∑k=0qρ,s−1\(nsk\)\]\+,\\displaystyle\\geq 2\+\\sum\_\{s=1\}^\{S\}\\binom\{B\}\{s\}\\left\[2^\{2^\{s\}\}\-s\\,2^\{n\_\{s\}\}\\sum\_\{k=0\}^\{q\_\{\\rho,s\}\-1\}\\binom\{n\_\{s\}\}\{k\}\\right\]\_\{\+\},\(18\)where\[a\]\+=def\.max⁡\{a,0\}\[a\]\_\{\+\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\max\\\{a,0\\\}\.

###### Proof\.

We decompose the class according to the number of relevant coordinates\. There are exactly two functions with no relevant coordinates, namely the two constant Boolean functions\. Now fixs∈\[S\]s\\in\[S\]and a relevant\-coordinate setJ⊆\[B\]J\\subseteq\[B\]with\|J\|=s\|J\|=s\. Functions with relevant\-coordinate setJJmay be identified with Boolean functions on\{0,1\}s\\\{0,1\\\}^\{s\}that have influence at leastρ\\rhoin every coordinate\. Sinceρ\>0\\rho\>0, this condition itself guarantees that every coordinate inJJis relevant\.

Fixj∈\[s\]j\\in\[s\]\. Thess\-dimensional Boolean cube containsns=2s−1n\_\{s\}=2^\{s\-1\}disjointjj\-edges, where ajj\-edge is a pair\{x,x⊕j\}\\\{x,x^\{\\oplus j\}\\\}\. We call such an edge*bichromatic*ifh⁡\(x\)≠h⁡\(x⊕j\)h\(x\)\\neq h\(x^\{\\oplus j\}\)\. If exactlykkof thejj\-edges are bichromatic, thenInfj⁡\(h\)=kns\\operatorname\{Inf\}\_\{j\}\(h\)=\\frac\{k\}\{n\_\{s\}\}\.

There are\(nsk\)\\binom\{n\_\{s\}\}\{k\}ways to choose the bichromatic edges\. Once these edges are selected, one endpoint value may be chosen freely on each edge, after which the other endpoint is determined by whether that edge is monochromatic or bichromatic\. Hence, the number of functions having exactlykkbichromaticjj\-edges is2ns​\(nsk\)2^\{n\_\{s\}\}\\binom\{n\_\{s\}\}\{k\}\.

It follows that the number satisfyingInfj⁡\(h\)<ρ\\operatorname\{Inf\}\_\{j\}\(h\)<\\rhois

2ns​∑k=0qρ,s−1\(nsk\)\.2^\{n\_\{s\}\}\\sum\_\{k=0\}^\{q\_\{\\rho,s\}\-1\}\\binom\{n\_\{s\}\}\{k\}\.
Requiring allsscoordinate influences to be at leastρ\\rhoexcludes the union of these low\-influence events\. Excluding the event for a single coordinate gives the upper bound

22s−2ns​∑k=0qρ,s−1\(nsk\),2^\{2^\{s\}\}\-2^\{n\_\{s\}\}\\sum\_\{k=0\}^\{q\_\{\\rho,s\}\-1\}\\binom\{n\_\{s\}\}\{k\},while a union bound over thesscoordinates gives the lower bound

\[22s−s​2ns​∑k=0qρ,s−1\(nsk\)\]\+\.\\left\[2^\{2^\{s\}\}\-s\\,2^\{n\_\{s\}\}\\sum\_\{k=0\}^\{q\_\{\\rho,s\}\-1\}\\binom\{n\_\{s\}\}\{k\}\\right\]\_\{\+\}\.There are\(Bs\)\\binom\{B\}\{s\}possible supports of sizess\. Summing overs=1,…,Ss=1,\\ldots,Sand adding the two constant functions proves the result\. ∎

### F\.2Extension to General Input Distributions

The main text measures both influence and prediction error under the uniform distribution on the Boolean cube\. We now show that the same analysis extends to an arbitrary probability distributionμ∈𝒫⁡\(\{0,1\}B\)\\mu\\in\\mathcal\{P\}\(\\\{0,1\\\}^\{B\}\)\. Recall from Definition[5](https://arxiv.org/html/2609.13439#Thmtheorem5)thatInfiμ\(h\)=def\.PrX∼μ\[h\(X\)≠h\(X⊕i\)\]\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\Pr\_\{X\\sim\\mu\}\\\!\\left\[h\(X\)\\neq h\(X^\{\\oplus i\}\)\\right\]\. In the paired\-sampling model, draw independentlyXn∼μX\_\{n\}\\sim\\muandIn∼Unif⁡\(\[B\]\)I\_\{n\}\\sim\\operatorname\{Unif\}\(\[B\]\), and letMi=def\.∑n=1N𝟙\{In=i\}M\_\{i\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{n=1\}^\{N\}\\mathbbm\{1\}\\\{I\_\{n\}=i\\\}\. IfMi\>0M\_\{i\}\>0, define

Inf^iμ,pair\(h\)=def\.1Mi∑n:In=i\{h\(Xn\)≠h\(Xn⊕i\)\}\.\\widehat\{\\operatorname\{Inf\}\}\_\{i\}^\{\\mu,\\mathrm\{pair\}\}\(h\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\frac\{1\}\{M\_\{i\}\}\\sum\_\{n:I\_\{n\}=i\}\\mathbbm\{1\}\\\!\\left\\\{h\(X\_\{n\}\)\\neq h\(X\_\{n\}^\{\\oplus i\}\)\\right\\\}\.IfMi=0M\_\{i\}=0, setInf^iμ,pair​\(h\)=def\.0\\widehat\{\\operatorname\{Inf\}\}\_\{i\}^\{\\mu,\\mathrm\{pair\}\}\(h\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}0\.

###### Corollary 22\(Simultaneous recovery ofμ\\mu\-influences\)\.

Letℋ\\mathcal\{H\}denote a finite Boolean function class, and letε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\)\. There exists a universal constantC\>0C\>0such that

N≥C​Bε2​\(log⁡\|ℋ\|\+log⁡2​Bδ\)N\\geq C\\frac\{B\}\{\\varepsilon^\{2\}\}\\left\(\\log\|\\mathcal\{H\}\|\+\\log\\frac\{2B\}\{\\delta\}\\right\)implies, with probability at least1−δ1\-\\delta,

max⁡suph∈ℋi∈\[B\]⁡\|Inf^iμ,pair​\(h\)−Infiμ⁡\(h\)\|≤ε\.\\max\_\{i\\in\[B\]\}\\sup\_\{h\\in\\mathcal\{H\}\}\\left\|\\widehat\{\\operatorname\{Inf\}\}\_\{i\}^\{\\mu,\\mathrm\{pair\}\}\(h\)\-\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)\\right\|\\leq\\varepsilon\.

###### Proof\.

Conditional onIn=iI\_\{n\}=i, the variablesXnX\_\{n\}are independent draws fromμ\\mu, and

𝔼X∼μ\[𝟙\{h\(X\)≠h\(X⊕i\)\}\]=Infiμ\(h\)\.\\mathbb\{E\}\_\{X\\sim\\mu\}\\left\[\\mathbbm\{1\}\\\{h\(X\)\\neq h\(X^\{\\oplus i\}\)\\\}\\right\]=\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)\.The proof of Theorem[14](https://arxiv.org/html/2609.13439#Thmtheorem14)therefore applies unchanged\. The occupancy argument concerns only the coordinate indicesInI\_\{n\}, while Hoeffding’s inequality and the finite\-class union bound are distribution\-free\. ∎

Combining Corollary[22](https://arxiv.org/html/2609.13439#Thmtheorem22)with Lemma[15](https://arxiv.org/html/2609.13439#Thmtheorem15)gives the correspondingSS\-junta bound:

N≥C​Bε2​\(2S\+S​log⁡e​BS\+log⁡2​Bδ\)N\\geq C\\frac\{B\}\{\\varepsilon^\{2\}\}\\left\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\+\\log\\frac\{2B\}\{\\delta\}\\right\)is sufficient for simultaneous recovery of allμ\\mu\-influences uniformly over𝒥B,S\\mathcal\{J\}\_\{B,S\}\. The remaining statistical arguments extend in the same manner\. Define

Ct,μ⋆=def\.\{i∈\[B\]:Infiμ⁡\(rt\)\>τ\},st,μ⋆=def\.min⁡\{K,\|Ct,μ⋆\|\},C\_\{t,\\mu\}^\{\\star\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\left\\\{i\\in\[B\]:\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(r\_\{t\}\)\>\\tau\\right\\\},\\qquad s\_\{t,\\mu\}^\{\\star\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\min\\\{K,\|C\_\{t,\\mu\}^\{\\star\}\|\\\},and letJt,μ⋆⊆Ct,μ⋆J\_\{t,\\mu\}^\{\\star\}\\subseteq C\_\{t,\\mu\}^\{\\star\}contain thest,μ⋆s\_\{t,\\mu\}^\{\\star\}coordinates with the largestμ\\mu\-influences\. Assume theμ\\mu\-analogue of Assumption[7](https://arxiv.org/html/2609.13439#Thmtheorem7)\. For coordinate recovery, assume additionally that, for every completed stagett,

mini∈Jt,μ⋆⁡Infiμ⁡\(rt\)\>τ\+εinf\.\\min\_\{i\\in J\_\{t,\\mu\}^\{\\star\}\}\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(r\_\{t\}\)\>\\tau\+\\varepsilon\_\{\\mathrm\{inf\}\}\.If\|Ct,μ⋆\|≤K\|C\_\{t,\\mu\}^\{\\star\}\|\\leq K, require, for everyj∉Ct,μ⋆j\\notin C\_\{t,\\mu\}^\{\\star\},

Infjμ⁡\(rt\)=0orInfjμ⁡\(rt\)<τ−εinf\.\\operatorname\{Inf\}\_\{j\}^\{\\mu\}\(r\_\{t\}\)=0\\qquad\\text\{or\}\\qquad\\operatorname\{Inf\}\_\{j\}^\{\\mu\}\(r\_\{t\}\)<\\tau\-\\varepsilon\_\{\\mathrm\{inf\}\}\.If\|Ct,μ⋆\|\>K\|C\_\{t,\\mu\}^\{\\star\}\|\>K, require

mini∈Jt,μ⋆⁡Infiμ⁡\(rt\)−maxj∈Ct,μ⋆∖Jt,μ⋆⁡Infjμ⁡\(rt\)\>2​εinf\.\\min\_\{i\\in J\_\{t,\\mu\}^\{\\star\}\}\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(r\_\{t\}\)\-\\max\_\{j\\in C\_\{t,\\mu\}^\{\\star\}\\setminus J\_\{t,\\mu\}^\{\\star\}\}\\operatorname\{Inf\}\_\{j\}^\{\\mu\}\(r\_\{t\}\)\>2\\varepsilon\_\{\\mathrm\{inf\}\}\.
The pairedμ\\mu\-influence estimator also preserves zero influence: ifInfiμ⁡\(h\)=0\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)=0, thenInf^iμ,pair​\(h\)=0\\widehat\{\\operatorname\{Inf\}\}\_\{i\}^\{\\mu,\\mathrm\{pair\}\}\(h\)=0almost surely\. Indeed, each disagreement indicator is nonnegative and has expectationInfiμ⁡\(h\)=0\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)=0, and hence equals zero almost surely\. Hence, on a probability\-one event, the proof of Lemma[17](https://arxiv.org/html/2609.13439#Thmtheorem17)carries over after replacing uniform influences byμ\\mu\-influences, without changing the stated failure probabilities\.

For each stage define

αt,μ=def\.infg:\{0,1\}\|Jt,μ⋆\|→\{0,1\}PrX∼μ\[g\(projJt,μ⋆\(X\)\)≠rt\(X\)\]\.\\alpha\_\{t,\\mu\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\inf\_\{g:\\\{0,1\\\}^\{\|J\_\{t,\\mu\}^\{\\star\}\|\}\\to\\\{0,1\\\}\}\\Pr\_\{X\\sim\\mu\}\\left\[g\(\\operatorname\{proj\}\_\{J\_\{t,\\mu\}^\{\\star\}\}\(X\)\)\\neq r\_\{t\}\(X\)\\right\]\.For anyδgen∈\(0,1\)\\delta\_\{\\mathrm\{gen\}\}\\in\(0,1\), the proof of Theorem[20](https://arxiv.org/html/2609.13439#Thmtheorem20)then yields, forT≥mT\\geq m,

PrX∼μ\[Ht\(X\)≠f\(X\)\]≤αt,μ\+Cm⁡\(2K\+K​log⁡e​BK\+log⁡mδgen\)T\\Pr\_\{X\\sim\\mu\}\[H\_\{t\}\(X\)\\neq f\(X\)\]\\leq\\alpha\_\{t,\\mu\}\+C\\sqrt\{\\frac\{m\\left\(2^\{K\}\+K\\log\\frac\{eB\}\{K\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}simultaneously over all completed stages, with probability at least1−δinf−δgen1\-\\delta\_\{\\mathrm\{inf\}\}\-\\delta\_\{\\mathrm\{gen\}\}\. Similarly, ifrtr\_\{t\}depends only on the coordinates inJt,μ⋆J\_\{t,\\mu\}^\{\\star\}and\|Jt,μ⋆\|≤S≤K\|J\_\{t,\\mu\}^\{\\star\}\|\\leq S\\leq K, then the argument of Theorem[9](https://arxiv.org/html/2609.13439#Thmtheorem9)gives

PrX∼μ\[Ht\(X\)≠f\(X\)\]≤Cm⁡\(2S\+S​log⁡e​BS\+log⁡mδgen\)T\.\\Pr\_\{X\\sim\\mu\}\[H\_\{t\}\(X\)\\neq f\(X\)\]\\leq C\\sqrt\{\\frac\{m\\left\(2^\{S\}\+S\\log\\frac\{eB\}\{S\}\+\\log\\frac\{m\}\{\\delta\_\{\\mathrm\{gen\}\}\}\\right\)\}\{T\}\}\.
The distribution\-dependent and uniform influences can be compared directly when the input measures are related by a bounded density ratio\.

###### Proposition 24\(Change\-of\-measure comparison\)\.

Letν=Unif⁡\(\{0,1\}B\)\\nu=\\operatorname\{Unif\}\(\\\{0,1\\\}^\{B\}\)and letμ\\mube any probability measure on\{0,1\}B\\\{0,1\\\}^\{B\}\. Defineξ⁡\(x\)=def\.μ⁡\(\{x\}\)ν⁡\(\{x\}\)=2B​μ​\(\{x\}\)\\xi\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\frac\{\\mu\(\\\{x\\\}\)\}\{\\nu\(\\\{x\\\}\)\}=2^\{B\}\\mu\(\\\{x\\\}\); then, for every Boolean functionhhand everyi∈\[B\]i\\in\[B\],

\(minx⁡ξ⁡\(x\)\)​Infi⁡\(h\)≤Infiμ⁡\(h\)≤\(maxx⁡ξ⁡\(x\)\)​Infi⁡\(h\)\.\\left\(\\min\_\{x\}\\xi\(x\)\\right\)\\operatorname\{Inf\}\_\{i\}\(h\)\\leq\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)\\leq\\left\(\\max\_\{x\}\\xi\(x\)\\right\)\\operatorname\{Inf\}\_\{i\}\(h\)\.

###### Proof\.

Setϕi\(x\)=def\.𝟙\{h\(x\)≠h\(x⊕i\)\}\\phi\_\{i\}\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\mathbbm\{1\}\\left\\\{h\(x\)\\neq h\(x^\{\\oplus i\}\)\\right\\\}\. Sinceϕi≥0\\phi\_\{i\}\\geq 0,

Infiμ⁡\(h\)=𝔼X∼ν​\[ξ⁡\(X\)​ϕi​\(X\)\]≤\(maxx⁡ξ⁡\(x\)\)​𝔼X∼ν​\[ϕi​\(X\)\]=\(maxx⁡ξ⁡\(x\)\)​Infi⁡\(h\)\.\\displaystyle\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)=\\mathbb\{E\}\_\{X\\sim\\nu\}\[\\xi\(X\)\\phi\_\{i\}\(X\)\]\\leq\\left\(\\max\_\{x\}\\xi\(x\)\\right\)\\mathbb\{E\}\_\{X\\sim\\nu\}\[\\phi\_\{i\}\(X\)\]=\\left\(\\max\_\{x\}\\xi\(x\)\\right\)\\operatorname\{Inf\}\_\{i\}\(h\)\.The lower bound follows analogously usingminx⁡ξ⁡\(x\)\\min\_\{x\}\\xi\(x\)\. ∎

Ifμ⁡\(\{x\}\)=wx\\mu\(\\\{x\\\}\)=w\_\{x\}, thenξ⁡\(x\)=2B​wx\\xi\(x\)=2^\{B\}w\_\{x\}\. Hence, Proposition[24](https://arxiv.org/html/2609.13439#Thmtheorem24)becomes

\(2B​minx​wx\)​Infi⁡\(h\)≤Infiμ⁡\(h\)≤\(2B​maxx​wx\)​Infi⁡\(h\)\.\\left\(2^\{B\}\\min\_\{x\}w\_\{x\}\\right\)\\operatorname\{Inf\}\_\{i\}\(h\)\\leq\\operatorname\{Inf\}\_\{i\}^\{\\mu\}\(h\)\\leq\\left\(2^\{B\}\\max\_\{x\}w\_\{x\}\\right\)\\operatorname\{Inf\}\_\{i\}\(h\)\.

### F\.3Auxiliary Results for the Certifiably Interpretable Neural Realization

This appendix records neural\-representation facts that are not needed for the main circuit\-to\-network compilation\. They clarify limitations of very small ReLU modules and give alternative exact realizations when a different depth–width tradeoff is desired\.

#### F\.3\.1Additional Gate Realizations and Impossibility Results

The AND module used in Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)follows the same width\-two template as OR, which simplifies the layerwise construction\. Conjunction itself can be represented more narrowly\.

###### Lemma 25\(Width\-one realization of multi\-input AND\)\.

For everyr≥1r\\geq 1anda∈\{0,1\}ra\\in\\\{0,1\\\}^\{r\},⋀j=1raj=σ⁡\(∑j=1raj−r\+1\)\\bigwedge\_\{j=1\}^\{r\}a\_\{j\}=\\sigma\\left\(\\sum\_\{j=1\}^\{r\}a\_\{j\}\-r\+1\\right\)\.

###### Proof\.

If all inputs equal one, the ReLU argument equals one\. Otherwise∑j=1raj≤r−1\\sum\_\{j=1\}^\{r\}a\_\{j\}\\leq r\-1; thus, the argument is non\-positive and the output is zero\. ∎

Although multi\-input AND admits a width\-one realization, the width\-two OR module used in Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)cannot, in general, be reduced to a single affine–ReLU unit\.

###### Lemma 26\(A single ReLU unit cannot realize multi\-input OR\)\.

Letr≥2r\\geq 2\. There are now∈ℝrw\\in\\mathbb\{R\}^\{r\}andb∈ℝb\\in\\mathbb\{R\}such thatσ⁡\(w⊤​a\+b\)=⋁j=1raj\\sigma\(w^\{\\top\}a\+b\)=\\bigvee\_\{j=1\}^\{r\}a\_\{j\}for everya∈\{0,1\}ra\\in\\\{0,1\\\}^\{r\}\.

###### Proof\.

Suppose suchwwandbbexist\. Evaluating ata=0a=0givesσ⁡\(b\)=0\\sigma\(b\)=0, henceb≤0b\\leq 0\. For each standard basis vectoreie\_\{i\}, the required output is one; therefore,σ⁡\(wi\+b\)=1\\sigma\(w\_\{i\}\+b\)=1\. Positivity implieswi\+b=1w\_\{i\}\+b=1, hencewi=1−bw\_\{i\}=1\-b\. For distincti,ji,j, OR again requires output one atei\+eje\_\{i\}\+e\_\{j\}, whereasσ⁡\(wi\+wj\+b\)=σ⁡\(2−b\)=2−b≥2\\sigma\(w\_\{i\}\+w\_\{j\}\+b\)=\\sigma\(2\-b\)=2\-b\\geq 2, a contradiction\. ∎

OR can nevertheless be realized with width one by adding depth\.

###### Lemma 27\(Depth\-two, width\-one realization of multi\-input OR\)\.

For everyr≥1r\\geq 1anda∈\{0,1\}ra\\in\\\{0,1\\\}^\{r\},⋁j=1raj=σ⁡\(1−σ⁡\(1−∑j=1raj\)\)\\bigvee\_\{j=1\}^\{r\}a\_\{j\}=\\sigma\\left\(1\-\\sigma\\left\(1\-\\sum\_\{j=1\}^\{r\}a\_\{j\}\\right\)\\right\)\.

###### Proof\.

If∑jaj=0\\sum\_\{j\}a\_\{j\}=0, the inner ReLU equals one and the outer ReLU equals zero\. If∑jaj≥1\\sum\_\{j\}a\_\{j\}\\geq 1, the inner ReLU equals zero and the outer ReLU equals one\. ∎

Parity also cannot be represented by one affine–ReLU unit as soon as there are at least two inputs\.

###### Lemma 28\(A single ReLU unit cannot realize multi\-input XOR\)\.

Supposer≥2r\\geq 2\. Then there are now∈ℝrw\\in\\mathbb\{R\}^\{r\}andb∈ℝb\\in\\mathbb\{R\}such thatσ⁡\(w⊤​a\+b\)=⨁j=1raj\\sigma\(w^\{\\top\}a\+b\)=\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}for everya∈\{0,1\}ra\\in\\\{0,1\\\}^\{r\}\.

###### Proof\.

Suppose suchwwandbbexist\. Ata=0a=0, parity is zero, sob≤0b\\leq 0\. At eacheie\_\{i\}, parity is one, implyingwi\+b=1w\_\{i\}\+b=1and hencewi=1−bw\_\{i\}=1\-b\. For distincti,ji,j, parity atei\+eje\_\{i\}\+e\_\{j\}is zero, butσ⁡\(wi\+wj\+b\)=σ⁡\(2−b\)=2−b≥2\\sigma\(w\_\{i\}\+w\_\{j\}\+b\)=\\sigma\(2\-b\)=2\-b\\geq 2, a contradiction\. ∎

#### F\.3\.2Alternative Exact XOR Realizations

The XOR module in Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2)is chosen to preserve constant overall depth, at the cost of a parity layer whose width scales with the number of inputs\. Exact alternatives exchange depth for narrower or more local parity computation\.

##### A width\-two composition\.

Following the triangle\-map construction of[Telgarsky \(2015\)](https://arxiv.org/html/2609.13439#bib.bib23), define

△⁡\(x\)=def\.σ⁡\(2​σ​\(x\)−4​σ​\(x−12\)\)\.\\triangle\(x\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sigma\\left\(2\\sigma\(x\)\-4\\sigma\\left\(x\-\\frac\{1\}\{2\}\\right\)\\right\)\.On\[0,1\]\[0,1\], this is the piecewise\-linear triangle

△⁡\(x\)=\{2​x,0≤x≤12,2−2​x,12≤x≤1\.\\triangle\(x\)=\\begin\{cases\}2x,&0\\leq x\\leq\\frac\{1\}\{2\},\\\\ 2\-2x,&\\frac\{1\}\{2\}\\leq x\\leq 1\.\\end\{cases\}The following lemma shows why repeated composition computes parity on an appropriate dyadic grid\. Fork∈ℕ\+k\\in\\mathbb\{N\}\_\{\+\}, let△∘k\\triangle^\{\\circ k\}denote thekk\-fold composition of△\\trianglewith itself; that is,△∘1=△\\triangle^\{\\circ 1\}=\\triangleand△∘k=△∘△∘\(k−1\)\\triangle^\{\\circ k\}=\\triangle\\circ\\triangle^\{\\circ\(k\-1\)\}fork≥2k\\geq 2\.

###### Lemma 29\(Parity on dyadic grids\)\.

For every integerk≥1k\\geq 1and everys∈\{0,…,2k\}s\\in\\\{0,\\ldots,2^\{k\}\\\},

△∘k​\(s2k\)=\{0,s​even,1,s​odd\.\\triangle^\{\\circ k\}\\\!\\left\(\\frac\{s\}\{2^\{k\}\}\\right\)=\\begin\{cases\}0,&s\\text\{ even\},\\\\ 1,&s\\text\{ odd\}\.\\end\{cases\}

###### Proof\.

We use induction onkk\. Fork=1k=1,△⁡\(0\)=0\\triangle\(0\)=0,△⁡\(12\)=1\\triangle\(\\tfrac\{1\}\{2\}\)=1, and△⁡\(1\)=0\\triangle\(1\)=0\. Therefore, the claim holds for the base case\. Now assume the result holds fork−1k\-1, and fixs∈\{0,…,2k\}s\\in\\\{0,\\ldots,2^\{k\}\\\}\. By the piecewise definition of△\\triangle,

△⁡\(s2k\)=\{s2k−1,s≤2k−1,2k−s2k−1,s≥2k−1\.\\triangle\\\!\\left\(\\frac\{s\}\{2^\{k\}\}\\right\)=\\begin\{cases\}\\displaystyle\\frac\{s\}\{2^\{k\-1\}\},&s\\leq 2^\{k\-1\},\\\\\[8\.00003pt\] \\displaystyle\\frac\{2^\{k\}\-s\}\{2^\{k\-1\}\},&s\\geq 2^\{k\-1\}\.\\end\{cases\}Thus, after the first application of△\\triangle, the argument has the forms′/2k−1s^\{\\prime\}/2^\{k\-1\}, where

s′=\{s,s≤2k−1,2k−s,s≥2k−1\.s^\{\\prime\}=\\begin\{cases\}s,&s\\leq 2^\{k\-1\},\\\\ 2^\{k\}\-s,&s\\geq 2^\{k\-1\}\.\\end\{cases\}In either case,s′∈\{0,…,2k−1\}s^\{\\prime\}\\in\\\{0,\\ldots,2^\{k\-1\}\\\}\. Moreover, since2k2^\{k\}is even,s′s^\{\\prime\}has the same parity asss\. Applying the remainingk−1k\-1copies of△\\triangleand using the induction hypothesis therefore gives

△∘k​\(s2k\)=△∘\(k−1\)​\(s′2k−1\)=\{0,s′​even,1,s′​odd\.\\triangle^\{\\circ k\}\\\!\\left\(\\frac\{s\}\{2^\{k\}\}\\right\)=\\triangle^\{\\circ\(k\-1\)\}\\\!\\left\(\\frac\{s^\{\\prime\}\}\{2^\{k\-1\}\}\\right\)=\\begin\{cases\}0,&s^\{\\prime\}\\text\{ even\},\\\\ 1,&s^\{\\prime\}\\text\{ odd\}\.\\end\{cases\}Sinces′s^\{\\prime\}andsshave the same parity, this is exactly

△∘k​\(s2k\)=\{0,s​even,1,s​odd\.\\triangle^\{\\circ k\}\\\!\\left\(\\frac\{s\}\{2^\{k\}\}\\right\)=\\begin\{cases\}0,&s\\text\{ even\},\\\\ 1,&s\\text\{ odd\}\.\\end\{cases\}This completes the induction\. ∎

###### Proposition 30\(Width\-two XOR realization\)\.

Letr≥2r\\geq 2,k=def\.⌈log2⁡r⌉k\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\lceil\\log\_\{2\}r\\rceil, anda∈\{0,1\}ra\\in\\\{0,1\\\}^\{r\}\. Then

△∘k​\(2−k​∑j=1raj\)=⨁j=1raj\.\\triangle^\{\\circ k\}\\\!\\left\(2^\{\-k\}\\sum\_\{j=1\}^\{r\}a\_\{j\}\\right\)=\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}\.Consequently,rr\-input XOR admits an exact realization with maximum width two and depth2​⌈log2⁡r⌉2\\lceil\\log\_\{2\}r\\rceil\.

###### Proof\.

Lets⁡\(a\)=def\.∑j=1rajs\(a\)\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\sum\_\{j=1\}^\{r\}a\_\{j\}\. Sinces⁡\(a\)∈\{0,…,r\}⊆\{0,…,2k\}s\(a\)\\in\\\{0,\\ldots,r\\\}\\subseteq\\\{0,\\ldots,2^\{k\}\\\}, Lemma[29](https://arxiv.org/html/2609.13439#Thmtheorem29)gives△∘k​\(2−k​s​\(a\)\)=s⁡\(a\)mod2\\triangle^\{\\circ k\}\(2^\{\-k\}s\(a\)\)=s\(a\)\\bmod 2, which is exactly⨁j=1raj\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}\. Each copy of△\\triangleconsists of a width\-two ReLU layer followed by a scalar ReLU layer, meaning that stackingkkcopies gives depth2​k2kand maximum width two\. ∎

##### A depth\-parameterized construction\.

A second alternative interpolates between one shallow high\-arity XOR and a deeper composition of smaller XOR modules\.

###### Proposition 31\(Depth\-parameterized XOR realization\)\.

Letr,d≥1r,d\\geq 1be arbitrary positive integers, andq=def\.⌈r1/d⌉q\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}\\lceil r^\{1/d\}\\rceil\. There exists an exact ReLU realization of⨁j=1raj\\bigoplus\_\{j=1\}^\{r\}a\_\{j\}on\{0,1\}r\\\{0,1\\\}^\{r\}obtained by composing at mostddcollections of XOR modules, each having arity at mostqq\. The resulting network has depth at most2​d2d, maximum layer width at mostrr, and at most2​d​r2drnon\-input neurons\. Equivalently, for prescribed even depthL=2​dL=2d, the required local XOR arity is at most⌈r2/L⌉\\lceil r^\{2/L\}\\rceil\.

###### Proof\.

Letn0=def\.rn\_\{0\}\\stackrel\{\{\\scriptstyle\\mbox\{\\tiny def\.\}\}\}\{\{=\}\}r\. At composition staget≥1t\\geq 1, partition thent−1n\_\{t\-1\}current Boolean signals into groups of size at mostqq, and replace each group by its parity using Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)\. Ifntn\_\{t\}is the number of resulting signals, thennt=⌈nt−1/q⌉=⌈r/qt⌉n\_\{t\}=\\lceil n\_\{t\-1\}/q\\rceil=\\lceil r/q^\{t\}\\rceil\. Sinceqd≥rq^\{d\}\\geq r, we havend≤1n\_\{d\}\\leq 1, ensuring that after at mostddstages one parity signal remains\. Associativity and commutativity of XOR imply that this signal isa1⊕⋯⊕ara\_\{1\}\\oplus\\cdots\\oplus a\_\{r\}\.

Each local XOR module has depth two, and all modules at one composition stage operate in parallel, giving total depth at most2​d2d\. If the group sizes at stagettareℓ1,…,ℓnt\\ell\_\{1\},\\ldots,\\ell\_\{n\_\{t\}\}, their hidden widths sum to∑jℓj=nt−1≤r\\sum\_\{j\}\\ell\_\{j\}=n\_\{t\-1\}\\leq r, while the output width isnt≤rn\_\{t\}\\leq r\. Hence every layer has width at mostrr\. Each stage uses at mostnt−1\+nt≤2​rn\_\{t\-1\}\+n\_\{t\}\\leq 2rnon\-input neurons\. Therefore, the total is at most2​d​r2dr\. Finally, whenL=2​dL=2d,q=⌈r1/d⌉=⌈r2/L⌉q=\\lceil r^\{1/d\}\\rceil=\\lceil r^\{2/L\}\\rceil\. ∎

The direct XOR module of Proposition[10](https://arxiv.org/html/2609.13439#Thmtheorem10)corresponds to the constant\-depth endpointd=1d=1\. Increasingddreduces the largest local parity arity, while Proposition[30](https://arxiv.org/html/2609.13439#Thmtheorem30)pushes further toward constant global width at logarithmic depth\. These alternatives are not used in Algorithm[2](https://arxiv.org/html/2609.13439#algorithm2); they are included only to document exact architectural tradeoffs available without changing the Boolean computation\.

## References

- G\. Alain and Y\. BengioUnderstanding intermediate layers using linear classifier probes\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.1)\.
- Bahriet al\.\(2024\)Y\. Bahri, E\. Dyer, J\. Kaplan, J\. Lee, and U\. SharmaExplaining neural scaling laws\.Proceedings of the National Academy of Sciences121\(27\),pp\. e2311878121\.External Links:[Document](https://dx.doi.org/10.1073/pnas.2311878121)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Basel Committee on Banking Supervision \(2009\)Basel Committee on Banking SupervisionRevisions to the basel ii market risk framework\.Technical reportBank for International Settlements,Basel, Switzerland\.External Links:[Link](https://www.bis.org/publ/bcbs158.htm)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Basel Committee on Banking Supervision \(2012\)Basel Committee on Banking SupervisionFundamental review of the trading book\.Technical reportBank for International Settlements,Basel, Switzerland\.External Links:[Link](https://www.bis.org/publ/bcbs219.htm)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Bengioet al\.\(2026\)Y\. Bengio, S\. Clare, C\. Prunkl, M\. Andriushchenko, B\. Bucknall, M\. Murray, R\. Bommasani, S\. Casper, T\. Davidson, R\. Douglas,et al\.International ai safety report 2026\.arXiv preprint arXiv:2602\.21012\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Bengioet al\.\(2024\)Y\. Bengio, G\. Hinton, A\. Yao, D\. Song, P\. Abbeel, T\. Darrell, Y\. N\. Harari, Y\. Zhang, L\. Xue, S\. Shalev\-Shwartz, G\. Hadfield, J\. Clune, T\. Maharaj, F\. Hutter, A\. G\. Baydin, S\. McIlraith, Q\. Gao, A\. Acharya, D\. Krueger, A\. Dragan, P\. Torr, S\. Russell, D\. Kahneman, J\. Brauner, and S\. MindermannManaging extreme ai risks amid rapid progress\.Science384\(6698\),pp\. 842–845\.External Links:[Document](https://dx.doi.org/10.1126/science.adn0117)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Boroumandet al\.\(2021\)S\. Boroumand, C\. Bouganis, and G\. A\. ConstantinidesLearning boolean circuits from examples for approximate logic synthesis\.In2021 26th Asia and South Pacific Design Automation Conference \(ASP\-DAC\),pp\. 524–529\.External Links:[Document](https://dx.doi.org/10.1145/3394885.3431559)Cited by:[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Braytonet al\.\(1984\)R\. K\. Brayton, G\. D\. Hachtel, C\. McMullen, and A\. Sangiovanni\-VincentelliLogic minimization algorithms for vlsi synthesis\.Vol\.2,Springer Science & Business Media\.Cited by:[§C\.1](https://arxiv.org/html/2609.13439#A3.SS1.p3.1),[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p2.1)\.
- Braytonet al\.\(1982\)R\. K\. Brayton, G\. D\. Hachtel, L\. A\. Hemachandra, A\. R\. Newton, and A\. L\. Sangiovanni\-VincentelliA comparison of logic minimization strategies using ESPRESSO: an APL program package for partitioned logic minimization\.InProceedings of the 1982 IEEE International Symposium on Circuits and Systems \(ISCAS\),pp\. 42–48\.Cited by:[§1\.1](https://arxiv.org/html/2609.13439#S1.SS1.p1.1)\.
- Bühreret al\.\(2025\)S\. Bührer, A\. Plesner, T\. Aczel, and R\. WattenhoferRecurrent deep differentiable logic gate networks\.InProceedings of the 2nd International Workshop on Edge and Mobile Foundation Models,pp\. 31–36\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Burnset al\.\(2023\)C\. Burns, H\. Ye, D\. Klein, and J\. SteinhardtDiscovering latent knowledge in language models without supervision\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.1)\.
- Changet al\.\(2018\)S\. Chang, X\. Zheng, I\. E\. H\. Yen, P\. Ravikumar, and R\. YuEfficient tensor decomposition with boolean factors\.arXiv preprint arXiv:1810\.04754\.Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p2.1)\.
- Chevallieret al\.\(2008\)C\. Chevallier, I\. A\. Noveck, T\. Nazir, L\. Bott, V\. Lanzetti, and D\. SperberMaking disjunctions exclusive\.Quarterly Journal of Experimental Psychology61\(11\),pp\. 1741–1760\.External Links:[Document](https://dx.doi.org/10.1080/17470210701712960)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p1.1)\.
- Ciravegnaet al\.\(2023\)G\. Ciravegna, P\. Barbiero, F\. Giannini, M\. Gori, P\. Liò, M\. Maggini, and S\. MelacciLogic explained networks\.Artificial Intelligence314,pp\. 103822\.External Links:[Document](https://dx.doi.org/10.1016/j.artint.2022.103822)Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1),[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Cyberspace Administration of China and Ministry of Industry and Information Technology and Ministry of Public Security and State Administration for Market Regulation \(2022\)Cyberspace Administration of China and Ministry of Industry and Information Technology and Ministry of Public Security and State Administration for Market RegulationProvisions on the administration of algorithmic recommendation in internet information services\.People’s Republic of China\.Note:Order No\. 9; effective March 1, 2022External Links:[Link](https://www.cac.gov.cn/2022-01/04/c_1642894606364259.htm)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Dawkins and Cook \(2017\)P\. C\. Dawkins and J\. P\. CookGuiding reinvention of conventional tools of mathematical logic: students’ reasoning about mathematical disjunctions\.Educational Studies in Mathematics94\(3\),pp\. 241–256\.Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p1.1)\.
- Delbaen \(1998\)F\. DelbaenCoherent risk measures on general probability spaces\.Working PaperETH Zürich,Zürich, Switzerland\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Denić and Szymanik \(2022\)M\. Denić and J\. SzymanikAre most and more than half truth\-conditionally equivalent?\.Journal of Semantics39\(2\),pp\. 261–294\.External Links:[Document](https://dx.doi.org/10.1093/jos/ffab024)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p2.1)\.
- d’Ascoliet al\.\(2023\)S\. d’Ascoli, A\. Renard, V\. Papadopoulos, S\. Bengio, J\. Susskind, and E\. AbbéBoolformer: symbolic regression of logic functions with transformers\.arXiv preprint arXiv:2309\.12207\.Note:Revised 2025External Links:[Document](https://dx.doi.org/10.48550/arXiv.2309.12207)Cited by:[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- European Parliament and Council of the European Union \(2024\)European Parliament and Council of the European UnionRegulation \(EU\) 2024/1689 laying down harmonised rules on artificial intelligence \(Artificial Intelligence Act\)\.Note:Official Journal of the European UnionRegulation \(EU\) 2024/1689External Links:[Link](https://eur-lex.europa.eu/eli/reg/2024/1689/oj)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Faroß and Schwarz \(2025\)N\. Faroß and S\. SchwarzGröbner bases for boolean function minimization\.Mathematics in Computer Science19\(1\),pp\. 7\.Cited by:[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p1.1)\.
- Feldman \(2010\)V\. FeldmanDistribution\-specific agnostic boosting\.InInnovations in Computer Science,pp\. 241–250\.Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1)\.
- Feldman \(2012\)V\. FeldmanLearning dnf expressions from fourier spectrum\.InConference on Learning Theory,pp\. 17–1\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Fleuret \(2004\)F\. FleuretFast binary feature selection with conditional mutual information\.Journal of Machine learning research5\(Nov\),pp\. 1531–1555\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Freund and Schapire \(1997\)Y\. Freund and R\. E\. SchapireA decision\-theoretic generalization of on\-line learning and an application to boosting\.Journal of computer and system sciences55\(1\),pp\. 119–139\.Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1)\.
- Friedgut \(1998\)E\. FriedgutBoolean functions with low average sensitivity depend on few coordinates\.Combinatorica18\(1\),pp\. 27–35\.External Links:[Document](https://dx.doi.org/10.1007/PL00009809)Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Friedman \(2001\)J\. H\. FriedmanGreedy function approximation: a gradient boosting machine\.The Annals of Statistics29\(5\),pp\. 1189–1232\.External Links:[Document](https://dx.doi.org/10.1214/aos/1013203451)Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1)\.
- Furstet al\.\(1984\)M\. L\. Furst, J\. B\. Saxe, and M\. SipserParity, circuits, and the Polynomial\-Time hierarchy\.Mathematical Systems Theory17\(1\),pp\. 13–27\.External Links:[Document](https://dx.doi.org/10.1007/BF01744431)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p2.1)\.
- Geirhoset al\.\(2020\)R\. Geirhos, J\. Jacobsen, C\. Michaelis, R\. Zemel, W\. Brendel, M\. Bethge, and F\. A\. WichmannShortcut learning in deep neural networks\.Nature Machine Intelligence2\(11\),pp\. 665–673\.External Links:[Document](https://dx.doi.org/10.1038/s42256-020-00257-z)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.2)\.
- Guyon and Elisseeff \(2003\)I\. Guyon and A\. ElisseeffAn introduction to variable and feature selection\.Journal of machine learning research3\(Mar\),pp\. 1157–1182\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Hall and Heyde \(1980\)P\. Hall and C\. C\. HeydeMartingale limit theory and its application\.Probability and Mathematical Statistics: A Series of Monographs and Textbooks,Academic Press,New York\.External Links:ISBN 978\-0\-12\-319350\-6,[Document](https://dx.doi.org/10.1016/C2013-0-10818-5)Cited by:[§4\.1\.1](https://arxiv.org/html/2609.13439#S4.SS1.SSS1.p2.1)\.
- Håstad \(1986\)J\. HåstadAlmost optimal lower bounds for small depth circuits\.InProceedings of the 18th Annual ACM Symposium on Theory of Computing,pp\. 6–20\.External Links:[Document](https://dx.doi.org/10.1145/12130.12132)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p2.1)\.
- Haussler \(1995\)D\. HausslerSphere packing numbers for subsets of the boolean n\-cube with bounded vapnik\-chervonenkis dimension\.Journal of Combinatorial Theory, Series A69\(2\),pp\. 217–232\.Cited by:[§A\.1\.3](https://arxiv.org/html/2609.13439#A1.SS1.SSS3.p2.3.1),[§A\.2\.3](https://arxiv.org/html/2609.13439#A1.SS2.SSS3.p1.3)\.
- Hestnesset al\.\(2017\)J\. Hestness, S\. Narang, N\. Ardalani, G\. Diamos, H\. Jun, H\. Kianinejad, Md\. M\. A\. Patwary, Y\. Yang, and Y\. ZhouDeep learning scaling is predictable, empirically\.arXiv preprint arXiv:1712\.00409\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.1712.00409)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Hewitt and Liang \(2019\)J\. Hewitt and P\. LiangDesigning and interpreting probes with control tasks\.InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing,pp\. 2733–2743\.External Links:[Document](https://dx.doi.org/10.18653/v1/D19-1275)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.1)\.
- Hong and Kratsios \(2024\)R\. Hong and A\. KratsiosBridging the gap between approximation and learning via optimal approximation by relu mlps of maximal regularity\.arXiv preprint arXiv:2409\.12335\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.2)\.
- Ibarzet al\.\(2022\)B\. Ibarz, V\. Kurin, G\. Papamakarios, K\. Nikiforou, M\. Bennani, R\. Csordás, A\. Dudzik, M\. Bošnjak, A\. Vitvitskyi, Y\. Rubanova, A\. Deac, B\. Bevilacqua, Y\. Ganin, C\. Blundell, and P\. VeličkovićA generalist neural algorithmic learner\.InLearning on Graphs Conference,Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Jackson \(1997\)J\. C\. JacksonAn efficient membership\-query algorithm for learning DNF with respect to the uniform distribution\.Journal of Computer and System Sciences55\(3\),pp\. 414–440\.External Links:[Document](https://dx.doi.org/10.1006/jcss.1997.1533)Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1)\.
- Johnson\-Lairdet al\.\(1992\)P\. N\. Johnson\-Laird, R\. M\. J\. Byrne, and W\. SchaekenPropositional reasoning by model\.Psychological Review99\(3\),pp\. 418–439\.External Links:[Document](https://dx.doi.org/10.1037/0033-295X.99.3.418)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p1.1)\.
- Jukna \(2012\)S\. JuknaBoolean function complexity: advances and frontiers\.Algorithms and Combinatorics, Vol\.27,Springer,Berlin, Heidelberg\.External Links:ISBN 978\-3\-642\-24507\-5Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p1.1)\.
- Kanakiaet al\.\(2021\)H\. Kanakia, M\. Nazemi, A\. Fayyazi, and M\. PedramESPRESSO\-GPU: blazingly fast two\-level logic minimization\.In2021 Design, Automation & Test in Europe Conference & Exhibition \(DATE\),pp\. 1038–1043\.External Links:[Document](https://dx.doi.org/10.23919/DATE51398.2021.9473961)Cited by:[§1\.3\.1](https://arxiv.org/html/2609.13439#S1.SS3.SSS1.p1.1),[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p1.1),[footnote 2](https://arxiv.org/html/2609.13439#footnote2)\.
- Kaplanet al\.\(2020\)J\. Kaplan, S\. McCandlish, T\. Henighan, T\. B\. Brown, B\. Chess, R\. Child, S\. Gray, A\. Radford, J\. Wu, and D\. AmodeiScaling laws for neural language models\.arXiv preprint arXiv:2001\.08361\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2001.08361)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Karnaugh \(1953\)M\. KarnaughThe map method for synthesis of combinational logic circuits\.Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics72\(5\),pp\. 593–599\.Cited by:[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p1.1)\.
- Kelleret al\.\(2012\)N\. Keller, E\. Mossel, and A\. SenGeometric influences\.The Annals of Probability40\(3\)\.External Links:ISSN 0091\-1798,[Link](http://dx.doi.org/10.1214/11-AOP643),[Document](https://dx.doi.org/10.1214/11-aop643)Cited by:[§2\.2](https://arxiv.org/html/2609.13439#S2.SS2.p3.1)\.
- Kohut and Steinbach \(2004\)R\. Kohut and B\. SteinbachBoolean neural networks\.Transactions on Systems2,pp\. 420–425\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p1.1)\.
- Kratsioset al\.\(2026a\)A\. Kratsios, S\. Brugiapaglia, B\. J\. Kim, G\. Cousins, and H\. S\. d\. O\. BordeAlgorithmic foundations of deep learning: complexity\-theoretic rates and a characterization of universal approximation\.arXiv preprint arXiv:2606\.26705\.Cited by:[§1\.1](https://arxiv.org/html/2609.13439#S1.SS1.SSS0.Px2.p1.1),[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p1.1)\.
- Kratsioset al\.\(2025a\)A\. Kratsios, T\. S\. Cheng, and D\. RoyBeyond universal approximation theorems: algorithmic uniform approximation by neural networks trained with noisy data\.arXiv preprint arXiv:2509\.00924\.Cited by:[§4\.1\.2](https://arxiv.org/html/2609.13439#S4.SS1.SSS2.p5.1)\.
- Kratsioset al\.\(2026b\)A\. Kratsios, A\. M\. Neuman, and P\. PetersenAdaptivity under realizability constraints: comparing in\-context and agentic learning\.arXiv preprint arXiv:2605\.04995\.Cited by:[§6](https://arxiv.org/html/2609.13439#S6.p3.1)\.
- Kratsioset al\.\(2025b\)A\. Kratsios, D\. Zvigelsky, and B\. HartQuantifying the limits of ai reasoning: systematic neural network representations of algorithms\.arXiv preprint arXiv:2508\.18526\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Liet al\.\(2026\)W\. Li, A\. Kratsios, H\. Ghoukasian, and D\. ZvigelskyCertifiable boolean reasoning is universal\.arXiv preprint arXiv:2602\.05120\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p1.1)\.
- Limmeret al\.\(2024\)Y\. Limmer, A\. Kratsios, X\. Yang, R\. Saqur, and B\. HorvathHigher\-order transformer derivative estimates for explicit pathwise learning guarantees\.arXiv preprint arXiv:2405\.16563\.Cited by:[§4\.1\.1](https://arxiv.org/html/2609.13439#S4.SS1.SSS1.p2.1)\.
- Loshchilov and Hutter \(2019\)I\. Loshchilov and F\. HutterDecoupled weight decay regularization\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Lundberg and Lee \(2017\)S\. M\. Lundberg and S\. LeeA unified approach to interpreting model predictions\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.1)\.
- Mallat and Zhang \(1993\)S\. G\. Mallat and Z\. ZhangMatching pursuits with time\-frequency dictionaries\.IEEE Transactions on Signal Processing41\(12\),pp\. 3397–3415\.External Links:[Document](https://dx.doi.org/10.1109/78.258082)Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1)\.
- McCluskey \(1956\)E\. J\. McCluskeyMinimization of boolean functions\.The Bell System Technical Journal35\(6\),pp\. 1417–1444\.Cited by:[§1\.3\.1](https://arxiv.org/html/2609.13439#S1.SS3.SSS1.p1.1),[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1),[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p1.1)\.
- McCoyet al\.\(2019\)R\. T\. McCoy, E\. Pavlick, and T\. LinzenRight for the wrong reasons: diagnosing syntactic heuristics in natural language inference\.InProceedings of the 57th Annual Meeting of the Association for Computational Linguistics,pp\. 3428–3448\.External Links:[Document](https://dx.doi.org/10.18653/v1/P19-1334)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.2)\.
- McCulloch and Pitts \(1943\)W\. S\. McCulloch and W\. PittsA logical calculus of the ideas immanent in nervous activity\.The Bulletin of Mathematical Biophysics5,pp\. 115–133\.External Links:[Document](https://dx.doi.org/10.1007/BF02478259)Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Meyn and Tweedie \(2009\)S\. P\. Meyn and R\. L\. TweedieMarkov chains and stochastic stability\.2 edition,Cambridge Mathematical Library,Cambridge University Press,Cambridge\.External Links:ISBN 978\-0\-521\-73182\-9,[Document](https://dx.doi.org/10.1017/CBO9780511626630)Cited by:[§4\.1\.1](https://arxiv.org/html/2609.13439#S4.SS1.SSS1.p2.1)\.
- Mitaet al\.\(2020\)G\. Mita, P\. Papotti, M\. Filippone, and P\. MichiardiLIBRE: learning interpretable boolean rule ensembles\.InProceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.108,pp\. 245–255\.Cited by:[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Mitzenmacher and Upfal \(2005\)M\. Mitzenmacher and E\. UpfalProbability and computing\.Cambridge University\.Cited by:[§A\.1\.1](https://arxiv.org/html/2609.13439#A1.SS1.SSS1.p2.1.1)\.
- Mosselet al\.\(2004\)E\. Mossel, R\. O’Donnell, and R\. A\. ServedioLearning functions of k relevant variables\.Journal of Computer and System Sciences69\(3\),pp\. 421–434\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Mosselet al\.\(2003\)E\. Mossel, R\. O’Donnell, and R\. P\. ServedioLearning juntas\.InProceedings of the thirty\-fifth annual ACM symposium on Theory of computing,pp\. 206–212\.Cited by:[§2\.2](https://arxiv.org/html/2609.13439#S2.SS2.p1.1)\.
- Nazemiet al\.\(2021\)M\. Nazemi, H\. Kanakia, and M\. PedramHeuristics for million\-scale two\-level logic minimization\.In2021 IEEE/ACM International Conference on Computer\-Aided Design \(ICCAD\),pp\. 1–7\.External Links:[Document](https://dx.doi.org/10.1109/ICCAD51958.2021.9643572)Cited by:[§1\.3\.1](https://arxiv.org/html/2609.13439#S1.SS3.SSS1.p1.1)\.
- Oliveira and Sangiovanni\-Vincentelli \(1993\)A\. L\. Oliveira and A\. L\. Sangiovanni\-VincentelliLearning complex boolean functions: algorithms and applications\.InAdvances in Neural Information Processing Systems 6,pp\. 911–918\.Cited by:[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Owenset al\.\(2008\)J\. D\. Owens, M\. Houston, D\. Luebke, S\. Green, J\. E\. Stone, and J\. C\. PhillipsGPU computing\.Proceedings of the IEEE96\(5\),pp\. 879–899\.External Links:[Document](https://dx.doi.org/10.1109/JPROC.2008.917757)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- O’Donnell \(2014\)R\. O’DonnellAnalysis of boolean functions\.Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/CBO9781139814782)Cited by:[§2\.2](https://arxiv.org/html/2609.13439#S2.SS2.p3.1)\.
- Perreaultet al\.\(2026\)V\. Perreault, K\. Inoue, R\. Labib, and A\. HertzNeural logic networks for interpretable classification\.Transactions on Machine Learning Research\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1),[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Petersenet al\.\(2022\)F\. Petersen, C\. Borgelt, H\. Kuehne, and O\. DeussenDeep differentiable logic gate networks\.Advances in Neural Information Processing Systems35,pp\. 2006–2018\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Pietroskiet al\.\(2009\)P\. Pietroski, J\. Lidz, T\. Hunter, and J\. HalberdaThe meaning of “most”: semantics, numerosity and psychology\.Mind & Language24\(5\),pp\. 554–585\.External Links:[Document](https://dx.doi.org/10.1111/j.1468-0017.2009.01374.x)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p2.1)\.
- Prairie and Tan \(2026\)A\. Prairie and L\. TanBoosting with list\-decodable codes\.InProceedings of the Thirty\-Ninth Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.336,pp\. 5377–5396\.Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p2.1)\.
- President of the Russian Federation \(2024\)President of the Russian FederationOn amendments to presidential decree no\. 490 of october 10, 2019, “on the development of artificial intelligence in the russian federation,” and to the national strategy approved by that decree\.Russian Federation\.Note:February 15, 2024External Links:[Link](https://www.kremlin.ru/acts/bank/50326)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Qiaoet al\.\(2023\)L\. Qiao, W\. Wang, S\. Dasgupta, and B\. LinRethinking logic minimization for tabular machine learning\.IEEE Transactions on Artificial Intelligence4\(5\),pp\. 1129–1140\.External Links:[Document](https://dx.doi.org/10.1109/TAI.2022.3224415)Cited by:[§1\.3\.1](https://arxiv.org/html/2609.13439#S1.SS3.SSS1.p1.1)\.
- Ramírez \(2018\)I\. RamírezBinary matrix factorization via dictionary learning\.IEEE Journal of Selected Topics in Signal Processing12\(6\),pp\. 1253–1262\.External Links:[Document](https://dx.doi.org/10.1109/JSTSP.2018.2875674)Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p2.1)\.
- Ribeiroet al\.\(2016\)M\. T\. Ribeiro, S\. Singh, and C\. Guestrin“Why should i trust you?”: explaining the predictions of any classifier\.InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 1135–1144\.External Links:[Document](https://dx.doi.org/10.1145/2939672.2939778)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.1)\.
- Rudell and Sangiovanni\-Vincentelli \(2004\)R\. L\. Rudell and A\. Sangiovanni\-VincentelliMultiple\-valued minimization for pla optimization\.IEEE Transactions on Computer\-Aided Design of Integrated Circuits and Systems6\(5\),pp\. 727–750\.Cited by:[§C\.1](https://arxiv.org/html/2609.13439#A3.SS1.p3.1),[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p2.1)\.
- Rudell and Sangiovanni\-Vincentelli \(1987\)R\. L\. Rudell and A\. L\. Sangiovanni\-VincentelliMultiple\-valued minimization for PLA optimization\.IEEE Transactions on Computer\-Aided Design of Integrated Circuits and Systems6\(5\),pp\. 727–750\.External Links:[Document](https://dx.doi.org/10.1109/TCAD.1987.1270318)Cited by:[§1\.3\.1](https://arxiv.org/html/2609.13439#S1.SS3.SSS1.p1.1)\.
- Sapraet al\.\(2003\)S\. Sapra, M\. Theobald, and E\. M\. ClarkeSAT\-based algorithms for logic minimization\.InProceedings of the 21st IEEE International Conference on Computer Design \(ICCD\),pp\. 510–\.External Links:[Document](https://dx.doi.org/10.1109/ICCD.2003.1240948)Cited by:[§1\.3\.1](https://arxiv.org/html/2609.13439#S1.SS3.SSS1.p1.1),[§2\.3](https://arxiv.org/html/2609.13439#S2.SS3.p1.1)\.
- Sasao \(1993\)T\. SasaoAND\-EXOR expressions and their optimization\.InLogic Synthesis and Optimization,T\. Sasao \(Ed\.\),The Kluwer International Series in Engineering and Computer Science, Vol\.212,pp\. 287–312\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4615-3154-8%5F13)Cited by:[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Schapire \(1990\)R\. E\. SchapireThe strength of weak learnability\.Machine Learning5\(2\),pp\. 197–227\.External Links:[Document](https://dx.doi.org/10.1023/A%3A1022648800760)Cited by:[§1\.3\.2](https://arxiv.org/html/2609.13439#S1.SS3.SSS2.p1.1)\.
- Schnapp and Sabato \(2021\)S\. Schnapp and S\. SabatoActive feature selection for the mutual information criterion\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.35,pp\. 9497–9504\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Secretaría de Gobernación \(2024\)Secretaría de GobernaciónIniciativa que expide la ley nacional que regula el uso de la inteligencia artificial\.Secretaría de Gobernación, Gobierno de México\.Note:Sistema de Información LegislativaPublicada en la Gaceta Parlamentaria el 13 de diciembre de 2024External Links:[Link](https://sil.gobernacion.gob.mx/Librerias/pp_ContenidoAsuntos.php?Clave=4825444)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Selsamet al\.\(2019\)D\. Selsam, M\. Lamm, B\. Bünz, P\. Liang, L\. de Moura, and D\. L\. DillLearning a SAT solver from single\-bit supervision\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=HJMC_iA5tm)Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Servedio \(2004\)R\. A\. ServedioOn learning monotone dnf under product distributions\.Information and Computation193\(1\),pp\. 57–74\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Sobol \(2001\)I\. M\. SobolGlobal sensitivity indices for nonlinear mathematical models and their monte carlo estimates\.Mathematics and computers in simulation55\(1\-3\),pp\. 271–280\.Cited by:[§1\.3\.4](https://arxiv.org/html/2609.13439#S1.SS3.SSS4.p1.1)\.
- Soegenget al\.\(2026\)H\. F\. Soegeng, S\. K\. Modi, and T\. PeyrinTT\-Sparse: learning sparse rule models with differentiable truth tables\.arXiv preprint arXiv:2603\.07606\.Note:To appear in ICML 2026External Links:[Document](https://dx.doi.org/10.48550/arXiv.2603.07606)Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1),[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Sundararajanet al\.\(2017\)M\. Sundararajan, A\. Taly, and Q\. YanAxiomatic attribution for deep networks\.InProceedings of the 34th International Conference on Machine Learning,Vol\.70,pp\. 3319–3328\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.1)\.
- Szymanik and Zajenkowski \(2010\)J\. Szymanik and M\. ZajenkowskiComprehension of simple quantifiers: empirical evaluation of a computational model\.Cognitive Science34\(3\),pp\. 521–532\.External Links:[Document](https://dx.doi.org/10.1111/j.1551-6709.2009.01078.x)Cited by:[§1\.2](https://arxiv.org/html/2609.13439#S1.SS2.p2.1)\.
- Tabassi \(2023\)E\. TabassiArtificial intelligence risk management framework \(AI RMF 1\.0\)\.Technical reportTechnical ReportNIST AI 100\-1,National Institute of Standards and Technology\.External Links:[Document](https://dx.doi.org/10.6028/NIST.AI.100-1)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- Telgarsky \(2015\)M\. TelgarskyRepresentation benefits of deep feedforward networks\.arXiv preprint arXiv:1509\.08101\.Cited by:[§F\.3\.2](https://arxiv.org/html/2609.13439#A6.SS3.SSS2.Px1.p1.1)\.
- Treasury Board of Canada Secretariat \(2026\)Treasury Board of Canada SecretariatAlgorithmic impact assessment tool\.Government of Canada\.External Links:[Link](https://www.canada.ca/en/government/system/digital-government/digital-government-innovations/responsible-use-ai/algorithmic-impact-assessment.html)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p2.1)\.
- van der Vaart and Wellner \(2023\)A\. W\. van der Vaart and J\. A\. WellnerWeak convergence and empirical processes: with applications to statistics\.2 edition,Springer Series in Statistics,Springer,Cham\.External Links:ISBN 978\-3\-031\-29038\-1,[Document](https://dx.doi.org/10.1007/978-3-031-29040-4)Cited by:[§4\.1\.1](https://arxiv.org/html/2609.13439#S4.SS1.SSS1.p2.1)\.
- Vardiet al\.\(2022\)G\. Vardi, G\. Yehudai, and O\. ShamirOn the optimal memorization power of reLU neural networks\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=MkTPtnjeYTV)Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.2)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. PolosukhinAttention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p1.1)\.
- Veličkovićet al\.\(2022\)P\. Veličković, A\. P\. Badia, D\. Budden, R\. Pascanu, A\. Banino, M\. Dashevskiy, R\. Hadsell, and C\. BlundellThe CLRS algorithmic reasoning benchmark\.InProceedings of the 39th International Conference on Machine Learning,pp\. 22084–22102\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Veličković and Blundell \(2021\)P\. Veličković and C\. BlundellNeural algorithmic reasoning\.Patterns2\(7\)\.Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p1.1)\.
- Veličkovićet al\.\(2020\)P\. Veličković, R\. Ying, M\. Padovano, R\. Hadsell, and C\. BlundellNeural execution of graph algorithms\.InInternational Conference on Learning Representations,Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1)\.
- Vershynin \(2020\)R\. VershyninMemory capacity of neural networks with threshold and rectified linear unit activations\.SIAM Journal on Mathematics of Data Science2\(4\),pp\. 1004–1033\.Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.2)\.
- Yue and Jha \(2024\)C\. Yue and N\. K\. JhaLearning interpretable differentiable logic networks\.IEEE Transactions on Circuits and Systems for Artificial Intelligence1\(1\),pp\. 69–82\.External Links:[Document](https://dx.doi.org/10.1109/TCASAI.2024.3462303)Cited by:[§1\.3\.3](https://arxiv.org/html/2609.13439#S1.SS3.SSS3.p2.1),[§1\.3\.5](https://arxiv.org/html/2609.13439#S1.SS3.SSS5.p1.1)\.
- Zhanget al\.\(2017\)C\. Zhang, S\. Bengio, M\. Hardt, B\. Recht, and O\. VinyalsUnderstanding deep learning requires rethinking generalization\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.13439#S1.p3.2)\.