Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates
Authors: Hang Chen
Jiaying Zhu
Xinyu Yang
Wenya Wang
Venue: NeurIPS 2025 poster ()
Keywords: mechanistic interpretability
language models
circuit discovery
logical gates
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We systematically introduce AND, OR, and ADDER gates and analyze the faithfulness and completeness via these gates, and we also propose a framework to fully discovery these gates and obtain some findings.

Abstract: Circuit discovery has gradually become one of the prominent methods for mechanistic interpretability, and research on circuit completeness has also garnered increasing attention. Methods of circuit discovery that do not guarantee completeness not only result in circuits that are not fixed across different runs but also cause key mechanisms to be omitted. The nature of incompleteness arises from the presence of OR gates within the circuit, which are often only partially detected in standard circuit discovery methods. To this end, we systematically introduce three types of logic gates: AND, OR, and ADDER gates, and decompose the circuit into combinations of these logical gates. Through the concept of these gates, we derive the minimum requirements necessary to achieve faithfulness and completeness. Furthermore, we propose a framework that combines noising-based and denoising-based interventions, which can be easily integrated into existing circuit discovery methods without significantly increasing computational complexity. This framework is capable of fully identifying the logic gates and distinguishing them within the circuit. In addition to the extensive experimental validation of the framework's ability to restore the faithfulness, completeness, and sparsity of circuits, using this framework, we uncover fundamental properties of the three logic gates, such as their proportions and contributions to the output, and explore how they behave among the functionalities of language models.

Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates
Hang Chen
Jiaying Zhu
School of Computer Science and Technology
School of Computer Science and Engineering The Chinese University of Hong Kong jyzhu2 4 cuhk eack.edd... edu.hk
Xi'an Jiaotong University
albert2123@stu xjtu. edu. cn
Xinyu Yang"
Wenya Wang
School of Computer Science and Technology Xi'an an Jiaotong University yxyphd@mail x xjtu. edu.en cn
School of Computer Science and Engineering Nanyang Technological University wangwy edu.sg sg
Abstract
Cireuit discovery has gradually become one of the prominent methods mech- anistic interpretability. and research on circuit completeness has also garnered increasing attention. Methods of circuit discovery that do not guarantee complete- ness not only result in circuits that are not fixed across different runs but also cause key mechanisms to be omitted. The nature of incompleteness arises from the presence of OR gates within the circuit, which are often only partially detected in standard circuit discovery methods. To this end, we systematically introduce three types of logic gates: AND, OR, and ADDER gates, and decompose the circuit into combinations of these logical gates. Through the concept of these gates, derive the minimum requirements necessary to achieve faithfulness and completeness. Furthermore, we propose framework that combines noising-based and denoising-based interventions, which can be easily integrated into existing cir- cuit discovery methods without significantly increasing computational complexity. This framework capable of fully identifying the logic gates and distinguishing them within the circuit. In addition to the extensive experimental validation of the framework's ability restore the faithfulness, completeness, and sparsity of circuits, using this framework, we uncover fundamental properties of the three logic gates, such their proportions and contributions to the output, and explore how they behave among the functionalities of language models.
Introduction
As intervention-based approach mechanistic interpretability. circuit discovery allows for the extraction of subgraphs from the computational graph of a language model that play a significant role task performance, referred as circuits 2 4 Several key studies have supported its development (5) 6), such as those focusing on ensuring that circuits faithfully reflect the model's sss outputs [2] 77 enabling efficient circuit extraction g and addressing scalability challenges for
models with extremely large parameters and corpora 10
As the concept of circuits evolves, recent attention has increasingly focused the completeness of circuits in addition to faithfulness. For example, completeness has been redefined such that
Corresponning author 'Coresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

