Certified Circuits: Stability Guarantees for Mechanistic Circuits

Alaa Anani; Tobias Lorenz; Bernt Schiele; Mario Fritz; Jonas Fischer

cs.AIFeb 26, 2026

Certified Circuits: Stability Guarantees for Mechanistic Circuits

Authors: Alaa Anani, Tobias Lorenz, Bernt Schiele, Mario Fritz, Jonas Fischer

Organizations: Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany · CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Abstract

Understanding how neural networks arrive at their predictions is essential for debugging, auditing, and deployment. Mechanistic interpretability pursues this goal by identifying circuits--minimal subnetworks responsible for specific behaviors. However, existing circuit discovery methods are brittle: circuits depend strongly on the chosen concept dataset and often fail to transfer out-of-distribution, raising doubts whether they capture the concept or merely dataset-specific artifacts. We introduce Certified Circuits, which provide provable stability guarantees for circuit discovery. Our framework wraps any black-box discovery algorithm with randomized data subsampling to certify that inclusion decisions over circuit components--neurons or edges of the model graph, depending on the base algorithm--are invariant to bounded edit-distance perturbations of the concept dataset. Unstable components are abstained from, yielding circuits that are more compact and more accurate. We validate across three architectures (ResNet, ViT, GPT-2) on vision (ImageNet and four OOD datasets) and language (IOI, IOI-Hard, Greater-Than) tasks. Certified circuits achieve up to 56% higher accuracy and up to 80% fewer components, and remain reliable where baselines degrade. Certified Circuits puts circuit discovery on formal ground by producing mechanistic explanations that are provably stable and better aligned with the target concept. Code: https://github.com/AlaaAnani/certified-circuits.

Figures & tables

Figure 2: Certified circuit discovery via concept deletion smoothing. (§ 3.1 ) Given a concept dataset $\mathcal{D}$ , model graph $G$ , and circuit discovery algorithm $A$ : (§ 3.2 ) We sample dataset variants via per-example deletion with probability $p_{\mathrm{del}}$ , (§ 3.3 ) run $A$ on each to obtain per-sample circuits, (§ 3.4 ) aggregate per-component (e.g., vertex) inclusion frequencies, (§ 3.4 ) certify components as in , out , or abstain ( $\oslash$ ) based on votes consistency. (§ 3.5 ) The certified circuit is provably invariant to concept dataset edits within radius $r$ .

\rectanglecolor CertHL3-614-6 \rectanglecolor CertHL3-1014-10			cACC $\uparrow$				Size $K$ $\downarrow$
Domain	Setting	Dataset / Task	Full	Baseline	Certified	$\Delta$	Full	Baseline	Certified	$\Delta$
Vision ResNet-101	ID	ImageNet	0.78	0.83	0.95	$\uparrow$ 14%	1.000	0.700	0.336	$\downarrow$ 52%
	OOD	ImageNet-A	0.07	0.60	0.94	$\uparrow$ 56%	1.000	0.400	0.342	$\downarrow$ 15%
		OOD-CV	0.20	0.73	0.93	$\uparrow$ 28%		0.400	0.269	$\downarrow$ 33%
		ImageNet-C	0.57	0.72	0.92	$\uparrow$ 28%		0.700	0.416	$\downarrow$ 41%
		ImageNet-O	0.81	0.93	0.98	$\uparrow$ 6%		0.700	0.417	$\downarrow$ 41%

Table 1: Certified vs. baseline circuit sufficiency. Peak cACC and corresponding circuit size

K

under sufficiency pruning on ResNet-101 for vision datasets and GPT-2 Small for language tasks. Circuits are discovered on ID datasets and evaluated on ID or on OOD shifts.

\Delta

is relative improvements on unrounded values. Certification hyperparameters are in App. Table 2 . All three vision discovery algorithms in App. Table 5 .

Figure 3: Circuit accuracy (cACC) vs. size

K

. Solid lines show certified circuits, dashed show the baseline, with colors distinguishing models. Circuits are discovered on ImageNet and evaluated on ID or OOD data. This figure is extended to ViT-B/16 in App. Fig. 12 and language circuits in App. Fig. 9 & 10 .

Figure 4: Edges of the certified vs. baseline EAP-IG circuits on GPT-2 Small at peak cACC. Annotations report the relative edge reduction and the gain in peak cACC of the certified circuit over EAP-IG. The certified radius

r

denotes the best value for every task.

Figure 5: Features encoded by certified-in, abstain (within Baseline), and certified-out neurons (class: digital watch , ResNet-101). Per layer, top-activating neurons in each category.

Figure 6: Structural stability under distribution shift. Per-class IoU between circuits discovered on ImageNet and re-discovered on each OOD dataset, at the

K

