Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees
Authors: Itamar Hadad
Guy Katz
Shahaf Bassan
Venue: ICLR 2026 Poster (2026)
Keywords: interpretability
mechanistic interpretability
circuit discovery
Primary area: interpretability and explainable AI

Abstract: *Automated circuit discovery* is a central tool in mechanistic interpretability for identifying the internal components of neural networks responsible for specific behaviors. While prior methods have made significant progress, they typically depend on heuristics or approximations and do not offer provable guarantees over continuous input domains for the resulting circuits. In this work, we leverage recent advances in neural network verification to propose a suite of automated algorithms that yield circuits with *provable guarantees*. We focus on three types of guarantees: (1) *input domain robustness*, ensuring the circuit agrees with the model across a continuous input region; (2) *robust patching*, certifying circuit alignment under continuous patching perturbations; and (3) *minimality*, formalizing and capturing a wide array of various notions of succinctness. Interestingly, we uncover a diverse set of novel theoretical connections among these three families of guarantees, with critical implications for the convergence of our algorithms. Finally, we conduct experiments with state-of-the-art verifiers on various vision models, showing that our algorithms yield circuits with substantially stronger robustness guarantees than standard circuit discovery methods, establishing a principled foundation for provable circuit discovery.

Published as a conference paper at ICLR 2026
FORMAL MECHANISTIC INTERPRETABILITY: AUTOMATED CIRCUIT DISCOVERY WITH PROVABLE GUARANTEES
Itamar Hadad', Guy Katz', Shahaf Bassan'
School of Computer Science and Engineering, The Hebrew University of Jerusalem i amar hadaddmaiil muiji.... ac. i1, k.kazmmaail hujji. ac il,
shahaf bassan htw.mmaii....aaaaaeaa.eeeeeeeeee huji.ac.il
ABSTRACT
Automated circuit discovery is a central tool in mechanistic interpretability for identifying the internal components of neural networks responsible for specific behaviors. While prior methods have made significant progress, they typically depend on heuristies approximations and do not offer provable guarantees over continuous input domains for the resulting circuits. In this work, we leverage recent advances in neural network verification to propose suite of automated algorithms that yield circuits with provable guarantees. We focus on three types of guarantees: input domain robustness, ensuring the circuit agrees with the model across a continuous input region; (ii) robust patching, certifying circuit alignment under continuous patching perturbations; and (3) minimality, formalizing and capturing a wide array of various notions of succinctness. Interestingly, we uncover a diverse set of novel theoretical connections among these three families of guarantees, with critical implications for the convergence of our algorithms. Finally, we conduct experiments with state-of-the-an verifiers on various vision models, showing that our algorithms yield circuits with substantially stronger robustness guarantees than standard circuit discovery methods - establishing principled foundation for provable circuit discovery.
INTRODUCTION
The rapid rise of neural networks, driven by transformative architectures such as Transformers, has reshaped both theory and applications. Alongside this revolution, interpretability has become a central research direction (Zhang al.) [202]] Räuker et al. 2023); and more recently, efforts have focused on mechanistic interpretability (MI), which aims to reverse-engineer neural networks into human-underssandable components and functional modules (Olah et al. 2020 Olah 2022 Zhao et al.)
2024). MI offers fine-graine nre-grained interpretability that serves various purposes, including transparency, trustworthiness, safety, and other applications (Bereska Gavves
2024
Zhou al. 2025).
A central open challenge in MI is circuit discovery (Olah et al. 2020). which seeks to identify subgraphs within neural networks, called circuits, that drive specific model behaviors. Recent works propose varied approaches (Wang et al. 2023] Conmy et al. 2023 Rajaram et al. 2024). differing by domain (text vs. vision), patching methods (zero. mean, sampling), and the balance between manual and automated steps. However, despite substantial progress, most current circuit discovery algorithms remain heuristic or approximate, without rigorous guarantees of circuit faithfulness, particularly under continnous perturbation domains (Adolfi al. 2025 Miller et al. 2024 Méloux et al., (2025). This limitation is concerning: even small perturbations can break circuit faithfulness, and since circuit discovery is tied safety considerations (Bereska & Gavves 2024), such guarantees essential.
To address these concerns, we introduce a novel algorithmic framework that builds recent and exciting advances in the emerging field of neural network verification (Wang) (et al., 2021] Zhou et al,, 2024) Brix et al. 2024) Kotha et al. 2023 Ferrari et al., (202)), enabling the derivation of circuits with provable guarantees across continuous domains of interest.
Our Contributions.

---