when a circuit is removed from the computational graph, the performance of the task should degrade significantly [2
[3]. Nevertheless, current circuit discovery methods have been found lack completeness 9 Moreover, theory analysis (14) indicates that incomplete circuits lead to two potential pitfalls: non-transitivity and preemption, which prevent the recovery of the key mechanisms underlying the circuit. Finally, incompleteness results in variability in circuit discovery outcomes, making the circuit appear more like an arithmetic solution to obtain the output rather than representing a closed-form solution with interpretability [15).
Incompleteness largely arises from the presence of OR gates [6 2. For instance, consider a model M that employs two identical and disjoint serial circuit paths, C1 and C2. which operate in parallel and whose outputs are subsequently combined via an OR operation. In this case, identifying either path is sufficient to achieve faithfulness, and removing the other path is a preferable choice for promoting sparsity. However, restoring completeness by discovering OR gates remains a challenge. The simplest approach, which involves repeated interventions on combinations of components [14], could theoretically uncover the complete OR gate; however, this makes circuit discovery an NP problem (We explained it in Appendix E.I). Additionally, while denoising-based intervention methods can rapidly restore OR gates [17) they lead to a more severe loss of faithfulness. Furthermore, these methods fail to isolate the OR gates from the final circuit, resulting in lack of logical interpretability.
To this end, we introduce the concept of logic gates, where any circuit can be decomposed into AND, OR, and ADDER gates, and propose a systematic framework to uncover and separate all the gates, and then to explain their correspondence faithfulness or completeness with the sparsity constraint. Our specific contributions are as follows:
1. We systematically introduce three types of logic gates that compose a circuit: AND, OR, and ADDER gates. Through these gates, we are able to infer the minimum requirements for circuit to achieve faithfulness and completeness, as well assess the capability of noising- and denoising- based interventions in restoring these gates. Based on these corollaries, we analyze three types of prevailing circuit discovery methods, named greedy search 18 M. linear estimation [8] 19], and differentiable mask [9 12 [0]. by evaluating their ability to recover the three logic gates and their faithfulness and completeness. Moreover, we conduct experiments provide empirical evidence supporting these theoretical conclusions.
2. We propose framework capable of fully discovering the three logic gates, which can be easily extended to current circuit discovery methods with constant-time complexity. Our frame- work combines poising-based and denoising-based interventions, ensuring both the faithfulness and completeness of the circuit, and enabling the separation of AND, OR, and ADDER gates from the final circuit. Extensive experimental results demonstrate that our framework achieves promising faithfulness and completeness. Additionally, to ensure consistency in the granularity of noising-base and denoising- based interventions. we introduce a misaligmment score for AND and OR gates to measure whether the scales of the two intervention strategies are aligned when combined.
3. We explore the characteristies of AND, OR, and ADDER gates in circuit, including their proportions and contributions to the output, building upon our proposed logic gates and recovery framework. Furthermore, examine the relationship between logic gates and the functionality of language models. Experimental results show that OR gates typically link multiple backup paths for the same function, while AND gates often connect paths for different necessary functions.
2 Preliminaries
2.1 Circuit Discovery
In Transformer decoder-based language models, the forward pass is typically conceptualized as computational graph G. where the nodes represent components (such as attention heads, MLPs, or even more granular elements like the query, key, and value matrices) and an edge + denotes connection where the output of component serves as input to component j. Circuit discovery seeks to identify subgraph (circuit) C C G that captures the task-relevant behavior of the model [3].
The process used to prune and obtain the circuit
referred to as intervention (also known as knockout, ablation) [7 20 21 22 For given task T, each sample is referred to as clean text, and the corresponding forward pass yields the clean activation v; at each component i. A perturbed version of the input, denoted 5, is called corrupted text, producing a corresponding corrupted

---

activation The corrupted activation 2; depends on the specific ablation method used. For example. ZERO ABLATION sets ã; while NOISE ABLATION draws 2; from a predefined noise distribution. A widely used method, INTERCHA AGE ABLATION, defines ã;; as the activation resulting from an input text that has been minimally perturbed to produce a different task label [TO.
The intervention is divided into two strategies: noising-based intervention (hereafter referred to as intervention (hereafter referred as Dn) [24). The Ns first runs the clean
Ns) and denoising- text in the computational graph. Then, corrupted activations replace each clean activation to observe the change in the final output y. If replaced (also known as removed or pruned) activations lead to a significant change in output, they are considered to make an important contribution to the task T and should be retained in the circuit [17]. Let py (y]z) denote the model's original output, Pc (z, .) represent the circuit's 's output after intervention. Specifically, if an edge j + i is retained within C, the activation of component keeps the clean one (I;). Conversely, it is replaced by the corrupted one (i:). Let denote the requirement of sparsity, and T) represent the distance used to quantify the difference between the two outputs. Ns has the following objective:
arg min B(e (D(p C
R)]], s.t. 1 - |C/////
(I)
Equation| I Jindicates that the circuit is subgraph that most closely approximates the functionality of the computational graph, where the components and edges have the most significant effect on the output. Similarly, the Dn first performs the corrupted run in the computational graph, and then replaces the corrupted activations with the clean activations. Those activations that lead to significant changes in the output (g) consist of the circuits. Dn thus has the following objective:
arg min B (a.a)) (Ping (0) (e s.t. 1 |C//
Most of the related work on circuit discovery follows the Ns strategy. We categorize these works
into three types: (1) Greedy search 2 18 11, which iteratively examines each edge (or node)
through intervention to obtain a greedy solution for the circuit.
(2) Linear estimation [8] [9].
where the contribution of each edge approximated by gradient measure obtainable in a single backward pass. This approach ranks the importance of each edge to approximate the circuit. (3) Differentialle masks
(9 22 10, where learnable mask assigned each edge (or node), treating circuit discovery as an optimization problem to derive the optimal circuit.
2.2 Circuit Evaluation
Circuit evaluation is primarily defined by three aspects: faithfulness, completeness, and sparsity.
Faithfulness refers to the circuit's ability to perform task T isolation, which is defined as the
difference between the circuit's 's output and the model's original output [66 9 [7]. This is represented
in Equations] as (( (D( (yl x) [Pc x, ]])] (simplified as DiG C)). Method ACDC [16] measures faithfulness by computing the average difference in the unnormalized output logits between the correct token and an incorrect option. Recently, work ( 25 proposes that KL divergence provides better measure of the distribution over the vocabulary, while other work p 15] suggests that task accuracy can avoid the overemphasis on irrelevant vocabulary in the KL divergence. In this
paper, we measure faithfulness using both KL divergence and task accuracy as metries.
Completeness refers to whether the circuit includes all the important paths that have an effect on the output. The work [16] first introduces the concept of circuit completeness, stating that C and G should ensure similar outputs even under any knockout. Therefore, the incompleteness score is defined as the difference D(C KIG \ K.) for any subcircuit K. C C. Existing work 9 [5] proposes that insufficient sampling of may lead to unreliable approximations (we show the practical results in Appendix A). and thus recommends evaluating completeness by assessing the performance after the circuit's 's removal from the computational graph on the task T, iee. D(g \ C 13 12 paper, we also adopt to evaluate completeness.
In this
Sparsity refers to that the circuit should be as small as possible. Currently, many works 10 9 1. recommend measuring sparsity using the ratio [Cl/[g]. which represents the proportion of edges in the circuit relative to those in the computational graph. In fact, higher sparsity tends to result in lower faithfulness, meaning that the circuit always reflects some trade-off between sparsity and faithfulness.
3

---

3 Circuit Logic
3.1 Logical Gates
have increasingly observed that within circuit, certain subcircuits influence the output according to logical relationships resembling AND or even OR operations. Building on these findings. we systematically introduce three fundamental circuit logic types: the AND gate, OR gate, and ADDER gate.
Recent studies [66 2 2
We assume a common paradigm in which a receiver node B, which is connected by more than sender node A1, A2,... For any edge A, - B, we use binary values 'O' and 'I' to represent the activation state of node. Specifically, A, = 0 indicates that node Ag is removed, ablated, or deactivated, whereas A, indicates that node A; is retained and active. When the sender nodes are ablated, the effect of node B on the output exhibits three distinct patterns, which are as follows:
Definition 1.
AND: All sender nodes satisfy an AND logical relationship with the receiver node, i.e., B = A1 A A2 A.... In this case, node B exerts significant effect on the output only if all of its sender nodes are retained. If even single sender node is ablated, the effect of B on the output is nearly eliminated.
OR gate: All sender nodes satisfy an OR logical relationship with the receiver node, i.e, B = A V A2 ..... In this case, node B always exerts significant effect on the output if one more of its sender nodes are retained. Only if all sender nodes are ablated, the effect of B on the output is nearly eliminated.
ADDER gate: all sender nodes satisfy an ADDER logical relationship with the receiver node, i.e., B = A A₂ .... In this case, node B exhibits its maximal effect on the output only when all of its sender nodes are retained. If any single sender node is ablated, the effect of B on the outpur is substantially diminished; when all sender nodes are ablated, B's effect the output is reduced to zero. Accordingly, we define the state of B as taking values 0.1.2...., where the total number of distinct states equals the number of sender nodes.
Theoretical analyses support the view that Ns is capable of recovering complete AND gate but fails to recover a complete OR gate, whereas Dn demonstrates the opposite pattern [17). This asymmetry is straightforward to interpret. The Ns procedure corresponds to the transition from a clean activation state (state = 1) to a corrupted activation state (state = 0). Since all gates can be regarded as being initialized with activation states equal to 1, any transition to state = 0 induces significant change in the effect of AND and ADDER gates on the output. Consequently, Ns can reliably identify AND and ADDER gates. Conversely, the Dn procedure corresponds initialization with activation states equal to O. In this case, any transition to state = produces a significant change in the effect of OR and ADDER gates on the output. Moreover, design toy model to explain ADD, OR, ADDER gates in Appendix [
Therefore, we denote the circuit constructed under the Ns strategy as CNs, and the one constructed
under the Dn strategy as CDn Based on the above set-thcoretic relationships between CNs and CDn. we extract subsets of edges corresponding to AND, OR, and ADDER gates as follows:
AND gate (CAND): edges that are present in CN. but absent from CDa.
OR gate (CoR): edges that are present in Cpa but absent from CNs-
ADDER gate (CADder): edges that are shared between CNs and CDn-
We conduct an ablation on these edges: for each gate, we randomly remove either one two edges on the same receiver node and measure the resulting change in the KL divergence of the output. This procedure is repeated 30 times for each receiver node, and the distributions of AKT values are summarized via box plots, as shown in Figure T (Detailed results are shown in Appendix H.2). We selected the computational graph of GPT2-small G. and Indirect Object Inference (IOI) [66] as the test task. For the baseline methods, we chose ACDC [2] to represent the greedy search method, EAP g to represent the linear estimation method, and EdgePruning (10] represent the differentiable mask method. For details regarding the implementation of these strategies within each baseline, we refer the reader to Appendix

---

A1
A2
A3
A4
A1
A2
A3
A4
A
A2
A
A4
AND
OR
AND
OR
AND
OR
B1
B2
B1
B2
B1
B2
ADDER
ADDER
ADDER
C
C
C
(a) Complete Circuit
(b) Max faithfulness and sparsity (c) Max completeness and sparsity
Figure 2: Presentation of a toy model designed to elucidate the logical relationships among faithful-
ness, completeness, and sparsity. Suppose that A₁ A Ag B1, A3 A B2, and B1 + B2 C, and among the three only C' connected to the output. When optimizing for faithfulness and sparsity alone, it is possible remove ensuring the minimal number of edges. Similarly, when optimizing for completeness and sparsity, one edge from the AND gate (either A - B1 A2 + B₁) can be eliminated for sparsity.
edge from the OR gate (either A₃ B2 or A4 B2). thereby
In Figure I for AND gates, the AKL values result- ing from removing one versus two edges similar, consistent with the conclusion that the disruption of any single edge in AND gates renders the gate inef-
KOBER RODER-WAOP
Targe
DA Gedges
BS ledge
fective. For OR gates, removing a single edge has
little effect on AKL, supporting the idea that the OR
gates remains functional as long as at least one edge OR gates remains intact. In contrast, for ADDER gates, removing two edges leads to significantly larger increase AKL compared to removing one, indicating that the edges contribute independently to the gate's function.
Edgo Pruning
Figure 1: AKL L in removing and 2 edges of AND, OR, ADDER gates.
3.2
How to Use Logical Gates to Interpret Faithfulness and Completeness
These logical gates reveal some interesting phenomena as shown in Figure 2 For optimal faithfulness and sparsity, the circuit only needs to include one edge from each OR gate. For optimal completeness and sparsity, the circuit only needs to include one edge from each AND gate. Based on the definitions Section 2,
we can draw the following corollary regarding these properties:
Corollary 1. The minimal edge subset that satisfies optimal faithfulness consists of all edges from the AND gates, all edges from the ADDER gates, and any one edge from each OR gate. The minimal edge subset that satisfies optimal completeness consists of all edges from the OR gates, all edges from the ADDER gates, and any one edge from each AND gate (The proofs are shown in Appendix C.
Corollary provides an explanation for why existing circuit discovery algorithms predominantly adopt the Ns strategy. The reason is that Ns is able to recover complete AND and ADDER gates, while its recovery of OR gates remains incomplete. This tradeoff corresponds precisely to the optimal balance between faithfulness and sparsity. Conversely, the Dn strategy is not adopted because fails to recover complete AND gates, thereby severely compromising the faithfulness of the resulting circuit.
Therefore, we further evaluate the performance of existing work terms of faithfulness and complete- ness. Table [1 presents the specific results for the three types of circuit discovery methods mentioned in Section
Among these, methods based on greedy search and differentiable masks can identify partial OR gates, whereas methods based on linear estimation are unable detect any edges of OR gates. Similarly, methods from Dn exhibit similar pattern. While they can completely identify OR and ADDER gates, methods based on greedy search and differentiable masks can detect partial AND gates, while methods based on linear estimation fail to identify any. In Appendix D we explain why greedy search and differentiable mask methods are able to identify some edges, whereas linear estimation completely fails to do so. Moreover, inspired by 22] we design a simple one-layer transformer toy model implement the basic AND, OR, and ADDER gates, and validate the performance of these circuit discovery methods corresponding to the conclusion from Table [
5

---

Table 1: Capabilitiess and performances of three types of circuit discovery methods in recovering logical gates, faithfulness, and completeness. The symbol v represents the ability to fully satisfy the corresponding requirement, x indicates the complete inability to satisfy the corresponding requirement, and O denotes the ability to partially satisfy the corresponding requirement.
Strategy
Method
AND
OR
ADDER
Faithfulness
Completeness
greedy search 18
X
linear estimation
differentiable mask 9 12.
greedy search 2
Dn
linear estimation
8 19
X
differentiable mask
10
V
Naising
Dempising
Denotsing
Ground Truth
AND
ADDER
ADDER
OR
Ground Truth
AND
ADDER
Osserved Results
AND
Obseave Results
AND
OR
(a) Aligned granularity
(b) Misaligned granularity
Figure 3: A Venn diagram for CN. and CDn In the case of granularity alignment, the intersection rectly separates the AND, OR, and ADDER gates (left figure). However, in the case of misalignment, it results in some ADDER gates being incorrectly classified AND (or OR) gates (right figure).
3.3 Granularity Alignment between CNs and CDn
The intersection operation mentioned above raise concerns about the granularity alignment between CN. and CDn As illustrated in Figure 3 if the number of edges in Cx. significantly exceeds that in CDn some edges identified as the AND gates could belong to the true type of the ADDER gates. This misalignment in granularity two metrics (refer to Appendix FD to assess the degree of misalignment between CNs and CDa when performing intersection.
also occur when CDu is considerably larger. Therefore, propose
We report the misalignment of CNss and CDn at different scales Appendix F The results indicate that when the number of edges in the Dn circuit is approximately equal to that in the Ns circuit, both the misalignment score and standard deviation reach an acceptable level. Therefore, throughout this paper, we assume that the optimal alignment occurs when Ns and Dn contain an equal number of edges and conduct experiments based on this assumption by scaling the number of edges identified by Ns and Dn strategies in a similar range.
4 Discovering Logically Sound Circuit
4.1 Optimization for Logically Sound Circuit
Existing baseline methods are capable of recovering only complete AND and ADDER structures, as demonstrated in Table Therefore, the recovery of complete OR gates remains challenge. Several approaches can be considered to address this problem, such as introducing additional combinations of interventions varying the order of the intervention to identify different surviving edges of the OR gate, or incorporating a completeness score, such as DG \ C G)) into the circuit discovery process. However, these approaches come with significant drawbacks. Expanding the space of intervention combinations renders circuit discovery an NP problem. Meanwhile, the inclusion of completeness scores is incompatible with non-differentiable optimization strategies such greedy search, and it also fails to effectively split the three logic gate types in the recovered circuits.
Therefore, we propose a combined Ns+Dn approach to recover logically complete gates. This method compatible with a wide range of circuit discovery algorithms, introduces minimal additional computational overhead, and enables clear and effective separation of the three types of logic gates.

---

arg min Waraa MAC
R
K.
730
2000
566
1.00
2008
1900
Pcsgos
2ceges
(a) 1OI task
(b) GT task
(c) SA task
Figure 4: Completeness evaluation of circuit from Ns and NS+Dn.
Ns+Dn has the following objective:
pe(s/ 2)) + (ppg (ū ( F,,),,, s.t. 1 |C//// 2 (3)
C
In brief, for each baseline, we modify its implementation to perform both the Ns and Dn strategies in parallel, whereas originally only the Ns strategy applied.
4.2 Validation of Logically Sound Circuit
In this subsection, we focus on the faithfulness and completeness of the logically sound circuit (from our framework in Section 4.1 denoted by CNa+Da) and the circuit of existing work (since existing work generally adopts Ns as basic intervention strategy, we denote it by Cva). Similar to Section 3.1 we select GPT2-small the computational graph, and ACDC, EAP, and EdgePruning methods to represent greedy search, linear estimation, and differentiable mask, respectively. We examine the circuits obtained through Ns, Dn, and Ns+Dn. For instance, in ACDC, when intervening each edge, we simultaneously compute the effect of substituting the clean activation with a corrupted one the clean run, and the effect of substituting the corrupted activation with clean one in the corrupted run. In EAP, we compute gradients under both clean and corrupted conditions. For EdgePruning, replace Equation 1 with Equation 3 the optimization objective. Detailed implementation can be found in Appendix E.3 These experiments are conducted on three mainstream tasks for
circuit discovery, namely indirect object inference (IOI) (16), greater than (GT) (26), and syntactic agreement [.]
The details of these tasks are presented in Table 2
Table 2: An overview of the tasks and datasets.
Task
Exumple([Comupte text])
Output
corrupted output
10I
When Mary and John went to the store, John (Alice) gave a drink to
Mary
other names
The war lasted from 1517 (1501) to 15
18 or 19 or.. 99 themselves
other digits
SA
Many girls (girl) insulted
herself
4.2.1 Completeness
Following the definition of completeness in Section 2 we first compare the changes in KL divergence and accuracy for the corresponding tasks (IOI, GT, SA) when the circuit is removed from the computational graph. Specifically, compare the differences between the original circuits (obtained through Ns) and the logically sound circuits (obtained through Ns+Dn) after removal, for three methods: ACDC, EAP, and EdgePPuningg To account for the effects of sparsity, constrain the number of edges in both circuits to remain consistent across six sparsity levels: 100, 200, 500, 1000, 2000, and 5000 edges. Figure 4 shows that, both in terms of KL divergence and accuracy, the performance of circuits removed through Ns+Dn is noticeably weaker compared to those removed through Ns. This corroborates Corollary [I where we note that Ns, due to its inability to fully recover the OR gate, results in suboptimal completeness. Additionally, we observe that the gap between Ns and Ns+Dn is largest in both metrics in the EAP method (see the solid line in Figure J where Ns fails to recover any edges of the OR gate. Additionally, since ACDC and EdgePruning are generally able to identify one OR edge, the recovered OR edge exhibits some degree of randomness. In the case of ACDC, this randomness is influenced by the search order, while in the case of EdgePruning, is influenced by the initial values of the mask. Moreover, we show the detailed results including in Appendix G
7

---

Table 3: Difference in Hamming distance between the CN2 and CN (we compute the average Hamming distance between CNs and subtract the average Hamming distance between CN (W++Dn). larger value indicates that the circuits obtained through Ns exhibit greater randomness compared to those obtained through Ns+Dn. #edges represents the number of edges in circuits.
10I
GT
SA
Nedges
ACDC
EAP
EdgePruning
ACDC
EAP
EdgePruning
ACDC
EAP
EdgePruning
100
3.4
0.640..1
8.413.7
4,8+0.9
0.5.0.1
12.7:4.9
2.8+0.4
1.1
15.345.8
200
5.9+1.3
1.2+0.3
18.1+6.7
6.7+1.8
1.3+0.2
22.5+9.1
4.340.9
2.2+0.5
28.+11277
500
14.7+3.7
1.8+0.7
44.5=13.8
16.9=4.2
1.6+0.8
49.1=15.6
12.8+2.9
2.9=0.9
55.9=16.7
1000
21.8:5.3
4.7
89.6=27.9
23.6:6.4
4.4g1.6
97.5a29.4
19.744.3
5.7=2.8
108.2431.4
2000
49,5+12.9
7,9+2.9
195.3+57.8
55.7=14.9
8.6+3.5
211.7=66.2
44.8=15.2
8.8=3.1
237.4
5000
127=28.5
14.526.9
509.5
136.5a33.4
15.946.1
564.8=181.1
113.7+5.8
15.425.8
688.9:144.5
<a0.9>
<a0.1>
<65.9>
< 8>
<m1>
<00 5>
<a2.2>
<mb>
<m5>
<.5.5>
<m8>
<resid_
(a) AND gate
(b) OR gate
(c) ADDER gate
Figure 6: The cases with 2-layer gates of AND, OR, ADDER circuits.
To further validate completeness, we test the overlap of randomly generated circuits by extracting 30 distinct circuits under different random seeds and calculating the Hamming distance between pairs of these circuits to assess the randomness of the discovered circuits. Table 3 shows that the randomness of ACDC and EdgePruning is significantly higher than that of EAP, and it increases with the sparsity scales (as more OR gates discovered). Additionally, the randomness of the circuits obtained through Ns+Dn is consistently lower than that of the circuits obtained through Ns, further supporting the claim that the inclusion of all three logical gates ensures optimal completeness.
4.2.2 Faithfulness
In Appendix H we compare the circuits obtained using three strategies-Na Dn, and Ns+Dn-under the same sparsity constraints (specifically, we select edge counts of 100, 200, 500, 1000, 2000, and 5000) in terms of KL divergence and accuracy. The results show that, in terms of faithfulness, we have the relationship: CA R Cx. > CDn- Figure 5 Slillustrates the average of the three methods on the 1OT task to corroborate this conclusion. More results can be found in Figure 9 (a)-(c, which further supports the faithfulness requirements asserted in Corollary [
Accurity
5 15
0.2
100
2000
5300
#odges
Figure 5: The average of three methods
in faithfulness of IOI task.
5 Exploration on Logical Gates
5.1 Graph Study
In Appendix[] I we present the circuits of the AND, OR, and ADDER gates recovered by ACDC on the 1OI task and map the functions of the components those the previous IOI eircuit [16]. We show parts of these circuits as demonstrations in Fi each color represents one function in IOI circuit and blocks represent components at different locations, such as "a5.9" indicating the 9-th attention head in the 5-th layer, and "m8" referring to the MLP in the 8-th layer. The complete gate circuit can be found in Figure of Appendix []. The results are interesting, revealing that the AND gates typically receive edges from different functions, suggesting that these functions must work together to support the receiver's activation. In contrast, the OR gates almost exclusively receive edges from the same function, indicating that these edges are likely interchangeable due to their
8

---

execution of the same function. The ADDER gates, on the other hand, tend to focus on combining two functions from different layers, with the activation generally considering the outputs both shallow-layer and deep-layer functions.
5.2 Output Contribution
In Appendix[] we investigate the contribution of three types of logic gates to the output. The gate effect represents the contribution of the entire gate to the output and the edge effect represents the average contribution each edge to the output. The results show that the contribution of the ADDER gates is significantly higher than that of the AND and OR gates. Furthermore, methods that focus on the edge effect, such as differentiable masks and linear estimation, lead to a higher average effect in the recovered circuit.
5.3 Proportion
In Appendix KJ we present the number of AND, OR, and ADDER edges recovered by different methods. The results indicate that the proportion is closely related to the type of circuit discovery method used. For instance, greedy search selects all edges beyond the threshold, resulting in nearly equal numbers of AND, OR, and ADDER edges. In contrast, differentiable mask methods calculate the effect of each edge, which is disadvantageous for gates like AND and OR that contain multiple edges. As result, the number of ADDER edges is significantly higher.
Conclusions
This paper systematically introduces three logic gates-AND, OR, and ADDER-to explain the essential requirements of circuit faithfulness and completeness. Furthermore, it provides an analysis of how existing circuit discovery methods perform with respect to these logic gates. Additionally, we propose an Ns&Dn-based method for separating the three logic gates, and for restoring logically sound circuit. We empirically validate the differences in faithfulness and completeness between the logically sound circuit and existing circuits. Finally, we explore the relationships between the logic gates in terms of distribution, contribution, and functionality.
6.1 Limitations and Future Research
The three logical gates under discussion in this paper are, in principle, derived from the intersection of CN2 and CDn- Nevertheless, it must be acknowledged that other types of logical gates may also exist-for instance, the XOR gate-whose underlying logic cannot be captured solely through the simple intersection of CNs and CD.. That said, contend that the three gates obtained from this Piarsection-ND... OR, and ADDER-an are already sufficient to cover all edges of the circuits constructed from CN. and Dn- For the purposes of the present scope of research, this coverage is adequate.
Moreover, with complete understanding of the logical relationships between edges, the circuit becomes more useful for offering insights into model control. For instance, a logically sound circuit offers novel approach for verifying the potential combination of tasks through boolean satisfiability, which is treated as our future study. We have demonstrated the potential contributions completeness research with toy task of model unlearning, shown in Appendix I
6.2 Societal and Ethical Impact
Our work aims to facilitate the process of understanding and explaining the logical connections in language models, which is crucial for their continued safe development and deployment. We do not foresee logically sound circuit and logical gates being used towards adverse societal or ethical ends.
Acknowledgments and Disclosure of Funding
This research/project is supported by the National Research Foundation, Singapore under its National Large Language Models Funding Initiative, (AISG Award No: AISG-NMLP-2024-000)

---

References
[1] Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodss, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. http://transfoomerecccciii pwtpppplpppppppppapppppp /fram/wwrk/nddxe.nnnonoo
[2] Arthur Conmy, Augustine Mavor-Parken Aengus Lynch, Stefan Heimersheim, and Adria Garriga-Alonoo. Towards automated circuit discovery for mechanistic interpretability. Advances 2023.
in Neural Information Processing Systems,
[3] Daking Rai, Yilun Zhou, Shi Feng, Abulhair Saparov, and Ziyu Yao. A practical review of mech- anistic interpretability for transformer-based language models. arXiv preprint arXiv:2407.02640 2024.
[4] Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom in: An introduction to circuits. Distill, 5(3):c002240011 2020.
[5] Aliyah R Hsu, Georgia Zhou, Yeshwanth Cherapanamjeri, Yaxuan Huang, Anobel Y Odisho, Peter Carroll, and Bin Yu. Efficient automated circuit discovery in transformers using contextual decomposition. arXiv preprint arXiv:2407.008886 2024.
[6] Tal Haklay, Hadas Orgad, David Bau, Aaron Mueller, and Yonatan Belinkov. Position-aware automatic circuit discovery. arXiv preprini arXiv:2502.04577, 2025.
[7] 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. arXiv preprint arXiv:2403. 19647, 2024.
[8] Aaquib Syed, Can Rager, and Arthur Conmy. Attribution patching outperforms automated circuit discovery. In Proceedings of the 7th BlackboxNLP Workshop: Analyzing and Interpreting Neural Networks for NLP, pages 407-416, 2024.
[9] Lei Yu, Jingcheng Niu. Zining Zhu, and Gerald Penn. Functional faithfulness in the wild: Circuit discovery with differentiable computation graph pruning. arXiv preprint arXiv:240..03779 2024.
[10] Adithya Bhaskar, Alexander Wettig, Dan Friedman, and Danqi Chen. Finding transformer circuits with edge pruning. Advances in Neural Information Processing Systems, 37:18506- 18534, 2024.
[11] Tom Lieberum. Matthew Rahtz, János Kramár, Neel Nanda, Geoffrey Irving. Rohin Shah, and Vladimir Mikulik. Does circuit analysis interpretability scale? evidence from multiple choice capabilities in chinchilla. arXiv preprint arXiv:2307.0944 2023.
[12] Nicola De Cao, Leon Schmid, Dieuwke Hupkes, and Ivan Titov. Sparse interventions in language models with differentiable masking. In Proceedings of the Fifth BlackboxNLP Workshop Analyzing and Interpreting Neural Networks for NLP, pages 16-27, 2022.
[13] Deniz Bayazit, Negar Foroutan, Zeming Chen, Gail Weiss, and Antoine Bosselut. Dis- covering knowledge-critiee critical subnetworks in pretrained language models. arXiv preprint arXiv:2310.03084, 2023.
[14] Aaron Mueller. Missed causes and ambiguous effects: Counterfactuals pose challenges for interpreting neural networks. In ICML 2024 Workshop on Mechanistic Interpretability.
[15] Hang Chen, Jiaying Zhu, Xinyu Yang, and Wenya Wang. Unveiling language skills under circuits. arXiv preprint arXiv:2410.01334, 2024.
[16] 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 The Eleventh International Conference on Learning Representations.
10

---

[17] Stefan Heimersheim and Neel Nanda. How to use and interpret activation patching. arXiv preprint arXiv:2404.15255, 2024.
[18] Yunzhi Yao, Ningyu Zhang, Zekun Xi, Mengru Wang, Ziwen Xu, Shumin Deng, and Huajun Chen. Knowledge circuits in pretrained transformers. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.
[19] Neel Nanda. Attribution patching: Activation patching at industrial scale. URL: https://www. neelnanda. wwapehhhnissi---nterrrrraaalliin patthiiniiinnniinnnni.ii.. 2023.
[20] Jesse Vig, Sebastian Gehrmann, Yonatan Belinkov, Sharon Qian, Daniel Nevo, Yaron Singer, and Stuart Shieber. Investigating gender bias in language models using causal mediation analysis. Advances in neural information processing systems, 33:12388-12401 2020.
[21] Lawrence Chan, Adrià Garriga-Alonso, Nicholas Goldwosky-Dill, Ryan Greenblatt, Jenny Nitishinskaya, Ansh Radhakrishnan, Buck Shlegeris, and Nate Thomas. Causal scrub- bing, a method for rigorously testing interpretability hypotheses. Al Alignment Fo- rum, 2022. https: :tta:://wwwr /wwwwww.
forum causal-scruiee scrubbinugnggg a method- for
[22] Nicholas Goldowsky-DDe Dill, Chris MacLeod, Lucas Sato, and Aryaman Arora. Localizing model behavior with path patching. arXiv preprint arXiv:2304.05969 2023.
[23] Fred Zhang and Neel Nanda. Towards best practices of activation patching in language models: Metrics and methods. arXiv preprint arXiv:2309. 16042, 2023.
[24] Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. Locating and editing factual associations in gpt. Advances in neural information processing systems, 35:17359-1733 17372, 2022.
[25] Tachyeon Kim, Jachoon Oh, Nak Yil Kim, Sangwook Cho, and Se- Se-Young Yun. Comparing kullback-leibler divergence and mean squared error loss in knowledge distillation. arXiv preprint arXiv:2105.08919 2021.
[26] Michael Hanna, Ollie Liu, and Alexandre Variengien. How does gpt-2 compute greater-than?: Interpreting mathematical abilities in pre-trained language model. Advances in Neural Information Processing Systems, 36:76033-76069, 2023.
[27] Joy Crosbic and Ekaterina Shutova. Induction heads as an essential mechanism for pattern matching in in-context learning. arXiv preprint (rxXix:4477.0011.1 2024.
[28] Jie Ren, Qipeng Guo, Hang Yan, Dongrui Liu, Xipeng Qiu, and Dahua Lin. Identifying semantic induction heads to understand in-context learning. arXiv preprint arXiv:2402. 13055, 2024.
[29] Benjamin L Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis. The evolution of statistical induction heads: In-context learning markov chains. arXiv preprint arXiv:2402.11004 2024.
[30] Jiaming Ji, Mickel Liu, Josef Dai, Xuehai Pan, Chi Zhang, Ce Bian, Boyuan Chen, Ruiyang Sun, Yizhou Wang, and Yaodong Yang. Beavertails: Towards improved safety alignment of Ilm via human-preference dataset. Advances in Neural Information Processing Systems, 36:24678-24700 2023.

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the claims made, including the contributions made in the paper and summary of the important work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discussed the limitations in Section 6 Moreover, Section 3. shows the limitations our corollary, including considering that the receiver node directly connected to the output.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
12

---

Answer: [Yes]
Justification: Section 3.1 provides full hypotheses and detailed examples to explain our theoretical definition.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide full settings of our experiments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
13

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We will make it open-aceess with github link.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c) cc/
public/
cissoooiicyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https?
/ wttp:ccccppccccccccccccc i ies CCodeeoodSuaaee bm ss i oonool icy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Section 4.1 and Section 3.3 provide full settings and details of our two experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Table 3 Figure X provide clear error bars with a.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
14

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix E.3 we claimed that all experiments only need low computational cost in the original setting of the existing work.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We checked the NeurIPS Code of Ethics and ensured that our paper satisfies it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discussed the broader impacts to ML. society in Section 6
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
15

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: We listed the pretrained LMs in footnotes and described the scraped datasets in Appendix
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We listed the URLs and references of existing assets that we used in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
16

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paaperswi haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We didn't release any pre-trained models and large-scale datasets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We didn't 't conduct any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
17

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The paper does not involve any LLMs tools for core methodology, scientific rigorousness, originality of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
btttp:://neerrpsscc//oooteee LLM) for what should or should not be described.
Please refer to our LLM
18

---

A The Preference between Two Types of Completeness Metrics
The earlier completeness evaluation method (proposed by [16]) in fact measures incompleteness, defined as D(C K || K)), where lower score indicates better performance. In contrast, the current method [9] measures completeness, defined as D(G \ C C)] where a higher score is preferable. Importantly, these two metrics are not directly interchangeable that is, 1 D(C K G K)
D(G \ C G).
Nevertheless, a comparison can still be made in terms of the standard deviation. It has been theoretically demonstrated that the earlier completeness method suffers from high variance due to insufficient sampling, leading to instability in the final results. To illustrate this, we provide simple comparison between the previous and current evaluation methods, shown in the Table
Table 4: The standard deviation between two metrics of completeness.
Method
5 sampled K
10 sampled K
20 sampled K
30 sampled K
New metric
ACDC
1.1
1.8
1.4+1.1
1.240.6
1.3+0.13
EAP
1.7#1.5
1.3
1.6+1.2
1.3+0.7
1.4
Edge-P Ours
1.5+1.8
1.411.9
1.441.6
1.640.6
1.2+0.08
0.4+0.3
0.640.4
0.340.3
0.340.2
1.8=0.03
We conducted five different runs of circuit discovery using random seeds, with the random subset K chosen from subcircuits of sizes ranging from 2 5 nodes. For the previous evaluation metric, performed 5, 10, 20, and 30 sampling iterations.
The experimental results clearly support two conclusions:
For algorithms that inherently lack completeness (such as ACDC, EAP, and well as for our own method, which ensures completeness. the previous evaluation metric exhibits large standard deviations across all trials. This indicates that the sampling process for the previous metric is insufficient, rendering the results highly unreliable.
as
2. The evaluation metric significantly reduces variance for all types of circuits, it does not suffer from sampling issues. The variance observed in the results arises from minor differences in the circuits generated by different random seeds.
B
How Does Circuit Logic Model Intervention?
B.1 AND Gate
Consider a simple logical gate: A₁ A2 B (only if both 2A, and ÆA, are present can B be activated), where B directly influences the output. For noising- based intervention (Ns), replacing FA, with A or AA,, with A., produces significant effect on the output. Thus, Ns is capable of detecting the structure {(A1, A2), B3.
However, for demoising- based intervention (Dn), substituting Σ.₁ with FA, alone does not yield noticeable change in the output, as A, remains present. Similarly, replacing FA, with FA, while A, still active also fails to significantly affect the output.
Under a greedy search strategy, if A is first replaced by FA, and the output remains unchanged, the algorithm concludes that A₁ is not relevant and removes it (i.e., replaces A with TA in the scenario of Dn). Subsequently, replacing A, with TA, causes a substantial shift in the output due to the presence of A thereby restoring the structure {(A2), B). since A₁ has already been removed.
Analogously, a greedy search that begins with Ag and then proceeds to Ai would only recover structure ((A1), B}. Therefore, we conclude that Ns is capable of identifying the complete AND gate structure, whereas Dn either fails detect the AND gates or only partially recovers under greedy search conditions.
19

---

B.2 OR Gate
Consider a simple logical gate: A V A2 = (if either J', or A are present can be activated), where B directly influences the output. For Ns, replacing IAi with ãA, alone does not yield noticeable change in the output, as 2 remains present. Similarly, replacing AA, with AA, while AA, is still active also fails to significantly affect the output.
Under a greedy search strategy, if A is first replaced by ΣA, and the output remains unchanged, the algorithm concludes that A1 is not relevant and removes it (i.e., retains AA,). Subsequently, replacing z with A causes a substantial shift in the output due to the lack of support of zAi thereby restoring the structure ((A2), B). since Ai has already been removed.
Analogously, a greedy search that begins with A2 and then proceeds Ai would only recover the structure B).
However, for Dn, replacing öA, with AA AA, with AA produces significant effect on the output. Thus, Dn is capable of detecting the structure A2),
Therefore, we conclude that Dn is capable of identifying the complete OR gate structure, whereas Ns either fails to detect the OR gates or only partially recovers it under greedy search conditions.
B.3 ADDER Gate
Consider a simple logical gate: A1 + A2 = B, where directly influences the output. Since the influence of each edge in an ADDER gate is independent, removing an edge in either Ns or Dn directly impacts the output via its effect on For instance, Ns, replacing 2 AA, with & A, results in B A2. which is significantly smaller than B = Ai + A2. Similarly, in Dn, replacing A with FA, yields B" AI, which is substantially greater than = 0. Therefore, both Ns and Dn are capable of identifying the complete structure of the ADDER gate.
C How Does Circuit Logic Affect Faithfulness, Completeness, and Sparsity?
C.1 Faithfulness
As introduced in Section following scenarios:
2
faithfulness requires that DGG be minimized. Let us consider the
For any gate {(Ai, A2), B), if the circuit does not include all edges or nodes from this gate, it is always possible to find circuit C* = CU A1, A2, B such that D(G]IC) > D(G][C").
For an AND gate {(A1, A2). B). if the circuit C' only includes A₁ and B, the gate effect of this AND gate is not maximized (the influence of is maximized when both A₁ and Ag are present). Therefore, it is always possible to find circuit C* =CUA Ag such that D(G > D(G](C**.
For an ADDER gate A2), B}. if the circuit C only includes A₁ and B, the gate effect of this ADDER gate not maximized (again, the influence of B maximized when both A₁ and A2 are present). Thus, there exists circuit C = C' U A2 such that DCG > D(GIC"").
For an OR gate ((A1, B), if the circuit C only includes A₁ and B, the gate effect of this OR gate is already maximized (the same applies if only Ag and B are included). Therefore, for C* = C U A2, we have D(G|(C) = D(GI(C"). However, from the perspective of sparsity, |C |C|.
Thus, to achieve optimal faithfulness, the circuit must include all edges that result in the maximum gate effects, namely all edges from the AND, ADDER, and OR gates. However, considering sparsity, the gate effect sum remains maximal even if only one edge from each OR gate is retained.
C.2 Completeness
Similarly, completeness requires that D(G \ CIIG) be maximized. Consider the following scenarios:
20

---

For any gate ((A1,A2), B), if the circuit does not include all edges or nodes from this gate, it always possible to find a circuit C CUUA,, A2, B such that D(G C| <
D(G \ C*
For an AND gate ((A1, A2), B), if the circuit C' only includes A and B, then G C will only contain A₂ or the edge A2 B (depending on whether pruning is applied to edges or nodes). Due to the AND operation, B will not produce gate effect. Therefore, for the circuit C* CU A2, we have D(G CIIG) = D(G C=I|G).
For OR gate A2), B), if the circuit C only includes A₁ and B, then G' \ C will only contain Ag or the edge A2 + B. Due to the OR operation, B still produces gate effect. Therefore, it is always possible to find circuit C* C A2 such that D(G \ CIIG) < D(G (*
For an ADDER gate {(A,, A2), B3. the circuit only includes A and B, then \ C will only contain A2 the edge A - B. Due to the ADDER operation, B still produces a gate effect. Therefore, it is always possible to find circuit C* C' U A such that D(G \ CIIG) < D(G C*I])).
Thus, to achieve optimal completeness, the circuit must include all edges that result in the maximum gate effects, namely all edges from the AND, ADDER, and OR gates. However, considering sparsity, the total gate effect remains maximized even if only one edge is retained for each AND gate.
D
Validation of Logical Gates
D.1 Toy Model
Motivated by [2]. to study a toy transformer model with an AND, OR, and ADDER gates, we take a I-Layer transformer model with two heads per layer, ReLU-based activations, and model dimension 1. Specifically, as shown in Figure 7 Let A₁ and A2 be two attention heads with respective biases bias] and biasg. both set to The activation function m based on the ReLU nonlinearity. To ensure that the output of each attention head corresponds directly to its bias, we use zero tensor the input. For corrupted activations, we employ zero ablation- we directly remove the activations along the corresponding edges.
The activation function m is configured differently to simulate logical gates as follows:
AND gate: m(x)= = ReLU(z - 1). Under this setting, the output is I only when both A and Ag are active (i.e., not ablated); otherwise, the output is 0.
OR gate: m(x)
ReLU(1 .²). Here, the output is 1 as long as least of A₁ A2 is active; if both are ablated, the output is O.
ADDER gate; The bias modified to 1.5, and m(x) = ReLU(z). In this case, the output is O when both A, and A2 are ablated; it is 1.5 when only Ai is ablated, I when only A2 is ablated, and 2.5 when both are active.
Under these configurations, evaluate the performance of existing methods on the toy model, as summarized in Table [ For example, under the default Ns, ACDC [2] (representing greedy search), EAP [8] (representing linear estima- tion), and EdgePruning [10 (representing differentiable mask) all successfully identify both A and A₂ in the AND and ADDER gates. However, in the OR gate, ACDC and EdgePruning identify only one of A₁ or A2 specific result depends on the search order in ACDC and the initialization of the mask in sdgePruning-wwilee EAP fails to identify any high-effect edge.
A1
A2
m
Conversely, when these methods are executed under Dn, the outcomes are reversed. In the OR and ADDER gates, all three methods, ACDC, EAP and EdgePruning, now identify both A and Ag. However, in the AND gate, only ACDC and EdgePruning are able to recover one of A, or Az, whereas EAP considers the effects of both be insufficiently strong.
output
Figure 7: A toy model to study AND, OR, and ADDER gates.
Ns can at least guarantee the full recovery of AND and ADDER gates. Greedy search, by retaining previous steps with removed results, can identify one OR
21

---

edge (a detailed analysis is provided in Appendix B). Differenniable mask, optimizing for faithfulness (as per Corollary D.. ensures that at least one OR gate is included (otherwise, optimal faithfulness cannot be achieved), while additional OR edges conflict with the sparsity constraint and are therefore removed. However, linear estimation, when computing the effect of each edge, keeps all other edges in their non-removed state, which results in a failure to detect the OR gate. For example, when computing the effect the edge A C' in the OR gate A + C <- B, the edge C' +- B is also in the clean activation state, leading to very small effect for + C. Similarly, when computing the effect of < B, the edge A + C remains in the clean activation state. In summary, linear estimation is unable detect any edges of the OR gate.
The performance on Dn is the opposite of that on Ns, where, in addition to the full OR gates and ADDER gates, greedy search and differentiable mask can similarly recover one AND edge, just as they could with the OR gates in Ns. Linear estimation also fails to detect the AND gates due to the non-removed status of the other edges. Based on Corollary[ [ we are also able to derive the performance of the three types of methods in terms of faithfulness and completeness.
E Experiment Details
E.1
Why Does Search Strategy by repeating interventions on combinations is NP Problem?
Due the differences in circuit algorithms, this issue cannot be fully proven mathematically. However, we will provide some additional explanation: we treat each ablation as O(1). Assuming the language model contains N nodes, if need to use all possible intervention combinations obtain complete circuit, the time complexity would be O(2 ), which far exceeds polynomial time. However, different strategies can optimize the solution verification process to varying degrees. For example, EAP only requires O(N) time to verify whether the circuit is complete, while gradient descent, making time complexity difficult to estimate. Additionally, greedy search can only perform a greedy verification in O(N) time rather than a thorough verification. Therefore, we ultimately classify this problem as NP problem.
involves
However, our proposed method, which employs the algorithm N₂ + Dn, does not introduce additional computational complexity the existing circuit discovery algorithm. Conceptually, is equivalent to reapplying the N, algorithm once more under the strategy of D.. As a result, the overall time complexity increases by most factor of two relative the baseline algorithm, without imposing any additional nonlinear burden.
E.2 Detailed Results of Figure
Table 5: The changes in KL divergence between the original output and the new output when one or two edges are ablated.
AND
ADDER
(stat(state)
edge2(stato)
(A KLXstato)
(stel(state)
edge2(state)
(A KLXsttre)
(stec(state)
edge2(state)
(A KLXstttt)
remain remain(1)
remain (1)
remaint()
0.28 (1)
remain
remuin(1)
remain (1)
ablate(O)
0.02 (0)
remain (1)
ablate(()
0.27 (1)
remain (1)
ablate(U)
0.32 (1)
ablate
remain(1)
0.04
ablate (0)
remain(()
0.27
ablate
remain(1)
0.36
ablate (0) ablato(0)
(0)
ablate (0)
ablate(0)
0.00 (0)
ablate (0)
ablate(O)
(.00(0)
All three subcireuits exhibit fundamental pattern: the effect on the output is maximized when both edges are retained, and it drops to zero when both edges are ablated (as there is clean activation left to support the node in this case). However, ablation of a single edge yields divergent outcomes:
In AND gate, ablating either edge nearly eliminates the effect on the output. In OR gate, ablating either edge has almost no impact on the output. In ADDER gate, ablating either edge leads to noticeable degradation in the output.
E.3 Baselines
In this work, we select ACDC to represent greedy search methods, EAP X to represent linear estimation methods, and EdgePruning [10] to represent differentiable mask methods. In the following
22

---

sections, we provide a detailed exposition of the original design of each method under the Ns. strategy, the corresponding formulation under the Dn. strategy, and the final approach that integrates both Doth-NN.+Dnn--ff for recovering logically complete gates.
E.3.1 Greedy Search Example: ACDC
The ACDC method identifies important edges by iteratively removing each edge and observing the effect of this intervention on the model output. Edges whose removal causes an effect greater than predefined threshold 7 are retained, while those with an effect smaller than T are pruned. The original algorithm (Ns. strategy), is outlined as follows:
Algorithm 1: The ACDC algorithm in Ns.
Data: Computational graph G, dataset (m:) corrupted datapoints (rr))= and threshold
T>
Result: Subgraph H S H. 4 G
// Initialize H to the full computational graph // Sort H so output first
H. <- ponerrssttopoloiicl_sorrt
v E H do
for parent of do
Huew f H. {w + 4) if D H D (Kl < then 11 Edge is unimportant, remove permanently
// Temporarily zemove candidate edge
H f Hnew
return H
In the Ns. strategy, G denotes the clean run, and H. \ {w + e} represents the replacement of the clean activation on the edge w - o with its corrupted activation. contrast, under the Dn. strategy, refers the corrupted run, and 7 fw - v) indicates the substitution of the corrupted activation on edge w - with the corresponding clean activation.
In the combined Nn. approach, the effects from both strategies are jointly considered. Specifically, the original pruning condition Dx || Hnow) D || H) is replaced with the aggregated criterion: DKI(g (Hnew) DKL (Gelean H + DK (uew) DKL (Commipeed
H) <.
E.3.2 Linear Estimation Example: EAP
The EAP method approximates the effect of each edge using the first-order term of its Fourier expansion, enabling the estimation of all edge effects with a single forward pass. important to note that, during the computation of each edge's effect, all other edges remain in their unpruned (active) state.
Specifically, Ns. has approximation:
L(xldo(z;)) L(x) vo (ū, xT,T Dr.
L(x)
(4)
and Dn. has approximation:
L(Eldo(z)) - L(ū) RJ (T; 2z¹² i
L(ū)
(5)
Jū.1
Therefore, the approximation for Ns.+Dn. is (ā. x T B
L(x) (ū, xz)T
a L())
E.3.3 Differentiable Mask Example: EdgePruning
EdgePruning assigns a learnable mask to each node or edge, where the mask is reparameterized using the hard concrete distribution. In the Ns. setting, the optimization objective corresponds to Equation Consequently, the objectives for the Dn. and Ns.+Dn. settings are given by Equation and Equation 3 respectively.
23

---

In the Ns.+Dn. setting, directly optimizing both objectives jointly can lead to gradient interference and convergence Pareto-optimal solutions, rather than a unified optimum. To address this, we independently compute the final mask values for Ns. and Dn. using Equations 1 and and then obtain the mask for Nn.+Dn. by averaging the two.
F Misalignment Score
Misalignment of AND: For any subcircuit KAND CAND. CAND CAND AAND Let E CAND. i" J" E CAND be any two edges with the same receiver, respectively. The score of misalignment of AND reads:
[ \ AilCCAND \ \(,5)] - EE- ID(CCDD \ | \
(6)
Equation 6 indicates that the higher the score, the higher the misalignment. This is due to their properties: the effect caused by removing one and two edges from the AND gates is similar, while the effect for the ADDER gates differs significantly.
Misalighment of OR: Similarity, let any KOR C COR CÖR CoR KoR, i.j COR, 1" , E CoR- respectively. The score of misalignment of OR reads:
B [D(oR EllCOR \<t)] F [D(CoR \i.jIICR \(","") + +
(7)
Equation 7 utiliiee the properties that the effect does not change by removing edge from OR gates, while it significantly changes from ADDER gates. Additionally, to avoid the bias caused by both effects of ADDER and OR edges being marginally small in large-scale eircuits, we replace the "difference in one edge" with the "difference in difference between one edge and two edges," and introduce a constant to ensure that the score (with m set to 1.5 in practice).
Therefore, for any pair of CNs and CDns we can compute the misalignment using these two scores. We report the misalignment scores resulting from the intersection of Ns and Dn circuits varying scales. Specifically, we select an Ns circuit consisting of 100 edges recovered from the IOI task and examine how the misalignment score changes the number of edges in the Dn circuit varies from 60 to 140. Figure 8 iillustrates that when Dn is significantly smaller than Ns, the misalignment score for the AND gates is high, as many ADDER edges misclassified when Dn is substantially larger than Ns, the misalignment score for the OR gates increases, due to many ADDER edges being misclassified as OR edges. When the number of edges in the Dn circuit is approximately equal to that in the Ns circuit, both the misalignment score and its standard deviation reach an acceptable level.
AND edges. Conversely,
As shown in Figure S when the OR set significantly exceeds the AND set, a large number of misclassified ADDER gates appear only within the OR set, leading much higher misalignment score for OR compared to AND. The misalignment score is more of a "property." reflecting the optimal scale at which OR and AND sets should intersect. We determine the optimal ratio of AND to OR gates by minimizing the sum of the misalignment scores for AND and OR. The optimal results obtained with different methods and datasets are approximately shown in Table
Table 6: The optimal ratio of edge numbers between Cr. and CDn-
strategics
101
ACDC
1.12: 1
1.05: 1
1.07:
EAP
1.09: 1
1.03:1
1.05:
Pigei-runnng
1.11:
1.07:
1.06:
The results show that the proportion of AND is always slightly higher than that of OR, but can be approximated as 1:1. Therefore, throughout this paper, we assume that the optimal alignment occurs when Ns and Dn contain an equal number of edges.
G Experiments of Completeness
In this Appendix, we present the detailed results of the completeness validation, together with comparison against the Dn strategy. The specific results reported in Tables 7 and g In brief,

---

100
Lopal Bokgerd AND
140
CAR of DR
OF
AEDE SLON
Eeguo
Bu0ges OF
TAP Scar
Score
Score
deciges
0.6
78
60
10
300
110
120
130
140
60
72
50
125
110
120
130
140
vedges with denoising
Redges with dencis
Misalignment of AND gate
(h) Misalignment of OR gate
Figure 8: Misalignment score with 100-edges IOI circuit from Ns.
method generally outperforms the approach based Dn. Although the Dn-based method is theoretically capable of identifying all OR gates, it suffers from certain shortcomings in practice. For instance, as shown in Table 1, EAP fails to identify under the Dn framework. Additionally, the greedy strategy may miss some OR gates located beneath branches of AND gates due its dependence on the search order. The differentiable mask approach, on the other hand, suffers from the drawback that, in gates involving multiple edges, the mask values assigned each edge tend to be lower, reducing its effectiveness.
of the edges associated with AND gate
Table 7: KL. in Completeness Validation of 1OI task, including Ns, Dn, and Ns+Dn.
Redges
ACDC_NS NS
ACDC_Ds Dn
ACDC_Nsb NsDn
EAP_Ns
EAP Dn
EAP EAP_NsDu NsDu
EdgeP_N NNs
EdgeP Dn
EdgeP PsDDn
100
0.62a0.1
0.6420.1
0.6420.1
0,5140.1
0.7140.1
0.7420.1
0.5640.1
0.6240.1
0.6410.1
200
0.6420.1
0.6920.1
0.71=0.1
0.5640.1
0.73+0.0
0.73+0.1
0.5840.1
0.6540.1
0.69x0.1 1
500
0.7120.1
0.84s0.1
0.87.0.1
0.6510.1
0.8110.1
0.8320.1
0.6740.1
0.8810.1
0,9420.1
1000
0.81
0.96:0.1
1.03=0.1
0.74+0.1
0.9640.1
1.02+0.1
1.0840.1
1.1140.1
1.13+0.1
2000
1.05a0.1
1.19+0.2
1.22=0.1
0.89+0.1
1.11
1.24+0.2
1.3140.2
1.400011
1.41#0.1
500D
1.34:0.2
1.4240.2
1.46=0.2
1.21+0.1
1.4240.2
1.48+0.2
1.6240.2
1.7340.1
1.73+0.1
Table 8: Accuracy in Completeness Validation of 1OI task, including Ns, Dn, and Ns+Dn.
Medges
ACDC_NS
ACDC_Dn
ACDC_NsDr NsDn
EAP_Ns
EAP_De Dn
EAP AAP_NsDn
EdgeP Nss
EdgeP Dn
EdgeP NsDn
100
0.7320.1
0.6840.0
0.63.0.1
0.74a0.1
0.53+0.0
0.5120.0
0.76400.1
0.6740.1
0.6640.0
200
0.6520.0
0.62+0.0
0.60=0.0
0.6810.0
0.4910.0
0.4620.0
0.59a0.0
0.5540.0
0.5610.0
500
0.53g0.0
0.51=0.0
0.51=0.0
0.6110.0
0.4120.0
0.38+0.0
0.55+0.0
0.43:0.0
0.43+0.0
1000
0.40=0.0
0.34:0.0
0.33=0.0
0.39+0.0
0.29+0.0
0.26+000
0.3240.0
0.2740.0
0.26+0.0
2000
0.3420.0
0.26=0.0
0.24=0.0
0.35+0.0
0.18+0.0
0. 14=0.0
0.24g0.0
0.18+0.0
0, 16+0..
5000
0.26#0.0
0.22+0.0
0.21=0.0
0.29+0.0
0.13+0.0
0.09=0.0
0.2140.0
0.1140.0
0.11
H Experiments of Faithfulness
In this section, investigate the faithfulness of circuits obtained using three and EdgeePrning--croon three tasks: IOI, GT, and SA. Specifically, we examine the changes in KL divergence and accuracy between the original eircuit (Ns.), the circuit with full OR and ADDER gates (Dn.) and the circuit with logically complete gates DN..+Dn.). For sparsity, we select edge counts of 100, 200, 500, 1000, 2000, and 5000.
EAP,
Figure illustrates that, under the same sparsity constraints, the circuits discovered using Dn. are significantly lower in both metrics compared to those discovered using Ns. and Ns.+Dn., which corroborates our assertion in Corollary [ Dn. is incapable of fully recovering the AND gate, and thus cannot achieve optimal faithfulness.
Additionally, in the EAP method, Ns clearly performs much worse than Ns+Dn, whereas in the ACDC and EdgePruning methods, the performance of Ns and Ns+Dn is quite similar. This aligns with our reasoning in Table where we note that only the linear estimation method completely fails to identify any OR edge, thus not satisfying the minimal requirement of faithfulness.
25

---

03
10:0
2000
300
1000
2000
360
2006
360
#03ges
#00ger
eodges
(a) ACDC of 1O1 task
(b) EAP of 101 task
(c) EdgePruning of I0I task
1.5
K5
Brdges
endges
(d) ACDC of GT lask
(e) EAP of GT task
(f) EdgePruning of GT task
Accooot
(g) ACDC of SA task
(h) EAP of SA task
(i) EdgePruning of SA task
Figure 9: Faithfulness of circuit from Ns., DN., and NS.+Dn Dn......
I
Graph Study
To investigate the relationship between the three logical gates and the functions of the language model, we extracted the circuits of AND, OR, and ADDER gates discovered through ACDC on the 1OI task. We then reviewed the circuit [16] to determine the function each component.
Interestingly, each receiver in the AND circuit is almost always influenced by edges from different functions, indicating that the AND operation can be understood combining different functions to jointly impact the subsequent layers. For example, in Figure aO)a). the Induction Head requires edges from both the Duplication Token Head and the Previous Token Head to function, which supports the mechanism behind the Induction skill [27 28 29). Similarly, the Name Mover Head requires support from both the S- S-hibiition Head and the Induction Head, which explains the functional mechanism of the AND operation.
In contrast, the OR circuit clearly shows that nearly every receiver node is influenced by edges from the same function, as shown in in Figure[[O{b) suggesting that these edges from the same function either backups or interchangeable. For instance, the S-Inhibition Head influenced by multiple Induction Heads, and the Backup Name Mover Head influenced by multiple S-Inhibition Heads.
Lastly, the ADDER circuit appears to focus more on the outputs of the MLP and often combines outputs from shallow-layer skills with those from leeper-layer skills, as shown in Figure (O(c). The Name Mover Head considers outputs from all functions between the Duplicate Token Head and the S-Inhibition Head, and the final output takes into account the combined results from all three Name Mover Heads.
Additionally, regarding the span of gates across layers, OR gates typically operate over shortest distances, usually occurring between two functions that are close in layer position. In contrast, the ADDER gates generally span the longest distances, typically combining shallow-layer functions with deeper-layer functions.
26

---

<111
-cel.7 7>
<al
Simpadd pont
Haad Si+
*p4. 11=
.eb Px
<a2.2>
<at 10>
<x2.4>
<m
<e5 So
<aa 10x
<md>
<ac S+
<85 B>
ca 10c
<moi
<mnZ>
Cal BC
Proiea leed
Neme
Inte Listee
Book of Viuer Head
(a) Circuit graph of AND gate
<a0.06
<mb>
<eb 10>
<bd
<mb>
<ml>>
Sap gD
<a6 9D
<010.0>
<a8 10
<all 3>
<eil.8+
<el1.1
pest
(b) Circuit graph of OR gate
emboo
cmd
(c) Circuit graph of ADDER gate
Figure 10: Circuit Graphs of AND, OR, and ADDER gates, respectively. We set the color of each component to be the same as that of the IOI circuit 16. allowing for easy reference to the function of each component.
27

---

200
2000
200
303
200
200
addges
imdges
aodges
(a) Edge contribution in IOT task (b) Edge contribution in GT task (c) Edge contribution in SA task
#ddges
4odges
eo0ges
(d) Gate contribution in IOI task
(e) Gate contribution in IOI task
(l) Gate contribution IOI task
Figure 11: The contribution of different logic gates the output."
J Output Contribution
In this section, we investigate the contribution of three types of logic gates to the output. Specifi- cally, we calculate the change in the KL divergence of the output caused by replacing these gates. Considering the collection of gates, we analyze their contributions from two perspectives: the gate effect and the edge effect. The gate effect refers to the impact on the output caused by replacing an entire logic gate, while the edge effect corresponds to equally distributing the gate effect across each edge within the gate. For example, for AND gate with two edges, if the activation of the receiver node contributes 0.8 to the output, the edge effect would 0.4. Figure TT illustraaee the gate effect and edge effect of these logic gates across different tasks and baselines. Clearly, the ADDER gates exhibit the largest contribution, demonstrating while the contributions of the AND and OR gates similar. Additionally, the average gate and edge effects in EdgePruning and EAP are significantly higher than those ACDC. This is because the differentiable mask and linear estimation methods optimize (rank) based on the edge effect, ensuring that the effect within the circuit is maximized, in contrast to greedy search methods.
role as the primary framework of the circuit,
K Proportion of AND, OR, and ADDER Gates
Figure 12 iillustrates the proportion of the three types of logical gates across different tasks for each method. Notably, in the ACDC baseline, the number of edges corresponding to each gate type is nearly equal. This is because ACDC employs greedy search strategy without ranking edges by their effect the output. In contrast, both EAP and EdgePruning yield significantly fewer OR edges. reflecting the fact that OR edges contribute the least to the output-a finding we detail in Section 5.2 and Appendix ! Furthermore, the results from EdgePruning indicate that the number of AND edges similarly low, comparable to OR edges. This arises from the fact that EdgePruning optimizes based on individual edge effects rather than gate-level effects. For instance, in gate comprising two AND edges, each edge contributes only half the total gate effect. As result, during optimization, the mask values for such edges may be suppressed, increasing the likelihood of pruning.
L Potential Contributions of Completeness: an Example of Model Unlearning
We have designed a toy task analogous knowledge unlearning to demonstrate its actual effec- tiveness. Specifically, given a harmful-response datasets (PKU-SafeRI.HF) R0,, we first obtain its circuit C, and then remove this circuit from the computation graph G, observing whether the model
28

---

1242
1698
17
18
204
6CS
62
240
2254
(a) ACDC in IOI task
(b) EAP in 10I task
(c) EdgePruning in IOI task
138
144
242
3527
300
315
2450
322
28
(d) ACDC in GT task
(e) EAP in GT task
(f) EdgePruning in GT task
20
216
124
200
J012
(g) ACDC in SA task
(h) EAP in SA task
(i) EdgePruning in SA task
Figure 12: Proportion of AND, OR, and ADDER edges in circuit from Ns.+Dn., The concentric rings from the innermost to the outermost represent circuits with 100, 500, 1000, and 5000 edges, respectively. The blue represents AND edges, red represents ADDER edges, and green represents OR edges.
29

---

can still respond to the dataset. The dataset provides harmful responses for certain questions, which are used to evaluate the efficacy preventing the model from generating these harmful responses.
In the Table 9 we present the performance of this toy task on the accuracy of g - C, which refers to the performance of the computational graph after the circuit has been removed (using the interchange ablation method), reflecting the completeness of the circuit. We test two circuit discovery methods: EAP and Edge-Pruning.
Table 9; A toy experiment on model unlearning task
Method
accuracy
accuracy of
EAP
92.74
29.17
Edge-P
92.74
31.44
Ours
92.74
13.21
is evident that, compared to existing circuit discovery methods, our method ensures that the computational graph loses almost all the necessary mechanisms for the task once the circuit is removed. Additionally, this toy task highlights the significance of studying circuit completeness,
which holds great potential in unlearning harmful information: complete circuit can help us pinpoint all neurons associated with harmful responses.
30


Reviews:
[{"review_id": "SKPv8ut6Ju", "reviewer": "Reviewer_mnpW", "summary": "When finding which subgraph (circuit) of the NN is responsible for a task, we want to have three properties: faithfulness (the circuit by itself does the task), minimality (the circuit is as small as possible) and completeness (the circuit contains all parts of the NN that are responsible by the task, even redundant ones).\n\nCircuit discovery algorithms until now focused mainly on faithfulness and minimality and the tradeoff between them. The circuits discovered by them often lack completeness. The \"automatic circuit discovery\" paper [ref 2 in paper, appendix M] also talked about a logical OR gate as something that its proposed method had trouble with, and methods since has not improved.\n\nThis paper argues that traditional circuit discovery algorithms miss OR gates because they use a noising (Ns) approach. Ns algorithms start with NN activations on 'clean' inputs, and replace them with 'corrupted' activations; which leads them to see that replacing one if the inputs is OK (so it has no effect). \n\nThe paper introduces denoising (Dn) as an alternative circuit discovery approach: modify any current algorithm to start with the corrupted activations, and replace parts of it with clean activations. The same way that Ns algorithms easily discover AND gates, and AND is the dual of OR (DeMorgan's law style, see lines 199-201), Dn algorithms easily discover OR gates.\n\nTo make an algorithm which discovers both kinds of gates (as well as linear ADDER gates), we can combine Dn and Ns approaches in the same loss.", "questions": "# Upgrading my score\nWhen the authors address all the weaknesses I wrote about, I will recommend this paper for acceptance.\n\n# Questions about experiments\nThis section contains some clarity problems that should be addressed\n\n## Section 4.1\n- In section 4.1, how do you choose the C_AND, C_OR and C_ADDER circuit parts? Using *which* Dn and Ns algorithm specifically? On how many random runs?\n- How do you choose the 1 and 2 edges to remove for Figure 3? Randomly, you average over all sets of 1 edges and sets of 2 edges, ... ?\n- I think the \"granularity alignment\" concept from Figure 2 and Lines 222-233 needs more explanation. Why is Figure 2 a good picture of what's really happening in the circuit? The misalignment scores from Appendix E, they're completely separate for OR and AND; from figure 2 I thought misalignment was a property of the ADDER intersection? Very confused here.\n\n## Completeness validation 1: removing the circuit\n\nThis corresponds to Section 4.3.1 (in page 7) and Figure 4\n\nFigure 4 is really hard to read, the dots are small and everything is the same color, so I don't know what to make of the results at all. In any case, the difference between circuit discovery methods doesn't seem that large? But it's consistent at least.\n\nFrom the text in lines 265-279, it seems that you're measuring completeness by removing the discovered circuit from the model and checking how much the KL divergence changes. Is that true?\n\nIf so, that doesn't match the definition of completeness from Wang et al. 2023: that's about whether removing a *subcircuit* K from both the model and the circuit, has the same effect on both.(as you well specify in lines 118-124). Why is this method a valid way to measure completeness?\n\n## completeness verification 2: average Hamming distance\nWhat is the Hamming distance on: which edges are present/absent? Is this the average of every pair of circuits from the 30 runs (900 pairs total), or from a few randomly selected pairs?\n\nIt would be much easier to read Table 3 if you would just compute the Hamming distance for C_Ns and for C_{ns + dn} and state both separately,  instead of subtracting them. Then we can compare which distance is greater.\n\n## Figure 6 + section 5.1\n\nHow are you supporting the claim that \"the AND gates typically receive edges from different functions\" vs \"the OR gates receive edges from the same function\"? What is a function here? Do you literally mean whether incoming edges are from MLPs (\"same function\") or attentions and MLPs (\"different function\")? That's a very strange thing to check, different MLPs and different attention heads will be computing different function, so I don't see why they're the same \n\n# Limitations that aren't actually limitations\nIn Line 336-338, you say that \"since there is no difference in faithfulness between the logically complete circuit and the existing circuit, it is difficult to directly demonstrate its 'superiority' over current work\". This seems false: you can just demonstrate superiority by demonstrating that the discovered circuit is more complete. (which the Hamming distance experiment kind of showed). Why did you say this?\n\n\n\n# Minor awkward wording\nL46: \"we introduce the concept of logic gates\" - no, you do not, it's at least a century old. You talk about logic gates in circuits.", "limitations": "The one limitation they acknowledge, in lines 335-340, that this is only theoretical research and cannot be shown empirically to be better, is straight up not a limitation.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths\n\nThis paper engages reasonably well with the existing literature. Its main idea, to introduce Denoising as an approach, is excellent: it makes it obvious everyone was making an assumption that restricted the design space. The resulting design plausibly addresses the largest remaining within-paradigm weakness of circuit discovery (OR gates).\n\nI really like the conceptual clarity of Table 1. In contrast with the attempted formal Definition 1 of the article, Table 1 very clearly defines what we expect of \"redundant + voting\" circuits (OR) or \"all outputs must work\" circuits (AND), or linear (ADDER) circuits.\n\nThe end result is a brilliant idea that, if I were writing a circuit discovery paper, I would definitely try out and give credit to.\n\n# Weaknesses\n\nUnfortunately, the paper suffers from two issues: superficial empirical validation, and conceptual problems.\n\n## Empirical problems.\n\nThere is not enough grounds for readers to believe that the presented method is actually better than the existing ones, despite the clearly motivated idea. A\n\n## Conceptual problems\n\n### Correctness of OR/AND/ADDER definitions\n\nDefinition 1 (L133-143) introduces OR, AND and ADDER gates with seemingly formal definitions, but these are very unclear. what is the input space to which the As and the Bs belong to? If it is booleans, what does the sum (+) operation mean? If they are numbers, what do OR (v) and AND (^) mean?\n\nWhat reason do we have to believe that NN circuits can be decomposed into these three gates? Neural networks do other operations as well, for example negation (if we stick to the boolean framing, which I also think is too restrictive).\n\nIt seems that the real definition of OR, AND and ADDER is whether they can be discovered by linear approximation methods or existing methods in Ns or Dn versions (L196-206 in Section 4). I think you should stick to that.\n\n### It's not true that you can just remove edges from OR and AND gates, or that OR gates \n\nIn the caption of figure 1: \"when optimizing for faithfulness and sparsity alone, it is possible to remove one edge from the OR gate\". Why? In the subset of inputs in which the node corresponding to the removed edge is activated, and the edge that remains is not, this changes the output of the circuit. So removing one edge *does* decrease faithfulness, which would make existing algorithms find the OR gates sometimes.\n\n### It's not true that all circuits can be decomposed in OR, AND and ADDER (as defined)\n\nLine 8-9: \"decompose the circuit into combinations of [OR, AND and ADDER]\" -- which circuit do you decompose in this way? You mean *any* circuit? How do we know that any circuit can be expressed with these three gates? (This claim is made again in L46 and L153-155).\n\nHow to fix?\n\nIf you change the definition to \"AND can be discovered by Ns, OR by Dn, and ADDER by both\" then you would just have to show that the OTHER gates (which can be discovered by neither Dn or Ns) don't exist. Then, every circuit is composed of these gates (note, I'm not sure that's true).\n\nYou could also argue that all circuits are OR and AND and NOT gates if they're made of booleans, but that seems like a huge stretch given that neural networks inputs and outputs are continuous.\n\n## Missing literature\n\nIn line 103, these two papers are missing for linear estimation: EAP-IG (https://arxiv.org/abs/2403.17806) and AtP* (https://arxiv.org/abs/2403.00745). Both of these are reasonably cited elsewhere, especially EAP-IG. They address some of the issues of EAP/AtP for circuit attribution.", "was_revised": true, "final_justification": "Given conceptual errors in the paper (presenting OR, AND and ADDER as fundamental whereas they come from the framework of Noising and Denoising that they just introduced; and lack of consideration in the argument to NONE gates that are detected by neither Noising nor Denoising) I'm keeping my score.", "rebuttal": "We sincerely thank you for your thorough review of our manuscript. However, due to the character limit imposed on this rebuttal, we are currently only able to provide responses with as much detail as possible, though some quantitative results may not be fully presented at this stage. In addition, some of our responses are necessarily too detailed and lengthy to be included in full here. We kindly ask you to refer to the responses provided to other reviewers, as guided in our navigation, for a more complete discussion. We hope for your understanding in this regard and look forward to the opportunity for subsequent discussions. Below, we address your comments one by one:\n\n### **Q1: There is not enough grounds for readers to believe that the presented method is actually better than the existing ones, despite the clearly motivated idea.** \n\nThank you for your question. While our method offers only a marginal improvement over existing approaches in terms of faithfulness, it significantly outperforms them in terms of completeness. Regarding the question of **\"how to demonstrate the practical value of completeness,\"** we have addressed this point **in our response to Reviewer mrxZ’s Q1** (The **fourth reviewer in this paper**, see **Key Question 2: How can we illustrate the potential contributions of completeness research to other areas of research?**). \n\nIn brief, we validate the core concept of our work—**circuit completeness**—through a downstream task in **model unlearning**. Specifically, we show that **completeness can offer indirect but meaningful support for model unlearning**, particularly in the context of removing harmful responses. This is a capability not afforded by existing methods that focus primarily on faithfulness.\n\n### **Q2: Correctness of OR/AND/ADDER definitions: Definition 1 (L133-143) introduces OR, AND and ADDER gates with seemingly formal definitions, but these are very unclear.**\n\nThank you for your question and suggestions. We recognize the need to further clarify **how a circuit gate transitions from the continuous activation values of neurons to discrete states such as 0, 1, or 2**. This issue involves numerous experimental results and nuanced explanations, and we kindly refer you to our **response to Reviewer ftP7’s Q1** (The **fifth reviewer in this paper**) for a more detailed discussion. \n\nBriefly, we interpret the state of an edge or node as follows: a state of **1 denotes active, retained, or exerts an effect**, while a state of **0 indicates inactive, ablated, or has no effect**. When minor variations in effect are ignored, certain subcircuit patterns exhibit **truth tables identical to those of AND, OR, or ADDER gates**. Thus, we adopt the terminology of AND, OR, and ADDER gates to describe these subcircuits.\n\n### **Q3:  It's not true that you can just remove edges from OR and AND gates, or that OR gates: In the caption of figure 1: \"when optimizing for faithfulness and sparsity alone, it is possible to remove one edge from the OR gate\". Why?** \n\nThank you for your question. Through **A2**, I believe we can clarify this misunderstanding. Ablating an OR edge （edge1=1 and edge2=0, or edge1=0 and edge2=1） does not result in a $\\Delta KL$ exceeding the threshold, so this edge would be classified as \"no contribution\" and thus ablated. This is also why Nosing, with its focus on faithfulness, cannot guarantee circuit completeness.\n\n### **Q4: It's not true that all circuits can be decomposed in OR, AND and ADDER (as defined)**  \n\nThank you for your question. We have addressed this issue in detail in our **response to Reviewer khCH’s Q1** (The **second reviewer in this paper**). In brief, the three gates are **not high-level constructs based on intuition**; rather, they form **a complete set that spans the intersection of Ns and Dn**, and other potential gates fall outside the scope of the Ns and Dn framework. Moreover, we will **include the potential gates in the limitation sections in the revised version.** \n\n### **Q5: In line 103, these two papers are missing for linear estimation: EAP-IG and AtP. Both of these are reasonably cited elsewhere, especially EAP-IG. They address some of the issues of EAP/AtP for circuit attribution.**\n\nThank you for your suggestions and we will add these to preliminaries in revised version! \n\n### **Q6: In section 4.1, how do you choose the C_AND, C_OR and C_ADDER circuit parts? Using which Dn and Ns algorithm specifically? On how many random runs?**  \n\nThank you for your question. The notion of intersection in Section 4.1 refers to a **general theoretical framework** we propose, which is compatible with **any** specific implementation of either Ns or Dn algorithms. The detailed procedural steps for these implementations are provided in Appendix D.\n\n### **Q7: How do you choose the 1 and 2 edges to remove for Figure 3? Randomly, you average over all sets of 1 edges and sets of 2 edges, ... ?** \n\nThank you for your question. First, we filtered out the receiver nodes that contain more than 1 edge. For these nodes, we randomly ablated 1 or 2 edges and recorded the results. This process was performed 30 times on each node (we detailed these in line202-209). The final results presented in Figure 3 (box plot) correspond to the statistical values of all the experiments involving 1 edge and 2 edge ablations.\n\n### **Q8: I think the \"granularity alignment\" concept from Figure 2 and Lines 222-233 needs more explanation. Why is Figure 2 a good picture of what's really happening in the circuit? The misalignment scores from Appendix E, they're completely separate for OR and AND; from figure 2 I thought misalignment was a property of the ADDER intersection? Very confused here.**\n\nThank you for your question. We have addressed this issue in detail in our **response to Reviewer xbit’s Q1** (The **third reviewer in this paper**). In brief, by analyzing the trade-off between the misalignment scores of AND and OR gates, we observed that the ratio of AND to OR gates approaches 1:1 when the sum of their misalignment scores is minimized. This empirical observation underlies the conclusion presented in our paper. We will **include these experimental results in the revised version**.\n\n### **Q9: Completeness validation 1: removing the circuit**  \n\nThank you for your question. The differences between ACDC and Edge-Pruning are minimal, except for EAP. This is because EAP is the only algorithm that cannot discover some OR gates within Ns (see Table 1). \n\nAdditionally, as mentioned in lines 118-128, the metrics proposed by Wang et al. (2023)[1] often lead to unreliable approximations due to insufficient sampling, a conclusion that has been confirmed by numerous existing studies[2][3]. Therefore, we adopted the completeness metric proposed in paper [2]. \n\nMoreover, in our **response to Reviewer mrxZ’s Q1**—**Key Question 1: How can we demonstrate that the new evaluation metric of completeness performs better than the previous evaluation metric?** (The **fourth reviewer in this paper**)—we present experimental evidence showing that the completeness metric proposed by Wang et al. suffers from **high variance** due to **insufficient sampling**, leading to **unstable results**. In contrast, our newly proposed completeness metric **significantly reduces the variance**, thereby yielding more reliable and consistent evaluations.\n\n**reference:**\n\n*[1]. Interpretability in the wild: a circuit for indirect object identification in gpt-2 small, ICLR 2023*\n\n*[2]. Functional faithfulness in the wild: Circuit discovery with differentiable computation graph pruning arxiv 2024*\n\n*[3]. Sparse interventions in language models with differentiable masking, ACL 2022*\n\n\n### **Q10: completeness verification 2: average Hamming distance**  \n\nThank you for your question. The main purpose of this experiment is to verify the circuit overlap under **multiple random circuit discovery experiments**. Because a circuit algorithm with completeness is capable of discovering all circuit paths, so the circuits obtained in multiple random seeds should remain highly consistent. In contrast, a circuit lacking completeness is more likely to find **different branches across multiple random seeds**, leading to inconsistency. Therefore, our Hamming distance measures the distance between **any two circuits** under random seed conditions.  In revised versions, we will separate Table 3 into two subtables. Due to page constraints, we can present the separated results in the upcoming discussion.\n\n### **Q11: How are you supporting the claim that \"the AND gates typically receive edges from different functions\" vs \"the OR gates receive edges from the same function\"? What is a function here? Do you literally mean whether incoming edges are from MLPs (\"same function\") or attentions and MLPs (\"different function\")? That's a very strange thing to check, different MLPs and different attention heads will be computing different function, so I don't see why they're the same**  \n\nThank you for your question. In lines 302-303, we explained that \"*each color represents one function in the IOI circuit.*\" Referring to Figure 10(a), these functions correspond to components such as the Duplicate Token Head, Induction Head, S-Inhibition Head, and others in the IOI model.\n\n### **Q12: Limitations that aren't actually limitations**  \n\nThank you for your question. Our intention is similar to your **Q1**. We believe that the key metric for circuits remains faithfulness, and our method does not show a significant improvement in faithfulness (on the contrary, it shows a noticeable improvement in completeness). Therefore, compared to existing work, it is difficult to demonstrate **\"superiority\" in terms of faithfulness**. However, as discussed in **Q1**, completeness indeed holds potential for some valuable application scenarios.\n\n### **Q13: Minor awkward wording** \n\nThank you for your suggestion, we will update “introduce” to “borrow”."}, {"review_id": "YvFbRg6MRf", "reviewer": "Reviewer_khCH", "summary": "This paper proposes a circuit discovery method using AND, OR, and ADDER gates. Categorizing existing intervention methods for circuit discovery as noising-based (Ns) and denoising-based (Dn), the authors argue that Ns recovers AND and ADDER gates while Dn recovers OR and ADDER gates. Furthermore, for optimal faithfulness, the circuit needs only one edge from each OR gate, while for optimal completeness it needs only one edge from each AND gate. The authors then propose to combine noising- and denoising-based interventions to discover all three types of logic gates. The proposed framework is evaluated through experiments on GPT2-small considering three tasks (indirect object inference, greater-than, and syntactic agreement). In particular, they show that the proposed Ns+Dn achieves higher completeness (measured by KL divergence and accuracy) than Ns only.", "questions": "1. Can there exist gates other than AND, OR, and ADDER, and would that affect Corollaries 1 and 2? I would also suggest adding a short proof sketch for them in the main text even though the full proofs are in the appendix.\n\n2. Regarding how optimizing for faithfulness allows removing an edge from OR gates, while only one edge being present will activate the OR gate, it doesn’t necessarily mean that each input activates all edges into the OR gate. In the extreme case, if the inputs that activate $A_1$ are disjoint from those that activate $A_2$, then removing either from gate $B = A_1 \\vee A_2$ will hurt faithfulness. Could the authors clarify why removing an edge in this case is still ok?\n\n3. When running Ns and Dn in parallel to identify the three types of gates, are there any assumptions such as them having to use the same strategy (greedy, linear estimation, ..)? Does misalignment vary depending on which method was used?\n\n4. In Section 4.3.2, the comparison should also include Dn methods especially because they aim to optimize for completeness.\n\nOther questions/comments:\n- Is the term “logically complete circuits” used with a precise meaning? I think this might not be the best name, potentially confused with completeness.\n- I don’t quite follow how the paragraph starting in line 171 is implied by Corollary 2.\n- Line 241: “Expanding the space of intervention combinations renders circuit discovery an NP problem”. Is this referring to it being an NP-hard problem? There should be a proof for the statement.\n- The marks and legends in Figure 4 were too small and very hard to read.\n- Figure 5: is there a statistically significant difference between Ns+Dn and Ns? I would hope to see error bars.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The proposed approach to circuit discovery using logical gates is novel and interesting. Circuits with multiple, clearly-defined types of gates can lead to richer interpretations of language models.\n\nThe proposed method for discovering these nodes, by combining noising- and denoising-based strategies, is fairly straightforward and can be adopted by tweaking existing Ns methods. Thus, there are immediately a few variants of Ns+Ds for logical circuit discovery based on which baseline was chosen. This adds to usability and potential impact.\n\nMy main concern of the paper is that some definitions or results are described not quite rigorously, but rather using high-level arguments using intuition. This made it difficult to check technical correctness and significance: e.g., proofs for Corollary 1 and 2 and how the Ns+Dn objective in Eq 3 can be optimized using different baseline strategies. Also, faithfulness and completeness are defined in Section 2.2 such that there are multiple ways to quantify them, and I wasn’t sure if the proof for Corollary 2 still applies if faithfulness is measured by accuracy for example.\n\nThe authors compare their method mainly to Ns methods, with the reasoning that most existing baselines are noising-based. However, Table 1 shows Dn methods as well (although I am confused that the methods for Ns and Dn are identical), and it would be appropriate to compare against them wrt completeness.", "was_revised": true, "final_justification": "The authors have addressed many clarity issues and provided additional experiments to strengthen the evaluation. While I think the planned revisions will significantly improve the paper, the rebuttal also clarified that the definitions of gate types are quite specific to the noising- and denoising-based interventions introduced by this paper. This somewhat limits the completeness and significance of the proposed circuits, hence my keeping the score at 4.", "rebuttal": "We sincerely appreciate your review and recognition of our work. Below, we provide detailed responses to each of the issues you have raised. Due to character limitations, some general concerns that were also noted by other reviewers may not be fully explained here. For a more comprehensive explanation of those points, we kindly refer you to the discussion pages associated with the other reviewers. We hope for your understanding in this regard.\n\n### **Q1: Can there exist gates other than AND, OR, and ADDER, and would that affect Corollaries 1 and 2? I would also suggest adding a short proof sketch for them in the main text even though the full proofs are in the appendix.** \n\nThank you for your question. As discussed in Section A2, all the gates under consideration are derived from the intersection between Ns and Dn. The three gates are **not high-level arguments derived from intuition**; rather, they **constitute a complete set that spans the intersection of Ns and Dn**. The union of these three gates encompasses all the nodes and edges present in both Ns and Dn , and therefore, we may reasonably assume that they are complete. \n\nMoreover, we must acknowledge that there **may be gates, such as the XOR gate, that the Ns and Dn frameworks cannot discover**. We will **include a discussion** on potentially undiscovered gates in the **limitations section** in the **revised version**; however, these gates would certainly require a circuit framework beyond Ns and Dn, which falls **outside the scope of the current research**. \n\nWe will also incorporate **these explanations** and **a short proof sketch** into the main text in the **revised version** to support the discovery of the three gates.\n\n\n\n### **Q2: Regarding how optimizing for faithfulness allows removing an edge from OR gates, while only one edge being present will activate the OR gate, it doesn’t necessarily mean that each input activates all edges into the OR gate. In the extreme case, if the inputs that activate A1 are disjoint from those that activate A2, then removing either from gate B=A1 or A2 will hurt faithfulness. Could the authors clarify why removing an edge in this case is still ok?** \n\nThank you for your question. In the extreme case you mentioned, when $A1$ is removed, $A2$ will **still provide the same effect** for $B$, even though the input to $A2$ differs from that of $A1$. Additionally, both **Appendix M of paper [1]** and **Section 4.1 of paper [2]** indicate that removing an edge from an OR gate does **not affect faithfulness**. These two papers are foundational works in circuit discovery, and we believe they support the validity of our inference. Furthermore, you can refer to **Appendices A and B** for a detailed derivation of the OR gate. \n\nTo further validate these conclusions, we removed one edge from each of the three gates obtained using the EAP algorithm on IOI, and observed the changes in faithfulness and completeness. The metrics for faithfulness and completeness were defined as in Section 2.2. The table below shows the average results on 30 randomly selected nodes: \n\n| gate                | faithfulness  |completeness|\n| ----------------    | ------------ |----------   |\n| AND                 |      0.43    |   0.38      |\n| AND removing 1 edge |      0.03     |   0.36     |\n| OR                  |      0.29    |   0.44      |\n| OR removing 1 edge |      0.28     |   0.19     |\n| ADDER                |      0.55    |   0.49      |\n| ADDER removing 1 edge |      0.23     |   0.24     |\n\nThis table also demonstrates that removing one edge from the AND gate has a negligible impact on completeness, but it significantly reduces faithfulness. Similarly, removing one edge from the OR gate has almost no effect on faithfulness, but it severely reduces completeness. **More detailed results** about removing edges can be shown in **Q1 for Reviewer ftP7** (the last reviewer in this paper). \n\n**reference:**\n\n*[1]. Towards Automated Circuit Discovery for Mechanistic Interpretability, NeurIPS 2023*\n\n*[2]. Interpretability in the wild: a circuit for indirect object identification in gpt-2 small, ICLR 2023*\n\n\n### **Q3: When running Ns and Dn in parallel to identify the three types of gates, are there any assumptions such as them having to use the same strategy (greedy, linear estimation, ..)? Does misalignment vary depending on which method was used?** \n\nThank you for your question. We recommend using the **same strategy** for both Ns and Dn, as different strategies may not lead to the discovery of the corresponding ADDER gate. For instance, greedy search selects based on the order of searching, whereas EAP selects based on score ranking. Consequently, different strategies can also result in variations in misalignment.\n\n### **Q4:  In Section 4.3.1, the comparison should also include Dn methods especially because they aim to optimize for completeness**\n\nThank you for your suggestion! We will **include the experimental results for Dn in revised versions**. Due to character limitations, we could present the specific performance for Dn in the subsequent discussion. \n\nIn brief, our method generally **outperforms** the approach based on Dn. Although the Dn-based method is theoretically capable of identifying all OR gates, it **suffers from certain shortcomings in practice**. For instance, as shown in Table 1, EAP fails to identify one of the edges associated with an AND gate under the Dn framework. Additionally, the greedy strategy may miss some OR gates located beneath branches of AND gates due to its dependence on the search order. The differentiable mask approach, on the other hand, suffers from the drawback that, in gates involving multiple edges, the mask values assigned to each edge tend to be lower, reducing its effectiveness.\n\n### **Q5:  Is the term “logically complete circuits” used with a precise meaning? I think this might not be the best name, potentially confused with completeness.** \n\nThank you for your suggestion. We are considering using the term \"logically sound circuit\" instead of \"logically complete circuit.\" We would appreciate if the reviewer has a better suggestion. \n\n### **Q6: I don’t quite follow how the paragraph starting in line 171 is implied by Corollary 2.** \n\nThank you for your question. In the proof presented in **Appendix B** and the **table in A2**, we derived the following two conclusions:\n\n- As long as one edge of the OR gate is activated, the faithfulness of the circuit will not be changed.\n- As long as one edge of the AND gate is activated, the completeness of the circuit will not be changed.\n\nTherefore, we further conclude in the paper that \"*faithfulness refers to the sum of all gate effects in the circuit, which should be as large as possible.*\" In other words, **faithfulness** requires that **all gates in the circuit be activated**: for AND and ADDER gates, this means all incoming edges must be active; for OR gates, at least one edge must be active. Similarly, **completeness** requires that none of the gates remain active in $G \\setminus C$. Therefore, in the circuit $C$, all edges of OR and ADDER gates must be activated, while for AND gates, activation of at least one edge is sufficient.\n\n\n### **Q7: Line 241: “Expanding the space of intervention combinations renders circuit discovery an NP problem”. Is this referring to it being an NP-hard problem? There should be a proof for the statement.** \n\nThank you for your suggestion. Due to the differences in circuit algorithms, this issue cannot be fully proven mathematically. However, we will provide some additional explanation: we treat **each ablation** as $O(1)$. Assuming the language model contains $N$ nodes, if we need to use all possible intervention combinations to obtain a complete circuit, the time complexity would be $O(2^N)$, which far exceeds polynomial time. However, **different strategies can optimize the solution verification process to varying degrees**. For example, EAP only requires $O(N)$ time to **verify** whether the circuit is complete, while Edge-pruning involves **gradient descent**, making its time complexity **difficult to estimate**. Additionally, greedy search can only perform a **greedy verification** in $O(N)$ time rather than a thorough verification. Therefore, we ultimately classify this problem as **NP problem**.\n\n**In the revised version, we will incorporate these analyses into the main text to provide a simple explanation for the \"NP problem.\"**\n\n### **Q8: The marks and legends in Figure 4 were too small and very hard to read.** \n\nThank you for your suggestion and we will **replace these figures with tables in revised version**. Due to character limitations, we could present the specific performance for Dn in the subsequent discussion.\n\n### **Q9: Figure 5: is there a statistically significant difference between Ns+Dn and Ns? I would hope to see error bars.**\n\nThank you for your suggestion. We will add their standard deviations and now we show the std. of KL below: \n| strategies| 100     | 200     | 500     | 1000    | 2000 | 5000 |\n|--------   |-------- |-------- |-------- |-------- |----  |----  |\n| Ns        |2.72±0.12|2.51±0.09|0.61±0.06|0.51±0.03|0.44±0|0.41±0|\n| Dn        |2.96±0.16|2.91±0.15|0.95±0.07|0.62±0.06|0.53±0.01|0.49±0|\n| Ns+Dn     |2.57±0.11|2.26±0.10|0.55±0.04|0.42±0.01|0.42±0|0.40±0|"}, {"review_id": "IZQkCAKWqL", "reviewer": "Reviewer_xbit", "summary": "1. This paper proposes a new framework for interpreting circuits in language models by decomposing them into three types of logic gates: AND, OR, and ADDER. The author argues that most existing circuit discovery methods fail to identify complete circuits due to the incomplete recovery of OR gates.\n2. This paper provides a detailed analysis showing the limitations of current noising-based and denoising-based strategies, and proposes a combined approach to recover logically complete circuits. \n3. This paper provides extensive experimental validation using three different circuit discovery methods (ACDC, EAP, EdgePruning) on three tasks (IOI, GT, SA). The results show that the proposed Ns+Dn framework discovers circuits that are more complete and less random than circuits found using Ns alone, while maintaining comparable faithfulness.\n4. This paper explores the functional roles these different gates play, suggesting AND gates integrate diverse functions while OR gates provide redundant pathways.", "questions": "Please see \"Weaknesses\".", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The idea of decomposing a circuit into AND, OR, and ADDER gates to understand circuit functionality is a strong and meaningful contribution. It provides an intuitive and straightforward way to understand the relationships between components in a neural network.\n2. The paper analyzes how the two primary intervention strategies (noising-based and denoising-based) are naturally suited to recovering different types of logic gates. The proposed framework (combine *Ns* and *Dn*) is modular and compatible with existing methods, making it practical for adoption.\n3. Extensive experiments are conducted to support the paper's claims. The framework is tested across three different classes of circuit discovery algorithms on three distinct benchmark tasks.\n4. The paper is clear and easy to follow.\n\nWeaknesses:\n1. One of the key parts of the method for separating the logic gates is based on the assumption that \"*optimal alignment occurs when Ns and Dn contain an equal number of edges*\" (L-231). This is a strong assumption that is not deeply justified. Is it possible that the true underlying circuit has an inherent imbalance between necessary (AND-like) and redundant (OR-like) pathways? How will the author handle this case? More discussions on this are suggested.\n2. The \"logically complete\" circuits discovered by the proposed Ns+Dn method are not significantly more faithful than those found by standard Ns methods alone (as acknowledged by the authors in Sec 6.1). Given that faithfulness is often a key goal, this may limit the method’s practical appeal for users who prioritize that metric.\n3. Some of the figures (e.g., Fig. 4 and 9) are difficult to understand.\n(1) For example, the multi-line graphs in these 2 figures show two metrics across multiple methods on dual y-axes. It is visually dense and makes it challenging for reviewers to compare results effectively. \n(2) Also, it seems to me (from Fig. 5) that KL divergence and task accuracy of Ns+Dn are very close to Ns-only. This raises my concern: why should we adopt this more complex method if existing approaches already perform nearly identically on core metrics? Is it possible to show the improvement through specific quantitative numbers rather than a line chart?\n4. The paper refers to the \"*gate effect*\" as the contribution of an entire gate, which is then used to calculate the \"*edge effect*\" (e.g., Sec. H). However, the method for isolating and calculating the total effect of a multi-edge gate (e.g., for AND and OR gates where inputs are not independent) is not fully detailed. It is unclear to me how these contributions were measured, and more explanations on this are suggested.\n5. All experiments are done on GPT2-small. There is no discussion showing whether the proposed Ns+Dn approach scales to other models (e.g., GPT-3, Llama).", "was_revised": true, "final_justification": "I raised my score from 3 to 4 after the rebuttal. The authors addressed key concerns, including the AND/OR gate balance, practical value of completeness via a toy task, and clarified gate effects. Their plan to improve figures and add quantitative results is appreciated.\n\nThe main limitation (lack of evaluation beyond GPT2-small) remains, but is reasonable given current field constraints. Overall, the response strengthened the paper’s clarity and contribution, and my final rating is \"4: Borderline accept\".", "rebuttal": "Thank you for your review! Your questions and suggestions have helped us improve the level of detail in the paper. Below, we provide point-by-point responses to each of your comments.\n\n### **Q1: One of the key parts of the method for separating the logic gates is based on the assumption that \"optimal alignment occurs when Ns and Dn contain an equal number of edges\" (L-231). This is a strong assumption that is not deeply justified. Is it possible that the true underlying circuit has an inherent imbalance between necessary (AND-like) and redundant (OR-like) pathways? How will the author handle this case? More discussions on this are suggested.** \n\nThank you for your suggestion. We discuss this issue in detail in Appendix E. As shown in Figure 8, when the OR set significantly exceeds the AND set, a large number of misclassified ADDER gates appear only within the OR set, leading to a much higher misalignment score for OR compared to AND. Similarly, when the size of the AND set significantly exceeds that of the OR set, a large number of ADDERs may be incorrectly classified as AND, thereby increasing the misalignment score of the AND set. As you mentioned, the misalignment score is more of a **\"property,\"** reflecting the optimal scale at which OR and AND sets should intersect. \n\nWe determine the **optimal ratio** of AND to OR gates by **minimizing** the $(\\text{misalignment scores of AND} +\\text{misalignment scores of OR})$. The optimal results obtained with different methods and datasets are approximately as follows:\n\n**Table: The optimal ratio of AND and OR sets**\n\n| strategies| IOI     | GT      | SA    |\n|--------   |-------- |-------- |-------|\n| ACDC      |1.12: 1  |1.05: 1  |1.07: 1|\n| EAP       |1.09: 1  |1.03:1   |1.05: 1|\n| Edge-Pruning|1.11: 1|1.07: 1  |1.06: 1|\n\nThe results show that the proportion of AND is always **slightly higher** than that of OR, but it can be **approximated as 1:1**. This suggests that, in general, there is **no significant imbalance between the AND and OR sets**. This forms the basis for our conclusion that \"*optimal alignment occurs when Ns and Dn contain an equal number of edges.*\" Moreover, we will **add these discussion into Appendix E in the future version**. \n\n### **Q2: The \"logically complete\" circuits discovered by the proposed Ns+Dn method are not significantly more faithful than those found by standard Ns methods alone (as acknowledged by the authors in Sec 6.1). Given that faithfulness is often a key goal, this may limit the method’s practical appeal for users who prioritize that metric.** \n\nThank you for your comment. We fully agree with your perspective that faithfulness warrants significantly more attention than completeness. Nevertheless, we aim to explore potential applications from the perspective of completeness, in order to highlight its practical significance. \n\nWe have designed a **toy task** analogous to **knowledge unlearning** to demonstrate the **actual effectiveness of completeness**. Specifically, given a harmful-response datasets (PKU-SafeRLHF), we first obtain its circuit $\\mathcal{C}$, and then remove this circuit from the computation graph $\\mathcal{G}$, observing whether the model can still respond to the dataset. The dataset provides harmful responses for certain questions, which are used to evaluate the efficacy of preventing the model from generating these harmful responses.\n\nIn the table below, we present the performance of this toy task on the accuracy of $\\mathcal{G-C}$, which refers to the performance of the computational graph after the circuit has been removed (using the interchange ablation method), reflecting the completeness of the circuit. We test two circuit discovery methods: EAP and Edge-Pruning.\n\n| Method | accuracy |accuracy of $\\mathcal{G-C}$|\n| ------ | -------- |-------------------------- |\n| EAP   |  92.74   | 29.17                   |\n| Edge-Pruning|  92.74    | 31.44                   |\n| Ours  |  92.74    | **13.21**                   |\n\n**Experimental Results:**\n\nIt is evident that, compared to existing circuit discovery methods, our method ensures that the computational graph loses almost all the necessary mechanisms for the task once the circuit is removed. Additionally, this toy task highlights the significance of studying circuit completeness, which holds great potential in unlearning harmful information: **a complete circuit can help us pinpoint all neurons associated with harmful responses**. \n\n### **Q3: Some of the figures (e.g., Fig. 4 and 9) are difficult to understand. (1) For example, the multi-line graphs in these 2 figures show two metrics across multiple methods on dual y-axes. It is visually dense and makes it challenging for reviewers to compare results effectively. (2) Also, it seems to me (from Fig. 5) that KL divergence and task accuracy of Ns+Dn are very close to Ns-only. This raises my concern: why should we adopt this more complex method if existing approaches already perform nearly identically on core metrics? Is it possible to show the improvement through specific quantitative numbers rather than a line chart?**\n\nThank you for your suggestion. To avoid making the figures too complex, we will **include a table with specific quantitative numbers in revised versions**. Due to the character limit, we are unable to provide detailed quantitative results in this response. However, we would be happy to share a table of the specific results during the subsequent discussion phase, should you be interested. Additionally, we provide a detailed explanation in **Q2** regarding the **significance of studying completeness**. In short, completeness offers potentially valuable insights for downstream tasks such as model unlearning. \n\n### **Q4: The paper refers to the \"gate effect\" as the contribution of an entire gate, which is then used to calculate the \"edge effect\" (e.g., Sec. H). However, the method for isolating and calculating the total effect of a multi-edge gate (e.g., for AND and OR gates where inputs are not independent) is not fully detailed. It is unclear to me how these contributions were measured, and more explanations on this are suggested.**\n\nThank you for your question. We will provide a specific explanation of the different effects:\n\n- **Edge effect**: The $\\Delta KL$ resulting from ablating this edge.\n- **Gate effect**: The $\\Delta KL$ resulting from ablating all the edges contained within this gate.\n- **Total effect of a multi-edge gate**: This is the same as the gate effect.\n\nTherefore, regardless of whether the input are independent, the **gate effect** of a given gate can be obtained **by ablating its receiver node**. In **Appendix H**, we further ensure that all gates used for effect computation have receiver nodes that are **not part of any branch of an OR gate**. This is because if a gate resides on a branch of a higher-level OR gate, then any ablation of that gate tends to have negligible impact on the final output. Additionally, this phenomenon is theoretically discussed in **Footnote 2 on Page 4**. \n\nFinally, in the **revised version**, we will **include these experimental details** on the local gate effect in Appendix H.\n\n### **Q5: All experiments are done on GPT2-small. There is no discussion showing whether the proposed Ns+Dn approach scales to other models (e.g., GPT-3, Llama).** \n\nThank you for your suggestion. However, current mainstream circuit discovery algorithms have been comprehensively studied only on GPT2-small. For instance, methods such as **ACDC**, **EAP**, and **Edge-Pruning** have **all** been developed and evaluated specifically on **GPT2-small**. Scaling these investigations to models with larger parameter sizes is itself a central and ongoing challenge in the field of circuits. We would be grateful for your understanding of this limitation."}, {"review_id": "4lWdLYnAqC", "reviewer": "Reviewer_mrxZ", "summary": "This paper presents an interesting abstraction of the behaviour that nodes and edges exhibit in circuits. In particular, it hypothesises that nodes are analogous to AND, OR, or ADDER logic gates in how they handle the input from incoming edges. The authors propose a framework that classifies nodes into one of the three gate classes based on their behaviour with respect to the intervention introduced its incoming edges. Using these identified behaviour, they were able to propose a more refined version of the completeness evaluation that could benefit the circuit discovery community.", "questions": "- Please refer to the Weaknesses section. I’d be interested to hear your thoughts on the issue of completeness.\n- Are there any previous convention to abbreviate noising-based intervention as Ns and denoising-based intervention as Dn?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### **Strength**\n\n- This paper is very clearly written and easy to follow.\n- It proposes a refinement to the completeness aspect of the evaluation of circuit discovery methods, an essential component that is often poorly assessed.\n- The paper thoroughly enumerates its limitations, which is important for any interpretability research right now, as we are still in a very early stage of cracking the black box open. The paper does not overclaim anything and carefully states its findings. This should be much appreciated.\n\n### **Weakness**\n- I would like the paper to elaborate further on the limitations of existing completeness measures. Section 2.2 briefly mentions some critiques of sampling-based completeness scores, but the discussion is limited. It is more or less accepted that previous approaches to completeness evaluation are problematic, but, to the best of my knowledge, there has been no empirical or critical examination of this. I believe this work could have taken that step. It would also motivate their method strongly.\n\n### **Smaller points:**\n- The choice to abbreviate noising-based intervention as Ns and denoising-based intervention as Dn is somewhat unconventional.", "was_revised": true, "final_justification": "Thanks for the response. I am satisfied with the elaboration. Please incorporate them in the updated draft. I will maintain my positive assessment.", "rebuttal": "Thank you for your suggestion and recognition! We also agree with your perspective that the discussion of completeness is both cutting-edge and interesting. Below, we will engage in a discussion with you on the topic of completeness, in relation to existing work in this area. \n\n**### Q1: I would like the paper to elaborate further on the limitations of existing completeness measures. Section 2.2 briefly mentions some critiques of sampling-based completeness scores, but the discussion is limited. It is more or less accepted that previous approaches to completeness evaluation are problematic, but, to the best of my knowledge, there has been no empirical or critical examination of this. I believe this work could have taken that step. It would also motivate their method strongly.** \n\nRegarding the discussion of completeness, we conducted two experiments to address two key questions:\n\n**Key Question 1**: How can we demonstrate that the new evaluation metric $D(G \\setminus C \\,|G) $ performs better than the previous evaluation metric $D(C \\setminus K \\,\\| G \\setminus K)$?\n\n**Key Question 2**: How can we illustrate the potential contributions of completeness research to other areas of research? \n\n**Answer to Key Question1**\n\nWe agree with your point *\"there has been no empirical or critical examination of this\"*. However, we must emphasize that the lack of empirical comparison arises from a fundamental **difference in the definitions** used by the two approaches. The earlier completeness evaluation method (proposed by Wang et al. [1]) in fact measures **incompleteness**, defined as$D(C \\setminus K \\,\\| G \\setminus K)$, where a lower score indicates better performance. In contrast, the current method [2] measures **completeness**, defined as $D(G \\setminus C \\,|G) $, where a higher score is preferable.\n\nImportantly, these two metrics are **not directly interchangeable** — that is,$1 - D(C \\setminus K \\,\\| G \\setminus K) \\neq D(G \\setminus C \\,|G)$. \n\nNevertheless, a comparison can still be made in terms of the **standard deviation**. It has been theoretically demonstrated that the earlier completeness method suffers from **high variance due to insufficient sampling**, leading to **instability** in the final results. To illustrate this, we provide a simple comparison on standard deviation between the previous and current evaluation methods, as shown in the table below:\n\n| Method | 5 sampled K|10 sampled K |20 sampled K |30 sampled K|New metric|\n| ------ | --------   |--------      |--------     |--------    |----|\n| ACDC  |  1.1±1.6    | 1.8±1.2      |1.4±1.1      |1.2±0.6     |1.3±0.13|\n| EAP   |  1.7±1.5    | 1.3±1.6      |1.6±1.2      |1.3±0.7     |1.4±0.11|\n| Edge-Pruning|  1.5±1.8    | 1.4±1.9      |1.4±1.6      |1.6±0.6     |1.2±0.08|\n| Ours  |  0.4±0.3    | 0.6±0.4      |0.3±0.3      |0.3±0.2     |1.8±0.03|\n\nWe conducted five different runs of circuit discovery using random seeds, with the random subset $K$ chosen from subcircuits of sizes ranging from 2 to 5 nodes. For the previous evaluation metric, we performed 5, 10, 20, and 30 sampling iterations.\n\nThe experimental results clearly support two conclusions:\n\n1. For algorithms that inherently lack completeness (such as ACDC, EAP, and Edge-Pruning), as well as for our own method, which ensures completeness, the previous evaluation metric exhibits **large standard deviations** across all trials. This indicates that the sampling process for the previous metric is insufficient, rendering the results **highly unreliable**.\n   \n2. The new evaluation metric (see \"New metric\" column) **significantly reduces variance** for all types of circuits, as it does not suffer from sampling issues. The variance observed in the results arises from minor differences in the circuits generated by different random seeds.\n\n**reference**\n\n*[1]. Wang, Kevin Ro, et al. \"Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 Small.\" ICLR 2023.*\n\n*[2]. Yu, Lei, et al. \"Functional faithfulness in the wild: Circuit discovery with differentiable computation graph pruning.\" arXiv 2024*\n\n**Answer to Key Question2**\n\nWe have designed a **toy task** analogous to **knowledge unlearning** to demonstrate the actual effectiveness of completeness. Specifically, given a harmful-response datasets (PKU-SafeRLHF), we first obtain its circuit $\\mathcal{C}$, and then remove this circuit from the computation graph $\\mathcal{G}$, observing whether the model can still respond to the dataset. The dataset provides harmful responses for certain questions, which are used to evaluate the efficacy of preventing the model from generating these harmful responses.\n\nIn the table below, we present the performance of this toy task on the accuracy of $\\mathcal{G-C}$, which refers to the performance of the computational graph after the circuit has been removed (using the interchange ablation method), reflecting the completeness of the circuit. We test two circuit discovery methods: EAP and Edge-Pruning.\n\n| Method | accuracy |accuracy of $\\mathcal{G-C}$|\n| ------ | -------- |-------------------------- |\n| EAP   |  92.74   | 29.17                   |\n| Edge-Pruning|  92.74    | 31.44                   |\n| Ours  |  92.74    | 13.21                   |\n\n**Experimental Results**:\nIt is evident that, compared to existing circuit discovery methods, our method ensures that the computational graph loses almost all the necessary mechanisms for the task once the circuit is removed. Additionally, this toy task highlights the significance of studying circuit completeness, which holds great potential in unlearning harmful information: **a complete circuit can help us pinpoint all neurons associated with harmful responses**. \n\n### **Q2: The choice to abbreviate noising-based intervention as Ns and denoising-based intervention as Dn is somewhat unconventional.**\n\nThank you for your suggestion; this is indeed somewhat unconventional. In previous works, *\"noising-based intervention\"* is often abbreviated as *\"noising,\"* and *\"denoising-based intervention\"* as *\"denoising.\"* We abbreviated them as *\"Ns\"* and *\"Dn\"* to reduce the page load. In the revised version, we will replace these abbreviations with *\"noising\"* and *\"denoising.\"*"}, {"review_id": "pXnNKZ0bmX", "reviewer": "Reviewer_ftP7", "summary": "This paper proposes a new way to interpret circuits in terms of three types of logical gate, which help shed light on and tease apart the important concepts of completeness and faithfulness. They explain how these gate types relate to the circuits found by existing methods, and propose a new method that compromises between existing methods to efficiently find better circuits by leveraging this new understanding. They apply these ideas to a number of well-studied tasks in mechanistic interpretability to validate key claims and show that these new concepts and methods can lead to new insights and improved interpretability in practice.", "questions": "See weaknesses above, particularly the last one.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. I found section 2 in particular to be a well-written, clear, and concise summary of background on terms and methods for this paper.\n2. The work is well-motivated—I agree it is important to have a better understanding of completeness and faithfulness, and more generally interpretability, of discovered circuits. And furthermore this seems to be a novel contribution.\n3. The empirical demonstrations seem to be compelling, particularly Fig 3 and the conclusions drawn in 5.1, in showing that these classes of gates exist, can be identified, and can lead to meaningful insights that wouldn’t otherwise be achievable.\n\nWeaknesses:\n1. Legend in Fig 4 is unreadably small\n2. I don’t understand lines 144-148: what does it mean “B can influence the result”? And why should an OR gate remain functional as long as at least one edge remains intact? The function f(A_1, A_2) = A_1 ^ A_2 is not the same as the function g(A_1,A_2) = A_1, so I don’t see why it should be the case that an OR gate doesn’t care if one edge is dropped. Actually, it’s not even clear to me what function is being used when, say, A_2 is “dropped”—I guess it depends on the ablation method, but surely it’s not true that no matter what ablation method is used, ablating one edge in an OR gate doesn’t change it at all?\n3. There is a claim (repeated twice) that the simplest approach to uncovering OR gates would make circuit discovery an NP problem, but no reference or explanation is given.\n4. Line 153 states that any circuit CAN be represented via the proposed gates, but I don’t see how that means that every circuit IS represented via the proposed gates in terms of the nodes and edges it is actually defined by. Like, in order to represent a given circuit via only these gates, it seems you’d have to make a new graph that is computationally equivalent to the old graph but only uses these three gates; it’s not clear how to do this, nor that one would want to do this, since nodes and edges in the new graph will no longer have the same interpretation as those in the old graph.\n5. I think I have a high-level, very fundamental point of confusion about this paper. It seems to use the language of binary computation throughout (e.g., words like “logic” and even the names of the gates “and”, “or”), yet as far as I know this is not what the circuits people discover look like, i.e., the information being passed along edges is not binary, but instead is continuous, and in general multidimensional. I think this must be the case in their experiments as well, since they use GPT2-small, and Fig 6’s nodes are entire attention heads or MLPs. So then is the binary/logical language just sort of figurative/suggestive for classifying the components of these circuits and interpreting them? This disconnect between binary intuition/motivation and the reality of non-binary components in actual circuits seems to be unaddressed in the paper, which I found surprising given that it seems to otherwise be clearly and thoughtfully written—I feel I am missing something simple but major, which may also account for a number of weaknesses I listed above. So if the authors can clarify this, it could significantly impact my score.", "was_revised": true, "final_justification": "I appreciate the authors' explanations and now feel I understand the paper's contribution much better. I think the authors present an interesting idea, but now that I understand these gates better I'm a bit less convinced of their interpretability impact, so I will raise my score only to a 4.", "rebuttal": "Thank you for your review. From your feedback, we understand that your **primary concern** lies in how the circuit gates model \"binary-like\" mathematical structures from continuous values (Q2, Q5). Your questions have provided valuable insights for improving the clarity of our paper, for which we are sincerely grateful. Below, we will first focus on addressing the modeling of circuit gates, followed by responses to the other issues you raised. \n\n### **Q1: This disconnect between binary intuition/motivation and the reality of non-binary components in actual circuits seems to be unaddressed in the paper. (weakness 2 and 5 in review text)**\n\nThank you for your suggestion! We will reinterpret the logical gates from the perspectives of Ns (Nosing) and Dn (Denoising) for you. Specifically, for any given dataset, we can derive two circuits: $C_{Ns}$ and $C_{Dn}$, using Ns and Dn. By examining the intersection of $C_{Ns}$ and $C_{Dn}$, we obtain three subcircuits:\n\n- **Subcircuit 1**: edges that are present in $C_{Ns}$ but absent from $C_{Dn}$.\n- **Subcircuit 2**: edges that are present in $C_{Dn}$ but absent from $C_{Ns}$.\n- **Subcircuit 3**: edges that are shared between $C_{Ns}$ and $C_{Dn}$.\n\nFor these three subcircuits, we separately calculated the changes in KL divergence between the original output and the new output when one or two edges are ablated. The following three tables present the mean values of the samples obtained using the EAP method on the IOI dataset. For each subcircuit, we randomly selected 30 \"three-node\" ($A1, A2, B$) samples, with the structure $A1 \\rightarrow B \\leftarrow A2$.\n\n**subcircuit 1** (edge1=$ A1 \\rightarrow B$, edge2=$ A2\\rightarrow B$):\n| edge1 | edge2   |($\\Delta KL$)|\n| ------------- | --------------|----------------------------  |\n| remain    |  remain    | 0.50       |\n| remain     |  ablate    | 0.02       |\n| ablate     |  remain    | 0.04       |\n| ablate     |  ablate    | 0.00       |\n\n**subcircuit 2**:\n| edge1 | edge2   |($\\Delta KL$)|\n| ------------- | --------------|----------------------------  |\n| remain     |  remain   | 0.28       |\n| remain     |  ablate    | 0.27      |\n| ablate     |  remain    | 0.27       |\n| ablate     |  ablate    | 0.00      |\n\n**subcircuit 3** \n| edge1 | edge2   |($\\Delta KL$)|\n| ------------- | --------------|----------------------------  |\n| remain     |  remain    | 0.65       |\n| remain     |  ablate    | 0.32       |\n| ablate     |  remain    | 0.36       |\n| ablate     |  ablate   | 0.00      |\n\nAll three subcircuits exhibit a fundamental pattern: the effect on the output is maximized when both edges are retained, and it drops to zero when both edges are ablated (as there is no clean activation left to support the node in this case). However, ablation of a single edge yields divergent outcomes:\n\n- In **subcircuit 1**, ablating either edge **nearly eliminates** the effect on the output.\n- In **subcircuit 2**, ablating either edge has **almost no impact** on the output.\n- In **subcircuit 3**, ablating either edge leads to **a noticeable degradation** in the output.\n\nTo formalize this, we define a **state variable** where (see **(state)** in three tables):\n- **state = 1** denotes that an edge or node is **active**/**retained**/**exerts an effect**,\n- **state = 0** indicates that it is **inactive**/**ablated**/**has no effect**.\n\nGiven that **subcircuit 3** exhibits a graded influence on the outcome, we further introduce:\n- **state = 2** to represent a significantly greater effect than **state = 1**.\n\nWith these definitions, the combinations of states in the three subcircuits correspond respectively to the **truth tables** of an **AND gate**, an **OR gate**, and an **ADDER gate**, as the following tables. \n\n**subcircuit 1 (AND gate)**:\n| edge1 state | edge2 state   |receiver state |\n| ------------- | --------------|----------------------------  |\n| **1** (remain)    |  **1** (remain)    | **1** ($\\Delta KL$=0.50)    |\n| **1** (remain)    |  **0** (ablate)    | **0** ($\\Delta KL$=0.02)     |\n| **0** (ablate)     |  **1** (remain)    | **0** ($\\Delta KL$=0.04)    |\n| **0** (ablate)     |  **0** (ablate)     | **0** ($\\Delta KL$=0.00)    |\n\n**subcircuit 2 (OR gate)**:\n| edge1 state | edge2 state   |receiver state |\n| ------------- | --------------|----------------------------  |\n| **1** (remain)    |  **1** (remain)    |**1** ($\\Delta KL$=0.28)       |\n| **1** (remain)    |  **0** (ablate)    | **1** ($\\Delta KL$=0.27)        |\n| **0** (ablate)    |  **1** (remain)    | **1** ($\\Delta KL$=0.27)         |\n| **0** (ablate)   |  **0** (ablate)   | **0** ($\\Delta KL$=0.00)      |\n\n**subcircuit 3 (ADDER gate)** \n| edge1 state | edge2 state   |receiver state |\n| ------------- | --------------|----------------------------  |\n| **1** (remain)    |  **1** (remain)    | **2** ($\\Delta KL$=0.65)      |\n| **1** (remain)    |  **0** (ablate)   | **1** ($\\Delta KL$=0.32)       |\n| **0** (ablate)   |  **1** (remain)    | **1** ($\\Delta KL$=0.36)       |\n| **0** (ablate)   |  **0** (ablate)   | **0** ($\\Delta KL$=0.00)      |\n\nAccordingly, we refer to **subcircuit 1 as the AND gate**, **subcircuit 2 as the OR gate**, and **subcircuit 3 as the ADDER gate**. In existing works [1][2][3], **similar definitions** of the OR gate have been proposed, providing a **solid theoretical foundation** for our work. In contrast to these studies, **our contribution** lies in the fact that, in addition to the OR gate, we also introduce the AND and ADDER gates, thereby endowing **all nodes and edges** in the Ns and Dn circuits with **logical properties**.\n\nMoreover, this phenomenon is **not incidental**; it is consistently observed across all implementations of both Ns and Dn. In Appendices A and B, we prove that the emergence of AND, OR, and ADDER gates arises from mutually exclusive properties of Ns and Dn, and that they represent an **intrinsic logical structure** of the circuit graph itself.\n\nFinally, as shown in the table above, this also explains why the OR gate has almost no change on the effect when one of its edges is removed (when edge1=1,edge2=0, or conversely edge1=0,edge2=1). \n\n**reference:** \n\n*[1]. Conmy, Arthur, et al. \"Towards automated circuit discovery for mechanistic interpretability.\" NeurIPS 2023.*\n\n*[2]. Wang, Kevin Ro, et al. \"Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 Small.\" ICLR 2023.*\n\n*[3]. Heimersheim, Stefan, et al. \"How to use and interpret activation patching.\" arXiv 2024.*\n\n### **Q2: Legend in Fig 4 is unreadably small**\n\nThank you for your suggestion. We will include a table with specific quantitative numbers in revised versions to avoid making the figures too complex. \n\n### **Q3: There is a claim (repeated twice) that the simplest approach to uncovering OR gates would make circuit discovery an NP problem, but no reference or explanation is given.**\n\nThank you for your suggestion. Due to the differences in circuit algorithms, this issue cannot be fully proven mathematically. However, we will provide some additional explanation: we treat **each ablation** as $O(1)$. Assuming the language model contains $N$ nodes, if we need to use all possible intervention combinations to obtain a complete circuit, the time complexity would be $O(2^N)$, which far exceeds polynomial time. However, **different strategies can optimize the solution verification process to varying degrees**. For example, EAP only requires $O(N)$ time to verify whether the circuit is complete, while Edge-pruning involves gradient descent, making its time complexity difficult to estimate. Additionally, greedy search can only perform a greedy verification in $O(N)$ time rather than a thorough verification. Therefore, we ultimately classify this problem as NP problem.\n\n**In the revised version, we will incorporate these analyses into the main text to provide a simple explanation for the \"NP problem.\"**\n\n### **Q4: Line 153 states that any circuit CAN be represented via the proposed gates, but I don’t see how that means that every circuit IS represented via the proposed gates in terms of the nodes and edges it is actually defined by. Like, in order to represent a given circuit via only these gates, it seems you’d have to make a new graph that is computationally equivalent to the old graph but only uses these three gates; it’s not clear how to do this, nor that one would want to do this, since nodes and edges in the new graph will no longer have the same interpretation as those in the old graph.**\n\nThank you for your question. In fact, representing a circuit using three types of gates does **not require making a new circuit**. We simply need to analyze the relationships between the edges in the current circuit, classifying them as one of the AND, OR, or ADDER gates based on their effect on the receiver node. As the simplest case, as shown in the tables in Q1, we only need to compute the impact of these edges on the receiver node in order to determine whether it belongs to the AND, OR, or ADDER gate.\n\nTherefore, the circuit with three types of gates is **structurally identical to the original circuit**. The reason we construct a new circuit using Ns+Dn is that the existing circuit is incomplete (due to the nature of Ns, which misses some branches of the OR gate). Moreover, as shown in the circuit graph in **Appendix G**, in the IOI task, we confirmed that the circuits completed using our method **contain all the nodes and edges originally present in the IOI circuit**. The additional components are almost entirely edges corresponding to \"OR\" gates that were not identified by the previous algorithm. As a result, the meaning and functionality of each edge and node remain consistent with the original IOI circuit, still corresponding to functions such as the duplicate head, induction head, and S-inhibition head."}]

Author rebuttal:

Meta-review: This paper reframes circuit discovery in mechanistic interpretability by introducing three logical gate types as abstractions of how components behave under noising and denoising interventions. The authors argue that incompleteness in existing methods largely stems from failure to detect OR gates, and propose a combined Ns+Dn approach that allows circuits to be recovered with greater completeness. Empirical studies on GPT-2 small across canonical interpretability tasks show that the Ns+Dn framework yields circuits that are more complete and less random across seeds, while maintaining comparable faithfulness. The work also explores the distribution and roles of these gates, suggesting OR gates capture redundancy, AND gates combine distinct functions, and ADDER gates provide additive contributions.

The reviewers were divided. One reviewer (mnpW) maintained a strong rejection, citing conceptual flaws in presenting AND/OR/ADDER as "fundamental" and objecting to the incompleteness of the definitions and completeness metrics. However, the other reviewers judged that the clarifications and revisions provided by the authors during the rebuttal period resolved most concerns. In particular, khCH and ftP7 initially shared mnpW’s confusion about definitions but accepted the authors' clarification that gates describe ablation-induced behavior rather than literal logical functions. Similarly, reviewers xbit and mrxZ appreciated the new completeness analysis and the demonstration of practical value in model unlearning. Across the discussion, consensus formed that the work is conceptually interesting, well-motivated, and empirically consistent, though its claims should be carefully delimited.

Strengths of the paper include a clear conceptual framing of incompleteness, a simple but effective Ns+Dn intervention strategy, extensive empirical validation across multiple circuit discovery baselines, and thoughtful exploratory analysis of the roles of different gate types. The rebuttal further strengthened the case by demonstrating that greater completeness can enable more thorough unlearning of harmful circuits.

The weaknesses remain worth noting. The framework is incremental in technical depth, since Ns+Dn is a straightforward combination of existing interventions. The definitions of gates required multiple rounds of clarification, and some readers may still find the logical analogy overextended. The empirical studies are limited to GPT-2 small, and faithfulness is not improved relative to prior methods, which may limit adoption by practitioners focused on that metric. Finally, ADDER gates function as a broad "catch-all" category and their interpretability value is less compelling than that of OR or AND gates.

Overall, the clarifications and revisions provided by the authors during the disuccsion period  and the potential impact of framing circuit completeness through the lens of logical gates makes me to recommend a weak acceptance (i.e., poster). The main recommendation to the authors is to revise the presentation carefully by making explicit that gate definitions describe ablation states rather than intrinsic node functions and clearly delimiting the scope to circuits derived from Ns and Dn, while acknowledging that other gate types may exist. Finally, the authors should improve the readability of figures and include quantitative tables to support claims.
Decision: Accept (poster)