maximizing the certified–baseline

\Delta

cACC gap. Boxes show the distribution over classes.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Domain	Setting	Dataset / Task	$\tau$	$p_{\text{del}}$	$r$
Vision ResNet-101	ID	ImageNet	0.95	0.60	1
	OOD	ImageNet-A	0.95	0.60	1
		OOD-CV	0.95	0.60	1
		ImageNet-C	0.95	0.60	1
		ImageNet-O	0.95	0.60	1
Language GPT-2 Small	ID	IOI	0.90	0.95	9

Appendix

Table 2: Certified algorithm configuration per dataset and task in Table 1 .

	ID	OOD (ours)
IOI	Then, Jessica and Rachel went to the garden. Rachel gave a drink to (Jessica / Rachel)	Then in the morning, Jennifer and Nicholas went to the school. While Nicholas looked around the school, Jennifer talked about the snack, and after a while Nicholas gave a snack to (Jennifer / Nicholas)
IOI-Hard	Then in the morning, Nicole and Katherine went to the restaurant. Katherine gave a ring to (Nicole / Katherine)	Then in the morning, Elizabeth and Allison went to the office. Elizabeth repeatedly asked Allison about the necklace … and resumed the discussion of the necklace, Allison gave a necklace to (Elizabeth / Allison)
Greater-Than	In scenario 920499 at the school with the drink, The war lasted from the year 1799 to the year (1800 / 1840)	In scenario 794799 at the station with the necklace, The war lasted from the year 1399 to the year after a long and distracting discussion at the school about the basketball, followed by more unrelated details, (1400 / 1440)

Appendix

Table 3: OOD prompt construction for the three language tasks. ID prompts follow the original task formulations; OOD prompts (ours) introduce task-specific distractors. Each cell shows the prompt followed by (answer / distractor).

Figure 7: Certified radius

r

at various deletion probability

p_{\mathrm{del}}

values for different confidence thresholds

\tau

. Larger

p_{\mathrm{del}}

and larger

\tau

yield larger certified radii.

Figure 8: Sample complexity vs. certification threshold. Minimum samples

n

required to certify a circuit at threshold

\tau

under perfect agreement and Bonferroni correction over

N=3{,}840

components (the vertex set

\mathcal{V}

of ResNet-101).

\tau^{\star}

is the largest threshold certifiable at a given

n

; any

\tau\leq\tau^{\star}

is certifiable, so larger

n

raises

\tau^{\star}

. Solid curves: circuit-level guarantees at

\alpha\in\{0.01,0.001,0.0001\}

. Dashed: per-vertex (no correction).

Panel of Table 4 — Table 4: Runtime breakdown for per-class ResNet-101 circuit discovery on the ImageNet validation set. Naive scales linearly with $n$ while the optimized implementation caches per-image attribution score (e.g., relevance, activation) across samples. Hardware: Intel Core i7-14700 CPU, 62 GiB RAM, NVIDIA RTX 4090, batch size 50.

Figure 9: Best certified vs. baseline EAP-IG circuits on GPT-2 Small. cACC–

K

curves for the certified circuit (highest peak cACC, blue solid) and EAP-IG (gold dashed) across three tasks (columns) and two settings (rows: ID, OOD). The certified radius

r

for each circuit is annotated in the bottom-right of each panel.

Figure 10: Certified EAP-IG circuits at higher radii on GPT-2 Small. cACC–

K

curves for certified circuits at

r=42

(blue),

r=50

(teal), and

r=59

(purple), compared against EAP-IG (gold dashed) across three tasks (columns) and two settings (rows: ID, OOD). Curves overlap tightly, indicating that larger certified radii are achieved without measurable loss in cACC.

\rectanglecolor CertHL3-617-6 \rectanglecolor CertHL3-1017-10			cACC $\uparrow$				Size $K$ $\downarrow$
Setting	Dataset	Top- $K$	Full	Baseline	Certified	$\Delta$	Full	Baseline	Certified	$\Delta$
ID	ImageNet	Relevance	0.78 $\pm$ 0.02	0.83 $\pm$ 0.02	0.95 $\pm$ 0.02 §	$\uparrow$ 14%	1.000	0.700	0.336	$\downarrow$ 52%
		Activation		0.80 $\pm$ 0.02	0.82 $\pm$ 0.02 §	$\uparrow$ 3%		0.700	0.502	$\downarrow$ 29%
		Rank		0.81 $\pm$ 0.02	0.82 $\pm$ 0.02 ‡	$\uparrow$ 2%		0.700	0.585	$\downarrow$ 17%