Published as a conference paper at ICLR 2026
1.1 THEORETICAL CONTRIBUTIONS
We formalize a set of novel provable guarantees for circuit discovery that hold strictly over entire continuous domains. These include: (i) imput-domen robustness, ensuring circuits remain faithful across continuous input regions; (ii) aatching-doman robustness, addressing criticisms of sampling- sampling-based based ablation; and (iii) broad family of minimality guarantees, extending earlier notions to include quasí- local-, subset-, and cardinal-minimaligy
We present novel theoretical proofs that reveal strong connections between these three families of guarantees. At the core is the circuil monotonicity property, which underpins min- imality guarantees for optimization algorithms and clarifies the conditions under which they hold. We also establish a crucial duality between circuits and small "blocking" subgraphs, enabling the efficient discovery of circuits with much stronger minimality guarantees.
1.2 EMPIRICAL CONTRIBUTIONS
We propose framework for encoding both input- and patching siiching-robustness guarantees in neural networks and their circuits, using technical siamese encoding of the network with its associated circuit or patching-domain, which enables certifying the desired properties.
We introduce set of novel automated algorithms that preserve the invariants of the robust- guarantees and prove that each converges to circuits meeting our various minimality criteria. These algorithms enable a trade-off between computational cost and the degree of minimality achieved in the resulting circuits.
We conduct extensive experiments with a-B-CROWN, the state-of-the-are neural network verification, to derive circuits with input, patching, and minimality guarantees. These are evaluated on standard neural vision models commonly used in the neural network verification literature. Compared to sampling-bass -ased approaches, framework certifies robustness, whereas even infinitesimal perturbations break the faithfulness of sampling- sumpling-based circuits.
Overall, we believe these contributions mark a significant step forward in establishing both theoretical and empirical foundations for circuit discovery with provable guarantees, paving the way for a wide range of future research directions.
PRELIMINARIES
2.1 NOTATION
Let fG IR" + Rd denote a neural network, with G (V, F) representing its computation graph. The precise structure of CC-that is, what each node and edge correspond (e.g., neurons, attention heads, positional embeddings, convolution filters)- - is determined both by the network's 's architecture and by the level of granularity chosen by the user. A circuit C' is defined as subgraph C C G, consisting of components hypothesized to drive the model's behavior on a task. Each such circuit naturally induces a function fc IR" + Rd. obtained by restricting fo the components in C.
In circuit discovery, the complement C = G C is often fixed to constant activations, practice known as patching, with variants such as pero-patching or mean-pater -etanppachiin..... Let fo have I. N layers with activation spaces V, for E [L]. and let X' C R be an input domain. For x E X, denote the activations at layer i as h; (x( E V,, and the reachable activation space as Hc(X) / (x),..,, (x))
E X) C V1 ... Vt, We write Hx((')) for the partial reachable activation space over C. For partial activation assignment Hzr(2)) write fc(x C a) to denote inference through (x), constructed from the components of C, while fixing the activations of C to the values a.
2.2 NEURAL NETWORK VERIFICATION
Consider generic neural network fo with arbitrary element-wise nonlinear activations. Many tools exist to formally verify properties of such networks, with adversarial robustness being the most studied (Brix et al. 2024). Formally, the neural network verification problem be stated follows:
2

---

Published as a conference paper at ICLR 2026
Neural Network Verification (Problem Statement):
Input: A neural network model fa. for which := fx(x), with an imput specification t'in (x), and an wnsafe output specification Vaul (y)- Output: No, there exists some x E IR" such that t/an (x) and (y) both hold, and Yes otherwise.
A variety of off-the-shelf neural network verifiers have been developed (Brix et al. 2024). When the input constraints e/in (X), output constraints (y), and model fc are piecewise-lined linear (c.g.. ReLU activations), the verification problem can be solved exactly (Katz al., 2017). In practice, it is often relaxed for efficiency, and the output enclosed within bounds that account for approximation errors.
3
PROVABLE GUARANTRES FOR CIRCUIT DISCOVERY
3.1 INPUT DOMAIN GUARANTEES
In this subsection, introduce the first set of guarantees that algorithms are designed to satisfy specifically, provable robustmess against input perturbations. A central challenge when evaluating circuit's faithfulness is that, even if it matches the model one point a finite set of points, small input perturbations can quickly break this agreement. To overcome this limitation, our first definition considers circuits that are not only faithful to the model on a discrete set of points but are also provably robust across an entire infinite continuous set of inputs.
Definition (Input-robust circuit). Given a neural network Ja and a union of continuous domains Z S R" (e.g.. a union of lp ep-balls of radius Ep around a set of discrete points {xx V say that subgraph C S G is an input-robust circuit with respect (fG, 2), , fixed patching vector applied to the complement set C = G C, and a tolerance level 5 E Rt, if and only if:
k
VW E 2 =
U
B (x)).
[15c(z C = =a) - -c(()))lpp S 5.
(I)
j=1
s.l. BP (xx) = (zj
R" ||z -xy1 S cp)
Certifying circuit input robustness via verification. Neural network verification properties are typically encoded a single model fa, while the circuit input robustness property (Def. ( requires evaluating both the model graph G and circuit C G. To address this, we introduce a novel method to certify the property in Def. Uusing a siamese encoding of the network fa. Specifically, we duplicate the circuit C" : and "stack" it with to form a combined model GUC" with a shared input layer. This induces a function [(GUCY) T 2d The activations of the non-circute components in the duplicate, C ==
Medal
Teyaur
Clncalenated ligis
foucyff [ C"-ol
Cheoul e
Figure 1: Illustration of the Siamese encoding for certifying the guarantee in Def. []
G i\Co C², are fixed constant a, so for any z E IR." inference is f(Guan (z C a), enabling direct certification of Def. over the combined model. The input constraint th (x) bounds x within 2, while the output constraint Moou (y) bounds the distance measure between the logits of C" and G. Further details of this encoding appear in Appendix E
3.2 PATCHING DOMAIN GUARANTEES
central challenge in circuit discovery lies in deciding how to assign values to the complementary activations of a circuit a process known as patching. The goal of patching is to replace these values to isolate the circuit's contribution. Prior work has examined several approaches, including zero-patching, which has been criticized as arbitrary since such values may be out-of-distribution unseen during training (Conmy et al., (2023) Wang et al., 2023). Other strategies include mean- value patching (Wang al.) 2023) and sampling from discrete input distributions (Conmy et al.) 2023). Yet, these methods still rely on evaluating complementary activations over a discrete set of sampled inputs, which may fail generalize in continuous domains: even small perturbations in the
3

---

Published as a conference paper at ICLR 2026
patching scheme undermine circuit's faithfulness. By analogy input-robustner patching-robustee robustness:: the requirement that a circuit preserve its faithfulness across an entire provable range of feasible perturbations to the complementary activations over a continuous imput domain.
introduce
Definition (Patching-robus' circuit). Given a neural network fG. a continuous input domain 2 S R" and reference set of inputs {x S X, we say that C " G is patching- rrbbust circuit with respect to (Ja, 2) and tolerance level 8 RR, iift for every xj in {xz}}=1;
Ya E H2)
[[fo(x, C a) (x (x)) S
Certifying circuit patching robustness via verifi- cation. Analogous to input robustness, we introduce here novel method to certify the property in 2et using a siamese encoding of fc. Concretely, we du- plicate the circuit C' == C' and "stack" it with G. but now G and C' have disjoint input domains, yield- ing ((GUC : R + Rdd We connect C' and G by fixing the activations of C' to those attained by (z)()) when evaluating fz). Thus, inference for (x, z) E R22n is given by [(GuCr)(X C' = (zz(z)) We then set input constraints to bound within 2. and output constraints to limit the distance ||-1Ip be-
Midde
Inpurt
Logits
(xausy())) T Ragi))
Cinaui
Figure 2: Illustration of the Siamese encoding for certifying the guarantee in Def. - Gray neurons denote non-circuit units whose activa- tions are patched with those of the full model.
tween the logits of C" and G. Further details appear in Appendix F We remark that input robustness and patching robustness can also be certified simultane-
ously within a single verification query by extending the siamese encoding (see Appendix G
4 FROM CIRCUITS TO MINIMAL CIRCUITS
common convention in the literature is that smaller circuits (i.e., lower circuit size) are generally
considered more interpretable than larger ones Mueller et al. [025 Adolfi et al. 2025 Chowdhary
al. 2025 Wang et al. 2023] Bhaskar al. 2024| Shi et al.
2024
Conmy et al. (023). This
makes minimality an important additional guarantee (Adolfi et al.
2025
Chowdhary al. 2025 Shi
ct al. 2024 Mueller et al. 2025). While many works have pursued minimal circuits, recent studies high that "minimality itself can take different forms (Adolfi et al. 2025), ranging from the weak notion of quasi- minimmlitt to the strong notion of cardinal-mnimaaiity In this work, we extend this spectrum to four main forms and provide rigorous proofs linking them to different optimization algorithms.
4.1 MINIMALITY GUARANTEES
In this subsection, introduce four central notions of minimality. Since minimality must be defined rel- ative what qualifies we begin by specifying a general faithfulness pred- icate, @CC, G). Given a circuit C S G within the computation graph G of a model fa. (CC, G) re- turns True if C' faithful under some condition of interest, and False otherwise. Instances of & may include standard sampling-bar based measures used in circuit discovery, such as requiring the mean-squared error or Kl--divergence between and G remain below a threshold (Conmy et al. 2023). Altema- tively, & can reflect our provable measures that hold across continuous domains (Section 3 e.g., defining (C,, G) to require input and/or patching robustness.
"valid" faithful circuit,
11 29
C
Ug = xn (8
(=
Figure 3: A toy Boolean circuit.
Consider, for example, toy Boolean circuit pre- sented in Fig. 3 as a running example. For sim- plicity, we assume that each node in the eircuit corresponds to component of the model.
4

---

Published as a conference paper at ICLR 2026
The network takes inputs 22) E {0, 1] whose outputs aggregated by XOR, yielding (2)) = v1 @ 02 + ... @ U/ = 22, since
fo(x1,02) ;= 22 1 2 + 21 @ (a) @22)
@ (a) (22)
+ (22)
= x2 + (z) (r1
@ [ (22))
@ (ar @42) + (22 = 22.
For simplicity, we set the faithfulness predicate to consider the very strong condition of strict equality between the circuit and the model for every boolean input. In other words, for all æ1 and 22 in (0, 10 it holds that ( G) == fc(21,02) fa(11 x2) this example appears in Appendix C.3
x2. A more detailed description of
We begin with the weakest form of minimality and proceed step by step until reach the strongest. The first notion, muani-minimallty, introduced by (Adolfi et al., 2025), defines C' as a subset that includes "breaking point": some component that, when removed, breaks the circuit's faithfulness:
Definition 3 (Quasi-Minimal Cireuit), Given G, quasi- minimal circuit C S G concerning 4 is circuit for which (C,, G) holds ("C' is faithful"), ), and there exists some element (i.e., nodeledge) in C. for which (C (i), false.
fc. but In our running example C' = {uI..... U5 quasi-minimal: satisfies U1 @ ..... 0 removing some essential node (e.g.. 21) breaks this equality. However, we observe that the quasi- minimality notion of (Adolfi et al., 2025) can be strengthened: instead of requiring single breaking point, one can demand that every component serves as one. Following conventions in the optimization literature, we refer to this stronger notion as local minimality.
Definition (Locall-Miiimal Minimal Circuit), Given G, a locally-minimal circuit C G concerning 4, is circuit for which (CC, G) holds, for any element in C, 4(C') \ {i), G) is false.
In example, C {ui, U2, U3} is locally minimal, as the predicate holds for {ui, U2 U3 but does not hold for (t1, ]. (11, 02). and (V2, v3). However, while local-minimality is stronger than quasi- minamiimnnimlity.. it still has a limitation. Although removing any single component from the circuit C' breaks it, removing multiple components may still leave C valid, giving misleading sense of minimality. For instance, in our locally minimal circuit C {uI, U2, v3). observe that while removing any single component (i.e., U1, U2, or Ug) breaks faithfulness, removing the pair {12, Us} (i.e., keeping only v1) nonetheless results in a faithful circuit. To address this, we define stronger notion: subset- minimality, which requires every subset of components to be breaking point.
Definition 5 (Subset-Minima) Circuit). Given G, subset-minimal circuit C C G concerning b, is a circuit which (CC, G) holds true, and for any subgraph S Ç C. &CC \ S, G) is false.
In the running example, = {12, 24 } is a moiimmll circuit, as U/2 + 04 = I1 2 (I) + @x2) = x2. since every strict subset (12). {ra}) fails to compute fc. We note that even this significantly stronger notion of bobsst-minimalityy does not necessarily yield subsets of the absolute lowest cardinality. To address this limitation, the final notion introduces the strongest form: cardinally-mnnimal which corresponds to the global optimum of minimality.
-inimal circuit,
Definition 6 (Cardinally--M) Muadinally-Minimal Circuit), Given G, a cardinally-minimal a circuit for which (CC, G) true, and has the lowest cardinality |C| (i.e., there is no circuit C" C G for which (CC', G) is true and |C"| < (C)).
minimal circuit C S G concerning
Here, {ug} } is cardinally minimal, since 01 = x22 is functionally equivalent to fo and no smaller faithful circuit exists.
4.2 ALGORITHMS FOR LOCAL AND QUASI MINIMAL CIRCUITS
In this subsection, we present optimization algorithms for discovering circuits with provable guar- antees. Building on prior circuit discovery frameworks, we show how modifying or validating optimization objectives changes the resulting guarantees. We also establish theoretical links between objectives based on continuous robustness guarantees and different notions of minimality. We begin with standard greedy algorithm (Algorithm
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 Greedy Circuit Discovery Iterative Search
1: Input Model Sa, circuit faithfulness predicate &
2: C ( G under some given element ordering (e.g., reverse topological sort)
3: for all i C' do
4: if ((C)) [i]. G) then
5:
C+ C
6: end
7: end for
8: return C
Algorithm| I describes standard greedy procedure that starts from the full model graph G and itera- tively removes components as long as the faithfulness predicate holds. While this structure underlies many circuit discovery methods, we also consider an exhaustive variant, given Algorithm in Appendix which repeatedly iterates over the remaining components and attempts further removals, stopping only when every single component is critical. This guarantees the following:
Proposition 1. Given any model fo and faithfulness predicate o Algorithm 7 visits munsi- circuit and Algorithm 3 converges to a locally-minimal minimal circuit C, both with respect to 4.
We note that each evaluation of ((C)) { G) may be costly, depending on the predicate & (e.g.. certifying imput patching robustness). To mitigate this, may use lighter notion of minimality the quasi-minimal circuits of (Adolfi et al. linear, number of invocations. For completeness, procedure, provided as Algorithm 4 in Appendix C Algorithm 4 follows a procedure similar to Algorithm|] [ but employs a binary rather than iterative search. As result, it yields a weaker notion of minimal circuits, while requiring fewer queries. We can therefore establish the following proposition:
2025) - -which require only a logarithmic, rather than formally present and extend their sinary-search
Proposition 2. While Algorithun converges to a quasi- minsial circuit using Ollog GI) evaluations of (CC G) Adolfi al. (025). Algorithm 7 visits a quasi- mmasi- circuit with O(GG)) evaluations, and Algorithm 3 converges to a locally-minimal circuit using (((G)2) evaluations.
Finally, we note that Algorithms I and 4 converge only to relatively "weak" forms of minimality, Even the stronger mitammiiiimlltyyy guarantee of Algorithm 3 can fall short: while every single- element removal C' \ {i] breaks faithfulness, removing two elements simultaneously, C' \ [i,j]. may still yield a faithful circuit. This undermines C's "minimality" and shows that neither algorithm ensures the stronger notion of subset-minimality.
Proposition 3. There exist infinitely many configurations of fa, and 4 for which Algorithms and 4 do not converge to a subset-minine circuit C concerning T.
3
4.3 THE CIRCUIT MONOTONICITY PROPERTY AND ITS IMPACT ON MINIMALITY
To address the issue of algorithms converging to "bad" local minima, we identify a key property of the faithfulness predicate & with crucial implications for stronger minimal subsets - monotonicity:
Definition 7. We say that a circuit faithfulness predicate is monotonic iff for any C C" C G it holds that if (C,, G) is true, then (CC", G) is true.
Intuitively, monotonicity means that once (CC, G) holds for circuit C' (i.e., it is "faithful"), it will keep holding as elements are added. In other words, enlarging the circuit never breaks faithfulness. This property is essential for Algorithm I as it underpins the stronger minimality guarantee:
Proposition 4. If & is monotonic, then for any model fc. Algorithm converges to subset-minimal circuit C. concerning +b
The condition of monotonicity. Interestingly, we establish a novel connection between the guarantees on the input and patching domains outlined in Section 3 and the monotonic behavior of 4:
Proposition 5. Let (CC, G) denote validating whether C. is robut- concerning (fG. Z) (Def and simultaneously patching aathuing-robust robust concerning (fa. Z') (Def. 2). Then if Z S Z' and Ho 2 is
closed under concatenation, t is monotonic.

---

Published as a conference paper at ICLR 2026
shows that if the patching domain 2' subsumes the imput domain 2, and the activation space Ho(2 2' is closed under concatenation, i.c.. concatenating any two partial activations
Intuitively, Proposition 5
remains within Ho Z then the faithfulness predicate & is monotonic. This introduces class of evaluation conditions that are monotonic by construction, yielding stronger minimal circuits.
Proposition 6. If the condition (CC G) is set to validating whether C. is input-robust concerning (fa, Z) (Def. 7 and also patching-robus rrobust with respect to (fa, 2") (Def. 2. then if Z C Z' and
Ha(2') (2) is closed under concatenation, Algorithm [ converges mubset-minimal circuit.
4.4 FROM SUBSET-MINIMAL CIRCUITS TO CARDINALLY-MINNNA CIRCUITS
Although the monotonicity of & provides stronger guarantee of subset- subset-minimality. it still does not ensure convergence to the globally minimal circuit (i.e., a cardinally-miniine circuit). naive approach to obtain such circuits is to enumerate all C' G, verify (CC, G), and choose the one with the lowest cardinality [C', but this quickly becomes intractable even for modestly sized graphs.
Exploiting circuit blocking-set duality for efficient approximation of perdinally-minineg circuits. In this subsection, we leverage the idea that neural networks often contain small "circuit blocking- sets" subgraphs C" C G whose altered activations break the faithfulness of any circuit C' that excludes them. We prove a duality between circuits (under monotone faithfulness predicates) and these blocking-sets enabling a new algorithmic construction that approximates exactly recovers - cardinally minimal circuits far more efficiently than naive search. Formally, for This
and sometimes
fc and h circuit blocking-sel set any C' C such that ((C' C", G) fails for all C' yields duality grounded in a minimum-hittee saitt--hittinn-eee set (MHS) relation between circuits and blocking-sets:
Proposition 7. Given some model fc, and monotonic predicate 4 the MHS of all circuit blocking- sets concerning & is cardinally minimal circuit C for which (CC, G) is true. Moreover, the MIS of all circuits C G for which (CC, G) is true, is cardinally minimal blocking-sel set w.rl
The definition of MHS, classic NP-Complete problem is given in Appendix B.7 This duality is powerful because, despite NP-completeness, MHS can often be solved efficiently in practice with modern solvers such as MILP MaxSAT (Ignatiev al. 2019a). Hence, similar dualities have already been central to formal reasoning and provable explamnailiiy methods (Bacchus & Katsirelos) 2015 Ignatiev et al. 2019c Bassan & Katz 2023 Liftiton et al. (016).. With this duality theorem in hand, we can design an algorithm that often computes (or approximates) cardinally minimal circuits:
Algorithm 2 Cardinally Minimal Circuit Approximation using MHS duality
1: Input model fa, faithfulness predicate क f'ux [|G]]
2: BlockingSets + 0
mmax do 4: c G, VU BlockingSets: = SuUgg S}
3: for t.
5:
for all S E C, do
parallelization
6: if DE-(G' \ S, G, then BlockingSets <- Blockinggets US
7:
8:
end if end for
9:
10:
C' MHHS(Bookinggeet.
11:
if (C, G)) then return C
12: end if
13: end for
Algorithm leverages Proposition 7 by iterating over blocking-sets in parallel and computing each set's MHS obtain a circuit C. This establishes lower bound on the cardinally minimal circuit and. through successive refinements, converges to the minimal one. While the number of blocking-sed subsets may be excessive in the worst case, in practice their size is often tractable (see Section 5) yielding a low fmux and enabling more efficient or closely approximate computation of cardinally minimal circuits. This is formalized in the following claim:
7

---

Published as a conference paper at ICLR 2026
Proposition 8. Given model fG. and monotonic predicate b, Algorithm 2 computes subset C whose size is a lower bound to the cardinally minimal circuit for which ( G) is true. For a large enough tmax value, the algorithm converges exactly to the cardinally minimal circuit.
EXPERIMENTAL EVALUATION
Experimental setup. We evaluate our method on standard benchmarks from the neural network
verification literature (Brix al. 2024 2023): (i) MNIST, (ii) CIFAR-10, (iii) GTSRB, and (iv) Tax-
input-explainabiiiyy studies (Wu et al. 2023a Bassan et al., 2025a)) For neural network verification, we use the state-of-the-art at C-CROWN verifier BBak et al. 2021 Müller et al. 2022a Brix et al. 2024); for MHS we use RC2 (ggatie al., (019a). For consistency,
iNet (a real-world dataset used in verification-
results model architectures from prior verification studies, particularly the neural network verification competition (VNN-COMP) (Brix et al. 2024);
evaluate
full architectural details appear in Appendix [ To balance circuit discovery difficulty and human interpretability, we chose the circuit granularity level to be neurons for MNIST and convolutional
filters for CIFAR-10, GTSRB, and TaxiNet. Both provable and sampling-bass basnd variants use the standard logit-difference metric (Conmy ct al. 2023). Further details are in Appendices
B and G
5.1 CIRCUIT DISCOVERY WITH INPUT-ROBUSTNES GUARANTEES
We begin by evaluating the continuous input robustness guarantees of our method. We compare two variants of Algorithm D (i) standard sampling-basee approach, where faithfulness assessed by applying the logit-differene predicate with tolerance on sampled inputs, and (ii) provable approach, which, via the siamese encoding of Section 3.1| certifies that the logit difference always remains below ó throughout the continuous input domain. For both methods, we report circuit size and robustness over the continuous input neighborhood across 100 batches (one circuit per batch). We set the input neighborhood using <p values aligned with VNN-COMP (Brix et al. 2024) (with variations in Appendix E) and adopt zero-patching in both settings. Results (Table I show that the provable method is slower, due to solving certification queries, yet achieves 100% robustness with comparable circuit sizes, whereas the sampling- An illustrative example appears in Figure 4
aaneling-based based baseline attains substantially lower robustness.
Table I:
Circuit results from Algorithm where & is defined either by bounding logit differences under input sampling or by verifying the bound using the siamese encoding.
Sampling-based based Circuit Discovery
Provably Input-Robust Circuit Discovery
Dataset
Time (s)
Size ((C)
Robustness (%)
Time (s)
Size ((C))
Robustness (%)
CIFAR-10
0.23 =0.52
16.47 +9.08
46.5 +5.0
2970.85 +874.23
19.18 110.16
100,0 +0.0
MNIST
0,31 10.89
12.56 12.30
19,2 14.0
611.93 197.14
15.84 122.3
100.0 10.0
GTSRB
0.11 +0.33
28.91 +4.69
27.6 +4.0
991.08 + 162.91
29.59 +4.45
100.0 +0.0
TaxiNet
0.01 +0.00
5.77 =0.80
9.5 #3.0
180.00 40.39
6.82 #0.46
100.0 +0.0
5.2
CIRCUIT DISCOVERY WITH PATCHING-ROBUSTNER GUARANTEES
Table 2: Circuit results from Algorithm| I
where & is defined either by bounding logit differences under zero patching, mean patching, by verifyying the bound using the siamese encoding.
Zero Patching
Mean Patching
Provably Patching- Robust Patching
Time (8)
Size (CC)
Rob, (%)
Time (s)
Size ((C))
Rob. (%)
Time (s)
Size ((C))
Rob. (%)
CI
0.1 = 0.3
65.1 +3.0
46.4 16.00
0.0 =0.0
64.1 +:366
33.3 +5..7
5408.5 + 1091.0
65.6 =1.6
100.0
MNIST
0.1 +033
20.0 =1.5
58.0 15.3
0.0 20.0
19.2 218
55.7 :5.3
714.9 1:207.1
17.0 =233
100.0
GISRB
0.3 10.9
32.6 14.2
38.0 144.
0.0 20.0
33.4 142
40.5 :14.5
2907.2 172177
34.3 14.1
100.0
TaxiNet
0.0 +0.1
588 =0.8
57.1 +5.0
0.0
5.4 +0.7
63.3
+4.9
175.7 +52.7
+..6
100.0
To assess patching robustness, we study three variants of Algorithm Coarrithmennii ennorrcing a bounded logit difference under different patching schemes: (i) zero-patching, (ii) mean-patching, and (iii) certified
8

---

Published as a conference paper at ICLR 2026
Convt
Conv2
Conv1
Conv2
Sampling
f
fc(z)
FC
Deer
2 BP
Conv1
Conv1
Conv2
Conv1
Conv2
Provably-
fi
robust
fc(z)
FC
Bird
E
BP
Figure 4: Examples of ResNet circuits at the filter level on CIFAR-IO. Filters are numbered within each layer, with non-circuit filters in gray and residual connections shown dashed lines. We compare circuits from the sampling-base discovery and the provably robust variant, highlighting components unique the provable circuit in green.
variant that, using a siamese encoding (Section 3.2, verifies the bound uniformly over continuous patching domain. Circuits found with zero or mean patching are then evaluated under the same cistinuous-domain criterion the certified setting. Results appear in Table Circuits found under standard patching (zero/mean) are sensitive to changes the patching domain and yield low robustness, whereas the verified method certifies this property and achieves 100% robustness. Despite the higher computational cost (due to the reliance on verification), the provable method delivers much stronger robustness comparable circuit sizes.
5.3 EXPLORING DIFFERENT MINIMALITY GUARANTEES OF CIRCUIT DISCOVERY
We experiment with the minimality guarantees from Sec. and their connection to the robustness and patching guarantees of Sec. 3 For the + predicate, we certify both input- and patching robustness using a couble-siamese encoding (Sec. 3.2 with environments Z Z', and run Alg. is run with fmax = 3, restricting the contrastive blocking-sel -et enumeration to sets of size at most three. Our experiments show that MHS size consistently below its MHS. In some runs, Alg. ciiccits meet the bound exactly, and some MHS circuits are certified as faithful (i.e., satisfying both input and patching robustness), as shown in Fig. 5a
Alg.
bounds circuit size, with no cireuit falling
We also note the efficiency- circuit size trade-off in Figure 5b the quasi-minimal (Alg. procedure terminates fastest but plateaus at larger sizes with weaker minimality: the iterative search (Alg I achieves smaller sizes (stronger minimality) at higher runtime; and the MHS (Alg. loop is slowest yet progressively approaches a cardinally minimal (optimal) circuit size.
6 RELATED WORK
Circuit discovery. Our work joins recent efforts on circuit discovery in MI (Olah et al.
2020 |Elhage
al.
202T [Dunefsky et (204), particularly those advancing automated algorithms (Conmy et
2023
Hsu et al. 2024). Other relevant avenues include metrics for circuit faithfulness (Marks ct al.
2025
Hanna et al. 2024), differing patching strategies (Jafari et al. 2025 Syed et al.) [024 Haklay
al.
2025
Miller al. 2024 Zhang & Nanda 2024). minimality criteria (Chowdhary et al. 2025
Wang et al.
2023). and applications (Yao et al. 2024 Sharkey et al. (025).
Theoretical investigations of MI. Several recent directions have examined other theoretical aspects of MI, often linked to circuit discovery. These include framing MI within a broader causal abstraction
framework (Geiger et al. 2025 2024). connecting it distributed alignment search (DAS) (Wul

---

Published as a conference paper at ICLR 2026
30
25
Esavay Sourch (Daun-Ntiki
Pastiid Caceel Hilli equilay Lea (yoa)
Brary Seurch (Dam8)
1.0
240
200
320
420
100
500
MHH Sinn
Elapoed Time (secondis)
(a) Circuit size against MHS size
(b) Circuit size over time
Figure 5: (a) Circuit size vs. MHS of blocking sets size, with the dashed equality line y=r as the lower bound. (b) Convergence of circuit size over the first 10 minutes; shaded region shows deviation.
ct al. 2023b Sun et al.
2025); analyzing learned eircuit logic through abstract interpretation from program analysis (Palumbo et al. 2025), proof theory (Miller et al. 2024 Wu et al. 2025), statistical
identification (Méloux et al. 2025). ), and complexity theory (Adolfi et al. 2025).
Neural network verification and formal explainability. Our certification of robustness guarantees (input and patching) builds on the rapid progress of neural network verification (Brix et al. 2024
Wang al. 2021 Zhou et al., 2024 Chiu et al. 2025 Müller et al. [022 (Sinhh et al. 2019). These advances have also been applied to certifying provable guarantees for input-based explainability notions (Wu et al. 2023a Bassan et al. 2025a Izza al. 2024 AAuemard et al.) 2022bb La Malfa
jet al. 2021) (often termed formal explainable Al (Marques-Si) Silva & Ignatiev 2022)). Our work is
the first employ neural network Verification based strategies for circuit discovery in mechanistic interpretability.
7 LIMITATIONS AND FUTURE WORK
limitation of our framework, shared by all methods offering robustness guarantees over continuous domains, is its reliance neural network verification queries. While current verification techniques remain limited for state-of-the-ar models, they are advancing rapidly in scalability (Brix et al.) 2024 Wang al., 2021 Zhou et al.) 2024). Our framework provides novel integration of such tools to mechanistic interpretability, enabling circuit discovery with provable guarantees. Hence, as verification methods continue scale, so will the reach of our approach, our extensive experiments are grounded in a- e-3-CROWN, the current leading verifier, and evaluated on standard benchmarks from the annual NN verification competition. Moreover, our novel theoretical results, covering guarantees over input domains, patching domains, and minimality, lay strong groundwork for future research on provable circuit discovery, including probabilistic and statistical forms of guarantees.
CONCLUSION
We introduce a framework for discovering circuits with provable guarantees, covering both (i) con- tinuous iiput-domain robustness, (ii) continuous aatching-domain robustness, and (iii) multiple forms minimality. Central to our approach is the notion of circuit monotonicity, which reveals deep theoretical connections between input, patching, and minimality guarantees, and underpins the convergence of circuit discovery algorithms. Our experiments, which leverage recent advancements in neural network verification, confirm that our framework delivers substantially stronger guarantees than standard sampling based approaches commonly used in circuit discovery. By bridging circuit discovery with neural network verification, this work takes novel step toward designing safer, more reliable circuits, and lays new theoretical and algorithmic foundations for future research in provable circuit discovery.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was partially funded by the European Union (ERC, VeriDeL. 101112713). Views and opinions expressed are however those the author(s) only and do not necessarily reflect those the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This research was additionally supported by grant from the Israeli Science Foundation (grant number 558/24).
REFERENCES
Federico Adolfi, Martina Vilas, and Todd Warcham. The Computational Complexity of Circuit Discovery for Inner Interpretability. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. In Proc. 27th European Conf. on Artifical Intelligence (ECAI), 2024.
Alaa Anani, Tobias Lorenz, Mario Fritz, and Bernt Schiele. Pixel-level Certified Explanations via Randomized Smoothing. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
M. Arenas, Barceló, M. Romero, and B. Subercaseaux. On Computing Probabilistic Explanations for Decision Trees. In Proc. 36th Conf. on Neural Information Processing Systems (NeurIPS), pp. 18695-28705 2022.
Marcelo Arenas, Daniel Baez, Pablo Barceló, Jorge Pérez, and Bernardo Subercaseaux. Foundations of Symbolic Languages for Model Interpretability. Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pp. 11690-11701, 2021.
G. Audemard, S. Bellart, L. Bounia, F. Koriche, J. Lagniez, and P. Marquis. On the Computa- tional Intelligibility of Boolean Classifiers. In Proc. 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp. 74 86, 2021.
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis. On Preferred Abductive Explanations for Decision Trees and Random Forests. In Proc. 31 Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 650, 2022a
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Maan-Marie Lagniez, and Pierre Marquis. Trading Complexity for Sparsity in Random Forest Explanations. In Proc. of the 36th AAAI Conf. on Artificial Intelligence, number 5, pp. 5461-5469, 2022b.
Gilles Audemard, Jean-Marie Lagniez, Pierre Marquis, and Nicolas Szezepanski. Computing Abductive Explanations for Boosted Trees. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 4699-4711, 2023.
Steve Azzolin, Sagar Malhotra, Andrea Passerini, and Stefano Teso Beyond Topological Self- Explainable GNNs: Formal Explainability Perspective. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Fahiem Bacchus and George Katsirelos. Using Minimal Correction Sets to More Efficiently Compute Minimal Unsatisfiable Sets. In Proc. 27th Int. Conf. Computer Aided Verification (CAV), pp. 70-86. Springer, 2015.
Stanley Bak, Changliu Liu, and Taylor Johnson. The Second International Verification of Neural Networks Competition (VNN-COMP 2021): Summary and Results. 2021. Technical Report. hittps://arkee 2109. 00498
P. Barceló, M. Monet, J. Pérez, and B. Subercaseaux. Model Interpretability through the Lens of Computational Complexity. In Proc. 34th Conf. on Neural Information Processing Systems (NeurIPS), pp. 15487-15498, 2020.
11

---

Published as a conference paper at ICLR 2026
S. Bassan and G. Katz. Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks. In Proc. 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 187-207, 2023.
S. Bassan, G. Amir, and G. Katz. Local vs. Global Interpretability: A Computational Complexity Perspective. In Proc. 41st Int. Conf. on Machine Learning (ICML), 2024.
Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Matthias Althoff, and Guy Katz. Explaining. Fast and Slow: Abstraction and Refinement of Provable Explanations. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025a.
Shahaf Bassan, Guy Amir, Davide Corsi, Idan Refacli, and Guy Katz. Formally Explaining Neural Networks Within Reactive Systems. In Proc. 23rd Int. Conf. on Formal Methods in Computer-Aided Design (FMCAD), pp. 1-13, 2023.
Shahaf Bassan, Guy Amir, Meirav Zehavi, and Guy Katz. What makes an Ensemble (Un) Inter- pretable? In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025b.
Shahaf Bassan, Ron Eliav, and Shlomit Gur. Explain Yourself, Briefly! Selt-Explaining Neural Networks with Coneise Sufficient Reasons. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025c.
Shahaf Bassan, Shlomit Gur, Sergey Zeltyn, Konstantinos Mavrogiorgos, Ron Eliav, and Dimosthenis Kyriazis. Self-Explaining Neural Networks for Business Process Monitoring. 2025d. Technical Report.
250:3..v:250... 18067,
Shahaf Bassan, Michal Moshkovitz, and Guy Katz. Additive Models Explained: A Computational Complexity Approach. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025e.
Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Volkan Şahin, Jan Kretinsky, Matthias Althoff, and Guy Katz. Provably Explaining Neural Additive Models. In Proc. 14th Int. Conf. Learning Representutions (ICLR), 2026a.
Shahaf Bassan, Xuanxiang Huang, and Guy Katz. Unifying Formal Explanations: A Complexity- Theoretic Perspective. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026b.
Leonard Bereska and Efstratios Gavves. Mechanistic Interpretability for AI Safety- Review. Transactions on Machine Learning Research (TMLR), 2024.
Adithya Bhaskar, Alexander Wettig, Dan Friedman, and Danqi Chen. Finding Transformer Cireuits with Edge Pruning. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pp. 18506-18534, 2024.
Guy Blanc, Jane Lange, and Li- Yang Tan. Provably Efficient, Succinet, and Precise Explanations. In Proc. 35th Conf. on Neural Information Processing Systems (NeurlPS), pp. 6129-6141, 2021.
Guy Blanc, Caleb Koch, Jane Lange, and Li- Yang Tan. A Query-Optimal Algorithm for Finding Counterfactuals. In Proc. 39th Int. Conf. on Machine Learning (ICML), pp. 2075-2090, 2022.
Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure, and Karim Tabia. ASTERYX: A model- Agnostic SaT-basEd appRoach for SYmbolic and Score-Based EXplanations. In Proc. 30th ACM Int. Conf. on Information & Knowledge Management (CIKM), pp. 120-129, 2021.
Ryma Boumazouza, Raya Elsaleh, Melanie Ducoffe, Shahaf Bassan, and Guy Katz. FAME: For- mal Abstract Minimal Explanation for Neural Networks. In Proc. 14th Int. Conf. on Learning Representations (ICLR), 2026.
Louenas Bounia. Enhancing the Intelligibility of Boolean Decision Trees with Concise and Reliable Probabilistic Explanations. In Proc. 20th Inf. Conf. on Information Processing and Management of Uncertainty in Knowledge-Bann Based Systems (IPMU), pp. 205-218, 2024.
Louenas Bounia. Using Submodular Optimization to Approximate Minimum-Siin Abductive Path Explanations for Bree-B Models. In Proc. 41st Conf. on Uncertainty in Artificial Intelligence (UAI), 2025.
12

---

Published as a conference paper at ICLR 2026
Christopher Brix, Mark Niklas Müller, Stanley Bak, Taylor T Johnson, and Changliu Liu. First Three Years of the International Verification of Neural Networks Competition (VNN-COMP). Int. Journal on Software Tools for Technology Transfer (STTT), 25(3):329-339 2023.
Christopher Brix, Stanley Bak, Taylor T Johnson, and Haoze Wu. The Fifth International Verification of Neural Networks Competition (VNN-COMP 2024): Summary and Results. 2024. Technical Report. https: /ttps://arxvv.. 2412. 19985.
Hong-Ming Chiu, Hao Chen, Huan Zhang, and Richard Y Zhang. SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Pratim Chowdhary, Peter Chin, and Deepernab Chakrabarty. K-MSHC: Unmasking Minimally Sufficient Head Circuits in Large Language Models with Experiments Syntactic Classification Tasks. 2025, Technical
12268
Arthur Conmy, Augustine Mavor-Parkers Aengus Lynch, Stefan Heimersheim, and Adrià Garriga- Alonso. Towards Automated Circuit Discovery for Mechanistic Interpretability. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 16318-16352, 2023.
A. Darwiche and Hirth. On the Reasons Behind Decisions. In Proc. 24th European Conf. on Artificial Intelligence (ECAT), pp. 712-720, 2020.
Adnan Darwiche. Logic for Explainable AI. In Proc. 38th ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-11, 2023.
Adnan Darwiche and Chunxi Ji. On the Computation of Necessary and Sufficient Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 5582-5591, 2022.
Alessandro De Palma, Greta Dolcetti, and Caterina Urban. Faster Verified Explanations for Neural Networks. 2025. Technical Report.
00164
Jacob Dunefsky, Philippe Chlenski, and Neel Nanda. Transcoders Find Interpretable LLM Feature Circuits. Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pp. 24375-24410. 2024.
Ruediger Ehlers. Formal Verification of Piece-Wiis Linear Ferd-Forward Neural Networks. In Proc. 15th Int. Symposium on Automated Technology for Verification and Analysis (ATVA), pp. 269-286. Springer, 2017.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A Mathematical Framework for Transformer Circuits. Transformer Circuits Thread, 1(1): 2021.
Thomas Fel, Mélanie Ducoffe, David Vigouroux, Rémi Cadène, Mikael Capelle, Claire Nicodème, and Thomas Serre. Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysis. In Proc. IEEE/CVF Conf. on Computer Vision and Pattern Recognition (CVPR), pp- 16153-16163, 2023.
Claudio Ferrari, Mark Niklas Mueller, Nikola Jovanović, and Martin Vechev. Complete Verification via Multi-Neuron Relaxation Guided aanechaandBounde In Proc. 10th Int. Conf. on Learning Representations (ICLR), 2022.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen. Petar Tsankov, Swarat Chaudhuri, and Martin Vechev, A12: Safety and Robustness Certification of Neural Networks with Abstract Interpretation. In Proc. 39th IEEE Symposium on Security and Privacy (S&P), pp. 3-18, 2018.
Atticus Geiger, Zhengxuan Wu, Christopher Potts, Thomas Ieard, and Noah Goodman. Finding Alignments Between Interpretable Causal Variables and Distributed Neural Representations. In Proc. 3rd Conf. on Causal Learning and Reasoning (CleaR), pp. 160-187, 2024.
Atticus Geiger, Duligur lbeling. Amir Zur, Maheep Chaudhary, Sonakshi Chauhan, Jing Huang, Aryaman Arora. Zhengxuan Wu, Noah Goodman, Christopher Potts, al. Causal Abstraction: A Theoretical Foundation for Mechanistic Interpretability. Journal of Machine Learning Research (JMLR), 26(83):1-66 2025.
13

---

Published as a conference paper at ICLR 2026
Chuqin Geng, Nham Le, Xiaojie Xu, Zhaoyue Wang, Arie Gurfinkel, and Xujie Si. Towards Reliable Neural Specifications. In Proc. 40th Int. Conf. on Machine Learning (ICML), pp. 11196-11212, 2023.
Chuqin Geng, Zhaoyue Wang, Haolin Ye, and Xujie Si. Learning Minimal Neural Specifications. 2024. Technical Report. https: http:::/aaxiv::::00::0:::: 04662
Tal Haklay, Hadas Orgad, David Bau, Aaron Mueller, and Yonatan Belinkov. Position-Awar Automatic Circuit Discovery. In Proc. 63rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 2792-2817, 2025.
Michael Hanna, Sandro Pezzelle, and Yonatan Belinkov. Have Faith in Faithfulness: Going Beyond Circuit Overlap When Finding Model Mechanisms. In Proc. 1st Conf. on Language Modeling (COLM), 2024.
Ouns El Harzli, Bernardo Cuenca Grau, and Ian Horrocks. Cardinaliyy-Mnniall Explanations for Monotonic Neural Networks. In Proc. 32nd Joint Conf. on Artificial Intelligence (IJCAI), pp. 3677-3688 2023.
Aliyah R Hsu, Georgia Zhou, Yeshwanth Cherapanamjeri, Yaxuan Huang, Anobel Odisho, Peter R Carroll, and Bin Yu. Efficient Automated Circuit Discovery in Transformers using Contextual Decomposition. Proc. 13th Int. Conf. on Learning Representations (ICLR), 2024.
Alexey Ignatiev, António Morgado, and Joao Marques-Silva. RC2: An Efficient MaxSAT Solver. Journal on Satisfiability, Boolean Modelling and Computation (JSAT), 11(1)533-64, 2019a.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva Abduction-Based Explanations for Machine Learning Models. In Proc. 33rd AAAI Conf. on Artificial Intelligence, pp. 1511-1519, 2019b.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. On Relating Explanations and Ad- versarial Examples. Proc. 33rd Conf. on Neural Information Processing Systems (NeurIPS), 2019c.
Alexey Ignatiev, Yacine Izza, Peter Stuckey, and Joao Marques-Sibe Using MaxSAT for Efficient Explanations of Tree Ensembles. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 3776- 3785, 2022.
Yacine Izza, Xuanxiang Huang, Alexey Ignatiev, Nina Narodytska, Martin Cooper, and Joao Marques- Silva. On Computing Probabilistic Abductive Explanations. Int. Journal of Approximate Reasoning (IJAR), 159:1, 2023.
Yacine Izza, Xuanxiang Huang, Antonio Morgado, Jordi Planes, Alexey Ignatiev, and Joao Marques- Silva. Distance-Restrieteed Explanations: Theoretical Underpinnings & Efficient implementation. In Proc. 21 Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp-
475-486, 2024.
Farnoush Rezaei Jafari, Oliver Eberle, Ashkan Khakzar, and Neel Nanda. RelP: Faithful and Efficient Circuit Discovery via Relevance Patching. 2025. Technical Report. https://arXiv: 25C8. 21258
Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong. Probabilistic Stability Guarantees for Feature Attributions. 2025. Technical Report. h 13787
Kyle D Julian, Ritchie Lee, and Mykel Kochenderfer. Validation of Image-based Neural Net- work Controllers through Adaptive Stress Testing. In Proc. 23rd IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), pp. 1-7, 2020.
Guy Katz, Clark Barrett. David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. Proc. 29th Int. Conf. on Computer Aided Verification (CAV), pp. 97-117, 2017.
14

---

Published as a conference paper at ICLR 2026
Guy Katz, Derek A Huang, Duligur lbeling, Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah, Shantanu Thakoor, Haoze Wu, Aleksandar Zeljić, et al. The Marabou Framework for Verification and Analysis of Deep Neural Networks. In Proc. 31st Int. Conf. Computer Aided Verification (CAV), pp. 443-452, 2019.
Suhas Kotha, Christopher Brix, Zico Kolter, Krishnamurthy Dvijotham, and Huan Zhang. Provably Bounding Neural Network Preimages. Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 80270-80290, 2023.
Alex Krizhevsky and Geoffrey Hinton.
Learning Multiple Layers of Features From Tiny Images, 2009. Technical Report. https://www cs. toronto. edu/-krzz/
Learning-features 2009-TR. pde
Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 2658-2665, 2021.
Faezeh Labbaf, Tomáš Kolárik, Martin Blicha, Grigory Fedyukovich, Michael Wand, and Natasha Sharygina. Space Explanations of Neural Network Classification. In Proc. 37th Int. Conf. on Computer Aided Verification (CAV), pp. 287-303, 2025.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-Based Learning Applied Document Recognition. Proc. of the IEEE, 86(11) (1:(1))227-23244 1998.
Mark H Liffiton, Alessandro Previti, Ammar Malik, and Joao Marques-Silva, Fast, Flexible MUS Enumeration. Constraints, 21(2):223-250, 2016.
Emanuele La Malfa, Agnieszka Zbrzezny, Rhiannon Michelmore, Nicola Paoletti, and Marta Kwiatkowska. On Guaranteed Optimal Robust Explanations for NLP Models. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), 2021.
Samuel Marks, Can Rager, Eric Michaud, Yonatan Belinkov, David Bau, and Aaron Mueller. Sparse Feature Circuits: Discovering and Editing Interpretable Causal Graphs in Language Models. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
Marques-Siie Silva, Gerspacher, M. Cooper, A. Ignatiev, and N. Narodytska. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. In Proc. 34th Conf. Neural Information Processing Systems (NeurIPS), pp. 20590-20600, 2020.
Joao Marques-Silva and Alexey Ignatiev. Delivering Trustworthy AI through Formal XAI. In Proc. 36th AAAI Conf. on Artificial Intelligence, pp. 12342-12350, 2022.
Joao Marques-Silva and Alexey Ignatiev. No Silver Bullet: Interpretable ML Models Must be Explained. Frontiers in Artificial Intelligence, 6: 128212, 2023.
Joao Marques-Sile Silva, Thomas Gerspacher, Martin Cooper, Alexey Ignatiev, and Nina Narodytska. Explanations for Monotonic Classifiers. In Proc. Int. Conf. on Machine Learning (ICML), pp. 7469-7479, 2021.
Reda Marzouk and Colin De La Higuera. On the Tractability of SHAP Explantiio under Markovian Distributions. In Proc. 41st Inf. Conf. Machine Learning (ICMLJ, pp. 34961-34986, 2024.
Reda Marzouk, Shahaf Bassan, and Guy Katz. SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism. In Proc. 39th Conf. Neural Information Processing Systems (NeurIPS), 2025a.
Reda Marzouk, Shahaf Bassan, Guy Katz, and De la Higuera. On the Computational Tractability of the (Many) Shapley Values. In Proc. 28th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp. 3691-3699. PMLR, 2025b.
Maxime Méloux, Silviu Maniu, François Portet. and Maxime Peyrard. Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable? In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
15

---

Published as a conference paper at ICLR 2026
Joseph Miller, Bilal Chughtai, and William Saunders. Transformer Circuit Evaluation Metries Are Not Robust. In Proc. 1st Conf. on Language Modeling (COLM), 2024.
Aaron Mueller, Atticus Geiger, Sarah Wiegreffe, Dana Arad, Iván Arcuschin, Adam Belfki, Yik Siu Chan, Jaden Fried Fiotto-Kaufman Tal Haklay, Michael Hanna, et al. MIB: A Mechanistic Interpretability Benchmark. In Proc. 42nd Inf. Conf. on Machine Leurning (ICML), 2025.
Christoph Müller, François Serre, Gagandeep Singh, Markus Püschel, and Martin Vechev. Scaling Polyhedral Neural Network Verification on GPUs. In Proc. 4th Conf. on Machine Learning and Systems (MLSys), pp. 733-746, 2021.
Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor Johnson. The Third International Verification of Neural Networks Competition (VNN-COMP 2022): Summary and Results. 2022a. Technical Report.
wwtpeiiv..r//iieoooooooo wtxg//bb/// abs /ta.////1... 2212.10377
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev, PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approxima- tions. Proc. 6th ACM on Programming Languages (POPL), pp. 1 1-33, 2022b.
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress Measures for Grokking via Mechanistic Interpretability. In Proc. 11th Int. Conf. on Learning Representations (ICLR), 2023.
Chris Olah. Mechanistic Interpretability, Variables, and the Importance of Interpretable Bases. Transformer Circuits Thread, 2022.
Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom In: An Introduction to Circuits. Distill, 2020.
Nils Palumbo, Ravi Mangal, Zifan Wang, Saranya Vijayakumar, Corina S. Pasareanu, and Somesh Jha. Validating Mechanistic Interpretations: An Axiomatic Approach. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
Achyuta Rajaram, Neil Chowdhury, Antonio Torralba, Jacob Andreas, and Sarah Schwettmann. Automatic Discovery of Visual Circuits. 2024. Technical Report. httpp:://rr.i..or/////.. 2404. 14349
Tilman Räuker, Anson Ho,, Stephen Casper, and Dylan Hadfield-Menell. Toward Transparent Al: A Survey on Interpreting the Inner Structures of Deep Neural Networks. In Proc. 1st IEEE Int. Conf. on Secure and Trustworthy Machine Learning (SaTML), pp. 464-483, 2023.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization. In Proc. 16th IEEE Int. Conf. on Computer Vision (ICCV), pp. 618-626, 2017.
Lee Sharkey, Bilal Chughtai, Joshua Batson, Jack Lindsey, Jeff Wu, Lucius Bushnaq, Nicholas Goldowsky-Dill. Stefan Heimersheim, Alejandro Ortega, Joseph Bloom, et al. Open Problems in Mechanistic Interpretability. Transactions on Machine Learning Research (TMLR), 2025.
Claudia Shi, Nicolas Beltran Velez, Achille Nazaret, Carolina Zheng, Adrià Garriga-Alonso, Andrew Jesson, Maggie Makar, and David Blei. Hypothesis Testing the Circuit Hypothesis in LLMss. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pp. 94539-94567, 2024.
Zhouxing Shi, Qirui Jin, Zico Kolter, Suman Jana, Cho-Jui Hsieh, and Huan Zhang. Neural Network Verification with Branch-and-Boud for General Nonlincarities. In Proc. 31th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp. 315-335, 2025.
A. Shih, A. Choi, and A. Darwiche. A Symbolic Approach Explaining Bayesian Network Classifiers. In Proc. 27th Int. Joint Conf. on Artificial Intelligence (IJCAI). pp. 5103-5111, 2018
Gagandeep Singh. Timon Gehr, Markus Püschel. and Martin Vechev. An Abstract Domain for Certifying Neural Networks. In Proc. 3rd ACM on Programming Languages (POPL), pp. 1-30, 2019.
16

---

Published as a conference paper at ICLR 2026
Jules Soria, Zakaria Chihani, Julien
Alban Grastien, Romain Xu-Darme, and Daniela Cancila. Formal Abductive Latent Explamations for Prototype-Bass Based Networks. 2025. Technical Report.
16588
Johannes Stallkamp. Mare Schlipsing. Jan Salmen, and Christian lgel. The German Traffic Sign Recognition Benchmark: A Multi-class Classification Competition. In Proc. 24th Int. Joint Conf. on Neural Networks (ICCNN) pp. 1453-1460, 2011.
Jiuding Sun, Jing Huang. Sidharth Baskaran, Karel D' D'Oosterlinck, Christopher Potts, Michael Sklar, and Atticus Geiger. HyperDAS: Towards Automating Mechanistic Interpretability with Hypernetworks. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
Aaquib Syed, Can Rager, and Arthur Conmy. Attribution Patching Outperforms Automated Circuit Discovery. In Proc. 7th BlackboxNLP Workshop: Analyzing and Interpreting Neural Networks for NLP, pp. 407-416, 2024.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating Robustness of Neural Networks with Mixed Integer Programming. In Proc. 5th Int. Conf. on Learning Representations (ICLR), 2017.
Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 Small. In Proc. 11th Int. Conf. on Learning Representations (ICLR), 2023.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-crown: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pp. 29909-29921, 2021.
Haoze Wu, Omri Isac, Aleksandar Zeljić, Teruhiro Tagomori, Matthew Daggitt, Wen Kokke, Idan Refaeli, Guy Amir, Kyle Julian, Shahaf Bassan, et al. Marabou 2.0: A Versatile Formal Analyzer of Neural Networks. In Proc. 36th Int. Conf. on Computer Aided Verification (CAV), pp. 249-264, 2024.
Min Wu, Haoze Wu, and Clark Barrett. VeriX: Towards Verified Explainability of Deep Neural Networks. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 22247- 22268, 2023a.
Wilson Wu, Louis Jaburi, Jason Gross, et al. Towards Unified and Verified Understanding of Group-Operation Networks. In Proc. 13th Int. Conf. on Learning Representations (ICLR). 2025.
Zhengxuan Wu, Atticus Geiger, Thomas Icard, Christopher Potts, and Noah Goodman. Interpretability at Scale: Identifying Causal Mechanisms in Alpaca. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 78205-78226, 2023b.
Anton Xue, Rajeev Alur, and Eric Wong. Stability Guarantees for Feature Attributions with Multi- plicative Smoothing. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pp. 62388 62413, 2023.
Yunzhi Yao. Ningyu Zhang, Zekun Xi, Mengru Wang, Ziwen Xu, Shumin Deng, and Huajun Chen. Knowledge Circuits in Pretrained Transformers. In Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), pp. 118571-118600 2024.
Jinqiang Yu, Alexey Ignatiev, Peter Stuckey, Nina Narodytska. and Joao Marques-Sike Silva. Eliminating the Impossible, Whatever Remains Must Be True: On Extracting and Applying Background Knowledge in the Context of Formal Explanations. In Proc. 37th AAAI Conf. on Artificial Intelligence, pp. 4123 4131, 2023.
Fred Zhang and Neel Nanda. Towards Best Practices of Activation Patching in Language Models: Metrics and Methods. In Proc. 12th Int. Conf. on Learning Representations (ICIR), 2024.
Huan Zhang, Tsui- Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient Neural Network Robustness Certification with General Activation Functions. In Proc. 32th Conf. on Neural Information Processing Systems (NeurIPS), 2018
17

---

Published as a conference paper at ICLR 2026
Yu Zhang, Peter Tiño, Aleš Leonardis, and Ke Tang. A Survey Neural Network Interpretability. IEFE Transactions on Emerging Topics Computational Intelligence, 5(5):726-742, 2021.
Haiyan Zhao, Hanjie Chen, Fan Yang, Ninghao Liu, Huiqi Deng, Hengyi Cai, Shuaiqiang Wang, Dawei Yin, and Mengnan Du. Explainability for Large Language Models: A Survey. ACM Transactions on Intelligent Systems and Technology, 15(2):1-38, 2024.
Duo Zhou, Christopher Brix, Grani A Hanasusanto, and Huan Zhang. Scalable Neural Network Veri- fication with Branch-and- and-oodd Inferred Cutting Planes. Proc. 38th Conf. on Neural Information Processing Systems (NeurIPS), 37:29324-29353, 2024.
Zhenhong Zhou, Haiyang Yu, Xinghua Zhang, Rongwu Xu, Fei Huang, Kun Wang, Yang Liu, Junfeng Fang, and Yongbin Li. On the Role of Attention Heads in Large Language Model Safety. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
18

---

Published as a conference paper at ICLR 2026
Appendix
The appendix collects proofs, model specifications, and supplementary experimental results that support the main paper.
Appendix contains additional background on neural network verification, circuit discovery, and patching.
Appendix contains the complete proofs of all propositions.
Appendix provides the pseudocode for the greedy quasi-minimality algorithm, together with
more detailed explanation of the toy example illustrating the minimality notion.
Appendix provides specifications of the datasets and architectures used.
Appendix provides additional details on the input-robustness experiment's methodology, verifica- tion setup, and evaluation.
Appendix verification setup, and evaluation.
F provides additional details on the
experiment's methodology,
Appendix G provides details on the minimality evaluation experiment's methodology, verification setup, and evaluation.
Appendix H provides the LLM usage discolsure.
A ADDITIONAL BACKGROUND ON NEURAL NETWORK VERIFICATION, CIRCUIT DISCOVERY, AND FORMAL XAI
Neural Network Verification. Neural network verification provides formal guarantees about the behavior of neural network fa over a continuous input region. Classic SMT//MLLP-basd
approaches (Katz al. 2017: Wu et al., 2024 Katz et al., 2019 Tjeng et al. 2017: Ehlers 2017) encode ReLU networks and specifications as logical or mixed -iteger constraints and offer exact guarantees, but scale only to
models. Abstract-interpretaaee interpretation methods (Singh et al.) 2019 Gehr et al. 2018: Ferrari et al., 2022 Müller et al. 2022b) propagate over-approximations layer by layer, giving fast but incomplete robustness certificates. A major advance came from linear- relaxation-based bound propagation, notably CROWN (Zhang et al. 2018) and follow-ups (Wang al. Chiu et al. 2025; Zhou et al. 2024 Shi al.] 2025), which compute tight dual-based linear bounds and serve either as scalable incomplete verifiers or as strong relaxations inside exact search. Modern branch-ane bound (BaB) frameworks leverage these relaxations achieve complete verification at scale, with a-B-CROWN and related variants now dominating VNN-COMP (Brix al., 2024) and handling million- parameter models. Recent progress includes tighter relaxations (e.g., SDP hybrids (Chiu et al. 2025)), cutting planes (Zhou et al., 2024), and support for non-ReL.U nonlinearities (Shi et al. 2025). Verification today routinely certifies robustness for moderately large CNNs and ResNets, though major challenges remain for transformers, complex architectures, and richer temporal or relational specifications.
million-parameter
Circuit discovery and patching. An important step in circuit discovery is patching, which seeks to isolate the computational role of a hypothesized circuit by intervening on the activations outside it. In typical setup, the model is replaced- - either with fixed baseline values (e.g., zero or mean activation) or with activations taken from counterfactual input. If the model's output remains unchanged, the circuit is understood to be sufficient for the behavior; if it changes, this reveals a dependency on the patched components. Numerous patching protocols have been proposed. including activation replacement, path patching, and attention/head interventions (Jafari et al.) 2025) Syed et al. 2024 Haklay et al., 2025 Miller al. 2024; Zhang Nanda (0024] Nanda al. 2023). all aiming to identify model components whose behavior is necessary or sufficient for a target computation. To the best of our knowledge, our method the first to provably certify the stability of circuits under families of such patching interventions.
base input, and activations at selected non-circuit nodes
Formal XAL Our work is also related to the line of research known as formal explainable Al (formal XAI) (Marques-Sile Silvu & Ignatiev| 2022), which studies input-based explanations with formal
guarantees Yu et al. 20233 Darwiche & Ji, 2022 Darwiche, 2023 Shih et al.) 2018 Azzolin
et al. 2025 Audemard et al. 2021). Since generating explanations with formal guarantees is often
computationally intractable (Adolfi et al. 2025 Barceló et al. 2020 Arenas et al.
202 Bassan et al.
2026b: Marzouk et al. 2025a Marzouk & De La Higuera
2024 Amir al.
2024
Bassan et al.
19

---

Published as a conference paper at ICLR 2026
2024|
Blane al. 2021 2022). much of this literature has focused simpler model classes (Marques
Silva & Ignatiev 2023). including decision trees (Bounia 2025| |025, Arenas et al. [022] Bounia 2024).
linear models (Marques- Silva et al.
2020), additive models (Bassan et al. [025e]] 20262]2222 monotonic
models (Marques-Silvaa et al. 2021 Harzli et al. 2023), and tree ensembles (Audemard et al. 2023
2022a
Ignatiev et al. 2022 Bassan al. 2025b Boumazouza et al. 2021). Closer to setting.
several works have extended these guarantees to neural networks (Malfa et al. 2021 Bassan et al.
2023
Wu et al. 2023a Bassan al. 2025a Boumazouza et al. 2026 Labbal al. 2025
De Palma
et al.
2025
Fel et al.
2023 Soria et al. 2025).
central concept in formal explainability is that of a sufficient reason (Darwiche & Hirth 2020
Bassan et al. 2025c d; Barceló et al.; 2020), also referred to as an abductive explanation (Ignatiev
et all.]|201bb 1zza et al. 2023). These notions are closely related to stability- -aaaeitt---sedddd feature attribution frameworks (Xue et al. 20233 Jin et al., 2025) Anani et al. 2025). Informally, a sufficient reason that fixing it preserves the model's prediction. Various minimality notions have been studied in this context, including subset-minimal explanations (Ignatiev et al. 2019b), as well as cardinally-minimal explanations that are computed via a similar minimal hitting set (MHS) duality (Ignatiev al., 2019b; Bassan & Katz, 2023) that was studied here. However, addresses a fundamentally different task: discovering circuits rather than input subsets. Moving from subsets of features to subcomponents of the model introduces several new challenges, including dual encodings of the model for certification, the need to handle patching operations, and the loss of monotonicity under certain patching schemes, which complicates convergence to minimal circuits. To the best of our knowledge, this is the first work to leverage ideas from formal explainability within mechanistic interpretability, and in particular for the task of circuit discovery.
resembles a circuit
work
Lastly, another partially relevant line of work has incorporated neural network verification to activation- patneenppttmmmamtee specifications (NAPs) (Geng et al. (023). which encode active/inactive neuron states and induce input regions beyond local perturbation balls. Recent work (Geng et al.) (024) fur- ther aims to learn minimal NAPs by removing redundant neuron states while preserving correctness. These also differ from our circuits which compute actual subgraphs of neural networks.
B PROOFS OF MAIN RESULTS
This appendix presents the proofs of the main propositions stated in the main paper.
B.I PROOF OF PROPOSITION I
Proposition 1. Given any model f and faithfulness predicate T. Algorithm 7 visits quasi-minimal circuit and Algorithm 3 converges to a locally-minimal circuit C, both with respect to 4.
Proof. We must establish three points: (i) Faithfulness: The final circuit C returned by Algorithms I and indeed faithful, i.e., the predicate (CC, G) holds true. (ii) Algorithm] I visits quasi-minimal circuit during its execution, i.e., there exists an iteration / where the corresponding circuit C. contains component such that (CC,, \ (t), G) is false. (iii) Algorithm 3erriithhmachieeeee achieves local minimality: In the returned circuit C, removing any single component i E C' breaks faithfulness; that is, for every i E C, (CC)) \ (i), Gi) is false.
In the first part of the proof, both Algorithms [ and 3 with C+ G. Since the full model graph G by definition, faithful, (GG, G) holds true. At each step, the algorithms check (CC (i), G) for the current component i and update C + C {i} only if this predicate remains true. Hence, the invariant preserved throughout the execution, and the final circuit C' still satisfies (CC
For the second part, we prove that Algorithm I visits quasi-minimal circuit during its execution. We assume that the empty circuit is unfaithful, i.e., -b,, G). Let C. denote the circuit maintained by the algorithm at iteration f. Since the algorithm maintains the invariant क (C,, G) and removes components only when faithfulness is preserved, it cannot reach the empty circuit. Hence, not all components can be removed while maintaining $. Therefore, there exists first iteration & at which the algorithm considers some component E C. and does not remove it because 1 (C, (i), G) is false. Thus, C, contains component whose removal violates faithfulness and is, by definition, quasi-minimal with respect to Φ. This establishes that Algorithm T visits a quasi-m minimal circuit during its execution.
20

---

Published as a conference paper at ICLR 2026
For the third part of the proof, note that Algorithm/ 3 continues to iterate over the circuit components until a full pass occurs with no further changes to the circuit C. This termination condition implies that for any remaining i C, the predicate &(C \ {i), G) must have been false during the final iteration. Otherwise, if (CC' { G) were true for any E C, the component would have been removed, and the algorithm would have proceeded to another iteration. Therefore, upon termination, every E C' is essential for maintaining the faithfulness predicate, establishing that C' is locally minimal with respect Q. This completes the proof.
B.2 PROOF OF PROPOSITION 2
Proposition 2. While Algorithm 4 converges to quasi-minimal circuit and performs O(log (Gl)
evaluations of & (C, G) (Adolfi al. 2025), Algorithm 7 visits a quasi-minimal circuit and performs O(G such evaluations, and Algorithm converges to a locally moilllamnniaal circuit and performs O P
evaluations.
Proof. We provide the proof for each algorithm:
(Algorithm Z). By Proposition Algorithm visits a quasi-minimal circuit during its execution. Observe that the algorithm processes each component of individually and exactly once. Since tests & upon the removal of each of these [G] components, the procedure carries out O(GG)) predicate evaluations in total.
(Algorithm 3.. By Proposition T Algorithm 3 converges to locally minimal circuit. For the runtime analysis, observe that Algorithm| processes each component of G and continues to do so until convergence. In each pass, tests the predicate T upon the removal of every remaining component. In the worst case, when only a single component is removed in each pass, the total number of predicate O(IG)). Thus, the procedure performs
evaluations is |G| - (IG) 1) (IG)- - O(G evaluations of ( G) in total.
(Algorithm The quasi- minimmatinlll algorithm and its runtime were established in Adolfi al. (2025). For completeness, we restate the argument regarding the number of evaluations: the algorithm halves the candidate index range at each step, requiring most [log [Gi] predicate evaluations before termination. Thus, its complexity is O(log GI).
B.3 PROOF OF PROPOSITION 3
Proposition There exist infinitelymmary number of configurations of fG. and 4, for which Algo- rithms 7 and do not converge subset-minimal circuit C. concerning Tb
Proof. Consider small nonlinear counterexample network fo R + R. with underlying structure G and node set VG := {v1, U2 U3, 31 The network is defined over a one-dimensional input æ, with three hidden nodes U1, U2, Vty and an output node Ua-
Consider a -ieddmmnsioonl input x, three hidden units 01, U2 Us. and an output neuron 04:
01 (x) == ReLU(x),
(2(x) = ReLU(x),
23(x) = x. Ca(u, w) = u 10 w (3)
Therefore, the following holds:
fa(x) = vs (v)(1)) (2(x), oa(x)) = un (x) - u2(x) + vz(x) = x
For any subset C C fer, 12, V3). define fc by applying zero-patching to all hidden units outside C. We take the faithfulness predicate to be strong equality, i..., corresponding to å = 0 and ep given by the foo norm the domain [0, 1). In particular:
(CC = Vx [0. 1). fc(x) fo(x)
21

---

Published as a conference paper at ICLR 2026
Iterative (Algorithms and 3. We consider the standard traversal order over these components from end to start (i.e., reverse topological order): (ii, Da U2, 21). We note that removing d (i.e., zero-patee patching it) directly breaks faithfulness.. Moreover, no other single-component removal preserves Φ: removing any hidden unit breaks the equality.
fartvs) (x) = (e)U(x) - ReLU(x) = 0 for r > O,
fC((12) (x) = (eLU(x) + x: + x for x > 0,
(6)
fa((1)) (x) = (a) + x # x for >
Hence, Algorithm [ and Algorithm 3 halt at C G (locally minimal). Yet a strict subset is faithful: removing the pair {v1, 02) yields [m) (z) = vz(x) x. so ((G (2), G) holds. Therefore, G is not subset-minimal.
Quasi (Algorithm With valid order (Vi, v3, U2 24), Algorithm 4 first tests the prefix removal {11, leaving (x) = (x)). & x, then tests {w1 ). leaving (a - ReLU(()) + x a; never considers the pair (11,02) and so returns
G, which is not subset-minimal, as we
previously showed in Equation 6
Since this holds for every m N. we obtain infinitely many configurations where both algorithms fail to return a subset-minimal circuit.
Infinite family. For any m 1, add pairs (pi, 9:) with (z q((x) ReLU(() and set
go(x) vz(x) Σ (p.(1) (+)))
Then fa(x) = x on [0, 1]. any single removal (of u3, some Pj. or some 43) breaks equality, but removing a whole pair (py: 9i preserves it. Under the ordering (Pi,.... Pp: 23 01s---. 9ms 14). the iterative greedy Algorithms I and Jad the quasi-minimal Algorithm both return G. Thus, there infinitely many such configurations.
B.4 PROOF OF PROPOSITION 4
Proposition 4. If monotonic, then for any model fa. Algorithm converges to subset-minimal circuit C concerning +.
Proof. By definition, establishing sunset-minimality of the circuit C requires showing: (i) that C is faithful, i.e., (CC, G) holds, and (ii) that no proper subgraph C" C C' also satisfies (CC', G).
For the first part of the proof, we follow the same trttfuulness-presevvatton argument used in the proof of Proposition] [ Algorithm| DaaiemmDeeiiii begins with the full model G, which is initially faithful to itself (#(G, G) holds). It then iterates through components in fixed order (c.g., reverse topological order). At each step, the algorithm maintains current circuit C₁; component i is removed only if its removal preserves faithfulness, i.c., if (C,, \ {i). G) holds. Consequently, faithfulness maintained loop invariant throughout the execution. In particular, upon termination, the resulting eircuit C satisfies (CC,G) G)-
For the second part of the proof, assume towards contradiction that there exists some C' Ç C for which it holds that (C", G) is true. Now, pick any e* E C. C.\ C". Let C, be the circuit at iteration l where this iteration marks the step over which the algorithm has evaluated whether to add e* the circuit. Because c* is present in the final returned circuit C, then by induction it was not removed at step & when considered, and hence it must hold that (C,, {c"), G) is false. On the other hand, we have the following inclusions:
C' C CC C C. C.
And so by the very definition of the monotonicity of C with respect b obtain that:
(C',,
$(C. (c)),G)
(8)
22

---

Published as a conference paper at ICLR 2026
This contradicts the fact that have derived that ((C,) { G) must be false from the algorithm's progression. Hence, we have obtained that for any subset C" holds that & (C", G) is false, and hence C' is subset-minimal with respect to d.
B.5 PROOF OF PROPOSITION S
Proposition 5. Let (C,, G) denote validating whether C¹ is input-robust concerning (fG. 2) (Def. Z). and simultaneously patching-re robbsst concerning (fa. Z') (Def. 2 Then if Z S Z', and H.g (Z') is closed under concatenation, & is monotonic.
Proof. We begin by formally stating the condition of activation space being closed under concate- nation:
We say that an activation space Hz(Z) of some model fo and domain 2 C R is closed under concatenation iff for any two partial activations a, a', where Ho (2) is activation over the circuit C C G, and a' E HZ)(Z) ) is an activation over the circuit C" C G, then it holds that a (Houu
Definition 1.
Now, let there be some C S C' S G. for which C" := C C (c)......,,) We assume that the predicate & is defined as validating whether some circuit C input-robust concerning (fa. 2), and also patching-robust with respect to (Ja. Z"). In other words, this implies that (CC, G) holds if and only if:
Vz
UZ Va E Ho(())) |c [o(z)]=oo ax Sc(z)) 58 58 j=1
(9)
We note that the following notation is equivalent to the following:
[ fa(z) ll, 5 + Hz(z1)) folz C fz(z) 1, 58
max zEZ (2))
(10)
ZE Z
where we use the notation (z' to denote the specific activation over C when computing fa(z') for some z' E R".
Since our goal to prove that monotonic, it suffices to show that C' also satisfies the above conditions. An equivalent formulation is to verify the condition for any C" == CU {c]}. i.c., for supersets that differ from by single element rather than an arbitrary subset. This valid because adding subsets inductively, one element at time, is equivalent to adding the entire subset at once. We therefore proceed under this formulation and assume, for contradiction, that the conditions fail to hold for C". In other words, we assume the following:
3Z E Z, 3a E HZ)(Z');
fc(() 1l, > >8 + [/ = =a)
Cr =a) - fo(z) 11, >8 +
max
(1I)
fo Ti = (z)( fa(z) 11, >6
max Z
This is also equivalent to stating that:
max x E
foute) Cu = Hou(ez(()) (z)) fa(z)
1 >8
(12)
Let us denote by S C R the set of all values that are feasible to obtain by fc(z Hz)) and
by S C TR. all values that are feasible by [c((z C² (z))) More precisely:
23

---

Published as a conference paper at ICLR 2026
:: = [ ZE 2, 27, A S' == (" ZE 2,
3 (13)
For finalizing the proof of the proposition, will make use of the following Lemma:
Lemma 1. Given the predefined JG. the circuits C C C" C G, and the aforementioned notations of S and S then it holds that S' S.
Proof. We first note that by definition:
s' = Cz (xr(z() ZE 2 2 (foute (z [c = Hou[er(()) (z)) z 2, Z')
(14)
We also note that for any z R holds, by definition, that:
fz C = =Ho(z)) = fo(z C
(15)
The notation fo(z C = Hz(z'), Ho (z)) simply means that we fix the activations of C' to (z) and those of C to (z'zz). From the same manipulation of notation, we can get that:
foure)) Cu(c) H HoL(oz(2))
folz (C H
culc) (z') ()) (i} Houle))
(16)
fo(z Cu = =H Houley
Mo(z), (c) = Hc((2))
fol2 ( 14) = H Hovey (z)) C = (c] Hey
Zo 1/ E Z. We will now prove that for any such choice of To prove that S' S, let us take some Zo, Zu, 2n then the following holds:
for C' Hor(Z)) C3
(17)
Since z E Z', zu E 2 2', and Ho((') closed under concatenation, then by definition holds that fixing the activations C {d] to (z) E Hor1) (Z') and those of {c]} to Hee (2o) (Z') yields an activation NoHejule) (2) Hence, we arrive
Sa C² = Hor (z/))
fou(e)) CU [c]] Hoolle) (2)))
(18)
fz (x(c) = Hov (24), C Ho (zo)) {(} He. (zu))
So(2n C = ===aC Hc((z))
Since we have shown that a E Hz(Z') and since Hc(zo) E (Z) then we have that:
for C = H)m(11))
folzo C = a, C = (z))) E
(19)
(s(z 7 = Ho(Z)) ZE Z E Z') = =
This establishes that C S, and hence concludes the proof of the lemma.
Now to finalize the proof of the proposition, we recall that we have shown that the following holds (and can now rewrite this expression given our new definition of S):
24

---

Published as a conference paper at ICLR 2026
max ZE 2'
|| C= - fa(z) 1l, =ō =
C
(20)
max yE
fc(z) 5 5
We have also assumed towards contradiction that the following holds, and we can similarly further rewrite this term given our new definition of S':
[z C Hzrr(()) - Sa(() ll, 5 =
max 2'2
(21)
max xE yEy
y fa(z) ll, >0
However, since have proven in Lemma
that S' C then know that:
y - fa(z) ||p
max yEE
|| fc(z) llp
(22)
YE
which stands in contradiction to equations concluding the proof the proposition.
20 and
21 hence implying the monotonicity of 4, and
B.6 PROOF OF PROPOSITION 6
Proposition 6. the condition (CC, G) is set to validating whether C' is input-robust concerning (fc. Z) (Def. []. and also patching-
with respect to (fa, (Def. 2 then if Z _ Z' and Ha((Z) is closed under concatenation, Algorithm converges to subset-minimal circuit.
Proof. The claim follows directly from Propositions Since 2 Z', Proposition implles that (CC, G) is monotonic. By Proposition 4 it follows that Algorithm converges subset-minimal circuit C' with respect to Φ.
B.7 PROOF OF PROPOSITION
Proposition 7. Given some model fG, and monotonic predicate &, the MHS of all circuit blocking- sets concerning & is cardinally minimal circuit C for which (CC, G) is true. Moreover, the MHS of all circuits C G for which (CC, G) is true, is cardinally minimal blocking w.Et
Proof. Prior the proof of Proposition 7 which establishes the connection between Minimum Hitting Sets (MHS) and cardinal minimality, we first recall the definition of MHS:
Definition (Minimum Hitting Set (MHS)). Given a collection S of sets over a universe U, hitting set H. C U for S is set such that
AS S, HOS
A hitting set H is called minimal if no subset of H is hitting set, and minimum if it has the smallest possible cardinality among all hitting sets.
We also show the following equivalence concerning the blocking sets.
Lemma 2. Under a monotone predicate & the of circuit blocking sets with respect to coincides exactly with the sets whose removal breaks faithfulness of the full model, i.e., C' C Gs blocking set if and only if (b C..
Proof. We prove both directions, starting with =. Let O' be a blocking set. By the definition of blocking set (Section 4.4), (CC') C², G) fails for all C' G. trivially including C' = G. Therefore, - \ C", G). For the reverse direction +, consider a set C" C whose removal from G, breaks the faithfulness of the full model G. namely + C", G). Assume toward contradiction that C'
25

---

Published as a conference paper at ICLR 2026
is not blocking set. Then there exists some C S G for which #(C' C², G) holds. By monotonicity of ④, since - G, we have CC) = ( \ C, contradicting our assumption.
This completes the proof, establishing that under monotonicity, the blocking sets exactly the sets whose removal breaks faithfulness of the full model G.
We now move to prove that the MHS of blocking-sets is a cardinally minimal faithful circuit. Let C be a minimum hitting set (MHS) of the set of blocking-sets B.
We now move to prove Proposition] 7 establishing that the minimum hitting set (MHS) of the blocking sets is cardinally minimal faithful circuit. Let B denote the set of blocking sets, which by Lemma 2 under monotonicity assumption, coincides with the sets whose removal breaks faithfulness of full model G. Let C' be minimum hitting set of B.
Assume towards contradiction that -Q G). Set 8 == =G C. Then @ \ is false, so 8* E B. Yet by definition C' = 0, contradicting that C' hits every set in B. Hence @ (CC, G) holds.
B) = &C, G)
We move forward to prove minimality. Assume there exists C' S G with ((C", G) and |CI| < -C|l. We claim C' is also a hitting set of B, contradicting the minimality of C' as an MHS. Indeed, if some B B satisfied C' n B 9,, then C" G' B, and by monotonicity of & we would have (G)) \\ B, G), contradicting B E B. Hence C' hits all of B, contradicting that C is an MHS.
For the second part of the proof, let C == (C & G) } and let B be minimum hitting set of C. Assume towards contradiction that is not, namely ((G B, G) holds. Then C' := G \ B is faithful circuit, implying C* C. Yet by definition C* n B contradicting that B hits every set in C.
Finally, assume towards contradiction that there exists blocking-set B' with B BB. Let E.C. If C'C' B' 0. then C' C B3, and by monotonicity of 4, we obtain that 4 B', G) holds, contradicting B' being a blocking-set. Hence, C B' + 0, so B' is hitting of C. But since [B'| < B, this contradicts the minimality of B as an MHS. Therefore, B is cardinally minimal among blocking-sess.
B.8 PROOF OF PROPOSITION g
Proposition 8. Given a model fc. and monotonic predicate 4, Algorithm coompuees a subset C whose size is lower bound the cardinally minimal circuit for which (CC,G) is true. For a large enough tmox value, the algorithu converges exactly to the cardinally minimal circuit.
Proof. We begin with the proof for the part on the lower bound to cardinally minimal circuit size. Let C' be the output of Algorithm for some max- By definition, C' is the MHS of the set blocking-sets accumulated by the algorithm, denoted B Bin...
Assume towards contradiction that |C| is not a lower bound for the size cardinally minimal circuit. This would imply the existence of faithful circuit C" with (CC,, G) and |C|| < |C|. From the minimality of C' as a hitting set, it follows that C' is not hitting set. Hence, there exists some B E Brnn such that C' n B 0. This implies C' C G B, and by monotonicity of & we obtain (G G) contradicting B being a blocking-set.
We now continue the second part of the proof regarding the convergence to cardinally minimal for large enough +max- For fmx = GG), the algorithm iterates over all possible blocking-sets. Hence, the resulting output C' is the MHS of all circuit blocking-sed and by Proposition| we conclude that C is a cardinally minimal circuit.
26

---

Published as a conference paper at ICLR 2026
C MINIMALITY GUARANTEES: ALGORITHMS AND ILLUSTRATTONS
C.I
GREEDY EXHAUSTIVE ITERATIVE CIRCUIT DISCOVERY
We present here an algorithm for exhaustively and repeatedly iterating over the circuit components, removing any component whose deletion does not violate faithfulness, until no further removals are possible (Algorithm
Algorithm Greedy Exhaustive Circuit Discovery
Input Model fc. circuit faithfulness predicate
2: C' t- G under some given element ordering (e.g., reverse topological sort)
3: changed + true
4: while changed do
5: changed t- false
6: for all E C do
7: if ( \ [i) G) then
8:
C C
changed + true 11: end for
9: end if
end while
13:
return C
C.2 GREEDY CIRCUIT DISCOVERY BINARY SEARCH FOR QUASI-MINIMAL CIRCUITS
We formalize the binary search procedure introduced in Adolfi et 2025 in Algorithm
Algorithm Greedy Circuit Discovery Binary Search
1: Input: Model fc, circuit faithfulness predicate & with 4 G) G)
2: C' G. low <- high <- |G|
3: while high - low > do
4: mid [[low + high) /2]
5: Cmid + G' G[1 mid]
6: if (CCid, G) then
7: low + mid; C +- Cmid
8: else
9: high < mid
end
11:
end while
12:
return C
C.3 TOY EXAMPLE: MINIMALITY NOTIONS
To illustrate the distinctions between the four minimality notions introduced in Definitions 3 (Section we construct a simple Boolean toy network.
For simplicity, we illustrate the different minimality notions using Boolean circuit with XOR gates. While this abstraction makes the example casier to follow, without loss generality, since Boolean gates can be equivalently expressed with ReLU activations.
(Specifically,, the XOR gate satisfies
I1 42 ReLU(x; - -x2) RRRUU(22 - x1).
for 11 (0, 1) both terms vanish when Di 22, and exactly equals when x2). We emphasize that this encoding is not part of the computation graph, which can be defined indepen- dently. Accordingly, toy boolean circuit (Fig. 3 can be viewed as a small feed-forward ReLU
27

---

Published as a conference paper at ICLR 2026
network. Despite its small size, this network cleanly separates the notions of cardinal, subset, local, and quasi- minimal circuits.
01 122
122 31
U3 = F1
+
D4 (0) 1 202
15 (0) 1 2/2
1/ 22
(=
Figure 6: Boolean toy network with XOR aggregation: y = U1 U/ 03 Us Uy. With 01 T2. U/2
Uy = Z1, U4 = = I1 22 and = 22 1 z2 = 0 the full model computes fc( = Z2-
Explanation. For clarity and simplicity, define Boolean network G which takes inputs in (x1, 222) E (0, 132. The network G is composed of six components, whose vertex set is denoted Ve (vi, U2 Us, u4 vs 16), aggregated by XOR (Fig. 60:
y = ii Ooy eus Dug. with
01 = I2, U2
U3 = 21, U1 = Us = 21 1z Vo = 22
The full network computes Sa x2) v2) fa(x1,
since
22 2 2i @ a + (a) @22)) @ (xr @x22) @ (x2()2))
I2 @ (m) (m)) e (ar (x2) @ (an @ar2) () (x2()
=0
We pick the faithfulness predicate to (CC, G) fc(11, = (c(xx1,22) = D2 ((11,0)),
i.e. C' is faithful it computes the same output G on all inputs.
This single construction cleanly separates the four minimality notions:
For each circuit C, we verify that it satisfies (2 x2) 22 and state why it meets (or fails) the corresponding minimality condition.
Cardinal-minimal::
Ceard = {v1}. It computes fcam -1 I2 fa- No circuit with
fewer components can be faithful.
Subset-minimal: C'sub {u2, v1 The computation
U2 @ e4 = Ii @ (I) @ (2) x2-
Removing any component breaks correctness: {u2) I1 + x2 and (ra)
22 + x2.
Local-minimal: Ctoc = {r1, U2 33 It computes
V1 U2 03 22 @ क 1 32.
Removing any single component breaks correctness: {Uz U2) = x2 + 21 7 # f2z vs = 2y @ Æ1 F 22, {12, by) = I1 Iι = 0 # Z2. However, removing two components may still leave a correct singleton (e.g. {m1 }), so it is not subset-minimal.
Quasi-minimal: Cquasi
{11, U2, U3, U4, ). It computes
v1 ① U2 O My ① F4 @ 0s #22
The circuit contains single essential component (v1). while the remaining ones can be removed in various combinations without changing the output (c.g., U2 @ V/ = and @ Us 0). Hence it is faithful but minimal under any stricter notion.
28

---

Published as a conference paper at ICLR 2026
D BENCHMARKS, MODELS AND ARCHITECTURAL SPECIFICATIONS
We evaluate methods on four standard benchmarks in neural network verification: three classifi- cation benchmarks (CIFAR-10 10 (Krizhevsky & Hinton 2009), GTSRB (Stallkamp et al. 2011) 1), and
MNIST (Lecun al. 1998)) and one regression benchmark, TaxiNet (Julian et al. 20220)
For each benchmark, we perform circuit discovery at the natural level of granularity for the model: convolutional filters (or channels) in CNNs and neurons in the fully connected network. The number of components at each granularity is summarized in Table 3
Table 3: Granularity and number of components considered for circuit discovery across the benchmark models.
Dataset
Model
Examined Granularity
# Components
MNIST
FC
Neurons
31
GTSRB
CNN
Filters
CIFAR-10
ResNet
Filters
72
TaxiNet
CNN
Filters
8
Data Selection. For the input and patching robustness experiments (Appendices E. we con- structed least 100 batches per benchmark, sampled from the test set using only correctly predicted inputs (or low-error inputs in the regression case). In classification tasks, each batch contained k 3 samples from a single class, evenly distributed across classes. In the regression task, batches of k = 3 were drawn from inputs with absolute error below 0.2, excluding large deviations relative to the model's performance. Specifically, we sampled 100 batches for CIFAR-10 and MNIST (10 per class), 129 batches for GTSRB (3 per class across 43 classes), and 100 batches for the regression benchmark TaxiNet.
For the minimality guarantees experiment (Subsection 5.3 Appendix Gp. used 50 singleton batches (k 1). obtained by selecting one sample from each MNIST batch above, thereby preserving the even class distribution.
D.1 CIFAR-10
For the CIFAR-10 benchmark Krizhevsky & Hinton 2009), we use the ResNet2b model, originating from the VNN-COMP neural network verification competition (Bak et al., 2021). This residual network consists of an initial convolutional layer, two residual blocks, and a dense classification head producing 10 output classes. In total, it comprises 72 filters (also referred to channels).
29

---

Published as a conference paper at ICLR 2026
Layer Block
Output Dim.
Details
Input
32 x 32 16
CIFAR-I0 image x 3, stride
Conv1
16
8
Residual Block I
Conv1
x 3, stride non non-lincarity
ReLU
X 8 X 16
Conv2
8 x 8 x 16
3 x 3, stride
Skip connection
x 8 16
identity/projection
Output
8 16
addition ReLU
Residual Block 2
Conv1
x 3. stride
RcLU
x 8 16
non-lincarity
Conv2
8 X 8 16
3 x 3, stride
Skip connection
x 8 16
identity addition ReLU
Output
x 8 16
Flatten
1 x 2048
Lincarl
2048 100
ReLU Output logits
Linear2
100 -> 10
Table 4: Full architecture of the ResNet2b model used in Bak et al. 2021 for the CIFAR-10 benchmark
D.2 GTSRB
The German Traffic Sign Recognition Benchmark (GTSRB) Stallkamp et al. (2011) is large-scale image classification dataset containing more than 50,000 images of traffic signs across 43 classes, captured under varying lighting and weather conditions.
(GTSRB))ttllkamp
We adopt the GTSRB-CNN CNN model used in recent explainability studies (Bassan et al. 2025a This architecture is convolutional network with convolutional layers using ReLU activations and average pooling, followed by two fully connected layers. It outputs logits over 43 traffic sign classes.
In total, the GTSRB-CNN comprises 48 filters across its two convolutional layers (16 + 32).
Layer
Output Dim.
Details
Input
32 32 x 3
GTSRB image
Conv1
32 x 32 16
3 3, padding 1, ReLU
AvgPooll
16
Conv2
x 16 32
3 3, padding 1, ReLU
AvgPool2
8 x 32
2 x 2
Flatten
x 2048
FCI
2048 128
ReLU Output logits
FC2
128 -
Table 5: Architecture of the GTSRB-CNN model used in (Bassan et al. 2025a).
D.3 MNIST
We use a simple, classic fully connected feedforward network for MNIST classification, which we trained given the simplicity of the task. The model achieves 95.20% accuracy the test set. It consists of two hidden layers with ReLU activations of sizes 13 and 11, followed by linear output layer, comprising 31 non-input neurons in total and 10,479 trainable parameters.
30

---

Published as a conference paper at ICLR 2026
Layer
Dimensions
Activation
Input
28 28 784
Fully Connected (fc1)
784 +
ReLU ReLU
Fully Connected (fc2)
13 + 11
Fully Connected (fc3)
11 + 10
Table 6: Architecture of the fully connected MNIST network. The model has 31 hidden neurons in total, which we treat as the granularity for circuit discovery.
D.4 TAXINET
The TaxiNet dataset (Julian et al. 2020) was developed by NASA for vision- based aircraft taxiing, and consists of synthetic runway images paired with continuous control targets. Unlike the classification benchmarks, TaxiNet is regression task: the model predicts real-valued outputs corresponding to flight control variables.
For our experiments, we adopt the TaxiNet CNN regression model introduced in the VeriX frame- work (Wu et al., 2023a) and subsequently used other explainability studies (Bassan al. 2025a). This convolutional network, comprising 8 filters, achieves a mean squared error (MSE) of 0.848244, and root mean squared error (RMSE) of 0.921.
Layer
Output Dim.
Details
Input
x 54 1
TaxiNet image
Conv1
27 x 54 4
3 3, padding 1, ReLJU
Conv2
27 x 54
3 3, padding 1, ReLU
Flatten
1 5832
FC1
5832 ->
ReLU ReLU
FC2
20 > 10
FC3
10 +
Regression output
Table 7: Architecture of the CNN regression model used for TaxiNet, following the VeriX frame- work (Wu et al. 2023a).
EXPERIMENTAL DETAILS
E INPUT ROBUSTNESS CERTIFICATION
In this experiment, evaluate the robustness of discovered circuits over continuous input neighbor- hood B (x), as established Section 3.1 We compare two variants the iterative circuit discovery procedure in Algorithm which differ in their climination criterion:
1. Sampling-based Circuit Discovery: directly evaluates the metric the input batch each step.
2. Provably Input-Robust Circuit Discovery: certifies that the metrie holds across the entire input neighborhood (Def. T..
The procedure traverses network components sequentially, deciding at each step whether to retain or remove a component. As noted in Conmy et al. (2023), the traversal order influences the resulting proceed from later fully-comnected convolutional layers
circuit. Following their approach, toward earlier ones, ordering neurons or filters within each layer lexicographically. For consistency, fix the patching scheme for all non-circuit components zero-patching.
31

---

Published as a conference paper at ICLR 2026
E.1 METHODOLOGY
E.1.1 SIAMESE NETWORK FOR VERIFICATION
To integrate circuit discovery with formal verification, we construct Siamese Network, which pairs the full model with candidate circuit, and outputs the concatenation of the two networks' logits.
This Siamese formulation provides the interface for the neural network verification used in two settings:
Provably Input-Robust Circuit Discovery: certify each elimination step that the candi- date circuit satisfies the metric across the continuous input neighborhood, ensuring robust- ness preserved.
verify after discovery (via either sampling- provable-based methods) that the resulting circuit is robust over the same neighborhood.
Evaluation:
Output Metric. For consistency, all of our experiments employ the same output metric for both the sampling- based and provably input-robust discovery methods. We measure the difference in logits, requiring this difference remain within a tolerance 8.
In classification tasks over an input we focus on the logit of the gold-class, indexed by k, and require that the predictions of the circuit and the full model G differ by at most 6:
[fc())[ fc()) S 5,
where the absolute value denotes the fy-norm on the one- me--immnniional vector corresponding to the k-th entry. In the sampling-bast based method, is evaluated on the sampled batch, whereas in the provable (siamese) setting, this criterion is certified over the concatenated logits of the siamese encoding, For instance, in 10-class classification task, the verification constraint on the siamese network's output is:
logits [k] logits
[A:]
S
where the first 10 entries correspond to the logits of the full model G and the second to those of the circuit C.
In regression settings (e.g., TaxiNet), the same principle applies to the full output (a scalar-valued prediction), measuring the absolute difference between the model and the circuit. In both cases, this metric directly instantiates the norm metric used in the robustness definitions (Definitions) 2
Input Neighborhoods. In our setup, the neighborhood B (x) defined in the input space with respect the - norm. For fully connected models (e.g., MNIST), inputs are flattened into vectors and the perturbation ball is defined over this representation. For convolutional models (e.g.. CIFAR-10, GTSRB, TaxiNet), inputs are multi-channel tensors, and the neighborhood is applied independently to each channel and spatial location.
1.1 VERIFICATION AND EXPERIMENTAL SETUP (INPUT ROBUSTNESS)
Since -oumd-and-complete verification of piecewise linear activation networks against linear properties NP-hard Katz et al. (2017), Some queries may not complete within the allotted time; such cases, the outcome is reported as unknown. In practice, with the a, 3-CROWN verifier, we limit each query to 45 seconds of Branch-and-bound time.
For fairness, we report robustness statistics only batches where the robustness check of the sampling-based method was determined (robust or non-robust, excluding timeouts) the main paper results, the rate of timed-out instances 1% MNIST, 1.6% GTSRB, 1% CIFAR- 10, and 5% on TaxiNet. Comparable rates were observed in the neighborhood size variations E.2.1 studies (on average, 0.5% for MNIST, 3% for CIFAR-10, 10, and 2.7% for TaxiNet), and in the tolerance level variations E.2.2 (on average 8.6% for TaxiNet, 3.6% for MNIST).
Experiments on MNIST, GTSRB, and CIFAR-10 were conducted unified hardware setup with 48 GB NVIDIA L40S GPU paired with a 2-core, 16 GB CPU. For the TaxiNet model, we used only a 2-core, 36 GB CPU machine.
32

---

Published as a conference paper at ICLR 2026
E.2 ROBUSTNESS EVALUATION AND PARAMETER VARIATIONS
We evaluate the robustness of circuits discovered by both methods over the neighborhood (x(xx] using formal verification via the Siamese Network as described above. The parameter controls the neighborhood size: if too small, the resulting circuits are trivial; if too large, the perturbations become unrealistic and off-distribution. We choose Ep values within ranges commonly used in prior verification work empirically selected balance circuit size and robustness, In addition, we vary both parameters, Cp and 6, to analyze their effect.
E.2.1 VARIATION OF INPUT NEIGHBORHOOD SIZE 6p
We fix the tolerance 6 and vary the input neighborhood size ép- For CIFAR-10 and MNIST, we use 5 2.0; for GTSRB, 5.0. For the TaxiNet regression model, we set á 0.92 (the model's root mean squared error, RMSE), reflecting its typical prediction scale (larger deviations would let the circuit drift more than the full model from the ground truth). Results are reported Table Rows highlighted in gray correspond to the results selected in the main paper.
Datnset
Sampling-buser based Circuit Discovery
Provably Input-Robust Circuit Discovery
Time (4)
Size ((C))
Robustness (5)
Time (s)
Size ((C))
Robustness (8)
MNIST (6-2.))
0.305
0.015 20.003
12.57 12.29
46.0 15.0
677.36 #183.65
14.51 1:2 41
100.0 1:0.0
0.016
12.30
1181.13
15.76
12:25
0,010
0.309 20.889
12.56 12.3
19.2 1:D
611.93 197.14
15.84
1:2 23
100.0 1:0.0
0.050
0.027
12:57 +2.20
0,0 =0.0
1700.05
+562.36 36
28.75
100.0 =0.0
TaxiNet (f=0.90 92)
0.001
0.040
:6.146
5,76 =0.77
62.2 +-9
201.81 131.6
6.07 +0.72
100.0 1:0.0
0.005
0.010
=0.002
5,77 +0.80
9.5 #3.0
180.00+-10.30
6.82 +0:46
100.0 =:0.0
0.010
0.010
+0.002
5.78 +0079
2.0
271.03 +-44.23
4-0322
+-0.0
CIEAR 10 (.0)
0.007
0.035
+0.001
16.70 +9.48
73.7 +4.4
2104. 118.9
17.96 4:0 90
100.0 1:0.0
0.012
0.116
10.367
16.91 19.12
58.1 1:5.1
2226.34 103.71
18.88 1.9.21
100.0 1:0.0
0.015
0.228
10.517
16.47 19.08
46.5 15.00
2970.85 1884423
19.18 : 1.10.16
100.0 1:0.0
GTSRB (6=5.0)
0.001
0.111
10.329
28.91
14.69
27.6 1.400
991.08
1669999
29.59 1.4.55
100.0 1.0.0
Table 8: Effect of varying the input neighborhood size Ep under a fixed tolerance Reported values means with standard deviations. For robustness binary variable), report the standard error (SE). Bold values indicate robustness percentages. Rows highlighted in gray correspond to the results selected in the main paper.
E.2.2 VARIATION OF TOLERANCE LEVEL 5
We vary the tolerance 8 while fixing the input neighborhood size ep to the datasct-specific values used in the main paper (MNIST: 0000.0 TaxiNet: 0.000).. Results are reported in Table 9 Rows corresponding to the main paper results are highlighted in gray.
Dataset
6
Sampling-based Circuit Discovery
Provably Input-Robust Circuit Discovery
Time (s)
Size ((C))
Robustness (%)
Time (s)
Size (C)
Robustness (%)
MNIST (c,=0.01)
0.50
0.083
0.329
19.72 1.50
15.6 3.8
460.14 14 36.59
22.02 2.52
100.0
2.00
0.309
0.889
12.56 + 2.29
19.2 + 4.0
611.93 + 97.14
15.84 + 2.33
100.0 :: 0.0
3.00
0.001 0.013
9.44 + 1.92
34,0 4.7
577.41 35.84
12.27 2.52
100.0
TaxiNet (s,00.00
0.50
0.038
0.115
6.84 + 0.86
32,1 1:
93.08 1: 22.75
7.75 1: 0.46
100.0 0.0
0.70
0.008
0.001
6.15 : 0.81
14,8 + 3.8
114.51
23,95
7.31 = 0.53
100.0 0.0
0.92
0.010
0.002
5,77 1: 0.80
9.5 3.0
180.00
1: 40.39
6.82 1: 0.46
100.0 0.0
1.00
0.009
0.002
5,57 1 0.82
9.5 3.3.
142.62
24.77
6.66 0.52
100.0 0.0
1.20
0.009
0.001
5.43 1 0.96
2.4
155.03
26.34
6.32 1: 0.59
100.0
Table Variation on tolerance level 5, with input neighborhood size fixed to the dataset-specific values used in the main experiments. Reported values means with standard deviations. For robustness (a binary variable), we report the standard error (SE). Rows highlighted in gray correspond to the results selected in the main paper.
33

---

Published as a conference paper at ICLR 2026
E.2.3 EVALUATION UNDER ALTERNATIVE OUTPUT METRICS
To further assess the generality of our framework, we repeat the robustness evaluation using alternative output metrics beyond the default logitdiiferrnce criterion. Specifically, we consider two additional formulations:
Consistent winner class: Given some target class E [d], enforces that the winner class remains consistent over a specified region. This metric directly targets preservation of the predicted class across the input domain and is widely used in robustness verification studies. The criterion then enforces that:
VZ Z, argmax(ff(2))g = argmax(fe(x C = () =
To allow greater flexibility, we relax the requirement by permitting the predicted class remain consistent under any change that stays within a tolerance E R+ above the runner-up class. When 5 = 0, this reduces back the original definition. To make this threshold more meanignful and interpretable, we set as a configurable fraction a E (0, 1] of the model's 's original winner-runner runner gap on the unperturbed input. our experiments, for simplicity, we enforce the consistency condition only between the winner and runner-up classes.
Abs-Max: Bounds the maximum absolute deviation across all output dimensions by specified threshold. This criterion does not guarantee class invariance but constrains the overall output drift. Formally, we require:
VZ E Z, [fc(z) - fx C = a) S 6,
ensuring that no individual logit differs by more than 5.
We evaluate both metrics, using the same discovery configurations and Cp as in the main input- robustness experiments. For the -iggtt-diffeeence metric, used the same 5 in main experiment (Table In the winner-runner setting, we set a = 0.5 (preserving half the original margin), and for the abs-max criterion we used 4.0. Results are reported in Table 10 which compares the sampling-bust baaedd and provable discovery methods under each metric.
Dataset Metric
baspling-based Circuit Discovery
Provably Input-Robust Circuit Discovery
Time (8)
Size ((C)
Robustness (%)
Time (6)
Size ((C))
Robustness (%)
MNIST
Logit-diff
0.31 1.089
12.56 12.30
19.2 14.0
611.93 197.14
15.84 12.33
100.0 10.0
Winner
5.18 1.05
20.94
5.79
#.000
Abs- Max
0.014 + 0.012
25.55 + 2.90
6.0 22.4
362.61 + 55.73
28.11 + 2.37
100.0 =0.0
Table 10: Comparison of circuit discovery methods under alternative output metrics. Reported values are means with standard deviations. For robustness (a binary variable), we report the standard error (SE). All methods use the same configurations as in the main experiments.
Across all metrics, the same overall trend is observed: the provable method consistently approaches 100% robustness while maintaining circuit sizes comparable to those of the caplling-bsed baseline, which attains substantially lower robustness. This consistency across different metrics suggests that the robustness of the provable approach not tied to a particular output metric, but reflects a stable characteristic of the method.
E.2.4 COVERAGE ANALYSIS OF PROVABLY-ROBUST VS. HAMPLING-BASER CIRCUITS
To better understand the relationship between the circuits identified by our provably-robust procedure and those produced by the sampling- method, we conduct an explicit coverage analysis over several robustness radii {0.005, 0.007, 0.01, 0.02, 0.03, 0.04, 0.05) on the MNIST benchmark. All other settings, including tolerance and metric definitions, follow those used in the main experiment (as discussed in section E.1 We conduct these experiments 2-core CPU machine with 16 GB of RAM.
For each perturbation radius Ep. examine the provably input-robust circuit Cp derived for that ra- dius and the sampling- paseed circuit C.,, each obtained over 100 different inputs (as in our experimental setup), resulting in 100 circuit pairs for every Cp.
34

---

Published as a conference paper at ICLR 2026
For these two circuits, compute: (i) the size of the intersection, |Cp n C.l. (ii) the components unique to the provable circuit provable-only) [Cp \ C.). and (ii) the components unique to the sampling-based circuit scampling-only: |Cs Cpl-
We average these quantities over the 100 circuit pairs and report their means and standard deviations. To summarize the overall similarity/dicrrpanncy between Cp and Cg across (p. additionally compute standard set-similarity measures: Intersection over Union (loU), Dice coefficient, and two asymmetric coverage metrics (provabee-vee-sampiing and campling-over-proaabbe trends are visualized in Fig. 7 To further highlight the non-overlapping components, Table reports their counts and their percentages relative to the full network size.
These aggregate
Because the sampling-bas constant across Ep. while the provable-based circuits naturally expand as 6p increases in order to guarantee certified robustness. We indeed view that as the required robustness grows, the provably- robust circuits include additional components essential for certification.
method does not enforce robustness condition, its circuit size remains
1.0
Similarity / discrepancy
0.6
0.4
JoU
(q-Bi--Knnc
Kyndi
24 Ky
0.2
(Provable sampling)
(Sampling over provable)
Suc
0.01
0.02
0.03
0.04
0.05
Figure 7: Comparison of similarity and coverage metrics between provably-robust and sampling-bast circuits. We report symmetric measures (loU, Dice), symmetric difference ratio, and asymmetric coverage ratios (provable over sampling, sampling over provable) to illustrate both overlap and directional differences.
As shown in Fig. 7 the provably robust circuits consistently recover the vast majority of units identified by the sampling-basee method across all 6, values, with especially high agreement for small perturbation radii (e.g., IoU and Dice z 0.9 at 6, 0.005). As cp increases, the overlap between the two circuits gradually decreases (IoU drops toward 0.5), indicating that the sampling- based circuits capture smaller fraction of the provable-hased ones under larger perturbations.
35

---

Published as a conference paper at ICLR 2026
Dataset
Ep
CCp C2l
of full net
C \
Cpl
of full net
0.005
2.64
7.76%
0.70
2.06%
0,007
3.32
9.76%
0.74
2.18%
0.010
4.10
12.06%
0.81
2.38%
MNIST
0.020
6.24
18.35%
0.58
1.71%
0.030
7.73
22.74%
0.39
1.15%
0.040
10.94
32.18%
0.24
0.71% %
0.050
16.11
47.38%
0.13
0.38%
Table 11: Set differences between the provably-rouss! circuit Cp and the sampling-based circuit C.,. For each Ep, we report (i) the number of units appearing only in the provably-robust circuit [Cp \ C. (ii) the number appearing only in the caapling-based circuit |C, Cpl. and (iii) the corresponding percentages relative to the full network size for that dataset.
This reflects the fact that the provably-robuse circuits expand to satisfy stronger robustness require- ments. This trend is also evident in Table [1] the difference Cp Cg grows steadily with Ep. while C, Cp remains small across all settings, and decreases further for larger perturbation radii indicat- ing that the sampling-ban based method contributes few components that are not required by the provable, certified solution.
E.2.5 RUNTIME TRADE-OFF ACROSS INPUT NEIGHBORHOOD SIZES
We aim to further analyze the runtime trade-off of the provably-robus method. For each input- robustness radius Cp. we run the method obtain a corresponding provably robust circuit and report the mean circuitsiize-ove--iine curves (with standard deviation shown as shaded regions) across these circuits for different input neighborhoods induced by increasing ép. We perform this analysis on MNIST benchmark, using the perturbation radii and experimental settings in the coverage analysis in Appendix E.2.4
Provably-robust Circuit Over Time (Mean = Std)
35
30
Circuit Size
25
==0.05
20
E=0.007
c=0.01
8= 0.02
15
0.04
8=0.05
0
500
1000
1500
2000
2500
Time (sec)
Figure 8: Provablc-robust circuit size over time on MNIST for different neighborhood radii cp.
Shaded regions denote the standard deviation.
In all cases, the curves start at the full network size at time and then decrease monotonically as components pruned, until the procedure terminates. Across the smaller and closely spaced ep values, the curves exhibit a very similar trajectory: an initial almost-lineal decrease during the first 300 seconds, followed by stabilization phase around 500 seconds. The standard deviation
36

---

Published as a conference paper at ICLR 2026
bands for these curves are also comparable. As expected, larger neighborhoods lead to larger final circuit sizes.
For substantially larger neighborhoods (e.g., Ep 0.03-0.05). the behavior changes: the decrease is slower, stabilization occurs later, and the variability (standard deviation) is considerably higher. Moreover, for these larger and more widely spaced Cp values, we observe clear increase in overall runtime (as indicated by where the curves terminate), reflecting the added complexity of discovering robust certified circuits under broader perturbation regions.
E.2.6 QUALITATIVE OBSERVATIONS OF THE DISCOVERED CIRCUITS
While our method is centered on formal guarantees, and our evaluation therefore focuses on robustness and minimality, we also include brief exploratory look the circuits discovered by our provably robust procedure and by the sampling-base baseline. This examination is qualitative in nature and is intended only to provide an informal visual sense of how the two circuits behave.
For this analysis, we consider several channel-level GTSRB circuits produced in the input-robustness experiments. Recall that for each batch (composed of samples from the same class) we executed both our provably robust discovery (under given 0.001 neighborhood) and the sampling- -based discovery, producing two circuits. the examples below, we select pairs of circuits with comparable sizes, where the sampling-based circuit is empirically non-robust while the provably robust circuit is certified robust. We then analyze their behavior on a representative clean input from the batch and on its corresponding adversarial example (an 0.001-bounded adversarial perturbation).
To obtain a coarse semantic signal, we apply Grad-CAM (Selvaraju et al. 2017) to the last convolu- tional layer of (i) the full model, (ii) the provably robust circuit, and (ii)) the sampling-based based circuit. Grad- Grad-CAM produces a class-specific importance map by weighting spatial activations according to the globally averaged gradients of the target class logit, Formally, for class c,
dye d
(c) 0k
CAM,(i,)) == ReLU
Σ o At
HW
Here, ye denotes the logit of the target class e (the true label in our case), A is the k-tth activation map (i.e., the output of filter k) of spatial size H x W, and (c) is the Grad-CAM weight obtained by spatially averaging the gradients 0y./OA Multiplying these weights by the corresponding activation maps and summing over channels, as in CAMg, highlights the spatial regions that the model relies on most for predicting class c.
We use this mechanism to compare the behavior of the discovered circuits with that of the full model. Following common practice in vision models, we apply Grad-CAM to the last convolutional layer of the GTSRB networks. For visualization, compute, normalize, and upsample the resulting Grad-CAM maps. Figure 9 illustrates these maps for an illustrative GTSRB sample depicting roundabout sign.
While the sampling- bampling-based based circuit is larger than the provably robust one (35 convolutional channels compared to 26), the latter exhibits closer match to the full model in the final convolutional layer. As shown in Fig. 9b] the heatmaps of the full model on this sample align well with those of the provably robust circuit, whereas the sampling-bass based circuit shows a less aligned activation pattern, with some loss of emphasis on regions in the sign interior.
In addition, despite the very small perturbation radius (which makes the clean and perturbed images visually almost indistinguishable; Fig. Da). Fig. 9b shows that the sampling-basee based circuit shifts its attention between the two inputs, while the provably robust circuit exhibits essentially no variation. This may suggest that the provably robust circuit better maintains its focus under perturbations.
These observations, though not central to our evaluation, provide an additional qualitative lens on how the discovered circuits operate.
37

---

Published as a conference paper at ICLR 2026
Input
Perturbed input
26 B (x)
(a) Original input, and perturbed input in GTSRB dataset.
Provably-robust Circuit
Sampling-ber based Circuit
Full Model
Input
X
Perturbed input
ZE B (x)
(b) GradCAM computations at the last convolutional layer
Figure Grad-CAM heatmaps comparison for GTSRB input and its adversarial counterpart, shown at the last convolutional layer across three models (the full model, the provably robust circuit, and the sampling-basse based circuit).
E.2.7 ADDITIONAL QUALITATIVE INTERPRETATION OF COMPONENT-LEVEL BEHAVIOR
Another possible direction for qualitative analysis is assign semantic interpretations inner components and subgraphs. This may include examining their behaviour and inferring the causal pathways in which they participate.
In the example shown in Figure 4 we consider CIFAR-10 10 bird sample together with its adversarial perturbation (also displayed in Figure [O), and compare the two circuit variants extracted from the ResNet model: the sampling-bass based circuit and the provably robust one. As illustrated, several filter- level components are preserved in the provably robust circuit, enabling satisfy the robustness criterion under perturbations.
To analyze the additional components, focus on the first convolutional layer, as shown Figure While later-layer interactions could also be insightful, for simplicity and clarity, we restrict our attention to the first-layer filters applied to the perturbed bird image. As the figure illustrates, this layer contains three filters shared by both circuits and additional filter present only in the provably-robust circuit.
We next examine the clean and adversarial images and their corresponding normalized difference heatmap, presented in Figure 10 within the main paper. Although the perturbation at = 0.015 is visually almost indistinguishable from the clean input, visualizing their difference reveals that substantial portions the perturbation concentrate the lower part of the image, beneath the bird's contour.
38

---

Published as a conference paper at ICLR 2026
Input
Perturbed input x B (x)
Difference Heatmap
30
34
02
Figure 10: Clean input x, its perturbed version z E B (x) with cp = 0.015, and the corresponding difference heatmap.
Filter 0
Filter
Filter ?
Pilter
(a) Shared filters across both circuits
(b) Filter retained only the provably-robust circuit
Figure 11: (a) Activation maps of the shared first-layer filters present in both the provably robust and sampling-basee based circuits. (b) Activation map of the additional first-layer filter included only in the provably robust circuit. Blue indicates negative activations; red indicates positive activations. White denotes neutral or near-zero values.
To gain further insight, we inspect the activation maps of these filters on the perturbed input (Fig- ure [T]. We examine the three filters shared by both circuits as well as the additional filter unique to the provably robust circuit. For each filter, we extract the signed activations (since this layer does not apply ReL.U,, normalize them, and upsample them for visibility. The resulting sign-normalized maps display negative activations in blue and positive activations in red.
Across the three shared filters, we observe in Figure Ia that, although they react to and capture aspects of the bird's contour, all of them assign negative values to the lower region where the noise concentrated. Filter outputs strongly negative values in this area, while filters 2 and 7 produce values between negative and neutral, passing only weak signal over that region.
In contrast, the additional filter included appears only in the provably-robus circuit (Figure Tlb produces strong positive activations precisely over the lower, aofse-affected region. It is the only filter in this layer to do so. This suggests that its inclusion, together with the other filters, may help enrich and stabilize the signal circuit's certified robustness under this perturbation. Such an illustrative view suggests a possible connection between the retained components and the circuit's robustness.
the perturbed region of the input, potentially contributing the
F PATCHING ROBUSTNESS CERTIFICATION
In this experiment, we evaluate the robustness discovered circuits when non-cireuit components are patched with feasible activations drawn from a continuous input range, rather than fixed constants, as defined in Section 3.2 Operationally, for any circuit C, we test whether perturbing non-circuit components within the range of activations induced by inputs B% (x) can cause violation of some metrie |- with tolerance 5. If such violation exists, declare C to be patching-robust
39

---

Published as a conference paper at ICLR 2026
We compare three patching schemes within the iterative discovery framework (Algorithm)
1. Zero patching: sets all non-circuit components to zero.
2. Mean patching: replaces non-circuit components with their empirical means, estimated from 100 randomly selected training samples.
3. Provably robust patching: verifies robustness across the full range of feasible activations induced by continuous input domain (Def. 2
F.1 METHODOLOGY
F. PATCHING STAMESE NETWORK FOR VERIFICATION
As an interface for verifying patching robustness, we employ a Patching Siamese network with two branches: (i) a full-network patching branch, used to capture non-cireuit activations for patching; and (ii) a circuit branch restricted to C, where every non-circuit component replaced by the activation of its counterpart in the patching branch. This replacement is implemented through dedicated wiring that copies the required activations from the first branch to the second.
We examine activations induced by inputs from neighborhood around 2 = B,5 (x). As outlined in Section 3.2] the siamese network is fed a concatenated input (x, z) (along the feature axis for MNIST and the channel axis for CNNs). Here, x is routed to the circuit branch and z to the patching branch. The verification domain is applied only to z, while x is held fixed. This setup simulates the circuit running on with its non- non-circuit activations replaced by those induced from Z E Z. We note that, for numerical stability on the verifier's side, the circuit-branch input is enclosed in a negligible 10-5 L ball.
For the output criterion, the resulting circuit logits are verified against the logits of the full model, fx(x) (precomputed independently of the Siamese construction) under the logit-difference metric with tolerance This guarantees that the patching-robustnes property (Def. 2 holds.
Input Neighhorhoods. As in Section E.1.2 define the neighhorhood 2 = Bo0 (x) using the to norm.
F.2 ROBUSTNESS EVALUATION AND PARAMETER VARIATIONS
After discovery (using zero, mean, or provably robust patching), we verify the resulting circuits with the Patching Siamese Network over the same B (x), reporting circuit size, runtime, and patching robustness. Since typical 6p values in the literature target imput perturbations, we use larger values for the patching domain to reflect the broader variability of internal activations while avoiding off- distribution regimes. We report results below for varying (ep,, 5) assess their effects robustness and size.
F.2.1 VERIFICATION AND EXPERIMENTAL SETUP (PATCHING ROBUSTNESS)
We use the same hardware configuration as in the input-robustness study E. 1.2 We a Branch- and-bound timeout of 45 seconds for MNIST, GTSRB, and TaxiNet as in the input experiment. For CIFAR-10, iterative discovery queries the provably robust method are limited to 45 seconds, while discovered cireuit-robustness evaluations are allowed up to 120 seconds. Queries that do not complete within these limits are reported as unknown.
As in the input robustness experiment B for fairness, we exclude cases where the robustness check for zero or mean patching timed out from the reported robustness statistics. In our main results, the timeout rates were 12% for MNIST, 2% for TaxiNet, 6.2% for GTSRB, and 31% for CIFAR- 10. while in the variations over ep ( (F2.2) they averaged 0.5% for TaxiNet and 8.8% for MNIST. Over the 5 variation [22.3). the average timeout rate was 1.5% on TaxiNet and 14% MNIST.
40

---

Published as a conference paper at ICLR 2026
F.2.2 VARIATION OF PATCHING NEIGHBORHOOD SIZE 6p
We fix the tolerance level ò and vary the patching neighborhood size Ep. For CIFAR-IO we use 8=0.1, for MNIST 0-0.5, 5, for TaxiNet 0-0.92, and for GTSRB 6-2.0. Table 12 extends the main results with additional Cp variations on the MNIST and TaxiNet benchmarks.
Dansort
Zero Patching
Mran Patching
Provably Patchhnng Rohest Patching
Tiine (5)
Size (JC1)
Rob. (9)
Time (S)
Size ([C)
Rob. (16
Time (S)
Size ((C)
Rob (S)
MNIST (f-0055
0.182
19.87
87.8 #3.6
0.13 0.001
631.08
100.0:0000
0.060
$8.0
20,
1207.05
17.05
18000:00
0.050
0.015 10,
1.2
398.41
$.96.96
23.20
TauNer (F
0,006
0.061
180,188
5.78 0.079
93.0 +2.0
0.022 20.061
5.38 =:0.5
100.0 2:0.0
220.67 2:57 28
4,60 20074
100.0:000
0.008
0.025
+0.007
5.78 20079
62.8 2445
0.005 2000011
5.38 2:0.5
77.0 5:4.2
168.99 2:44 88
5.36 2.0.4
180.0:0.00
8.000
0.004
+0.059
5/18 0:077
57.1 95.0
0,05 10.0K8
5:00 00.05
63.3 1-1.8
175.21
9932.71
541 1:0.3
18t01 9:000
0,030
0.099
+0.002
5.78 m0-7a
27.8 1-1.4
0.00 10.001
5.58 :::45
48,8 1:1.9
95.31 #:15.54
5:04 1:0:30
1400 :000
0,050
0.024
10.003
5.77 -0.78
3:00
0,012 33.003
5.37 20.65
0.0 :0000
89.37
4:17.58
7,00 ::0:26
160.0 10000:000
CHRAR--0 (f
65.07 3,00
46.4
0.046 0,003
3.00
3:7
54405.1 a: 1091.05
65.55
0.005
32,65
38,0
0.041
0,009
4.16
2907.17 721.67
34.34
Table 12: Variations on patching neighborhood size Ep with fixed tolerance 6. Reported values are means with standard deviations (formatted as (mean + std)). For robustness (a binary outcome), report the mean robustness with its standard error (SE), and display robustness values in bold. Rows highlighted in gray correspond to the results selected in the main paper.
F,2.3
VARIATION OF TOLERANCE TOLERANCE
We fix Ep and examine various tolerance values. As in the main paper results, we use Ep 0000. for MNIST and Taxinet and vary the tolerance Results are reported in Table 13
Dnisect
Zero Patching
Mean Patching
Provably Robunt Putching
Time (x)
Sixe ((CT)
Rob (9)
Time
Sioe(CD
Rob
Time
((C)
Robs (9)
MINIST (..001)
0.25
0.342 0,476
21.36
21,22
52.8 5.59
523.67
41.31
19
0.50
0,000
& 0,323
1996 8: 1.50
$8.0 1 5.3
0016 e 0003
19.16 = 1.84
55.7 5:53
71487
20708
17.05 8 2,30
100.0 0.
1,00
0.013
0,000
61.2
0.13
66.3
44.38
1000:000
TaxiNet (..00.0))
0.50
0.011 + 0.001
6.66 0.78
74.0 4.4
0010 0.01
588 0:40
50.8 4:40
18767
39.68
600 0.00
100.0
0.90
0.080
5.0
0.000
5.49
61.2 4:40
204.38
40.04
8.92
(0034
=0.000
5.78 8075
87.1 15.0
0,005 20088
5:90 20.05
63.3 1:1.
195
4:5.71
541 99.59
100.0 80.0
1.20
| 0.011 + 0.001
5.44 + 0.96
46.0 46..t.35 5.0
0.100 = 8000
5.30
58.2 +.50
346.14 + 50.32
5.15 = 0.51
100.0 + 0.0
Table 13: Variation of tolerance level 5 with fixed patching neighborhood size 6, = 0.01. Reported values are means with standard deviations (formatted as mean + std). For robustness (a binary outcome), we report the mean robustness with its standard error (SE), and display robustness means in bold. Rows highlighted in gray correspond to the results selected in the main paper.
G EXPLORING CIRCUIT MINIMALITY GUARANTEES
In this experiment, we examine circuits that must simultancously satisfy both ioput-robustness (Def. I and mutching-robustnes (Def. 2 as introduced in Section 3.2 Specifically, we define & to require that circuits remain robust within the input neighborhood 2 Bog (x), when non-circuit components
are patched with values drawn from the patching neighborhood 2' B (x).
Thus, two domains are involved: one for inputs and one for obtaining activations used in patching. Here, ein and Ep denote the radii of the respective balls. In our setup, we use en 0.01, "p = 0.012, and d 2.0.
G. VERIFYING SIMULTANEOUS INPUT- AND -OOTINGGRS WITH TRIPLED STAMESE
We certify simultaneous input- and patching-robustness robustness using a tripled Siamese network with three branches, each evaluated on its designated domain: (i) full-network patching branch, which
41

---

Published as a conference paper at ICLR 2026
processes inputs z' E Bep (x) to capture activations for use patching values; (ii) the full network, which processes inputs 8% (x) to provide reference logits fz(z); and (iii) the circuit branch, also evaluated on z E t (x) but restricted to C, where non-circuit components are masked and instead receive transplanted activations from the patching branch.
This special wiring enables the direct transfer of non-circuit activations, allowing the verifier to certify that the eircuit logits (z(z) remain faithful to (z) across the input neighborhood E (x) under patching values induced by 8 (x), thereby establishing the simultaneous input- and patching- robustness property.
We evaluate three discovery strategies under this setting, all applied with the combined robustness predicate O defined above:
1. Iterative discovery: Algorithm
2. Quasi-minimal search: Algorithm
3. Blocking-sets MHS method: Algorithm approximate cardinally minimal circuits.
2
leveraging circuit blocking duality to
G.2 BLOCKING-SEIT MHS METHOD: ANALYSIS AND EXPERIMENTAL DETAILS
Experimental setup. We conduct experiments on the MNIST network (34 hidden neurons). Since contrastive subsets are enumerated increasing order of size, the number of verification queries grows combinatorially. Even when restricted to subset sizes E (1,2,3), each batch requires thousands of verification calls. To keep computations tractable, we evaluate singletons (k per batch) and enforce 30-second timeout per query. In one rare case, the procedure produced empry circuil (size 0), as & held vacuously under a particular choice environments and metric, eliminating all components. This case was excluded from the reported results.
Parallelism. Unlike iterative discovery, where elimination steps are sequentially dependent, the verification of contrastive subsets is independent. This independence allows full parallelization: distribute verification queries across workers, with runtime scaling nearly linearly with the number of workers.
Properties. Under monotonic O the MHS method yields either (i) lower bound on the size of any cardinally minimal circuit, (ii when the hitting set itself satisfies ④, certified cardinally minimal circuit. Although more computationally expensive than iterative discovery, MHS provides strictly stronger guarantees: if the hitting set is valid, the result is provably cardinally minimal; otherwise, its size gives tight lower bound that exposes whether iterative discovery reached cardinal minimality and quantifies any gap.
H DISCLOSURE: USAGE OF LLMS
An LLM used solely writing assistant to correct grammar, fix typos, and enhance clarity. It played no role in generating research ideas, designing the study, analyzing data, or interpreting results; all of these tasks were carried exclusively by the authors.
42


Reviews:
[{"review_id": "N8ZVibrv1N", "reviewer": "Reviewer_ZmUt", "summary": "This paper focuses on automated circuit discovery in neural networks, one of the key challenges of mechanistic interpretability (MI). Current circuit discovery methods are heuristic and rely on sampling and approximations, therefore failing to provide theoretical guarantees about the obtained circuits (faithfulness and robustness to perturbations). The authors introduce a novel framework that uses neural network verification testing to discover circuits with three types of provable guarantees:\n- Input-domain robustness, ensuring that the circuit's behavior remains faithful across a continuous input region.\n- Patching-domain robustness, guaranteeing faithfulness under a continuous range of perturbations (patching) to the activations of non-circuit components.\n- Minimality: The authors introduce and formalize four types of circuit minimality, hierarchically ordered (quasi-, local, subset- and cardinal minimality) and provide algorithms to either obtain or approximate those.\n\nSome of the key technical contributions of this work include:\n- A siamese network encoding, which allows standard verifiers to certify the aforementioned properties\n- Identifying a \"circuit monotonicity\" property that enables stronger minimality guarantees\n- Using a circuit-blocking-set duality based on Minimum Hitting Sets (MHS) to find cardinally-minimal circuits.\n\nThe authors validate their approach on several vision models and benchmarks, obtaining circuits with substantially stronger robustness guarantees than sampling-based baselines.", "questions": "- Have the authors considered adapting the framework to certify different properties? For instance, instead of bounding the logit difference (which can be problematic, as stated above), could it be adapted to certify that the predicted class remains invariant across the input domain? This seems like a natural guarantee for classification.\n- The complexity of MHS depends on enumerating blocking sets up to size t_max. What was the practical size of the blocking sets found in the experiments, and how large did t_max need to be to provide good lower bounds or find the minimal circuit? (My apologies if this is answered in the attached codebase, which I did not consult)\n- For the example in Figure 1, do the authors have any functional hypothesis for why the components highlighted in green are essential for robustness (handling specific edge cases)? What kinds of input perturbations would cause the sampling-based circuit to fail, which the provably-robust circuit correctly handles?\n- Do the authors have any insight into potential ways to apply this framework to larger models/architectures, such as Transformers? Are there specific verification techniques that offer a better trade-off for this application?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The core contribution (applying formal verification to automated circuit discovery) is novel and significant. It directly addresses a fundamental and critical limitation in the field of MI (moving from heuristic approximations to provable guarantees), which has been acknowledged in many recent works in the literature. This work makes a significant step towards increasing the reliability of MI methods and is much-needed.\n- The paper is technically excellent. The formalizations are clear, and the introduced hierarchy of minimality guarantees (Definitions 3 through 6) clarifies a concept often used loosely in the literature. All of the stated theorems are proved in depth in the Appendix, which is rare to find in this type of work.\n- The experiments clearly support the paper's claims. The authors use the SOTA α,β-CROWN verifier on standard benchmarks, and their proposed methods achieve 100% certified robustness (Tables 1 and 2), whereas sampling-based methods largely fail. Finally, the experiments in section 5.3 are a good illustration of the trade-off between minimality strength (as defined in the proposed hierarchy) and runtime.\n- The paper is very well-written, given the complexity of the topic.", "weaknesses": "- The most significant weakness (which the authors do acknowledge) is the scalability of the neural network verification methods. The experiments are conducted on relatively small vision models (e.g. ResNet2b) yet already require computation time in the minutes to hour range. Current MI research largely focuses on large LLMs or other models using the Transformers architecture, and as proposed, the authors' framework would likely be computationally intractable for such models. This is an inherent challenge of the verification field and by no means a flaw in the paper's methodology itself and doesn't detract from the foundational contribution of the work, but it does limit the immediate practical applicability to SOTA models.\n- The paper could be strengthened by adding a more detailed qualitative analysis of the discovered circuits. For example, the provably robust circuit depicted in Figure 1 contains an extra component. A natural question is: What functional role does it play? An illustrative example would make the benefits of the approach even more tangible and would also be interesting from a research perspective.\n- The paper uses a logit-difference metric for faithfulness, which works well for verification and is a standard choice in MI, but may not always accurately reflect the semantic meaning of a circuit that one may be interested in. It is not entirely clear if a small logit difference is always the most meaningful proxy for a circuit \"doing the same thing\" as the model (a circuit could potentially maintain a small logit difference but modify its internal representations or attributions in a way which may be significant). However, this is, again, the de facto standard used in most MI research and this is a fairly minor point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LelkDjKhpk", "reviewer": "Reviewer_X5ZF", "summary": "In the context of mechanistic interpretability for neural networks, the authors use neural network verification methods to come up with circuits with provable guarantees. Authors claim to outperform conventional circuit discovery methods., i.e.e they provide stronger robustness guarantees for discovered circuits.", "questions": "- I could not find a discussion on the computational overhead of the method w.r.t. the baselines.  Could you briefly post a comment about it? (Apologies if I have missed)", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Problem addressed is impactful and the authors identified clear blind spot in literature\n- Thorough theoretical contribution\n- Experiments rely on VNN-COMP community-benchmark. Results show authors method strongly outperforms the chosen baselines, across all experiments.\n- Paper is clear and flows well. Authors contribution also clear.\n- Literature review carried out with diligence. I am not a domain expert - fellow reviewers with greater expertise may have identified gaps.", "weaknesses": "- Some neural network verification concepts could have been introduced more in details (e.g. \"Patching\")\n- Lack of running example make reading hard to instantiate into a real-world, impactful use case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ywCjeLSZaX", "reviewer": "Reviewer_WbQb", "summary": "This paper proposes a framework for provable circuit discovery in mechanistic interpretability, offering formal guarantees of input robustness, patching robustness, and minimality. It introduces two algorithms—a greedy local-minimality search and a blocking-set duality method—for discovering circuits with verified faithfulness using α–β-CROWN. Experiments on MNIST, CIFAR-10, GTSRB, and TaxiNet confirm 100 % robustness within specified domains but show high computational cost.", "questions": "A recent paper, “Learning Minimal Neural Specifications” (Geng et al., NeuS 2025), finds that a small subset of neurons can often characterize a model’s robust behavior. Your minimal-circuit formulation appears conceptually related. Could you discuss the connections between these phenomena?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Clear definitions and proofs for robustness and minimality in circuit discovery.\n\n2. The greedy and hitting-set approaches are well motivated and practically implementable.\n\n3. Connects mechanistic interpretability with formal verification through provable guarantees.", "weaknesses": "1. High computational cost: Verification with α–β-CROWN for each candidate circuit is extremely slow; scalability remains a bottleneck.\n\n2. Small experimental scope: Only small convolutional and MLP networks are tested; no evidence on larger or modern architectures.\n\n3. Limited interpretive analysis: The paper emphasizes correctness and robustness, but offers little discussion of what the discovered circuits mean semantically.\n\n4. Evaluation imbalance: Most comparisons are against heuristic baselines without runtime or coverage trade-offs clearly analyzed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)