OOD	ImageNet-A	Relevance	0.07 $\pm$ 0.01	0.60 $\pm$ 0.03	0.94 $\pm$ 0.01 §	$\uparrow$ 56%	1.000	0.400	0.342	$\downarrow$ 15%
		Activation		0.20 $\pm$ 0.02	0.36 $\pm$ 0.03 §	$\uparrow$ 84%		0.400	0.330	$\downarrow$ 18%

Appendix

Table 5: Certified vs. baseline circuit sufficiency across three Top-K scoring algorithms with uncertainty estimates. Peak cACC and corresponding circuit size

K

under sufficiency pruning on ResNet-101. Circuits are discovered on ImageNet and evaluated either in-distribution or on OOD shifts. Significance markers compare certified circuits against the corresponding baseline circuit using paired class-level tests:

{}^{\dagger}p<0.05

{}^{\ddagger}p<0.01

{}^{\lx@sectionsign}p<0.001

Figure 11: Certified circuits are highly stable across seeds, even for the least stable classes. Pairwise IoU between independent runs of the certification pipeline ( $n{=}1000$ masks) across 40 seeds, for the 10 least stable ImageNet classes (ordered least to most stable); each dot is one seed-pair. Even in the worst case IoU exceeds $0.95$ . The dashed line marks the mean over 100 classes, $0.973\pm 0.0015$ (95% CI).

Figure 12: Circuit accuracy (cACC) vs. size

K

on ResNets and ViT-B/16. Solid lines show certified circuits, dashed show the baseline, with colors distinguishing models. Circuits are discovered on ImageNet and evaluated either ID or on OOD data.

Figure 13: Certified circuits scale to large radii given sufficient concept data. cACC vs. circuit size for

r\in\{1,3,11,59\}

(colors) and

|\mathcal{D}_{c}|\in\{50,100,500,1000\}

(rows), across five ID/OOD benchmarks (columns). Solid: certified; dashed: baseline. Large radii degrade at small

|\mathcal{D}_{c}|

but recover by

|\mathcal{D}_{c}|=1{,}000

. ResNet-101,

\tau=0.95

n=1{,}000

Figure 14: Effect of radius and

|\mathcal{D}_{c}|

at fixed

K=0.60

. cACC (top), effective circuit size (middle), and abstention rate (bottom) as a function of certified radius for

|\mathcal{D}_{c}|\in\{50,100,500\}

. Larger

|\mathcal{D}_{c}|

stabilizes both cACC and abstention at high radii; effective circuit size stays roughly constant. ResNet-101,

\tau=0.95

n=1{,}000

Figure 15: Effect of radius and

|\mathcal{D}_{c}|

at the per-setting optimal

K

. Peak cACC (top), corresponding circuit size (middle), and abstention rate (bottom) as a function of certified radius. With

K

optimized per setting, higher radii yield more compact circuits without sufficiency loss when

|\mathcal{D}_{c}|

is large enough. ResNet-101,

\tau=0.95

n=1{,}000

Figure 16: Certified circuits outperform majority vote at identical compute. cACC vs.

K

for certified, majority vote (same

n

>

50% inclusion, no

\tau

), and baseline across five benchmarks. The gap between certified and majority vote isolates the contribution of certification (through the threshold

\tau

) beyond ensemble averaging.

Panel of Figure 17 — Figure 17: Features encoded by certified-in, abstain (within baseline), and certified-out neurons (ResNet-101). Per layer, top-activating neurons in each category. Certification improves cACC while shrinking the circuit by abstaining from unstable, spurious neurons.

Panel of Figure 18 — Figure 18: Features encoded by certified-in, abstain (within baseline), and certified-out neurons Extension of App. Fig. 17

Panel of Figure 19 — Figure 19: Features encoded by certified-in, abstain (within baseline), and certified-out neurons Extension of App. Fig. 18

Explore similar work

Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees
Feb 18, 2026Itamar Hadad, Guy Katz, Shahaf BassanCircuit Discovery Mechanistic Interpretability
School of Computer Science and Engineering, The Hebrew University of Jerusalem
How Much Do Circuits Tell Us? Measuring the Consistency and Specificity of Language Model Circuits
May 8, 2026Michael Li, Nishant SubramaniCircuit Discovery Mechanistic Interpretability
Northeastern University · Carnegie Mellon University – Language Technologies Institute
Seeing Through Circuits: Faithful Mechanistic Interpretability for Vision Transformers
Apr 15, 2026Nina Żukowska, Wolfgang Stammer, Bernt Schiele +1Transformer Interpretability Mechanistic Interpretability
Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Feb 18, 2026J/K move · Enter open · S save

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

Circuit Discovery Mechanistic Interpretability

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees

How Much Do Circuits Tell Us? Measuring the Consistency and Specificity of Language Model Circuits

Seeing Through Circuits: Faithful Mechanistic Interpretability for Vision Transformers